This project was made with a demo purpose, I don’t plan to distribute it commercially. I was asked to design an AI for a game called Connect 4 at one of my interviews. I implemented the design with C# scripts in Unity engine for the demo purpose. My AI can handle any size of a square board, not exactly like one of the traditional Connect 4 boards(7×6, 8×7, 9×7, 10×7) and connect any specific number of discs or checkers as long as it’s smaller tha
n the number of columns per row( or the number of rows per column since it is a square board). However, for this demo, I set the board size to 7x7 and the number of discs or checkers to connect is 4. Like Connect 4, you can connect your discs vertically, horizontally, or diagonally. When you play, just click on anywhere in the column that you wish to put your discs in, the computer would place your disc to the currently available spot in that column for you. It is a 3D game, I made the 3D game board and discs models by myself. Appearance-wise, they may not look pretty but since this is a project to demonstrate my coding ability, I decided to focus more on coding and making the AI solid.The core algorithm of the AI is based on the MinMax method, where the depth first search is used to look ahead in the future and the AI will then make moves based on the best result possible. A full DFS on a 7x7 board is exceptionally costly as it takes a couple of hours to complete, so to improve the AI’s performance and response time, I implemented depth limit and branch pruning( a.k.a alpha beta pruning).
Branch pruning eliminates additional searches once it has determined the best/worst case result has been found, which saves some computations, however, I found depth limit is a more effective technique in reducing the search space. I have my AI look only 3 steps ahead( 6 recursive calls) for all the available moves and it works pretty well, increasing that value does not make the AI much smarter while the computational time increases dramatically.
Since this is a very simple board game, I found implementing the above technique is sufficient enough in providing a very challenging AI to the player. However, there are some additional techniques that can be utilized to make the AI respond quicker or even improve the gameplay. For example, heuristics for selecting a better move based on the current game board is another method to reduce the computations. But the AI can be handicapped by doing so, thus taking some time to balance between making the AI more “human-like” and yet challenging is necessary.
Note: I have done a few changes here and there since I published this article. Now it has "Two players mode", "Switching players", "Menu", "SFX" and it can have an asymmetric board. I haven't updated the link for downloading the latest version, trying to port it onto iPhone right now.
