Scratch Chess Engine - Game of Kings

ArnoHu

S_P_A_R_T wrote:
Ok, thank you! I've searched for “value mapping”, but couldn't find anything, is it called by a different name in the CPW wiki?

https://www.chessprogramming.org/Transposition_Table
https://www.chessprogramming.org/Hash_Table

S_P_A_R_T

Thank you! I still have 2 questions.

1. If the table index from the hash is empty (because the hash of the position has never been seen before), does that just return nothing, and the search just continues as usual?

2. Why do you use the specific way that you use for the key? (Using a modulo function)

Check out Space Program Simulator!

In it, you can build your own rockets from a variety of parts!
Then fly it with realistic orbital mechanics.

Go to orbit, explore different planets, share your save codes, and do so much more!

If you would like to help out on the project or chat about space or really anything else, check out the offical SPS Studio!

For more information & tutorials, check out the offical forum post!

ArnoHu

S_P_A_R_T wrote:
Thank you! I still have 2 questions.

1. If the table index from the hash is empty (because the hash of the position has never been seen before), does that just return nothing, and the search just continues as usual?

2. Why do you use the specific way that you use for the key? (Using a modulo function)

1. Yes
2. Modulo is essential to stay within the size of the list, otherwise you will run out of bounds. At this point it is not a key any more, it is a list index. The key (=Zobrist hash) is still verified after that, this is why it is also stored at that very index. Linear probing (AKA collision handling) means it could be located at that or one of the next indexes. Due to modulo, several Zobrist hashes might end up at the same index otherwise.

Last edited by ArnoHu (June 20, 2023 04:41:09)

S_P_A_R_T

Thanks! I will get started with implementing a TT in WD today

Check out Space Program Simulator!

In it, you can build your own rockets from a variety of parts!
Then fly it with realistic orbital mechanics.

Go to orbit, explore different planets, share your save codes, and do so much more!

If you would like to help out on the project or chat about space or really anything else, check out the offical SPS Studio!

For more information & tutorials, check out the offical forum post!

ArnoHu

ArnoHu wrote:
GoK Chess 6.130 (Medium, Scratch 3) vs. Bonsai Chess (Blue, TurboWarp) Testgame Series

GoK Chess - Bonsai Chess / Result: 9.5 - 0,5
GoK Chess - Bonsai Chess / Average Accuracy: 88% - 81%

Game #1: GoK (white) wins in 72 moves: https://lichess.org/wEksyi2j#143 (94% vs. 90% accuracy)
Game #2: GoK (white) wins in 58 moves: https://lichess.org/g6JZzNlG#115 (94% vs. 89% accuracy)
Game #3: GoK (white) wins in 22 moves: https://lichess.org/mqIiXdDG#43 (92% vs. 75% accuracy)
Game #4: GoK (black) wins in 54 moves: https://lichess.org/X5SGsY70#108 (95% vs. 87% accuracy)
Game #5: GoK (black) wins in 50 moves: https://lichess.org/UxWfLrwn#100 (79% vs. 73% accuracy)
Game #6: GoK (black) wins in 68 moves: https://lichess.org/1STO8xbQ#136 (89% vs. 84% accuracy)
Game #7: GoK (black) wins in 39 moves: https://lichess.org/5WRTZL0g#78 (79% vs. 73% accuracy)
Game #8: GoK (black) draws in 98 moves after nearly losing: https://lichess.org/IanQMvwW#196 (85% vs. 84% accuracy)
Game #9: GoK (white) wins in 65 moves:https://lichess.org/mBZs8ZHj#129 (92% vs. 88% accuracy)
Game #10: GoK (white) wins in 27 moves: https://lichess.org/zcYGIbb8#53 (76% vs. 67% accuracy)

Games 6 to 10 were played on a slower system, which partly explains GoK's lower accuracy (it also depends on how the game develops, see Bonsai's accuracy which also dropped, although Bonsai's playing strength does not depend on system speed.

Think time is a bit difficult to compare as Bonsai was running on TurboWarp, which is much faster than Scratch 3. During midgame, the adjusted think time for Bonsai Blue is 4 times longer in average than the one of GoK Medium. During endgame the adjusted think time is about the same in average. That is also the reason why Bonsai sometimes leads during midgame, but loses the advantage during endgame.

GoK Chess 6.133 (Medium, Scratch 3) vs. Bonsai Chess (Blue, TurboWarp) Testgame Series

For the first time, GoK wins such a series 10:0

Game #1: GoK (white) wins in 39 moves: https://lichess.org/lRepgE6o#77
Game #2: GoK (black) wins in 48 moves: https://lichess.org/lDOrbN6f#96
Game #3: GoK (white) wins in 29 moves: https://lichess.org/vMFXN2LZ#57
Game #4: GoK (black) wins in 26 moves: https://lichess.org/rYIz0Rnr#52
Game #5: GoK (black) wins in 70 moves: https://lichess.org/IxGV4cuI#140
Game #6: GoK (black) wins in 34 moves: https://lichess.org/pfPxjubn#68
Game #7: GoK (white) wins in 39 moves: https://lichess.org/ZOfjmZwx#75
Game #8: GoK (white) draws in 25 moves: https://lichess.org/ydGdgk7D#49
Game #9: GoK (black) wins in 48 moves: https://lichess.org/wLw7oZ1R#96
Game #10: GoK (white) wins in 51 moves: https://lichess.org/D1S1dwFt#101

S_P_A_R_T

Very interesting, GoK's performance on Scratch 3 seems to be unmatched anywhere else. Would you say this is because of the higher search depth, or a better evaluation function?

Check out Space Program Simulator!

In it, you can build your own rockets from a variety of parts!
Then fly it with realistic orbital mechanics.

Go to orbit, explore different planets, share your save codes, and do so much more!

If you would like to help out on the project or chat about space or really anything else, check out the offical SPS Studio!

For more information & tutorials, check out the offical forum post!

ArnoHu

S_P_A_R_T wrote:
Very interesting, GoK's performance on Scratch 3 seems to be unmatched anywhere else. Would you say this is because of the higher search depth, or a better evaluation function?

It's both, but search depth probably is more a factor than evaluation in those matches against Bonsai.

AFAIK Bonsai reaches ply 5 or even ply 6 on level Blue Belt (this is comparable to GoK ‘s full search depth on level Medium to Difficult on Scratch 3), but it does not have quiescence search. That’s a major factor, as the time invest for quiescence search is a lot larger than for full search for GoK. This is only possible because GoK's search is very fast, with highly optimized move generation and move ordering. Keep in mind that GoK Medium takes about 25% of Bonsai Blue's think time during midgame.

That quiescence advantage might kick in some time during midgame in a certain situation, and then it usually pays off big time, or it won't, then it's decided during endgame.

I have invested a lot, and I mean a lot into GoK's evaluation functionality, it covers all kind of factors. I don't quite understand Bonai's evaluation logic yet, but it seems to do magic, with less code. Bonsai sometimes gains some positional advantage early on.

S_P_A_R_T

What is GoK's full search on Medium on Turbowarp?

Check out Space Program Simulator!

In it, you can build your own rockets from a variety of parts!
Then fly it with realistic orbital mechanics.

Go to orbit, explore different planets, share your save codes, and do so much more!

If you would like to help out on the project or chat about space or really anything else, check out the offical SPS Studio!

For more information & tutorials, check out the offical forum post!

ArnoHu

S_P_A_R_T wrote:
What is GoK's full search on Medium on Turbowarp?

Depends on the complexity of the board, full search probably ply 9 to 10 during midgame, plus quiescence search.

S_P_A_R_T

Wow, impressive!

Check out Space Program Simulator!

In it, you can build your own rockets from a variety of parts!
Then fly it with realistic orbital mechanics.

Go to orbit, explore different planets, share your save codes, and do so much more!

If you would like to help out on the project or chat about space or really anything else, check out the offical SPS Studio!

For more information & tutorials, check out the offical forum post!

P-P-C

Here is a game against a 2600 ELO bot from chess.com

Bot : White
GoK : Black
Accuracy : 87.0/81.4
Winner : Bot
Lenght : 98 moves

1. d2d4 d7d5 2. e2e3 Ng8f6 3. c2c4 Nb8c6 4. Nb1c3 e7e6 5. Ng1f3 Bf8b4 6. Bc1d2 O-O 7. Bf1d3 d5xc4 8. Bd3xc4 e6e5 9. Nf3xe5 Nc6xe5 10. d4xe5 Nf6g4 11. O-O Ng4xe5 12. Bc4e2 Bc8e6 13. Qd1c2 Be6c4 14. Be2xc4 Ne5xc4 15. Rf1d1 Qd8h4 16. Nc3e4 Nc4xd2 17. Ne4xd2 Ra8d8 18. Nd2f3 Rd8xd1 19. Ra1xd1 Qh4e7 20. a2a3 Bb4d6 21. b2b4 a7a5 22. b4xa5 Bd6xa3 23. h2h4 h7h6 24. Qc2d3 Ba3b4 25. Qd3b5 c7c5 26. Rd1d7 Qe7e4 27. Qb5xb7 Qe4xb7 28. Rd7xb7 Bb4xa5 29. Nf3e5 Ba5c3 30. Ne5c4 g7g5 31. h4xg5 h6xg5 32. Rb7c7 Bc3b4 33. Nc4d6 f7f6 34. Nd6f5 Rf8e8 35. Rc7c6 Re8f8 36. e3e4 Kg8f7 37. Rc6c7 Kf7g8 38. Kg1h2 Rf8a8 39. Kh2h3 Kg8f8 40. f2f3 Ra8a6 41. Kh3g4 Ra6a2 42. Kg4h5 Ra2a6 43. Kh5g4 Kf8e8 44. Nf5e7 Ke8f7 45. Ne7f5 Kf7e8 46. Nf5e7 Ke8f7 47. Kg4f5 Bb4a5 48. Rc7b7 Kf7e8 49. Ne7d5 Ba5d8 50. Rb7c7 c5c4 51. Rc7xc4 Ke8d7 52. Rc4c3 Ra6a5 53. Kf5g6 Ra5a6 54. Kg6f5 Kd7e8 55. Rc3b3 Ra6d6 56. Rb3b8 Ke8d7 57. Rb8b7 Kd7e8 58. Rb7a7 Rd6c6 59. g2g4 Ke8f8 60. Ra7h7 Rc6d6 61. Rh7a7 Rd6c6 62. Ra7d7 Kf8e8 63. Rd7b7 Rc6c5 64. Kf5g6 Rc5c6 65. Rb7a7 Rc6e6 66. Ra7a3 Ke8d7 67. Ra3a8 Re6d6 68. Kg6f5 Rd6c6 69. Ra8a3 Kd7e8 70. Ra3a8 Ke8d7 71. Ra8a7 Kd7e8 72. Ra7h7 Rc6d6 73. Rh7a7 Rd6c6 74. Kf5g6 Rc6d6 75. Ra7g7 Rd6c6 76. Rg7g8 Ke8d7 77. Rg8h8 Rc6d6 78. Kg6f5 Kd7c6 79. Rh8f8 Kc6c5 80. Nd5xf6 Bd8xf6 81. Rf8xf6 Rd6xf6 82. Kf5xf6 Kc5d4 83. e4e5 Kd4e3 84. e5e6 Ke3f4 85. e6e7 Kf4xf3 86. Kf6xg5 Kf3e4 87. Kg5g6 Ke4e3 88. g4g5 Ke3e4 89. Kg6f7 Ke4d5 90. g5g6 Kd5d4 91. Kf7e6 Kd4c4 92. g6g7 Kc4d4 93. Ke6d7 Kd4e3 94. e7e8=Q Ke3d3 95. g7g8=Q Kd3c3 96. Qe8e5 Kc3b4 97. Qg8b8 Kb4a3

ArnoHu

P-P-C wrote:
Here is a game against a 2600 ELO bot from chess.com

Bot : White
GoK : Black
Accuracy : 87.0/81.4
Winner : Bot
Lenght : 98 moves

