## EQSDebugger saves the day! Kinda.

I wanted to share a short story of fixing a bug in EQS.

A colleague for the Paragon dev team IMed me asking what the EnvQueryManager is and sent me this image:

The number marked in red is the single call cost in milliseconds. Yeah, it’s pretty high. It’s enormous in fact! With EQS supporting time slicing I knew this had to be a bug so I’ve started digging. By looking at the code my hunch was that the unexpected cost was related to the new-ish EQS profiling functionality since time it takes is not included in the loop’s time budget. So I’ve added stats to the EQS debugger functions to confirm my hunch. Here’s what I gotten:

The last column is the call count within a frame.. I’m pretty sure we’re not suppose to try to log over 600k queries a tick ;)

The core issue turned out to be us not accounting for EQS queries that have been aborted before the main EQS loop had been triggered. This way if we finished all active queries, and skipping the aborted ones, the loop “thought” there was still some more work to do, up until it run out of time budget. Only thanks to a minor bug in EQS debugger’s usage (the fact that it can end up logging the same query multiple times after the query has finished) and it causing such a huge performance drop, the core, deeper EQS bug has been found. So, in essence, EQS Debugger uncovered and helped nail down the bug. Well done, EQSDebugger!

## Fixing EQS with math

(Warning, there’s some math involved later in the post! You’ve been warned ;) )

I’ve recently found a little inconsistency in the way EQS normalizes scores (if you have no idea what EQS is see here, in short it’s an spatial reasoning system in UE4). It’s not a bug per se, it doesn’t result in eliminating wrong items, or influence items’ relative score. But I did notice it because it may result in not-totally-worthless items getting a score of 0. Let me give you a practical example.

I was looking into changing the way bots in Paragon pick their targets (which is done via EQS). I wanted to try to do some additional, non-EQS processing on enemies that scored more than 0.9 (90% of the best score). However, while looking though a vislog recording of a bot game, I’ve notice this:

Having an enemy score a total of 0 points caught my attention. So I’ve stared digging. Here’s more query details from the log:

The Score column shows the total score of an item (an enemy actor). Every Test columns first show the normalized score followed by the raw result of a given test. At a first glance everything’s all right. The negative normalized score comes from some tests having negative result multiplier to indicate that smaller values, closer to zero, are to be preferred. Something doesn’t feel right though – why is Muriel’s score $0$ while in the last test she had second best result?

Here’s how we come up with a total score of an item:

1. calculate the sum of all normalized test results for a given item
2. offset it by the lowest score (or $0$, whichever is smaller)
3. divide it by the score span

It’s all well and good until you have negative scores. If lowest total score is $\lt 0$ then after offsetting and normalizing the lowest scoring item will always get 0, regardless of how well it did on some of the tests. It can even lead to very misleading results! Imagine having three items of respective total scores of $-0.2, -0.1, 0$ – the presented scoring normalization algorithm will result in final scores of $0, 0.5$ and $1$! Not at all representing relatively similar performance of items being scored.

Not to mention the whole scoring falls apart if the best total score is also negative.. Wow, looks like I’ve found an interesting bug :D

Fixing the issue is a pretty straightforward affair. While normalizing test results, if a user configured weight is negative instead of using $w \cdot v$ (where $w \lt 0$ is the weight and $v \in [0,1]$ is normalized test value of an item) we just use $\mid{w}\mid \cdot (1 - v)$. This results in the expected reversing of scores (lower is better) and has an added benefit of making the result positive.

“Why this post then? Just fix it, guy!” I hear you say. Well, normally I would. But the problem is that EQS is widely used in both Epic’s internal projects (most notably Paragon and Fortnite) as well as a number of external projects (I can tell by number of questions people ask ;) ). Messing up EQS scoring would make many developers unhappy/miserable/angry (pick at least one). On the other hand I’m pretty use the solution is good, but how do I test it? I can come up with a number of test cases, but that’s not enough, there’s always something that test cases would not cover. If only there was a way to prove something beyond any finite test set… MATH!

Now it has been many (many, many) years since I last proven anything mathematically, so what I’m about to present might be rough around the edges, but I’m pretty sure there’s no holes in the reasoning (and if there are please let me know!).

All right, so what do I need to prove? Obviously the suggested change will affect the final scores, that’s the whole point. But what is the property we don’t want to change? We want to make sure the final order of scored items is preserved. Or in other words (and here’s where the math starts):

$$\forall{x_{n},x_{m}\in X} \quad s(x_{n}) \leq s(x_{m}) \Longrightarrow s'(x_{n}) \leq s'(x_{m})$$

where $X$ is the set of all items being scored, $s(x)$ is the “old” scoring function that for $k$ tests looks like this:

$$\begin{matrix} s(x) = \frac{1}{\beta} \sum_{i=0}^{k}{t_{i}(x)} \\ t_{i}(x_{n}) = w_{i}\cdot v_{i}(x_{n}) \end{matrix}$$

where $v_{i}(x)$ is the $i$-th’s test normalized score of item $x$ and $\beta$ is the normalization term, the total score span. The “only” difference between $s(x)$ and $s'(x)$ is the $t$ function. We define the new scoring function as follows

t_{i}'(x_{n}) = \left\{\begin{matrix} w_{i}\cdot v_{i}(x_{n}) & w_{i} \geq 0 \\-w_{i}\cdot (1-v_{i}(x_{n})) & w_{i} \lt 0 \end{matrix}\right.
We see that $t$ and $t'$ differs only when $w_{i}\lt 0$ and since

$$\frac{1}{\beta} \sum_{i=0}^{k}{t_{i}(x)} = \frac{1}{\beta}\left(\sum_{j\in K_{-}}{t_{j}(x)} + \sum_{l\in K_{+}}{t_{l}(x)}\right )$$

where $K_{-}$ and $K_{+}$ represent the sets of negatively and positively weighted tests we can focus on negative weights from this point on.

We’re almost there! All that’s left to show is that if:

$$\begin{matrix} s(x_{n}) \leq s(x_{m})\\ \frac{1}{\beta} \sum_{i=0}^{k}{t_{i}(x_{m})} - \frac{1}{\beta} \sum_{i=0}^{k}{t_{i}(x_{n})} \geq 0\\ \sum_{i=0}^{k}{t_{i}(x_{m}) - t_{i}(x_{n})} \geq 0 \\ \sum_{i=0}^{k}{w_{i}\cdot (v_i(x_{m}) - v_i(x_{n}))} \geq 0 \end{matrix}$$

then

\sum_{i=0}^{k}{t_{i}'(x_{m})-t_{i}'(x_{n})} \geq 0

and since we’re considering $w_{i} \lt 0$, then using $(1)$ we can expand $(2)$ to

$$\begin{matrix} \sum_{i=0}^{k}{-w_{i}\cdot (1-v_{i}(x_{m})) + w_{i}\cdot (1-v_{i}(x_{n}))} \geq 0 \\ \sum_{i=0}^{k}{-w_{i} + w_{i}\cdot v_{i}(x_{m}) + w_{i}-w_{i}\cdot v_{i}(x_{n}))} \geq 0 \\ \sum_{i=0}^{k}{w_{i}\cdot (v_i(x_{m})-v_i(x_{n}))} \geq 0 \qquad q.e.d \end{matrix}$$

<mic drop> ;)
If you find anything wrong with the prof please let me know!