Thank you for 5000 games played with Scratch Chess - Game of Kings!

Scratch Chess - Game of Kings

After some additional improvements, GoK delivers a more stable game, and is down to 2 inaccuracies, 0 mistakes and 0 blunders according to Stockfish analysis (Bonsai Blue Belt (white) vs. GoK Level Difficult (black)), played on Sulfurous.

The GoK development version now has a first prototype of PGN export and FEN import/export running. It does not include all PGN/FEN features yet, but should be enough to play around with it. On lichess you can import PGN via https://lichess.org/paste (and FEN can be opened via the lichess URL provided by the GoK export). I would be happy to receive feedback - thanks!

https://scratch.mit.edu/projects/195913008/ is a GoK prototype that plays white. It is pretty hacky and certainly still buggy, but I would appreciate if you would give it a try and provide feedback. Thank you!

OK, I went ahead and updated the main project at https://scratch.mit.edu/projects/148769358 to the current development version, which includes support for the engine to play white, as well as for FEN/PGN import/export. I haven't done too much testing, but I think I will get quicker feedback like this, and any bug emerging now should probably be easy to fix.

In addition, levels Easy and Medium are faster now, esp. Medium.

Thank you for 300 Likes for Scratch Chess - Game of Kings!

Scratch Chess - Game of Kings

How Game of Kings is implemented

Hello Chess Players and Programmers!

Over the last couple of months, several Scratch users have asked for more detailed info on how Scratch Chess - Game of Kings works internally. So, I decided to provide a forum posting on that topic, which might also trigger further discussion. I should mention that I am not a good chess player, know next to nothing about chess in theory, and had only a basic idea about chess programming when I started the project. But luckily, I got help from others, and found valuable online material too.

In general, Scratch is probably the least suited programming and runtime environment to implement a chess engine. It was designed for other purposes - for simple games and animations, programmed by kids. The language's capabilities are limited, esp. regarding structured programming, there are no bitwise operations (hence no bitboard data structure), it is very slow and even has some performance throttling built in (so that kids wouldn't have to worry about timing). But that hasn't stopped people from writing pen-based 3D games in Scratch. And for the chess engine case, that just meant it was bit more difficult, and that no implementation would ever reach the playing strength of chess games on other platforms (BTW, running GoK on other Scratch engines like TurboWarp shows the performance potential: https://turbowarp.org/148769358). So perfect, it was just the challenge I was looking for.

