Survival Mode

[iouri_]

Maxime81: looks like your strategy beat mine..

[iouri_]

[montanalow]

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.

[callinwire]

[Maxime81]

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...)

[iouri_]

[Maxime81]

[iouri_]

[dmj]

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.

[a1k0n]

dmj: that's not useless, that's utterly brilliant. Gives a tight upper bound without any computation to speak of.