I am looking for an algorithm (or hint where to start), for Toads and Frogs Game. What I am interested in is not how to solve the problem (it's NP-hard), but how to plan one player's moves. I.e. how to design a computer player (AI), which could win against another player (another program or human player). I was looking for some clues but with no luck so far, there's not much about it on the Web.

Link to game description on Wikipedia.

And here you can play the game. Please bear in mind, that starting positions may not be that straightforward. They may be mixed up from the very start.

  • 1
    $\begingroup$ It's hard to answer this since there'a a gazillion ways an AI could play. Whether a specific strategy is better than another is more or less anybody's guess. Start with something very simple, and see how it could be improved. If you can't even start with anything really, read about something suitable (Russell & Norvig is a good starting point). $\endgroup$
    – Juho
    May 6, 2013 at 17:18
  • 1
    $\begingroup$ If you are already somewhat familiar with the AI literature, something I've found really cool recently is the Monte Carlo Tree Search. There's much hype about it right now. $\endgroup$
    – Juho
    May 6, 2013 at 17:22
  • 1
    $\begingroup$ How big are your problem instances? The average (single-row) Toads&Frogs position may have hundreds of subpositions, which makes expressing the value as a combinatorial game difficult, but is still an almost-trivial search for any actual game tree algorithm, and even several rows summed should be easy to search (particularly combined with judicious use of the Number Avoidance Theorem). $\endgroup$ May 6, 2013 at 17:34
  • $\begingroup$ Certainly there will be humans who won't know all of "New Toads and Frogs results", and as @StevenStadnicki said, things like the Number Avoidance Theorem, too. Simply using those would probably do better (or at least more efficiently) than a method without them. $\endgroup$
    – Mark S.
    Nov 25, 2013 at 13:01


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy