Connect4 Using the Alpha-Beta Search Algorithm

• Download source files - 9.48 Kb
• Download demo project - 5.15 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 who 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 a 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

The code of the game AI may seem unreadable because it was done under C++ first. I'll try to explain the AI algorithm briefly, so you don't need to read the code.

The AlphaBeta search is based on the MiniMax algorithm. It works by a recursion function that checks the 7 possible plays that the computer can make. And tries to give a score for each play and decides which is the best place to play for the computer.

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 it has 2 pieces around it, 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 have 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 gives 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 puts his coin also. That would need to check for all the possibilities 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 positions 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.

Though the MiniMax algorithm may work good, it takes a lot of processing. We added a little variation to the algorithm and called it Alpha Beta Search. It relies on the idea that if you already have a choice you know is not bad, when you are looking at other choices, and you find one that you know is no better, you don't have to go to the trouble of figuring out exactly how bad it is. Anything that is no better than the best choice found is bad enough, so you toss it out without completely understanding it. You can throw it away the instant you prove that it is no better than the best choice.

The idea is that two scores are passed around in the search. The first one is alpha, which is the best score that can be forced by some means. Anything worth less than this is of no use, because there is a strategy that is known to result in a score of alpha. Anything less than or equal to alpha is no improvement.

The second score is beta. Beta is the worst-case scenario for the opponent. It's the worst thing that the opponent has to endure, because it's known that there is a way for the opponent to force a situation no worse than beta, from the opponent's point of view. If the search finds something that returns a score of beta or better, it's too good, so the side to move is not going to get a chance to use this strategy.

When searching moves, each move searched returns a score that has some relation to alpha and beta, and the relation is very important and might mean that the search can stop and return a value.

If a move results in a score that was less than or equal to alpha, it was just a bad move and it can be forgotten about, since, as I stated a few paragraphs ago, there is known to be a strategy that gets the moving side a position valued at alpha.

If a move results in a score that is greater than or equal to beta, this whole node is trash, since the opponent is not going to let the side to move to achieve this position, because there is some choice the opponent can make that will avoid it. So, if we find something with a score of beta or better, it has been proven that this whole node is not going to happen, so the rest of the legal moves do not have to be searched.

If a move results in a score that is greater than alpha, but less than beta, this is the move that the side to move is going to plan to play, unless something changes later on. So alpha is increased to reflect this new value.

The more you give the algorithm depth levels, the more it can predict the best play in the future. So, I made the easy level have 3 levels of recursion (checks for the computer turn, the player next and the computer next) and the normal have 5 levels, and the hard have 7 levels of recursion to make better estimates while having longer processing time. (It is not recommended to select hard level while on the Pocket PC Emulator).

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 a more 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.