How many chess positions are there?

[@sebastiandierks7919]

21:31 I counted 216 legal moves twice, not sure where I missed two. Very nice video, as a physicist and chess lover I liked this mathy and code approach to chess very much!

[@maxpacker8222]

thanks glad you enjoyed it! tbh i found this position online and didn't check it for myself, but i just looked and here's what i got for the number of legal moves for each piece (each line is a row and the numbers on each line correspond to the white pieces in that row left-to-right): 10 9 21 19 19 25 22 17 15 21 18 5 4 4 4 5 ---------------------------------- = 218

[@sebastiandierks7919]

@@maxpacker8222 I found the mistake. The position shown in the video is incorrect, the white king has to be on f1, not e1. The original composition/study is by Nenad Petrovic, Fairy Chess Review, 1946. With the king on f1, your numbers of legal moves per piece are correct and add to 218.

[@maxpacker8222]

@@sebastiandierks7919ah guess i copied it wrong and then looked at the original for the numbers 🤦‍♂️ nice catch!

[@TYsdrawkcaB]

@@sebastiandierks7919woah, nice

[@cowsrcool]

@@maxpacker8222I am confused on why there are bishops and rooks in that position? It seems that white would have more legal moves if those pieces were queens

[@MrMasterGamer0]

If you need a lower bound for number of board states: I can confidently say there is more than 7 👍

[@user-yv6xw7ns3o]

What makes you so sure about that? 🤔 /s

[@mrsesh7364]

source?

[@tallskinnygeek]

​@@mrsesh7364I can confirm this independently. After 1024 consecutive losses in 6 turns, I manually deduplicated all the distinct board states seen. There were 7.

[@_yuri]

​@@mrsesh7364fool's mate

[@CarlosFloresP]

Lmao

[@klaus6122]

"If you look at it logartihmically, we are halfway there" - God I love Geek humor! Well done!

[@jemmerl]

I misread this as "Greek" humor and spent far too long confused XD

[@deathvideogame]

@@jemmerlLMAO me too 💀

[@coolava2952]

​@@jemmerlyup yup same

[@Extinct_1]

NERD 😂 (I am just kidding)

[@subjekt5577]

I mean hey if moores law holds for storage it's doable in some living people's lifetime

[@haroldp.sadwood1181]

Magnus Carlsen when there's a position for each atom in Uranus: "Nah man, chess is unsolvable" Magnus Carlsen when there's a position for each atom in the Moon: "Nvm give me 10 seconds"

[@maxpacker8222]

ez

[@badpiggs]

you mean Carlsen

[@haroldp.sadwood1181]

​@@badpiggsgood catch. edited

[@DanielSong39]

If someone solves a position against him in a game: "You cheater!"

[@aileannpret7934]

The problem is if there are less positions than atoms in Hans Niemann's "Uranus" !

[@gustavosouza5600]

"if we look at it logarithmically, we are half way there" that broke me

[@vladthemagnificent9052]

14:19 this is also impossible because the second a pawn has captured two pieces and ended up in the 3rd rank

[@maxpacker8222]

facts

[@Vearru]

I was so confused by your comment for about 30 seconds since I read “a” as the word and not the letter

[@quentind1924]

There is an easier way to see that it’s not a valid position : WHERE ARE THE KINGS ?? This was an example for a concept, not saying that it’s a valid position

[@zygoloid]

If you want to build a perfect chess lookup table, then you shouldn't need to consider the multiplicity from the 50 move rule. If a move wins when there have been N plies since the last capture or pawn move, then it also wins if there have been M

[@maxpacker8222]

mm yeah thats big

[@hvok99]

Love this video, it really shows the itteeative considerations and creativity that goes into building a model. Thanks for making this.

[@JackMott]

I like how Claude Shannon's hand waving decades ago was so close to the current state of the art estimate!

[@priyavkaneria]

This years #SoME3 is on another level Loved the video❤

[@mickeyrube6623]

Full disclosure: I haven't finished the video yet. I've seen so many videos on this topic, and have read quite a bit of articles, forum discussion, etc. I am still flabbergasted about how this game can have so many strict rules about positions (no pawns on first or last rank, always two kings on the board etc.) and this question is still not solved, even with modern committing power.

[@maxpacker8222]

yep i feel the same way

[@Gameknight2169]

Dude is criminally underrated, this is really interesting

[@avelhabolachuda]

As someone who had to learn Racket in college, you are an absolute gigachad for using it

[@20Gero09]

I'm working on a lower bound atm by playing against myself and counting the legal states - I'm at 73 so far and still going strong! Will be sure to check back with you and edit my comment some time after the heat death of the universe 😊 (on another note, where would I find a neverending supply of pencils and paper? Or should I be using a computer to keep track instead? Was worried my hard drive might be a limiting factor..)

[@anarchosnowflakist786]

