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}


\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!

Leave a Reply

Your email address will not be published. Required fields are marked *