How to Develop a Chess Program for Dummies 2

Other Related articles

Introduction

In the previous (first) lesson we learned about how to create a new project in Microsoft Visual Studio environment. We also learned the basics about object oriented programming – i.e. variables, functions and classes. I demonstrated how one can get user input from the keyboard and store it in a variable, how to create new functions and how to create new classes.

In this second lesson we will learn how to develop the game’s structure (i.e. the loop structure that reads/waits for user input) and the chess engine of our chess program (i.e. the Artificial Intelligence of the application). We will set the starting position of the chessboard, get user input for the human opponent’s move and then start scanning the chessboard to find the best possible move. We will also show how to use the debugging mode to help us look inside the mechanism of the program and how it works.

Huo_Chess_0961_2_small

Method of Teaching

The method of teaching will be as follows: I will analyze in small chapters every aspect of the full chess program, explain in simple words its purpose and how it works and I will show a characteristic part of the C# source code that implement it. With all that you will be able to go to the respective function which implements that aspect in “Huo Chess” and understand how it works in high level.

In that way after this lesson you will be able to read the whole source code of the complete Huo Chess game and at least be able to understand how it works and what every command in it does. Hopefully much more than you ever imagined to do after just two lessons…!!!
This will give you access to the depth of programming as no other tutorial is able to give you. You will not spend weeks after weeks so as to understand how to write a “Hello World” program, but you will be able to experiment on your own and test your own hypothesis on the real “thing”.The commands used in the program are simple and you shouldn’t have a problem with them. I mostly use “if” and “for” commands, which we have analyzed in the previous lesson. Don’t hesitate to contact me for any clarifications you may need.
However you must understand that this lesson will not explain how every function works in full detail. This is the subject of lessons to come. A program like that is complicated and even though you may understand what a function does in general and know all the commands used, you may not be able to grasp the full detail at this stage you are now. Patience is the only good advice I can give you…

Important Note – Learning material

In order to follow the lesson you must download the Huo Chess application source code.

Places to download Huo Chess (source code and executable)

The files above contain all versions of Huo Chess, so be sure you use the C# version – it is tagged as ‘cs’ version in the folder you download).

In every chapter below I will note explicitly which Huo Chess part is the part I am describing. Look for the “Huo Chess Point” tag to find where in the Huo Chess source code is the thing we talk about.

Our progress so far

The program we have developed so far just initiates a screen and asks the user to enter his/her preferred colour. In this lesson I will demonstrate how to build on the knowledge earned in the previous lessons and develop a complete and fully functional game application.

The main program loop

Any game has a main loop which continually “looks” for user input. In case the user presses a key (or in our case, makes a move), it does “something” (in our case it thinks for the best move to make). You have to program that never-ending loop on your own. In our case we will design a never-ending loop that will continuously check for user input and call the computer chess engine in case the user enters a move. When the user enters a move, the program will stop from checking for input and start thinking its answer. As soon as the computers stops thinking and makes a move in the chessboard, the application will once again start waiting for new user input. The code will be as simple as that:

bool exit = false;

do { 
[check for user input]

if user enters move {
  [check user move validity]
  [if move entered is valid => call computer chess engine to answer]
  [if move entered is not valid => prompt for error and do nothing!]
}

}while(exit == false); 

What does that code do? It is based on a do…while loop which continues to loop until the condition inside the parenthesis next to “while” is set to false. It is a rather intuitive set of commands. Until the condition in the “while” (at the bottom of the code segment) becomes true, the set of commands inside the do…while block will continue to execute. So practically the program will continually be in that loop and will exit only when the user enters a move (we will see in details how that is performed).

Huo Chess Point: You can see the respective loop in Huo Chess at the Main(string[] args) function. The Main function of a C# program is the function which is loaded when the program starts. So this is the best place to enter that loop which reads user input.

Setting the chessboard

In order for the game to begin, we must set up the chessboard. The best way to store the chessboard into memory is by using a new kind of variable called “array”. You can visualize an array as a “table” of values. An array can have as many dimensions as we wish. As you may have thought already, in our chess program we need a 2-dimension table that will represent the chessboard.The two dimensions array which the program uses as a virtual representation of the chessboard is declared with the following command:

