Other related articles

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. 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)

• Huo Chess @ Codeplex
• Huo Chess @ Codeproject (includes analysis of the code)
• Huo Chess @ MSDN Code Gallery

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. 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 defined (via the ComputerMove => HumanMove1 => ComputerMove2 => HumanMove3 => ComputerMove4 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# 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. Checks for dangerous squares. Makes all possible moves. (excluding moves which are “stupid” based on spefici criteria)
2. CheckMove: Stores the initial values of the move and makes some additional checks (e.g. for check)
3. If thinking depth not reached => call Analyze_Move_1_HumanMove
4. Analyze_Move_1_HumanMove: Checks all possible answers of the human opponent
5. If thinking depth not reached => call Analyze_Move_2_ComputerMove
6. Analyze_Move_2_ComputerMove: Scans the chessboard and makes all possible moves for the computer at the next thinking level
7. If thinking depth reached => record the score of the final position in the Nodes of the MiniMax algorithm
8. The algorithm continues until all possible moves are scanned
9. The MiniMax algorithm is finally used to calculate the best move via the analysis of the thinking tree Nodes

II. Huo Chess Thought Flow analysis

Below, I analyze briefly 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 best one. For any additional detail one can refer to the source code itself, which is heavily commented in order to facilitate the understanding of the AI engine.

If human plays first => EnterMove

(else ComputerMove is called directly from Main_Console())

For the move entered by the human opponent…

• Check legality of the move
• Check for mate
• Check if there is check active
• Store move’s coordinates
• Store the value of the piece human moves
• Store the coordinates of where that piece moved [Human_last_move_target_rank/column]

ComputerMove [Move_Analyzed = 0]

#region InitializeNodes       //Initialize all nodes

#region StoreInitialPosition  //Store initial position

#region OpeningBookCheck      //OPENING BOOK CHECK

#region DangerousSquares      //CHECK FOR DANGEROUS SQUARES

// Initialize variables

For each possible move

{

// Check if the move is stupid

#region CheckStupidMove

If Move < 5 and you move the knight to the edges => Stupid move etc…

+ Store moving piece’s value

#endregion CheckStupidMove

If not stupid & Destination square not dangerous => …

if ((ThisIsStupidMove.CompareTo("N") == 0) && (Skakiera_Dangerous_Squares[(m_FinishingColumnNumber - 1), (m_FinishingRank - 1)] == 0))...

Call CheckMove

CheckMove(Skakiera_Thinking, m_StartingRank, m_StartingColumnNumber, m_FinishingRank, m_FinishingColumnNumber, MovingPiece);

<Call CheckMove(Skakiera_Thinking)> to:

• Check legality (Gr. Nomimotita) and validity (Gr. Orthotita) of the move
• Check for mate (This is not done! Must add it!)
• Check if there is check active

// If move analyzed in the first: Store move to ***_HY variables (so as to keep the initial move somewhere)

if (((m_OrthotitaKinisis == true) && (m_NomimotitaKinisis == true)) && (Move_Analyzed == 0)) => ...

Go back to ComputerMove

If the move is valid…

if ((m_OrthotitaKinisis == true) && (m_NomimotitaKinisis == true))

// Do the move

ProsorinoKommati = Skakiera_Thinking[(m_FinishingColumnNumber - 1), (m_FinishingRank - 1)];

Skakiera_Thinking[(m_StartingColumnNumber - 1), (m_StartingRank - 1)] = "";

Skakiera_Thinking[(m_FinishingColumnNumber - 1), (m_FinishingRank - 1)] = MovingPiece;

Check the score after the computer move

if (Move_Analyzed == 0) then...

    NodeLevel_0_count++;

    Temp_Score_Move_0 = CountScore(Skakiera_Thinking, humanDangerParameter);

if (Move_Analyzed == 2) then...

    NodeLevel_2_count++;

    Temp_Score_Move_2 = CountScore(Skakiera_Thinking, humanDangerParameter);

// Store the best move score at this level

if ((m_PlayerColor.CompareTo("Black") == 0) && (Temp_Score_Move_0 > bestScoreLevel0))

{

              bestScoreLevel0 = Temp_Score_Move_0;

}

// Check if you can eat back the piece of the human which moved!

if ((m_FinishingColumnNumber == Human_last_move_target_column)

     && (m_FinishingRank == Human_last_move_target_row)

     && (ValueOfMovingPiece <= ValueOfHumanMovingPiece))

{

    Best_Move_StartingColumnNumber = m_StartingColumnNumber;

    Best_Move_StartingRank = m_StartingRank;

    Best_Move_FinishingColumnNumber = m_FinishingColumnNumber;

    Best_Move_FinishingRank = m_FinishingRank;

    possibility_to_eat_back = true;

}

Check possibility to eat

If there is a possibility to eat a piece of the opponent, then there is no need to analyze any further...

If thinking depth not reached, call next level of analysis

if ((Move_Analyzed < Thinking_Depth) && (possibility_to_eat_back == false) && (possibility_to_eat == false))

{

    Move_Analyzed = Move_Analyzed + 1;

    for (i = 0; i <= 7; i++)

    {

        for (j = 0; j <= 7; j++)

        {

            Skakiera_Move_After[(i), (j)] = Skakiera_Thinking[(i), (j)];

        }

    }

    Who_Is_Analyzed = "Human";

     Analyze_Move_1_HumanMove(Skakiera_Move_After);

}

// Undo the move

Skakiera_Thinking[(m_StartingColumnNumber0 - 1), (m_StartingRank0 - 1)] = MovingPiece0;

Skakiera_Thinking[(m_FinishingColumnNumber0 - 1), (m_FinishingRank0 - 1)] = ProsorinoKommati0;

}

…

}