My approach was to try different ideas, and only when I was stuck, I investigated about underlying chess programming theory in certain areas. So I still knew MiniMax from University (it's the logical approach for board games), and came up with some kind of move ordering (based on iterative deepening), square piece tables, mobility evaluation and attack tables myself - I just fine-tuned the crude original implementations later, after reading on https://www.chessprogramming.org and other places. Other things like alpha/beta-pruning or quiescence search I picked up from there directly.


Kochy-Richter checkmate detected by GoK - click image to view video

The First Week - CoderDojo Linz Chess
The GoK project started as a tutorial for the CoderDojo Linz Kids Programming Club. I had implemented some other Scratch games before, which were all accompanied by step-by-step tutorials for children to re-create the programs on their own. It was Sunday evening, CoderDojo takes place Fridays, so I had four nights for coding and one for writing the tutorial. This is how that went:

Day #1
At first I worked on the graphical user interface. I found some nice open-usage chess graphics, and drew the pieces via Scratch Pen functions, applying the Stamp operation. Sprites were only used for animating piece-movement. I preferred a simplistic 2D bird’s eye view to complex 3D graphics or similar. And user input should be intuitive and require just two clicks: first click the piece to move, then click the target square. When tinkering about how to represent board data in memory, I ended up with a Scratch List with 64 entries, one for each square. The list contains Centipawn values for each type of piece - negative ones for white, positive ones for black. E.g. the black queen’s value is “900”, rook is “500”, bishop “330”, knight “310”, pawn “100”, and finally a king is “20000” (capturing a king surpasses everything else combined). By adding up all the piece values on the board, one ends up with a material evaluation of the current board.

Day #2
Day #2 was dedicated to ramping up a chess engine prototype. I was aware that this would require a Move Generator and a Board Evaluation Function, combined with a MiniMax algorithm - a recursive approach, with one recursion for each subsequent move, spanning up a tree of moves. On each tree leaf, that is after the final move, the resulting board would be evaluated. I guessed the program could look ahead three moves (“Ply 3”) and put a hardcoded limit there. Luckily recursions are possible in Scratch via Custom Blocks, but local state cannot be kept, as local variables don’t exist, and block parameter values cannot be changed. So, I applied lists for emulating a call stack. Every local variable has its own list. Some other Scratch chess engines have a dedicated custom block for each Ply, but I didn’t want to introduce duplicate code (by now we are at a move depth of 25 including Quiescence). I also implemented a move generator, initially for pawns and knights, and had the engine make its first moves. The move generator filled a move list for every search depth level with all possible moves at that point. Those moves were then applied one-by-one, MiniMax was invoked again for the next depth, and after returning the move was reverted to bring the board back to its original state. A move was represented by a 4-digit number, referring to the source and target squares. E.g. Nb8a6 would be “0217” – a move from square 2 to square 17 on the board.

Day #3
Next I completed the move generator for all other pieces. And I read about Alpha/Beta Pruning on the Chess Programming WIKI, which was an eye-opener. Alpha/beta pruning allows to discard all moves early in MiniMax which won’t make sense anyway - something that the human mind does intuitively. This caused a major speedup. Alpha and beta are assured lower and upper bounds for the board evaluation, which are passed up and down the recursive MiniMax calls and checked on each move. We can then ignore anything worse than alpha, because we will not make a move that’s worse than the best we have found so far. And we can ignore anything better than beta, because the opponent has a better move option than that. I then added positional consideration to the board evaluation function as well by using Piece Square Tables (the tables for pawns and kings even distinguish between midgame and endgame). This made pieces on certain squares more valuable than on others. I also added check and checkmate testing by invoking the MiniMax, either for one move of the same side (check), or two consecutive moves in normal order (checkmate), and then probing for king captures. At that point castling was added, too. The engine was able to play a correct game, apart from en-passant, which was implemented some weeks later.

Day #4
The final coding evening was dedicated to pawn promotion, code cleanup, and to verifying that the user input was valid. Pawn promotion was a quick and dirty implementation and stayed like this for months. This resulted in several lost games against @Samueldora’s Bonsai later, until I handled promotion in a generic way, just like any other move, so it would have full evaluation coverage.

Day #5
The day before the CoderDojo event, I wrote the programming tutorial. Recreating all code would have been too much effort for the CoderDojo Scratchers, so I limited that task to the MiniMax and Evaluate blocks.

Extensions and Tuning
At this point the chess engine was working fine, delivering a Ply3 game at around 25 seconds think time. It was kind of fun, but slow with mediocre playing skills. I had not invested any time in performance tuning yet, which would be the key to look ahead more moves, hence increase playing strength. You can still run an early remix of this initial version: https://scratch.mit.edu/projects/150365816/

All other Scratch engines were at Ply3 or Ply4 too. My goal was to get to Ply6 and beyond, as well as improving the evaluation function. And it took me several months to accomplish this, and other improvements for having a more sophisticated evaluation. Here is what I did:

(1) Opening Book
I cranked out a quick Opening Book implementation, just as a proof of concept, with something like 10 common openings. Luckily user @Grijfland picked up there and put a lot of work into what finally became GoK’s complete opening book. Thanks a lot for that! You can notice the opening book is applied at the beginning of a game, indicated by the opening book icon.

(2) Additional Evaluation Considerations
Over time I added support for evaluating double/isolated pawns, passed pawns, double bishops, early queen movement, castling and king protection, and similar, as well as special support for king/queen and king/rook endgame scenarios. Some of those calculations are costly and are not done at the MiniMax leaf, but earlier up the tree, and down the tree only again after pawns or kings have moved, as those piece's positions define most of extended evaluation. This also includes King Safety, Pawn Storms and Open Files (see (11)).

(3) Incremental Evaluation
Evaluating the whole board at each MiniMax tree leaf is expensive, performance-wise. Instead, GoK now evaluates the whole board only once at the beginning, and then just adds/subtracts the material and positional changes connected with each subsequent move.

(4) Move Ordering
By ordering the move lists from best move to worst move, alpha/beta pruning can be much more efficient. The alpha/beta funnel will be smaller early on, allowing to cutoff more moves outside the funnel immediately. GoK first applies known hash-moves that have led to pruning on the same board before (this does not even require move generation), then promotions, then good captures (according to Most Valuable Victim - Least Valuable Aggressor Evaluation, or short MVV/LVA), then so called KillerMoves (which led to pruning on different but similar boards before), and then the rest of moves according to their expected positional effect. Additionally there is Iterative Deepening – see below. With move ordering, GoK currently only has to traverse 5 out of 35 generated moves in average. And when transposition tables are applied (see below), that number is even smaller (AKA “Branching Factor”). Imagine GoK on Ply6, having to evaluate 35 moves on each MiniMax call. Those are 35^6 = 1,838,265,625 boards to be evaluated. But if we can skip 30 out of 35 moves each time, we end up with only 5^6 = 15,626 boards.

(5) Transposition Tables
Every board ever evaluated in the current MiniMax run is stored in a so-called Transposition Table (whose underlying implementation is a Hashtable). Table entries consist of board hash (key), and board evaluation (either exact, or upper/lower-bound, depending whether there was an Alpha/Beta cutoff) plus the best follow-up move (value). If we ever encounter a board we have seen again, we can then re-use what we have calculated before. Board hashes are created using Zobrist Hashing. Bitwise operations like XOR are not supported by Scratch, so fast calculating of hashes, and incrementally adding / removing hash values was a challenge too. In Scratch terms, every entry member requires a list. Those lists are pre-allocated with 200,000 slots, the Scratch list size limit.

(6) Move Generator Lookup Tables
The original move generator was pretty naïve and had hardcoded instructions for calculating where each piece could move. Now all those calculations are done in advance before starting the game - for every piece, on every square. The result is stored in lists and can be looked up much more quickly.

(7) Attack Tables
Each time we calculate the next round of moves, we also calculate which squares are currently attacked (and - albeit currently disabled, as it is only used for SEE - by which kind of pieces). This ensures that a king will not enter a checked square, and is the data basis for static exchange evaluation (SEE). To prevent runtime overhead, we do that lazily on quiescent moves, namely then when a king could capture a piece.

(8) Quiescence Moves
After a certain search depth has been reached, MiniMax calculates and returns the current board evaluation. But this arbitrary border can lead to horizon effects. For example, consider the final move is a queen capturing a pawn. But what if that queen can be counter-captured, but that information is beyond the current Ply horizon? We could end up sacrificing a queen for a pawn. To prevent this, GoK adds a few extra MiniMax rounds where it only inspects captures, checks and check evasions, once the maximum Ply depth has been reached. GoK can go up to 25 Ply levels; on the Scratch 3.0 runtime it usually between Ply4 and Ply6, with additional Quiescence moves.

(9) Mobility
GoKs also considers how many target squares each piece can reach on the final two plies. Extra mobility is rewarded accordingly in move evaluation. There are lookup tables for each piece, which map target square count to evaluation value.

(10) Iterative Deepening
It might seem counter-intuitive, but running several MiniMax invocations, each looking ahead more moves, can improve think time. This is possible due to transposition table caching and move ordering. By applying cached hash moves first - moves that led to a cutoff on a previous run - we might not have to calculate any other moves at all - that is if they trigger a cutoff again. And for Ply1 we keep stats of their evaluations from the run before, and apply them for ordering Py1 moves during the next deepening step.

(11) King Safety, Pawn Storms and Open Files
During midgame the king should be protected by pawns. Only during endgame it can play a more active role. Also, a group of approaching pawns can become dangerous, and so can an open file which might quickly be occupied by the opponent's rook. And having opponent pieces attack the ring around the king is not good either, especially double attacks. GoK calculates all of that during board evaluation, and it was the 2nd most important improvement in regard to playing strength (right after increased search depth and quiescent move). I implemented this based on the Delocto chess engine's approach - thanks to the author!

(12) Futility Pruning
Futility Pruning is applied towards the leafs of the search tree, when the current board situation is bad enough to conclude that it cannot be recovered from later, hence may be cut off as the player will select better moves before. That means a lot of search tree leaves don't have to be visited, which may save a significant amount of time.

(13) Aspiration Windows
An Aspiration Window is an expected range for the MiniMax evaluation result. As we are applying Iterative Deepening, the previous runs' result can be used here. The initial alpha / beta values can be set to a small range around that expected value, hence a lot more moves can be cut off early and MiniMax will be much faster. The drawback is, in case we end up with a result outside the range, we need to increase the range and rerun MiniMax.

(14) Late Move Reduction
Moves at the end of an ordered move list are most likely not worth being checked at the same depth as those at the beginning. What we do is a probe run with limited depth on later moves that seem to be stable, and if they cut off, we do not need to examine them in detail.

(15) Principal Variation Search
Once we have found a move sequence acceptable for both players (means it has not produced alpha/beta cutoffs, hence we know it's exact evaluation), we can then speculate that we will pretty likely stick with it, as other sequences won't be better. So we search subsequent nodes with a null-window, which will tell us if it could still produce a better evaluation (but not its exact value). This is a much faster search. If contrary to our expectation a move might increase the evaluation, we do a full re-search on it.

(16) Null Move Pruning
Null move pruning is basically a heuristic where we let one side make two consecutive moves, and if the 2nd move still produces a cutoff, we can prune that whole search branch, as it doesn't have any potential.

(17) Staged Move Generator
Since the introduction of the transposition table, stage #1 of move generation was to look up the stored hash move (that is the best move from previous searches), as this could render generating more moves unnecessary. In 2022 I added more stages, namely a fast procedure to detect good captures and another one to re-apply former cutoff moves (killer moves) from earlier searches. In two out of three searches those moves are sufficient for early cutoff, with no more traditional move generation necessary.



Original posting continues:

While the main focus was on performance tuning, I also added some other features, e.g. providing three difficulty levels (higher level = more search depth, plus on level “Difficult” think time is measured and search depth is adjusted after each move), underpromotion, support for playing black, undoing moves, PGN/FEN import/export, and lichess.org integration for automatic game analysis.

I hope you found this interesting. For comments or questions, please reply to this posting. Thank you!

ArnoHu

Scratch Chess - Game of Kings



Update March 2018:

I did what I promised nearly a year ago and cranked out an online two player version of GoK by using cloud variables. Players require Scratcher login to take part - only Scratchers can read from and write to cloud variables. The community can watch the ongoing game. In case no one wants to play, the GoK engine steps in. It might even play against itself. I hope you like it!

Scratch Chess - Game of Kings ONLINE



Update September 2018:

This slidedeck contains more detailed info on chess programming techniques: https://www.slideshare.net/ArnoHuetter/chess-engine-programming


Update May 2019:

The GoK Chess engine source code is available in textual form at https://github.com/ArnoHue/scratch/blob/master/chess/Engine.scratch


Update September 2019:

Added Principal Variation Search, Futility Pruning, Null Move Pruning, Aspiration Windows and Late Move Reduction. And GoK can now reach up to ply 20, not only 15.


Update September 2020:

More performance tuning and bug fixing lately. Also, GoK can look ahead up to 25 moves now, but that's only realistic during late endgame and on fast Scratch runtimes like TurboWarp: https://turbowarp.org/148769358


Update October 2020:

I created a tutorial project on chess engine programming at https://scratch.mit.edu/projects/442870614/


Update March 2021:

There is a great Chess engine programming video at https://www.youtube.com/watch?v=U4ogK0MIzqk


Update January 2022:

It is done! GoK (TurboWarp, Difficult / Competition mode) wins against Stockfish 14 level 7 (2700) in 93 moves: https://scratch.mit.edu/discuss/post/5970871/


Update November 2022:

With the latest improvements in GoK 4.68 (staged move generator, trapped rook evaluation, improved castling evaluation, performance tuning, search extension when there is any check in previous plies), the engine won another game against Stockfish 14 level 7.


Update August 2023:

GoK Chess Profiler Mode Explained: https://scratch.mit.edu/discuss/post/7455708/

I just updated the stable GoK version to the previous development version. Level “Easy” is faster now at equal playing strength, and the delay after an engine move (caused by checkmate verification, which is required on low Plys) was shortened. “Easy” should now allow for a real blitz game on decent hardware.

Scratch Chess - Game of Kings

Interesting game here between GoK (Level Easy, white) and Bonsai (Yellow Belt, black), so both engines playing in their fastest (and weakest) mode. GoK was hopelessly behind, but turned it around after several strange Bonsai blunders. Average think time: GoK 5sec, Bonsai 7sec (up to midgame it was GoK 4sec, Bonsai 9sec - during endgame GoK gears up from Ply2 + Quiesc4 to Ply3 + Quiesc3), hence is a bit slower than before, while Bonsai gets faster. lichess.org game protocol and analysis: https://lichess.org/q9TQkKTL

Scratch Chess - Game of Kings

Some more move ordering optimization led to an average think time speedup of 20% in Chess - Game of Kings.

Scratch Chess - Game of Kings

ArnoHu wrote:

Over the last couple of months, several Scratch users have asked for more detailed info on how Scratch Chess - Game of Kings works internally. So, I decided to provide a forum posting on that topic, which might also trigger further discussion.

Thank you for sharing this! I found it very interesting to read, especially as I have seen how GoK developed during the last months. It is stunning, which complexity and, in the end, performance is possible despite the limitations of Scratch.

In my own approach Bonsai Chess, I have realized only part of those concepts, though I already thought about some others of them, e.g. incremental evaluation, iterative deepening, and SEE.

What are your experiences with GoK against human players? With Bonsai I have very little feedback there. I am an experienced club player, though no longer active, and beat Bonsai (and Gok) without problems, my family members, which are hobby players, normally lose against it, because Bonsai just exploits their tactical blunders. It seems to be on the level of early commercial chess computers around 1980.

Samueldora wrote:

ArnoHu wrote:

Over the last couple of months, several Scratch users have asked for more detailed info on how Scratch Chess - Game of Kings works internally. So, I decided to provide a forum posting on that topic, which might also trigger further discussion.

Thank you for sharing this! I found it very interesting to read, especially as I have seen how GoK developed during the last months. It is stunning, which complexity and, in the end, performance is possible despite the limitations of Scratch.

In my own approach Bonsai Chess, I have realized only part of those concepts, though I already thought about some others of them, e.g. incremental evaluation, iterative deepening, and SEE.

What are your experiences with GoK against human players? With Bonsai I have very little feedback there. I am an experienced club player, though no longer active, and beat Bonsai (and Gok) without problems, my family members, which are hobby players, normally lose against it, because Bonsai just exploits their tactical blunders. It seems to be on the level of early commercial chess computers around 1980.

Thanks Samueldora! I will provide more details over time in the original posting, also add some code snippets via forum scratchblocks, so stay tuned! I am also curious about Bonsai's inner workings. I took a look once, but insights from the creator might be easier to understand than skimming through Scratch code.

My experience is that better players win by taking advantage of the horizon effect. Hobby players may lose, esp. on faster engines like Sulfurous, because one or two blunders are enough for GoK to bring the game home.

Scratch Chess - Game of Kings

A nice substantive story about GoK . However, still a few points of criticism.
References to Chess Programming Wiki (CPW) do not all go well
and I would have liked to see a global flow chart from GoK.

Grijfland wrote:

A nice substantive story about GoK . However, still a few points of criticism.
References to Chess Programming Wiki (CPW) do not all go well
and I would have liked to see a global flow chart from GoK.

Thanks! And thanks for reporting the broken links. Actually I had all inserted them correctly, but this forum software decided to escape special characters within the URL, which in turn the Chess Wiki cannot handle. I replaced the links with Google URL-shortened ones, and that works. Please try again!

Scratch Chess - Game of Kings

Thank you for 6000 Scratch Chess - Game of Kings games played! Thanks to your feedback I was able to improve the project significantly over the last couple of months (in playing strength, features and usability). Also, ★s and ♥s are always appreciated if you happen to like the game!

Scratch Chess - Game of Kings

GoK Chess (white) wins against Midecah Chess (black) in 6 moves: https://lichess.org/IoGFuh8d

1. a4 { A00 Ware Opening } h5 2. d4 f5 3. e3 h4 4. Be2 g5 5. Bh5+ Rxh5 6. Qxh5# { White wins by checkmate. } 1-0

Scratch Chess - Game of Kings

GoK Chess (white) wins against The Turk (black) in 18 moves: https://lichess.org/DRnkjEFN

1. Nf3 Nc6 { A04 Zukertort Opening: Black Mustang Defense } 2. Nc3 Nb4 3. e3 Nh6 4. d4 d6 5. a3 Nc6 6. d5 Na5 7. b4 Bg4 8. h3 Nb3 9. cxb3 Bh5 10. g4 Bg6 11. Bb5+ c6 12. dxc6 bxc6 13. Bxc6+ Qd7 14. Bxd7+ Kxd7 15. O-O Rc8 16. Ne5+ Ke6 17. Qd5+ Kf6 18. Nd7# { White wins by checkmate. } 1-0

Scratch Chess - Game of Kings

Announcing Game of Kings Blitz Chess (AKA Level “Easy”)

After the latest move-ordering optimizations, I was also able to re-enable quiescence expansion for check-situations - that means that if a check happens at the Ply leaf, it is not considered a quiet situation any more. Instead we add another Ply and look what happens next.

Now that allows for staying on Ply2 + Quiesc4 even during endgame, and still let the GoK engine figure out checkmate approaches. And this in turn implies that think time stays at around 2-3 seconds throughout the match on level “Easy”, making it a real blitz game!

Please give it a try. I am curious to hear about your playing experiences with “GoK Blitz Chess”!

Scratch Chess - Game of Kings

GoK Chess (white, Sulfurous player) wins against Stockfish (Strength 5, 1750 ELO) (black) in 80 moves: https://lichess.org/vMtILMna

1. d4 Nf6 2. c4 e6 3. Nc3 Bb4 4. e3 O-O { E46 Nimzo-Indian Defense: Normal Variation } 5. a3 Bd6 6. c5 Be7 7. Nf3 b6 8. Bc4 d6 9. cxd6 Bxd6 10. O-O Bb7 11. Bd2 c5 12. dxc5 Bxc5 13. b4 Bd6 14. Nb5 Nc6 15. Nxd6 Qxd6 16. b5 Na5 17. Bxa5 Qxd1 18. Raxd1 bxa5 19. Ne5 Rfd8 20. Rxd8+ Rxd8 21. Nc6 Ra8 22. Nxa5 Be4 23. f3 Bf5 24. Kf2 Bg6 25. e4 Nd7 26. Ke3 Kf8 27. Nc6 Nb8 28. e5 Ke8 29. Rd1 Nd7 30. f4 Bc2 31. Rd6 h6 32. Kd4 Nb6 33. Be2 Bg6 34. g4 Kf8 35. h4 Bh7 36. h5 Ke8 37. Bf3 Kf8 38. g5 Rc8 39. Bh1 Bb1 40. gxh6 gxh6 41. Kc3 Kg7 42. Kb3 f6 43. Rxe6 fxe5 44. Nxa7 Rc1 45. Bg2 Nc4 46. fxe5 Bf5 47. Rf6 Bh7 48. Bd5 Nxe5 49. Re6 Bc2+ 50. Kb4 Nd3+ 51. Kc3 Nc5 52. Rd6 Bf5+ 53. Kd4 Na4 54. b6 Rd1+ 55. Ke5 Nxb6 56. Rxb6 Rb1 57. Rxb1 Bxb1 58. a4 Kh8 59. a5 Bd3 60. Kf6 Bf1 61. Kg6 Bc4 62. Be4 Bd5 63. Bf5 Kg8 64. Kxh6 Bh1 65. Kg6 Kf8 66. Kf6 Kg8 67. h6 Bg2 68. h7+ Kh8 69. Ke6 Bf1 70. Nc8 Kg7 71. Nd6 Be2 72. Ke7 Bh5 73. a6 Be8 74. Kxe8 Kf6 75. h8=Q+ Kg5 76. Qg7+ Kf4 77. a7 Ke3 78. a8=Q Kd2 79. Qf3 Kc1 80. Qgc3# { White wins by checkmate. } 1-0

Scratch Chess - Game of Kings