Scratch Chess Engine - Game of Kings

S_P_A_R_T

Yes, GoK is truly unmatched!

Also, @ArnoHu , I have a question.

I've been doing some reading for Move Gen, and I found this article, that says legal move gen is faster than pseudo-legal move gen, is this because of the bitboard in other programming languages, or could (properly implemented) legal move gen have the same (or better) performance on Scratch?

Thanks!

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!

HasiLover

Something Crazy just happened,i made GOK play LC0 and LC0 straight up crashed against it O:

Edit:I did make it work,again, in the end LC0 won in 47Moves,with an 98%accuracy against Gok with an 92% accuracy,this is the game link:https://lichess.org/study/aElNEByx/h6OqdFeV

Last edited by HasiLover (Aug. 31, 2023 12:25:29)

S_P_A_R_T

Uh oh

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

HasiLover wrote:
Something Crazy just happened,i made GOK play LC0 and LC0 straight up crashed against it O:

Edit:I did make it work,again, in the end LC0 won in 47Moves,with an 98%accuracy against Gok with an 92% accuracy,this is the game link:https://lichess.org/study/aElNEByx/h6OqdFeV

Thanks, GoK's mistake at move 8 actually was a bug that has been fixed by now.

ArnoHu

S_P_A_R_T wrote:
Yes, GoK is truly unmatched!

Also, @ArnoHu , I have a question.

I've been doing some reading for Move Gen, and I found this article, that says legal move gen is faster than pseudo-legal move gen, is this because of the bitboard in other programming languages, or could (properly implemented) legal move gen have the same (or better) performance on Scratch?

Thanks!

Thanks, that is a really good article. Well it depends, but as you said, we cannot implement bitboards on Scratch (no 64bit ints, no bitwise ops), and creating an equivalent logic in Scratch for pinned pieces, etc. will be very slow in comparison.

Still there are some things we can do. GoK does create attack tables, but only for the first plies, and for later plies lazily in case a king move is going to be applied (article part 1). GoK also generates check evasions when in check (part 2). For most other scenarios, such as pinned pieces, GoK will apply pseudo-legal moves, but do a fast verification for checks right after that, before traversing further down any move sequence.

Last edited by ArnoHu (Sept. 1, 2023 05:19:59)

ArnoHu

HasiLover wrote:
ArnoHu wrote:
ArnoHu wrote:
Another GoK Chess vs. Stockfish Test Game

GoK Chess (TurboWarp, level Difficult, competition mode) held out 115 moves, before it lost against grandmaster-stage Stockfish 14 level 7 in this test game: https://lichess.org/RUKJQKEj#230 . 94% vs. 96% playing accuracy.

Next game was incredible - a draw after 48 moves, and a perfect game by both sides, with 0 blunders, 0 mistakes, 0 inaccuracies each. GoK white: https://lichess.org/qC8qo5OM#95
It seems like GOK truly is the greatest Scratch chess engine.

Well, I am not aware of another Scratch chess engine drawing or winning against Stockfish 14 level 7. GoK has won 3 games so far, but at the same time probably lost 20.

S_P_A_R_T

ArnoHu wrote:
S_P_A_R_T wrote:
Yes, GoK is truly unmatched!

Also, @ArnoHu , I have a question.

I've been doing some reading for Move Gen, and I found this article, that says legal move gen is faster than pseudo-legal move gen, is this because of the bitboard in other programming languages, or could (properly implemented) legal move gen have the same (or better) performance on Scratch?

Thanks!

Thanks, that is a really good article. Well it depends, but as you said, we cannot implement bitboards on Scratch (not 64bit ints, no bitwise ops), and creating an equivalent logic in Scratch for pinned pieces, etc. will be very slow in comparison.

Still there are some things we can do. GoK does create attack tables, but only for the first plies, and for later plies lazily in case a king move is going to be applied (article part 1). GoK also generates check evasions when in check (part 2). For most other scenarios, such as pinned pieces, GoK will apply pseudo-legal moves, but do a fast verification for checks right after that, before traversing further down any move sequence.

Hmmm, thanks! I think I will get back into chess programming & WD dev soon! (I'm still playing chess.com and school starts soon, but I hope I'll be able to make WD good enough to share with the chess club

)

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:
ArnoHu wrote:
S_P_A_R_T wrote:
Yes, GoK is truly unmatched!

Also, @ArnoHu , I have a question.

I've been doing some reading for Move Gen, and I found this article, that says legal move gen is faster than pseudo-legal move gen, is this because of the bitboard in other programming languages, or could (properly implemented) legal move gen have the same (or better) performance on Scratch?

Thanks!

Thanks, that is a really good article. Well it depends, but as you said, we cannot implement bitboards on Scratch (not 64bit ints, no bitwise ops), and creating an equivalent logic in Scratch for pinned pieces, etc. will be very slow in comparison.

Still there are some things we can do. GoK does create attack tables, but only for the first plies, and for later plies lazily in case a king move is going to be applied (article part 1). GoK also generates check evasions when in check (part 2). For most other scenarios, such as pinned pieces, GoK will apply pseudo-legal moves, but do a fast verification for checks right after that, before traversing further down any move sequence.

Hmmm, thanks! I think I will get back into chess programming & WD dev soon! (I'm still playing chess.com and school starts soon, but I hope I'll be able to make WD good enough to share with the chess club )

Cool!

Forgot to mention, one of the reasons why this article is so good is the following clarification:

a good position evaluator is more valuable than a fast move generator. Although fast move generator can try more potential moves, a good position evaluation can help you prune huge chunks off the search tree, massively reducing the number of positions you need to search.

That's exactly it! Move generator tuning beyond a certain point won't help that much more, the most important thing then is good move ordering.

S_P_A_R_T

By position evaluator, does it mean the “real” eval at the end of each branch, or does it mean the “rough” move ordering eval?

Also, how would I get the NPS on WD?

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:
By position evaluator, does it mean the “real” eval at the end of each branch, or does it mean the “rough” move ordering eval?

Also, how would I get the NPS on WD?

It refers to move ordering. But of course leaf evaluation must be good (and fast) as well.

NPS: Just count each move applied resp. the resulting board evaluations. High NPS is good of course, but again, a lot more important is move ordering. Like it is better to have 1,000 NPS on Scratch with great move ordering than 10,000 NPS with bad move ordering.

So another important metric is the position of the best move within the move list (but you only know later, after full subtree traversal, how good the move really was). And the number of moves you generate (compared to the number of moves you apply / traverse). See https://scratch.mit.edu/discuss/post/7455708/ for details.

On my system, GoK currently reaches up to 300,000 generated moves per second (MPS) and 250,000 applied moves per second (NPS) on TurboWarp, and 6,000 MPS / 5,000 NPS on Scratch 3, at an average “best move list index” of 1.25 during full search.

Last edited by ArnoHu (Sept. 1, 2023 05:22:48)

ArnoHu

Important GoK Chess Bugfix

I finally found the root cause for occasionally wrong move selections in GoK Chess, which were only reproducible with pre-filled transposition table. Up during null move searches, the reduced search depth did not consider search extensions, which led to cached evaluation values with wrong search horizon meta info.

GoK 6.177 resolves those cases of wrong move selection, and while additional tests are stil ongoing, the improvement resulted in this beautiful win of GoK (Scratch 3, Difficult) against Bonsai Blue: https://lichess.org/Z22Gpx41#89. Bonsai played a great game at 92% accuracy, GoK was at 96%.

Last edited by ArnoHu (Sept. 10, 2023 17:44:26)

HasiLover

I will make a Rematch between Gok and Lc0

HasiLover

I made it and it was Crazy, both Engines made Blunders,GoK was down two Pawns and somehow got into a Drawn Endgame,but then it lost another Pawn and lost in the end.Both Engines played an accuracy of 91% This is the game:https://lichess.org/study/aElNEByx/tqEPCPW4

Last edited by HasiLover (Sept. 10, 2023 10:14:57)

HasiLover

Also i think you should maybe look for more Bugs in GoK,since it made its Blunder on Move 7

ArnoHu

HasiLover wrote:
I made it and it was Crazy, both Engines made Blunders,GoK was down two Pawns and somehow got into a Drawn Endgame,but then it lost another Pawn and lost in the end.Both Engines played an accuracy of 91% This is the game:https://lichess.org/study/aElNEByx/tqEPCPW4

I could not reproduce white's blunder on move 38, GoK discards Rh4 after 1 second on TurboWarp. I suppose this was run on TurboWarp / Difficult? Competition mode?

ArnoHu

HasiLover wrote:
Also i think you should maybe look for more Bugs in GoK,since it made its Blunder on Move 7

I am not aware of any other bugs, those blunders don't show their effect until much later, beyond the search horizon. Making a wrong move selection is not necessarily a bug. A wrong move is most likely caused by the slowness of Scratch 3 (and by extension, the backward compatibility limitations of TurboWarp). On a (much) faster Scratch runtime, those suboptimal moves would not happen - same code though.

birdracerthree

ArnoHu wrote:
HasiLover wrote:
Also i think you should maybe look for more Bugs in GoK,since it made its Blunder on Move 7

I am not aware of any other bugs, those blunders don't show their effect until much later, beyond the search horizon. Making a wrong move selection is not necessarily a bug. A wrong move is most likely caused by the slowness of Scratch 3 (and by extension, the backward compatibility limitations of TurboWarp). On a (much) faster Scratch runtime, those suboptimal moves would not happen - same code though.

Does anyone know why 1. Nf3 is a blunder, 2. Why didn't GoK take the pawn trade on g7 (instead of just leaving the pawn) and 3. Why gxf6 is so much better than Qxf6?

HasiLover

ArnoHu wrote:
HasiLover wrote:
I made it and it was Crazy, both Engines made Blunders,GoK was down two Pawns and somehow got into a Drawn Endgame,but then it lost another Pawn and lost in the end.Both Engines played an accuracy of 91% This is the game:https://lichess.org/study/aElNEByx/tqEPCPW4

I could not reproduce white's blunder on move 38, GoK discards Rh4 after 1 second on TurboWarp. I suppose this was run on TurboWarp / Difficult? Competition mode?

Turbowarp,with turbo mode

birdracerthree

HasiLover wrote:
ArnoHu wrote:
HasiLover wrote:
I made it and it was Crazy, both Engines made Blunders,GoK was down two Pawns and somehow got into a Drawn Endgame,but then it lost another Pawn and lost in the end.Both Engines played an accuracy of 91% This is the game:https://lichess.org/study/aElNEByx/tqEPCPW4

I could not reproduce white's blunder on move 38, GoK discards Rh4 after 1 second on TurboWarp. I suppose this was run on TurboWarp / Difficult? Competition mode?
Turbowarp,with turbo mode

I tested it myself, on GoK Medium, it never considered Rh4 (it was between Rxb7, Rc3 and Ree4 in that order) the 2nd time I ran it. The 3rd time, it played Rh4.

birdracerthree

Element is finally working as it should! I'll do a few more things before improving the eval

Discuss Scratch