The Quixotic Engineer

I think I had best wrap up this series before I completely alienate my non-programmer readers. Firstly, I have an algorithm by fellow blogger and mathematician Tim Sell of Planet Nectarius.

[A.I Competition – Tim’s Algorithm]

What I did was get 3 values for all the empty spaces to the left, right and in front of the player. To be “in front” the empty spaces must be connected to the forward move square and it must be forward of the player. So each connected space is bounded by a rectangle to one side of the current cycle position. I then regard each rectangles emptiness value as half if the nemesis cycle is within that rectangle. Then I arbitrarily decide to move to the square which has the second highest empty space value associated with it. […] Basically the idea is to cut of the nemesis cycle from the empty space without retreating into it.

→ Read more

Since I returned from the CS games a few weeks ago, I’ve been vigorously discussing the Tron A.I. problem with anyone who would listen. Much of this took place on the skrud.net forums, where I had a chance to debate with Alexei and Andrew of the other Concordia team. Their team tied for third place on the second day, and they had some really interesting ideas. I’ll be posting snippets of our discussion here, including the pseudocode for their algorithm.

In part 2 of this series, I wrote about how the recursive Algorithm 4 was memory intensive because it needed to clone the entire map at every step. Alexei, however, thought of a very clever way to get around this problem by implementing backtracking.

→ Read more

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.

→ Read more

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.

→ Read more

I’ll write something a little more detailed later this week about the competitions themselves, but for now here’s a weekend in pictures

→ Read more