1. d2d4 d7d5 2. e2e3 Ng8f6 3. c2c4 Nb8c6 4. Nb1c3 e7e6 5. Ng1f3 Bf8b4 6. Bc1d2 O-O 7. Bf1d3 d5xc4 8. Bd3xc4 e6e5 9. Nf3xe5 Nc6xe5 10. d4xe5 Nf6g4 11. O-O Ng4xe5 12. Bc4e2 Bc8e6 13. Qd1c2 Be6c4 14. Be2xc4 Ne5xc4 15. Rf1d1 Qd8h4 16. Nc3e4 Nc4xd2 17. Ne4xd2 Ra8d8 18. Nd2f3 Rd8xd1 19. Ra1xd1 Qh4e7 20. a2a3 Bb4d6 21. b2b4 a7a5 22. b4xa5 Bd6xa3 23. h2h4 h7h6 24. Qc2d3 Ba3b4 25. Qd3b5 c7c5 26. Rd1d7 Qe7e4 27. Qb5xb7 Qe4xb7 28. Rd7xb7 Bb4xa5 29. Nf3e5 Ba5c3 30. Ne5c4 g7g5 31. h4xg5 h6xg5 32. Rb7c7 Bc3b4 33. Nc4d6 f7f6 34. Nd6f5 Rf8e8 35. Rc7c6 Re8f8 36. e3e4 Kg8f7 37. Rc6c7 Kf7g8 38. Kg1h2 Rf8a8 39. Kh2h3 Kg8f8 40. f2f3 Ra8a6 41. Kh3g4 Ra6a2 42. Kg4h5 Ra2a6 43. Kh5g4 Kf8e8 44. Nf5e7 Ke8f7 45. Ne7f5 Kf7e8 46. Nf5e7 Ke8f7 47. Kg4f5 Bb4a5 48. Rc7b7 Kf7e8 49. Ne7d5 Ba5d8 50. Rb7c7 c5c4 51. Rc7xc4 Ke8d7 52. Rc4c3 Ra6a5 53. Kf5g6 Ra5a6 54. Kg6f5 Kd7e8 55. Rc3b3 Ra6d6 56. Rb3b8 Ke8d7 57. Rb8b7 Kd7e8 58. Rb7a7 Rd6c6 59. g2g4 Ke8f8 60. Ra7h7 Rc6d6 61. Rh7a7 Rd6c6 62. Ra7d7 Kf8e8 63. Rd7b7 Rc6c5 64. Kf5g6 Rc5c6 65. Rb7a7 Rc6e6 66. Ra7a3 Ke8d7 67. Ra3a8 Re6d6 68. Kg6f5 Rd6c6 69. Ra8a3 Kd7e8 70. Ra3a8 Ke8d7 71. Ra8a7 Kd7e8 72. Ra7h7 Rc6d6 73. Rh7a7 Rd6c6 74. Kf5g6 Rc6d6 75. Ra7g7 Rd6c6 76. Rg7g8 Ke8d7 77. Rg8h8 Rc6d6 78. Kg6f5 Kd7c6 79. Rh8f8 Kc6c5 80. Nd5xf6 Bd8xf6 81. Rf8xf6 Rd6xf6 82. Kf5xf6 Kc5d4 83. e4e5 Kd4e3 84. e5e6 Ke3f4 85. e6e7 Kf4xf3 86. Kf6xg5 Kf3e4 87. Kg5g6 Ke4e3 88. g4g5 Ke3e4 89. Kg6f7 Ke4d5 90. g5g6 Kd5d4 91. Kf7e6 Kd4c4 92. g6g7 Kc4d4 93. Ke6d7 Kd4e3 94. e7e8=Q Ke3d3 95. g7g8=Q Kd3c3 96. Qe8e5 Kc3b4 97. Qg8b8 Kb4a3

Thank you, very helpful. GoK should actually see the (same) mistake at move 44 and 46. I will take a closer look.

ArnoHu

ArnoHu wrote:
P-P-C wrote:
Here is a game against a 2600 ELO bot from chess.com

Bot : White
GoK : Black
Accuracy : 87.0/81.4
Winner : Bot
Lenght : 98 moves

