Sunday, February 21, 2010

Google AI bot

Well I achieved my initial goal of getting into the top 10, only to be hoinked out to around 100 as the opposition got a lot stronger once the maps changed to avoid draws.

The bots that seem to beat mine have great depth in their searches. I'm using minimax with alpha beta pruning which is probably what they're using so search depth isn't the issue. So I figure their evaluation functions are finding the better moves at the same depths. My rudimentary 'most available squares' approach needs an upgrade. Without adding too much time as the evaluation function is called quite frequently (around 10000 times per second).

With the middle island forming a significant 'block' I need to get better at luring them my way, cutting their approach off then going around the other side and cutting at a point favourable to me. I'm going to try changing the evaluation function that evaluates which player is first to each square. This should give me a better sense of where a future border will be and hence try to maximize my player's area.

Link to my bot

Wednesday, February 10, 2010

Google AI Competition

Hmmm, how good are AI comps? I am letting my inner geek take over for the next few days as I put the evil stumac bot in Google's AI comp.

I am currently 30th (out of 415 entrants) with a few things still to do to really make my bot competitive.

To begin with I implemented a basic strategy and that had me at 90th out of 400. When I say basic, I mean really basic (code to come after the competition).

I then added a minimax look ahead, this currently looks ahead 9 moves, a bug was causing me to lose games.

So now I will:
  • alpha beta prune my minimax.
  • upgrade my evaluation function.
  • add a 'in same area' check and revert to flooding if in separate areas.
  • Add a timing check (if possible) to give a good answer before timing out.
Should be fun!

Hopefully this should be able to get us into the top 10.