public static String[,] Skakiera = new String[8,8];

We then use function Starting_position()to fill in that table with the values of the chess pieces. The values are quire straightforward. I enter “White Rook” to represent a white rook, “Black Bishop” to represent a black bishop and so on. In order to note a move (either from the human player of from the computer) you just have to change the initial chessboard square value and the destination chessboard square value.Huo Chess Point: You can see the source code which sets the chessboard starting position in the Starting_position() function.

Human plays a move

When the human enters a move, this move is recorded in the following way:

// Human enters his move

Console.WriteLine("");

Console.Write("Starting column (A to H)...");

m_StartingColumn = Console.ReadLine().ToUpper();

Console.Write("Starting rank (1 to 8).....");

m_StartingRank = Int32.Parse(Console.ReadLine());

Console.Write("Finishing column (A to H)...");

m_FinishingColumn = Console.ReadLine().ToUpper();

Console.Write("Finishing rank (1 to 8).....");

m_FinishingRank = Int32.Parse(Console.ReadLine());

// show the move entered

String huoMove = String.Concat("Your move: ", m_StartingColumn, m_StartingRank.ToString(), " -> " );
huoMove = String.Concat( huoMove, m_FinishingColumn, m_FinishingRank.ToString() );

Console.WriteLine( huoMove );

We use the ReadLine command to read user input from the keyboard. The input (in this case the move parameters) is stored in the variable we will enter in the left side of the operation in the command.
The .ToUpper();function converts the text entered by the user to uppercase letters. This is required because we have only uppercase letters in some “if” statements later in the program.We then use the WriteLine command to show that move on the screen, as a verification that it has been entered and processed by the program.In summary, the program uses the following variables:

  • Variable MovingPiece records the piece that is being moved.
  • Variable StartingColumn records the column of the starting square
  • Variable StartingRank records the rank of the starting square
  • Variable FinishingColumn records the column of the destination square
  • Variable FinishingRank records the rank of the destination square

These variables are then used in the validation checks (see next chapter).

Huo Chess point: Look at the Enter_move()function to see how the program stores the parameters of the move the human player enters.

How to use Debug Mode – Part 1

You can have a look at how the program stores values in the above-mentioned variables by debugging the program. Debugging is the process of analyzing how the program actually works while it is executed, so as to fix any possible bugs. In order to do that you must follow the following steps:

1. Set Breakpoints: Breakpoints are points in the program where you want the debugger to stop execution and let you see what is happening inside your code. You usually set breakpoints at places you expect to have errors or at places you want to examine more closely if they work correctly. Go to line 461 and left-click on the margin at the left of the code window to set a breakpoint as in the following figure.

Set a new breakpoint by clicking on the left margin of the source code window [click on image to enlarge]

2. Run the application in debugging mode: Start the program in debugging mode by pressing F5.

3. The application will execute. Choose white colour as human and enter a move. The program will start filling in the values of the move you entered in the respective variables we mentioned. Because you have a breakpoint it will stop executing exactly after it has stored these values. You will then see the code screen on your monitor.

4. You can now see the values stored in each of these variables and understand more on how the program works. Just hover with your mouse above the name of the variables in the source code window and you will see the value attached to each variable! Easy huh?

See values stored in variables during debugging by hovering over the variable [click on image to enlarge]

Press F5 to continue executing the program or choose Stop Debugging to exit debugging mode.

Human move validation checks

When the human player enters his move the computer must first check of the move is valid. The program makes two kind of validation checks for a move:

1. Checks the legality of the move(this is performed by the ElegxosNomimotitas function – where ‘Elegxos’ stands for ‘Check’ in Greek and ‘Nomimotita’ stands for ‘Legality’ in Greek): This check is related to the kind of move performed. A bishop can move only in diagonals, so if the human player attempts to move a bishop in a horizontal way, the move is not “legal”.

