Since there’s no editorial on the interactive challenge of April 2016, I’m going to contribute the main ideas of my approach. in my opinion the problem was pretty tough to implement and I wouldn’t consider my solution as very intelligent. I think it is still below the capabilities of a human opponent playing fast (on a human scale).
It turned out that in order to get many points it is most importatn to make the first snake as long as possible, the contribution of the rest is rather small. So I will concentrate on the first one.
Basic Motion (determined locally)
I tried to fill the board systematically, starting from somewhere near the bottom (high first coordinate) and slowly moving up. So whenever it had to be decided where to move next DOWN was favored compared to LEFT and RIGHT which in turn were favored compared to moving UP. On an empty board this would already produce a good solution. But combined with the initial blocked squares and Chef's motion the snake gets easily trapped in a small connected component. So something had to be done about that:Finding the right component to move on
At some point the snake will split up the connected component (wrt. to the conectivity induced by the 4 nearest neighbors) of the board into (most of the time) two distinct components. At this point the right (larger) component has to be chosen to go on. It was in fact possible to track the sizes of the components online during the evolution (described below).Some more improvements
There were some more improvements. While implementing them gave some more points it was difficult to choose the "best" method to implement them or the "right" factor by which they should contribute to the evaluation of the next move.- Head/tail of he snake should’t come too close to each other. Otherwise they are easyly killing each other (with the simple logic implemented). So I simply added a penalty for moves bringing the two snakes closer together (up to a certain distance).
- Similarily I didn’t implement much logic to evade chefs snake if it was close by. Instead i Just ran - i.e. used another penalty if chef’s head or tail is close.
- Typically evaluating moves just according to directions yielded a pretty rough surface. So in addition I tried to smoothen it somewhat by prefering to move to cells which already have neighbors.
- I didn’ t choose whether to move head or tail by evaluating the best move. Instead i moved them alternately (as long as possible) unless Chef’s snake was close to one. Then I ran.
Combining all the parts into an evaluation function yielded an algorithm which was able to cover roughly 30% of the cells with the first snake.
Keeping track of the components
This is some kind of reverse union-find-problem, starting with one (typically maybe 2 or 3) component. it gets split up during the motion of the snakes. Looking at it from a general graph-theoretic point of view there don't seem to be solutions which would run in time (as far as I know). Maybe the situation is better for the problem at hand but I didn't find anything which could be proven to be fast enough for the timelimit. My approach would definitly fail in a worst-case analysis but was fast enough to pass (by a pretty good margin) anyway.- Keep track of the components of blocked cells (with respect to the connectivity) induced by all 8! neighbors including two additional coloumns/rows of blocked cells on the sides of the board
- If the a snake (either mine or chef’s) covers a cell neighboring blocked cells of the same component, a new component of empty cells may have formed
- In that case I started a BFS from all neighboring empty cells in parallel. If two of them met I merged them. If one BFS runs out of cells it will define a new component. Continue until only one BFS is left.
- If no BFS was stopped due to running out of cells there’s no addionial component. Otherwise the components are the components identified by the stopped BFSs and the the component defined by the last remaining BFS combined with the remaining unexplored cells.