Coding Adventure: Making a Better Chess Bot
ฝัง
- เผยแพร่เมื่อ 28 เม.ย. 2024
- Trying to improve an old chess bot by experimenting with various interesting techniques.
You can play (or watch) the bot on lichess: lichess.org/@/CodingAdventure...
This is a sequel to: • Coding Adventure: Chess
If you'd like to support my work (and get early access to new videos and projects) you can become a patron of the channel over here: / sebastianlague
Source code: github.com/SebLague/Chess-Cod...
A really fun video about various algorithms for playing chess by @tom7:
• 30 Weird Chess Algorit...
Music and other credits:
github.com/SebLague/Misc-Proj...
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 - บันเทิง
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
That's awesome, is your thesis available online? I'd love to take a look :)
And in the deleted comment I also admitted to miss-spelling you in my thesis‘ introduction, which I am forever ashamed of.
Also this new video of yours is amazing and massively increased my motivation again to continue work on my engine as well!
@@RabbleRousy Haha don't worry about the miss-spelling at all, and I'm happy to hear the video has boosted your motivation!
@@SebastianLagueCODING GAME, WORK ON NOW I BEG YOU IT WAS SO COOL
Im not sure how much support Ill get in this particular comment section, but
What a nerd
an hour long ? We are blessed, thank you Sebastian
An hour long and links to another 40 min video that you probably watched ages ago but sure why not, lets have another look.. perfection
@@biocode4478 exactly
Please don't apologize for a part 3, I'd love to see it!
for part 3 I think that engine is already strong enough that he needs to actually use some SPRTs for testing and not fixed games tests :) Somewhere there is where you need to start something that every "serious" engine uses as a development tool nowadays.
Waiting for 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
I agree that the obvious next step for this engine is to get a better idea of its rating with CCRL/cutechess-cli. Sadly SPRT can be slow unless your hardware is top-shelf. This is one of the reasons that I haven't been able to use it to improve my own engine (Homura).
@@redbedhed I wouldn't say that, the time controls for SPRT are much faster than what he is doing and multithreading is a flat N speedup in the number of cores. I have 6 logical cores and a sub-1000 game SPRT is reasonable to wait for, I can test one or two of those changes a day. Once the patches start gaining less (~10 elo) it starts taking too long though
Interesting. I would have just assumed that the wins are binomially distributed.
Then I could use some calculator to get the CDF for at least that many wins out of (num wins + num losses) trials assuming that the probability to win is 0.5.
That would give the p-value.
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
İf the number of games is 1000, np and np are both > 10. Thus, we can model it with a normal model with a mean at 0.5 and a stdev of sqrt(0.5*0.5*1000) rather than a binomial
@@soliform3485 you mean np and nq ?
@@typoilu3413 Yes my bad
Great explanations !
I wasn't sure how to deal with draws, but I suppose treating it as 0.5 of a win _kind of_ works? I just kept them separate :) I know whether equating a draw to a 50/50 win lose really works tho? Surely losses should be their own 3rd category which is either left out or treated separately?
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!
He did some sort of “making of” a while ago
@@lucbloom for some unknown reason I missed his previous video. Thank you for mentioning it, it explains a lot!
agree, know absolutely nothing about coding but still watched all of it, spectacular storytelling and calm voice
@@Vespura_ what about the cats tho xd
@@csehszlovakze clearly the best part
Ngl the fact that a chessboard is 8x8 is a happy little coincidence that makes chess programming easier since all the values fill well
Ancestors knew what they were doing 😮
50:25 "So I may need to subject you all to a Chess Part 3 in the future."
YES! My body is ready.
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!
Hey, I’m happy you enjoyed the video! And yes, the computer series will definitely be back in the future - there’s still so much I want to explore there.
Hello, profile picture twin!
@@LimitedWard slightly different but thats cool
@@SebastianLague I highly recommend looking into neural networks and how they can be applied into your engine. It will probably be a lot of work and very very complex but I highly recommend it
@@mod6870 complete rewrite. I'm not saying its not worth it but it'd be starting over from scratch
You know today is going to be a good day if Sebastian uploads a new video 😊
Bruh, I was about to comment that 😂😂
Fax no prinrert
True
True, make me learn about stuffs
I agree
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
Problem is, mine is tomorrow 😂
@@richardueltzen3755 hope it goes well
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.
Oh nice, I wasn’t aware of that! That part of the calculation is computed ahead of time, so the speed doesn’t really matter, but still good to know.
There's also "pext", which can extract bits in the other direction. It can replace the magic bitboard calculation, provided a cpu supports the instruction.
@@user-dh8oi2mk4f are you saying that INTERCAL predicted the performance needs of chess engines decades in advance with its select operator?
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
Been working on mine on and off for a few months now, just started on version 4. How did you get magic numbers? My generation can't seem to find a single one in hours on randomly generating with a specified amount of 1s bits or random amount, in hundreds of millions of attempts. Not even a single valid one.
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
10:48 this is such a good reaction gif. ori is clearly an excellent performer. she has mastered the art of less is more
Telegram the above username, got a package for you📦🎉..
all this makes me realise just how terrifying stockfish is
holy fook.
Always a pleasure to watch another Coding Adventure.
An hour long coding adventure featuring cats, that somehow makes me feel both relatively inedequate at coding but also motivates me to 'go do stuff!'... My day couldnt get any better!
Honestly thank you for these videos, the animation work is so clean and you can tell how much effort goes in
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!
I would love a part 3! Also I loved how long this one was :)
This is so so good as always, hoping you will make a part 3!
My English is so little and this video is so fabulous. Thank you Sebastian! This programming - chess content is really interesting
I’m subscribed to a few hundred different TH-cam channels, some inactive and others active.
Yours is the only one I have notifications set up, so I get notified when you upload a new video.
I absolutely love watching your videos. They are paced and explained to perfection, and you tackle some really interesting subjects.
By far my favorite TH-cam channel.
Thank you!
Currently writing a study about coding my own chess engine. Your video was the first and most impactful one I watched to inspire myself for my study. And now I get to have part 2?! Thank you very much Sebastian!
Holy, I just finished watching the video and damn, I was hoping for copper but found a pile of gold!
i'm sure you've heard by now how amazing your work is. what i want to point out though, is how remarkable your patience is. Sticking through gigantic projects like these and keeping on through all the bugs and edge cases is an amazing feat!
I love this
some months ago, inspired by the first video, I also decided to give writing my own engine a try.
you have no idea how much I needed that boost of confidence to keep going and know that I'm going in the right direction.
when I have some time and a stable build I will definitely make our engines play a game and let you know the result.
you are by far my favourite (coding) content creator and I hope you never stop uploading once in a while.
OMG, Sebastian. Even your code editor color theme is aesthetically pleasing.
I was thinking that XD
do you know what that theme is called?
@@unnamedbot2960 palenight on vs code
Love this video series. I did a chess game for my A level comp sci project (A level is a qualification taken at 18 in UK). Spent hours watching and rewatching your first vid as it was released right in the middle of that time. This vid was awesome too! Would love to see more in the future :)
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
Nice explanation :) It's interesting to see how different people deal with draws - I kept win/draw/loss-stats separate, some people counted them as 0.5 of a win, and you've left them out completely! I personally think it's better to include them somehow, because in the case of 6vs7, the wins slightly increased, draws significantly decreased, and the losses slightly increased! In fact from my calculations, the draw-stats were the only one of the three that *was* significant!
I also got 68% as P-value for the V6b vs V5b matchup
hi
i'm a stats student, and i also ran some of these calculations when he mentioned it. if someone doesn't mind explaining, why use a two-tailed test (the proportion of wins != 0.5) instead of a right-tailed test (the proportion of wins > 0.5)?
@@target0330one-tailed is more logical here. i also think using a 1-prop z test and interval would be more appropriate but i guess they'd yield similar results
best series ever, the storyline is perfect
Love these videos! It was very satisfying to watch it slowly get better and better 😄
Thank you for recommending that 30 chess bots suckerpinch video! It's really great for people who enjoy similar content and one of the most under-viewed videos on youtube. These two chess bot videos of yours have been the only things to scratch that same lovely itch for me, so thank you even more for making such amazing videos like these.
I think that might be my favorite video on youtube.
I am a computer science professor, and I teach heuristic search and Game AI each year. I am blown away by your animations and your detailed explanation of these concepts. I wish I had the time per lecture and video production skill to be able to make content like this for students.
27:51 - Sometimes adding calculations to the evaluation which theoretically improve things can cause your evaluation to be a bit slower, meaning fewer nodes / depth searched. There's not exact science to this, and this is why your evaluation is so important
28:16 - You can eliminate some of the conditionals that you have here by doing clever tricks like saying numIsolatedPawns += (1 - (friendlyPawnsBitboard & Bits.adjacentFilemask[pawnFile] > 0)). Doing the math directly on the result rather than using an if-statement helps eliminate slowdown due to branch prediction. In practice this may not actually make the program any stronger, and the compiler may be smart enough to do this for you anyway, but it's something to think about.
Final comment: Did you tie-break scores with the number of moves performed? I did not see this anywhere in the video, but you definitely want to be taking 'quicker' checkmates than later ones due to the incomplete nature of the search.
do you consider your teaching subject harder than average?
The source code for the first video includes mate pruning, so he is looking for quicker mates
do you have a chess engine? If so, I'd love to read it! :)
@@Wariowa345 I can imagine that teaching search is difficult but very necessary... Many problems in AI are search problems.
The basic search algorithms are not too difficult to grasp... Depth-first, breadth-first, best-first, uniform-cost, A*, backtracking depth-first, minimax, alpha-beta, mcts.
However, customizing any one of these basic algorithms to make decisions in a particular environment (especially a stochastic environment [not computer chess] with multiple agents)... That's where things get extremely challenging.
This video, while excellent, lacks quite a bit of detail and leaves out quite a few chess programming techniques. Programming a computer to play chess at super-human level is a feat that often takes many years to achieve (assuming you aren't just cloning stockfish and changing a few lines).
Good hardware can speed the process up quite a bit. As others have mentioned in this thread, SPRT is the only way to really test if your engine has improved. SPRT tests often take many thousands of games to do this. If you can run games in parallel, the SPRT test will finish much faster. Good hardware is also needed to train neural networks in a timely manner.
I'm personally about to upgrade from a cheap laptop to a desktop (now that I'm no longer living on student loans lol).
Yay, you're back! I really love watching your videos, it's always a surprise when a new one is released.
Wow! I've rewatched the first part many times and now its finally time for the sequel. Good job, I can't wait for the next part!!
This is absolutely amazing! I haven't actually watched your first video (i'll make sure to do that now), but this video is so interesting as a chess player and programmer myself - I actually tried making a program similar to that recently but gave up on the idea. Perhaps I'll continue now with the new motivation I've obtained from this video and what I've learned. Thank you!
Your last video was super entertaining and informative,,,, saw part 2 and I immediately clicked! Thanks for the vid :)
I never fought about that, but I think you're my favorite TH-camr among the hundreds I watched.
1) Inspiration for coding
2) So much I learned
3) So eye pleasing graphics
Wow! Keep up the work 👍
Thank you Sebastian for such an interesting and informative video.
You're definitely my favorite programming/development creator on TH-cam!
I absolutely adore how you approach your projects with such enthusiasm and care, especially when you go the extra mile to provide enlightening visualizations and demos in your videos.
I love this video. The first was one of my favorites, and this is a well-made sequel with the same relaxing tone and pacing that anyone can understand. Thank you!
Sebastian's videos have been such an incredible inspiration for me! They sparked my passion for programming my very own chess engine. And now, seeing him in action, making it even more efficient, is truly motivating me to strive for improvement and enhance my skills. Thank you so much, Sebastian! You've made my day incredibly special. Sending lots of love and gratitude from India. ❤
A sequel to my favourite coding adventure video!
You never disappoint
This is one of my favorite things you've done on this channel, please do a part 3!
Half way throught but can safely say that this is another fantastic video. Pace, quality and obviously the subject is unmatched. Thank you Sebastian for this ❤
I don't often leave a comment but I just have to here.
Wow. Gosh I love watching this stuff. Watching a Sebastian Lague's video is a fun activity all by itself. Thank you so much for the 1 hour long content.
I was really hoping you'd come back to this! Your previous video inspired me to start working on my own chess engine, which after many iterations is now the project I'm most proud of!
I've watched that first video along with that tom7 video countless times, and I'm so excited to see a sequel!
I really enjoy coding various things/projects and watching your videos really is enjoyable, as i can see how various things work, watch an effective planning process, and do all of this with pleasant visuals and audio. the editing and overall content of these videos is really great, and i cant wait for more videos. thank you for making such great content!
"makes more sense than En Passant at least"
En Passant was added because moving pawns 2 squares was added to speed up the early game.
Originally pawns could only move one square, so it was impossible for pawns to "jump past" each other to avoid capture. En Passant was added to allow for pawns to retain their same amount of control while keeping the speed of the early game fast.
Another simple improvement would be to use the “allowed moves” bitboards in your evaluation. You can combine it with the square scores as well and add all of the possible moves weighted by the square score. This would solve your “rook stuck in corner behind bishop” problems!
Very cool video!
great idea to promote opening up pieces
This was such a great sequel to my favorite video of yours! Your videos are so inspiring, keep it up :)
Someone mentioned your channel in passing and I've been having such a good time watching your videos. Seeing you tackle these problems and clearly explain each approach with the code on-screen really helps make the whole thing feel more approachable.
This is an awesome adventure through the associated code! I really appreciate the cleverness of the use of bitboards to represent various aspects of game state, and the various ways you show of working with them through mathematical operations that stand in for more conventional approaches such as iteration loops. One thought that crossed my mind repeatedly was taking all the metrics you employ, turning them into inputs for a neural net, and utilizing machine learning to let it experiment with various combinations of weights, to arrive at optimal values. I realize this is much, much easier said than done, since it amounts to many dozens of inputs. Anyway, great video, as always!
Yeah, it seems really hard to get anywhere close optimal values just tweaking all those weights by hand, so I think some sort of automated tuning process (using neural networks or otherwise) would definitely be a good idea. I’m happy you enjoyed the video btw, thank you!
@@SebastianLague You could try reinforcwment learning, it's not as heavy a subject as machine learning and I feel like it would fit well with your explanation style and how you bounce back and forth between code and examples
ERRATA: In this comment I use the phrase "machine learning" as opposed to reinforcement learning, as my peers below have repeatedly pointed out, reinforcement learning is part of machine learning, using machine learning to refer to neural networks in specific as was my intention was unduly imprecise and contributed to misinformation on this topic
@@Imperial_Squidyou do realize that reinforcement learning is a variety of machine learning, right?
@@DanKaschel yeah of course but when people talk about machine learning, they most commonly mean _neural networks,_ that's the distinction I was drawing
I'm very aware ML is a hugely broad topic referring to anything from RL, NNs, deep learning, neural architecture search, etc etc (I'm a data scientist by trade and currently doing a PhD on multitasking neural networks so I've touched all of these topics to some extent!)
Came here to say this :}
I have been working in a chess engine myself in Rust. I had played chess for a few years but only your last video on this series made me excited to start. Great stuff!
I was waiting for this video!!! Thank you!!!
I'm so excited to watch this! Your first chess video was what brought me to your channel, can't wait to see what you did this time :).
I love this video concept so much!!
As a chess player and evolving programmer, you have officially just made my day!
btw PLEASE make a third video, this is so enjoyable to watch...
I reallly like this video and as someone who also created a chess bot (much weaker) I know to appriciate how much work you putted into this video.
I also want to add that the bot isn't overrated at all. I am 2600 in bullet and blitz and played some bullets against it and it outplayed me most of the time.
By the way I couldn't help but notice that you are also a decent chess player by your way of thinking
It’s not extremely overrated when playing against humans at tight time controls, no. But the only way to get an accurate rating for a chess engine is to pit it against other chess engines for many thousands of games.
Amazing work! Love your thorough explanations on the inner workings of a chess program.
Fantastic video as always Sebastian! I've watched Tom7's video several times so it's awesome to see it called out!
Man, your vidoes are production quality, your narrations are well written and structured. No sure why this isn't on master class. Please do keep up the good work.
wasnt expecting a second part of this. the first chess video of you was already my favorite video and it was very detailled. i cant even imagine whats in this video :)
I KEPT REWATCHING THAT FIRST VIDEO CUZ I LOVED IT SO MUCH! THANK U FOR MAKING ANOTHER AND BLESSING US WITH AN HOUR OF AMAZING CONTENT ❤️❤️
Exceptionally good and very interesting video Sebastian, thanks for all the hard work. I really hope you make a 3rd one to see how much you can improve it again.
You made a mistake on the passed pawn mask. The two squares immediately diagonal to the pawn should not be included. If it's your turn to move and there's a pawn that could capture you, you can simply move the pawn forward to get past the pawn. You could also potentially capture the enemy pawn to make your pawn a past pawn.
It depends on whether it is your turn to or the opponent's turn to move in the position you're analyzing. If it's the opponent's turn, they can capture your pawn.
@@scifino1 well the engine can't play during your opponents turn, so there's nothing to evaluate.
@@MorganBlem But when evaluating the results of a potential best move, you need to evaluate what the opponent can do after that move. More concretely, when you want to check whether a move you can make results in a position where you have a useful past pawn, you'll want to make sure that the opponent's pawns cannot immediately take that pawn.
It looks like you need to add King safety in the bitmap as well, it is not penalizing open space near king it looks like. Great video btw, never knew where the entire hour went!
I've been coding for a while and worked on a few big projects, but I've never really relied on bit manipulation to keep track of and manipulate data. This video was amazing, and it greatly increased my appreciation for binary operations and bit manipulation. Even though I understood what it was before I never really liked it, but now I'm definitely going to make a point to use it in my next project. Fantastic stuff as always, can't wait for the next one.
I'm so happy you've come back to this project - it's amazing!
You've a very powerful talent Sebastian. I'm absolutely uninterested in chess or board games in general. Yet, when you make a video like this my fingers start to itch to create my own chess engine. There're very little other videos as inspiring and motivating as yours. I hope you are aware of the impact your videos have. Thanks so much for making these.
I always love your videos! So cool!
I always look forward to your videos man.. This is a treat
the first video was absolutely incredible, and this is too, I love this content and keep it up!!! pls pt 3
It's always a good day when Sebastian posts a video. And always a terrible month afterwards, as I get inspired fo start a similar project and innevitably fail.
If a coding adventure comes out, you know you have to binge watch it immediately 😂
Amazing! What a great video. I am always so happy to see a new video of yours!
Your videos are gold, Thank you I appreciated every single seconds of this video.
Your previous video about your chessbot was amazing and inspired me to make my own chessbot and this one is even more entertaining.
Loved this video, please more uploads just like this! :)
Very cool of you to narrate these experiments your cat made!
oh my god ive been waiting for a followup for so long this has made my day, you even inspired me to make my own chess engine thank you!!
I would love to see you do a triangulation series, covering things like Delaunay and Constrained Delaunay Triangulation.
An interesting challenge would be to make a non-random bad bot, that feels like a human beginner.
Maybe have a very low depth or if it finds a “killing move” have a likely probability it won’t play it.
I really love your videos. I discovered your channel about a year ago. So calming and interesting. I really enjoyed the flying delivery game round Earth :).
Awesome video. Very entertaining and informative at the same time. I thought 20 minutes have passed and then the whole video ended. Really enjoyed the explanation on every addition. Keep it up!!
18:31 Not a statistician, but I think I can calculate the P-value (the chance that the test would have given the exact same results or less evenly distributed assuming winning and losing both have a probability of 0.5) anyways. I assume the games that are drawn were never played, im pretty sure that's an assumption that you're allowed to make.
Before finding the P-value, I first want to explain how you would find the chance that exactly 365 out of 718 are won. This question is the same as asking 'suppose you threw a fair coin 718 times. What are the chances that it lands heads exactly 365 times?'. If you throw a fair coin 718 times, there are 2^718 possible sequences. Out of those sequences, 718! / ( 365! * (718-365)! ) contain heads exactly 365 times. Let me explain:
"
suppose you have 718 tickets with each a unique value between 1-718. If you lay them down in a random order, there are 718! different possible sequences. If instead you paint over 365 tickets with yellow paint (analogous to getting heads in the coins analogy, or winning in the actual problem) before laying out the sequence, the amount of different sequences suddenly becomes 718! / 365! as for every new way of laying out a sequence, the yellow tickets would have otherwise had 365! different ways of being ordered. If you paint over the other 353 tickets with blue, the amount of different sequences becomes 718! / 365! / 353!
"
Thus, the chance to get heads exactly 353 times is 718! / ( 365! * (718-365)! ) / 2^718 which roughly equals 0.0269.
Now, to calculate the P-value, we add up ((the chance to win 365 times out of 718) + (the chance to win 366 times out of 718) + .... + (the chance to win 718 times out of 718 times)) + ((the chance to lose 365 times out of 718) + (the chance to lose 366 times out of 718) + ... + the chance to lose 718 times out of 718 times)) = 2 * ((the chance to win 365 times out of 718) + (the chance to win 366 times out of 718) + .... + (the chance to win 718 times out of 718 times)) which roughly equals 0.68. This is not low enough to conclude that the newer version does not have a winrate of 50% at all.
Let me know if anyone has any questions!
I'm all in for a PART 3. DO IT!
The video a few years ago inspired me to make my own chess engine, starting with the features he added in the video, and then diving into the chess programming rabbithole to develop it further.
Satisfying to see a lot of the work I've done matching up with the progress in this video (own test framework, lichess bot, better evaluation, bitboard-based move generation...)
This video made me somewhat motivated to keep developing the engine :)
We'd all love to see a third video!! And beating your version one that badly wow!!! Amazing improvements on your end
BMI2 would actually help with the bit manipulation a lot, it's a common x86/64 extension in most modern processors
I second this. Sadly, it is Intel only though afaik. The intel x86_64 assembly syntax has the instructions baked in which is very nice. "bsf" and "pext" are by far the most useful.
My engine Homura uses both of these instructions. The perft can do 700,000,000 leaf nps on my 13th gen i9.
I think that part of the reason for its inflated bullet rating is because it plays so quickly that it probably won a bunch of games on time
Insane video as always.
Please continue!
I love your vids, I’ve been subbed for over a year and every single video I’ve enjoyed!
Great stuff, looks like bullet rating is stabilizing at 2700. In my (I'm 1950 rated) game I still got an early lead though of +2. I think there is the most room for improvement. Something like piece moveability could be factored in (a queen/rook/bishop is much better if it is not blocked by other pieces).
Very cool! If you do end up returning for a third video in this series, I bet that some basic parameter tuning could result in a huge increase in performance for the bot. At 27:11 in the video you allude to this a bit by saying the weights could use some tweaking in the future. I'm sure there are more sophisticated ways to do this, but at first glance it seems like you'd just need to set up a training where you tweak the weights a bit, run a test against the old weights, and then take whichever performs better and use that to tweak again.
The scientist in me is extra interested in the patterns of weights that would come out of starting with a random set. Say you take the weights at 16:25 and randomize them, then begin the tweaking and let it run until you get a stable result. Does the algorithm agree with your general shape for the weights? Who knows!
That would be very pog
That could easily take weeks to complete. He mentions that a test takes a few hours to complete, and running enough of them to get a significant improvement would take quite a few iterations.
@@nikkiofthevalley Agh, you're right. I've gotten spoiled working in a field where whenever we need to do something like this we just can throw it at a supercomputer.
Would love chess engine number 3! The original video was how I found your channel (and then binged the rest of the videos)
Slowly tempting me to make an engine for Gungi, even though it would be way more complicated. Lovely to watch everything you do, keep it up!
Great video, I loved the explanations and new ideas you came up with from start to finish! :)
I don't even know how to play chess but was so invested lmao
I feel the most major improvement to make here is having CAB care a lot more about the safety of it's king, and the vulnerability of the opposing king.
Telegram the above username, got a package for you📦🎉...
A really incredible video, thanks you for showing actual code and explaining optimisations you used. The Magic Bitboards remind me a lot of perfect hash functions.
Fantastic video! Love how you work through the thought process of coding, you capture it wonderfully
i live for your cat b roll footage