2. Checks the correctness of the move (this is performed by the ElegxosOrthotitas function – where ‘Elegxos’ stands for ‘Check’ in Greek and ‘Orthotita’ stands for ‘Correctness’ in Greek): If the player attempts to move a piece to a square that is already taken by another piece of the same color, then the move is not “correct”. In the same way, if the player attempts to move to a square but another piece exists in the way towards that square, then the move again is not “correct”.We will analyze how these functions work in the next lesson. They are rather “simple” functions that use only the “if” and the “for” commands. For now, just consider them as “black boxes” which you can feed with the variables mentioned above and they return a true-false value that you can use to determine legality and correctness of move. The program calls these functions with the following commands:

// Check correctness of move entered

m_OrthotitaKinisis = ElegxosOrthotitas(Skakiera);

// check legality of move entered

// (only if it is correct - so as to save time!)

if( m_OrthotitaKinisis == true )

       m_NomimotitaKinisis = ElegxosNomimotitas(Skakiera);

else

       m_NomimotitaKinisis = false;

These commands are a normal call to a function (as we showed in the previous lesson) and stored the legality / correctness of the move (true / false) in the NomimotitaKinisis / OrthotitaKinisis variables.
You should have noticed that the program does not bother to call the function ElegxosNomimotitasif the correctness of the move is found to be false in the previous validation check. This is for performance purposes only: there is no need to make more validation checks for legality if the move is not correct.

Huo Chess Point: You can see the respective functions in the program at the Enter_move() function.

How to use Debug Mode – Part 2

You can have a look at how the program analyzes the legality of a move entered by using debugging mode, as we did in the previous chapter:

First, enter a breakpoint where the ElegxosOrthotitas function is called.

Then enter a second breakpoint where the result of the legality check is stored in the NomimotitaKinisis variable.

Set breakpoints where legality and correctness validation checks are performed [click on image to enlarge]

Now run the program in debugging mode by pressing F5.

Choose white as your colour and try to enter e2>d3 as your first move. This is obviously a wrong move.You will see that the program stops at the first breakpoint you have set. Press F5 to go to the second breakpoint. There you will see the legality of the move being stored in the NomimotitaKinisis variable.Hover your mouse over that variable’s name in the source code window and you will see the value of the variable appearing. So you have now verified that your program conducts the correct legality checks. That check is crucial because you might have the move rejected as illegal not due to legality issue but due to a correctness issue (see above for the difference between the two). This is the only way to see under the hood and verify that everything is indeed working the way you want them to.

Computer Thinking Process

After the human opponent plays a move and the computer accepts it, it is now the turn of the AI to initiate so as to find the best answer. The logic of the program is simple:

  1. It scans the chess board to find where its pieces are.
  2. Then the computer makes all possible moves in the chessboard.
  3. It searches and finds the best human answer to each of the moves found in the previous step.
  4. It continues thinking in more depth by applying steps 2 and 3 over and over again.

Let’s start analyzing each step slowly, one at a time.

A. Scanning the chessboard

A simple nested “for” (nested = a for loop inside another for loop) loop is used for the scanning of the chessboard, so as to find where all the pieces of the compute are. You can see that full loop here (I have removed some sections which do not matter right now, leaving just the commands which conduct the main work in the chess engine):

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

