How to play

To begin, click on any bottom-most slot in any column.

This is Connect Four, a game where you and an opponent take turns placing coins down in slots, and the first to form a run of 4 coins wins. The 4 coins in a winning run can be horizontal, vertical, or diagonal. The coins fall down each column due to gravity, so you can only place them on the bottom-most empty slot in each column. You are yellow 🟡 and your AI opponent is red 🔴.

After every move, Your AI opponent will think and play a counter-move automatically, and you take turns until someone wins. You can auto-play moves, and you can undo your moves to try playing different ones.

What is this?

This is a technical demo of a game-playing algorithm called Monte Carlo tree search (MCTS). I've chosen to use Connect Four as the game, although MCTS is a general algorithm that can be applied to any game. The AI opponent 🔴 here "thinks" by running MCTS search for 1 second before making each move. For every move, the valid next-move cells are heatmapped to their simulated win frequency, which intuitively corresponds to how good MCTS estimates that move to be.

AutoPlay uses MCTS to pick a move for yourself 🟡. Because AutoPlay and opponent moves share one MCTS instance, you benefit from previous searches on ancestor nodes originally performed for the benefit of the opponent 🔴. Similarly, it will benefit descendant nodes regardless of the player.

Undo moves 2 states back so you can try playing different moves. I don't re-run MCTS search on previously reached states, so every state only gets 1 second of compute even if you reach them multiple times using undos. One annoying thing is that because I don't track updates to the MCTS statistics (I only track updates to the game state), the statistics accumulate to shared ancestors with undos. This manifests as super red heatmap cells if you undo to some ancestor after playing a bunch of its descendants.

Background

Monte Carlo tree search (MCTS) is a general game-playing algorithm to find the best move from any given game state of any game.

In 2017, I wrote a Medium article explaining the idea behind MCTS, and another one going through a JavaScript implementation. For a deeper dive into MCTS, please read those articles.

MCTS is one of those deep algorithm things that benefit from high performance, which JS isn't known for. I reasoned at the time that, since I'm running the project on Node.js, Chrome's V8 JS engine would give me good enough performance. While it did take me down a minor rabbit hole of JIT optimization, it actually ran well enough for the algorithm to self-play a tree that beats me convincingly at connect four.

The real reason I did it in JS was because it was the language I was most comfortable with at the time. However, I did foresee that implementing it in JS would theoretically allow me to run an interactive MCTS demo client-side, but I was too lazy to deal with setting up a whole web stack just to showcase it. Six years later in 2023, the React ecosystem has developed to the point of extremely mature and well-designed frameworks and deployment solutions (i.e. Next.js + Vercel), and they take care of enough annoying details that I managed to implement this in 2 days. The entire demo runs on your browser.