Sunday, February 20, 2011

Planet Wars - My First AI Contest (part 2)

First part of this post described how I missed the actual competition but still managed to have loads of fun and come up with my own bot thanks to nice people who have published their bots and made it possible for me to conduct a local tournament. Those who wondering what the Planet Wars is and what the big deal behind this so called AI competition, you can get up to date with all that from here.

In this post, I will mainly discuss the strategies and path I took when designing my bot and the lessons learned.

One of main lessons I learned from this experience is that the precious calculations are always way better than heuristic guesses. Sometimes when the problem is complicated, we tend to invent an obvious looking heuristic ("if my planet's ships are greater than enemy planet ships, attack the enemy with 50% of my strength" for instance) even though it may be the easier option, in the long run, investing our time on preciously calculating and picking our choice is always superior. It was particularly interested to note how heuristics disappeared from my algorithm and replaced by calculations as it was evolving.

Mainly I had 5 steps in my code :
1) Attack : if one or more of my planets can send ships to capture another planet even temporarily, do so. After considering all incoming fleets for the enemy planet, enemy growth over the attacking distance and possible reinforcements enemy can receive from it friends, (if those friends are nearer than my attacking planet that is), if it seems like I can capture the planet, I usually did so. My Planet will not hesitate to even attack with full strength if the enemy planet has a higher growth than itself, Otherwise it will use just the excess ships.

2) Defense : if one of my planets has incoming enemy fleets, I would assemble ships from my nearby planets and reinforce the planet which is under threat. Again all the incoming fleets, my own growth over the enemy attacking distance and reinforcements I can find were included in calculations. Nearby planets were given priority when selecting defenders.

3) Sniping : If an enemy is moving towards a neutral planet, I would try to reach there just after enemy has landed. That way enemy will do all the hard work of destroying the neutral defenders while I will have to fight only with it's depleted remaining forces.

4) Neutral planet hunting : if there are unoccupied planets which are nearer to me than to the enemy and if it is desirable (hear I used a heuristic) to take them, do so.

5) reinforcements : far away planets sending their ships to planets which are nearer to enemy planets.

Beside above, I tried to maintain a minimum force on planets which are nearby to enemy. Amount of that force was calculated by the attacking strength of the nearest enemy and defensive strength of my planets which were nearer to me than the enemy. Any excess above this limit was used in attacks. In defense, defenders trying their best to send enough ships to defend a planet by using their excess forces only.

Some bots were passing there chance on very first turn hoping for sniping chances on their second turn or in fear of being sniped themselves, I guess. I never liked that strategy. In initial moves, I took only the planets which are nearer to me than the enemy. In case of planets which fell in the middle, I chose not to attack them on the very first turn and to leave them for the enemy take, then I tried sniping on 2nd turn. This strategy gave me mixed results. When attacking a neutral planet or when doing a sniping, I did try to calculate the impact of "future planets" on them. That is planets which are not being claimed by either party but very soon will belong to one side. This could be easily deduced by the fleets in motion. Code would explain how this is done. I got few extra rating points after implementing this feature.

Another gray area for me was to decide whether I should change my behavior according to the game status. That is, should I attack less when I'm ahead in growth, should I attack more when I'm behind etc. Experiments on those always gave me mixed results. I eventually concluded that attack whenever it can be done with accuracy is best in most situations. This increased my score against stronger bots.

Few things I haven't implemented : Ideally the bot should compare advantages and disadvantages between an attack and defense. Should I let my planet fall and try to take that enemy planet etc... If I saw a sure attack I always took it and then tried to defend planets with available ships. It would have been cool to have a comparison though.

I gave lowest priority to attacking neutrals at the later stages of the game.

my functions to determine what is the minimum force to take an enemy planet and the minimum force required to defend an own planet was the same. It considered all fleets bound towards that planet, growth and reinforcements from friends. However I did not have any game tree and a mechanism to decide what if I do this, he do that and then I do this etc... I thought that sort of a min max tree approach is not so suitable for something like Planet Wars where problem space was huge and we had to come up with a move within a second. However, I have noted others talking about this any apparently getting some good results as well. I never tried that approach. If we are sensibly reinforced, well defended and always on the look for weaknesses of the enemy while being aggressive at the early stages on neutral hunting, I thought that will be good enough to be within first 100. may be I was correct in that, but then again that may also explain why my bot couldn't reach first 60, for instance.

One very interesting thing I noted was that even some of the stronger bots were not defending themselves properly at times. For instance, when in the opening where both parties have only one planet each, I managed to take the enemy by directly attacking it while it was busy sending fleets for neutrals. This was an easy check to do and guard against, yet most haven't done it and I scored few quick victories with that.

There are lot of finer details I like to discuss but that will grow this post to insane levels. Anyway the shared code should explain lot of things adequately. If anyone has questions/criticisms/suggestions, I would be glad to reply.

2 comments:

  1. Could you share the code? I'm learning about the techniques used by programmers Wars Planet and I would like to test your bot

    ReplyDelete
    Replies
    1. Miguel, code is already shared and the link is in part 1 of this article. Enjoy!

      Delete