CHESS PROGRAMMING: Evaluating Material – Episode 1: Bishop vs. Knight

Advertisements
Photo by Pixabay from Pexels

Small chess programming lesson summary

Overview: This is a short chess programming lesson, part of the ‘How to develop a chess program’ tutorials series in Harmonia Philosophica for total beginners. The goal of this lesson is to discuss the very basics of position evaluation.

Tutorials on how to develop a chess program in Harmonia Philosophica include:

Supporting material: Please use the Huo Chess source code to support you in your reading. Huo Chess is one of the most known micro-chess open source programs for educational purposes. Start by the major page of Huo Chess here to view the code.

Evaluating Material – Episode 1: Bishop vs. Knight

One of the most important tasks in chess programming is to properly and cleverly evaluate the positions the computer thinks of. This evaluation consists of two aspects: Material and Positional/ Strategic aspects.

In this article we will show the most basic ideas for evaluating the position from a material aspect.

First thing is to assign values to pieces. The standard values look something like…

  • Queen: 9 points
  • Rook: 5 points
  • Bishop: 3 points
  • Knight: 3 points
  • Pawn: 1 point

Calculating the total score of a position based only on material is pretty straightforward: You have a loop that iterates through all squares of the chessboard and simply adds the value of each piece to the total score of the position. The evaluation is the number you come up with after you have added the values of all the pieces on the board (the terms ‘evaluation’ and ‘score’ and sometimes used interchangeably to refer to that total sum of the values of all pieces).

Another important thing to keep in mind is that the values of black pieces have the same values but with a negative sign. In that way, if the total score of a position is positive then white is winning material, while if the total value of the position is negative then black is winning. So by simply checking the sign of the total position evaluation your program can know if the position is winning for the colour of the computer – that could come in handy in chess programming.

View the CountScore function of Huo Chess to see a simple way to do that. Note though that the Huo Chess also utilizes some other criteria as well to evaluate the position – which we will discussed in next episodes.

Even though such a simple calculation of the position’s score will give you an idea of the material aspect of the board, even that is not so straightforward as it seems. The material is indeed easy to calculate, but the truth is it can never be viewed completely independently from the positional aspect.

For example, a bishop could have the same value as a knight, however when the position has locked pawn structures as below, then the knights become invaluable while the bishops useless…

Knights being better than bishops…

Another last thing to keep in mind for now is that tweaking the values of the pieces in your evaluation function could alter the playing style of the chess program you build. For example, if you increase the value of the queens, let’s say from 9 to 9.5, then your program will more aggressively hunt down the queen of the human opponent and will also more harshly defend its own queen from attacks.

Experimenting with these values is a nice way to gain a first hand understanding on how your program behaves. If you have not yet built your own program, simply use Huo Chess code to change the CountScore function.

Remember: Coding is all about experiments!

(after you have a good backup of your working code…)

Until next time…

Keep coding!

