Connect4 using MIN-MAX algorithm

• Download source files - 37 Kb
• Download demo project - 5 Kb

Introduction

This is the traditional Connect4 game that we all played, trying to build a row consisting of 4 pieces of the same color (horizontal, vertical or diagonal).

It will be very helpful for the programmers that need to learn general game AI to put in any turn based strategy game like Tic Tac Toe or even Chess.

I made this game on C++ two years ago. I converted all the code to C# to see how easy it is to convert C++ code to C#.

Implementation

The project contains the Form1 class which contains simple user interface and drawing functions. Function Form1.Draw takes the Graphics object of the form to draw the board based on the saved values for the pieces.

The Connect4Board class is the one that was converted from C++ and it contains all the AI code and the game rules and functions.

The Game AI

I am very sorry that the code of the game AI may seem unreadable because it was done under C++ first. So I'll try to explain the AI Algorithm breifly so you don't need to read the code.

The AI is based on the MiniMax algorithm. It works by a recursion function that checks the 7 possible plays that the computer can make. Inside each one of them it checks the 7 plays that the player may play after. Then inside each one of the player, it checks again for the next 7 plays for the computer and go on until a certain recursion level like (3 or 5) levels.

Then it position the board state and give it a score based on the opportunities for the computer and for the player. The score is returned per level to the upper level until reach the first level where there is a score for every computer possible play. If we are on a computer recursion level, the best score is returned to the previous level. If we are in a player level then the worse score is returned because the player would make the better move for him against the computer.

For those who got confused I'll try to say it with another words.

First we need a function that calculates a score for the board position based on opportunities for both the computer and the player. This function is called 'int position()' in the code.

An opportunity is an empty place (a hole) that has around it, a row of 3 pieces of the same color (horizontal, vertical or diagonal). If around it 2 pieces, then it takes less score. The board position score is the sum of all the scores of the computer - the scores of the player.

Then we need to figure out when to check for the position of the board. A possible way is to check after every computer move and that will be 7 possible moves for the computer in Connect4. So we add a move for the board. Calculates the score of the board. Then remove this piece. Then we add another move until all the moves has been given a score. So the computer will decide to play the best move based on the maximum score.

This approach will work fine if the function that calculates the score, is very complex code that give a score for every next turn. But we will not be able to make this function. So the better approach is to calculate the score after the player put his coin also. That would need to check for all the possiblilties for the computer and player will play. That means for every one of the 7 plays for the computer we can have 7 plays for the player. That would be 49 position to check for score. Then we return the worst position on every 7 plays of the player. Then we take the best position on every 7 plays of the computer.

The more you give the algorithm more recursion levels, the more it can predict the best play in the future. So I made the easy level has 3 levels of recursion (Checks for the computer turn, the player next and the computer next) and the hard level has 5 levels of recursion to make better estimates while having longer processing time.

This algorithm can be used for any turn based strategy game like Chess or something. But the more complex the game is. You will need to make complex score function. And have more recursion levels. And the most important is to remove some of the bad plays on every level to reduce the processing cost. Because you don't have to see all the future for a turn that will make you lose a lot of score.

I hope you enjoy the game and the algorithm.