[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/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 - Combat using iterative refinement of local theaters

It is currently Wed Jul 18, 2018 8:20 pm Advanced search

Combat using iterative refinement of local theaters

Share and discuss ideas for your entries here.

Combat using iterative refinement of local theaters

Postby nhaehnle » Wed Dec 07, 2011 8:00 am

Since a1k0n revealed his combat strategy in , I thought I'd post mine as well in the spirit of friendly competition. It got my bot up around rank 50, but then again I haven't had time to tweak it much yet (I have only just uploaded my second combat-aware version).

Introductory rant: as we all know, the big problem in generating moves is the combinatorial explosion of 5^N moves for N ants. a1k0n works around this by sampling from a product distribution, as far as I understand it. I will have to try this out as an alternative to my approach. I briefly considered something like that but have not actually tried it because of the following heuristic: there are many situations in which moving a single ant is a losing proposition, but moving two or more ants simultaneously can score a kill. This thought lead me to the following design.

Every ant that is within a certain distance of the enemy (basically close enough to participate in combat during the next round) is marked for tactical evaluation. I then look at small (fixed size) square sub-maps containing those tactical ants. For every sub-map, I maintain a list of my ants' and enemy's moves that have been considered so far. Here, a move is the joint move of all ants within the tactical sub-map. The size of the space of possible moves is still exponential in the number of ants. The idea is to explore it in a heuristic but coordinated way.

The move list is initialized with the moves generated by my food collecting etc. logic for my ants, while the enemy ants are initially assumed to be stationary.

Then I keep evaluating all pairs of moves (my move vs. enemy move) using a simple scoring function. I repeatedly pick out the (max-min) best move found for my ants, and try to generate better moves from this best move based on some simple heuristics: for ants of mine that are killed, try to retreat; also, try to attack enemy ants. The heuristics try to generate reasonable moves, i.e. the attacking logic only actually "commits" to a new move if it can rally enough ants to kill an enemy. I generate new moves for the enemy using the same logic.

In principle, this process of refinement can be continued until the timeout is close. (I'm currently terminating the search based on the number of moves considered instead of time, because I like to have repeatable behaviour for testing.)

One thing that I haven't dealt with yet is overlapping local theaters. For the evaluation of moves to not miss information, the "tactical ants" must be close to the center of the sub-map on which I perform my computations. Therefore, it often happens that an ant participates in more than one of those sub-map evaluations - one in which it is at the center, and one or more others in which it is closer to the boundary. I don't have a lucid method for resolving the case when those evaluations yield different moves for the same ant.
nhaehnle
Cadet
 
Posts: 7
Joined: Wed Dec 07, 2011 7:28 am

Return to Strategy

Who is online

Users browsing this forum: No registered users and 2 guests

cron