[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/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 - Chambers, dead ends, and graphs with cycles

It is currently Wed Sep 19, 2018 11:34 am Advanced search

Chambers, dead ends, and graphs with cycles

Share and discuss ideas for your entries here.

Chambers, dead ends, and graphs with cycles

Postby montanalow » Wed Feb 24, 2010 12:04 am

montanalow
Lieutenant-Colonel
 
Posts: 42
Joined: Thu Feb 18, 2010 6:50 pm

Re: Chambers, dead ends, and graphs with cycles

Postby iouri_ » Wed Feb 24, 2010 12:52 am

True, with my algorithm the performance (# of move evaluations per sec) is worse when trying to find chambers, but it's actually not that much worse. If there are no chambers to merge, the run time is only marginally slower than simply calculating the total available area (one still has to visit each cell). In most cases there are maybe 1-3 chamber mergers covering part of the territory; in those cases the evaluation runs 2-4 times slower than simple total area calculation. Of course, in worst case (something like 'toronto' map, or particularly devilish chamber configuration), my rough guesstimate puts the run time closer to O(n^2), where n=remaining accessible squares.

The scenario I've described above (the very inaccurate tree-based calculation) is exactly the reason I decided not to forgo chamber mergers. The mergers are done by finding the lowest common parent chamber and relabeling all the cells as belonging to that chamber (this is where the square in O(n^2) comes from - may have to visit every cell an extra time per merger). To decrease number of chambers one has to merge (or keep track of), I try to recognize each corridor as a single chamber.

Anyway, since the mention of 'articulation vertexes' in the same thread I realized that my approach was actually rather naive. There's an algorithm () with O(n) runtime for finding articulation squares (squares that would disconnect the reacheable area), and then one needs just one more breadth-first pass (again, O(n)) to find all chambers (create a new chamber each time you step on an articulation vertex). Then iterate over the leaf chambers to find the longest path to the root.

On the whole, I find because of extra work my search ends up going 1-2 steps shallower in open spaces. But then, as montanalow mentioned, I find that this algorithm finds things that simple area calculation would recognize only 20 steps later, so on the whole I decided to stick with it.
iouri_
Brigadier-General
 
Posts: 105
Joined: Thu Feb 11, 2010 4:16 pm
Location: Toronto, Canada

Re: Chambers, dead ends, and graphs with cycles

Postby Maxime81 » Wed Feb 24, 2010 4:19 am

I doubt of the real benefits of all of that because my naive approach is rarely wrong on small maps (< 25x25)... Anyway, it's still interesting !

I've just implemented the algorithm you're talking (http://www.eecs.wsu.edu/~holder/courses ... phapps.pdf) and I'm thinking of how I can use it (I'm implementing a chambers tree too)... But it's easy to see how using it in a survival mode but I don't know how I can take benefits from the cut vertices list in the voronoï compute... Any idea ?
Maxime81
Lieutenant-Colonel
 
Posts: 42
Joined: Sat Feb 13, 2010 10:56 pm
Location: INSA Toulouse, France

Re: Chambers, dead ends, and graphs with cycles

Postby analyst74 » Thu Feb 25, 2010 7:38 am

I don't see how chamber tree would be of any use in survival mode, after all, once you are separated from the opponent, the outcome of your moves are fairly straight forward, and accuracy of forecast will benefit more if you can look deeper.
analyst74
Major
 
Posts: 39
Joined: Wed Feb 17, 2010 7:45 pm

Re: Chambers, dead ends, and graphs with cycles

Postby Maxime81 » Thu Feb 25, 2010 1:26 pm

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

Re: Chambers, dead ends, and graphs with cycles

Postby grogers » Fri Feb 26, 2010 4:49 am

grogers
Lieutenant
 
Posts: 15
Joined: Fri Feb 19, 2010 4:08 am


Return to Strategy

Who is online

Users browsing this forum: No registered users and 1 guest

cron