Optimal strategy for a game on a binary tree

Decision and strategy, simulations and probability models, card and board games, ...
Post Reply
wrongrook
Posts: 300
Joined: Sat Oct 17, 2009 9:39 pm

Optimal strategy for a game on a binary tree

Post by wrongrook » Tue Aug 26, 2014 6:20 pm

I have been struggling to solve a problem from CodeForces involving the optimal strategy for a two player game played on a tree. (This is a problem from a finished contest - but no editorial has been published yet as far as I can see.)

I have put a description of the problem on Stack Overflow http://stackoverflow.com/questions/25503886 but have not got any answers yet.

Anyone here got any suggestions?

It actually makes for quite a fun two player game. I've coded up an implementation here http://penguinspuzzle.appspot.com/blobs.html if you want to just play the game against a friend. Don't press the "Find best move" button for depths of 5 or above as it will take forever. (It just uses a simple non-memoising minimax search for the moment.)

Post Reply