[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 - Gravity Wells

It is currently Wed Jul 18, 2018 1:23 am Advanced search

Gravity Wells

Share and discuss ideas for your entries here.

Gravity Wells

Postby Memetix » Thu Dec 01, 2011 11:36 am

When I first heard about the contest a month ago and put some thought into how to approach the problem I made a fundamental decision to avoid pathfinding for individual ants. I realised that, if you were doing well and your number of ants was growing, your code would slow down to the point of timing out as the game progressed.

I decided to use the concept of gravity wells and I wanted to share my findings with the community. I suspect a top 20 position is possible using this technique, though my programming skills are very rusty (its been over 15 years) so I'm learning Java as I go and tending to produce code with bugs.
Version 12 of my software got to rank 23 and it had very buggy combat code.

Gravity Wells.
I imagine the map to be a large rubber surface. Then I place conceptual ball bearings of differing weights onto the rubber surface at key points (i.e. food, enemy hills, unexplored locations) and watch the rubber surface deform. Some balls are heavier than others (i.e. food is heavier than unexplored locations). Using a ripple out routine from each point of interest I score the tiles reached depending on the distance travelled from the ball bearing (using 1 over distance squared, just like gravity). The higher the score, the nearer you are to a point of interest.
This gives every tile on the surface a score and all we need to do to get effective exploration is to move each ant to the adjacent tile with the highest score (or stay still if it is in the best place already).

I got this working by adding about 200 lines of code to the starter package and at the start of a game, the code keeps up its growth rate with the best of them, only getting into problems when it meets other ants.

Once you have this map of scores the strategy can be improved by
1. Working out the best set of moves for your ants to maximize the total score after all the moves are done (rather than maximizing each ant individually)
2. Adding in some sort of combat code to work out if an enemy ant should act as an attractor (a ball bearing) or a repeller (helium balloon).

I'm stuck on how to approach option 1, any ideas?
Having recently discovered the tcp servers I've been able to improve my code for option 2 and I'm seeing some good results (See CombatAnts on fluxid if you are interested). I may post later on my approach to combat if people want.
Memetix
Major
 
Posts: 39
Joined: Tue Nov 08, 2011 3:53 pm

Re: Gravity Wells

Postby mac » Thu Dec 01, 2011 1:28 pm

This sounds strikingly similar to diffusion (if you search for this term or "collaborative diffusion") you will find a few hits on the forum.

If I got how your code works, diffusion has the advantage of taking in consideration impassable tiles (water).

...but maybe I missed some nuance of how your algorithm works?
mac
Brigadier-General
 
Posts: 151
Joined: Mon Oct 31, 2011 6:39 am

Re: Gravity Wells

Postby deccan » Thu Dec 01, 2011 1:45 pm

How do you prevent all your ants from simply converging in the area with the heaviest ball bearings?
deccan
Lieutenant
 
Posts: 18
Joined: Tue Nov 30, 2010 1:30 am

Re: Gravity Wells

Postby Memetix » Thu Dec 01, 2011 1:54 pm

Memetix
Major
 
Posts: 39
Joined: Tue Nov 08, 2011 3:53 pm

Re: Gravity Wells

Postby Parasprites » Thu Dec 01, 2011 5:26 pm

1. is a simple matter of constraint optimization. Combat is the hard part.

Anyway, the term for what you're doing is a influence map. Personally, I don't bother weighting. I just use min distance.
Parasprites
Major-General
 
Posts: 224
Joined: Mon Oct 24, 2011 3:08 pm

Re: Gravity Wells

Postby dimkadimon » Fri Dec 02, 2011 6:44 am

dimkadimon
Major-General
 
Posts: 263
Joined: Wed Oct 06, 2010 11:34 pm
Location: Adelaide, Australia

Re: Gravity Wells

Postby Memetix » Fri Dec 02, 2011 8:54 am

Memetix
Major
 
Posts: 39
Joined: Tue Nov 08, 2011 3:53 pm

Re: Gravity Wells

Postby ikaros » Fri Dec 02, 2011 9:59 am

What I wonder is:
How often do you run the bfs? One time for all food at once? Another one for exploration targets and so on? Or do you put everything into one bfs?
Do you add up the different weights ?
For example if you start in the middle of unexplored/unseen area would every tile there just have the base value for "unexplored tile" or would they add up to a very heavy weighted big area?
ikaros
Cadet
 
Posts: 9
Joined: Mon Oct 24, 2011 7:02 pm

Re: Gravity Wells

Postby Memetix » Fri Dec 02, 2011 10:29 am

Memetix
Major
 
Posts: 39
Joined: Tue Nov 08, 2011 3:53 pm

Re: Gravity Wells

Postby ikaros » Sat Dec 03, 2011 10:15 pm

Thanks for the explanation.

I have implemented this myself now and try to use it for exploration only so far. In general it seems to work with some little flaws. There is one question remaining from my side :)

You say you put all tiles to explore in the bfs queue at once(which makes sense) but also your weighting function is weight/dist^2.

I understand how that works if you have one source .. like a food location. If the food is weighted with 100 you have a value of 100/4 two tiles away and 100/9 three tiles away and so on.

But with multiple sources how can I be sure about the source(and so the distance)? Because every visited tile has 4 influences(its neighbors) how do i determine which is the source?
I assume the exploration targets have different weights.. if not everything would be clear :)
ikaros
Cadet
 
Posts: 9
Joined: Mon Oct 24, 2011 7:02 pm

Next

Return to Strategy

Who is online

Users browsing this forum: No registered users and 1 guest

cron