It is currently Tue May 24, 2016 11:21 pm Advanced search

A simple approach to combat

Share and discuss ideas for your entries here.

A simple approach to combat

Postby Memetix » Thu Dec 08, 2011 4:00 pm

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 http://ants.fluxid.pl/replay.18266
Many thanks to A1kon for starting the ball rolling ... I've had many good fights with his ants which use is very different approach. http://forums.aichallenge.org/viewtopic.php?f=24&t=2044
The results seem broadly comparable.
Memetix
Major
 
Posts: 39
Joined: Tue Nov 08, 2011 3:53 pm

Re: A simple approach to combat

Postby a1k0n » Thu Dec 08, 2011 5:09 pm

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!
a1k0n
Colonel
 
Posts: 90
Joined: Fri Feb 12, 2010 3:51 am

Re: A simple approach to combat

Postby zaphod » Thu Dec 08, 2011 6:02 pm

@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?
zaphod
Captain
 
Posts: 21
Joined: Tue Nov 01, 2011 6:07 pm

Re: A simple approach to combat

Postby carlos.guia » Thu Dec 08, 2011 6:39 pm

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.
carlos.guia
Lieutenant
 
Posts: 19
Joined: Mon Oct 31, 2011 11:19 pm

Re: A simple approach to combat

Postby antimatroid » Thu Dec 08, 2011 7:17 pm

I use that kind of information when picking out offensive and defensive moves for my game tree. Although I'm not sure you're most accurately obtaining the information? Let me just offer an example situation to let people think about that...


Code: Select all
.............
.............
....b........
.....b.......
.....%.......
...a.........
.............



Only 1 enemy can really battle 'a' next turn if they remain static. I'll leave it as an exercise to the reader to work out how to calculate that.
antimatroid
Brigadier-General
 
Posts: 126
Joined: Tue Feb 16, 2010 7:41 am

Re: A simple approach to combat

Postby McLeopold » Thu Dec 08, 2011 7:55 pm

Only 1 enemy can really battle 'a' next turn if they remain static. I'll leave it as an exercise to the reader to work out how to calculate that.


Here's another example. Unless I'm updating status wrong...

http://paste.aichallenge.org/NidJk/?row ... 14&turn=33

Yellow is KILL (1 for 1) and Red is DIE.
McLeopold
Contest Organizer
 
Posts: 262
Joined: Sun Sep 19, 2010 3:31 am

Re: A simple approach to combat

Postby Memetix » Thu Dec 08, 2011 9:45 pm

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).
Memetix
Major
 
Posts: 39
Joined: Tue Nov 08, 2011 3:53 pm

Re: A simple approach to combat

Postby erdman » Thu Dec 08, 2011 10:02 pm

Great post, thanks!
i.e. enemies = total[row][col] - influence[player][row][col]
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.

These (array 'enemies' and array 'fighting') are the same array / same information, just two different names in the post, right?

I didn't follow the idea of 'best ant'. Do you mean player who has the most influence in a given square? So, looking at array fighting[player][row][col], the 'best ant' is the player with highest value for given row, col?

If that is the case, for a given ant-move, why compare only to 'best ant', when all our enemies can combine to kill us?

I don't think I'm quite following this.
erdman
Major
 
Posts: 34
Joined: Thu Oct 27, 2011 12:52 am

Re: A simple approach to combat

Postby McLeopold » Thu Dec 08, 2011 10:50 pm

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.
McLeopold
Contest Organizer
 
Posts: 262
Joined: Sun Sep 19, 2010 3:31 am

Re: A simple approach to combat

Postby BenJackson » Thu Dec 08, 2011 10:53 pm

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.


This is just directly from the game specification. When combat is resolved, the "weakness" of every ant is computed. The actual moment of combat happens simultaneously for all ants after the initial weakness calculation. Each ant fights its best enemy: the ant threatening it with the lowest weakness. If it loses or ties that comparison it dies.

So enemies[player][row][col] tells you the weakness of an ant standing there. But to know if you'd die you must also know the weakness of the best ant attacking that position. So in fighting[player][row][col] you must place the minimum of enemies[any enemy][nearby row][nearby col].

Finally if enemies[player][r][c] < fighting[player][r][c] you win, if == you die and they die, if > you die and they live.

(my interpretation: I don't use this combat but I'll probably implement it just to see it)
BenJackson
Colonel
 
Posts: 94
Joined: Sat Oct 29, 2011 4:16 am

Next

Return to Strategy

Who is online

Users browsing this forum: Yahoo [Bot] and 1 guest

cron