Automated Four in a Row

Explorations in Tree Searches and Game Algorithms

Hi There!

We implemented and tested a Monte Carlo Tree Search algorithm that can successfully play Connect Four against a human player or another simulation.

In the process, we learned about the logic behind the approach, trained our algorithm, and built an alternative minimax simulated player. In this website, we included our findings, research, and conclusions. Take a dive in the world of board game bots and connect four!

Connect Four

Connect Four is a game in which two players take turns dropping colored pieces into a vertical grid.

The objective of the game is to create a sequence of four pieces in a row horizontally, vertically, or diagonally.

The Monte Carlo Tree Search algorithm determines the best move possible for our player given the results of many game situations.

Each node in the tree represents a unique game state.

For each potential move, the computer plays multiple simulation games, choosing random moves as necessary until a win/loss/draw is reached.

The algorithm then backpropagates up the tree, updating values at each node depending on the outcome.

The move with the best win rate is the move taken by the player.

Minimax

The Minimax Search Algorithm is a graph decision algorithm used, in this case, to offer move candidates for our connect four bot.

Its name comes from its goal to minimize the score of its opponent while maximizing the bot score at every move made.

In contrast to the MCTS, it doesn't play out the game tree entirely.

Performance

While our MCTS-based computer player will not be going pro anytime soon, we looked into analyzing what it would take to make our implementation a tough competitor.

Bibliography

Made with ❤️ at Olin College. source code (opens new window)