I did a tiny writeup on my profile on aishowdown.com, but I’m not sure what people want to know =]

The first thing I tried was a bot based on potential fields, because the map didn’t have obstacles and potential fields are easy… but I wasn’t getting good results – it was barely beating dumbplayer.py!  This bot was scrapped, never to be seen again.

Then I cobbled together a simple bot based on distance maps, which I’d intended to improve, but after watching it in a handful of practice rounds against other players I realized all of us had many areas on the map with more than 1 chicken.  Any chicken not working for a living had no place in my society.

So I started thinking A*, which might’ve looked like Brixican‘s bot (except I would’ve avoided the 2 chickens 1 farm scenario)…  and then I was thinking Dijkstra, because it would probably be ‘good enough’ to path to the nearest empty/enemy… but then I realized that was also overkill, because all the edge weights are 1, so I went with a simple breadth-first search.

So my BFS bot was humming along, expanding in a pyramid (turtle!), but since I could really only expand from a single space with multiple chickens in 4 directions at once, I added some logic that moved extra chickens… somewhere.  I tried moving them several different places, actually – some variations tried to expand towards money or food or the enemy’s money or food, but ultimately the version which expanded towards the enemy’s spawn beat the rest when I pitted them against each other.  There’s always room for chickens on the front lines.

So that bot was pretty successful but then I suspected that other players would also devise this expand-as-fast-as-possible strategy, so I should prioritize expansion *and* food…  so I added some logic which caused any chicken not already issued an order to move onto an adjacent empty/enemy area, if that area offered additional food.  I thought this was good, and it beat the other variations… most of the time.

Sometimes, though, one of the other variants which just expanded would still win – sure, I’d have more food and chickens, but my chickens would be abandoning money in favor of food while my opponent would be occupying every space in his radius… leading to economic victory.

The first change I made was that the food seeking logic would only kick in if the enemy had more food than I did – this seemed to work well enough… and, indeed, this is the only behavior which kicks in during the tournament (sadly!)

The next thing I experimented with was prioritizing money instead of food – this is usually suicide, but if you wait until around the middle of the game… and you only attempt to beat your opponent by a narrow margin… you can sometimes snag a win from what otherwise would be certain defeat.  This behavior never showed up during the tournament, but I basically guessed that the average payout rate was 0.5 (I really should’ve tested this) and so if my enemy controlled half the map, they could expect to receive height*width*0.5*0.5 = 625 money per turn.  So, if at any point after turn 500 my bot doesn’t have more than 625 chicken dollars than my opponent, the chickens attempt to occupy wall street.

That’s basically how I arrived at the champion AI, I just kept writing bots and pitting them against each other while trying to think of both the optimal strategy for the game and anticipating that my enemies would be doing the same.  I really thought phoenix was going to win, because I’d watched a previous match and it looked like his strategy was similar to mine except he was seeking resources with pathing instead of hill climbing, though it appears that in our match he suffered from a lower population due to wasting multiple chickens on a single space.

While I’m glad that my bot never needed to prioritize money, I would have liked to have seen that happen – as-is all of my matches were pretty boring.  I’m still thrilled I won, though! =]

Advertisements