Overview
I was playing the "Hare and Tortoise" board game and loved that it could be played completely without chance. You decide how many squares to move, not the dice. I thought this would be a good oportunity to code a computer to also play the baord game given its deterministic nature. I worked in Python to create version 1 then 2 of the engine, which is now capable of playing competitively with real players.
Currently, it uses a random branching search to explore possible moves from the current game state for each player. The algorithm I developed simply looks at the current possible moves, and how many games each player wins from each of these when later moves are made randomly. Over time, probabalistic behaviour takes over and the "most winning" move is identified, or least losing. The computer then makes this move.
As development, the computer is also evaluating everyone else's best moves, and gives higher probabilities to those moves being made. This then feeds back to the computer's own decision. For example, it may see that the density of moves it thought were winning following a certain branch are actually increasingly unlikely to happen, as other players chose their better moves more often.
The animated chart shows each of the three players' next possible moves, and how many games they win (or lose) following a random game after that move as the engine runs live. The computer (top) can see it is doing best with the middle option, to move forward 3 squares and spend 6 carrots. The human players would not see these graphs, as it would clearly give away player 3's best move, and disappoint player 2 that whatever move they make, they are most likely to lose.
Half way through the animation, you may notice the bars quickly change. This is the point at which the algorithm weights the other players' best moves more likely. You can see the effect this has as player 3 increases the number of their 4th option, player 2's slim advantage of their 8th and 9th option is reduced, as they are even less likely to win now that players are chosing better moves.
I plan to add further complexity to the algorithm in the future, enabling it to evaluate moves to greater depths down the branches of games. I also plan to increase the efficiency to enable more games to be explored.
If you want to try the engine for yourself, I keep an up to date executable version on my Github.
About the game
The German-style board game was devised by David Parlett in 1974 and became the first winner of the Spiel des Jahres award in 1979. Instead of rolling dice to move, you spend carrots, with longer moves costing increasingly more carrots. You can earn carrots in many ways, including moving backwards and landing on certain squares at certain times. The winner is the first player to cross the finish with less than 10 carrots in their hand, and after having discarded all their lettuces on the lettuce squares.
