Category Archives: C#

Improving the C# Ants AI Challenge starter kit for debugging support

The C# starter kit for the current AI Challenge works well out-of-the-box, but doesn’t easily let you debug your bot live. There’re a number of ways of supporting live debugging, so I chose one of the more interesting.

The aim is to host the bot in a Visual Studio debugging session, then write a proxy that the Python game script runs which relays commands and responses between the Python script (which expects IO through stdin and stdout) and the bot being debugged.

To start this, we need to do a little refactoring to the starter kit classes. Our aim is to decouple the starter kit from talking directly to Console.In and Console.Out. This only happens in a couple of places so is reasonably straightforward, and the methods called are few.

So, let’s define an interface representing a bot’s connection to the game:

public interface IGameDataPipe
{
   string ReadLine();
   void WriteLine(string s);
}

We’ll also implement a console-based version of this:

public class ConsoleGameDataPipe : IGameDataPipe
{
   public string ReadLine()
   {
      return Console.In.ReadLine();
   }    

   public void WriteLine(string s)
   {
      Console.Out.WriteLine(s);
   }
}

We then want to modify the Ants class to use our interface instead of talking directly to the Console class. First off, we add a member variable of type IGameDataPipe and default it to our console version. Then we find everywhere that calls Console.* and replace it with an equivalent call on the IGameDataPipe member.

There’s one other place in the starter kit that talks to the console directly – the base class for our bot implementation in Bot.cs. Here, IssueOrder is directly calling Console.WriteLine. It’d be great if we could avoid having to expose the Bot class to the concept of how to present its data to the game layer, so I’d like to avoid pushing an IGameDataPipe into the Bot. Instead we’ll expose this through a delegate and event – when the bot wants to issue an order to mutate the game state it raises the event with appropriate arguments and the Ants class figures out what to do with it.

That takes our definition of Bot to looking something like this:

public abstract class Bot {    
   public delegate void OrderIssueHandler(Location loc, Direction direction);
   public event OrderIssueHandler OrderIssued = delegate { };
   public abstract void DoTurn(IGameState state);

   protected virtual void IssueOrder(Location loc, Direction direction)
   {
      this.OrderIssued(loc, direction);
   }
}

We then modify the Ants class to hook the event upon entering PlayGame, with the handler delegating to the IGameDataPipe.

So after all that we’ve achieved nothing functionally different but we have managed to decouple the bot implementation from the actual mechanism by which it talks to the Python game script.

This lets us replace our console in-out implementation with something else. We could use IPC here, WCF remoting, anything. I’m going with TCP for this example. Our server and client implementations can be very simple because the way our IGameDataPipe is consumed is also very simple. The original Console-based client worked just fine using the blocking IO provided by the Console class, so we can replicate the same. First things first – let’s modify Ants.cs with a new constructor that lets us override the IGameDataPipe to be used for comms with any other implementation.

// Default to the console, allow caller to override as required.
IGameDataPipe dataPipe = new ConsoleGameDataPipe();

public Ants()
{
}

public Ants(IGameDataPipe pipe)
   : this()
{
   this.dataPipe = pipe;
}

Now on the server side (that is, the side that’s hosting the bot) we simply wrap a TcpClient with a StreamReader and StreamWriter and expose ReadLine and WriteLine methods delegating their work to the two Stream* classes.

public class TcpIPGameDataPipe : IGameDataPipe
{
   StreamReader _reader;
   StreamWriter _writer;
   TcpClient _client;    

   public TcpIPGameDataPipe(TcpClient client)
   {
      _client = client;
      NetworkStream stream = _client.GetStream();
      _reader = new StreamReader(stream);
      _writer = new StreamWriter(stream);
   }

   public string ReadLine()
   {
      return _reader.ReadLine();
   }

   public void WriteLine(string s)
   {
      _writer.WriteLine(s);
      _writer.Flush();
   }
}

On the client side (that is, the shim that the Python script talks to) we need to relay stdin over a TCP connection, and relay incoming data from the TCP connection to stdout. This is marginally more involved than the server implementation as we need to thread these operations since they’re being initiated from one of the Python script on one side and the TCP connection on the other. Still, the code’s straightforward:

public class ConsoleTcpIPForwarder
{
   TcpClient _client;
   StreamWriter _writer;
   StreamReader _reader;    

   Thread _readThread;
   Thread _writeThread;

   public ConsoleTcpIPForwarder(int port)
   {
      _client = new TcpClient(new IPEndPoint(IPAddress.Loopback, 0));
      _client.Connect(new IPEndPoint(IPAddress.Loopback, port));

      NetworkStream stream = _client.GetStream();
      _reader = new StreamReader(stream);
      _writer = new StreamWriter(stream);
   }

