Building a Connect Four AI

Connect Four is a two-player game sold by Hasbro, played on a 6x7 grid. Each player alternates dropping coloured discs into one of the seven columns. The discs fall to the lowest available space within the selected column. The objective is to be the first player to align four discs in a row, which can be achieved horizontally, vertically, or diagonally. The game reaches a draw if all 42 spaces are filled without either player achieving this alignment. Given these rules, Connect Four classifies as a perfect information zero-sum game.

As a solved game, Connect Four allows the first player to always secure a win with optimal play. However, identifying the optimal move in real time for each board state using a brute-force approach, as I did with my Tic Tac Toe AI, is not feasible in Connect Four due to the game's complexity. To address this, I programmed an AI using the minimax algorithm with alpha-beta pruning for decision-making. However, unlike my approach in Tic Tac Toe, this AI does not search the entire game tree. Instead, it limits its foresight to a certain number of moves and employs a heuristic to estimate the value of non-terminal board states at its maximum search depth.

The core of the heuristic lies in evaluating the difference in the number of potential four-in-a-row alignments for each player. This method was chosen based on the intuition that immediate wins and losses are identified within the search scope. At the same time, board states that preserve more opportunities for future alignments increase the likelihood of winning as the game progresses.

To introduce an element of unpredictability and to adjust the difficulty level, I incorporated random noise into the AI's value estimations at each depth. This addition means the AI might occasionally select suboptimal moves, particularly when the path to a forced win or loss is not immediately evident. Such a strategy ensures a balance between challenge and accessibility, making the AI a versatile opponent across various skill levels. Below is a Python implementation of the algorithm.