[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 - Exploration algorithms

It is currently Sat Aug 17, 2019 3:39 pm Advanced search

Exploration algorithms

Share and discuss ideas for your entries here.

Exploration algorithms

Postby DrClaes » Tue Nov 01, 2011 12:19 pm

Hello!

I'm doing some big revisions of my code based on the experience so far; I've got pathfinding in already visualized areas of the map working well; assigning ants to food sources is trickier but in the early game on large maps my colonies are growing at a similar rate to stronger bots.

Right now I'm putting a lot of energy into exploration algorithms rather than pathfinding. Does anyone feel like sharing their thoughts--and even better, any references/web pages/articles on the subject?

Things I've tried to implement so far:

1. Scent-based system where the ants go in the direction of least scent in order to move away from the nest. Has worked decently, especially if the ant is allowed to look out to some radius for "unscented places" to try to get to, otherwise it can get stuck in corners

2. Keeping track of shortest-path-to-own-hill and always moving away from the own hill. Also gets stuck in corners and dead ends. Some attempts to rectify that with backtracking for shorter or longer distances improved the situatino a little bit but not great

3. Keeping track of where the edge of explored map is and sending each ant along the shortest path leading to an edge. With some thought I implemented this quite efficiently, and I like what this looks like on open maps. In mazes this has missed a lot of corners, which I didn't like.

Directions I'm taking now:

Combining approach 3 above with a priority system for checking on previously spotted food which is no longer visible. I have high hopes for this, and after reading about "ant colony optimization" on wikipedia I find the thought of relatively simple, decentralized decision making (hopefully) generating complex emergent behavior very appealing :)...

Combat tactics and home nest defense..... sigh, haven't even tried to implement those yet... but if I'm lagging in the early game against the top bots simple economics of warfare tells me I'm toast anyway :)... production is king...
DrClaes
Lieutenant-Colonel
 
Posts: 49
Joined: Sat Oct 29, 2011 6:27 am

Re: Exploration algorithms

Postby Parasprites » Tue Nov 01, 2011 12:59 pm

I don't think there's any real need to do decentralized pathfinding. You can bruteforce pathfinding for dozens of ants in well under the time limit.
Parasprites
Major-General
 
Posts: 224
Joined: Mon Oct 24, 2011 3:08 pm

Re: Exploration algorithms

Postby DrClaes » Tue Nov 01, 2011 1:15 pm

I agree, and wasn't clear in my post above; I have no problem doing bfs pathfinding for getting from one known spot to another on the map, nor with building an internal representation of the visualized map so far. The interesting problem for me now is how to explore the map most efficiently, distributing your ants as widely as possible before they inevitably run into competition.
DrClaes
Lieutenant-Colonel
 
Posts: 49
Joined: Sat Oct 29, 2011 6:27 am

Re: Exploration algorithms

Postby Parasprites » Tue Nov 01, 2011 1:27 pm

I'm having problems with exploration and distribution too.

I thought I had it solved, but after making an unrelated change to a different part of the bot, my ants now suck at exploring.
Parasprites
Major-General
 
Posts: 224
Joined: Mon Oct 24, 2011 3:08 pm


Return to Strategy

Who is online

Users browsing this forum: No registered users and 2 guests

cron