Coding Adventure: Making a Better Chess Bot

Trying to improve an old chess bot by experimenting with various interesting techniques.

A really fun video about various algorithms for playing chess by @tom7:

Music and other credits:

Chapters:
00:00 Intro
00:38 Battle of the Bots
03:18 Maybe Don’t Throw Away the Best Move?
07:13 Transposition Troubles
10:55 Search Extensions
14:01 Refactoring and Recapping
15:51 Tweaking Kings and Pawns
19:35 Bitboards!
23:54 Passed Pawns (and more)
28:32 Magic Bitboards (minus the magic)
34:40 The Magical Part of Magic Bitboards
39:00 Testing and Optimizing Move Generation
41:50 Killers, Reductions, and Repetitions
45:56 Creating a Lichess Bot
49:30 Let’s Play!
54:54 Existential Crisis
55:02 The Bot’s First Game Online
56:12 Can Our Bot Beat Stockfish? (No)
56:59 Rating Speculation
59:28 Outro

[RabbleRousy]

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

[kitsuneprincess]

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

[scaffus]

an hour long ? We are blessed, thank you Sebastian

[splajanku]

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

[Algorhythm]

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

[Vespura_]

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!

[tamertamertamer]

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

[twiddlinbits]

The "theoretical" best computer approach is to play out all possible continuations from a position to game completion, and choose the best continuing move. Humans can't do this, so we make generalizations instead. Having more pieces than our opponent will generally give us a greater ability to win, as will pushing passed pawns, delivering check, mobilizing our king in the end game, etc. Of course computers can't execute that "theoretical" best approach either, so (as represented in this video) we teach bots to use the generalizations that humans have come up with. I've sometimes wondered what it might look like to get computers to come up with generalizations of their own. Not only could this result in stronger bots, but it might create opportunities for bots to teach us strategies.

[Dev.]

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

[LittleLily_]

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.

[jakesilberstein]

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!

[atypicalprogrammer]

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.

[youerny]

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

[vladchira]

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

[Max-ooxw]

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

[WolfVidya]

"I think this move is pretty good but... *considers alternatives you know what? f it. *blunders queen.

[dialog_box]

10:48 this is such a good reaction gif. ori is clearly an excellent performer. she has mastered the art of less is more

[jamesmnguyen]

Always a pleasure to watch another Coding Adventure.

[PiercingSight]

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!

[keldwikchaldain]

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