3-5-7 (Part 2)

I wrote about the board game 3-5-7 in my previous post.

I wrote this program to as an experiment in AI. A simple board game seemed to be a good way to start. The program implements the minimax algorithm for determining the best move.

3-5-7 is a simple game, so the program can explore the entire problem search space. This means that if there is a winning move, the computer will find it.

3-5-7 also has a clear winner. Unlike tic-tac-toe, draws are not possible. Therefore, if there is no guaranteed winning move available, then the opponent has a guaranteed winning move irrespective of the move you make. In particuler, the player playing first has a winning move, so the first player cannot lose if the player plays a perfect game. Make a mistake however, and player 2 has a winning move.

When the computer has no winning move and is guaranteed to lose irrespective of the move it plays (provided the player plays perfectly), then how does it choose which move to make? Against an experienced player who knows how to play a perfect game, it does not make a difference which move is played. However, against a novice, some moves are more adept at inducing mistakes.

This is where the Strategy classes come into play. The program implements two strategy classes - RandomStrategy and FilterStrategy. RandomStrategy randomly chooses a move. FilterStrategy gets rid of moves that leave the board in obvious states, and chooses from the remaining moves. This has the effect of increasing the chance that the novice player will make a mistake and give the computer a winning move.

To implement other algorithms for choosing a losing strategy, we just need to implement another strategy class and set the strategyClass variable in the first line of the main program to point to this class.

The boardstate variable is initialised to [3, 5, 7] in the main program. We can change this to try playing with different number of coins. Change it to [21, 23, 25] and we can see how slow the AI is because it no longer becomes feasible to search the whole tree. An interesting evolution would be to limit the depth of the tree searched by the AI and see how it performs. Pruning the search and implementing heuristics are other possible improvements.

One interesting technique to learn the perfect moves is to play the computer against itself. Start two instances of the game. Play first in one, and play second in the other. Feed in the moves played by the computer in the first game as the player move in the second game, and vice verca (in effect playing the computer against itself). Soon, you will get a hang of the better moves.

This post is a part of the selected archive.