Click here to Skip to main content
Click here to Skip to main content

Connect4 using MIN-MAX algorithm

, 15 May 2004
Rate this:
Please Sign up or sign in to vote.
MiniMax algorithm can be used in game AI.

Sample Image - Connect4.gif

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.

License

This article, along with any associated source code and files, is licensed under The Code Project Open License (CPOL)

Share

About the Author

Bishoy Labib
Team Leader Link Development
Egypt Egypt
IF YOU WANT TO IMPROVE YOUR SOFTWARE, DON'T TEST MORE; DEVELOP BETTER.
 
http://bishoylabib.blogspot.com

Comments and Discussions

 
QuestionIt works fine under vs2010 Pinmemberjmtree25-Sep-12 11:16 
QuestionHi PinmemberAlisalahi28-Jun-12 2:15 
GeneralMy vote of 1 PinmemberMR.Haghighat10-Aug-09 7:31 
GeneralNew code for connect4 PinmemberBishoy Labib11-Apr-09 12:31 
GeneralMiniMax for Tic Tac Toe PinmemberMario Campo18-Sep-08 23:07 
General[Message Deleted] PinmemberDanny Rodriguez27-Jan-08 9:16 
Generalcode comments PinmemberKaptainKruton15-Sep-05 22:11 
GeneralC++ code PinmemberKristjanK5-Sep-04 22:27 

General General    News News    Suggestion Suggestion    Question Question    Bug Bug    Answer Answer    Joke Joke    Rant Rant    Admin Admin   

Use Ctrl+Left/Right to switch messages, Ctrl+Up/Down to switch threads, Ctrl+Shift+Left/Right to switch pages.

| Advertise | Privacy | Mobile
Web01 | 2.8.140814.1 | Last Updated 16 May 2004
Article Copyright 2004 by Bishoy Labib
Everything else Copyright © CodeProject, 1999-2014
Terms of Service
Layout: fixed | fluid