Survival Mode

[krzyk1]

[iouri_]

[dhartmei]

[Wolftrak]

[r0u1i]

This thread grew to a very interesting discussion.
Back to my original question - I've improved slightly on my "wall-hugging" technique and now allow up to one exception to the rule of "stick to the wall as much as you can". It seems to work very well, and although not perfect, I no longer lose due to poor survival technique (but still have to improve my fighting mode - current rank is only 90)

[AnAron]

Excellent idea dmj concerning the checkerboard. I know that puzzle and it didn't occur to me!

[dmj]

I appreciate the comments about the checkerboard idea. So, more formally the grid is a bipartite graph. I could not find any more efficient algorithms or ideas to take advantage of that. Any takers?

Most of the specialized bipartite graph seemed to deal with flow type problems, which did not seem to help much.

Oh well, I'm out of ideas. Good luck to all, this has been fun

[masharpe]

[Fritzlein]

[Letzlo]

I haven't seen my idea mentioned yet so I guess I'll chip in.

I visualized the problem as a graph (that is, a graph of a function, not a graph from graph theory) of the amount of reachable squares on every point in a path. The goal is then to make the inevitable decline of this graph as gradual as possible; a sudden drop in reachable squares would mean passing through a corridor before visiting all squares in the room you are in, while a slow decline (ideally of 1, which is the square occupied in the previous turn) would make sure that all (or as many as possible) reachable squares are visited before the bot exits the room.

I found that this approach works very well partly because it can go quite deep (floodfill can be done pretty fast). However as I never got to calculating articulation points it has its limitations, especially on larger maps where it can't go deep enough.