Monday, February 13, 2012

How to Develop a Chess Program for Dummies 3

Introduction

This lesson will describe the Artificial Intelligence algorithm that one has to implement in order to have the chess program play chess.

How to read this lesson

In order to understand what is mentioned in this lesson, you must have downloaded the latest version of Huo Chess (currently v0.93). You should have the MS Visual Studio open with Huo Chess, while you read so that you can understand the article. Please contact me for any issues or questions at skakos@hotmail.com.
Places to download Huo Chess (source code and executable):

The article that follows can also be found in the Codeproject site of Huo Chess.

I. Chess Algorithm Analysis

The algorithm used in this program for the implementation of the computer thinking is the MiniMax algorithm for the latest version (C# 0.93) and the "Brute Force Algorithm" for the older C++ / VB / C# version. Huo Chess plays with the material in mind, while its code has some hints of positional strategic playing embedded (e.g. it is good to have your Knights closer to the center of the chessboard in the beginning). More analytically: When the program starts thinking, it scans the chessboard to find where its pieces are (see ComputerMove function) and then tries all possible moves it can make. It analyzes these moves up to the thinking depth I have defined (via the ComputerMove => ComputerMove2 => ComputerMove3 => ComputerMove4 => ComputerMove5 path), measures the score (see CountScore function) of the final position reached from all possible move variants and – finally – chooses the move that leads to the most promising (from a score point of view) position (ComputerMove function).

C# v0.93 Kakos-Minimax algorithm summary


A high-level example of the progress of the main algorithm for versions 0.84 and older is as follows:
  1. ComputerMove: Scans the chessboard and makes all possible moves
  2. CheckMove: Checks the legality and correctness of these possible moves
  3. (if thinking depth not reached) => call HumanMove
  4. HumanMove: Checks and finds the best answer of the human opponent
  5. ComputerMove2: Scans the chessboard and makes all possible moves at the next thinking level
  6. CheckMove: Checks the legality and correctness of these possible moves
  7. (if thinking depth not reached) => call HumanMove
  8. HumanMove: Checks and finds all possible answers of the human opponent (Note: Previous (v0.84 and older) versions found only the best answer of the human opponent (by finding with which move the human earns more)
  9. ComputerMove4 /ComputerMove6 / ... ComputerMove20: Scans the chessboard and makes all possible moves at the next thinking level
  10. CheckMove: Checks the legality and correctness of these possible moves
  11. (if thinking depth reached) => record the score of the final position in the Nodes of the MiniMax algorithm
  12. The algorithm continues until all possible moves are scanned
  13. The MiniMax algorithm is finally used to calculate the best move via the analysis of the thinking tree Nodes
You can SET huo_debug to TRUE to see live the progress of the computer thought while the computer thinks. Just press a key to move step-by-step into the Huo Chess inner mechanism… You can also uncomment the code lines that record the time the program requires to think its move, so as to have an idea of the time required by the processor to complete the thinking process.



II. Huo Chess Thought Flow (v0.93 Simple-Minimax algorithm)

Below, I analyze the thought flow of the chess program. I will describe only the main steps and code segments, so as to show the way the computer scans the chessboard, conducts all possible moves and finally finds the better one. The function names appear in bold, i.e. ComputerMove - Start indicates the beginning of the ComputerMove() function. Be aware that some code segments may be slightly different from the code in the distributed ZIP file since I continuously change the program. As it appears, the "constant beta" state is the trend nowadays. ComputerMove – Start When the computer thinking starts, the first thing to do is to initialize all the variables and store the initial chessboard position in an array.

// store the initial position in the chessboard 
for (int iii1 = 0; iii1 <= 7; iii1++)
{
    for (int jjj1 = 0; jjj1 <= 7; jjj1++)
    {
        Skakiera_Thinking_init[(iii1), (jjj1)] = Skakiera_Thinking[iii1, jjj1];
    }
}

Call: CheckMove

ComputerMove – Dangerous Squares filter

The program then scans the chessboard and analyzes it in order to find the Dangerous Squares. These squares are the squares where the computer cannot move its pieces to, since they are protected by pieces of the other side. These Dangerous Squares analysis is conducted for every level of thinking and serves as a “filter”, so as to reduce the number of moves analyzed (this helps to the program speed) and make sure both sides do not “make” stupid moves.
DangerousSquares(Skakiera_Thinking, "ComputerMove0", m_PlayerColor);

ComputerMove – Main Thinking
  • Scan the chessboard ® find any possible move (MoveFilter makes a pre-scanning of valid moves so as to increase the thinking speed).
  • Make the move temporarily
(Versions 0.82 and earlier called CheckHumanMove to find the move of the human which wins more material – However newer versions analyze all possible moves of the human with MiniMax algorithm)
  • Call ComputerMove2 [Chessboard with the move analyzed applied, is passed over as an argument]
ComputerMove_2(Skakiera_Thinking);

CheckHumanMove2 / CheckHumanMove 3 / CheckHumanMove 4...

Deeper thinking is implemented by respective thinking functions. Each one has as input the chessboard array from the previous one.

 CountScore

Every move score is measured (if the move is legal and correct). These scores are stored in the NodesAnalysis array (see below). The scoring function is the heart of the program. It currently takes into account mainly material values, with some positional considerations for the opening phase of the game (i.e. if Move < 11 it is not good to move your Queen or else a small “scoring penalty” is imposed). The optimization of that function is key to the increasing of the computer play strength.

 Thinking Depth - End

When we have reached the thinking depth (i.e. when we have reached the ComputerMove function which we have defined as the last one in the chain of analysis), we store the chessboard scores of the thinking tree nodes for every thinking depth level (applies for version 0.93 and newer). These nodes are then going to be used in the MiniMax algorithm to find the best move.

// Record the node in the Nodes Analysis array (to use with MiniMax algorithm)
NodesAnalysis[NodeLevel_1_count, 1, 0] = Temp_Score_Human_before_2;
NodesAnalysis[NodeLevel_2_count, 2, 0] = Temp_Score_Human_after_2;
NodesAnalysis[NodeLevel_3_count, 3, 0] = Temp_Score_Human_before_4;
NodesAnalysis[NodeLevel_4_count, 4, 0] = Temp_Score_Human_after_4;
NodesAnalysis[NodeLevel_5_count, 5, 0] = Temp_Score_Human_before_6;
NodesAnalysis[NodeLevel_6_count, 6, 0] = Temp_Score_Human_after_6;
For every node, we also store the number of the parent node:
// Store the parents (number of the node of the upper level)
NodesAnalysis[NodeLevel_1_count, 1, 1] = 0;
NodesAnalysis[NodeLevel_2_count, 2, 1] = NodeLevel_1_count;
NodesAnalysis[NodeLevel_3_count, 3, 1] = NodeLevel_2_count;
NodesAnalysis[NodeLevel_4_count, 4, 1] = NodeLevel_3_count;
NodesAnalysis[NodeLevel_5_count, 5, 1] = NodeLevel_4_count;

MiniMax algorithm

This is required for the MiniMax algorithm implementation (see http://en.wikipedia.org/wiki/Minimax on how this algorithm works): We start from the lower level nodes and go up to the beginning of the tree, like in the schema that follows:

 

Suppose the game being played only has a maximum of two possible moves per player each turn. The algorithm generates the tree shown in the figure above, where the circles represent the moves of the computer AI running the algorithm (maximizing player), and squares represent the moves of the human opponent (minimizing player). For the example’s needs, the tree is limited to a look-ahead of 4 moves. The algorithm evaluates each leaf node using the CountScore evaluation functions, obtaining the values shown. The moves where the maximizing player wins are assigned with positive infinity, while the moves that lead to a win of the minimizing player are assigned with negative infinity (this is again for illustration purposes only – infinity will not happen in the game as it is currently developed). At level 3, the algorithm will choose, for each node, the smallest of the child node values, and assign it to that same node (e.g. the node on the left will choose the minimum between "10" and "+8", therefore assigning the value "10" to itself). The next step, in level 2, consists of choosing for each node the largest of the child node values. Once again, the values are assigned to each parent node. The algorithm continues evaluating the maximum and minimum values of the child nodes alternately until it reaches the root node, where it chooses the move with the largest value (represented in the figure with a blue arrow). This is the move that the player should make in order to minimize the maximum possible loss. In order for the program to calculate the best move, a number of “for loops” are applied so as to make the abovementioned backwards computation possible.

for (counter7 = 1; counter7 <= NodeLevel_7_count; counter7++)
{ for (counter8 = 1; counter8 <= NodeLevel_8_count; counter8++)
{ if (NodesAnalysis[counter8, 8, 1] == counter7)
{ if (counter8 == 1)
                        NodesAnalysis[counter7, 7, 0] = NodesAnalysis[counter8, 8, 0];
                    if (counter8 > 1)
                        if (NodesAnalysis[counter8, 8, 0] < NodesAnalysis[counter7, 7, 0]) NodesAnalysis[counter7, 7, 0] = NodesAnalysis[counter8, 8, 0];
 }
}
}

After the algorithm has reached the root node, the move with the best score is selected. ComputerMove[Maximum thinking depth] – End

 III. Huo Chess Thought Flow (v0.93 Kakos-Minimax)

In this section, I analyze the thinking algorithm for version 0.93 (Kakos-Minimax edition) or for versions 0.84 and older. Below, I illustrate the step-by-step process of the computer's thought for a thinking depth of 2. Let's see the "step" boxes to understand the way the program is structured. Scenario Details
  • Computer Level: Maitre (ThinkingDepth = 2)
ComputerMove - Start

 Step 1

 START

 Move_Analyzed = 0

1. If the first time called -> store initial chessboard position.
2. if( Move_Analyzed >Thinking_Depth )
3. Stop_Analyzing = true;
4. if( Stop_Analyzing = false)
5. Scan chessboard. for iii, jjj
6. Scan chessboard, find a piece of the HY , conduct move, check correctness and legality of move, and if all is OK, then call CheckMove to measure the score of the move.

Call: CheckMove CheckMove - Start
  1. Number of moves analyzed ++.
  2. Check correctness and legality of move.
  3. Check if there is a mate on the chessboard.
  4. If the move is correct and legal, then do it.
  5. Check if there is a pawn to be promoted.
  6. Store move to ***_HY variables because, after many calls of ComputerMove and CheckMove functions, the initial values of the move analyzed will be lost.
  7. If this is the first move analyzed, then record it as the correct "best" move, no matter how bad it is.
Step 2

IF result: FALSE Move_Analyzed = 0
  1. if(Move_Analyzed = Thinking_Depth)
  2. Measure the score of the move and record it as "best" move if it is larger than the score of the so-far best move score.
Step 3

IF result: TRUE Move_Analyzed = 1
  1. if (Move_Analyzed < Thinking_Depth)
HumanMove - Start [HumanMove_Template for v0.93]

 Step 4

Find the best answer of the Human (Move_Analyzed = 1). Version 0.93: Find ALL possible human moves
  • Scan the chessboard -> find any possible move.
  • Call CheckHumanMove. [redundant in v0.93]
Store the chessboard score before and after the human move.

 CheckHumanMove - Start

voidCheckHumanMove(array<String^, 2>^ CMSkakiera_Human_Thinking)
Count the score of the move and record it as "best" if its score is better than the so-far best move.

In v0.93 and newer: Record the score before and after the human opponents makes his move. Those scores are recorded in the Nodes Analysis array and will be used for the MiniMax algorithm at the end (to evaluate the best move).

 CheckHumanMove - End

Conduct the best move of the human [conduct all possible human moves in v0.93].

Move_Analyzed = Move_Analyzed + 1; Who_Is_Analyzed = "HY";
for(i = 0; i <= 7;i++)
{
    for(j = 0; j <= 7; j++)
    {
        Skakiera_Move_After[(i),(j)]=Skakiera_Human_Thinking[(i),(j)];
    }
}

Step 5

Move_Analyzed = 2

Step 6

CALL next ComputerMove function for next-level move analysis.

Move_Analyzed = 2 if(Move_Analyzed == 2)
this->ComputerMove2(Skakiera_Move_After);
else if(Move_Analyzed == 4)
this->ComputerMove4(Skakiera_Move_After);
else if(Move_Analyzed == 6)
this->ComputerMove6(Skakiera_Move_After);
else if( Move_Analyzed == 8 )
this->ComputerMove8(Skakiera_Move_After);
// Call ComputerMove2 to find the best next move of the HY (deeper thinking)

Step 7

Scan the chessboard and find the best move for the computer.

Move_Analyzed = 2 voidComputerMove2(array<STRING^, />^ Skakiera_Thinking_2)
{
// Same as…ComputerMove if(Move_Analyzed has not reached thinking depth) {
// Same as…ComputerMove: Call CheckMove -> HumanMove -> next ComputerMove etc
// (If we haven't reached the desired level of analysis, then the HumanMove
// will be called again, then again the ComputerMove function etc.)
}

Step 8

Return to a previous ComputerMove (i.e. ComputerMove4 calls ComputerMove2) function to continue the analysis. Move_Analyzed = 2 (at the end of the analysis this variable will be equal to 0, see Step 9).

// Return to the ComputerMove function of the 'previous' thinking
// level to continue the analysis
Move_Analyzed = Move_Analyzed - 2;
Who_Is_Analyzed = "HY";
for(i = 0; i <= 7; i++)
{
    for(j = 0; j <= 7; j++)
    {
        Skakiera_Thinking[i,j] = Skakiera_Move_0[i,j];
    }
}
ComputerMove2 - End HumanMove - End CheckMove - End
// close for iii, jjj loop// close if( Stop_Analyzing = false ) segment

If no legal move is found -> we have MATE!

 Step 9

Version 0.93: Apply the MiniMax algorithm to reach to the best move. Play the move with the highest score. Now it is the Human's turn to play.

if (move_analyzed==0){
  1. Check if it is good to conduct castling.
  2. "Redraw" the chessboard with the best move found.
  3. Move the rook next to the king, if castling occurred.
  4. Check if a pawn is promoted (at the current version computer always promotes a pawn to queen).
  5. Now it is the turn of the other player (human) to play!
}
else
{
    Move_Analyzed = Move_Analyzed - 2;
    Who_Is_Analyzed = "HY";
    for(i = 0; i <= 7; i++)
    {
        for(j = 0; j <= 7;j++)
        {
            Skakiera_Thinking[i,j] = Skakiera_Move_0[i,j];
        }
    }
}
ComputerMove – End

 Other resources

One can find the same article published in Codeproject at http://www.codeproject.com/KB/game/cpp_microchess.aspx. Next Lessons In the next lesson, I will analyze a little bit more the MiniMax algorithm.

► Tags: , , ,
Related Posts Plugin for WordPress, Blogger...