   public void Start()
   {
      _readThread = new Thread(ReadForwarder);
      _writeThread = new Thread(WriteForwarder);

      _readThread.Name = string.Format(“{0} read thread”this.GetType().Name);
      _writeThread.Name = string.Format(“{0} write thread”this.GetType().Name);

      _readThread.Start();
      _writeThread.Start();
   }

   private void ReadForwarder()
   {
      while (true)
      {
         _writer.WriteLine(Console.ReadLine());
         _writer.Flush();
      }
   }

   private void WriteForwarder()
   {
      while (true)
      {
         Console.WriteLine(_reader.ReadLine());
      }
   }
}

Now we’re almost home. Our shim implementation simply needs to kick off a ConsoleTcpIPForwarder and leave it running, which will in turn forward all console input to the network and network traffic back to console. Our server implementation that hosts the bot just needs to listen for incoming TCP connections made by the shim and when one’s initiated kick off a new Ants game using the TcpIPGameDataPipe. We’ll keep this in a busy-loop that runs a game then waits for more connections to avoid having to keep kicking off the Visual Studio side of things.

The only final comment here is that we want to keep out TcpIPGameDataPipe in a separate assembly to avoid breaking compilation of our main bot assembly when uploaded to the server (as it’s unlikely that it has the required System.Net* assemblies available for compilation against).

I’ve combined both the forwarding client and the game-host server in the same executable for straightforwardness, deciding whether to spin up the server or forward from the client based on whether any command-line params are supplied (none = client, anything, say ‘-server’ = server).

To run, we start the shim process in Visual Studio (with a command-line parameter of ‘-server’ to force it to go into server mode) and then run the Python game script pointing it at our shim exe instead of the actual bot exe. We can now put breakpoints into our bot code and have them fire just as we want.

The modified package is available here.

AI Challenge 2011

I’ve not taken part in an AI Challenge before but with the next few weekends looking pretty quiet I decided to sign up. The latest challenge, run as a collaboration between Google and the University of Waterloo Computer Science Club, simulates a competitive environment in which two or more ant colonies fight for survival on a selection of maps.

The contest is distinctive for the broad range of languages supported. You code up your entry, zip it and upload it where it is compiled (where necessary) on the server and put into a queue to fight against other players’ creations. There are starter packages provided so that you don’t have to parse all of the incoming data and wrap up the output.

You control an ant colony located somewhere on a map. By commanding your ants to move to and collect food you spawn new ants from your anthills. Survival is key, but a scoring system also encourages attacking behaviour – get close enough to another ant and you’ll attack it, and if you manage to land on an undefended ant-hill that hill is lost and no longer produces ants for the opposing player.

Your code has a limited amount of time to perform its processing per time-step, and if it exceeds that time then your bot is eliminated. Equally if your bot crashes during execution then you’re also out. Winning or losing changes your rank based upon the Trueskill algorithm and your bot will keep being queued for more battles in a round-robin fashion for a number of days after you upload it.

I’ve decided to try a diffusion approach which I suspect many others will be trying too. The idea is reasonably simple – goal items in the world exude a digital pheremone that makes them attractive to your ants, and this pheremone is diffused throughout the map over time by simple averaging in adjacent cells. For example, a food item might have a score of 1000 scent units in time step 0; in time step 1 its neighbours will have attributed themselves some proportion of that scent, and in time step 2 their neighbours will also be imbued. If you consider the scent of food to be a surface then we iteratively smooth out sharp peaks caused by goal items throughout the rest of the surface.

That means that we can find food or unexplored squares (if we associate a suitable attraction score to cells we’ve not yet visited) by simple hill-walking per-ant. When an ant is deciding where to move it examines the squares to the north, west, east and south of it and picks the direction with the highest scent value. It also means that we get pathfinding for free by clamping the ability of wall-cells to propagate scent to zero – any other cell adjacent to a wall cell will have a higher attractiveness, so the ant will not consider the move.

There are substantial kinks to work out in my implementation but I’ve only just started. For now, my bot (not yet uploaded) seeks only to explore the map without bothering to look for food (though there is enough food that it’ll stumble upon some accidentally fairly often). This video shows the pheremone trails over time; the green on the left is the ‘unexplored’ pheremone, while the red on the right is the ‘food’ pheremone. Just now the ants are configured to consume the unexplored pheremone when they are within a cell such that any ants following behind will seek different routes.

The ants are starting from near the top-left of the map. The green pheremone quickly ramps up across the map even in regions the ants cannot yet see because we do not yet know where the walls are in those sections – ants have a limited field of view. Once we start exploring these regions the wall cells start to clamp correctly and the map topology becomes a lot clearer.

On the red side the food pheremone pulses as new food items are added randomly. When an item is consumed its red signal falls off over a few time units.

The contest closes for new entries in December on the 18th, after which the tournament-proper starts – I’ve enough time to hopefully get something based on this diffusion approach uploaded by then!