The Alpha-Beta algorithmus

Now we come to the most difficult part of our programming course: The Alpha-Beta algorithmus. The goal of the Alpha-Beta algorithmus is to reduce the calculation outlay during the move seach. This reduction enables our programm to calculate for 4 halfmoves in a good time.

The Alpha-Beta algorithmus is based on the Minimax algorithmus. It forecloses nodes that have no chance to be choosen. Let's imagein the following scenatio: The computer calculates the value for a node in deep 4. He get a negative value for the node, that means that the computer has the better position. Then, in deep 3, a new move for the computer will be analyzed and all possible moves for the human that results are generated. The human is going to take the move with the highest value. But if one move give a value that is better as the value of the previous node that we calculated for the computer, the computer can abort the evaluation of the human moves for that node. The computer is not going to take the node we're calculating the human moves for, because he will the deepest value and the value of this node will be over them of the last node.

Because it should be clear now what the Alpha-Beta algorithmus does, we start to implement it.

We have to define two variables in the global namespace of the class board:

float alphabeta [] = new float [10]; //Alpha Beta values
boolean ababort = false; //AlphaBeta abort

The Alpha - Beta values have to be initialized, so the following code has to be put before the newgame () call in the constructor:

//initialize AlphaBeta
alphabeta [0] = -3000.0f;

The method genmove () has to initialize the array for the current deep, too:

deep++;
ababort = false;

//find checkmate & AlphaBeta initialization
if (deep % 2 != 0) { //move of the computer
   minimax [deep] = 2000.0f;
   alphabeta [deep] = 3000.0f;
} else { //move of the human
   minimax [deep] = -2000.0f;
   alphabeta [deep] = -3000.0f;
}

We also have to add code on bottom of the method genmove ():

ababort = false;

Most changes are in the method simulize ():

if (ababort)
   return;

//simulize move
int orgstart = board [start];
int orgend = board [end];

board [end] = board [start];
board [start] = 0;

if (! ischeck ()) {
   if (deep == 1) {
      movelist [movecounter] = start * 100 + end;
      movecounter++;
   }

   //calculate value of node
   if (target == deep)
      value = evaluation ();
   else {
      if (color == 1)
         color = 2;
      else
         color = 1;

      genmove ();
      value = minimax [deep + 1];

      //changes on the Alphabeta field?
      if (deep % 2 != 0) { //Computer
         if (value < alphabeta [deep])
            alphabeta [deep] = value;
      } else { //Human
         if (value > alphabeta [deep])
            alphabeta [deep] = value;
      }

      if (color == 1)
         color = 2;
      else
         color = 1;
   }

   //Minimax Algorithmus
   if (deep % 2 == 0) { //human layer
      if (value > minimax [deep] )
         minimax [deep] = value;
      //Alphabeta
      if (value > alphabeta [deep - 1])
         ababort = true;
   } else { //Computer layer
      if (value <= minimax [deep] ) {
         minimax [deep] = value;
         if (deep == 1)
            move = start * 100 + end;
      }
      //Alphabeta
      if (value < alphabeta [deep - 1])
         ababort = true;
   }
}

The rest of the method doesn't change. Now we can put the calculatoin deep in the method run () to 4 halfmoves:

target = 4;

Now the AlphaBeta Algorithmus works. The chess programm is playing already well. Now we wan't to tell you some tips that may help you to make the AI play better. The implementation of these methods are to much for this programming course. Most of the tips are implemented in the Chess Partner Applet of this site. Because the applet is published under the terms of the GNU Public License, you can find help in the souce code of the applets. Out tips are:

• Implement an opening library. You can download and use the opening library that we wrote for our Chess Partner Applet..
• Optimize the code:
  • Seperate the board array in three arrays, one for special information, one for color and one for the typ of the pieces.
  • Save the position of the kings, so you haven't to look for the kings in the method ischeck ().
• You can make the positional play of the programm better if you implement valuearrays for each piece type.

show applet step 9
source code of step 9

---

to the overview | back | continue