[phpBB Debug] PHP Warning: in file /includes/bbcode.php on line 483: preg_replace(): The /e modifier is no longer supported, use preg_replace_callback instead
[phpBB Debug] PHP Warning: in file /includes/bbcode.php on line 483: preg_replace(): The /e modifier is no longer supported, use preg_replace_callback instead
[phpBB Debug] PHP Warning: in file /includes/bbcode.php on line 483: preg_replace(): The /e modifier is no longer supported, use preg_replace_callback instead
[phpBB Debug] PHP Warning: in file /includes/bbcode.php on line 483: preg_replace(): The /e modifier is no longer supported, use preg_replace_callback instead
[phpBB Debug] PHP Warning: in file /includes/bbcode.php on line 483: preg_replace(): The /e modifier is no longer supported, use preg_replace_callback instead
[phpBB Debug] PHP Warning: in file /includes/bbcode.php on line 483: preg_replace(): The /e modifier is no longer supported, use preg_replace_callback instead
[phpBB Debug] PHP Warning: in file /includes/bbcode.php on line 483: preg_replace(): The /e modifier is no longer supported, use preg_replace_callback instead
[phpBB Debug] PHP Warning: in file /includes/bbcode.php on line 483: preg_replace(): The /e modifier is no longer supported, use preg_replace_callback instead
[phpBB Debug] PHP Warning: in file /includes/bbcode.php on line 483: preg_replace(): The /e modifier is no longer supported, use preg_replace_callback instead
[phpBB Debug] PHP Warning: in file /includes/bbcode.php on line 483: preg_replace(): The /e modifier is no longer supported, use preg_replace_callback instead
[phpBB Debug] PHP Warning: in file /includes/bbcode.php on line 483: preg_replace(): The /e modifier is no longer supported, use preg_replace_callback instead
[phpBB Debug] PHP Warning: in file /includes/bbcode.php on line 483: preg_replace(): The /e modifier is no longer supported, use preg_replace_callback instead
[phpBB Debug] PHP Warning: in file /includes/bbcode.php on line 483: preg_replace(): The /e modifier is no longer supported, use preg_replace_callback instead
[phpBB Debug] PHP Warning: in file /includes/bbcode.php on line 483: preg_replace(): The /e modifier is no longer supported, use preg_replace_callback instead
[phpBB Debug] PHP Warning: in file /includes/bbcode.php on line 483: preg_replace(): The /e modifier is no longer supported, use preg_replace_callback instead
[phpBB Debug] PHP Warning: in file /includes/bbcode.php on line 483: preg_replace(): The /e modifier is no longer supported, use preg_replace_callback instead
[phpBB Debug] PHP Warning: in file /includes/bbcode.php on line 483: preg_replace(): The /e modifier is no longer supported, use preg_replace_callback instead
[phpBB Debug] PHP Warning: in file /includes/bbcode.php on line 483: preg_replace(): The /e modifier is no longer supported, use preg_replace_callback instead
[phpBB Debug] PHP Warning: in file /includes/bbcode.php on line 483: preg_replace(): The /e modifier is no longer supported, use preg_replace_callback instead
[phpBB Debug] PHP Warning: in file /includes/bbcode.php on line 483: preg_replace(): The /e modifier is no longer supported, use preg_replace_callback instead
[phpBB Debug] PHP Warning: in file /includes/bbcode.php on line 483: preg_replace(): The /e modifier is no longer supported, use preg_replace_callback instead
[phpBB Debug] PHP Warning: in file /includes/bbcode.php on line 483: preg_replace(): The /e modifier is no longer supported, use preg_replace_callback instead
[phpBB Debug] PHP Warning: in file /includes/bbcode.php on line 483: preg_replace(): The /e modifier is no longer supported, use preg_replace_callback instead
[phpBB Debug] PHP Warning: in file /includes/bbcode.php on line 483: preg_replace(): The /e modifier is no longer supported, use preg_replace_callback instead
[phpBB Debug] PHP Warning: in file /includes/bbcode.php on line 483: preg_replace(): The /e modifier is no longer supported, use preg_replace_callback instead
[phpBB Debug] PHP Warning: in file /includes/bbcode.php on line 483: preg_replace(): The /e modifier is no longer supported, use preg_replace_callback instead
[phpBB Debug] PHP Warning: in file /includes/bbcode.php on line 112: preg_replace(): The /e modifier is no longer supported, use preg_replace_callback instead
[phpBB Debug] PHP Warning: in file /includes/bbcode.php on line 112: preg_replace(): The /e modifier is no longer supported, use preg_replace_callback instead
[phpBB Debug] PHP Warning: in file /includes/bbcode.php on line 112: preg_replace(): The /e modifier is no longer supported, use preg_replace_callback instead
[phpBB Debug] PHP Warning: in file /includes/bbcode.php on line 112: preg_replace(): The /e modifier is no longer supported, use preg_replace_callback instead
[phpBB Debug] PHP Warning: in file /includes/functions.php on line 4586: Cannot modify header information - headers already sent by (output started at /includes/functions.php:3765)
[phpBB Debug] PHP Warning: in file /includes/functions.php on line 4588: Cannot modify header information - headers already sent by (output started at /includes/functions.php:3765)
[phpBB Debug] PHP Warning: in file /includes/functions.php on line 4589: Cannot modify header information - headers already sent by (output started at /includes/functions.php:3765)
[phpBB Debug] PHP Warning: in file /includes/functions.php on line 4590: Cannot modify header information - headers already sent by (output started at /includes/functions.php:3765)
AI Challenge Forums • View topic - A simple approach to combat

It is currently Sun Dec 11, 2016 11:47 am 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
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.
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

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

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

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

BenJackson
Colonel
 
Posts: 94
Joined: Sat Oct 29, 2011 4:16 am

Next

Return to Strategy

Who is online

Users browsing this forum: No registered users and 1 guest

cron