The Quixotic Engineer

I had a chance to participate in a number of events at the CS games, but the most interesting by far was the A.I. competition. All I had been told about the event beforehand was that in past years they had programmed the A.I. for Pac-man ghosts (enough for me to know that I HAD sign up.) Fortunately this year’s challenge also did not disappoint, as we were asked to program the A.I. of the Light Cycles from Tron.

The match was played on a roughly 30×30 grid where each cell was either empty, a wall or a cycle. Each player was given one second every turn to decide whether to move forward, left or right, with each movement leaving a wall in place behind. The cycle that could survive longest without running into a wall or another cycle was deemed the winner.

The competition took place over two sessions, the first worth 25% and the second 75%. The A.I.s from all thirty schools went head to head in a round robin tournament at the end of each day. With this in mind, my teammates and I decided to apply what we were learning in Software Processes and grow the program iteratively. This was a wise decision; we had a simple yet effective working model ready for the first competition while many groups were still debugging their more complex algorithms. In the end, we tied for 6th on the first day and 10th on the second.

After the competition, however, I found myself still thinking about this problem. It’s a twist on pathfinding, as there’s no set destination, and could nearly be described as a longest path problem. The ideal solution has to be flexible enough to accommodate both narrow corridors and open spaces. Our algorithms didn’t even take into account the position of the enemy, mostly because we weren’t sure what to do with that data.

I’ve written from memory the pseudocode for our four iterations, as well as a little something about their performance, strengths and weaknesses. I present this in the hopes that you too will get this problem stuck in your brain, and will soon return to comment with your wild and crazy ideas about the best Tron A.I.

Note: I’ve tried to keep my pseudocode notation consistent and as close to plain English as possible. They looked ugly when embedded, so click through to read each txt.

[A.I Competition – 1st Iteration]

We began with a very simple algorithm that could look exactly one square ahead. It would therefore never run into a wall unless it was the only possible move. It’s simple and it works reasonably well, but with no foresight it quickly gets caught in traps that it should have avoided. There’s really not much else to say about it, it was a stepping stone to greater things.

[A.I Competition – 2nd Iteration]

Our next plan was to look in a straight line in every direction, and turn in the direction with the most empty space. Another simple yet solid algorithm, but with more foresight than the first. This was what we ended up submitting for the first day’s competition, so we have a glut of experimental data on it. Namely, we discovered one common situation that it handles very poorly.

We lost two of our first round matches getting caught in this scenario. Any human can see that the correct choice in the above situation is to turn left, but algorithm 2 only evaluates one block left and one block forward. Since we hard coded it to move forward in the event of a tie, it traps itself and dies in two turns. Clearly a robust A.I. would need to evaluate length around corners, a concept that we applied to our next iteration.

Since I got a little carried away with the diagram, I’ll finish writing about our two final iterations this weekend. Stay tuned.