Connect Four AI

Program and Hardware Design

The Connect Four game infrastructure is implemented in C and runs on the HPS while the AI logic is implemented in hardware on the FPGA. The current game state is communicated between the HPS and the FPGA via shared SRAM memory.

The game infrastructure utilizes an 84-bit value to represent the current state of the game. Each position of the 6 x 7 Connect Four board is represented by two bits of information, with 00 = empty position, 01= AI token, and 10= human player token. This 84 bit value is segmented into 6 14-bit rows that are individually stored at a distinct memory address in shared SRAM memory. The FPGA then has to perform six sequential SRAM reads in order to obtain the full game state written by the HPS. The structure of the 84-bit game state value and how it maps to the Connect Four board is shown in the diagram below.

On the FPGA side, the Connect Four AI implementation utilizes a top level finite state machine to read the current game state from SRAM, compute the next AI move, and write the new move to SRAM. The top level FSM is depicted in the diagram below.

The FSM first reads the value at SRAM address 0, which serves as a flag to communicate between the FPGA and HPS when a new human player move is available. If there is a new move, the FSM progresses to read the next six memory locations, otherwise it returns to the initial state. SRAM address locations 1-6 contain the 14-bit game states of each of the six Connect Four board rows. Once the full game state has been read from SRAM memory, it is fed into the AI compute module, which determines the next AI move in a single cycle. There are two AI compute modules that are utilized throughout the game. During the first four rounds of moves, a simpler and purely defensive AI module is utilized when the board is relatively empty, which evaluates the next move based only on our defensive heuristic. After this, our full AI compute module (described in detail later) is used to determine the next AI move. This new AI move is then written to SRAM memory at address 7, and the HPS is signaled that a new AI move is available.

The hardware implementation of the AI compute module is shown in the block diagram below.

The top level AI module is implemented entirely in combinatorial logic. It first utilizes seven genStateFrom Column modules to produce an 84-bit game state for each of the possible next AI moves. It then utilizes a trap determiner module and a move determiner module per newly generated game state. These modules produce predicted moves based on a predicted game state one move ahead of the current game state. In parallel, the AI move also utilizes another moveDeterminer module using the current game state to make two priority checks: 1) if the AI can win in the next move and 2) if the AI must block the human player from winning in the next move. The AI out logic prioritizes these checks as determined by the rightmost moveDeterminer module in the diagram before considering the parallel moveDeterminer and trapDeterminer logic outputs. The outputs of the trap determiner module are fed directly into the AI out logic. The move determiner modules output a maximum heuristic value for a particular human player move given the generated game state. These seven maximum values are fed into a findMinimum module that outputs the minimum of these heuristic values. This value is then used in the AI out logic to determine the final AI move.

Each moveDeterminer module utilizes seven maxConnectFinder modules, as shown in the block diagram below. The maxConnectFinder modules receive as inputs the rows of the generated game state and use the same heuristic to produce a value corresponding to each of the seven possible moves. It outputs the maximum of these values. Each of these correspond to the move that the AI determines is the most likely for the human player to play given each of the possible game states. The moveDeterminer module utilizes the minimum of these maxConnectFinder outputs to produce the best AI move, predicting the human player’s next move.

The maxConnectFinder module utilizes the following logic to compute a heuristic value for a given move column and game state. It first checks to see if playing in this column given the input game state will produce an AI win. If so, it assigns this move the highest possible value. It then checks to see if a move in this column is necessary to block a human player win on the next move; if so, it assigns this move the next highest value. It then assigns the column a value equal to the weighted sum of the number of consecutive opponent tokens bordering the next open position in that column. So, it assigns a position next to a string of two opponent tokens a higher value than a position next to just one opponent token. It also takes into account open spaces between player tokens, i.e. it assigns a position that has an opponent token on either side the same weighted value as a position next to two consecutive opponent tokens because placing an opponent token in that position would result in a string of three opponent tokens in both cases. This same maxConnect logic is used both in determining AI moves and in the reverse case, predicting human player moves for looking ahead.

There are seven trapDeterminer modules in parallel with the seven moveDeterminer modules. Each trapDeterminer module also takes in the newly generated gameState. The trapDeterminer module first utilizes seven winFinder modules to determine if any of the moves given the input gameState can generate an AI win, which the human player would most likely block in its next move. If so, it generates a new gameState using a genStateFromColumn module with a human player token in that blocking position and subsequently uses seven more winFinder modules to determine if an AI win is possible.

Regarding the software design itself that is running on the HPS, as aforementioned, the main goal of the C code is to act as an intermediary between the FPGA (which is actually computing the AI’s next move) and the VGA display of the Connect Four board. Additionally, due to the remote nature of this semester due to the COVID-19 pandemic, we also needed to utilize the C code to serve as the user’s interface for inputting their moves into the game.

The C code begins by including all relevant libraries and setting up the shared memory-mapped addresses between the FPGA and the HPS (for example, for the VGA interface, the shares PIO port for HPS-driven reset to the FPGA, and the base address for the shared on-chip SRAM used to communicate between the HPS and the FPGA). It then toggles the reset on the FPGA. Once this initialization, as well as other variable initialization, has been complete, the C code draws an empty Connect Four board on the VGA by means of drawing perpendicular vertical and horizontal lines to create a 6x7 grid, and by placing discs in each created square. The game then prompts if the user would like to go first or not, and lets the user type into a terminal the column it would like to place its move in. There is some basic error checking to ensure that the entered column is valid and can actually have a token placed inside of it, and this error checking code will constantly press the user for a valid move until one is inputted (via use of a do...while() loop). Once these error checks are satisfied, the C code will call a helper function called placeDisc() that will take the user’s inputted move, a variable tracker that keeps track of what row to place a token in for that particular column, and the player that inputted the move (AI or user). The placeDisc() function then overwrites the corresponding disc on the VGA display with the appropriate color, updating the player’s move in real time.

After the user’s move has been played, it is necessary to update our game state representation (recall this was the 14-bit representation of each row of the board that indicated which tokens were placed where). To do so, we used an updateGameState() helper function, which took as an input an array used to track the game state rows, the row we would be placing our token on, the corresponding column of that placement, and which player made that move. The function then does binary-based arithmetic, an optimization that was necessary due to the nature of the data we would be sending to the FPGA for processing. To update the game state row, it is important to note that we are effectively adding a power of 2 to the current game state representation. As such, the code determines the exponent of the power of 2 we are adding (by using the column_to_place as well as the player), and then raises 2 to the power of that exponent and adds that to the original game state row.

After all our trackers have been updated to reflect the player’s move, this data (all row game states) is sent over to the FPGA via the shared on-chip SRAM. The C code then indicates there is new data available to the FPGA, which will then read the data, perform its computation, and then write to a new location on the SRAM the move that the AI would like to make. The C code would then perform the same process it did for the player’s move (displaying the appropriate disc, updating the game state, etc.) before repeating the process. Note that our game framework has the inherent assumption that the AI will not return an invalid move to the HPS. Also note that all updating of the game states, even on the AI side, is done by the HPS to make the interface easier and require latency from on-chip SRAM accesses.

One of the last portions of the C code to be discussed is the logic implemented in order to determine whether the game has ended. This function, called checkGameOver(), is performed every time someone plays a move (player or AI), and returns 0 if the game is not over, 1 if the game is over and the player who just played has won, or 2 if the game is over and it is a tie. To do all of these checks, the C code must again do binary arithmetic to check for certain cases. As such, based on the player who has just played, the checkGameOver() function will check for certain patterns (i.e. 10101010 in a row, which is the decimal 170, to determine if the AI won) in order to determine whether someone has won or not. Other patterns to check involve checking 4 in a column (which was done via shifting the values in game state rows for 4 rows by the same amount and checking all 4 entries), checking 4 in a diagonal going from lower left to upper right (which was done by checking 4 different game state rows with shift values, aka columns, varying by 1 per row), and checking 4 in a diagonal going from upper left to lower right (which was done by a similar process). Should none of these checks have worked, we check whether the board is full to determine whether a tie has occurred. Else, the game is still ongoing.

If a game over condition has been detected, the program will output a corresponding message to the user’s terminal. It then prompts the user on whether they wish to play again or not, which they can also input via terminal. This play again functionality was possible by putting our entire code inside a do...while() loop and appropriately spreading out our initialization functions so that we can start a fresh game (with a new empty board VGA display and all our internal game state trackers reset). All of this functionality put together enabled a nice gameplay experience that allows a user to truly train their Connect Four skills against an AI that makes decisions comparable to one that an above average Connect Four player would.

AI Design Iterations

When we first researched existing implementations of Connect Four AI’s, a common trend we found was the use of a Minimax algorithm for deciding moves due to the zero-sum-game nature of Connect Four. That is combined with recursively traversing game state trees in order for a properly-programmed AI to always make the optimal move. Our first approach was to try and figure out how we could implement this in hardware on the FPGA, but the immediate roadblock we faced was how we would be able to keep track of exponentially increasing game trees. Consider an empty playing board; there are seven possible first moves, and thus 7 “root” game tree nodes. From each node, there are 7 more potential moves, and so with each iteration of the game the size of the tree increases exponentially. Although still theoretically possible with very careful memory management and re-usage of hardware modules within a complicated outer FSM, we instead decided on a more iterative design approach. We wanted to first implement the overall framework of the game, and then implement more of the AI behavior as we progressed rather than trying to implement recursion and Minimax from the get-go.

After the framework was implemented, our first behavioral model was a fully-defensive AI (first generation) that would, on its turn, strictly evaluate the current game state and play in the spot where the human player would have the highest “profit” (heuristic value) if the human player were to place there instead. We evaluate profit as shown in the following code snippet:

