[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/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 - Floodfill strategy

It is currently Mon Dec 10, 2018 11:59 am Advanced search

Floodfill strategy

Share and discuss ideas for your entries here.

Floodfill strategy

Postby amstan » Fri Feb 05, 2010 1:06 am

I am surprised nobody is using this yet. (well, except me, till I stepped down)
This is a very effective strategy to use short of A* or AlphaBeta

Basically, it's a space seeker, so it goes toward the area with more spaces; nothing fancy.

The idea is that for each of the 3 choices you have to move in(4 if you're really suicidal and you wanna go backwards), count how many spaces there are starting at that point. You count this using the floodfill algorithm, basically a recursive function that counts if the spot it ocupies has a wall or not, if it does exits, if it doesn't it will increase the count then call itself on the neighbor spots. More info , including animations.

This is not cool on its own because it's boring and stuff, like a wallbot. So a good addition would be that if it's in empty space and has more choices to pick the spot leading closest to the enemy.

Implement this and you'll get to first spot until someone gets something better.
Note: this should even beat nneonneo's space searching strategy(he only looks 1 recursion deep, this strategy looks until the space is filled).
Alexandru M. Stan
Contest Organizer
User avatar
amstan
Contest Organizer
 
Posts: 691
Joined: Sun Jan 31, 2010 4:02 am
Location: Stoney Creek, Ontario

Re: Floodfill strategy

Postby amstan » Fri Feb 05, 2010 1:52 am

If anyone's using this so far, could you reply to this post?
It's basically shifting the contest to the next level if someone does. Would be cool to know when.
Alexandru M. Stan
Contest Organizer
User avatar
amstan
Contest Organizer
 
Posts: 691
Joined: Sun Jan 31, 2010 4:02 am
Location: Stoney Creek, Ontario

Re: Floodfill strategy

Postby mzulak » Fri Feb 05, 2010 4:46 am

I've been using a naive floodfill implementation on a past Python submission; the performance was okay, but I found that my bot had a hard time cornering the enemy. I've since switched to minimax (with Alpha-Beta pruning to come), but I might have to revisit flood-fill again to see which performs better. :3
mzulak
Cadet
 
Posts: 9
Joined: Mon Feb 01, 2010 10:17 pm

Re: Floodfill strategy

Postby smf68 » Fri Feb 05, 2010 10:13 am

smf68
Lieutenant
 
Posts: 11
Joined: Thu Feb 04, 2010 11:24 pm

Re: Floodfill strategy

Postby kronos » Fri Feb 05, 2010 11:06 am

er, I don't believe this should time out. A basic floodfill (so essentially just a standard dfs) should work. I haven't implemented it yet, but I was just wondering: wouldn't the floodfill usually return an equal number of squares when run for the three neighbors? I mean, usually when taking either of the three moves, you should be accessible to the same number of squares...

I mean, I guess one could break ties with what you said (take the square closer to the enemy). Ok, I'll implement this.
kronos
Lieutenant
 
Posts: 18
Joined: Fri Feb 05, 2010 5:41 am

Re: Floodfill strategy

Postby smf68 » Fri Feb 05, 2010 11:26 am

Reimplemented the whole thing and now it seems to be fast enough and compete quite well: http://csclub.uwaterloo.ca/contest/prof ... er_id=1018, currently rank 4.

It doesn't seem to lose any game, but still scores too many draws imo. Furthermore, it's not all too hard to beat it as a human...
smf68
Lieutenant
 
Posts: 11
Joined: Thu Feb 04, 2010 11:24 pm

Re: Floodfill strategy

Postby kronos » Fri Feb 05, 2010 3:33 pm

So, you went to the neghboring square that returned the highest floodill value (i.e. can access the most squares), and you broke ties with taking the one closest to the enemy?
kronos
Lieutenant
 
Posts: 18
Joined: Fri Feb 05, 2010 5:41 am

Re: Floodfill strategy

Postby Yatrix » Fri Feb 05, 2010 3:50 pm

Implemented something similar...instead of recursively checking most space, it recursively finds longest possible path to traverse. Of course, I can only look ahead a certain number of steps without timeout.
Yatrix
Cadet
 
Posts: 3
Joined: Wed Feb 03, 2010 6:11 pm

Re: Floodfill strategy

Postby bormanm » Fri Feb 05, 2010 4:34 pm

Mine uses two levels of recursion and a distance algo to break ties.

morgan
bormanm
Cadet
 
Posts: 2
Joined: Wed Feb 03, 2010 7:24 am

Re: Floodfill strategy

Postby Experiment Garden » Fri Feb 05, 2010 5:29 pm

I implemented a custom flood fill in Java and reached #7 on the scoreboard. I agree, though, that with just floodfill there are far too many draws. I just added some extra logic to try to avoid draws, and my bot is at #1 so far, but then again, its only played 42 games so far.

We'll see how it goes.
Experiment Garden
Cadet
 
Posts: 9
Joined: Fri Feb 05, 2010 5:26 pm

Next

Return to Strategy

Who is online

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

cron