Survival Mode

[r0u1i]

My bot, like many other bots currently in the arena, switches to "survival mode" once it detects that it cannot reach the other bot. That is, it tries to find the longest path in the available space. I'm currently using a very naive approach which is basically the wall hugger 's approach combined with checking on every step whether the available space is divided in to two compartments, and if so, choosing the bigger one.
Since finding the true longest path is in NP (as far as I remember), I wonder if anyone would like to share some tips on how to approach that problem in a more robust way.
thanks!

[dutchflyboy]

The longest path is NP if the graph is cyclic. However, in this case it isn't (each cell can only be visited once, which makes cycles impossible), so the problem is solvable in polynomial time. I haven't managed to get it working yet, so I can't guarantee it's fast enough to be usable. See http://en.wikipedia.org/wiki/Bellman%E2 ... _algorithm

[Fritzlein]

Nice try, but the fact that you are constrained to visit each node at most once doesn't mean the graph is acyclic, it only means that your path within the graph is acyclic. Playing Tron perfectly in survival mode is therefore quite probably NP-hard, and the near-to hand proof is to reduce some form of Hamiltonian Cycle to it.

[dutchflyboy]

Ah well, that at least explains why I can't get it to work right. I thought it was some error in my code that made my program hang. But if it's NP-complete it's not that strange that it doesn't work. Back to the drawing board!



EDIT: Who added the owned image??? I know it's valid, but still... it's not very polite.

[grogers]

What I'm currently doing when isolated from the opponent is searching depth first (but limited by iterative deepening) through all possible moves. Ties are scored by the number of reachable squares from the end position. Near the end of the game or when the board is not very open, on my computer this can often search through all possible moves (often up to a depth of about 40) to find the guaranteed optimal choice. Even when it doesn't pick the optimal choice it can often do a pretty good job of filling the space almost optimally.

Another improvement is to handle dead-ends separately from open space. If you have two dead ends that you can reach, you know it would be impossible to visit both of them. So you can take the longer of the two and make that the one that counts towards your number of reachable squares. This addition prevents the bot explained above from creating a new dead end when one already exists, which would prevent it from filling the space optimally. I have an example of this behavior, but I have since resubmitted my bot and can't find the game it was in...

In any case, filling the space perfectly is very important, because often you will get separated into equally sized compartments (or you would just try to draw beforehand). If you don't fill the space as good as your opponent does, you will lose. Also important is accurately scoring the number of reachable squares of your bot versus the opponent's (esp. in close matches) - if you are not reflecting the true count even just by one, you may make a suboptimal move into a space that you think is bigger than it really is and lose.

[iouri_]

I use pretty much the same strategy when in "survival mode" as compated to normal mode. I use minimax several steps deep where the cost function is as follows:

- split the playable area into cells that you can reach first and cells that your opponent can reach fist
- divide each area into a tree of 'chambers', where if you go down one branch of this tree, you eliminate other branches (i.e. say you've one corridor that splits into two dead-end corridors: you can go down only one of the dead end corridors; first corridor is the first chamber, which has two child chambers: each of the two dead-end corridors).
- find the sequence of chambers that you can reach with the highest total cell area.

When in survival mode, it fills the space pretty much perfectly, I am yet to see it make a mistake that's not due to me screwing up implementation. It's also a pretty decent heuristic for minimax when you're still in the same area as your opponent (though others are better).

[Maxime81]

iouri_, I was wondering how you actually do your "tree of 'chambers'" ? The only algorithms I have in mind are too complex in time to be usable.

[iouri_]

[Maxime81]

Well, thanks a lot, I'll re-read it later (I'm on something else than this contest right now).

Currently my algorithm is quite simple :

First thing : Am I in the same area than my opponent ? If false, I'm gonna ignore his possible moves and then I just maximize the size of the area few moves deep (DFS, I just reuse my minimax in fact) using floodfill.
If i'm not alone, I use MinMax algorithm to find the best move. The evaluation considers the voronoi score and if I'm far from my opponent, the distance from him (A*).
I evaluate the depth using the size of the area, the map and my position (bfs to count the number of leaves).

So my survival mode is only based on a floodfill calculated few steps forward. And most of the time, because the maps are small, it's doing great. If there are less than approximatively 1000 different paths, they are all calculated and compared.

Edit: My algorithm is fooled here : http://csclub.uwaterloo.ca/contest/visu ... id=3976519 .

[bruudruuster]

Hi,

My space filling (aka survival mode) strategy so far is a simple DFS with a cost function that basically optimizes the area left to fill. There are some simple extensions, e.g. a tendency to wall hugging and not counting simple dead-ends, to improve things.

I am currently testing a strategy similar to iouri_'s chambers, but based on computing articulation vertices. This requires 2 scans over the accessible part of the board to first compute the articulation vertices and then a scan to select the largest chambers on forks in the chamber tree. I haven't figured out a way yet to do this in one pass.

The nuisance is that this algorithm does not perform better than the simple one. I am testing it on a 20x20 random board where I can do up to 400k evaluations/second of the more complex evaluation function and up to 680k evaluations/sec of the simpler one. The difference is that the "correct" move is out of the horizon of the search with the more complicated evaluation function but the simple one finds it.

Anyone with a similar experience?

Cheers.