A simple approach to combat

[Memetix]

If you want to try a simple, single pass approach to combat that produces good results with low CPU usage, the following has worked well for me. On my 3 yr old laptop, the Java code runs in 3-5 milliseconds.

For each ant (ours and the enemies that we know about) we work out which tiles on the map the ant can affect with it's combat zone after 1 move. Store the number of times each tile is affected in an array influence[players][rows][cols]. While doing this, store the total influence in another array total[rows][cols].
This influence map represents the number of ants each player could get to "attack" each tile of the map. It represents the best that can be achieved.

Once this is done we know how many ants each ant could be fighting in each tile of the map.
i.e. enemies = total[row][col] - influence[player][row][col]
We can now work out the best ant in each combat zone, the best ant being the one that is fighting the least number of other ants. Store this in another array fighting[player][rows][cols].
i.e. fighting[0][0][0] would contain the number of enemy ants an ant at (0,0) belonging to player 0 would be fighting.
This can be simply derived from the values in the influence array.

The last step of the process is to work out what could happen to each player if it put an ant in a tile and store this in an array status[players][rows][cols]. We only need to do this for tiles an ant can get to with 1 move.
The values in this array are set to SAFE, KILL or DIE depending on whether the best ant we are fighting in the tile is fighting more, equal to or less ants than us.

That's it. If you want to be safe, never allow a move into a tile with status of KILL or DIE.
If you want to break deadlock situations you can allow entry into KILL tiles and expect to get a 1:1 swap.

You can also check to see if an enemy ants' move towards you would result in its death, if so it is probably safe to advance towards that tile. At the moment I'm not doing this, but it could be useful information and produce better results.

To see this strategy in action check out CombatAnt on fluxid
Many thanks to A1kon for starting the ball rolling ... I've had many good fights with his ants which use is very different approach.
The results seem broadly comparable.

[a1k0n]

Well, your bot definitely seems to be kicking mine's butt, so thank you for demonstrating that my first assumption is invalid! Much appreciated. I never did work out the details of this approach, though I had considered it.

It wasn't totally clear what you meant by "total influence" but by formulating the question I now understand that total[x][y] = Sum_{p} influence[p][x][y]. That is, the number of ants from all players which could attack that square next turn.

Thanks for sharing!

[zaphod]

@Memetix: I am almost using the same strategy, except that there are still some minor bugs in my heuristics. I'd prefer to call it a greedy heuristic strategy. The good thing about it is that it is extremely simple to implement in Python using a few lists, dictionaries and the sort method. In my games so far, I haven't found the strategy to be too bad in combat. The bot can fight pretty decent event when the solution is sub optimal. Maximising the greedy function over all the other possibilities is out of question for my bot. This allows me to concentrate more on the exploring logic and sacrificial moves which my bot is currently lagging far behind, while saving valuable CPU time (especially true for Python bots). Ofcourse, my bot has never been tested against an opponent within the top 100 where the combat would be highly important, so I might be wrong in concluding too early!

@a1k0n: I am not sure if I understand what you meant by the invalid assumption. Is it linked to some other post?

[carlos.guia]

Thanks for sharing this simple algorithm, mine is almost like that but but you pointed out a small difference that should improve my results a lot.

I've tried a1k0n's approach a couple of times but never got good results out, however, I believe my evaluation function was close to nonsense.

[antimatroid]

[McLeopold]

[Memetix]

When working out the influence array you can improve things by taking into account that only 1 ant can move into a given tile. I implemented this is my last iteration, simply keeping track of whether a tile has been used as the centre of a combat zone. In the example given by antimatroid this stops both "b" ants exerting influence from the same tile (south of the top ant and west of the other one).

[erdman]

[McLeopold]

I didn't get it at first either. Now I do.

When calculating status, pick a player and a location, then loop through all squares within attack range (22-1) looking for any player (not yourself) with fighting[player][enemy_row][enemy_col] that is <= to fighting[0][row][col]. If you find you'll DIE, then you can exit early.

[BenJackson]