Huo Chess (C# micro chess)

Advertisements
Huo Chess DV – GUI edition

Latest versions

  • In .NET Framework: Huo Chess 0.9922
  • In .NET: Huo Chess DV [2021-11-10]

Huo Chess News

  • 2021-11-10: Ported Huo Chess in Visual Studio 2022 (C# .NET 6.0) to create the latest Huo Chess DV version. The equivalent version in .NET Framework is the v0.9922 version.
  • 2021-04-07: Re-optimization of CountScore (evaluation of position) function for endgames regarding the pawns evaluation.
  • 2021-04-03: Optimized the CountScore (evaluation of position) function for endgames. Huo Chess v0.9921 beat bot at Chess.com with 1100 ELO rating.
  • 2021-03-20: Added the castling capability also for the computer (up to now, the program only recognize and allowed the castling move for the human opponent).
  • 2021-03-14: Thinking in level 4 and 5 is conducted only if the moves entail the capturing of a piece. Removed redundant code. Improved CountScore function with positional elements for the ending of the game. Introduced the elements of mate and stalemate in the thinking process.
  • 2021-01-06: Fixed initialization of nodes 3 and 4.
  • 2020-09-03: Minor updates.
  • 2020-08-10: Updated the countScore function that evaluates positions to include also qualitative criteria for the position.
  • 2020-08-03: Minor updates to the v0.992 Developers Edition. The trimming rules have been updated to enable deeper thinking.
  • 2019-02-21: The v0.992 has received initial operational capability. The algorithm now works for thinking depth of 5 half-moves, with thinking tree trimming applied.
  • 2019-02-12: Huo Chess version 0.991 published. Now the algorithm performs as planned. Thinking depth limited to 3 half-moves.

Huo Chess Overview

The Huo Chess is one of the smallest open source chess programs in C# (the latest .NET console version is only 159 KB is size, even though it utilizes the latest .NET Platform; while the latest version in .NET Framework is only 44 KB in size). It has heavily commented source code so that it can be used for teaching purposes on how to develop a chess program (or a program in general). It can be easily reused in other applications, e.g. to use it as a chess engine for a robot playing chess (see here).

Feel free to re-use it as you see fit (including changing it or selling it), as long as the source is cited properly. The goal is to spread the knowledge on the basics of chess programming, so sharing is important. Feel free also to contribute to the project, by contacting Harmonia Philosophica with ideas or code that can be used.

Huo Chess sites

You can download the latest files via the relative sites:

Alternatively you can download it below.

Important Notes: The latest version of Huo Chess that is still in development is available only in this site and in GitHub repository. The CodeProject and the MSDN sites still have the v0.992 version.

Huo Chess-based tutorials

Over the years I have written several tutorials on how to develop a chess program based on the Huo Chess.

Tutorials on how to develop a chess program include:

LATEST VERSIONS

DV Version highlights

The latest Huo Chess DV (Delta Version) editions are built in the latest Visual Studio 2022 and use the latest C# .NET 6.0 platform. Remember: along with having the goal of being the smallest chess program for educational purposes, the goal is also to constantly follow all developments in the programming landscape so as to stay relevant!

However being modern and flexible has a price. The new platform had a significant impact on the size of the Huo Chess application: Even after all optimizations, the console edition is now 159 KB (from 44 KB that it used to be) and the GUI edition is now 239 KB (from 96 KB that it used to be). Hopefully the application trimming in the new .NET platform will be improved in the future so these numbers can do down.

Read the Develop a (chess) program in Visual Studio 2022 (C# NET 6.0) article to see how the Huo Chess program was ported into Visual Studio 2022 and .NET 6.0, along with some details on the publishing and trimming settings of the application.

Version 0.9922 highlights

The version 0.9922 is the latest .NET Framework version, i.e. the equivalent to the latest DV Version in .NET. This version has only minor updates regarding logs when compared to v0.9921.

OLDER VERSIONS

Version 0.9921 highlights

The new version of Huo Chess (v0.9921) is even smaller in size than all the previous ones and yet much more capable. This was made possible by optimizing code and removing redundant code as well. The official edition with Windows Forms user interface is 77 KB in size (as opposed to 78 KB of the previous version), the Console application with a chessboard User Interface (UI) edition is 45 KB (as opposed to the 46 KB of version v0.992) and the Console application with text-based chessboard UI edition is 44 KB in size (whereas the previous version was 46 KB in size).

The new version has an updated evaluation function (CountScore) for the endgame, it has improved code for the castling move and also has an optimized deep thinking mechanism.

Huo Chess v0.9921 editions

  • Huo Chess 0.9921 with GUI: This version is the main version with a Windows Forms chessboard User Interface.
  • Huo Chess 0.9921 cs: Console application (text only).
  • Huo Chess 0.9921 cs with graphics: Console application, with minimum text-graphics to depict the chessboard.
  • Huo Chess 0.9921 Developers version: Full developers version with Windows Forms chessboard and logs to show the thinking mechanism. (Attention: Remember to delete the logs when needed, since their size can increase significantly)

Version 0.992 highlights

The v0.992 version of Huo Chess is small in size (as all the previous ones) and much more capable. The official edition with Windows Forms user interface is 78 KB in size, the Console application with a chessboard User Interface (UI) edition is 46 KB and the Console application with text-based chessboard UI edition is 46 KB in size.

Issues with the MiniMax thinking algorithm are fixed and now the computer makes logical moves in every circumstance (at least for the depth of 5 half-moves in which it thinks). Capability of thinking at depth of more half-moves will be added in the future. The program also features an Opening book capability (must have positions in the “Opening Book” folder to use it).

Additional to the above, a Developers Edition has been created, which includes analytic logs of the thinking mechanism for debugging (for teaching purposes). The logs can be easily activated or deactivated. This edition also takes a small step towards showing the variant which the computer thinks to the user interface.

The Opening Book editor is distributed separately. Along with the editor, a library of some sample opening book positions is also included in the distribution files.

Huo Chess editions

There are various Huo Chess editions, each one with slightly different User Interface, plus one for developing purposes.

For the latest Huo Chess DV (Delta Version) there are currently two editions:

  • Huo Chess DV console: The console edition supporting opening functionality and up to 5-ply thinking. Currently using C# .NET 6.0 and standing at 159 KB.
  • Huo Chess DV: The GUI edition supporting opening functionality and up to 5-ply thinking. It also contains logs that can be activated to analyze and debug the thinking algorithm. Currently using C# .NET 6.0 and standing at 239 KB.

Both editions have heavily commented code to allow for using the open source chess engine for educational purposes.

Future versions candidate improvements

There is already a list of potential improvements for the next version of Huo Chess, that can be found below:

  • Add castling capability for the computer to also be able to castle. Also castling should be embedded in the CountScore function.
  • Reduce size by improving ‘peripheral’ functions (like CheckForBlackMate, ElegxosNomimotitas et cetera).
  • Increase efficiency of MiniMax algorithm, by taking into account the average score of each branch. (code already in place, but commented out)
  • Add neural network capability: This will be achieved at a very primitive level by having key points of the MiniMax algorithm (the inequalities at each node level analysis in ComputerMove) being dependent of values stored in external configuration files and by updating those files every time a game is played (increase ‘score’ if the game is a win, decrease if it resulted in defeat). This is still in preliminary stage, but I will try to have a relative Developer edition ready in the next version (without compromising the size).
  • Improve CountScore function, to take into account the position of the chessboard, whether you move the same piece twice in the opening et cetera.

Huo Chess DV distribution files (latest .NET version)

The Huo Chess DV version is the version developed in Visual Studio 2022 and utilizing C# .NET 6.0.

These versions are expected to be updated frequently as the .NET Platform is also updated. Needless to say that these editions render the v0.9921 version the last version utilizing the .NET Framework.

Huo Chess v0.9922 distribution files (latest .NET Framework version)

The version 0.9922 of Huo Chess is the latest version available in .NET Framework. It is the equivalent of the DV version but in the .NET Framework.

Huo Chess v0.9921 distribution files

The version 0.9921 of Huo Chess is currently in development. Take a look at the progress of the project exclusively here at Harmonia Philosophica or directly in the GitHub repository. The code is updated frequently.

HUO CHESS 0.9921 with GUI – Developers edition 2021-04-03 (GitHub)

Note that this is a draft version which is still under development. Also please remember to delete the logs after some moves, or disable them completely if you want to play a full game. The size of the logs of the Developers edition can increase significantly after only some moves.

Di mi se mai fu fatta alcuna cosa
(Tell me if anything was ever done to completion)

~ Leonardo da Vinci

Huo Chess v0.992 distribution files

The version 0.992 of Huo Chess is in development. Take a look at the progress of the project exclusively here at Harmonia Philosophica! The code is updated frequently.

All the files of the v0.992 can be found below. Make sure you download the latest one. The previous versions are kept for historical reference purposes. Also at the end feel free to download the latest v0.9921 version that is still in development

This version is the officially stable version that can also be found in the GitHub repository and the official sites (like CodeProject) which host the Huo Chess code.

Huo Chess v0.991 distribution files

Distribution files for the Huo Chess v0.991 version include the following:

  • Huo Chess 0.992 with GUI
  • Huo Chess 0.992 cs
  • Huo Chess 0.992 cs with graphics
  • Huo Chess 0.992 Developers version
  • Opening Book editor
  • Opening Book

Feel free to contact me for anything regarding the code or the project in general. Remember that the goal is not only to create the smallest chess program but also to create a good basis for educational purposes.

Huo Chess Opening Editor

From the beginning of the Huo Chess project (well, almost from the beginning), an opening functionality was developed. The opening book of Huo Chess is edited with the help of a dedicated tool: the Huo Chess Opening Editor. Simply run the tool, play the moves by selecting “Opening mode” and all the moves will be stored as suggested moves for the computer in its opening book.

There is a C++ (cpp) and a C# (cs) version of the tool, which can be both downloaded below.

The tools generate txt files which hold the positions of the opening book, along with the suggested moves for each position. Note that there must exist a ‘Huo Chess Opening Book‘ folder in the same folder as the application for the latter to store the opening book files.

Make sure you keep checking back in this page for more updates.

Huo Chess Java edition

The Java edition of Huo Chess is also developed in parallel with the C# versions. Currently, only the core engine with text interface with the user is developed in Java. Anyone willing to provide a GUI is more than welcome to do so. (I will try to do that as soon as I have time)

This code can be the basis for an Android Huo Chess application. I am currently working with Visual Studio and Xamarin framework to build it.

Huo Chess QBasic edition

The Huo Chess has been written in QBasic as well. Yes, you read it right! The old friend from the past, BASIC, is still alive and kicking!

You can find the code below. Along with the games’ source code, an opening editor is also distributed. Both work in the same way the C# edition works.

Feel free to write to me for any comments or suggestions.

Instead of epilogue…

The ultimate goal is to go back to where I begun programming and fulfill my child dream: to create a chess program for Commodore 128. The porting of the current Huo Chess version to QBasic is currently in progress and then the road to porting to Commodore BASIC v7.0 is open…

And remember: Huo Chess was not made to be completed. But exactly the opposite: It is here to remind us all the constant struggle to perfection. A struggle so vain as any other human struggle and yet, a struggle so familiar and lovely.

Huo Chess will constantly be upgraded…

By me… By you… By everyone…

And year by year it will constantly be better and smaller…

Until there is nothing left…

Because at the end, the best chess game I will ever play will be that game I played as a child, with my father, trying to learn how to play…

APPENDIX – Huo Chess games

This appendix contains various games played by Huo Chess over the years.

Game 1: Huo Chess v0.9921 vs. Jimmy bot (600 ELO rated) at Chess.com

Huo Chess v0.992 vs. Jimmy Bot @ Chess.com [2021-03-21]

[Site “Chess.com”]
[Date “2021.03.21”]
[Round “?”]
[White “Huo_Chess”]
[Black “Jimmy”]
[Result “1-0”]
[TimeControl “-“]

1. g4 g5 2. Nc3 d5 3. Bh3 Nc6 4. Nf3 h6 5. d4 Qd6 6. Be3 b6 7. Bd2 Nb4 8. Nb5 Qd7 9. Nxa7 Rxa7 10. Bxb4 Nf6 11. Ba3 Ba6 12. c3 Bc4 13. Ne5 Qb5 14. Bg2 Ra4 15. e3 Qa5 16. b4 Ba6 17. bxa5 Rxa5 18. Bb2 Bg7 19. Qf3 Bb7 20. c4 h5 21. gxh5 Ra7 cxd5 Ra6 23. e4 Bh6 24. Bc1 Ra4 25. Be3 O-O 26. Kd1 Ba6 27. Nc6 Kh7 28. Nxe7 Ra5 29. Qxf6 Bd3 30. Nf5 Kg8 31. Nxh6+ Kh7 32. Bxg5 Raa8 33. Nxf7 Rxf7 34. Qxf7+ Kh8 35. Bf6# 1-0 

The game resulted in Huo Chess easily beating the bot within 35 moves.

Game 2: Huo Chess v0.9921 vs. Jimmy bot (600 ELO rated) at Chess.com

Huo Chess v0.992 vs. Jimmy Bot @ Chess.com [2021-03-22]

[Event “vs Computer”]
[Site “Chess.com”]
[Date “2021.03.22”]
[Round “?”]
[White “Huo_Chess”]
[Black “Jimmy”]
[Result “1-0”]
[TimeControl “-“]

1. g4 g5 2. Nc3 e5 3. e4 Ne7 4. Nf3 f6 5. Bb5 Ng8 6. Ba4 Nh6 7. d4 a6 8. dxe5 c6 9. exf6 Kf7 10. Nxg5+ Kg6 11. Ne6 Rg8 12. Nxd8 d6 13. Bxh6 Kxh6 14. Nf7+ Kg6 15. Nxd6 b5 16. Bb3 Bxd6 17. Bxg8 Bc5 18. Qf3 h6 19. Ne2 Bb6 20. Nc1 Bd8 21. c4 Bxf6 22. cxb5 cxb5 23. e5 Bxg4 24. Qxa8 Bxe5 25. Qe4+ Kf6 26. Qxg4 Ke7 27. Qe6+ Kd8 28. Qxe5 Nd7 29. Qd6 h5 30. Be6 Kc8 31. Qxd7+ Kb8 32. Qe8+ Kc7 33. Qxh5 Kb7 34. Bd5+ Ka7 35. Nb3 Kb8 36. Rd1 Kc7 37. Qg6 a5 38. Nxa5 b4 39. Qg4 Kb6 40. Qxb4+ Ka6 41. Nb3 Ka7 42. Qb7# 1-0

Game 3: Huo Chess v0.9921 vs Sven bot @ Chess.com (1100 ELO rated)

[Event “vs Computer”]
[Site “Chess.com”]
[Date “2021.03.26”]
[Round “?”]
[White “Huo_Chess”]
[Black “Sven”]
[Result “1/2-1/2”]
[TimeControl “-“]

Huo Chess v0.9921 vs Sven (1100) [2021-03-26]
1. g4 g6 2. Nc3 d5 3. Bh3 c6 4. d4 Nf6 5. Be3 h6 6. Bd2 Na6 7. Nf3 Nb8 8. Bf4 Nxg4 9. Rg1 h5 10. e4 Be6 11. exd5 cxd5 12. Ng5 Bh6 13. Nxe6 fxe6 14. Bxb8 Rxb8 15. Rh1 Bg7 16. Rb1 Qb6 17. Qd3 Rh6 18. Qd2 Ra8 19. Na4 Qd6 20. Nc5 b5 21. Nb7 Qa6 22. Nc5 Qd6 23. Nb7 Qa6 24. Nc5 Qxa2 25. Rd1 Qc4 26. b3 Qxd4 27. Qxd4 Bxd4 28. Rxd4 e5 29. Rxd5 b4 30. c4 Rh8 31. Ke2 Rh6 32. Kf1 Rh7 33. Ke1 Rf7 34. Nd3 Rg7 35. Nxb4 Kf7 36. Nc6 Kg8 37. Nxe5 Nh6 38. c5 g5 39. Nf3 Kh7 40. Nxg5+ Kg6 41. Ne6 Kf7 42. Nxg7 h4 43. Nh5 Ng8 44. Rd4 Rb8 45. b4 a5 46. bxa5 Rb1+ 47. Rd1 Rb7 48. c6 Rb8 49. Rd4 Rb2 50. Rxh4 e5 51. c7 Rc2 52. c8=Q Rxc8 53. Bxc8 Ke7 54. Ba6 Kd7 55. Re4 Ke6 56. f4 Kf5 57. Rxe5+ Kg6 58. Bd3+ Kf7 59. Bc4+ Kf8 60. Rf5+ Ke7 61. Bxg8 Kd7 62. Rd5+ Kc8 63. Rd1 Kb8 64. Ra1 Kc8 65. f5 Kc7 66. Rd1 Kc8 67. Rd2 Kb7 68. Rd8 Kc7 69. Rd1 Kc8 70. Ra1 Kc7 71. f6 Kd8 72. f7 Ke7 73. Rd1 Ke6 74. Rb1 Ke7 75. Ra1 Kf8 76. Nf4 Kg7 77. Nd3 Kf8 78. Nb2 Ke7 79. Rd1 Ke6 80. Na4 Ke7 81. Nb2 Ke6 82. Ra1 Ke7 83. Na4 Kf8 84. Nb6 Ke7 85. Rd1 Kf8 86. Na4 Ke7 87. Nb2 1/2-1/2

Game 4: Huo Chess v0.9921 vs Sven bot @ Chess.com (1100 ELO rated)

[Event “vs Computer”]
[Site “Chess.com”]
[Date “2021.04.02”]
[Round “?”]
[White “Huo_Chess”]
[Black “Sven”]
[Result “1-0”]
[TimeControl “-“]

Huo Chess v0.9921 vs Sven (1100) [2021-04-02]
1. g4 c6 2. Nc3 h6 3. d4 g6 4. Be3 Qc7 5. Qd2 Bg7 6. Bf4 Qd8 7. e4 Kf8 8. Bc4 Ke8 9. Nge2 Qb6 10. Na4 Qd8 11. Nc5 b6 12. Nb3 d6 13. Rg1 Kf8 14. h4 Qe8 15. Nbc1 Bd7 16. Nd3 a5 17. c3 h5 18. g5 a4 19. Qc1 b5 20. Bxb5 Ra5 21. Bc4 Bg4 22. b4 Ra8 23. Ng3 Qd8 24. Nf1 Bd7 25. Qa3 Bg4 26. Nb2 Rh7 27. Nxa4 Na6 28. Bxa6 Qc7 29. Nb2 Bh3 30. Nd2 Be6 31. Qa4 Ke8 32. Nd1 Qb6 33. b5 Bf8 34. Rh1 Bc8 35. Nc4 Qc7 36. b6 Rxa6 37. Nxd6+ exd6 38. Qxa6 Be7 39. Qa8 Qd7 40. Qb8 Kf8 41. c4 Qd8 42. b7 Bxb7 43. Qxb7 Ke8 44. Qxc6+ Kf8 45. Qa6 Qd7 46. Qa8+ Bd8 47. Qa3 Be7 48. Qa6 Qd8 49. Nb2 Qc7 50. Qa3 Qb6 51. Qa8+ Kg7 52. Rb1 Qxd4 53. Ke2 Qb6 54. Qd5 Rh8 55. Na4 Qc7 56. Ra1 Qc8 57. Qd4+ Kh7 58. Bxd6 Qe6 59. Bb8 Qc6 60. Be5 Ba3 61. Bxh8 Bf8 62. Nb2 Qc7 63. Nd1 Qe7 64. Nc3 Qc7 65. Nb5 Qb7 66. Na7 Qa8 67. Be5 Bb4 68. Rab1 Ba3 69. Rb8 Qxe4+ 70. Qxe4 Bc5 71. Nc6 Ba3 72. Rb7 Nh6 73. Qd3 Ng4 74. Qxa3 Nxf2 75. Rxf7+ Kg8 76. Qf8# 1-0 

Game 5: Huo Chess v0.9921 vs. Sven bot @ Chess.com (1100 ELO rating)

[Event “vs Computer”]
[Site “Chess.com”]
[Date “2021.04.07”]
[Round “?”]
[White “Huo_Chess”]
[Black “Sven”]
[Result “1-0”]
[TimeControl “-“]

1. g4 d5 2. Bg2 Be6 3. Nc3 c5 4. e3 Qd6 5. Qf3 Nf6 6. Bh3 b6 7. Nge2 a6 8. d3 Qe5 9. Nf4 g6 10. d4 cxd4 11. Na4 Nbd7 12. Rb1 Rg8 13. Bd2 b5 14. Nd3 Qe4 15. Qxe4 dxe4 16. Nac5 Nxc5 17. Nxc5 Bxa2 18. Ra1 dxe3 19. Bxe3 Nd7 20. Rxa2 Rd8 21. Rxa6 Nb8 22. Ra5 Nc6 23. Rxb5 Ne5 24. Nxe4 f6 25. Bb6 Ra8 26. Ra5 Rb8 27. Ra6 Bh6 28. Bc7 Rb7 29. Ra8+ Kf7 30. Rxg8 Rxc7 31. Rh8 Rxc2 32. Rxh7+ Bg7 33. Rf1 Rc6 34. Nc3 Rb6 35. Na4 Re6 36. g5 Rc6 37. Rg1 Nf3+ 38. Kf1 f5 39. Rg2 Kg8 40. Rg3 Nd4 41. Rh4 Rc2 42. b4 Be5 43. Re3 Rc1+ 44. Kg2 Nc6 45. Rh6 Bg7 46. Rxg6 Kh8 47. b5 f4 48. Re4 Nd4 49. b6 e5 50. Nb2 Kh7 51. Rd6 Nb3 52. Nc4 Ra1 53. Bf5+ Kg8 54. Nxe5 Nc5 55. Rd8+ Bf8 56. Rxf4 Kg7 57. Ng6 Ra4 58. Rf3 Be7 59. Nxe7 Rh4 60. Rd5 Ne4 61. Rd4 Nxg5 62. Rxh4 Kf7 63. Re3 Kf8 64. Re5 Kf7 65. b7 Nf3 66. Kxf3 Kf8 67. b8=Q+ Kg7 68. Qa8 Kf6 69. Qh8+ Kf7 70. Rh7# 1-0
Huo Chess v0.9921 vs Sven (1100) [2021-04-07]

More games to be uploaded soon with stronger opponents!

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.
Exit mobile version
%%footer%%