oh if you want I can make a machine to turn matter into pencils and papers endlessly, I'll contact you when it's done

[@psymar]

your hard drive? that's what The Cloud is for

[@Starwort]

5:25 I'm disappointed that there is neither a missing king nor doubled kings here

[@maxpacker8222]

haha, wonder what the "most illegal position" i should have shown there is

[@yt_is_a_pussy]

​@@maxpacker8222 white kings on dark squares and black kings on light squares: maximizes illegal piece count both by type and in total, maximizes "king touches" and enrages whoever wanted light squares for white and dark squares for black

[@DemoboyOot]

this comment reminds me of the monty python skit where michaelangelo paints "the last supper" with 3 Christs and a bunch of kangaroos

[@neko-sauerbraten7774]

This is so underrated. Great video

[@manuman5319]

The reason why chess engines don't draw all the times against each other is only because they purposefully get told to play unbalanced opening heavily favoring one side. If not, they'd draw each other a huge majority of times.

[@maxpacker8222]

that's a good point, but don't they play each opening twice, with each engine getting white once - so if one engine comes out ahead overall, that means that the two games had different outcomes (white win / draw / black win), so at least one of the games was not consistent with perfect play

[@DukasFiguliras]

"Unbalanced opening" isn't about being favored to white or black, but it's very asymetrical. For example, italian opening is never played in engine matches, but the grunfeld defense might be

[@anthonywarfield7348]

Engines are playing book openings, some of which are solved like some queens Indian defenses. I would love to see results of games that don't follow those parameters but I only see results published after opening guidelines are followed. I guess those games can't be played because the engines would take too long to make the first few moves.

[@anarchosnowflakist786]

@@anthonywarfield7348 I don't think you can fully solve an opening though no ? besides stuff that ends up also being an endgame

[@xeuszzz]

I once pondered this very same question, and through simple but rigorous binary encoding of board states came up with an upper bound of 2¹⁶⁰, whose magnitude is 10⁴⁸. Even 10⁴⁴ is about the same as 2¹⁴⁶, so the number of UUIDs (or GUIDs), which is 2¹²⁸, is likely less than the number of legal board states. Therefore using a UUID as a key representing every board state through some encoding is likely impossible. To prove this, one needs to calculate a lower bound of definitely legal board states.

[@maxpacker8222]

Yeah I have no idea how to calculate any sort of reasonable lower bound, but that would be quite interesting as well. There's a lot of board states that are "obviously possible", but the exact moves needed seem specific enough that it would be hard to treat any large number of cases in the same way.

[@xeuszzz]

@@maxpacker8222 Here's a strategy I've been thinking. 1) Encode locations of the kings. They definitely take at least 12 bits (rank & file, 3 bits each for both kings) 2) Encode locations of at most exactly one pawn from both w&b, that are seemingly still on their own file (even if they might've eaten twice), and closest to their respective starting squares (even if changed places with an opposing pawn). Dismiss doubled, tripled, etc. pawns that are further down the files. Use variable length encoding so that less bits are needed for less pawns. With non-variable encoding this would take max. ~43 bits (43^8 different states) with all 16 pawns. 3) Encode the remaining pawns using a specific pattern dependent on the number of files without a pawn on either side (w or b). You have at most as many extra pawns on other files as you have files without a pawn. Again, use variable length encoding. Can be skipped if there are no files without a pawn, or if there are no pawns on any file. X? bits. 4) Encode the locations of the pieces using the information of the number of empty squares, which is at least 46 and at most 62. Having used variable length encoding for pawns, you should have more bits to spare, when there are less pawns and more empty squares. Notice, that the same piece location encoding may represent different locations depending on the pawn locations. Max. 38-45 bits (46-62 choose 14) for locations without piece identity, and max. 35 bits (14!/4) for piece identity permutations. This makes 12+43+X+38+35=128+X bits with all pawns and pieces. However, this doesn't necessarily mean a lower bound of at least 2¹²⁸×2^X board states, because not all the bit strings encode some board state. For example, without any pawns only 12+45+35=92 bits are required which alone leaves 36 bits unused, which should give room for board states with extra pawns in files. Perhaps the information of the states requiring more than 2¹²⁸ bits could be packed. This of course would also mean that the upper bound is actually much smaller! If you happen to try this approach yourself, please, come back to me with your results, especially if you find any glaring errors in my thought process. :)

[@J7Handle]

@@maxpacker8222 Well, the number of possible game states is definitely higher than 3.

[@thewhitefalcon8539]

Why would you need it to be a UUID?

[@DrZaius3141]

@@maxpacker8222 Lower bounds seem pretty impossible. While reasonable assumptions can be made for pawns, checks are just an utter pain to deal with.

[@fraser21]

This is spiritually the perfect use case for Racket

[@apollo_predates_soup]

5:02 "and even this naive calculation has gotten us below that number" please note the difference between possible positions and possible games, each game includes a massive amount of positions, hence there are more possible games.

[@thelazyguy3735]

I find those illegal positions unsettling, kinda like liminal spaces

[@justinmayhew6848]

Really cool video, especially the way of thinking, taking a kind of iterative approach, narrowing down the range with these different insights on each level. Also love mixing the math with code. I feel like the video emphasizes the creativity involved in math and all the different ways you are able to tackle a problem from.

[@simonachtnich4417]

I looked at this problem by coming up with an encoding for each game state. empty -> 0 pawn -> 1x0 rook -> 1x100 knight -> 1x101 bishop -> 1x110 queen -> 1x1110 king -> 1x1111 with x for black/white You need an additional bit to record the current player, four bit for castling and up to five bit for en passant(two bit for whether a player has en passant and if so three additional bit for the rank). This does not record the 50 moves rule or threefold repetition. The starting position would be 171 bit. The only way to extend this is through promotion with queen-promotion giving +3 bit. This can not happen to all pawns though since they have to cross each other. The most efficient way for that is: four pawns in a square -> one pawn captures another -> three pawns out of four can promote. Therefore an upper bound on the number of game positions should be 2^(171+4*3) ~ 8*10^59.

[@ElectricLimeade]

I would be very interested in a proof that this encoding is unique for all board states - it seems to be the case, but I haven't sat down to try and show it. I feel like it would be quite succinct, too.

[@orangecitrus8056]

1:52 this reminds me of other fields of research where scientists narrow down the upper and lower bounds to attack the question from two sides. Maybe this question can be further narrowed down like this idk. I hope one day we will know the exact answer to this question

[@paulembleton1733]

I think you demonstrated proof for the gut feeling that it is practically impossible and pointless to count the number of positions.

[@isavenewspapers8890]

2:17 First position: 1. Nf3 d5 2. Ng1 Qd6 3. f3 Qf6 4. g4 Qh4# Second position: 1. e3 f6 2. e4 g5 3. Qh5#

[@janisschock9191]

17:30 is a wrong assumption. While it is true, that for *almost* all board states, there is an 'inverse', there are some, which have no inverse (though neglibably few, considering the overall amount of board states). The reason is, that as long as certain pawns have not moved, or only moved 1 rank up (for given player A), some of the non-pawn pieces can only 'toggle' between two positions. Moving back and forth between those positions will cause player A to 'waste' an even number of moves. If both players are so restricted, it is impossible for any of the game states to have an inverse, as by the configuration of the board alone, it is calculable whose player's turn it is. Take for example the sequence "1. a3 a6 2. Ra2 Ra7 3. Ra1". None of the states reached in this sequence have an inverse. There are other examples that involve knight moves (which also must always waste an even number, as each knight move always 'toggles' the color of field it stands on). For an inverse to be potentially possible, at least one king, queen, bishop or rook (of either player) must be 'free', meaning for any of those pieces, that it can move 'freely' in between at least 3 possible squares (or have been able to do so in the past). This is equivalent to all pawns except the pawns in front of the rooks being in starting position, and the rook-pawns being moved at most one field. It follows that the number of non-invertible positions is actually determinable a lot simpler than the overall positions, as the pawn structure of both players must be 'intact' (as described above) and then you can easily iterate over the possible combination of positions of rooks and knights (as those are the only pieces able to move in this scenario). It is therefore a given, that this number does not greatly affect the overall upper bound, because it only affects a tiny subset of all possible positions.

[@maxpacker8222]

good point, i should have been more clear about what i meant, that the argument we had used so far had been completely symmetric and didn't distinguish between white and black in any way, even though in reality there may be some difference between the two. i didn't consider what those differences might be, but i think what you're describing is totally right and that's a great example of another way we are still over counting game states.

[@Umbra451]

Actually, League of Legends is a solved game! The perfect move at any point in the game is to uninstall

[@Veptis]

Since there is theoretical longest game (and plenty permutations). Considering the sequence of moved as like a pgn seems to be interesting. And you could reduce any form of repetition. So turn it into a graph of reached states. I always wondered if rating how good(or bad) every legal moves are is a good practice exercise

[@maxpacker8222]

sure, people have also tried to calculate the number of distinct games of chess - a crude upper bound for that would be 267^12700 (267 = upper bound for number of legal moves in a position, 12700 = upper bound for number of half-moves in a game assuming 50-move rule is automatic) - that's an interesting question in itself but even if you knew the answer i'm not sure how you'd use it to help with the number of reachable positions

[@Veptis]

