Mission Accomplished: Time to Play - Programming GPS and OpenStreetMap Applications with Java - page 204

root node represents the runner's current position and its child nodes reect
the next possible moves. Then, every move can be scaled with the heuristic
and the best move is chosen.
A further development cycle could introduce game triggers to the tree
thread, which drop the unapplied branches, move the executed move to
the root, and supply the latest game parameters. In the end, the runner is
continuously building a tree, and the server request to make a move triggers
the selection of the best move.
13.4.3 AIChaser s
The chaser template is already prepared as described in Section 13.4.1.
The implementation challenge is different and more complex than that
of the runner. For one thing, all chasers form a team and the order of their
moves actually doesn't aect the game. First, the runner moves and then
all chasers make their move.
In order to implement a team strategy, one heuristic function can be
created to calculate all chasers' moves. The function is more complex,
since the runner's location is only published by the server every ((round
-2)%x==0) with x being 3, 4, or 5 for different skill levels. While the
runner is hidden, the chasers can create an estimation tree for all possible
runner moves.
While the runner tree can search the tree by depth, the chasers' tree is
more effective by searching the full width of each round. Before entering
the game, the chasers can determine the best positions on the game map to
reach any other station quickly and subtract two moves to get there as soon
as the runner shows up. One of the main goals is to minimize the total
distance, which is the sum of all chaser' distances to the runner. Addi-
tional criteria can minimize the escape options and avoid different chasers
from blocking each other. Yet another aspect to consider is the (hidden)
time consumption of route calculations. The results of each calculation
could be stored in a matrix to access previous results and avoid redundant
calculations.
Finally, a technical solution has to be found to communicate each cal-
culated move to the relevant player. For example the search thread could
be placed in one leading player, who broadcasts the move to its followers.
With the normal London Chase parameters of one runner, three{four
chasers, and 199 stations, the calculation time of one minute can be a
challenge. The tournament rounds can begin with two minutes and slowly
reduce the time to move, which will segregate the better players. The game
complexity can be raised by, for example, introducing barriers to block the
runners best escape routes, features for ferries, and tickets for features can
be added.