1. d2d4 d7d5 2. e2e3 Ng8f6 3. c2c4 Nb8c6 4. Nb1c3 e7e6 5. Ng1f3 Bf8b4 6. Bc1d2 O-O 7. Bf1d3 d5xc4 8. Bd3xc4 e6e5 9. Nf3xe5 Nc6xe5 10. d4xe5 Nf6g4 11. O-O Ng4xe5 12. Bc4e2 Bc8e6 13. Qd1c2 Be6c4 14. Be2xc4 Ne5xc4 15. Rf1d1 Qd8h4 16. Nc3e4 Nc4xd2 17. Ne4xd2 Ra8d8 18. Nd2f3 Rd8xd1 19. Ra1xd1 Qh4e7 20. a2a3 Bb4d6 21. b2b4 a7a5 22. b4xa5 Bd6xa3 23. h2h4 h7h6 24. Qc2d3 Ba3b4 25. Qd3b5 c7c5 26. Rd1d7 Qe7e4 27. Qb5xb7 Qe4xb7 28. Rd7xb7 Bb4xa5 29. Nf3e5 Ba5c3 30. Ne5c4 g7g5 31. h4xg5 h6xg5 32. Rb7c7 Bc3b4 33. Nc4d6 f7f6 34. Nd6f5 Rf8e8 35. Rc7c6 Re8f8 36. e3e4 Kg8f7 37. Rc6c7 Kf7g8 38. Kg1h2 Rf8a8 39. Kh2h3 Kg8f8 40. f2f3 Ra8a6 41. Kh3g4 Ra6a2 42. Kg4h5 Ra2a6 43. Kh5g4 Kf8e8 44. Nf5e7 Ke8f7 45. Ne7f5 Kf7e8 46. Nf5e7 Ke8f7 47. Kg4f5 Bb4a5 48. Rc7b7 Kf7e8 49. Ne7d5 Ba5d8 50. Rb7c7 c5c4 51. Rc7xc4 Ke8d7 52. Rc4c3 Ra6a5 53. Kf5g6 Ra5a6 54. Kg6f5 Kd7e8 55. Rc3b3 Ra6d6 56. Rb3b8 Ke8d7 57. Rb8b7 Kd7e8 58. Rb7a7 Rd6c6 59. g2g4 Ke8f8 60. Ra7h7 Rc6d6 61. Rh7a7 Rd6c6 62. Ra7d7 Kf8e8 63. Rd7b7 Rc6c5 64. Kf5g6 Rc5c6 65. Rb7a7 Rc6e6 66. Ra7a3 Ke8d7 67. Ra3a8 Re6d6 68. Kg6f5 Rd6c6 69. Ra8a3 Kd7e8 70. Ra3a8 Ke8d7 71. Ra8a7 Kd7e8 72. Ra7h7 Rc6d6 73. Rh7a7 Rd6c6 74. Kf5g6 Rc6d6 75. Ra7g7 Rd6c6 76. Rg7g8 Ke8d7 77. Rg8h8 Rc6d6 78. Kg6f5 Kd7c6 79. Rh8f8 Kc6c5 80. Nd5xf6 Bd8xf6 81. Rf8xf6 Rd6xf6 82. Kf5xf6 Kc5d4 83. e4e5 Kd4e3 84. e5e6 Ke3f4 85. e6e7 Kf4xf3 86. Kf6xg5 Kf3e4 87. Kg5g6 Ke4e3 88. g4g5 Ke3e4 89. Kg6f7 Ke4d5 90. g5g6 Kd5d4 91. Kf7e6 Kd4c4 92. g6g7 Kc4d4 93. Ke6d7 Kd4e3 94. e7e8=Q Ke3d3 95. g7g8=Q Kd3c3 96. Qe8e5 Kc3b4 97. Qg8b8 Kb4a3

Thank you, very helpful. GoK should actually see the (same) mistake at move 44 and 46. I will take a closer look.

I just made late move reduction more aggressive in the dev version, and it finds the right move in 47 seconds (press ‘c’ for longer think time)

ArnoHu

New GoK Version

I just uploaded GoK Chess 6.136, which comes with an improved late move reduction / principal variation search implementation. The first test games show promising results. I am interested in feedback about the effects on playing strength. Thank you!

ArnoHu