Analyze_Move_1_HumanMove [Move_Analyzed = 1]

Analyze all possible moves

{

// If the move is valid and legal…

if ((m_OrthotitaKinisis == true) && (m_NomimotitaKinisis == true)) then...

// Do the move

ProsorinoKommati = Skakiera_Human_Thinking_2[(m_FinishingColumnNumber - 1), (m_FinishingRank - 1)];

Skakiera_Human_Thinking_2[(m_StartingColumnNumber - 1), (m_StartingRank - 1)] = "";

Skakiera_Human_Thinking_2[(m_FinishingColumnNumber - 1), (m_FinishingRank - 1)] = MovingPiece;

// Measure score AFTER the move

NodeLevel_1_count++;

Temp_Score_Move_1_human = CountScore(Skakiera_Human_Thinking_2, humanDangerParameter);

// Store the best move at this level

if ((m_PlayerColor.CompareTo("Black") == 0) && (Temp_Score_Move_1_human < bestScoreLevel1))

{

    bestScoreLevel1 = Temp_Score_Move_1_human;

}

If thinking depth not reached, call next level of analysis

if (Move_Analyzed < Thinking_Depth) && (Temp_Score_Move_1_human better than bestScoreLevel1)

{

    Move_Analyzed = Move_Analyzed + 1;

    Who_Is_Analyzed = "HY";

    if (Move_Analyzed == 2)

        Analyze_Move_2_ComputerMove(Skakiera_Move_After);

    else if (Move_Analyzed == 4)

        Analyze_Move_4_ComputerMove(Skakiera_Move_After);

    else if (Move_Analyzed == 6)

        Analyze_Move_6_ComputerMove(Skakiera_Move_After);

}

// Undo the move

Skakiera_Human_Thinking_2[(m_StartingColumnNumber1 - 1), (m_StartingRank1 - 1)] = MovingPiece1;

Skakiera_Human_Thinking_2[(m_FinishingColumnNumber1 - 1), (m_FinishingRank1 - 1)] = ProsorinoKommati1;

}

// Return to previous depth of analysis