@@maxpacker8222 the main motivation for this approach would be that you only ever reach legal positions. And my maths professor strongly suggested to us (through some of their own research). Do tackle large combinatory problems with ordered representations like graphs or lattices. Since there is a lot of computational tricks to reduce them. And computational complexity isn't O(n^2). I will look around, but my idea is that any legal board state can be reached by at least one sequence of moves. and there will be one or more minimal sequences that reach that position. by representing it as an ordered system, you will be able to distinguish between moves that are reversible and those that are irreversible (pawn move, castle and likely all captures). So you can clearly follow this order of progression moves. And there will be an end (checkmake, stalemate, tie due to50 moves, draw). You would end up with a graph (not a tree) where edges are moves and vertices are board states. and it should be complete. I am sure someone has gone down this route before

[@umraissaleem1079]

You deserve way more subscribers. Loved the video

[@Skyb0rg]

DrRacket is a great programming language. Awesome video too

[@amitshukla1495]

Can we not statistically determine this, basically try randomly placing pieces on the chess board and calculating the number of times it is a valid position. Simulating this many times should give as a better estimate over time 🤔

[@glitchy5420]

Very insightful video! Chess is so complicated sometimes in terms of the extra rules like en passant and castling, which seem simple until you try to implement them into a chess engine, or use math to figure out anything chess related 😂

[@imumsi]

i might have missed it but kings also need to stay away from each other which shrinkens the upper bound a bit. you could also consider mirrored positions without pawns and without the right to castle as equivalent, taking away a bit of multiplicity

[@maxpacker8222]

ya true that would have been good to include in the limitations at the end

[@paulpinecone2464]

To the set of additional information you mentioned that is required to specify the game state, I would add a convention: That white pawns are moving upward. This affects the initial double move, en passant, and queening. If one wishes to be able to present a board from either players perspective, an additional bit of information is necessary. In practice this would only be needed in late game when pieces are sufficiently disordered that starting sides cannot be inferred.

[@bjarnelk3807]

The most impressive video I've seen all month🎉

[@chottomatekudasai-kun3887]

Count the atoms in the observable universe, arrange each one to a posible chess position. You're not even close to the total number of posible positions on a given chess game.

[@MrBrotatoHead897]

Great video and I've been enjoying all the content on your channel so far! I'm curious, what made you decide to use racket when writing your programs? I've never seen it used in the wild, but I've had a lot of experience using it in undergrad for a class I took/TA'd for.

[@maxpacker8222]

thanks :) Racket was the first language I ever used, my friend's dad showed me when I was a kid and then I kept messing around with it from time to time. then in college I showed up to the first day of a programming languages class and found out it was gonna use Racket which was a fun surprise, I ended up TAing for that class as well. most of my classes used other languages but I've always had a soft spot for Racket, especially for stuff like this where you just wanna get something simple done quickly. and I used Clojure for work for a while which is similar but I don't have it set up on this computer lol

[@NoriMori1992]

The "Moore's law or something" slide got me good 😂

[@EPMTUNES]

Cool video! Very intuitive explanation

[@ron_yyy]

you know he's a programmer when you start counting with 0

[@infernoplayzgames1684]

"No hidden information..." *Me laughing in en passant...*

[@maxpacker8222]

holy hell

[@eliasmazhukin2009]

@@maxpacker8222 New response just dropped

[@Digby8]

Really good video, weird to think that this question *could* be answered in my lifetime..

[@uz_ac]

now how many positions are in 5d chess

[@davidanderson_surrey_bc]

Sure, but did you remember to carry the 1?

[@SilentSword22]

if we are doing this with a brute force approach, can't you just randomly create a board, use a checker to see if it is possible then once the probability converges just take probability multiply by the total game board states and then get a reasonable guess?

[@maxpacker8222]

yep, that is what they did with github.com/tromp/ChessPositionRanking to get the estimate of 4.82 * 10^44 - although even writing a program that can check any single position is hard, sounds like they still had to go through some of them manually

[@anonymousanon4822]

I had the same thought but I'm thinking that even with extremely fast hardware and very optimized checking algorithm, you'd still only be able to check such a tiny fraction of the total number of (mostly impossible) board states that your confidence score is so absurdly low that the upper bound (with 95% certainty for example) ends up higher than what this guy figured out. Maybe (hopefully?) I'm wrong but that's my theory after thinking about this for 2 minutey.

[@maxpacker8222]

@@anonymousanon4822 where i ended up is about 10,000 times higher than the best estimate, so it might work ok if you took like a million random game states from there since you'd expect ~100. idk i only thought about this for a couple minutes too lol. but definitely you'd need to narrow it down some, the first upper bound of ~10^75 is way too high to be useful

[@psymar]

​@@anonymousanon4822yes, but the way random sampling works you can get a pretty high confidence pretty quickly. polls are good at predicting elections not because they ask a huge portion of Americans, but because they use a random sampling and do math that actually works even for an infinite population.

[@tomatoboi1-inf]

0:22 they could use that manhole cover that person is sitting on as a chessboard

[@olavisau]

