Chambers, dead ends, and graphs with cycles

[montanalow]

[iouri_]

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.

[Maxime81]

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 ?

[analyst74]

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.

[Maxime81]

[grogers]