To enumerate the possible solutions, we perform a breadth-first search, simulating the game state for each action at each time step, and recording any path through the breadth-first graph that ends with a node representing Mario reaching the right side of the screen. Of course, there are an infinite number of such solutions because of the option to do nothing for any amount of time, and aside from that, this graph would expand exponentially and become intractable very quickly. To avoid both of these issues, we first compute the optimal solution using the A* search algorithm (Hart, Nilsson, & Raphael,
1968), using the following heuristic for evaluating the fitness
h of each node in the graph:
\begin{equation}\tag{4}h\left( {x,y,t,d} \right) = 100,000 - \left( {\left( {t + e\left( x \right)} \right) \times 100} \right) - \left( {d \times 3,000} \right)\end{equation}
where
x and
y are the coordinates of Mario in the level,
t is the amount of time currently elapsed, in seconds, and
d is the number of times Mario has received damage.
e(
x) is a function for estimating the amount of time remaining before Mario reaches the level end and is simply calculated as the remaining distance to the goal divided by Mario's maximum speed. Note that this equation is the same as
Equation 3, except that the time component is broken down into current time and estimated remaining time, which is available to the model. The players had no direct information about the estimated remaining time. However, all of the levels are the same length, so players could have noticed this and gained an approximate sense. The model computes the optimal solution to
Equation 4 using A*, which is used to limit the breadth-first search by evaluating each node using the same fitness function. Any node whose fitness is lower than the optimal solution's fitness by more than a threshold
Display Formula\({\delta _{\rm fitness}}\) is pruned, reducing the graph to a manageable size. Even with this restriction, the size of the search tree becomes extremely large, and the search must be performed several times on every frame. Because of this, it became necessary to set this threshold to 0 to satisfy computational constraints. To ensure that this did not negatively affect our results, we compare the results of our saliency models using a higher threshold, but using data from a small subset of our participants, in the Effect of
δfitness on NSS Scores subsection.