It is currently Sat Dec 07, 2013 10:46 pm Advanced search

## Survival Mode

Share and discuss ideas for your entries here.

### Survival Mode

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!
r0u1i

Posts: 6
Joined: Fri Feb 19, 2010 9:48 pm

### Re: Survival Mode

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
dutchflyboy
Colonel

Posts: 57
Joined: Sun Feb 07, 2010 1:08 am

### Re: Survival Mode

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.
Fritzlein
Colonel

Posts: 81
Joined: Thu Feb 18, 2010 9:20 pm

### Re: Survival Mode

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.
Last edited by dutchflyboy on Sun Feb 28, 2010 10:25 am, edited 1 time in total.
dutchflyboy
Colonel

Posts: 57
Joined: Sun Feb 07, 2010 1:08 am

### Re: Survival Mode

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.
grogers
Lieutenant

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

### Re: Survival Mode

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

Posts: 105
Joined: Thu Feb 11, 2010 4:16 pm

### Re: Survival Mode

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.
Maxime81
Lieutenant-Colonel

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

### Re: Survival Mode

Yeah, the algorithm takes a while to run, though that means that in my original c++ implementation I could run it 'only' ~20,000 times per second (complied with MSVC, with /O2 flag, running on a decent Core 2 Duo, forget exact specs) on 15x15 maps.

Algorithm goes as follows:
Part 1. Split the area into cells that your opponent can reach first, and the cells that your bot can reach first. If a cell can be reached at the same time by both bots, it's not included in either area. I did this originally by doing the following:
- label the cell where my bot is as '1', label the cell where the opponent is as '-1'. Add them to the queue of cells to be examined.
- While the queue is not empty, take a cell from the queue, call it the 'current cell'. Look at all of its neighbours. Label all its unlabeled neighbours as ({currentCellLabel} + sign(currentCellLabel)). This way, all the cells immediately next to your position will be labeled as '2', all cells one more step away will be labeled as '3', etc. Likewise, for your opponent, all cells one step away from it will be labeled as '-2', all cells two steps away will be labeled '-3', etc. Add all newly labeled neighbours to the queue of cells to be processed.
- Obviously, it's very likely that the two areas will be gradually spreading and will run into each other. Thus, if the current cell has a neighbour that has the opposite sign and a label with absolute value (abs(currentCellLabel) + 1), then the neighbour is a neutral cell, and should be relabeled as '0' (or whatever you chose the neutral label to be).

This does preparatory work of finding which area is whose. This step can be actually rolled into part 2, but the algorithm is easier to explain if this part is separate.

Part 2. Create the tree of chambers. For this, we will need:
- a matrix the same dimensions as the map; this will store which cell is in which chamber. Call it the 'chamber map'.
- a 'chamber' class that will describe chamber objects; will have member variables:
* entrance (refers to a valid cell in the chamber map)
* size
* whether a chamber a leaf chamber - true if this chamber doesn't lead to any more chambers, false otherwise
* note that a chamber does not directly contain links to parent or children; you never really need to access children, and the parent will be chamberMap[thisChamber.entrance] (if you want, you can wrap this in a function call).

The algorithm below will construct the tree of chambers only for the your bot; it's easy to generalize this to work for both bots. The algorithm:
- on the chamber map, set all cells as belonging to no chamber.
- Create the first chamber (chamber 1), set its entrance to be the cell where you were before you stepped on the current cell (note that chamberMap[chamber1.entrance] == no_chamber). Set the chamber1 size to 1.
- Set chamberMap[yourPosition] = chamber1. Add your position to the queue of cells to be processed.
- While the queue is not empty, take a cell from the queue. Call it 'currentCell'; call the chamber it belongs to the 'currentChamber'. For every neighbour of currentCell:
* if the neighbour is not in the area that is closer to your bot (from Part 1), ignore it.
* if the neighbour has not been assigned to a chamber and is not a bottleneck (i.e. there's extra empty space on the sides - specifics are left to the reader), set chabmberMap[neighbour] = currentChamber; increment currentChamber.size. Add the neighbour to the queue.
* if the neighbour has not been assigned to a chamber and is bottleneck, create a new chamber (call it newChamber), set chamberMap[neighbour] = newChamber, newChamber.entrance=currentCell, newChamber.size = 1. Add the neighbour to the queue.
* if the neighbour has been assigned to a chamber, and if it is currentChamber or is the entrance to currentChamber, ignore it.
* if the neighbour has been assigned to a chamber which is not currentChamber (and is not the entrance currentChamber), merge the two chambers. This is actually relatively complicated operation that requires you to determine the lowest common parent chamber and merge them into this common parent; chamberMap will need to be updated too. The specifics are left to the reader. After this is done, do not add the neigbour to the queue of cells to process.

After all this is done, just iterate over the leaf chambers, computing the total size of the path from the root chamber to the leaf chamber. Pick the best one.

Hope the general idea of the algorithm is pretty clear. There are a number of things that can be done to speed up the execution, and I've obviously omitted some of the details. That should be a decent starting point though.
iouri_

Posts: 105
Joined: Thu Feb 11, 2010 4:16 pm

### Re: Survival Mode

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 .
Maxime81
Lieutenant-Colonel

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

### Re: Survival Mode

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

Posts: 6
Joined: Fri Feb 12, 2010 10:13 pm

Next

### Who is online

Users browsing this forum: No registered users and 1 guest