Chess moves and positions can be encoded quite a bit, I wouldn't be surprised if the best move table could be possible with current technology. Just think how many positions would include moving the central pawns or checkmate in ones. You could also encode as move -> range of positions as moves can repeat but positions can't. One nice thing about this is that captures don't have to considered as all chess moves result in a moving of a piece and capture is always clear - it's either impossible or forced. It's actually interesting as to why chess notation even includes x as capture as it is implicit, same for checks and double checks.

[@elementgermanium]

Nah, even at a ludicrous minimum of one atom per state you’d still need a planetary-scale computer.

[@olavisau]

@@elementgermanium My point is that states repeat to an extreme extent that can be represented in ranges instead of each induvial state. Think - how many possible moves are there? like d5, e5, d4, e4 and etc.

[@jercki72]

12:06 that felt personal

[@kruksog]

Excellent stuff. Really enjoyed the presentation. Subbed. Please keep making videos.

[@limbolegs]

ive had an idea for making a list of all game finishing moves. all possible checkmates/stalemates by all possible captures of pieces, moves of pieces, promotions, and castlings. and then setting up a scoragami-style grid to see the most common in like the lichess database. i imagine casting with stalemate will be the least likely to occur

[@theaureliasys6362]

2:46 that board is unreachable from standard chess, but you almost certainly know.

[@TimothyChapman]

2:28 - Chat GPT thinks White has a legal move left.

[@ramdamdam1402]

Holy hell the Asmr makes me cry and i don't even have earphones.

[@dylanrambow2704]

Another approach one could take is to calculate how many positions there are with exactly x pieces on the board. It's real easy to calculate how many positions with only the 2 kings. With 3 pieces on the board it's still not so bad; just be wary about positions that would've had to arise from moving into check. But with 4 pieces it becomes quite complicated.

[@gn0my]

Wow! And somehow i manage to pick the worst ones constantly

[@alexrobinet7576]

Keep doing this please. Be the chess hero

[@archiveprovider3981]

There might be a way to ignore the 50 moves rule and bring down the number by a lot. Without the 50 moves rule the best move would be the one that (a) forces a win in the least number of moves or (b) if that is impossible forces a draw or delays a loss by as much as possible. This means that if you played using a look-up table that ignores the 50 moves rule the only situations were you would end up worse are situations where you were going for a mate in >50 that would have broken the 50 moves rule and therefore ended in a draw, that could have been prevented by moving a pawn or capturing. (The only other way I could think of to end up worse is if you could delay a loss long enough for the 50 moves rule to make it a draw, but instead you choose a different set of moves that delays a loss for over 50 moves, but includes pawn moves or captures thereby resetting the 50 moves, making it possible for the other player to win. This feels like something that would almost never happen.) I know that this would mean the result wouldn't be a true upper bound anymore, but I think that it could be reasonably assumed that the resulting number would still be greater than the number of board states you would have in a theoretical look-up table with the best moves for every position.

[@maxpacker8222]

yeah i don't think it counts as solving chess anymore if there are any states where it disagrees with the "real" table, but i agree there would probably be very few disagreements so maybe it's the next best thing

[@GrindelTF]

not sure if someone poined out yet but 17:32 the first position isnt possible cuz the queen cant reach the square in 2 moves without teleportation

[@maxpacker8222]

that picture is wrong i meant to move the e pawn instead of the d pawn

[@DemoboyOot]

it's possible. white could have spent moves moving knights, king, or f1 bishop. black could also have moved knights, king, bishop, or queen more than implied. 1. Nf3, e5 2. Ng1, Qd6 3. f3, Qf6 4. g4, Qh4

[@PlexusTen]

Excellent video!

[@madplayer1236]

(sniff sniff) I smell an underrated channel

[@FloydMaxwell]

16:56 - extra ")" at the bottom right.

[@maxpacker8222]

oh yeah, this was part of a larger list that i cropped to only show the last part, so there's an ending ) but not a starting (

[@FloydMaxwell]

@@maxpacker8222 Understandable. Your very analytical video got me analyzing the smallest things. Thank you for it!

[@lowflyingdonut]

Nice, I managed to sumble upon a video using Racket entirely by random.

[@zolariuscookie9318]

Racket, my beloved! Here, have my like!

[@TheGeckoIsKing]

I was literally thinking about this question 2 hours ago

[@Merluch]

Hidden masterpiece of a video.

[@dantedeloden]

im just curious if during the pawn structure calculations, the fact bishops only start on a specific color and when promoting to a bishop it stays on that specific color was inserted. im only at 15:37 so far lol

[@iwersonsch5131]

If we, for some reason, want to simplify, we can say that there are no more than 106 combinations of half-move number and en passant, and no more than 67 combinations of king position + castling rights for each side. This glosses over a few percent on each of them, but it's a lot simpler

[@maxpacker8222]

