Discuss Scratch
- Discussion Forums
- » Show and Tell
- » Scratch Chess Engine - Game of Kings
- HasiLover_Test
-
100+ posts
Scratch Chess Engine - Game of Kings
https://lichess.org/5kXtjSQY#143Impressive Game, both GoK Versions played close to perfect Chess. Highest accuracy game, GoK 6.396 Medium (white) vs GoK 6.395 (black) on TurboWarp, draw in 72 moves, 96% vs 97% accuracy:
- ArnoHu
-
1000+ posts
Scratch Chess Engine - Game of Kings
https://lichess.org/5kXtjSQY#143Impressive Game, both GoK Versions played close to perfect Chess. Highest accuracy game, GoK 6.396 Medium (white) vs GoK 6.395 (black) on TurboWarp, draw in 72 moves, 96% vs 97% accuracy:
True, but also the way the game developed allowed for that to happen, was not the normal case :-)
Will the tournament start soon? I was a bit reluctant to upload the new GoK version shortly before, but I still did. It reduced LMR aggressiveness a bit.
Last edited by ArnoHu (March 14, 2024 05:40:52)
- ArnoHu
-
1000+ posts
Scratch Chess Engine - Game of Kings
Thank you for 700,000 GoK project visits!
When will we hit the 1,000,000 mark?
Throwback to one of the first tournaments in 2017: https://scratch.mit.edu/discuss/post/2936664/
That was still on Scratch 3 of course. GoK's accuracy in full-length games: 82%, 83%, 84%. But think time on Difficult was also longer back then, due to fix search depth up to a minute as far as I remember.
When will we hit the 1,000,000 mark?
Throwback to one of the first tournaments in 2017: https://scratch.mit.edu/discuss/post/2936664/
That was still on Scratch 3 of course. GoK's accuracy in full-length games: 82%, 83%, 84%. But think time on Difficult was also longer back then, due to fix search depth up to a minute as far as I remember.
Last edited by ArnoHu (March 14, 2024 06:37:19)
- HasiLover_Test
-
100+ posts
Scratch Chess Engine - Game of Kings
Thank you for 700,000 GoK project visits!Wow, 700000 visits is very Impressive, congrats and thank you so much for creating such an amazing Project.
When will we hit the 1,000,000 mark?
Throwback to one of the first tournaments in 2017: https://scratch.mit.edu/discuss/post/2936664/
That was still on Scratch 3 of course. GoK's accuracy in full-length games: 82%, 83%, 84%. But think time on Difficult was also longer back then, due to fix search depth up to a minute as far as I remember.
- HasiLover_Test
-
100+ posts
Scratch Chess Engine - Game of Kings
Yes, I am gonna hold it tomorrow, im still unsure if im gonna run it in TW or S3.https://lichess.org/5kXtjSQY#143Impressive Game, both GoK Versions played close to perfect Chess. Highest accuracy game, GoK 6.396 Medium (white) vs GoK 6.395 (black) on TurboWarp, draw in 72 moves, 96% vs 97% accuracy:
True, but also the way the game developed allowed for that to happen, was not the normal case :-)
Will the tournament start soon? I was a bit reluctant to upload the new GoK version shortly before, but I still did. It reduced LMR aggressiveness a bit.
- HasiLover_Test
-
100+ posts
Scratch Chess Engine - Game of Kings
I wanted to ask, I noticed Thundershark only looked around 200k - 300K nodes, but Scurious sometimes even looks at 1Mio. Nodes, why is there such a difference when they both use AB Pruning?
- birdracerthree
-
500+ posts
Scratch Chess Engine - Game of Kings
This is the importance of move ordering. Scurious’ move ordering is very non-standard. I have no idea how you detect checks and run the program so quickly. Element uses MVV-LVA + Piece Square Tables. Try to use MVV-LVA when ordering captures. Then, use piece-square tables for the “quiet moves”. MVV-LVA alone should make a big difference. I ran a test with stable Element (5+8). It reaches 100k-200k nodes. 50k-100k when running 5+0. I wanted to ask, I noticed Thundershark only looked around 200k - 300K nodes, but Scurious sometimes even looks at 1Mio. Nodes, why is there such a difference when they both use AB Pruning?
- birdracerthree
-
500+ posts
Scratch Chess Engine - Game of Kings
Thank you for 700,000 GoK project visits!Actually, this was run on Scratch 2
When will we hit the 1,000,000 mark?
Throwback to one of the first tournaments in 2017: https://scratch.mit.edu/discuss/post/2936664/
That was still on Scratch 3 of course. GoK's accuracy in full-length games: 82%, 83%, 84%. But think time on Difficult was also longer back then, due to fix search depth up to a minute as far as I remember.
![](http://cdn.scratch.mit.edu/scratchr2/static/__74e70580e9dbe93ce1c3f8422dde592d__/djangobb_forum/img/smilies/smile.png)
Last edited by birdracerthree (March 14, 2024 16:15:06)
- HasiLover_Test
-
100+ posts
Scratch Chess Engine - Game of Kings
Thanks alot, I will try to implement MVV-LVA.This is the importance of move ordering. Scurious’ move ordering is very non-standard. I have no idea how you detect checks and run the program so quickly. Element uses MVV-LVA + Piece Square Tables. Try to use MVV-LVA when ordering captures. Then, use piece-square tables for the “quiet moves”. MVV-LVA alone should make a big difference. I ran a test with stable Element (5+8). It reaches 100k-200k nodes. 50k-100k when running 5+0. I wanted to ask, I noticed Thundershark only looked around 200k - 300K nodes, but Scurious sometimes even looks at 1Mio. Nodes, why is there such a difference when they both use AB Pruning?
- ArnoHu
-
1000+ posts
Scratch Chess Engine - Game of Kings
Thank you for 700,000 GoK project visits!Actually, this was run on Scratch 2
When will we hit the 1,000,000 mark?
Throwback to one of the first tournaments in 2017: https://scratch.mit.edu/discuss/post/2936664/
That was still on Scratch 3 of course. GoK's accuracy in full-length games: 82%, 83%, 84%. But think time on Difficult was also longer back then, due to fix search depth up to a minute as far as I remember.Was Forkphorus/Phosphorus still a thing at the time? I think Turbowarp was released in 2020. I didn’t find out until 2 years later (around the time when the url was changing to .xyz).
True, it was Scratch 2. Before Forkphorus there was Sulfurous, and the first reference I found was right after the 2017 tournament: https://scratch.mit.edu/discuss/post/2942887/ And wow, GoK already played a perfect game then at 97%. I wonder if all the improvements since even paid off at all?
![](http://cdn.scratch.mit.edu/scratchr2/static/__74e70580e9dbe93ce1c3f8422dde592d__/djangobb_forum/img/smilies/smile.png)
- ArnoHu
-
1000+ posts
Scratch Chess Engine - Game of Kings
Thanks alot, I will try to implement MVV-LVA.This is the importance of move ordering. Scurious’ move ordering is very non-standard. I have no idea how you detect checks and run the program so quickly. Element uses MVV-LVA + Piece Square Tables. Try to use MVV-LVA when ordering captures. Then, use piece-square tables for the “quiet moves”. MVV-LVA alone should make a big difference. I ran a test with stable Element (5+8). It reaches 100k-200k nodes. 50k-100k when running 5+0. I wanted to ask, I noticed Thundershark only looked around 200k - 300K nodes, but Scurious sometimes even looks at 1Mio. Nodes, why is there such a difference when they both use AB Pruning?
Yes, I would expect move ordering to be a main reason. Also there are more pruning techniques, transposition tables, staged move generator, …
And of course the way NPS are calculated, that can differ quite a lot.
E.g. GoK spends a lot of time in creating attack tables, that does not count of course, but is just another way to run its move generator.
BTW, there is something off I think with Scurious's NPS calculation, because a wait(1) when the engine is running, keeping the CPU busy, is no guarantee for a 1 second delay until code execution. I took timer snapshots, and on Scratch 3 the NPS calculation happened every 1.5 seconds in average, on TurboWarp every 1.2 seconds.
I was also wondering what you meant by “200k - 300K nodes”, “1 million nodes”. For what kind of search (board, depth)? Per second? Per search run? Including quiescence?
Last edited by ArnoHu (March 14, 2024 20:43:50)
- ArnoHu
-
1000+ posts
Scratch Chess Engine - Game of Kings
Thank you for 700,000 GoK project visits!Wow, 700000 visits is very Impressive, congrats and thank you so much for creating such an amazing Project.
When will we hit the 1,000,000 mark?
Throwback to one of the first tournaments in 2017: https://scratch.mit.edu/discuss/post/2936664/
That was still on Scratch 3 of course. GoK's accuracy in full-length games: 82%, 83%, 84%. But think time on Difficult was also longer back then, due to fix search depth up to a minute as far as I remember.
Thank you!
- birdracerthree
-
500+ posts
Scratch Chess Engine - Game of Kings
I think now is a good time to mention the broken Ruy Lopez book in GoK. 1. e4 e5 2. Nf3 Nc6 3. Bb5 a6 4. Ba4 Nf6 5. O-O Be7 6. Re1 O-O? (correct move is 6…b5 7. Bb3 O-O or 7…d6Thank you for 700,000 GoK project visits!Wow, 700000 visits is very Impressive, congrats and thank you so much for creating such an amazing Project.
When will we hit the 1,000,000 mark?
Throwback to one of the first tournaments in 2017: https://scratch.mit.edu/discuss/post/2936664/
That was still on Scratch 3 of course. GoK's accuracy in full-length games: 82%, 83%, 84%. But think time on Difficult was also longer back then, due to fix search depth up to a minute as far as I remember.
Thank you!
I found a reference to it here https://scratch.mit.edu/discuss/topic/248984/?page=60#post-7545827 and here https://lichess.org/study/MSjgYtQd/XHbimh8M#12, the latter in 2017. There is also the Halloween Gambit book issue.
- ArnoHu
-
1000+ posts
Scratch Chess Engine - Game of Kings
Thanks alot, I will try to implement MVV-LVA.This is the importance of move ordering. Scurious’ move ordering is very non-standard. I have no idea how you detect checks and run the program so quickly. Element uses MVV-LVA + Piece Square Tables. Try to use MVV-LVA when ordering captures. Then, use piece-square tables for the “quiet moves”. MVV-LVA alone should make a big difference. I ran a test with stable Element (5+8). It reaches 100k-200k nodes. 50k-100k when running 5+0. I wanted to ask, I noticed Thundershark only looked around 200k - 300K nodes, but Scurious sometimes even looks at 1Mio. Nodes, why is there such a difference when they both use AB Pruning?
Yes, I would expect move ordering to be a main reason. Also there are more pruning techniques, transposition tables, staged move generator, …
And of course the way NPS are calculated, that can differ quite a lot.
E.g. GoK spends a lot of time in creating attack tables, that does not count of course, but is just another way to run its move generator.
BTW, there is something off I think with Scurious's NPS calculation, because a wait(1) when the engine is running, keeping the CPU busy, is no guarantee for a 1 second delay until code execution. I took timer snapshots, and on Scratch 3 the NPS calculation happened every 1.5 seconds in average, on TurboWarp every 1.2 seconds.
I was also wondering what you meant by “200k - 300K nodes”, “1 million nodes”. For what kind of search (board, depth)? Per second? Per search run? Including quiescence?
Some more numbers, I imported “rnbqkbnr/pppp1ppp/8/4p3/8/4P2P/PPPP1PP1/RNBQKBNR b KQkq - 0 2” to Scurious, and for 4 plies it searched 63,000 nodes. GoK searched 7,200 nodes for the same 4 plies, and 180,000 nodes for 8 plies. For ply4, Scurious was done in a second, GoK in 0.16 seconds. For ply8, GoK took less than 2 seconds. White Dove needs 13 seconds to finish ply8.
Scurious's NPS in general runs at similar or slightly higher level than GoK's - I expect most time is used for move generation, and the generator must be really fast. But one would have to make it 9 times faster again to make up for the lower cutoff rate, and the evaluation would still be a topic. And that is for 4 plies, the number explodes with increasing search depth.
That is why pruning and move ordering are of uttermost importance. GoK gained half a ply on TurboWarp using history tables instead of piece square tables for ordering, and close to a ply by making LMR a bit more aggressive. If there is a decent move generator already, it is nearly impossible to gain a ply by any additional tunings on the move generator itself.
Thanks to staged move generator and early cutoff rates, GoK just has to generate only slightly more moves than nodes evaluated (typically around +20%)
Thundershark searched 195,000 nodes for the same board, and took 7 seconds. And it has 5 plies without quiescence I think?
Last edited by ArnoHu (March 15, 2024 04:39:44)
- birdracerthree
-
500+ posts
Scratch Chess Engine - Game of Kings
The mate scores are actually from virtual king captures. No nodes are stored in quiescence, and as of right now it is the only know TTable bug in Element.How do I deal with checkmate evaluations in a transposition table? They occur in the search setup and they stop the script like a beta-cutoff, but my TTable is having issues with the mate evaluations.
The table is giving Element a non-mate evaluation when it should be a mate evaluation.
We would have to see the code, it might have to do with whether the evaluation is exact our alpha/beta-bound. In general that topic is not all trivial, e.g. when in check you cannot apply standing pat. I have also seen engines not storing mate evals during quiescence, maybe you want to do the same in the meantime.
The statement about being in check isn’t relevant here (no check extension in Element, although I’ll have to put that in eventually, so it’s good to know).
Element’s “search” function does things like move generation and move ordering. It is the setup for the “negamax” function. A king capture check is run in the search function.
Last edited by birdracerthree (March 15, 2024 03:56:29)
- HasiLover_Test
-
100+ posts
Scratch Chess Engine - Game of Kings
Scurious 5 Ply in the Position rnbqkbnr/pppp1ppp/8/4p3/8/4P2P/PPPP1PP1/RNBQKBNR b KQkq - 0 2 had around 961 Tousand Nodes and on my system around 7 seconds aswell. It runs with an i5 intel coreThanks alot, I will try to implement MVV-LVA.This is the importance of move ordering. Scurious’ move ordering is very non-standard. I have no idea how you detect checks and run the program so quickly. Element uses MVV-LVA + Piece Square Tables. Try to use MVV-LVA when ordering captures. Then, use piece-square tables for the “quiet moves”. MVV-LVA alone should make a big difference. I ran a test with stable Element (5+8). It reaches 100k-200k nodes. 50k-100k when running 5+0. I wanted to ask, I noticed Thundershark only looked around 200k - 300K nodes, but Scurious sometimes even looks at 1Mio. Nodes, why is there such a difference when they both use AB Pruning?
Yes, I would expect move ordering to be a main reason. Also there are more pruning techniques, transposition tables, staged move generator, …
And of course the way NPS are calculated, that can differ quite a lot.
E.g. GoK spends a lot of time in creating attack tables, that does not count of course, but is just another way to run its move generator.
BTW, there is something off I think with Scurious's NPS calculation, because a wait(1) when the engine is running, keeping the CPU busy, is no guarantee for a 1 second delay until code execution. I took timer snapshots, and on Scratch 3 the NPS calculation happened every 1.5 seconds in average, on TurboWarp every 1.2 seconds.
I was also wondering what you meant by “200k - 300K nodes”, “1 million nodes”. For what kind of search (board, depth)? Per second? Per search run? Including quiescence?
Some more numbers, I imported “rnbqkbnr/pppp1ppp/8/4p3/8/4P2P/PPPP1PP1/RNBQKBNR b KQkq - 0 2” to Scurious, and for 4 plies it searched 63,000 nodes. GoK searched 7,200 nodes for the same 4 plies, and 180,000 nodes for 8 plies. For ply4, Scurious was done in a second, GoK in 0.16 seconds. For ply8, GoK took less than 2 seconds. White Dove needs 13 seconds to finish ply8.
Scurious's NPS in general runs at similar or slightly higher level than GoK's - I expect most time is used for move generation, and the generator must be really fast. But one would have to make it 9 times faster again to make up for the lower cutoff rate, and the evaluation would still be a topic. And that is for 4 plies, the number explodes with increasing search depth.
Thanks to staged move generator and early cutoff rates, GoK just has to generate only slightly more moves than nodes evaluated (typically around +20%)
Thundershark searched 195,000 nodes for the same board, and took 7 seconds. And it has 5 plies without quiescence I think?
Last edited by HasiLover_Test (March 15, 2024 04:38:30)
- ArnoHu
-
1000+ posts
Scratch Chess Engine - Game of Kings
Scurious 5 Ply in the Position rnbqkbnr/pppp1ppp/8/4p3/8/4P2P/PPPP1PP1/RNBQKBNR b KQkq - 0 2 had around 961 Tousand Nodes.Thanks alot, I will try to implement MVV-LVA.This is the importance of move ordering. Scurious’ move ordering is very non-standard. I have no idea how you detect checks and run the program so quickly. Element uses MVV-LVA + Piece Square Tables. Try to use MVV-LVA when ordering captures. Then, use piece-square tables for the “quiet moves”. MVV-LVA alone should make a big difference. I ran a test with stable Element (5+8). It reaches 100k-200k nodes. 50k-100k when running 5+0. I wanted to ask, I noticed Thundershark only looked around 200k - 300K nodes, but Scurious sometimes even looks at 1Mio. Nodes, why is there such a difference when they both use AB Pruning?
Yes, I would expect move ordering to be a main reason. Also there are more pruning techniques, transposition tables, staged move generator, …
And of course the way NPS are calculated, that can differ quite a lot.
E.g. GoK spends a lot of time in creating attack tables, that does not count of course, but is just another way to run its move generator.
BTW, there is something off I think with Scurious's NPS calculation, because a wait(1) when the engine is running, keeping the CPU busy, is no guarantee for a 1 second delay until code execution. I took timer snapshots, and on Scratch 3 the NPS calculation happened every 1.5 seconds in average, on TurboWarp every 1.2 seconds.
I was also wondering what you meant by “200k - 300K nodes”, “1 million nodes”. For what kind of search (board, depth)? Per second? Per search run? Including quiescence?
Some more numbers, I imported “rnbqkbnr/pppp1ppp/8/4p3/8/4P2P/PPPP1PP1/RNBQKBNR b KQkq - 0 2” to Scurious, and for 4 plies it searched 63,000 nodes. GoK searched 7,200 nodes for the same 4 plies, and 180,000 nodes for 8 plies. For ply4, Scurious was done in a second, GoK in 0.16 seconds. For ply8, GoK took less than 2 seconds. White Dove needs 13 seconds to finish ply8.
Scurious's NPS in general runs at similar or slightly higher level than GoK's - I expect most time is used for move generation, and the generator must be really fast. But one would have to make it 9 times faster again to make up for the lower cutoff rate, and the evaluation would still be a topic. And that is for 4 plies, the number explodes with increasing search depth.
Thanks to staged move generator and early cutoff rates, GoK just has to generate only slightly more moves than nodes evaluated (typically around +20%)
Thundershark searched 195,000 nodes for the same board, and took 7 seconds. And it has 5 plies without quiescence I think?
That is interesting, thanks for providing the number. Yes, that number explodes at some point. I somehow did not manage to run that, because depth selection comes after import and search on Scurious.
I was just editing the original post, and added this section:
That is why pruning and move ordering are of uttermost importance. GoK gained half a ply on TurboWarp using history tables instead of piece square tables for ordering, and close to a ply by making LMR a bit more aggressive. If there is a decent move generator already, it is nearly impossible to gain a ply by any additional tunings on the move generator itself.
Last edited by ArnoHu (March 15, 2024 04:39:21)
- ArnoHu
-
1000+ posts
Scratch Chess Engine - Game of Kings
The mate scores are actually from virtual king captures. No nodes are stored in quiescence, and as of right now it is the only know TTable bug in Element.How do I deal with checkmate evaluations in a transposition table? They occur in the search setup and they stop the script like a beta-cutoff, but my TTable is having issues with the mate evaluations.
The table is giving Element a non-mate evaluation when it should be a mate evaluation.
We would have to see the code, it might have to do with whether the evaluation is exact our alpha/beta-bound. In general that topic is not all trivial, e.g. when in check you cannot apply standing pat. I have also seen engines not storing mate evals during quiescence, maybe you want to do the same in the meantime.
The statement about being in check isn’t relevant here (no check extension in Element, although I’ll have to put that in eventually, so it’s good to know).
Element’s “search” function does things like move generation and move ordering. It is the setup for the “negamax” function. A king capture check is run in the search function.
OK, do the virtual king captures happen before and return immediately, so that quiescence search is not even invoked any more? That is at least how GoK handles it.
- birdracerthree
-
500+ posts
Scratch Chess Engine - Game of Kings
Yes, it is detected during move ordering. If the move ordering finds a king capture move, it terminates. After that, the search function also terminates.The mate scores are actually from virtual king captures. No nodes are stored in quiescence, and as of right now it is the only know TTable bug in Element.How do I deal with checkmate evaluations in a transposition table? They occur in the search setup and they stop the script like a beta-cutoff, but my TTable is having issues with the mate evaluations.
The table is giving Element a non-mate evaluation when it should be a mate evaluation.
We would have to see the code, it might have to do with whether the evaluation is exact our alpha/beta-bound. In general that topic is not all trivial, e.g. when in check you cannot apply standing pat. I have also seen engines not storing mate evals during quiescence, maybe you want to do the same in the meantime.
The statement about being in check isn’t relevant here (no check extension in Element, although I’ll have to put that in eventually, so it’s good to know).
Element’s “search” function does things like move generation and move ordering. It is the setup for the “negamax” function. A king capture check is run in the search function.
OK, do the virtual king captures happen before and return immediately, so that quiescence search is not even invoked any more? That is at least how GoK handles it.
if <[(letter (2) of (LastCaptured))] = [K]>then
stop [this script v]
Last edited by birdracerthree (March 15, 2024 04:57:23)
- HasiLover_Test
-
100+ posts
Scratch Chess Engine - Game of Kings
Gonna hold the first round of the tournament now, this is the Lichess Link:https://lichess.org/study/XM1MArJC/U9hkU2h4 I did decide on TW Think Time for this Tournament.