Choose a mve

In this paragraph, we have to do a lot of work. At the end of this paragraph, our programm will makes the moves for black. We implement the choose of a move with the Minimax algorithmus. This algorithmus says that every side moves in such a way that his advantage is masximized and the advantage of his enemy minimized. That means concret that, if a node is in a deep in which the computer moves, the node takes the value of the worst sub-node. If it is a deep in which the human moves, the node takes the value of the highest sub-node. Negative values for a position means that the position is better for the computer, because the evaluation is in the sight of the human.

First of all we have to add several new variables. Because they're global variables we declare them in the global namespace of the class Board:

Thread th = null; //AI Thread
int deep = 0; //actiaö deeü
int target = 4; //target deep
float value = 0; //value cache for minimax
float minimax [] = new float [10]; //Minimax Algorithmus
int move; //The move of the AI

Next we have to change the genmove () method. We add the following code at the begining:

deep++;

//checkmate
if (deep % 2 != 0) //move of the computer
   minimax [deep] = 2000.0f;
else // move of the human
   minimax [deep] = -2000.0f;

When the position is checkmate, we can not generate further moves and the value in the minimax field will not be changed. At the end of the method we have to add the following line:

deep--;

We don't want that the user interface lags while we calcuate the best move, so we have a own thread for the calcuation. The thread will be definied in the method run ().

//no access to the move list
code = 1;

deep = 0;
target = 2;

//look for best move
movecounter = 0;
genmove ();

if (movecounter == 0) //no moves -> end of game
{
   if (ischeck ())
      parent.getAppletContext ().showStatus ("White wins!");
   else
      parent.getAppletContext ().showStatus ("Game is a draw");
   return;
}

//execute found move
execute ( move / 100, move % 100 );

//enable access to the movelist
code = 0;

The method simulize () has to be changed so that it calls the method genmove () until the target deep is reached. We also implement the Minimax algorithmus:.

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];

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

   //Minimax Algorithmus
   if (deep % 2 == 0) {
      if (value > minimax [deep])
         minimax [deep] = value;
   } else {
      if (value < minimax [deep]) {
         minimax [deep] = value;

         if (deep == 1)
            move = start * 100 + end;
      }
   }
}

The rest of the method do not change. We have to change the method execute () so that it makes the AI calculating the best move:

//change player
if (color == 1) {
   color = 2;

   //look for best move
   th = new Thread (this);
   th.start ();
} else {
   color = 1;

   //calculate valid moves
   movecounter = 0;
   deep = 0;
   target = 1;
   genmove ();

   if (movecounter == 0) //no valid moves -> end of game
   {
      if (ischeck ())
         parent.getAppletContext ().showStatus ("Black wins!");
      else
         parent.getAppletContext ().showStatus ("Game is a draw!");
   }
}

Also the method newgame () has to be changed:

movecounter = 0;
color = 1;
deep = 0;
target = 1;
genmove ();
code = 0;

Now our programm plays chess. but it is really slow and calculates only for two halfmoves. In the next part, we will implement the AlphaBeta algorithmus. Then the programm will be much quicker and it can calucate for 4 halfmoves.

show applet step 8
source code step 8

---

to the overview | back | continue