true, i think 106 for half-move number + en passant is just a better way of saying what i ended up doing, and 67 for king position + castling rights should be pretty close

[@iwersonsch5131]

@@maxpacker8222 you did prune it down a bit lower to just barely over 101 because most positions don't have the pawn structure for en passant If there was a rule that banned promoting pawns to a piece that had not yet fallen, the number of positions would probably drop a decent bit further

[@maxpacker8222]

@@iwersonsch5131 ah true

[@J4NTZ]

You can doble check, if you have a rook or a queen, and a knight or a bishop in the same file, you cam move the knight or the bishop to get doble check

[@maxpacker8222]

true, but not with the position at 20:24, hence "in a way that isn't possible for black to do in a single move"

[@mickeyrube6623]

What happens when you try to load a FEN file that is an illegal board state into a chess app? I assume it will give some sort of predictable message. So... Can't we write a program that starts to write every FEN broard state as described at 4:18, and have it keep a count of which ones can continue with a legal game, and which ones can't? Ofc it would be impossible for a computer to do all 13^64 states, but you could cut it off after a week or so and then have a ratio of legal states to illegal states. You then could use this to maybe get a more accurate estimate 🤔idk maybe?

[@maxpacker8222]

it might error on some unreachable states like no kings, double kings, too many pieces etc. but i don’t think any normal chess program would detect all the more subtle impossibilities

[@maxpacker8222]

using a random sample is how they got the best estimate of ~4.82 x 10^44, but you need to narrow it down a lot first because 10^44 / 13^64 is too small of a ratio to determine experimentally with any kind of precision

[@mickeyrube6623]

@@maxpacker8222 Yes. I now realize that many chess programs specifically allow some crazy piece combinations for the opening set-up for chess variants, while only denying things like both kings being in check.

[@daboffey]

Another impossibility is where the two kings are adjacent. Again, there are some situations that necessitating a king must have moved, imply that that side cannot castle.

[@maxpacker8222]

do you have an example of a situation where the king must have moved, but is on its starting square? i couldn’t think of any

[@daboffey]

@@maxpacker8222 One such example would be k7/7R/8/8/6PP/8/PPPPPP2/4K2R

[@DemoboyOot]

@@maxpacker8222 you might be able to find some if you look up the concept of 'dead reckoning'

[@razor2infinity48]

I think what people have been trying to calculate is not the possible amount of game states, but the total possible amount of games in chess. Using your upper-bound calculation for the amount of game states, the upper bound for the possible amount of games should be around 3.82*10^663637. absolutely unimaginable number!

[@maxpacker8222]

people have tried to calculate both, but in my completely subjective opinion this one is more interesting, since once you're in a particular game state it doesn't really matter how you got there. like, you could visit the US state capitols one by one in 50! > 3 x 10^64 different ways, but it's still the same 50 cities

[@EebstertheGreat]

While you need the halfmove clock to technically differentiate positions, you wouldn't need it for a table base. The number of board states should be a little over 2% of the number calculated by tromp, so around 10^43. Ideally you would store the DTZ of each position, but if you only care about positions that cannot be claimed drawn, you will never need a DTZ over 100 anyway. That allows you to strongly solve chess with a table base with 7 bits for each of the 10^43 positions. If we excavated the entire moon and turned its material into memory cell, each bit could have up to 300,000 atoms, which is comparable to the size of memory today. How hard could it be?

[@ANonymous-mo6xp]

You know where you pulled the answer for part 4 from!!! 😂😂😂

[@danielyuan9862]

Has there been any effort done on the lower bound of the number of chess positions?

[@maxpacker8222]

I'm not sure where the lower bound is at, the highest I've seen is 2,015,099,950,053,364,471,960 which is apparently the number of positions possible after 15 half-moves

[@thewhitefalcon8539]

You can't have two bishops on the same colour square unless one of them was promoted

[@maxpacker8222]

yeah i wasn’t sure how to include that in the calculation but i mentioned it at 19:40

[@campbellhutcheson5162]

the second I saw the racket code you had me

[@denalozecon9074]

I have never heard of any variation of Chess with more possible games than 5D Chess. I am curious which has more possible games; Sovereign Chess or Deuce Chess? Sovereign Chess has a lot more pieces, but Deuce Chess has 7 new types of pieces with new rules + all original pieces.

[@Chrischi3TutorialLPs]

Calculating castling rights completely is even more complicated than what you did. Why? Because other pieces have an influence on it. For instance, you cannot castle if your king has to move through check, or into check to do so.

[@maxpacker8222]

That’s true, but the “castling rights” are still there. Even if you can’t castle that particular turn, we need to keep track of whether the king/rook has moved, because if not you may be able to castle in the future, but if so you will never be able to.

[@hrnukeatp]