{

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

{

if (((Who_Is_Analyzed.CompareTo("HY") == 0) && ((((Skakiera_Thinking[(iii),
(jjj)].CompareTo("White King") == 0) || (Skakiera_Thinking[(iii),
|| ......... (Skakiera_Thinking[(iii), (jjj)].CompareTo("Black Pawn") == 0))
&& (m_PlayerColor.CompareTo("Black") == 0)))))

{

for (int w = 0; w <= 7; w++)

{

for (int r = 0; r <= 7; r++)

{

// Changed in version 0.5

Danger_penalty = false;

Attackers_penalty = false;

Defenders_value_penalty = false;

MovingPiece = Skakiera_Thinking[(iii), (jjj)];

m_StartingColumnNumber = iii + 1;

m_FinishingColumnNumber = w + 1;

m_StartingRank = jjj + 1;

m_FinishingRank = r + 1;

Moving_Piece_Value = 0;

Destination_Piece_Value = 0;

// Calculate the value (total value) of the moving piece

.........

// Find the value of the piece in the destination square

.........

CheckMove(Skakiera_Thinking); 

...

}

}

}

}

}

The “if” statement checks whether the piece detected is a piece of the same color as the color of the computer. If yes, the program proceeds with the next steps of the thinking process (after some checks about the dangerousness of the destination square, which I have omitted here for clarity purposes).

Huo Chess point: Look at ComputerMove(string[,] Skakiera_Thinking_init) function for the above-mentioned main chess engine loop. This loop is referred to in the following steps as well.

B. Finding all possible moves

The first thing to do in order to find the best move, is to find all the possible moves that the computer can make in the current chessboard position. Huo Chess uses a very simple and brute way to find all possible moves: it actually attempts to move every piece in every possible square of the chessboard and then checks the legality and the correctness of these moves. Every move that has legality=true and correctness=true is a valid move worth analyzing!

The code that performs the moving of all pieces to all possible directions is:

for (int w = 0; w <= 7; w++)

{

for (int r = 0; r <= 7; r++)

{

MovingPiece = Skakiera_Thinking[(iii), (jjj)];

m_StartingColumnNumber = iii + 1;

m_FinishingColumnNumber = w + 1;

m_StartingRank = jjj + 1;

m_FinishingRank = r + 1;

.........

CheckMove(Skakiera_Thinking);

}

}

In particular, this nested “for” loop stores every possible value as destination square parameters (in the m_FinishingColumnNumber and m_FinishingRankvariables respectively). The computer “makes” the moves in the 2-dimensions tables (virtual chessboards) we use to represent the chessboard in the computer memory. “Making” the move actually means that the program stores the starting and destination square parameters in the respetive variables.The code then calls the CheckMove(Skakiera_Thinking) function to see if that move is valid or not and – if yes – the same function (CheckMove(Skakiera_Thinking)) rates the move to see how good it is.
This function is another key ingredient of the game: it is the functions which performs the analysis of the move and rates it. We will have a separate lesson for the function only in the future lessons. For now you need to know that this function rates all moves, after it has reached the thinking depth we have set.

The code in CheckMove(Skakiera_Thinking) checks the legality and correctness of every possible move by using the ElegxosNomimotitas and ElegxosOrthotitas functions that we mentioned above (see the CheckMove(string[,]  CMSkakiera) function).

Every move that passes the legality and correctness checks is conducted by the program so as to find the best of them (see next steps right below).

C. Rating each move analyzed

Each possible move must be analyzed and rated. After all possible moves have been analyzed and rated, the computer simply chooses the best move (i.e. the move with the best rating). The rating of each move is calculated by the program with the help of the CountScore(string[,] CSSkakiera) function. After the computer has reached the thinking depth we have set, it sends the final position it has reached to the CountScore function and the latter calculates the score of that position.

You can see part of the CountScore function here:

if (CSSkakiera[(i), (j)].CompareTo("White Pawn") == 0)

Current_Move_Score = Current_Move_Score + 1;

else if (CSSkakiera[(i), (j)].CompareTo("White Rook") == 0)

{

.........

Current_Move_Score = Current_Move_Score + 5;

}
.........
.........
else if (CSSkakiera[(i), (j)].CompareTo("Black Rook") == 0)

{

.........

Current_Move_Score = Current_Move_Score - 5;

}

As you can see the way it works is very simple: It just scans the chessboard with a nested for statement and adds points when if finds white pieces and subtracts points when it finds black pieces. The final score is then a clear indication of who wins the game at the current position.

Huo Chess point: Look the CountScore(string[,] CSSkakiera)function.

D. Deciding on the best move

The final decision of which move to play is conducted in the CheckMove function with the following set of commands:

// DO THE BEST MOVE FOUND

if (Move_Analyzed == 0)

{

// Επαναφορά της τιμής της Stop_Analyzing (βλ. πιο πάνω)

Stop_Analyzing = false;

// REDRAW THE CHESSBOARD

// erase the initial square

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

{

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

{

Skakiera[(iii), (jjj)] = Skakiera_Move_0[(iii), (jjj)];

}

}

MovingPiece = Skakiera[(Best_Move_StartingColumnNumber - 1), (Best_Move_StartingRank - 1)];

Skakiera[(Best_Move_StartingColumnNumber - 1), (Best_Move_StartingRank - 1)] = "";

.........

// position piece to the square of destination


Skakiera[(Best_Move_FinishingColumnNumber - 1), (Best_Move_FinishingRank - 1)] = MovingPiece;

These commands tell the computer to use the parameters of the Best Move (where the best move that has so far been found is stored) and then make the move.

Next lesson

In the next lesson we will analyze deeper the chess engine algorithm that is used to make the computer think and actually play chess.

What we have accomplished

In this second lesson, we have accomplished the following not-so-trivial tasks:

  • Understood how the game loop is used to read input from the game’s user.
  • Outlined the thinking process of the computer.
  • Understood what each function used in the AI process does at high level.
  • Had a look inside some functions of the program.
  • Looked at how we can use the debugging mode to see the mechanisms of the program.

Until the next time, happy coding and experimenting!

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.

16 responses to “How to Develop a Chess Program for Dummies 2”

  1. THANKS — THIS WILL COME IN HANDY SOME TIME FOR SOME PEOPLE

    Like

    1. Untitled — Thanks. I am trying to post the 3rd lesson of the series but I am really short of free time at the moment. I hope during this year I will be able to do it… Any comments or suggestions for that next lesson are more than welcomed!

      Like

  2. Luis Alberto Migliorero — I am following the course, please continiu with the third and oters parts of the course. I am programming a chess engine and i need help.Greetings, Luis Alberto.

    Like

    1. Untitled — Thanks Luis. I am trying to write the third part.

      Like

  3. Best Knol of the Month August 2009 — Congratulation!Your Knol is the winner of the Contest Best Knol of the Month August 2009! This Knol gets the second place!http://knol.google.com/k/andreas-kemper/best-knol-of-the-month/8bgikaqot3ts/46#You get together 45.596 Knol Translation Points.http://knol.google.com/k/andreas-kemper/knol-translation-points/8bgikaqot3ts/207#viewBestAndreas

    Like

    1. Untitled — Thanks! Ευχαριστώ!

      Like

  4. You are an excellent athour because of the excellent contents in your knols — I read your another knol article which discusses about the harmonization of religion and science. Although you are not a sociologist but a scientist, the article was interesting and in detail. Moreover, you are the author of this artificial intelligence programming article, which is far another topic. I have two independent questions about your ability and this article. For your ability, how can one be a multi-disciplinary researcher who has in-depth knowledge for each field? Next, my question on this knol is as follows. Do you believe, by solely computer programming without fundamentally new hardware architectures we can build up an intelligent machine similar to human intelligence? 2009.8.27 -James

    Like

    1. Untitled — Mr. Pandya,I have challenged you in the Best Knol of the Month knol to write down the parts of the article you think I “stole”. I am still waiting. Remember, a text-to-text comparison, not just posting text from one article. However I am really glad you removed your accusations from that comment of yours. Please do so here as well and we can call it a day.

      Like

    2. Untitled — How clueless and irrelevant to the subject in matter must you be to say such an idiotic thing. The article to which you refer is posted YEARS after I have developed my chess and posted my first articles on Codeproject (yes, I am an old member of Codeproject – see below for more surprise details). And the chess in the article you refer to has nothing to do with my program at all! Let alone the article, which has no similarity whatsoever!I have personally written every single line of code in Huo Chess program and my articles and I challenge you to prove otherwise (if you know anything about programming of course). I have posted my chess program in numerous online freeware libraries (see code.msdn.microsoft.com/huochess, http://www.codeproject.com/KB/game/cpp_microchess.aspx, http://www.codeplex.com/huochess for a small sample of them) and answered to various comments on it during the last few years.As for the article, go to the Huo Chess page in Codeproject (http://www.codeproject.com/KB/game/cpp_microchess.aspx) just to see what I have written there years before the article you refer. There you will also find some of my communication exchanges with other programmers. You accuse me of stealing a Codeproject article. I must so inform you that I am an old member of the Codeproject community for years under the username Palavos (see http://www.codeproject.com/script/Membership/View.aspx?mid=1712453) !!! Do better research next time…It is also of uttmost importance to stress the fact that I have already communicated with the creator of that other chess (you know, the one from whom you accuse me of copying the article) and I am discussing with him as programmer-to-programmer!! I have also made a comment to his page in the comments section (see the bottom of the page and remember I have the username Palavos in Codeproject), where the writer of the article you refer to gladly accepted the challenge to have our two chess programs play with each other! That’s all for the communication I already have with the writer from whom you accuse me of stealing! Hahaha!!!So please recall and mind what you write the next time. (I could delete it myself or report it to Google as abusive, but I trust you do it yourself) Gaining some votes in the Best Knol Competition is not a very good reason to be completely humiliated publicly.PS. What does it mean “he is a chemical engineer with an MBA”? Does that prove something about my knowledge in programming? I am in programming since I was a kid and your comment simply proves that you know nothing about the whole area of programmers at all! I know programmers who have studied theology for Christ’s sake!!! You can find me also at http://www.kakos.com.gr.

      Like

    3. Untitled — Dear James,The Knol Author himself is a Chemical Engineer & MBA.Do you think that this knol is from his mind?its all COPIED content I’ve Personally Observed & Reserched From Following Link(s):(1)http://www.codeproject.com/KB/java/Chess_JavaFX.aspxAnd This Type of knol are getting best knol award in HALL OF KNOL contests.Got it?Have a nice day.Regards,Mr.C.M.PANDYA

      Like

    4. Untitled — Godel proved that no given set of axioms can construct a full “truth” system – likewise no given set of computer instructions can help the computer answer everything. We, on the other hand, have an inherent capability and belief that we can answer everything somehow, someday. That seems to show that our thinking is not algorithmic. This is an argument postulated by Roger Penrose on his book “The last emperor?”. And you are more than right with what you say about quantum computers: indeed Penrose thinks that our brain works by using quantum states and not just algoritmically finetuning its neurons.The randomization approach is not something that can result into something able to pass the Turing Test. You can find many chatterbots in the internet, but not one can stand a conversation with a human more that 2 minutes without being exposed it is a machine.The question on how we can have human-level intelligent machines is tricky. Maybe we can in some very specific fields, like chess. Is that what you have in mind? For chess I can tell you all the problems I had and you will understand what I mean when I say that “algorithmic” is not the answer to the problem of the human brain. For the others we can discuss as well of course.

      Like

    5. Untitled — Thank you for your answer. I read a few book about Godel but I haven’t checked whether he proves the impossibility of artificial human intelligence. Is it right if I fix your answer only to the recent form of computing machines which will not be changed their hardware architecture fundamentally such as using Quantum computing concept. Back to the Godel’s theorem, even if considering randomization approach, do you believe that their proof is valid? The machine can answer to any question if he has randomization logics, although the answer is not exactly matched to the question. If no, what do you think how we can make human-level intelligence machine? -James

      Like

    6. Untitled — The answer to the 1st question is: reading a lot every time you have a chance. As for your second question the answer is: no! If I ask you anything, you will be able to say something. However a computer cannot do that because it thinks algorithmically based on a given set of instructions. And Godel and Turing proved that no given set of instructions can make a computer able to discuss everything.

      Like

  5. […] article is part of the How to Develop a Chess program for Dummies Series. Click here for the second lesson. Click here for the third […]

    Like

  6. […] of the How to Develop a Chess program for Dummies Series. Click here for the first lesson. Click here for the second […]

    Like

  7. […] to Develop a Chess program for Dummies Series. Click here for the second lesson. Click here for the third […]

    Like

%d bloggers like this: