6
$\begingroup$

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? :)

Improve this question
$\endgroup$
6
  • 4
    $\begingroup$ Did you see the recent analysis by Thanatipanonda Further Hopping with Toads and Frogs? $\endgroup$
    – Vor
    Jun 5, 2013 at 13:18
  • $\begingroup$ Interesting game, but I'm afraid this might be too hard a question for Computer Science Stack Exchange. From what I can tell from the Wiki page, this is a game for which there are still several important open questions, so asking for optimal algorithms or provably good heuristics may indeed be a research-level question. While research-level questions are fine to ask here, you might have better luck at cstheory.stackexchange.com $\endgroup$
    – Patrick87
    Jun 5, 2013 at 15:32
  • $\begingroup$ @Vor - thank you very much. The paper is very intersting but unfortunately, it doesn't get me any closer to the winning strategy as I'm still quite confused if evaluating the board using the tricks in Erickson, Winning Ways and this paper and then moving accordingly the best way to go or maybe one should take other factors into account as well. $\endgroup$
    – Straightfw
    Jun 8, 2013 at 16:57
  • $\begingroup$ @Patrick87 - thanks a lot, will crosspost it there :) $\endgroup$
    – Straightfw
    Jun 8, 2013 at 16:57
  • 1
    $\begingroup$ No, please don't cross-post. Ask the CS.SE moderators to migrate the question instead. $\endgroup$
    – JeffE
    Jun 8, 2013 at 18:06

1 Answer 1

Reset to default
9
$\begingroup$

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

Improve this answer
$\endgroup$
9
  • 1
    $\begingroup$ Thank you a lot for your insight. What do you mean by "exponential backtracking" - building a full game tree and then choosing the move which would lead to the most potential wins? $\endgroup$
    – Straightfw
    Jun 8, 2013 at 16:52
  • 2
    $\begingroup$ Not quite that simple; there are well-known algorithmic techniques to prune away redundant or obviously stupid branches of the game tree. But at least in the worst case, you'll still need to examine an exponential number of positions to find the absolute best move. $\endgroup$
    – JeffE
    Jun 8, 2013 at 18:02
  • 1
    $\begingroup$ I see, thank you very much. So basing on this, a better idea seems to be to evualuate a profit (or loss) after each of the possible moves (where a profit is how many more moves we'll have at hand after such move + how many less moves our opponent will have because of our move) and then evaluate all the possible opponent's moves, then again only the best of ours and so on. Does that sound right? That way, we don't have to evaluate a whole game tree (though we still do have to evaluate all the possible opponent's moves after ours and the first move's going to be very time-consuming). $\endgroup$
    – Straightfw
    Jun 9, 2013 at 9:59
  • 1
    $\begingroup$ Not so fast. In the position $\Box F \Box F \Box F T \Box^{100}$, Toad has only one available move and Frog has three, but Toad clearly wins by a landslide. What you're calling "profit" is better formalized as the value of the game, as defined in Winning Ways and used in my paper and Aek's. Unfortunately, computing the value exactly almost certainly requires an exponential search, and (even worse) the value isn't always a number in the usual sense. $\endgroup$
    – JeffE
    Jun 9, 2013 at 22:23
  • 1
    $\begingroup$ There are good heuristics for estimating values of combinatorial games using techniques called cooling and thermography; see volume 1 of Winning Ways for a good introduction. I don't think anyone has seriously tried to apply thermography to Toads and Frogs, though. $\endgroup$
    – JeffE
    Jun 9, 2013 at 22:38

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.