What about a position thats in check where you're forced to move your king (and therefore are forced to lose your castling rights)? In that case the position with and without castling rights should be the same since no future castling is possible? This might also be possible with a check where a rook is forced to move (to capture the checking piece)@@maxpacker8222

[@maxpacker8222]

sure, you could define those to be the same position, you could also say that if it's a checkmate/stalemate/50-move rule position then the castling rights/en passant rights don't matter - i went for the simpler, less strict definition since those cases would be hard to enumerate anyway

[@Dalroc]

@4:22 6 for the en passant check? EDIT: This part is wrong -> Shouldn't it be 256? 8 pawns that are either en passant'able or not, so 2^8? EDIT: Only one pawn can be en passant'able at a time. So either of the 8, or none of them, for a total of 9 possiblities, not 256.

[@ygalel]

Awesome approach Just out of curiosity why can’t we left-hand-on-the-wall approach this? Start by moving one pawn multiply number of possible moves, and keep doing that until you exhaust all possible cases?

[@unflexian]

because that would take too long to finish, like possibly on the order of the lifetime of the universe too long.

[@19LG99]

I think you overlooked the cases where casteling is denied by an opposing piece threatening one or more of the kings traveling squares

[@psymar]

at that point it's too complicated to calculate.

[@אלוהים-י8ו]

I think KZbin goes the more subs you have, the better microphone you have

[@Jrakula10]

17:17 your black pawn on D5 should be E5, gotta restart

[@maxpacker8222]

fuck, alexa delete the video

[@diveinnjim]

can you do the same calculations thing with a game of backgammon??

[@professorx3060]

I have a strange feeling that I watched this video a year ago. Also, yes, there are so many positions, but maybe only 10 billion "good positions" 😅 Where you try to play the most logical moves

[@maxpacker8222]

depends on your definition of "good" i suppose. if chess is a draw with perfect play, maybe there are under 10 billion positions that two perfect players could ever reach against each other while still forcing a draw, idk. but even if that's true you'd need to consider many, many other positions in order to be confident of that - if you could solve chess by only looking at 10 billion positions it'd be done by now. you might be able to solve it in some more clever way without looking at 100% of the legal positions, but i'm not sure how, and i'm not sure how many you would have to consider (although i imagine it's still out of the realm of possibility)

[@mrsesh7364]

maybe you watched that down the rabbithole episode on deep blue

[@rareram]

Minute 20... That knight example is also impossible since you put the kings in check without the knight being captured back in response. They would have to capture and exit the rook space without putting anything in check

[@maxpacker8222]

the only knight that comes within a knights move of the white king is white, and same for black, so i think it’s fine in that regard, the diagram is pretty confusing though lol

[@rareram]

​@@maxpacker8222my bad, perhaps red and blue for the different sizes would have helped me. Love the video, I like chess and I like math

[@jiaan100]

Threefold reptition and the 50 move rule are just tournament rules anyway

[@Ro-12-21]

I'm waaaaaay too dumb to watch this

[@Jrakula10]

do you need to take into account illegal castling moves because of check or attacked squares between the king and the rook?

[@maxpacker8222]

i don't think so - for board states where the king and rook are in their starting positions but castling is impossible due to check, it is still important to keep track of the castling rights in case the check isn't there later in the game

[@zoltantorok1189]

7:15 If 6.149 * 10^54 is less than the number of atoms in the sun and close and 9:11 4.64 * 10^53 is less than the number of atoms in Jupiter, then it can't possibly happen, the original must be way smaller than the sun, because those two are just about a factor of 15 from each other and the sun is 98% of the total mass in the solar system, meaning at least a 50 times difference.

[@xXJ4FARGAMERXx]

Mass does not mean a certain number of atoms, because there are heavy and light atoms

[@maxpacker8222]

yep you're right, 6.149 * 10^54 is way less than the number of atoms in the sun (~10^57)

[@zoltantorok1189]

@@xXJ4FARGAMERXx both the Sun and Jupiter are mostly made of Hydrogen and Helium. Mostly hydrogen.

[@zoltantorok1189]

@@maxpacker8222 i knew it ;) How much is in Jupiter?

[@maxpacker8222]

@@zoltantorok1189 the numbers i got were ~1.2 x 10^57 and ~1.2 x 10^54 by multiplying the number of grams by Avogadro's number, but that assumes every atom is hydrogen, so in reality they'd both be a bit less

[@carlcinco6675]

What a great way to end the video 😂

[@aos1932]

Could each single naturally occurable game state be saved as an image along with its evaluation. To be compared to any natural game position for example. We already partially have this, i.e. end game table bases, puzzles and tactics, opening theory and traps. If so could those images be used referentially to evaluate a position instead of running an engine ??? Almost like comparing two pictures

[@psymar]

For one thing you have to have accurate evaluations to compare against, which we mostly don't. for another, there's cases where very minor changes can completely change the evaluation. even in as simple an endgame as king and pawn vs king and pawn there's situations where whoever moves wins, and there's others where whoever moves loses. And these can even be constructed to be visually similar to each other.

