[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/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 - Survival Mode

It is currently Sat Aug 19, 2017 1:01 pm Advanced search

Survival Mode

Share and discuss ideas for your entries here.

Re: Survival Mode

Postby iouri_ » Tue Feb 23, 2010 2:31 am

Maxime81: looks like your strategy beat mine..

iouri_
Brigadier-General
 
Posts: 105
Joined: Thu Feb 11, 2010 4:16 pm
Location: Toronto, Canada

Re: Survival Mode

Postby iouri_ » Tue Feb 23, 2010 2:47 am

iouri_
Brigadier-General
 
Posts: 105
Joined: Thu Feb 11, 2010 4:16 pm
Location: Toronto, Canada

Re: Survival Mode

Postby montanalow » Tue Feb 23, 2010 3:05 am

I've had similarly disappointing experiences with just about all the "enhancements" I've tried to make to simple binary territory calculation using flood fill as a board evaluation heuristic.

I've tried assigning fractional ownership of squares based on relative distances - worse result.
I've tried subtracting all not-the-longest dead ends from territories, since you can only enter 1 dead end - worse result.
I tried extrapolated dead ends to chamber trees like iouri_ describes, but noticed A) complex chamber trees are rare in actual game play B) when they do occur, it's the mutual exclusion that is interesting, but those exclusions are generally not visible until you calculate several moves in the future, which is C) more expensive since you are calculating chambers now, and can't go as deep down the board tree at which point D) the simpler, more forward thinking yet naive binary territory bot has out maneuvered you.

Something interesting I've noticed, is that at many critical points in the game play, minimax values wiggle based on search depth. For example, up to 5 moves ahead North looks best, then at 6 and 7 moves, East looks better, then at 8 and more moves, North is best again.

This seems to happen when my bot is in a chamber with a long hallway leading to the opponents territory. Apparently my bot is afraid to prematurely enter the hallway, since it implies wasting his territory advantage, but it leaves a distant bot plenty of time to maneuver to the other end of the hallway, and gain the advantage on the other side, if it's aggressively inclined. Originally I think this was a lot of the problem I had with Quadrant, but I see this particular dilemma happen often on Triangle, Oval and Box.

Has anyone played with strategic planning? As in, use a heuristic to pick an objective, then formulate a plan to reach that objective, then follow the plan over the next few moves to reach your objective in a space efficient way? On maps like Triangle and Box particularly, efficiently fencing off area from the get go seems like an unbeatable strategy. Especially while other minimax bots are wandering around aimlessly out of range.
montanalow
Lieutenant-Colonel
 
Posts: 42
Joined: Thu Feb 18, 2010 6:50 pm

Re: Survival Mode

Postby callinwire » Tue Feb 23, 2010 3:29 am

callinwire
Lieutenant
 
Posts: 16
Joined: Thu Feb 11, 2010 8:54 pm

Re: Survival Mode

Postby Maxime81 » Tue Feb 23, 2010 3:41 am

iouri_, I don't understand why your bot decided to go back at one moment... Maybe the issue would have been different...


I found an algorithm for finding the articulation vertices (http://www.ibluemojo.com/contents/articDFS.pdf). I didn't tried to implement it yet but it doesn't seems too complicated... Maybe I'll tried tomorrow (it's 4am and half here...).
I know there are better algorithms but I want to understand what I'm doing :). (my graph teacher didn't taught me the algorithms to find the cut vertices, just shortest paths and flow...)
Maxime81
Lieutenant-Colonel
 
Posts: 42
Joined: Sat Feb 13, 2010 10:56 pm
Location: INSA Toulouse, France

Re: Survival Mode

Postby iouri_ » Tue Feb 23, 2010 4:02 am

iouri_
Brigadier-General
 
Posts: 105
Joined: Thu Feb 11, 2010 4:16 pm
Location: Toronto, Canada

Re: Survival Mode

Postby Maxime81 » Tue Feb 23, 2010 4:07 am

Maxime81
Lieutenant-Colonel
 
Posts: 42
Joined: Sat Feb 13, 2010 10:56 pm
Location: INSA Toulouse, France

Re: Survival Mode

Postby iouri_ » Tue Feb 23, 2010 4:23 am

iouri_
Brigadier-General
 
Posts: 105
Joined: Thu Feb 11, 2010 4:16 pm
Location: Toronto, Canada

Re: Survival Mode

Postby dmj » Tue Feb 23, 2010 4:23 am

Regarding survival mode...

I originally let my Voronoi + minimax code fill space for me, but it would often leave holes. Then I just did an "iteratively deepened" DFS on only my bot's moves (not the opponent's) to find the longest path I could that did not reduce the reachable squares.

This worked ok, but would often leave long tunnels instead of sacrificing one square to fill in the others in the tunnel.

Now I have code to find the cut vertexes in the graph, and to estimate how many of them I will fill (sort of like the tree of chambers idea.) I then use this function + the iterative DFS to find the move that gives me the most possible squares.

My evaluation functions are expensive, and the code is in Python, so it does not look very far out. Sometimes it leaves squares open that I think it should hit, but I think I am done tweaking my survival mode.

Fun idea, but mostly useless:
When I was frustrated with some of the holes my bot left, I remembered a puzzle about checker boards, and realized we have the same thing here. Bots can only move from red to black and vice-versa. So, if you have 10 black squares to fill, and 6 red, you know that at least 3 of your black squares are not going to be reachable (and that is only if you are starting on a red square). I tried to put that in my evaluation functions, but it only made a tiny difference, if any. Of course, I have made many mistakes so far, so maybe I did not do it right. :)
dmj
Lieutenant-Colonel
 
Posts: 41
Joined: Thu Feb 11, 2010 11:36 am

Re: Survival Mode

Postby a1k0n » Tue Feb 23, 2010 6:01 am

dmj: that's not useless, that's utterly brilliant. Gives a tight upper bound without any computation to speak of.
a1k0n
Colonel
 
Posts: 90
Joined: Fri Feb 12, 2010 3:51 am

PreviousNext

Return to Strategy

Who is online

Users browsing this forum: No registered users and 1 guest

cron