Coding Adventure: Making a Better Chess Bot

Wait, a one hour sequel to the video that inspired me to write my own Chess engine and eventually became my Bachelor thesis? HELL YEAH!:D

an hour long ? We are blessed, thank you Sebastian

Please don't apologize for a part 3, I'd love to see it!

The method to calculate the probability of one engine being better than another based on game outcomes is called the Sequential Probability Ratio Test (SPRT). The CLI-based match runners that the chess programming community use to test their engines have this capability built-in, and can automatically run a test until the probability of improvement exceeds some desired bound. The most popular one is called cutechess-cli, which works with UCI chess engines

18:25 An easy way to find if the bot has improved is performing a sign test. We model the number of wins for v7 as a binomial variable X~B(n,p) with number of games(n) = 1000, and hypothesise that probability of a win(p) = 0.5. If we treat every 2 draws as one loss and one win, we can find the probability of 365 + 282/2 = 506 wins. Finding the probability that X >= 506 gives us a p-value of 0.364. At a significance level of 0.05, this means we cannot conclude that the v7 bot is better than v6c and would need a larger sample of games to be sure. TLDR: we cannot say there is a significant improvement

50% of why i love watching these videos is about the code. The other half is about the fantastic story telling along the way. Incredible video editing (animating code edits, animations between code/variable changes and the actual impact of those changes in the final product, statistic tracking and animating, good pacing throughout the video, no chapter feels slow or boring). And I could keep going for a while. I’m curious what kind of tools you use to do this editing. It’s really awesome and I hope you keep making these kinds of videos for a very long time!

Ngl the fact that a chessboard is 8x8 is a happy little coincidence that makes chess programming easier since all the values fill well

50:25 "So I may need to subject you all to a Chess Part 3 in the future." YES! My body is ready.

You know today is going to be a good day if Sebastian uploads a new video 😊

What impresses me the most is how dedicated you are to tackle new ideas and then return later to improve them. Usually when I start a personal project I put a lot of time into it and then kind of abandon it and move on to something else You are a true inspiration

This one really deserves the title "Adventure" and is exactly what you need when you can't sleep at night because you keep thinking about your terrible maths exam from 2 days ago. Thank you :D

Blame on you, Sebastian! I went down the rabbit hole of a chess engine from scratch of my own. I made bit boards , alphabeta search, nn evaluation, Montecarlo tree search and many other micro elements retrieved here and there as ideas. A wrote the code from zero 3 times, changing programming language as well as approaches. After two months I am dreaming of bishops moving only on diagonal bits (don’t know, in the dream a “diagonal bit” has totally sense). In fact it has been a huge journey and I am happy I had the stamina to overcome the several difficulties and the final result is definitely mediocre but totally mine and this is enough. You started the interest in the topic I had since I was a child as a personal programming challenge. Very nice job pal. Thanks a lot

This is really cool! I've been a chess nerd all my life so seeing this is like magic to me. Separately, do you have plans to continue working on your explaining computers series? And, if so I'd appreciate it if you would share with us! I really think that series is incredible. Thanks!

At 31:58 this sounds like something that could utilize the "pdep" assembly instruction on pretty much all 64 bit processors. There's a C# binding for the command called ParallelBitDeposit. The purpose of the command is to take a 64 bit value you have, and a 64 bit mask representing the locations you want the bits from that value to be distributed over, and it deposits the bits from the value into the spots defined in the mask. Being able to do that in a single instruction sounds like it could heavily speed up that part of the application.

I was waiting for this video!!! Thank you!!!

all this makes me realise just how terrifying stockfish is holy fook.

Always a pleasure to watch another Coding Adventure.

I would love a part 3! Also I loved how long this one was :)

18:24 You wanted to know if this is better or just random. Well, I calculated the P-value(*) using a two-tailed Binomial test(**) for every version you tested: Match | Wins-Loss | P | Better? V2b vs V1 | 409 vs 270| 1.1e-7 | YES V3 vs V2b | 399 vs 387| 69% | Random V3_64vs V2b | 386 vs 246| 2.8e-8 | YES V4 vs V3_64 | 433 vs 237| 3.3e-14 | YES V5b vs V4 | 337 vs 273| 1.0e-3 | YES V6 vs V5b | 393 vs 310| 1.0e-4 | YES V6b vs V5b | 298 vs 309| 68% | Random V6c vs V5b | 385 vs 276| 2.6e-5 | YES V7 vs V6c | 365 vs 353| 68% | Random V8 vs V7 | 415 vs 325| 1.1e-7 | YES V9 vs V8 | 347 vs 367| 48% | Random V9b vs V8 | 396 vs 341| 4.7% | Random (debatable) V10 vs V9b | 447 vs 275| 1.6e-10 | YES V11 vs V10 | 477 vs 221| 1.6e-22 | YES V12 vs V11 | 397 vs 238| 2.9e-10 | YES The notation "2.8e-8" means "2.8*10^(-8)" that is 28 in a billion odds, 1e (*)What does the P-Value mean? It is the chance we would still get this result if the players were equally good. A lower P means more likely not random (**)How do we calculate that? Using a two-tailed binomial test (If you already know how that works you can stop reading now) Our null hypothesis (which we hope to debunk) is that both players are equally likely to win. (I ignored all draws, and looked only at the games with a winner) The P-value is the likelihood that we would still get this result or something less likely if our Null hypothesis is true. So for the 365 wins and 353 losses, the P-value is the chance of getting either 365 wins and 353 losses, 365 losses and 353 wins, 367 wins and 352 losses and so on. This is a "two-tailed" binomial test, and you can look up the formula for calculating that on Wikipedia. A low P-value means that it is unlikely (But still possible) that we would get this result if the players are equal. I decided that if P<0.1%, then I do not believe the players are equally good. Some people use P<5% as the threshold, in which case V9b is better than V8, I think they are too close to say for sure though.

I look forward to Chess Part 3! Also, this is such a SPECTACULARLY good explanation of so many difficult concepts of chess engine design. The magic bitboards part especially. Well friggin' done!