The Quixotic Engineer

In my last post I wrote about the simple yet functional algorithms we wrote on the first day of the A.I. Competition. Today I will discuss the two more complex algorithms we developed on the second day and why they were both beautiful failures.

[A.I Competition – 3rd Iteration]

This is where the pseudocode starts to become a little obscure. Essentially, this is a case of algorithm 2 where the scanners can turn exactly once. In other words, at every point along the straight line search we send a second set of scanners out perpendicularly left and right until they reach a wall. We find the maximum value of the sum of a straight and perpendicular scanner and turn in that direction.

In theory this algorithm is more powerful than the one from our second iteration. It looks further ahead, avoiding the situation that prematurely killed our cycle in the first competition. However, in execution, it actually dies a bit faster than the previous A.I. on some maps. The reason for this is that algorithm 3 will often turn faster when filling up an empty space. For instance, in the diagram below, algorithm 2 survives four turns longer in an empty rectangular space.

While the light cycle deathmatch was ostensibly a head to head fight, matches usually degenerated into a race to fill a separate space more slowly than the opponent. Needing to slowly fill empty space was actually much more common than the situation that exposed the flaw in algorithm 2. Algorithm 3 was therefore a bit of a flop.

[A.I Competition – 4th Iteration]

Where algorithm 3’s scanners could turn exactly once, these scanners search the map exhaustively and turn as many times as possible. This is achieved recursively, with each cell calling the check method on the left, right and forward cells. The result is a longest path value for each direction, and the cycle chooses to turn towards the maximum of the three.

However, the moment you allow the scanner to turn more than once you must allow for the possibility of visiting the same cell more than once. Algorithm 4 gets around this by cloning the map at every step. The scanners can leave walls behind themselves on these replicated maps without affecting the real one. Note that the map must be cloned at every recursion and that is is the modified clone that is passed as a parameter to the next step.

Unless some bug in the pseudocode has evaded me, there is no logical error in this algorithm. It will find the longest movement possible on any kind of map, which is exactly what we were looking for. However, there are two big problems with it in execution.

1. If placed in the centre of an empty map with n cells, this algorithm would have a worst case time complexity of O(2ⁿ)* (see Big O Notation.) The resulting calculation would take much longer than one second to process.
2. The entire map is cloned at every recursion, potentially using a tremendous amount of memory. We could slightly improve on this by instead keeping a list of visited nodes, but this list would also need to be cloned. There is a very clever way to get around this problem, but I’ll save it for my next post.

*Finding the time complexity of a recursive algorithm without having real code to test is tricky. I’m basing my analysis on the fact that the longest path problem is NP-complete. Feel free to disagree in your comments, and enjoy the following nerdy song (thanks Skrud.)

Longest Path – Daniel Barrett [download]

Were time and memory not factors, algorithm 4 would be sufficient to find the longest path at every step. In a real time system, however, it’s unfortunately completely useless. Since algorithms 3 and 4 were failures, we were forced to resubmit algorithm 2 for the final competition.

I’ve been discussing this problem with programmers smarter than myself (including the other Concordia team who came in 3rd on the second day) ever since I got back from the CS Games and have learned a great deal in the process. In my next post I’ll be discussing a few of their solutions.