Interested in chess programming? You are interested in philosophy too! What is thinking? Can AI be conscious? What does it mean to do something? Can the AI understand that it does play chess? Explore the AI related articles in Harmonia Philosophica and understand why you are already a philosopher!
Hello again!
After having published various tutorials on basic chess programming, it is time to move on to more advanced concepts.
Programming for kids – How to program a chess program in BASIC
Existing chess tutorials
- How to Develop a Chess program for Beginners Series
- Programming for kids: Developing a chess program in BASIC
- Programming a chess application in QBasic (QB64)
Huo Chess resources
- Huo Chess (Main page at Harmonia Philosophica)
- Huo chess @ Codeproject
This article 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 IFWith 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).
You can download the program below.
Download Source Code
Simply copy and paste the code in your QBasic editor and try it out!
One can also download a graphics version, where I have added the graphics engine by Deep Chess (by Thomas McBurney).
Important: 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).
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!
Advanced concepts: Improving the computer thinking
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.
However it does not make good moves!
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 SUBBut 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.
Make sure to check the latest version of Huo Chess uploaded, to see how qualitative criteria were added in the countScore SUB!
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
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.
Make sure you check the relevant Huo Chess C# tutorials 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!
Until next time…
Happy coding!
