[Solved]: Finding a winning strategy for toads and frogs

Problem Detail: 

Recently I got interested in a game called Toads and Frogs and I'm trying my best to come up with some software which would be able to beat an average (i.e. not knowing the strategy) human though I'm struggling with the strategy.

I read on it everything I could google out but turns out there's not that much to read about it as one may think - the most helpful thing I've found was probably an analysis by Erickson though it concentrates more on evaluating each position rather than some algorithm which would have to decide how to move a toad or a frog given a particular board as input. Same goes for "Winning Ways", where they evaluate a bunch of positions but don't give you too much insight on how to optimally play your game

The best playthrough strategy I could come up with is evaluating the value of the current position (using "Winning Ways" and Erickson's tricks), evaluating the values of all the positions we can go to with our toads/frogs in a given moment and then performing a move which leads to the lowest value of the board so that our opponent has the worst moves to choose from.

Is there anything better? Or if all the "good" strategies are very hard (as I said, I'm just starting out with my game theory interest), what's the best one that even someone with my experience could utilize? :)

Asked By : Straightfw

Answered By : JeffE

Ultimately, unless you can prove something very interesting, you're stuck with exponential backtracking. For at least one natural encoding of positions, Toads and Frogs is NP-hard.

Jesse Hull observed that the position $T^n\Box TFT^m \Box TF$ has the game value $\{m+n-1\mid \{ n\mid 2 \}\}$, which means

• If $T$ moves first, $T$ gets $m+n-1$ free moves.
• If $F$ moves first and then $T$, then $T$ gets $n$ free moves.
• If $F$ moves twice, $T$ gets $2$ free moves.

By combining this position with positions of the form $T\Box^x$ and $\Box^y F$, we can set up a position whose value is $\{a\mid\{b\mid c\}\}$ for any integers $a,b,c$.

Yedwab and Meows proved that determining which player wins a sum of games with values $\{a_i\mid\{b_i\mid c_i\}\}$ is NP-hard. A sum of games is a set of games that are being played simultaneously; each player can choose which game to play in on their turn; and the first player unable to move at all wins. Toads and Frogs positions often decompose into sums; for example, a position that contains $TTFF$ is equivalent to the sum of the pieces to the left and the pieces to the right.

These two results imply that playing Toads and Frogs optimally is NP-hard if positions are run-length encoded. That is, any string of $n$ frogs should be encoded using only $O(\log n)$ bits, encoding the integer $n$ in binary, not using $O(1)$ bits per frog.

It is possible, although I think very unlikely, that an optimal move in Toads and Frogs can be computed in polynomial time if the input position is encoded as a simple string over the alphabet $\{T, \Box, F\}$. (Yedwab's NP-hardness proof is a reduction from PARTITION, which is only weakly NP-hard.)

Best Answer from StackOverflow

Question Source : http://cs.stackexchange.com/questions/12471