# How to Develop a Chess Program for Dummies 3

This series of tutorials for dummies will show how one can develop a chess playing program in C# from scratch with no prior knowledge of programming. It will guide the reader step-by-step until the final building of a fully-features chess application in Microsoft Visual Studio. The tutorial is based on the open source Huo Chess software developed by me.

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

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.

### 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") == ) && (Skakiera_Dangerous_Squares[(m_FinishingColumnNumber - 1), (m_FinishingRank - 1)] == ))...`

#### 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 == )) => ...`

#### 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 == ) 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") == ) && (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 = ; i <= 7; i++)

{

for (j = ; 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") == ) && (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;```

}

```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") == ) && (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, ] = Temp_Score_Move_0;

NodesAnalysis1[NodeLevel_1_count, ] = Temp_Score_Move_1_human;

NodesAnalysis2[NodeLevel_2_count, ] = Temp_Score_Move_2;

NodesAnalysis3[NodeLevel_3_count, ] = Temp_Score_Move_3_human;

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

NodesAnalysis0[NodeLevel_0_count, 1] = ;

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, ]: 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()), ] = NodesAnalysis2[counter2, ];

}

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

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

}

// 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()), ] = NodesAnalysis1[counter1, ];

}

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

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

}

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

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, ] > temp_score)

{

temp_score = NodesAnalysis0[counter0, ];

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, ] = NodesAnalysis[counter8, 8, ];

if (counter8 > 1)

if (NodesAnalysis[counter8, 8, ] < NodesAnalysis[counter7, 7, ]) NodesAnalysis[counter7, 7, ] = NodesAnalysis[counter8, 8, ];

}

}

}```

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

• Update 2011-09-29: The third lesson with the chess algorithm analysis is now published!
• Update 2018-12-02: Refreshed the article. Fixed minor mistakes.
• Update 2020-03-21: Minor updates and fixes.

## Author: skakos

Spiros Kakos (or Spyros Kakos or Spyridon Kakos) [Σπύρος Κάκος] is a thinker located in Athens, Greece. He has been the Chief Editor of Harmonia Philosophica since its inception. Spiros has a diploma in Chemical Engineering, an MSc in Advanced Materials' Technology, an MBA in Decisions' Science, a phD in the use of conductive polymers in PCB industry and is still learning. He also worked as a technical advisor and a researcher in the Advanced Materials sector for many years in the past. In his free time he develops software solutions and contributes to the open source community. He is the creator of Huo Chess, one of the smallest micro-chess programs ever that is perfect for educational purposes. He believes that science and religion are two sides of the same coin and is profoundly interested in Religion and Science philosophy, as well as the philosophy of the irrational. His philosophical work is mainly concentrated on an effort to free thinking of "logic" and reconcile all philosophical opinions under the umbrella of the "One" that Parmenides - one of the first thinkers - visualized. Since our thought is dictated by our assumptions, the only way to free it and know cosmos as it is, is to think irrationally and destroy everything we have built. The "Harmonia Philosophica" articles program is the tool that will accomplish that. Life's purpose is to be defeated by greater things. And the most important things in life are illogical. We must fight the dogmatic belief in "logic" if we are to stay humans. We should stop thinking in order to think. Credo quia absurdum!