[@walternullifidian]

I'm really glad you did this, so now I don't have to! Well, I'm pretty sure I couldn't do it anyway, since I don't have the math skills. 🖖

[@iwersonsch5131]

I wonder if it would be productive to make tablebases for - 8-piece positions where a pair of pawns blockade each other (true invariant) - 8-piece positions without rook, knight, or bishop (practically almost invariant, needs a carry-over asterisk to denote an unexplored option to underpromote) Each of those should have a similar amount of positions as the 7-piece tablebase

[@maxpacker8222]

I did some searching and apparently the first one's been done and that's how the longest known forced mate (ignoring 50-move rule) was found - see arves.org/arves/index.php/en/endgamestudies/theory/endgame-tablebases-check-a-7-men-position?view=article&id=1533&catid=2

[@iwersonsch5131]

@@maxpacker8222 Pretty neat. Tho it looks to me like it only seems to have positions where each side has exactly one pawn, leaving 4 non-pawn pieces. If someone filled in the positions where more than 2 pawns may exist, as long as there is a pair of pawns that blockade each other, the tablebase should still end up smaller than the 7-piece tablebase. Having at least one blocked pawn should be a lot more common than having exactly one pawn, so the difference would likely be quite meaningful for the usefulness of 8-piece tablebases. Actually, it should even be feasible to have 9-piece tablebases where at least 2 pairs of blockading pawns exist, so long as these pairs of pawns aren't on neighboring lanes. Such a tablebase would only contain 21*15*15 constellations of those pawns, leaving only 2 kings and 3 more pieces/pawns unaccounted for. A 7-piece tablebase has 5 variable pieces or pawns, an 8-piece tablebase with blockading pawns has 4. A 9-piece tablebase with 2 sets of blockading pawns only has 3. That's what could make the computation practical

[@maxpacker8222]

@@iwersonsch5131 ah you're right yet again. yeah that would make sense for the 8-piece with 1 blocked pair of pawns and 9-piece with 2 nonadjacent blocked pairs to be similar size to the 7-piece, since you can kinda think of each blocked pair as a single piece. maybe you could keep going to 10-piece with 3 nonadjacent blocked pairs and 11-piece with 4 nonadjacent blocked pairs though at that point it's not much more than kings and pawns

[@mskiptr]

Cool to see Racket!

[@oinkymomo]

where is the 6 coming from with en passant rights?

[@giladu.6551]

i still don't understand how you get 6 for en passant multiplicity, can someone explain?

[@maxpacker8222]

if it’s white’s move and the fifth rank is filled with pawns in the pattern BWBBWBBW, then there are 5 black pawns that could potentially be en passanted, or maybe none could be, depending on black’s last move, so thats 6 possibilities. and there’s no way to get it higher than that

[@giladu.6551]

@@maxpacker8222 wonderful, thanks!

[@Mar184]

If the intent of counting or enumerating game states is to still serve the original goal of finding the optimal strategy, we can also exclude some legal positions on the basis of dominance, i.e. who can only come about through either player playing in a way that is certainly suboptimal so there exists a related position that is in every way preferable over it to the player whose choice it was which will realize. The easiest class of positions to identify as such is due to promotions. A pawn may be promoted to Rook, Knight, Bishop or Queen. But the Queen's allowed set of moves is a superset of both the Rook's and the Bishop's. Therefore, in any game state where you have a promoted Rook or Bishop, it would be more desirable to have promoted to a Queen instead, because she can do everything the Rook or Bishop can and more. Only the Knight can do moves a Queen can not. Therefore, one only needs to reasonably consider those game states in which all promotions have been made into Queens or Knights. Anything else will not occur in the game tree of two perfect agents playing each other.

[@maxpacker8222]

in general yeah, although there are some cases where under promotion is necessary since promoting to a queen would lead to stalemate, so i’m not sure we can rule out every single one of those positions

[@Mar184]

@@maxpacker8222 Damn, forgot about the stalemate rule. You're right, very good catch. Due to that rule it isn't always desirable to have more targetable fields. While it might be easy to except board states where the promotion causes a stalemate immediately, I imagine it becomes tricky to ever rule out with perfect certainty that a queen promotion wouldn't admit the other player to enforce a stalemate further down the line. It would require some kind of proof system to decide whether in a given game state with a promotion, the opponent can enforce a stalemate against a promoted queen that he couldn't enforce against a bishop or rook. I think it's fair to say that intuitively, in almost all chess game states, having a strict superset of avenues of attack is a bigger advantage to yourself than your opponent. So maybe the cases where it is not are a restricted enough subset of states to characterize and enumerate them. But clearly it isn't nearly as easy as I thought.

[@Maxmaxs5]

Absolutely insane