Making Expert Connect 4 AI

I program a Python connect 4 AI to play against real people online. How well do you think it will do?

After implementing connect 4 in Python, I choose an algorithm that will power the connect 4 bot. The algorithm, minimax, searches the entire game tree, or all possible game states, to come up with an optimal move every single time. Unfortunately, there are so many states in the game that it is impossible to search the game tree in any reasonable time in Python (which is slow compared to low-level languages like C++). Specifically, given a few seconds per move, my Minimax agent could only look 5-6 levels deep, when 42 levels is required to search the entire game tree (because a game of connect 4 can take at most 42 moves). Even with techniques like Alpha Beta Pruning and using a Transposition Table (which I did not mention in the video), the code would be too slow. In a future video, I'll consider using Minimax and program it in C++ to see how well we can do.

Instead, I used an algorithm called Monte Carlo Tree Search. This algorithm takes in the current state of the game and for each possible move, it simulates the game to a terminal state (until the game ends) randomly. Using the result of the simulation (win, loss, or draw), the algorithm slowly builds up the game tree, storing the statistics of each position (basically, how favorable each position is) at each node in the game tree. When we go from a root of the tree to a node, we use an approach called UCB (Upper Confidence Bound), which allows us to both explore unseen positions and moves while also trying to choose moves that have been proved to be good in prior simulations. I will link more resources about this algorithm in the description.

After giving MCTS a reasonable 5 seconds per move (we do not want our opponents waiting for too long!), it can get 4,000 to 5,000 iterations during that time. The more iterations, the better the result. So, I change the architecture of my game to store the states using two integer - a mask and a position, both of which represent the state of the game in binary. Using binary arithmetic, we can figure out what legal moves are allowed and whether the game has ended very fast. This speed increase allows my new algorithm to get 12,000+ iterations in 5 seconds - huge improvement!

After this, I tweak the algorithm by having it run more simulations once it finds a node, which saves time on traversing the tree and leads to more precise play. This last version beats the previous version over 70% of the time, so I kept it.

On the PaperGames website, my connect 4 Python bot hit top 10 within a few hours with a win rate over 70%. This is pretty good, given that most of the other top 10 players were also bots running for 8+ hours per day and likely using a fast C++ M ... https://www.youtube.com/watch?v=42bkrj19swo