Programming a chess application in QBasic (QB64)

Advertisements

Other Related articles

News

  • 2021-03-14: Updated thinking in levels 4 and 5; now extra analysis at these levels only happens if the move entails the capturing of a piece. Updated CountScore to include positional elements in the evaluation. Introduced the notions of mate and stalemate in the thinking process.
  • 2020-12-16: Fixed issue with en passant move.

This is an article on how one can develop a chess program in QBasic.

It is based on Huo Chess that was developed by me and is available as open source in multiple programming languages (C#, Java, older versions in C++ and Visual Basic).

Parts of the article have been posted as separate tutorials (check here). They are all gathered here in a unique article that can provide an overall understanding of the chess programming complexity.

The tutorial is at the point at a very simple/ high level but it will be enriched as time passes by. The initial goal was to have at least a starting point for someone who needs to delve into the chess programming cosmos and this I believe I have managed to achieve.

Why in QBasic?

Well, BASIC is simple and fun!

Do you need more reasons?

Well…

Here is another one:

10 PRINT "Why not?!"
20 GOTO 10

That’s what happens when you mess with BASIC. Seriously now, at the end, the goal here is to present the algorithm. The specific language of the implementation does not play a particular role. When you are at a level to develop the next Stockfish be sure to remember that it was here from where you started your journey…

The tutorial should be read in conjunction with the source code of Huo Chess offered here. The code itself is written in a simple and structured way and it is heavily commented so that even without any prior knowledge one can easily understand how thw algorithm works.

Let’s not waste any more time!

Happy coding!

I. Beginning

Let us begin from the… beginning. And one step at a time, try to see how we can develop our chess program.

Important Notes

  • Refer to QB64 site for questions regarding how QBasic commands work. Essentially they are simple, but in case your are stuck with an error you cannot resolve, this is the place where you will find your answers.
  • Always have the source code open in a separate window. Although the tutorial only goes throug portions of the code to explain how it works, it is always beneficial to have the whole source code of the working program in front of you.
  • A note about the source code versions: Chapter I to IV refer to the version 0.3 of the code. Chapter V refers to the version 0.6 of the code.

And don’t forget: Coding is about experimenting!

Do not wait everything from this tutorial or from any other tutorial! Just open the QBasic editor and write code! Change things! See what they do! At the end it is YOU who is learning, not me teaching you!

Programming is fun.

Want to learn? Why not start now?

And what better way there is than to develop an advanced program that makes the computer “think” how to play chess?! Forget about those silly beginners’ example programs which print “Hello world”. Who in his right mind ever spends time to write a program which prints “Hello world” on the screen?

BASIC is fun.

A very easy language for kids to start learning programming. So we will use it here. (Not in the mood for BASIC? Search for the Java and C# relevant tutorials in Harmonia Philosophica!)

And in one day, you will have learnt the basic of how to program a chess program in BASIC! The actual implementation could take a bit longer but in general in some days you will have the knowledge of how the program works, thus being in a position to improve it or write your own!

The BASIC programming language is one of the simplest ones. Especially designed for simplicity, it uses simple commands to perform operations. The commands are easy to learn and use, since they are utilizing English language words which are easily recognizable. Want to print something on the screen? Use the command PRINT! Want to determine what will happen if something else happens? Use the command IF! See what I mean?

IF YOU_UNDERSTAND = "Yes" THEN PRINT "Yes I understand!"

Did you understand the above command? Great!

The only thing that might trouble you if you are new to programming is the notion of variables. A variable is an element which holds values. This element is used in various places of the program. The values could be of different types – the ones we will use are integers (1, 4, 10…) and strings/ characters (e.g. “white pawn”).

Variables could be stored also in arrays. An array is a collection of variables in one or more dimensions. It is also known as a “table”. And yes, you guessed right: we will use an array (table) to store the chessboard. Could you guess the dimensions of that table? Spot on again.

DIM SHARED chessboard$(8, 8)

The command DIM defines a variable. We do all the variable declarations in the beginning of the program. The above command declares an 8×8 array which holds the… you guessed it right: The chessboard!

By the way, we are using QBasic64, a version of Quick Basic that is available for free and pretty popular as well. Check https://www.qb64.org/portal/ to get it. The site also contains excellent tutorials and training material. You will have it as a reference throughout the whole process, so make sure you create a bookmark out of it.

After you download QBasic64 from the site, just click on the QB64.exe file and execute it. You will be presented with the IDE (programming interface) of QBasic where you will write your program. I do not need to explain the “Create new”, “Save” or “Save as” functions…

Just start writing the commands and then press “Save as”. Executing the program is easy as well. Just select Run > Start.

As said above, what is the first thing to do? (Besides the “Create new program” part and saving it in a folder of your choosing with a name of your choosing as well)

Some of the first things to do we already mentioned.

First, declare the variables. BASIC is really simple in the sense that it is not so strict in requiring you to declare all the variables before using them, in contrast to other high level languages like C#. However this is also a downside of the language. Leaving the programmer with some slack makes the programmer careless.

So we will declare all the variables we use…

DEFINT A-Z
OPTION BASE 1 'Make tables dimensions start from 1
DIM SHARED chessboard$(8, 8)
COMMON SHARED startingRank, startingColumn
COMMON SHARED finishingRank, finishingColumn
COMMON SHARED startingRankText$, startingColumnText$
COMMON SHARED finishingRankText$, finishingColumnText$
COMMON SHARED Move$
COMMON SHARED MovingPiece$
COMMON SHARED debugMode

There you go. (Read the QB64 Wiki for what DEFINT A-Z and OPTION BASE 1 commands do – Remember, learning entails the process of… learning)

What is next?

What else?

Ask the user for input!

And what else to ask than his first move! For simplicity purposes we will present the main command which tells the user to put his move. The drawing of the board on the screen will be done by the drawBoard() function. A function is an independent set of code that you can call to perform an action. In our case we call the drawBoard function (with the command… CALL DRAWBOARD – I told you it was simple). For the time being forget how the function works. (Even though reading through it and trying to understand how it works would be a lesson on its own…)

So how would you ask for the user input?

Simple by the command… INPUT!

There you go:

INPUT "Enter your move: ", Move$

This command tells the computer to wait for the user to enter something and press Enter. When this happens, the text entered by the user is saved in the Move$ variable. The dollar sign ($) indicates that the variable is a string (text) and not a number.

Let’s stay there.

For now you have learnt how to…

  • Create a new program.
  • Declare the variables you will use (including the chessboard).
  • Ask from the user to enter his first move.

You have also been acquainted with the notions of variables and functions and with some basic BASIC (get the joke?) commands, like IF… THEN or INPUT and PRINT. Don’t worry if you don’t get everything yet. You will as you program more and more every day.

Next lessons will include the next logical steps:

  • Validate that the user move is valid and legal.
  • Redraw the chessboard with the move of the user.
  • Make the computer think of an answer.

You would be surprised how the last part (the thinking of the computer) is a rather simple one. In essence the computer thinks of all possible moves, validates them (in the same way we will validate the move entered by the user) and then for the valid ones it will calculate a score of the position. The move with the best score will be the move of the computer.

II. Check legality of a move

In the previous chapter we managed to create our program in BASIC (QB64) and write the first lines of code to ask for input from the user for his move.

Now we will perform the next and one of the most important steps in a chess program: Checking the legality and validity of a move!

Remember that we asked from the user his move by the command…

INPUT "Enter your move: ", Move$

With this command the computer asks for input by the user and then stores what the user entered (after he presses Enter) into the Move$ variable. As we said in the previous lesson, the $ sign in a variable name denotes that the variable stores a string (text) value and not a number.

Now that we have the move into a single text variable, we should first of all “break it down” into four specific elements:

  • Starting column
  • Starting rank
  • Finishing column
  • Finishing rank

In that way we will have the starting and finishing coordinates of the user’s move, which we will use for the checking of the legality of the move later on.

How do we “break up” the text? By using the MID$ built-in function of BASIC which returns a specific character from a text. So if the user entered the move “g2g4” (which is Grob opening by the way, one of my favorites), then the command…

MID$(Move$, 2, 1)

will return the character “2”, since it will start from character 2 of the Move$ variable and will get 1 character.

Without further delay, here is the code which breaks up the move the user entered into the four numbers we are looking for.

INPUT "Enter your move: ", Move$
startingColumnText$ = MID$(Move$, 1, 1)
startingRankText$ = MID$(Move$, 2, 1)
finishingColumnText$ = MID$(Move$, 3, 1)
finishingRankText$ = MID$(Move$, 4, 1)
SELECT CASE startingRankText$
CASE "1"
startingRank = 1
CASE "2"
startingRank = 2
CASE "3"
startingRank = 3
CASE "4"
startingRank = 4
CASE "5"
startingRank = 5
CASE "6"
startingRank = 6
CASE "7"
startingRank = 7
CASE "8"
startingRank = 8
END SELECT
SELECT CASE finishingRankText$
CASE "1"
finishingRank = 1
CASE "2"
finishingRank = 2
CASE "3"
finishingRank = 3
CASE "4"
finishingRank = 4
CASE "5"
finishingRank = 5
CASE "6"
finishingRank = 6
CASE "7"
finishingRank = 7
CASE "8"
finishingRank = 8
END SELECT
SELECT CASE startingColumnText$
CASE "A", "a"
startingColumn = 1
CASE "B", "b"
startingColumn = 2
CASE "C", "c"
startingColumn = 3
CASE "D", "d"
startingColumn = 4
CASE "E", "e"
startingColumn = 5
CASE "F", "f"
startingColumn = 6
CASE "G", "g"
startingColumn = 7
CASE "H", "h"
startingColumn = 8
END SELECT
SELECT CASE finishingColumnText$
CASE "A", "a"
finishingColumn = 1
CASE "B", "b"
finishingColumn = 2
CASE "C", "c"
finishingColumn = 3
CASE "D", "d"
finishingColumn = 4
CASE "E", "e"
finishingColumn = 5
CASE "F", "f"
finishingColumn = 6
CASE "G", "g"
finishingColumn = 7
CASE "H", "h"
finishingColumn = 8
END SELECT

The above code breaks up the Move$ into the above-mentioned four numbers and you would have noticed that the break up has two steps which we didn’t quite mention before: First we break up the text and then we ‘translate’ the four text values into numbers. This is done with the SELECT CASE commands, which essentially select different numeric value for each possible value of the columns and ranks. And yes, the text “8” needs to be translated to the number 8. As far as the computer is concerned they are completely different monsters altogether.

So now we have what we need. The starting column and rank and the finishing ones. How do we check the legality and validity of the move? Well, there is no “magic” way. We just have to write code to do that.

For clarity purposes we will gather all the code performing the check of the legality in one function (= set of code) which we will call ElegxosNomimotitas (= Check of Legality, in Greek). We will define the call parameters of the function (i.e. what parameters we need to pass over the function for it to do its job) and then write the code inside it.

What would be the input parameters?

The starting and end column and ranks of course. And we will also send the Moving Piece in a separate variable because this is a crucial part of the function. Different pieces move in a different way, right?

The function declaration would be something like…

DECLARE SUB ElegxosNomimotitas(ENSkakiera() AS STRING, startColumn AS INTEGER, startRank AS INTEGER, finishColumn AS INTEGER, finishRank AS INTEGER, MovingPieceEN AS STRING)

The ENSkakiera (=Elegxos Nomimotitas Skakiera = Check Legality Chessboard in Greek) is the array of the chessboard (= Skakiera in Greek) we will need to pass. The function will check the legality of a move not in general, but in the context of a specific chessboard of course. Then beyond the chessboard we pass over the start and end columns and ranks and the Moving piece as mentioned above.

Now we are in the function which checks the legality of the move. We will show how to do this for one piece, the rook. Then the logic is similar (not exactly, but you will get the meaning) for the other pieces.

Without further delay, here is the code…

IF (MovingPieceEN$ = "wrook" OR MovingPieceEN$ = "brook") THEN

    IF debugMode = 1 THEN PRINT "Nomimotita = " + STR$(NomimotitaEN)

    'Check correctness of move (Rook only moves in lines)

    IF ((startColumn <> finishColumn) AND (startRank <> finishRank)) THEN NomimotitaEN = 0

    IF debugMode = 1 AND NomimotitaEN = 0 THEN PRINT "Checkpoint ROOK-0"

    'Check if the Rook moves beyond the limits of the chessboard

    IF ((finishColumn < 1) OR (finishRank < 1)) THEN NomimotitaEN = 0
    IF ((finishColumn > 8) OR (finishRank > 8)) THEN NomimotitaEN = 0


    'Check if another piece is between the current and the target square

    'Horizontal movement

    IF (startColumn > finishColumn) AND (startRank = finishRank) THEN
        FOR J = startColumn TO finishColumn STEP -1
            IF (J <> startColumn) AND (J <> finishColumn) AND ENSkakiera(J, startRank) <> "" THEN NomimotitaEN = 0
        NEXT J
    END IF

    IF (startColumn < finishColumn) AND (startRank = finishRank) THEN
        FOR J = startColumn TO finishColumn
            IF (J <> startColumn) AND (J <> finishColumn) AND ENSkakiera(J, startRank) <> "" THEN NomimotitaEN = 0
        NEXT J
    END IF

    'Vertical movement

    IF (startColumn = finishColumn) AND (startRank > finishRank) THEN
        FOR J = startRank TO finishRank STEP -1
            IF (J <> startRank) AND (J <> finishRank) AND ENSkakiera(startColumn, J) <> "" THEN NomimotitaEN = 0
        NEXT J
    END IF

    IF (startColumn = finishColumn) AND (startRank < finishRank) THEN
        FOR J = startRank TO finishRank
            IF (J <> startRank) AND (J <> finishRank) AND ENSkakiera(startColumn, J) <> "" THEN NomimotitaEN = 0
        NEXT J
    END IF

    'If the start square is the same as the destination...
    IF startColumn = finishColumn AND startRank = finishRank THEN NomimotitaEN = 0

    'Check if a piece of the same colour is at the destination square
    IF MID$(ENSkakiera$(finishColumn, finishRank), 1, 1) = MID$(ENSkakiera$(startColumn, startRank), 1, 1) THEN NomimotitaEN = 0

    IF debugMode = 1 AND NomimotitaEN = 0 THEN PRINT "Checkpoint ROOK-5": 'INPUT a$

END IF

This code checks for many things:

  • If the rook moves in rows or columns
  • If the rook moved beyond the limits of the chessboard
  • If the rook is blocked by another piece before he reaches the destination square
  • If there is a piece of the same colour at the destination square.

If any of the above validations fail, then the Nomimotita (legality in Greek) variable is set to false (0). If not, the Nomimotita is 1 (= true). Note that we use an integer variable to indicate the Nomimotita (which takes values 0 or 1) instead of a text variable (which would take the values “True” or “False”) to use less memory. But we could anyway use a text variable with the same result.

Note: The “IF debugMode = 1” lines of code are used to print to the screen messages for debugging.

It may look complicated, but at the end it is not. The code is simple and self explanatory, with comments. Take for example the first validation: A rook must move in columns or ranks. How is this translated in the code?

    IF ((startRank = finishRank) AND (startColumn <> finishColumn)) THEN NomimotitaEN = 0
IF ((startColumn = finishColumn) AND (startRank <> finishRank)) THEN NomimotitaEN = 0
IF ((startColumn <> finishColumn) AND (startRank <> finishRank)) THEN NomimotitaEN = 0

Read the code at your own pace.

At the end it is just… English. 🙂

After making sure that the move entered is valid, then all we have to do is… make it and present it to the screen.

'If move is legal, then do the move and present it in the chessbooard
IF Nomimotita = 1 THEN

    IF debugMode = 1 THEN
        PRINT "Now we will redraw the chessboard"
    END IF

    'Do the move
    chessboard$(finishingColumn, finishingRank) = chessboard$(startingColumn, startingRank)
    chessboard$(startingColumn, startingRank) = ""
    CLS
    CALL drawBoard

END IF

Go on and check the program source code (check at the end of the tutorial to find it), which contains all the other move validity checks for all the other pieces. You will find it pretty easy to read and understand. It contains comments within the code to support you in your lesson. Copy and paste the code in your QBasic interpreter/ compiler to see it and compile it.

III. Chess thinking algorithm

In the previous chapter we managed to create the function that checks the legality of a move. With that we managed to check the move entered by the user and present it to the screen.

What is next?

To make the computer think of an answer!

In essence this is easy! (the difficult part is to make the computer think of a really good move, that we will tackle later on)

What we will need besides the SUB which checks the legality of the move (ElegxosNomimotitas) is a SUB which counts the score of any given position in the chessboard. This will allow us to evaluate all the possible moves, so that the computer can select the best one.

This is done by the code below, which simply scans the chessboard for pieces and adds or subtracts the value of each piece it founds from the total score of the chessboard.

SUB countScore

positionScore = 0

FOR I = 1 TO 8
    FOR J = 1 TO 8

        IF chessboard$(I, J) = "wpawn" THEN positionScore = positionScore + 1
        IF chessboard$(I, J) = "wrook" THEN positionScore = positionScore + 5
        IF chessboard$(I, J) = "wknight" THEN positionScore = positionScore + 3
        IF chessboard$(I, J) = "wbishop" THEN positionScore = positionScore + 3
        IF chessboard$(I, J) = "wqueen" THEN positionScore = positionScore + 9
        IF chessboard$(I, J) = "wking" THEN positionScore = positionScore + 100

        IF chessboard$(I, J) = "bpawn" THEN positionScore = positionScore - 1
        IF chessboard$(I, J) = "brook" THEN positionScore = positionScore - 5
        IF chessboard$(I, J) = "bknight" THEN positionScore = positionScore - 3
        IF chessboard$(I, J) = "bbishop" THEN positionScore = positionScore - 3
        IF chessboard$(I, J) = "bqueen" THEN positionScore = positionScore - 9
        IF chessboard$(I, J) = "bking" THEN positionScore = positionScore - 100

    NEXT J
NEXT I

END SUB

Easy? Pretty much. All that is needed is a nested FOR loop (read in QB64 here how that works). Nothing more.

Now that we have that, let’s move on to the main course.

The ComputerMove SUB, which – you guessed right – makes the computer perform a move!

In essence, the steps needed are pretty simple:

Scan the chessboard.

If you find a piece of the computer, then…

Scan all possible moves of that piece to all squares of the chessboard.

For every possible move, check the legality of that move.

If the move is legal, then make it!

Check the score of the move.

If the score is best than the current best move (in the beginning there obviously no current best move), then this is the current best move!

After you have examined all the possible moves, do the current best move

Simple isn’t it?

How is the scanning of the chessboard and the checking of all possible moves performed? With four nested FOR loops.

Check the code below. It simple scans all the chessboard with the FOR loops of I and J and then, if it finds a piece which belongs to the computer, it scans all possible destination squares with the FOR loops of ii and jj.

How do we determine is the piece we found is one of the computer’s pieces? We compare the first letter of the piece (which would be ‘w’ or ‘b’ for white and black pieces) with the color of the player. If for example the color of the player is ‘w’ (for white) and we encounter a piece ‘brook’, then this is a piece of the computer since it is black – i.e. opposite than the color of the player.

'Scan the chessboard...
FOR I = 1 TO 8
    FOR J = 1 TO 8

        'If you find a piece of the computer...
        IF ((MID$(chessboard$(I, J), 1, 1) = "w" AND playerColor$ = "b") OR (MID$(chessboard$(I, J), 1, 1) = "b" AND playerColor$ = "w")) THEN

            'Scan all possible destination squares...
            FOR ii = 1 TO 8
                FOR jj = 1 TO 8

                    startingColumn = I
                    startingRank = J
                    finishingColumn = ii
                    finishingRank = jj

                    MovingPiece$ = chessboard$(I, J)
                    ProsorinoKommati$ = chessboard$(ii, jj)

                    'Check legality of the move entered
                    CALL ElegxosNomimotitas(chessboard$(), 0, startingColumn, startingRank, finishingColumn, finishingRank, MovingPiece$)

                    'If move is legal, then do the move and present it in the chessbooard
                    IF Nomimotita = 1 THEN

                        'Do the move
                        chessboard$(finishingColumn, finishingRank) = chessboard$(startingColumn, startingRank)
                        chessboard$(startingColumn, startingRank) = ""

                        'Count the score of the move
                        CALL countScore

                        'If the score is better than the existing best score, then this is the best move now (and the best score)
                        IF ((playerColor$ = "b" AND positionScore >= bestPositionScore) OR (playerColor$ = "w" AND positionScore <= bestPositionScore)) THEN
                            bestStartingRank = startingRank
                            bestStartingColumn = startingColumn
                            bestFinishingRank = finishingRank
                            bestFinishingColumn = finishingColumn
                            bestPositionScore = positionScore
                        END IF

                    END IF

                    'Undo the move
                    chessboard$(startingColumn, startingRank) = MovingPiece$
                    chessboard$(finishingColumn, finishingRank) = ProsorinoKommati$

                NEXT jj
            NEXT ii

        END IF

    NEXT J
NEXT I

If the move analyzed is legal (the ElegxosNomimotitas SUB is called to determine that) then the move is performed. The score of the position resulting after that is counted (the CountScore SUB is called for that). If the score is better than the current ‘best score’ (the initial best score is zero of course) then this move is registered as best move.

After the scanning is complete, we simply perform the best move!

'Do the best move found
chessboard$(bestFinishingColumn, bestFinishingRank) = chessboard$(bestStartingColumn, bestStartingRank)
chessboard$(bestStartingColumn, bestStartingRank) = ""
CLS
CALL drawBoard

Easy? Yes!

IV. Advanced concepts (Part 1)

The last chapters (Advanced concepts Part 1 and 2) will touch-base on some more advanced concepts in chess programming:

  • Thinking for more moves ahead in the game
  • Improving the position evaluation
  • Selecting the best move (miniMax concept introduction)

Up to now the program we have developed (see the previous lessons, where you can download the program) can think in one (1) move depth. This means that it simply (well, not ‘simply’ – we have gone a long way to make this happen) scans all the possible moves and then selects the one with the highest score.

This has just gave us an insight of the way a computer may think for chess, but a very limited one. The basic thing for thinking for chess is thinking in depth. Everybody would agree that thinking in more depth makes someone a better player.

How can we make that happen?

Simple!

We will copy-and-paste (sort of speak) the main computerMove SUB (Move depth 1 – Existing) two times more, so that the computer also thinks two moves more in depth. In essence, there will be two additional ‘thinking SUB-routines’: One which thinks of the potential human moves (Move depth 2) and another that thinks of the reactions of the computer to those moves (Move depth 3).

After that we will have the following structure:

DEPTH 1: computerMove: This routine thinks of the potential moves of the computer at the first level of thinking. If the thinkingDepth is not reached (i.e. if it is not set to 1, but e.g. 3) then the HumanMove1 SUB is called.

IF Move = thinkingDepth THEN
   'If the score is better than the existing best score, then this is the best move now (and the best score)
   IF ((playerColor$ = "b" AND positionScore >= bestPositionScore) OR (playerColor$ = "w" AND positionScore <= bestPositionScore)) THEN
           bestStartingRank = startingRank
           bestStartingColumn = startingColumn
           bestFinishingRank = finishingRank
           bestFinishingColumn = finishingColumn
           bestPositionScore = positionScore
   END IF
END IF

IF Move < thinkingDepth THEN CALL HumanMove1(chessboard$())

DEPTH 2: HumanMove1: This routine is scanning for all the possible answers of the human opponent. For each of those movements, the next thinking depth routine is called.

DEPTH 3: ComputerMove2: The last routine. Searches for possible moves at depth 3 (i.e. 3 half-moves). The move which ends up with the position with the best score at the end, is the one chosen.

IF ((playerColor$ = "b" AND positionScore >= bestPositionScore) OR (playerColor$ = "w" AND positionScore <= bestPositionScore)) THEN
          bestStartingRank = startingRank
          bestStartingColumn = startingColumn
          bestFinishingRank = finishingRank
          bestFinishingColumn = finishingColumn
          bestPositionScore = positionScore
END IF

With these you will have the program think in depth of 3 half-moves (i.e. a move of the computer, a move of the human opponent and a last move by the computer).

We have been slowly progressing.

Yet, there is a lot more way to go…

V. Advanced concepts (Part 2): Improving the computer thinking with MiniMax

The algorithm described above is simple and does make the computer think in depth. When using the code below, you will see an obvious latency in computer’s thinking vis-a-vis the time needed by the previous version which thinks in depth of only 1 move.

When using the code however one can see that it does not make good moves! Simply by checking the score of the positions at the end, does not lead to wise decisions. The computer thinks, but not very well.

Yet.

What is needed for that to happen?

First improvement: Improvement of the position evaluation.

Now we are just counting the material in the final position.

SUB countScore

positionScore = 0

FOR I = 1 TO 8
    FOR J = 1 TO 8

IF chessboard$(I, J) = "wpawn" THEN positionScore = positionScore + 1
IF chessboard$(I, J) = "wrook" THEN positionScore = positionScore + 5
IF chessboard$(I, J) = "wknight" THEN positionScore = positionScore + 3
IF chessboard$(I, J) = "wbishop" THEN positionScore = positionScore + 3
IF chessboard$(I, J) = "wqueen" THEN positionScore = positionScore + 9
IF chessboard$(I, J) = "wking" THEN positionScore = positionScore + 100

IF chessboard$(I, J) = "bpawn" THEN positionScore = positionScore - 1
IF chessboard$(I, J) = "brook" THEN positionScore = positionScore - 5
IF chessboard$(I, J) = "bknight" THEN positionScore = positionScore - 3
IF chessboard$(I, J) = "bbishop" THEN positionScore = positionScore - 3
IF chessboard$(I, J) = "bqueen" THEN positionScore = positionScore - 9
IF chessboard$(I, J) = "bking" THEN positionScore = positionScore - 100

    NEXT J
NEXT I

END SUB

But material is not everything.

For example in the initial position all moves seem to result in the same material score, however it is known that in the chess opening the good player always moves hies pieces near the center of the chess board, avoid unnecessary movements of the king and the queen and avoids to move the same piece twice.

EXERCISE: Try to improve the countScore SUB to cater for the above. You might need to also introduce a new variable which will count the number of moves we are in the game, so that the computer knows if we are at the opening, the middle of the final stage of the game.

Second improvement: Apply the MiniMax algorithm

Improving the CountScore SUB does not solve our problems.

The thinking mechanism of the program we have desribed is inefficient. One could say that it is inherently flawed.

The program searches for the best score at the end of 3 half-moves, but does not cater at all for the fact that the human opponent moves (at move depth 2) will not be the ones which maximize the score for the computer, but the ones maximizing the score for the human opponent.

In other words: The variants (set of moves) which include completely stupid human opponent moves end up in high scores in favor of the computer and that is why, those variants will at the end be chosen.

But in real life the human opponent will never play his worst moves, but quite the opposite: He will play his best moves so as to win the computer!

The following example will better illustrate the problem.

Imagine we are at the following position…

Important note: The Huo Chess program was developed with simple text-like ‘graphics’. There is also a graphics-version based on Deep Basic chess program (by Thomas McBurney), which you can also download.

An initial version of Huo Chess which simply thought in terms of the best score at the end of 3-half-moves, would play… Qf7+ in this position.

But this is a bad move! Why does it play that?

Simple.

The computer assumes that at the next move human will play something stupid and then it will be able to capture the king of the opponent. The set of moves “1. Qf7+ [something stupid] 2. Qxe8” results in the best (highest) score for the computer, so this move is selected.

The algorithm did not even think that human after Qf7+ will simply play KxQf7 and take the queen, simply because this move results in low score for the computer.

But how do you take into account the best moves for the human opponent (MAXimize value) and at the same time the worst possible variants for the computer (MINImize value)? In other words, at the end, how can the computer play its best move taking into account the worst scenario, which we will have only if the human opponent plays his best move?

EXERCISE: Try to think of the above on your own, WITHOUT reading online about the MiniMax algorithm. First of all – who knows? – you might think of something better! Secondly, one only masters knowledge when he has tried on his own and failed to acquire it. Having things ready for you simply does not lead to wisdom.

The solution to the above problem is the MinMax algorithm. The current version of Huo Chess utilizes it, so you can read there how it works. However note that you can never learn anything by simply copying the program of someone else. Unless you write the program on your own, make mistakes, spend countless nights and days pondering upon them, you will never truly develop anything.

In the MinMax algorithm, we start from the lower level nodes and go up to the beginning of the tree, like in the schema that follows:

MinMax algorithm [Source: Wikipedia]

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 half-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. (source)

In simpler words: It is not enough to calculate the best end-score of a node! Because this might be the result of a combination of good computer moves and bad human moves. The human will not make stupid moves (or at least this will have to be our assumption). So in the level that the computer plays, we must maximize the score (the computer makes the best possible move), but in the levels the human opponent plays we must minimize the score of the computer (i.e. the human plays the best move for him, so the worst move for the computer).

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.

Make sure you check the relevant Huo Chess C# tutorials or the page in Codeproject which refer in more depth to the algorithm (which stays the same regardless of the programming language you use of course).

More updates coming soon!

Download Source Code

This section contains the source code of the Huo Chess QBasic application. Make sure to check here frequently for the latest updates.

Huo Chess source

The Huo Chess source code can be found below. Copy and paste the code in your QBasic interpreter/ compiler to see it and compile it.

One can also download a version with more elaborate graphics for the chessboard, where I have re-used the graphics from the Deep Chess program (by Thomas McBurney). Note that all the code is the same as the Huo Chess above, only the graphics are added – so if you need to study the engine the Huo Chess edition without these more elaborate graphics will perfectly fit your needs.

Important Note: For it to work, copy the PIECES.EGA file you will find in the Deep Chess site to the same folder as your program (this file contains the images of the pieces).

For historical purposes I have added previous versions of the code. You do not have to worry about those. Simply choose the latest one. Make sure you keep on coming to this page for updates of the code.

Opening Book Editor

The latest versions (v0.6) of the code have an opening book functionality. In order to generate the files of the opening book you can use the Opening Book Editor found below.

Simply run the program, play the moves you want to store in the opening book and they will all be stored in separate txt files. These files must then be places in the same folder as the Huo Chess executable for the latter to utilize them.

As with Huo Chess, make sure you visit this page again to check for any updates or improvements in the code!

Other Huo Chess resources

Other Huo Chess related resources are listed in this section.

Feel free to write for any comments or suggestions for the program.

Until we meet again…

Happy coding!

How to code a chess program in one day. (C# and Java examples)

Advertisements

Introduction

Coding is easy.

Today there are a lot of people learning how to do it.

Why not you?

And you know what is the most difficult step in learning how to code?

TO START LEARNING.

You know there is an old Buddhist saying claiming that “When the student wants, the teacher appears”. So the question is not whether there are tutorials out there to teach you. There are a lot. Here or elsewhere, you can easily find articles showing how to code.

The question is: Are you willing enough?

(And yes, Harmonia Philosophica is mainly a philosophy portal, so feel free to read about philosophy while trying to debug your first chess program)

For this ultra quick training I will use a Java edition of my Huo Chess program. This edition lacks basic functionalities like deep searching, but it can however play chess according to the rules and choose the best move at the current position based on which move earns the most material.

Places to download Huo Chess (source code and executable)

License: You can reuse the code you see here in any way you want, as long as you mention the author and the place where you read it first!

RELATED TUTORIALS:How to program a chess program for dummies” series will give you a more detailed description of how to create your chess program! Check also the Programming for kids: Developing a chess program in BASIC and the Programming a chess application in QBasic (QB64) tutorials for developing a chess program in BASIC programming language. Check out also the “How to develop an adventure game ultra-fast tutorial” tutorial! You could also find interesting the HUO Writer: A simple AI writer with basic Neural Network capabilities (QB64) article.

千里之行,始於足下

(A journey of a thousand miles begins with a single step)

~ Lao Tzu, Tao Te Ching

Step 1: Get a programming interface

This tutorial will show you how to code a demo chess program in one day, even without any prior knowledge of programming. All you need is a programming interface to write and compile (i.e. make an executable program out of your code) the code that you will write. These are also known as Programming IDEs (Integrated Development Interfaces). This could be the Microsoft Visual Studio (the Express edition of which can be downloaded for free) for C# or any Java compiling studio available out there (like NetBeans for example, which again can be downloaded for free).

The tutorial will not cover the details on how to use these programming interfaces. But this is not something hard to learn anyway. Just go to the web (or the page of the tool itself) and you will gain an understanding on how to write a small console program (this is what we are going to do here) in less than an hour. When I refer to a console program I mean a program which does not have graphics but only displays text. We will start with building such a program since writing code for graphics will surely need an additional effort to learn how to do it. And it will be easy to later on add graphics to your program, once you have the AI logic of the chess engine up and ready, don’t you think?

Open the IDE and select to create a new project…
Select to create a simple application…
Your program is created. All you have to do is add the code…

Tools to use for coding your program

  • Microsoft Visual Studio (free edition)
  • Java NetBeans

After you download the IDE, install it in your computer and go to the option New Project. Select to create a simple C# console application (in Visual Studio) or a simple Java program (in NetBeans). Click Create and there you are. You have the shell in which you will add your chess program code!

Step 2: Design the chess program structure

Let’s go into the chess program now.

But wait!

Don’t we need to learn the programming language first?

The answer is simple: NO!

You will learn them as you go.

This is how I (and many others) learned programming in the first place. I opened my Commodore computer and started typing my first program by copying the code from the manual. After I typed it in and spent time to get it right (even copying can be difficult, especially if you are a rookie) I typed RUN and I had my first game! Forget the long chapters of books trying to teach you – after reading 100 pages – how to just print “Hello world” on a screen. Programming is for people who like experimenting and are not afraid to simply start trying things on their machine.

So just go ahead!

You will read here about the basic structure needed for the program, and then you will see the commands required to code that structure into a C# or Java program. The commands are fairly simple and you will understand what they do as you write the program. Do you really need a programming language manual to understand what an “if” command does anyway?

The main structure of the program is depicted in the following schema.

Fairly simple isn’t it?

The story goes like this…

  1. You get input from the user for his move. [EnterMove function]
  2. You check the legality and the validity of the move entered [ElegxosNomimotitas and ElegxosOrthotitas functions, which also utilize the CheckForWhiteCheck and CheckForBlackCheck functions to check if there is a check in the position]
  3. If the move is legal and valid, then do the move. [call drawPosition function to redraw the chessboard; note that the Java edition of the program only prints the chessboard in text]
    • Exercise for you: Add graphics to the application. (use the C# edition ot get some insight on how you could do that)
  4. Call the function which makes the computer think. [ComputerMove function]
  5. Scan the chessboard to find all the pieces of the computer. In the sample code provided for Java, this means that it scans for all the black pieces since the program is made only for the computer to play with black.
    • Exercise for you: Add the ability for the program to play with white as well)
  6. For each piece of the computer, check all possible moves to all possible squares of the chessboard.
  7. If you find a valid move (by invoking the ElegxosNomimotitas and ElegxosOrthotitas functions) then do the move and count the score of the position. [CountScore function: This is one of the most central functions of the program; changing it makes the computer play differently according to the values you assign to pieces or to elements of the chessboard like empty ranks, concentration of the pieces at the center et cetera]
  8. If the score of the move is better than the so far better score, then store this position as the best one. (Note: The program stores the first position analyzed as ‘best’ anyway, so that there is a starting point for the best score)
    • Exercise for you: Change the values in the CountScore function to improve the playing abilities of the computer)
  9. Do the best move found and redraw the chessboard.
  10. Wait for next user input. [call EnterMove function again]

The Java edition of the program does not think in more depth. It just finds the move which earns the more material and makes it. This is not chess isn’t it? Well actually it is. The basis for a good chess program. All you have to do is improve it.

Look at the C# version of “Huo Chess” (search the web for it, there are many repositories where I have uploaded the code, including MSDN Library, CodePlex and Codeproject) to gain a small insight on how the chess program can search into more depth.

Exercise for you: Make the Java edition of the program to think in more depths, by adding more “ComputerMove”-like functions to analyze the next potential moves for the human and the computer. Be careful how you pass over the chessboard between these functions. (yes, Google will be your best friend)

Related resources for C# Huo Chess edition

Step 3 : Write the code

This last section contains the source code of the chess program in Java.

As mentioned above, look for “C# Huo Chess” in the web (See the Recourse listed above) to see the full source code of that Huo Chess edition. This code is also heavily commented to make it easy to read and re-use, while the names of the functions are the same as in the Java edition of the program.

Look also at the “How to program a chess program for dummies” series here in Harmonia Philosophica, to get some more details on the Huo Chess program. (the tools used in those articles are a bit outdated, but yet the logic is still the same)

Paste that code into the main java file in your NetBeans project and compile it.

Execute your program and enjoy your new chess game.

Epilogue

So there it is. Depending on your copy-paste and reading comprehension skills, you now have a working chess program on your hands and some knowledge on how it could be improved. Everything is up to you now.

Happy coding!

And don’t forget: Keep experimenting!

The worst thing that could happen?

To just ruin your computer…

How to Develop a Chess Program for Dummies

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.

Advertisements

Other Related articles

Huo Chess – The program we will code…

Huo Chess is one of the smallest open source chess applications. It is an application that I have personally developed and distribute as fully open source via many channels in the Internet. One can download it for free from the MSDN Code Gallery, Codeplex Huo Chess site or its Codeproject page. In the series I will analyze how one can program the computer to play chess. The final “deliverable” will be the full Huo Chess program as it can be found in the Internet.

Note: An intermediate/ advanced programmer can go directly to the above links and download the Huo Chess source code so as to study it directly. Please contact me for any questions on the code or the algorithm either via email (skakos@hotmail.com) or via comments in this article (Knol). However, even though the source code of my chess is heavily commented, starting looking directly at the full program source code without first reading the lessons I have posted here at Google Knol is not advised for beginner programmers.

Method of teaching

The method I will use for teaching you how to program is by example. The “try to do something and see what happens” may sound like a bad method, but it is actually the best when it comes to computers programming. As long as you have kept a backup of all your valuable files, you must and should try anything with programming if you really want to learn! That is why I will show practical steps you need to follow and I will guide you through every stage of the programming process, without first giving a 100-page lecture on the theory or the basic principles of programming. You will be taught the theory you need to know as we progress through the steps of building the chess game. That method is the method actually used by programmers in the 1980’s. We used to experiment with new things, try new techniques and learn from our mistakes. There is no better way of learning than experimenting and doing mistakes. You will never learn from something you did right in the first place!

The language of choice is C# and the tool we are going to use the Microsoft Visual Studio. However please note that I have created and distributed versions of the “Huo Chess” also in C++ and in Visual Basic. Feel free to search for the free source code in the Internet (I am now trying to create a Commodore version).

Getting started

The first thing you need, is the tool with which you will program. You can download the Microsoft Visual Studio – Express Edition from the respective Microsoft Visual Studio Express Edition site. The “Express” editions of MS Visual Studio are completely free to download and they include all the programming tools and features a novice, intermediate or even an advanced programmer needs. After you download it, installing it is what is keeping you from programming your first game application!

Installing Visual Studio

After you have downloaded the MS Visual Studio – Express Edition, you will have to install it. Installing the Visual Studio is no more complex than the installation of any other program.

You just double-click the file you downloaded and the installation will automatically begin. Normally, the setup will install the Microsoft .NET Framework if it isn’t already installed in your computer (the .NET Framework is required for the Visual Studio to operate – Huo Chess requires .NET Framework 2.0 or above to work) and the Visual Studio. An icon with the characteristic sign of the Visual Studio will appear in your desktop.

Using Visual Studio

Double-click the icon of the Microsoft Visual Studio to begin programming. The Integrated Development Environment (IDE) of the Visual Studio will appear and you are now ready to make your application.

Create a new project

First you need to create a new project. Go to the menu and click File > New > Project.

From there you must choose the language in which you will develop your program. We will write our chess in C# so we must select Visual C# > Windows > Console Application (later we will show how we can also program the same game in C++ or other languages). To create a chess program with a user interface you would need to choose to create a new Windows Forms application. (that would be easy after you have created the code to play chess)

A console application is an application with no graphics. We will start developing our chess game Artificial Intelligence engine as a console application in the beginning and afterwards, when the computer can think and play chess, we will add graphics (that will be the final step in this programming tutorial series). Name the new project “Huo Chess tutorial” and press OK. Visual Studio will do its work and create all the initial things required for you to start developing.

The project is by default saved in a folder with the name you specified, that resides in the My Documents/Visual Studio folder.

Start developing

After you have created your project, you can start programming. The window will initially look like this.

That is a good point to say some things about programming. Programming in one of the modern languages of today entails using three elements:

  • Variables
  • Functions
  • Classes

All programming uses these three elements and if you master them properly then you can do everything. I will try to explain these elements in summary in the lines below.

Variables

The variables used in a program are the elements which store values, that are used in the program. Variables come in many types depending on the type of data they will be used for. For example you can declare an integer variable to store integer values, or a float variable to store numbers with a decimal segment, or a String variable to store text.

The first variable we will use in our program in the variable which will store the color of the human player in the game. In particular, after the human player starts our game he/she should choose the colour with which he (excuse me ladies for using the “he” instead of the “he/she”, but I am a man so I am used to it) will play.

We will declare our variable in the class program by entering the code public static String m_PlayerColor; as seen in the following figure.

Some clarifications are needed here: Every command in C# must end with semicolon (;). Secondly, we declared the variable as public which in short means that it will be visible from every part of our program (the opposite, private variables can be accessed only inside the function/class we declare them in). The static keyword should not concern you at the time (it actually means that only one instance of the variable can be created as the program executes, but we will have more on that later on the tutorial series).

You can then define the value of that variable by hard-coding it in your program. Try to enter m_PlayerColor = “Black”; in the Main function of your program and then print it to screen with the command Console.WriteLine(m_PlayerColor); as seen in the next figure (in fact I have added a Writeline command more as you can see).

Compile the program

The first thing you must do when programming a change in your program is to save your work. Select File > Save All… to save all the changes you made. After you have saved the program, you may want to execute it in order to see what you have done. Before a program is executed, it must first be compiled. Compiling a program means converting the programming language file you just saved to a form readable by the machine (i.e. machine language, which is comprised of 010101’s). Select Build -> Build solution to do that as illustrated in the following figure. If you have followed the steps above, no errors will exist and the compiler will notify you that the solution was successfully built.

Then select Debug > Start without debugging (or simply press Ctrl + F5) to start/ execute your program. The following will show.

You have just created your first program which includes declaring a variable and printing it to screen.

Note about the graphics

The graphics of the chessboard will be added at the final stage of the project. Right now we will focus on developing the chess engine algorithm which is the most difficult part. That is why we started by developing a console application (i.e. an application without graphics). We will worry about the graphics after we have created a fully functional chess AI engine.

Let us now say some things more about functions and classes as promised.

Functions

Functions are code segments which require some input to perform a specific action and produce a specific result. For example you can have a function that adds two numbers called Add_numbers. The code for that function will look something like that (you do not have to code anything in your Huo Chess project now, this is just for theory education purposes):

int Add_numbers(int Number1, int Number2)

int Add_numbers(int Number1, int Number2)

{
      int Result;
      Result = Number1 + Number2;
      return Result;
} 

The code is simple and intuitive, isn’t it? The “int” in the beginning declares that this function will return an integer number as the result of the process it implements. The two integer variables in parenthesis declare the input required for the function to work. That is why when you need to call that function you should call it in a way like the one listed below:

int myAddResult;
myAddResult = Add_numbers(5, 6); 

The above code calls the function Add_numbers by giving it the input of number 5 and 6. The result will be the function to return the value of 11 (= 5 + 6) which we have allocated to variable myAddResult.

Object Oriented Programming

Functions and variables can be used in creating objects. These objects are called classes and are the cornerstone of the Object Oriented Programming (OOP) you may have heard many times before.

Classes

But how do you create and use objects? First, you have to declare the class of the object. For example, if you want to create an object called ‘Blue Calculator’, you must first create and declare a class of objects called Calculator. Define the parameters of that class: the variables it will be using (i.e. the color of the calculator, the numbers which the user will enter in the calculator by pressing the buttons + the result that the calculator will print on its screen) and the methods (or functions) that the calculator will utilize in order to reach the result (i.e. functions for adding numbers, subtracting number etc).

The definition of that class will have the following scheme (independent of what the programming language you use may be):

class Calculator

 class Calculator
          {
               // Variables
               Number_type number1;
               Number_type number2;
               Number_type Result;
               Color_Type Calculator_Color;
               // Methods
               Function Add(number1, number2)
               {
                    Print “The result is:”, (number1 + number2);
               }
               Function Sutract(number1, number2)
               {
                    Print “The result is:”, (number1 – number2);
               }
          } // End of class definition 

The two slash (//) text are comments. Whatever you write after these slashes is not taken into account by the compiler. It is considered best practice to write comments in your code.

After you have properly declared your class of objects, you can create as many objects of that class you like and use them in your program. For example you can create a new blue color calculator by writing a command that could look something like that:

Calculator my_calculator = new Calculator(Blue);

You can then use the member-variables and member-functions of the calculator with commands like:

Integer no1 = 2;
Integer no2 = 7;
Print “Result = ”, my_calculator(Add(no1, no2));
// this should print ‘9’ in the screen
my_calculator.number1 = 20;
Print “Result = ”, my_calculator(Add(my_calculator.number1, no2));          // this should print ‘27’ in the screen

The specific commands again depend on the programming language you use, but you get the meaning. It is all too easy: Declare class => Create new object of that class => Manipulate / define parameters of the new object => Use member functions of that object to generate the result they are designed to generate.

It may be difficult for you to grasp, but ALL programming in ANY language (C++, C#, Visual Basic, Java etc) are based on that logic. What is more, the languages themselves have some ready-made classes that you can use to develop your programs! For example, Visual C++ and C# in the Microsoft Visual Studio has a stored class for Buttons. To add a button to your application, you just write:

Button my_button = new Button();
my_button.color = Blue; 

You don’t have to reinvent the wheel! That simple (and I think you understand what the second command does, without telling you…)! I keep repeating myself, in order for you to stop fearing the unknown realm of programming and just…start programming! The ready-made classes (or even simple functions) are usually stored in packets called ‘libraries’. Add the library you want in your program and them just use any class/ function it contains.

Classes you already use without knowing it

You may think that all the above have nothing to do with the code you just wrote. But you would be wrong. Your program, even at this initial stage, uses many classes without you knowing it! Actually Microsoft has developed some classes that facilitate programming for Windows and you are using these classes with the “using” statements in the beginning of your code. You do not have to know more details about that now, just be aware that you can program your chess because someone else have already developed and implemented a great number of classes in order to help you do that.

A good example of classes you already use if the Console command you wrote in order to print the player’s color. Remember that the command looked something like that:

Console.WriteLine(m_PlayerColor);

The above code actually uses the class Console and calls one of its member-functions: the WriteLine function (that is why the dot is required: to call members of classes as we said above). That functions requires input: the text that you want to display. That is what we write in the parenthesis!

Intellisense

The Visual Studio has embedded features that help you know which are the members of the various classes and how to use them. So when you write “Console” and then enter a dot, the Intellisense of Visual Studio produces a list with all available member variables and functions of that class. You will find yourself more comfortable with the use of Visual Studio and C# only after you have tried to use many of the functions appearing in that list on your own and see what happens. Remember, experimenting and doing mistakes is the only way to learn!

Get user input

In a similar way to printing something to the screen, you can get user input. You will find that very useful when you want the user to enter his/her move for the chess game. In this point, we will require the user to enter his color of choice by using a function similar to Writeline: the Readline. See the figure below on how that can be accomplished.

The code is simple and straightforward. You print instructions to the screen and then read the input from the user. When the user presses “Enter”, the value he entered is allocated to the m_PlayerColor variable which is then printed on the screen.

Next lesson

In the next lesson we will learn how to instantiate the chess board, build the Artificial Intelligence engine of the program and the program’s user interface structure. Until then, try to enter the following code in the program:

 if (m_PlayerColor == “Black”)
               Console.WriteLine(“My first move is: e2 -> e4”);
          else
               Console.WriteLine(“Please enter your first move!”);

Save, compile and run the program. You will see that if the player enters “Black” the program “plays” a first move! Well, actually this is not the way we will use to develop our AI (using “if” statements is not the way to make the machine think), but what I want to note and emphasize here is the simplicity of programming in general. All you need is will to learn!!!

What we have accomplished

In this first lesson, we have accomplished many things which are listed below:

  • Created our first project in MS Visual Studio.
  • Learned how to save, compile and execute the project via Visual Studio.
  • Learned how to print text on the screen.
  • Learned how to use variables and read user input from the user.
  • Gave a look at our first code structure command (“if” command).
  • Learned about functions and classes.
  • Understood the basics of Object Oriented Programming.

Until the next time, happy coding and experimenting!

How to Develop a Chess Series updates

  • Update 2009-06-04: Due to other obligations the next lesson is not going to be published as soon as I expected to. However I am in the process of writting it and it WILL be published as soon as I can.
  • Update 2009-07-30: The new lesson of the series is now published
  • 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.

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.

Advertisements

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)

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

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

How to Develop a Chess Program for Dummies 2

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.

Advertisements

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.

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.