Connect Four AI

The beginnings of this project were in high-school; for one of my computer science classes, we were given the task of creating a game of connect four that is playable by two players. This project consisted of placing the pieces in the correct spot and determining if there is a four-in-a-row. A few years later, I decided to create an engine out of the project. The goal of this engine was not to make it invincible, but rather make it play more human-like. This was done by using a simple heuristic approach; if I wished to make it invincible, then I would use a tree search method to search for all possible moves. This can easily be done since there are only around four trillion possible positions in connect four, meaning that the number of winning positions is relatively minute. Therefore, the game can easily be solved for any position, making it invincible to imperfect play. However, I wanted my engine to have an element of human-like play. This means that it plays logically based on what seems like a good move in general while also avoiding simple traps. Also, I wanted to add a machine learning element to the engine since I was interested in AI software and the idea of machines learning strategy on their own. As a separate project for another class, I made a short video explaining the engine. The video can be found here: https://www.youtube.com/watch?v=sNigJiClm7M&feature=youtu.be

Above is the UI of the engine; the engine works by giving the game board to 11 different algorithms to find a move based on priority. What that means is that the board is first analyzed by the winning move algorithm since if the next move is winning, it is the top priority. Likewise, the second priority is to block a win for your opponent; these algorithms are all based on the four-in-a-row pattern. Each algorithm internally places pieces to check for winning/losing patterns and places pieces in accordance with that information. An example game can be found below.

However, it should be noted that unlike the higher tier algorithms, the lowest three algorithms play to set up combinations and therefore do not lead to a definite win or prevent a definite loss. They exist to compliment the offensive and defensive algorithms, since there must be an element of the engine that creates plays by setting up good positions.

The beginning of the engine function can be found in the image above. The more interesting part of this project is the AI feature that is implemented within the separate decision algorithms.

The images above displays the code segment that stores the games played by the engine in an SQL server. Whether or not the engine wins, the game data will be serialized and uploaded to the database. Serialization is a technique of compressing data into binary large objects to save space in storage and increase efficiency in pulling the data. Two methods are used to increase the usability of the data, they are; invert the data so that a winning position for the engine can also be submitted to the database as a losing position. This makes it so that every win/loss will be recorded as both and therefore give more data for the AI to use. The other method is to store only the positional data from the sixth last to the second last move in the database. The reason for this is that if there was a losing position in which it would lose in one move, the block algorithm can take care of it; however if the game is unwinnable, then it is pointless to have the position stored either way. This way, if a position is reached in which the engine has previously had a win or a loss, there will be a database hit. The storage of the position data can be seen in the image below.

At the beginning of each run of the program, the positions are loaded and de-serialized from the database onto a global array in order to be used as can be seen in the code segment below.

Once the positions are obtained, the engine plays as it does until it reaches a position it has already reached before. The image below shows the functions called to check for wins/losses from the database.

These functions are only called within the move algorithms that are not absolute. This means they are only called in the three lowest move algorithms, since the others only find moves that are definitely the best in that position. If such a move is not found by one of the algorithms, the engine moves to set up such a play; this move can however be flawed. As I played against the engine, I was noticing that there was a simple pattern that it kept losing to. This was particularly interesting since it was not the absolute loss that it could not see, but the set up to it that was evading the engine. By saving this position in the database, the engine can use its previous game knowledge to realize that the move it is about to make leads to a loss, and can therefore force the engine to reconsider. With this addition to the project, the simple engine now becomes artificially intelligent.

The image above was taken from a video I made explaining the engine (Link at the top). This image shows the reconsideration of the move that gives a result not previously leading to a loss. The particular example is the one I discussed above, and after implementing this algorithm, the mistake was never made again.

This machine learning algorithm was successful, however I wanted to create a method for the database to be populated with a large amount of data. My solution to this was to allow the engine to play itself thousands of times and only use unique games that only end in a win/loss. This process was streamlined by using a technique known as thread pooling. Thread pooling is the creation of multiple instances of the same program that are run simultaneously. This is because programs are usually run on a single thread on the processor, however we can use thread pooling to access multiple. With this technique, I was able to play the same amount of games in a much reduced time. The code segment for this can be found below.

With this final feature, the AI is complete. The original engine was powerful enough to have a 70% win rate which rose to around 75% when the AI feature is added. All in all, it was a good learning experience in both technical concepts such as thread pooling or data serialization, but also a good application in logic.