Move_Analyzed = Move_Analyzed - 1;

Who_Is_Analyzed = "HY";

Analyze_Move_2_ComputerMove [Move_Analyzed = 2]

Check all possible moves

{

// If the move is valid and legal…

if ((m_OrthotitaKinisis == true) && (m_NomimotitaKinisis == true))

{

// Do the move

ProsorinoKommati = Skakiera_Thinking_HY_2[(m_FinishingColumnNumber - 1), (m_FinishingRank - 1)];

Skakiera_Thinking_HY_2[(m_StartingColumnNumber - 1), (m_StartingRank - 1)] = "";

Skakiera_Thinking_HY_2[(m_FinishingColumnNumber - 1), (m_FinishingRank - 1)] = MovingPiece;

// Check the score after the computer move.

NodeLevel_2_count++;

Temp_Score_Move_2 = CountScore(Skakiera_Thinking_HY_2, humanDangerParameter);

// Store the best score at this level

if ((m_PlayerColor.CompareTo("Black") == 0) && (Temp_Score_Move_2 > bestScoreLevel2))

{

              bestScoreLevel2 = Temp_Score_Move_2;

}

If thinking depth not reached, call next level of analysis…

if (Move_Analyzed < Thinking_Depth)

{

    Move_Analyzed = Move_Analyzed + 1;

    Who_Is_Analyzed = "Human";

    // Check human move

    if (Move_Analyzed == 1)

        Analyze_Move_1_HumanMove(Skakiera_Move_After);

    else if (Move_Analyzed == 3)

        Analyze_Move_3_HumanMove(Skakiera_Move_After);

    else if (Move_Analyzed == 5)

        Analyze_Move_5_HumanMove(Skakiera_Move_After);

}

// If you have reached the defined depth of analysis…

if (Move_Analyzed == Thinking_Depth)   

{

// [MiniMax algorithm - skakos]

// Record the node in the Nodes Analysis array (to use with MiniMax algorithm) skakos

NodesAnalysis0[NodeLevel_0_count, 0] = Temp_Score_Move_0;

NodesAnalysis1[NodeLevel_1_count, 0] = Temp_Score_Move_1_human;

NodesAnalysis2[NodeLevel_2_count, 0] = Temp_Score_Move_2;

NodesAnalysis3[NodeLevel_3_count, 0] = Temp_Score_Move_3_human;

// Store the parents (number of the node of the upper level)

NodesAnalysis0[NodeLevel_0_count, 1] = 0;

NodesAnalysis1[NodeLevel_1_count, 1] = NodeLevel_0_count;

NodesAnalysis2[NodeLevel_2_count, 1] = NodeLevel_1_count;

NodesAnalysis3[NodeLevel_3_count, 1] = NodeLevel_2_count;

}

Note: Because the analysis ends only in ComputerMove functions, the ThinkigDepth must be an even number!

// Undo the move

Skakiera_Thinking_HY_2[(m_StartingColumnNumber2 - 1), (m_StartingRank2 - 1)] = MovingPiece2;

Skakiera_Thinking_HY_2[(m_FinishingColumnNumber2 - 1), (m_FinishingRank2 - 1)] = ProsorinoKommati2;

}

Move_Analyzed = Move_Analyzed - 1;

Who_Is_Analyzed = "Human";

ComputerMove [Continued… – The End of Analysis]

Check for mate

// Find the Best Move: Use MiniMax algorithm (only if possibility to eat a piece of the opponent is false)

if (possibility_to_eat_back == false)

{

    // [MiniMax algorithm - skakos]

    // Find node 1 move with the best score via the MiniMax algorithm.

    int counter0, counter1, counter2;

    // ------------------------------------------------------

    // NodesAnalysis

    // ------------------------------------------------------

    // Nodes structure...

    // [ccc, xxx, 0]: Score of node No. ccc at level xxx

    // [ccc, xxx, 1]: Parent of node No. ccc at level xxx-1

    // ------------------------------------------------------

    int parentNodeAnalyzed = -999;

    //v0.980: Remove

    //parentNodeAnalyzed = -999;

    for (counter2 = 1; counter2 <= NodeLevel_2_count; counter2++)

    {

        if (Int32.Parse(NodesAnalysis2[counter2, 1].ToString()) != parentNodeAnalyzed)

        {

            //parentNodeAnalyzedchanged = true;

            parentNodeAnalyzed = Int32.Parse(NodesAnalysis2[counter2, 1].ToString());

            NodesAnalysis1[Int32.Parse(NodesAnalysis2[counter2, 1].ToString()), 0] = NodesAnalysis2[counter2, 0];

        }

        if (NodesAnalysis2[counter2, 0] >= NodesAnalysis1[Int32.Parse(NodesAnalysis2[counter2, 1].ToString()), 0])

            NodesAnalysis1[Int32.Parse(NodesAnalysis2[counter2, 1].ToString()), 0] = NodesAnalysis2[counter2, 0];

    }

    // Now the Node1 level is filled with the score data

    parentNodeAnalyzed = -999;

    for (counter1 = 1; counter1 <= NodeLevel_1_count; counter1++)

    {

        if (Int32.Parse(NodesAnalysis1[counter1, 1].ToString()) != parentNodeAnalyzed)

        {

            //parentNodeAnalyzedchanged = true;

            parentNodeAnalyzed = Int32.Parse(NodesAnalysis1[counter1, 1].ToString());

            NodesAnalysis0[Int32.Parse(NodesAnalysis1[counter1, 1].ToString()), 0] = NodesAnalysis1[counter1, 0];

        }

        if (NodesAnalysis1[counter1, 0] <= NodesAnalysis0[Int32.Parse(NodesAnalysis1[counter1, 1].ToString()), 0])

            NodesAnalysis0[Int32.Parse(NodesAnalysis1[counter1, 1].ToString()), 0] = NodesAnalysis1[counter1, 0];

    }

    // Choose the biggest score at the Node0 level

    // Check example at http://en.wikipedia.org/wiki/Minimax#Example_2

    // Initialize the score with the first score and move found

    double temp_score = NodesAnalysis0[1, 0];

    Best_Move_StartingColumnNumber = Int32.Parse(NodesAnalysis0[1, 2].ToString());

    Best_Move_StartingRank = Int32.Parse(NodesAnalysis0[1, 4].ToString());

    Best_Move_FinishingColumnNumber = Int32.Parse(NodesAnalysis0[1, 3].ToString());

    Best_Move_FinishingRank = Int32.Parse(NodesAnalysis0[1, 5].ToString());

    for (counter0 = 1; counter0 <= NodeLevel_0_count; counter0++)

    {

        if (NodesAnalysis0[counter0, 0] > temp_score)

        {

            temp_score = NodesAnalysis0[counter0, 0];

            Best_Move_StartingColumnNumber = Int32.Parse(NodesAnalysis0[counter0, 2].ToString());

            Best_Move_StartingRank = Int32.Parse(NodesAnalysis0[counter0, 4].ToString());

            Best_Move_FinishingColumnNumber = Int32.Parse(NodesAnalysis0[counter0, 3].ToString());

            Best_Move_FinishingRank = Int32.Parse(NodesAnalysis0[counter0, 5].ToString());

        }

    }

}

Do the move

Redraw the chessboard

If no move found => Resign

MiniMax algorithm

This is required for the MiniMax algorithm implementation (see here 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

Epilogue

The programming of a chess program is not an easy task. This series of lessons tried to show you the main steps in doing so and to demystify the whole task. It is true that we are all afraid of what we do not know, so the first thing to do when trying to master any new field of knowledge is to just dive into it. Use the code provided, read this lesson, but most important of all: experiment yourself! This is the only way to learn

How to Develop a Chess Series updates