ArnoHu wrote:
New GoK Version

I just uploaded GoK Chess 6.136, which comes with an improved late move reduction / principal variation search implementation. The first test games show promising results. I am interested in feedback about the effects on playing strength. Thank you!

In a test game series of 10 games against Bonsai Blue, GoK Medium's accuracy level on Scratch 3 has increased to 90%, compared to 88% in the previous two series. GoK won all 10 games this time.

Here is the code changeset if someone is interested: https://github.com/ArnoHue/scratch/commit/524d43a37fa2cd6c98b57fbba48326bb0b157d47

Last edited by ArnoHu (July 1, 2023 06:23:23)

ArnoHu

GoK Chess 6.141 (TurboWarp) draws against Stockfish 14 Level 7

After some initial advantage for GoK (white), the game balanced out, and ended in a draw: https://lichess.org/p6yvy9Ym#127

Grijfland

ArnoHu wrote:
GoK Chess 6.141 (TurboWarp) draws against Stockfish 14 Level 7

After some initial advantage for GoK (white), the game balanced out, and ended in a draw: https://lichess.org/p6yvy9Ym#127

I am speechless. Congratulations on these improvements.

S_P_A_R_T_Test

@ArnoHu

It's been quite a while, but I'm back developing White Dove! I've done tons of research on transposition tables, but I feel like implementing faster move generation would be a priority. (As so much time is dedicated to move generation)

I've have a basic version where in the move generation code loop, has a if else statement, that if the move generation can be “pseudo-legal”, and isn't castling, it skips the complicated (and slow) part of the code to check for pins, and pinned directions.

I have yet to add the checkmate or stalemate detection, so I've been testing in the opening (specifically, opening that aren't in the book), and I haven't noticed an improvement in performance.

I was wondering how I should implement the “pseudo-legal” move generation.

I test

ArnoHu

S_P_A_R_T_Test wrote:
@ArnoHu

It's been quite a while, but I'm back developing White Dove! I've done tons of research on transposition tables, but I feel like implementing faster move generation would be a priority. (As so much time is dedicated to move generation)

I've have a basic version where in the move generation code loop, has a if else statement, that if the move generation can be “pseudo-legal”, and isn't castling, it skips the complicated (and slow) part of the code to check for pins, and pinned directions.

I have yet to add the checkmate or stalemate detection, so I've been testing in the opening (specifically, opening that aren't in the book), and I haven't noticed an improvement in performance.

I was wondering how I should implement the “pseudo-legal” move generation.

Hi, I think I have talked about that before, there is no need to check for pins at all in general purpose move generation. GoK does not do this, and I am not aware of any other chess engines doing it either. Moving a pinned piece would lead to a virtual king capture (you should implement that), hence the worst possible evaluation, hence will be pruned.

Another pseudo-legal but invalid move is placing the king onto an attacked square. The same holds true here, you don't have to implement any verification at all for this if you don't want to, as a virtual king capture on the next move would follow, again leading to the move never being considered. GoK still does this verification if attack info is available, as it is slightly faster to exclude the invalid move upfront, than to generate the next ply's moves, including the virtual king capture.

Stalemate detection just means you did not find any legal moves during full search, no extra code required.

Last edited by ArnoHu (July 15, 2023 03:12:04)

S_P_A_R_T

Ok thank you! I still have 2 questions.

1. If for example, the position is this. And rook g8 is played, it is a stalemate, but if for example, the engine is calculating, it finds that every move will result in a virtual king capture the next turn.

But, if rook b1 is played, it is checkmate, but still any move that the opponent plays, will again result in a virtual king capture. The difference being, whether it starts in check or not, do I need to include “check” information in stalemate detection?

2. How should castling be implemented during checks. As it technically doesn't allow a virtual king capture, though still being illegal.

Thank you!

Check out Space Program Simulator!

In it, you can build your own rockets from a variety of parts!
Then fly it with realistic orbital mechanics.

Go to orbit, explore different planets, share your save codes, and do so much more!

If you would like to help out on the project or chat about space or really anything else, check out the offical SPS Studio!

For more information & tutorials, check out the offical forum post!

Discuss Scratch