Where given a rowArray representing the current game state along with a moveColumn and moveRow dictating exactly where the piece is to be placed, a profit value is assigned for a specific direction based on the number of consecutive player pieces such that longer connections result in higher profits. These values are calculated for the top left, top right, left, right, bottom left, bottom right, and bottom directions, and summed up to give an overall profit value. This summation occurs within the maxConnectFinder module, and seven of these modules are instantiated in the moveDeterminer module, one corresponding to each column of the game board. The profit values for all seven are calculated, the maximum profit is found, and the column holding that maximum is chosen as the move. In a tiebreaker scenario, priority is given to the middle column, then alternating left and right going towards the outer edges of the board since moves placed closer to the middle tend to have higher potential for connections.

The behavior of this basic AI was rather limited. As it was using a completely defensive heuristic, it would successfully make moves that blocked long connections and would prevent the human player from easily connecting four in a row. However, the AI itself had no concept of aggression, and was also highly susceptible to being trapped due to the lack of knowledge of game states resulting from its current move. This would also lead to scenarios wherein the AI would place a move that enabled the human player to win on the immediate next turn. Of these issues, the main modification we made to this iteration of the AI was checking not only the opponent’s profit, but also the AI’s own profit to see if it could immediately win. In the case that it could make a move that connected four of its own, it would do so in order to win the game. However, against any competent human player this modification made little to no difference in the overall difficulty of the AI. This initial AI, along with the subsequent iterations, was implemented in our final design due to the value that it provided for accurately detecting if the AI needed to make an immediate move to either (A) prevent itself from losing, or (B) win by connecting four immediately.

The next iteration of the AI behavior incorporates looking ahead one move to observe the opponent’s maximum profit given the AI making a move in a certain column on the previous turn (second generation). This would change the AI behavior to prevent it from making a move that would cause it to lose on the next turn (unless forced to), and would also give us an opportunity to implement a pseudo-minimax algorithm. By finding the opponent’s maximum profit given a certain AI move, the AI could then choose to make the move that minimized the opponent’s maximum profit. This comes with the added benefit of being able to use the same maxConnectFinder module without needing to change its functionality. In order to implement this, we needed to first generate seven new game states corresponding to the AI making a move within each column; this was done with the genStateFromColumn module which takes the current game state, player, and a column as an input, and returns the new game state with the designated player having made a move in that column. By instantiating seven of these, all possible game states after the AI move could be generated; these are then fed into seven moveDeterminer modules (resulting in 49 possible move determinations). Within each of these modules, the opponent’s highest potential profit is found for the given AI move, and then the minimum of these values is chosen in order for the AI to make a move allowing the human player the least possible profit. After implementing this, we found that the AI no longer made moves that caused it to lose on the next turn. This significantly raised the playing level of the AI, since it was now much more common to play the AI to a tie if the human player did not set any traps. Furthermore, by choosing the move that limited the human player’s maximum profit, the AI’s overall move choice was significantly improved in terms of difficulty for the human player. The weaknesses of this design, as we observed, were still that it was unable to detect human player traps (since it could not look far enough ahead) and also that it would often find itself in winning trap configurations, but because it did not recognize them, would give the human player opportunities to block it. However, the logic for this AI is the dominant behavior in our final implementation since we deemed it rather sufficient in terms of gameplay difficulty.

The last iteration of AI behavior modifications (third generation) was to allow the AI to detect its own trap setups. To do this, after taking the possible game state outputs of the genStateFromColumn modules, the AI checks whether it currently has a winning configuration, i.e. the human player is forced to block it on the next turn. This is done with a new winFinder module, which has similar functionality to maxConnectFinder, but only returns whether an AI winning move is detected. Based on the move the human player is forced to play, another genStateFromColumn module is used to create that game state, and another layer of winFinder modules is used to check if the AI can win on the next move. This effectively looks ahead in time by two moves, but only identifies if the AI can obtain a winning trap configuration. A major reason we implemented this is to add another element of aggression to an otherwise almost purely defensive AI.

The reason we chose not to implement detection of human player traps is simply because it would require analyzing three moves ahead of the current game state: given AI move, analyze human move, then analyze next AI move, then analyze subsequent human move. In order to effectively implement this, an extra iteration would require 49 * 7 profit evaluation and determination modules, which we felt would push our hardware utilization beyond the limits of the FPGA given the fact that our current implementation (with all three AI iterations effectively in parallel) already used 54% of the ALM’s on the board, and thus would likely not be able to fit an additional level due to the exponential size increase.

Thus our final AI implementation incorporates all three iterations as follows:

foundMax[7] takes the maximum value found in the moveDeterminer module associated with the first-generation AI as a check to see if there are any moves it must make immediately to win or prevent itself from losing. AllFull is a check in case there is only one valid move left on the board. In the case where either of these is true, then the move associated with this module is chosen. Otherwise, the next prioritization step is whether a trap for the AI exists, implemented in the third generation; if it exists and the subsequent player move would not result in a human player win (foundMax[trapMoveFlag] check), then the move that would lead to a trap is played. Otherwise, the default case is to go with the move that minimizes the human player’s maximum profit, established in the second generation.