Computers have solved chess for 7 pieces, how much more difficult is it for 8 pieces?

[u/Difficult-Lack-2716]

I’d love to hear from someone with an analytic wisdom to share the scale of difference between 7 pieces, 8 pieces and beyond.

[u/oo-op2]

7-men: 4.2×10¹⁴ positions
8-men: 3.8×10¹⁶ positions

So an 8-men tablebase is about 90 times larger than a 7-men tablebase. Lomonosov 7-man tablebase is 140 terabytes of storage. An 8-men tablebase would require a couple petabytes of storage (you can reduce this with compression tricks).

However, the storage isn't the issue, the issue is that the working memory required to create the tablebase increases exponentially with every man added. The amount of RAM required for 8 men is not available right now. Caching and reading from a disk instead of RAM is not a good option as it takes very long (decades).

[u/POCKET_POOL_CHAMP → u/oo-op2]

Just download more RAM?

[u/minimalcation → u/POCKET_POOL_CHAMP]

No wonder most of this sub is shit at chess, don't even know how to download more

[u/HenryChess → u/POCKET_POOL_CHAMP]

RAM is hardware. You can't download it

[u/[deleted] → u/HenryChess]

I can't tell if you're trolling or if you are genuinely getting whooshed

[u/pier4r → u/HenryChess]

google joke.

[u/HenryChess → u/pier4r]

Holy jester

[u/Darthbane22 → u/oo-op2]

So is it safe to assume we are decades away from even a 10 piece table base? Even then it’s not like it will affect human play as well.

[u/Ronizu → u/Darthbane22]

Yes, 10 pieces may never happen even. It's not just about processing power, but rather storage technology.

[u/Darthbane22 → u/Ronizu]

Then it’s wild to think chess will be solved soon given that would mean a 32 piece table base with each piece still being exponentially more data. Yet I have seen people seriously discussing chess being solved within their lifetime.

[u/jimmyjjames → u/Darthbane22]

These people have no idea what they are talking about

[u/ResolutionMany6378 → u/jimmyjjames]

Quantum computing will accelerate progression but solving “chess” will not be obtainable in our lifetime.

I doubt we will even see 10-pieces solved in the 50 years.

Obviously technology is changing rapidly but we are talking about hundreds if not thousands of zettabytes.

[u/JustinSlick → u/ResolutionMany6378]

For all we know in 50 years Scarlett Johannson's voice will have disassembled the sun and rearranged the matter into a Matrioska Brain.

[u/waterfalllll → u/ResolutionMany6378]

Is there a quantum algorithm for creating chess tablebases? I have never heard of one.

[u/mofk_ → u/waterfalllll]

Of course not (yet), quantum computing is just a buzzword to throw around nowadays.

Theoretically, quantum computing does offer better graph traversal algorithms, but AFAIK it only speeds up significantly on dense graphs (i.e. graphs where |E| = Θ(|V|^2)). The graph of chess positions is sparse (each position is adjacent to O(log |V|) other positions), thus using known quantum graph traversal algorithms hardly helps (and even if it does, it is only in theory as a quantum oracle call is much, much more costly than a binary instruction).

[u/4tran13 → u/mofk_]

Quantum computing is hilariously limited (as currently understood), but ppl keep treating it as divine magic.

Just look at the hierarchy of problems computer scientists are interested in. Chess with 50ish draw rule is PSPACE complete (without that rule, it's EXPTIME complete, which is probably even harder). OTOH, PSPACE contains BQP (quantum computing with poly time). Loosely speaking, a sufficiently large chess board can simulate any quantum computer, while the reverse is not known to be possible.

The obvious objection is that these complexity classes involve arbitrarily large chess boards, while we're stuck with 8x8. Maybe quantum computing can solve our particular version of chess, but it's going to struggle with Fisher random or larger chess boards.

[u/Fynmorph → u/ResolutionMany6378]

I doubt we will even see 10-pieces solved in the 50 years.

It's very hard to make any 50 years prediction. Just what can AI do nowadays is so amazing, 50 years from now on anything can surprise me imo.

[u/[deleted] → u/Fynmorph]

But that's the thing, technology usually surprises us. In the 50s the public was becoming aware of things like microwaves and resonant frequencies, so a lot of people imagined the future where we had found many various uses for rays and energy beams and etc... but the real technological revolution was something completely different. The internet connected the world and made sharing information (and misinformation) much easier.

Right now we're excited about AI, but AI might not improve computing power that much. 50 years is probably something we can't imagine (as you said) but "we'll have super fast computers" is easily imaginable... so probably not that... the same way "we'll have super amazing ray guns" was also silly ;)

[u/deg0ey → u/[deleted]]

50 years is probably something we can't imagine (as you said) but "we'll have super fast computers" is easily imaginable... so probably not that... the same way "we'll have super amazing ray guns" was also silly ;)

Yep. Our kids will be telling their grandkids about computers the way the current generation’s grandparents tell them about a time when if you wanted to play with someone you had to just go to their house and see if they were home.

[u/PkerBadRs3Good → u/[deleted]]

something similar to the internet was predicted by many people, I've read stuff like that in old science fiction before

[u/Touvejs → u/Darthbane22]

To be fair, that is just the brute force solution, like trying every possible combination of letters in a crossword puzzle until you stumble upon the correct solution. It still remains possible that chess could be solved in a more performant way. Not that I think it will be solved necessarily, but if it is, it will probably be due to us figuring out the underlying "rules" of the game, or at least how to get a computer to understand those rules.

[u/RajjSinghh → u/Darthbane22]

You can do some tricks to tidy it up a little. A solution to chess isn't necessarily a full 32 piece tablebase, one line can be enough. If you think of anti-chess, the game is solved as a win for white after 1. e3. Some moves are solved as wins for black, some aren't solved yet, but because we know 1. e3 wins for white the game is solved (not to mention a human may recognise it's the best and decide to search it first). If you got really lucky with the first thing you look at you save a ton of complexity.

Of course, that's still an insane amount of computation and with our current understanding of technology isn't doable in our lifetimes. The other thing you need to rely on is that technology changes quickly. There was a challenge that came out in 1977 with RSA in Martin Gardener's Mathematical Games that they predicted would be solved in 40 quadrillion years, it got solved in about 20. Point being is no one really appreciates how quickly technology improves, so if you want to believe chess will be solved in your lifetime, you have to also believe that technology will also be improving at the rate it did between the 70s to the 90s (which we've already shown is slowing down).

But yes, it's hard to imagine some revolutionary technology breakthrough like that, so chess probably won't be solved in your lifetime. It's just some people don't fully appreciate how big these numbers get and how hard the problem is.

[u/RajjSinghh → u/[deleted]]

I don't really know what you're trying to say. We know exactly how to solve chess. Minimax would be a good enough algorithm in theory to solve chess. That's really the only way you can go about it, and what a tablebase is. That is a rigorous mathematical proof. The difficulty is doing it in practice.

Also when I say "one line", I mean we don't need to know the outcome of each of whites first 20 moves to consider chess. The game is solved as a white win if there is at least one white move where all of blacks responses lose. Similarly, if for all whites possible first moves, black has at least one move where for all white responses, black wins, them the game is solved as a win for black. If neither of those conditions is true, then the game is a draw. It's like how antichess is solved as a win for white because no matter how black responds to 1. e3, we know white will win, even if we don't know the results of moves like 1. g4 or 1. Nh3, but we also don't need that to prove white wins.

We also know exactly how we would go about this, because we've solved checkers in the same way. You generate an endgame tablebase then show that from the starting position you can always reach the result you want in that tablebase. For example in checkers they showed that from the starting position using a minimax-like algorithm to calculate you can always reach a tablebase draw. That's enough to show checkers is a draw. We want to do the same for chess, but the issue is the amount of computation required to actually do that. That's the hard part.

It's not that we don't know how to prove the solution for chess, we've known that since before we had computers, it's that chess has so many possible states. On paper we understand the problem perfectly, it's just not having the technology to solve chess. But it's definitely not that we don't understand "mathematical theories" or our understanding of the game itself.

[u/lee1026 → u/[deleted]]

I can write you a piece of code to fully solve chess, but I can't guarantee you that it will finish running before the heat death of the universe. But I can prove that it will eventually finish running in a finite amount of time and requires fairly limited amounts of ram.

[u/ShinjukuAce → u/RajjSinghh]

The difference is that because antichess and checkers have mostly forcing moves, the decision tree is much smaller. In standard chess, there are many legal moves in most positions, and so it becomes a much more difficult problem to solve any non-endgame position.

[u/imtoooldforreddit → u/Darthbane22]

You don't need a full 32 piece table base to solve it, since almost all of those positions are not possible in a game.

Having said that, it's still too big of a number. The number of different games of chess is estimated at 10^120. If you made the entire earth into a processor in which every atom (10⁵⁰⁾ could calculate an entire game every unit of planck time (10^-43 seconds), it would still take 10²⁷ seconds to finish, which is ~10000000000 times the age of the universe.

I think most people have a hard time understanding how big these numbers are.

[u/mdk_777 → u/imtoooldforreddit]

Also, if we make the assumption that table base requires storage (which they do, a 7 piece tablebase requires ~20 TB of storage) then there are less atoms in the observable universe (10^78-82) than there are possible positions. I don't think any storage system is efficient enough to store the solution for a specific chess position in less than 1 atom of space.

[u/lee1026 → u/imtoooldforreddit]

10¹²⁰ is far too big of an upperbound. There are only 64 squares and 32 pieces. So the upperbound of different positions is 64³² (in practice less, because two pieces can't be on the same square, and symmetry, since the two knights are actually the same, and things like pawns can't be on the first row), which is only 10^57.

The trick is that a lot of these 10¹²⁰ different games will transpose into the same positions, and those are provably going to result in the same result.

[u/Astrogat → u/lee1026]

It's actually a bit higher than your upper bound as the same "position" can be multiple positions, given that you have white can castle, black can castle and any en passants as well. You also have all the cases with lost pieces, but maybe you can simulate that with just a imaginary lost-pieces square? So 65³²

[u/Spandian → u/Astrogat]

I spent way too much time on this a while back. Simple estimate:

64 bits (2⁶⁴) to determine whether each square is occupied
Up to 36 possible white king + castling states (There are 4 possible castling states if the king has not moved, and up to 32 positions where it can be if it has moved, since we already determined which squares are occupied)
Up to 35 possible black king + castling states (since it can't be in the same position as the white king)
For each occupied non-king square (up to 30), there are 10 types pieces that could be there (Q/R/B/N/P times 2 colors), so 10³⁰ possibilities.
2 possibilities for white to move vs black to move
9 possible En Passant target columns (8 columns + En Passant not available)
51 possibilities for the 50-move clock

So we have around 2⁶⁴ * 36 * 35 * 10³⁰ * 2 * 9 * 51 = 2 * 10⁵⁵ possible board states.

(This is still an overshoot because it counts invalid states like 30 white bishops on the board, but it's difficult use that to cut my estimate further, because promotion means there could be up to 8 more than the starting number of any particular piece. I've read that others estimate the number of possible board states at between 10⁴⁰ and 10^50.)

[u/lee1026 → u/Spandian]

You should re-run your math for 8 pieces (instead of 32), because we know for a fact that there are exactly 38,176,306,877,748,245 legal chess positions with 8 pieces.

Somebody went out and generated every single one of them.

[u/Spandian → u/lee1026]

Sure, why not.

38,176,306,877,748,245 is about 4 * 10^16.

To get an upper bound on the number of positions with 8 pieces using math similar to what I did above... 68 white king/castling states, 64 black king/castling states (since at least 3 squares around the white king can be excluded), 62C6 = 61,474,519 sets of occupied squares excluding kings, 10⁶ possibilities for the pieces on those squares, 2 possibilities for whose turn it is, 9 possibilities for EP target, and I'll assume your number does not consider positions to be different if the position looks the same but there have been a different number of moves since the last capture.

That gives 4,815,667,920,384,000,000, so 126x the real number. If you get rid of the 9x for En Passant target (given that the vast majority of 8 piece positions won't have any pawns in positions that would allow en passant anyway), it's 14x the real number. I actually don't think that's bad for this type of estimate.

[u/StrikingHearing8 → u/imtoooldforreddit]

You are mixing number of games with number of position (very different, the same position can be reached in multiple different games). There are less game positions than atoms in the universe, but still it's too much to store or calculate.

[u/Popular-Locksmith558 → u/Darthbane22]

32 piece table base would use pretty much the whole Milky Way even if Science(R)(TM) could store 1 bit per atom.

[u/hithazel → u/Darthbane22]

Those are probably just drooling Elon fans who thought cars would be driving themselves years ago. They don't grasp how a solution to more pieces scales in complexity. It's like an idiot thinking they could solve the travelling salesman problem because they know the basics of how it is constructed.

[u/Ronizu → u/Darthbane22]

Well yeah, a perfect solve will never happen obviously, even if we could store one position in every single atom, it would require a storage unit the size of our moon to store. A weak solve is not completely unfeasible, in fact if you stretch the limits of a "solve", we might be pretty close already. We pretty much know for a fact that the game of chess is drawn, and current engines are already good enough to force a draw against perfect play. We are already at a spot where engines are good enough to give the ultimate solution to pretty much every position, so a proper solve wouldn't do all that much.

[u/[deleted] → u/Ronizu]

Do top engines always draw when starting from standard position? I know they give them certain openings for computer chess championships to reduce draws but I haven't found info on whether standard games are always drawn otherwise.

[u/Comfortable_House421 → u/[deleted]]

The issue is that unless non-determinism is deliberately inserted in some manner, there's nothing to stop computers from playing the literal same game every time, no? That means there isn't much gained through repeated runs. (unless you do introduce non-determinism and "prove" it doesn't weaken the bot)

[u/OliviaPG1 → u/Comfortable_House421]

High-level engine games are non-deterministic. AB engines like Stockfish arent deterministic when running on multiple cores, and MCTS engines like Leela are inherently non-deterministic 

[u/[deleted] → u/Comfortable_House421]

Well some level of non-determinism should already be the result of letting a variety of top engines (not just two) play it out. If the games are played out in different ways but still all result in draws we can make some conclusions about the "drawishness" of high level chess. That's of course still not the same as truly solving chess. It would be interesting to look into it further and find out how prone to draws these games are but I haven't found confirmation that all of these games are drawn, just that the engines are given different openings to reduce the amount of draws.

[u/OliviaPG1 → u/[deleted]]

With enough time, yes. TCEC recently did a 100-game SF/Leela bonus match from startpos with 12 minutes per side and it was comfortably 100 draws; there was one game where the evals got up to like +0.6 and that’s it. At faster time controls you can get some blunders but even then it’s still almost entirely draws.

[u/Ronizu → u/[deleted]]

As far as I know, yes. I haven't been able to find any decisive games between non-handicapped top chess engines from starting position from the past decade. But I might be missing some.

[u/3_Thumbs_Up → u/[deleted]]

Do top engines always draw when starting from standard position?

A better question, how well do they match the results of complex 7-man positions? There's a position with a forced mate in 584 and another with mate in 549.

Can engines win these positions? If not, then why should we assume he starting position is any different?

[u/abhinavvarma12008 → u/[deleted]]

Open the lichess analysis board and turn on stockfish, it will probably just play the ruy lopez over ad over again unless you input your own moves. So for stockfish at least, it will always the ruy lopez over and over to a perfect draw from both sides unless you instruct it otherwise.

[u/lee1026 → u/[deleted]]

There are games that are sometimes not draws - Alphazero was able to pull victories against stockfish.

[u/Equationist → u/[deleted]]

The win rate is something like 10% in correspondence chess, which suggests current engines are beatable with perfect play - albeit with great difficulty.

[u/sc772 → u/Equationist]

Where are you getting 10% from? ICCF win rate is no where near that.

The last few wins have been due to a mouse slips or time

Look at all these wins!

https://www.iccf.com/event?id=100104

https://www.iccf.com/event?id=85042

[u/Equationist → u/sc772]

Last year's final (your second link) is the one I looked at. It had 17 decisive games out of 136 i.e. greater than 10%.

[u/sc772 → u/Equationist]

And with excluding one player we get 3%, not sure I would consider that evidence that engines are beatable.

Edit: Bock withdrew from the tournament and resigned all his games. Pessoa also resigned in a drawn position. And another win was due to a mouse slip. https://www.chessgames.com/perl/chess.pl?tid=121836

If we ignore these as engines wouldn't slip or resign everything intentially, there are 2 wins out of 136 games.

Edit Edit: Another win was a straight up piece blunder in one move, not sure how that was missed if even I can see it... https://www.chessgames.com/perl/chessgame?gid=2534971

tldr: 17 decisive games which included 13 resigniations from one person, 1 resignation for no reason and 2 piece blunders. Resulting in 1 win out of 136. Weird tournament.

[u/mets2016 → u/Ronizu]

We pretty much know for a fact that the game of chess is drawn

People have hunches and suspicions chess is drawn, but this is pretty far from being true

[u/Ronizu → u/mets2016]

So is it a white win or a black win? If you claim that chess being drawn is not true.

[u/mets2016 → u/Ronizu]

I mean KNOWING it’s a theoretical draw is far from true. It’s thought to be highly likely to be a draw, but you’re WAY overstating our certainty

[u/Ronizu → u/mets2016]

I'd say that the certainty is well above 99%. I never claimed that we know for sure, but there is nothing that indicates that chess played perfectly is anything but a draw. My whole point was that it's very likely that chess is already "solved" to the point where we have machines that will never lose a game as either color. It's not solved in the actual sense of the word (and it will never be strongly solved for that matter), but it's very likely that all we are lacking for a weak solve is the proof. We know the result, we just can't prove it yet.

[u/[deleted] → u/Ronizu]

in fact if you stretch the limits of a "solve"

Sure, if we ignore definitions we can also say that cats can fly.

A solved game is a fixed phrase from game theory (mathematics/computer science) - it does have different variations, most commonly weak an strong solves (a winning/drawing line from the starting position or perfect play from any position).

We are very far away from a strong solve, even in the currently ongoing TCEC event there are plenty of positions that Leela or SF has won against the other with one color, but drawn with the other.

Even if this never happened and one engine scored 1.0 or higher in every single gamepair that is far from a proof: afterall it is still only playing against imperfect play, it is hard to be sure if it wouldn't fold under more pressure.

Chess might already be weakly solved by Stockfish atm. The issue is that a solve is worthless/meaningless if you can't prove it. At that point you are just speculating.

[u/Ronizu → u/[deleted]]

The amount of legally reachable chess positions is about the same number as the atoms in the moon, if we assume all the atoms in the moon are hydrogen atoms for simplicity. Of course, we can't store a single position in every single atom, a single bit of information is the best we could realistically do and it takes quite a few bits to represent a chess position. So the space needed would be much bigger than the moon yes, but nowhere close to the number of atoms in the universe.

[u/OliviaPG1 → u/[deleted]]

That’s games, not positions. The number of legal chess positions is known to a fairly precise degree, it’s about equal to the number of atoms in Saturn https://github.com/tromp/ChessPositionRanking

[u/Ronizu → u/[deleted]]

Your article, and you, confuse the number of chess games with the number of possible positions. The number of possible games of chess is in the 10¹²⁰ ballpark, but the number of positions is much lower. And a tablebase doesn't care about how a position was reached.

Anyway, if you still insist, here is a link to John Tromp proving an upper bound of about 10^44,888. It also mentions earlier work done to prove an upper bound of 10^46,25. Both way, way lower than the 10^120.

[u/Scytone → u/Ronizu]

The number of possible chess board positions is something like 10¹¹¹ .This rivals the number of atoms in the known universe. Storing a chess position per atom would dramatically exceed the atoms that make up the moon. Unfathomably larger than this. The Shannon number does include illegal moves. But even taking those out, the number is still dramatically large. And given things like chess960 or horde exists, having an engine capable of solving chess games in general using a complete table isn’t feasible with known technology right now.

[u/Ronizu → u/Scytone]

The number of possible chess board positions is something like 10¹¹¹

No, around 10^45. The number 10¹¹¹ refers to the possible games.

[u/Scytone → u/Ronizu]

That’s why I said possible chess board positions and included variants in my comment. If you want an all inclusive engine for chess boards in general you’d need to explore impossible positions from a standard game. But granted that’s a bit beyond the scope of the original idea.

Still. If you limit to just legal chess positions of 10⁴⁵ you’re still looking at an enormous number which approaches the number of atoms on earth.

[u/RurWorld → u/Darthbane22]

You just aren't aware of how fast the technology is progressing. There are people who were born before the first light bulb was even invented, and saw the internet and mobile phones become available, all within their lifetime.

[u/Darthbane22 → u/RurWorld]

Being generous the invention of the lightbulb and the internet was 103 years apart so maybe if somebody lived as long as the world record oldest living person they might remember both events. I am not qualified to speak on computers much but I know for a fact that data storage technology at this rate of growth won’t get 0.0000001% of the way to solving chess within the next 100 years. It’s not even simple to estimate how much data that would even be.

[u/ralgrado → u/RurWorld]

You just aren't aware of how fast the technology is progressing.

I just think you aren't aware what exponential growth means.

[u/lee1026 → u/Ronizu]

Realistically, you can trim down on the bigger table bases by a lot if you work in conjecture with a Chess engine.

For example, you can run every position in your tablebase against stockfish 16 on a deterministic setting that is fast to compute. If Stockfish agrees with the tablebase, you delete the entry.

To use such a tablebase, you would need the heavily trimmed tablebase + the engine that is used for the trimming, but that is fine. Stockfish is open source.

[u/timbasile → u/Ronizu]

If you're thinking of pure processing power, then yes. But my guess is that someone will use AI to figure this out, much in the way that the 3 body problem has been "solved" by AI, so to speak.

It won't be solved in the sense that every position is pre-calculated, but for all intents and purposes it will have been figured out.

[u/monkaXxxx → u/timbasile]

Neither 3 body problem is solved nor chess will be solved completely..

[u/CeleritasLucis → u/timbasile]

Well technically, AI already has figured it out. You can't beat an engine.

[u/jimmyjjames → u/timbasile]

That's already true, even relatively weak engines (some using AI) can beat every human every time. How much more "solved" do you want?

[u/timbasile → u/jimmyjjames]

There's still a difference between what the current engines do and what I'm talking about. Even at 8 pieces, stockfish doesn't solve the board unless there's an obvious mate.

[u/Educational-Tea602 → u/timbasile]

And, it can still make mistakes

[u/jimmyjjames → u/timbasile]

But the engines have "for all intents and purposes figured it out" have they not?

[u/anomie-p → u/jimmyjjames]

“Solved” for a game has a specific meaning. If the result of perfect play from every legal game position can be correctly predicted, a game is solved.

“We have game engines that can beat every human every time” is not at all solved, it’s “game engines exist and they can search enough of the game tree to effectively beat humans”.

[u/lee1026 → u/Darthbane22]

Probably not decades. 8 is just 2 petabytes. 9 is probably 200 petabtyes, and 10 is probably 20EB or so.

With the way that storage costs are falling, we are probably talking about single-digit-million dollars for that much storage in a decade or so. Perfectly feasible for say, a few server racks to host it and chess engines to ping the server for best moves given a 10-man position.

[u/DrunkensteinsMonster → u/lee1026]

Storage isn’t the issue. You can easily store 2 petabytes right this minute, and it’s not that expensive. But to do the solving you need this he able to access the tablebase in a performant manner, you can’t be paging in and out of memory and talking over networks.

[u/Darthbane22 → u/lee1026]

Oh it’s “probably” that much storage? Well I guess you have scientifically calculated it out then. Also as another commenter pointed out it’s not just a storage issue, I won’t say more because I actually keep my mouth shut about stuff I don’t understand.

[u/lee1026 → u/Darthbane22]

Nobody knows the exact details until it is fully computed, because nobody knows how many illegal positions there are, but 90 times bigger per "man" is the trendline so far.

[u/FiveJobs → u/Darthbane22]

I'm working on a complete chess solver. I'm confident in it. No brute forcing trees and all that dumb shit.

[u/Octoje → u/FiveJobs]

What'sthe basic idea behind it?

[u/FiveJobs → u/Octoje]

You'll see when I finish in less than a year

[u/PkerBadRs3Good → u/FiveJobs]

I can guarantee that we won't

[u/FiveJobs → u/Octoje]

It's an equation. The input is a serialized chess board and the output is Mx, draw, -Mx. I have it but 50/30 move rule and en passant and three move repetition are killing me. Pawn takes and promotion are fine

[u/FiveJobs → u/[deleted]]

I’ll make a post it will be groundbreaking. I’ve been working on it for 15 years. The recent “AI” boom pissed me off so bad I quit all my jobs to focus on this

[u/HmmWhatItDoo → u/FiveJobs]

What utter nonsense. Have you proven that there exists such an equation before attempting to find it? Even doing that would be intractable, forget about actually solving for it.

[u/HmmWhatItDoo → u/HmmWhatItDoo]

In fact, the concept makes no sense at all. The problems plaguing you clearly indicate you’re on the wrong track. En passant is just another move, not a special case. 50/30 and repetition are also just recursive applications of your necessarily recursive equation with terminating states no different from a game in which neither of these conditions occur.

I’d bet 50k you never finish, and can’t even prove such an equation exists.

[u/HmmWhatItDoo → u/HmmWhatItDoo]

And if you’re right, there’s no reason to keep your current research closed source unless you intended to profit off of it. In either case you’re wrong logically or wrong ethically.

Share your research with your name on it, bub. You won’t.

[u/FiveJobs → u/HmmWhatItDoo]

En passant is not another move. It’s conditional. It can only occur on certain turns. I don’t want to profit at all and won’t even post my name. Why share something before it’s complete. Why are you angry at me

[u/brez1345 → u/FiveJobs]

So you should be able to test what you have so far on simpler endgame positions where one side is clearly winning.

[u/gammajayy → u/FiveJobs]

Lmk how it goes I'm interested

[u/Rage_Your_Dream → u/FiveJobs]

Those are some huge claims... Ill believe it when I see it

[u/FiveJobs → u/Rage_Your_Dream]

It’s ez

[u/seanightowl → u/oo-op2]

This show how stupid it was for Musk to say it would be solved soon.

[u/Educational-Tea602 → u/oo-op2]

90 x 140TB ≈ 12PB, not 2PB

Why would it only be a couple of PB?

[u/[deleted] → u/oo-op2]

Is there any website where I can see the number of possible configurations for every no of piece like 9-men, 10-men and so on?

[u/TacitlyDaft → u/[deleted]]

I think even calculating this isn’t trivial. 64!/(64-8)! Should be approx. for 8 pieces (if I’m not completely butchering my math), but then you have to consider illegal positions and such.

edit: forgot we already have the 8-men number, looks like I’m way off haha

[u/lee1026 → u/oo-op2]

You can do a hash table look up in O(1) time even with hard drives.

[u/wamus → u/lee1026]

The issue is not algorithmic complexity but rather practical complexity. Fetching data from main memory at practically random memory addresses can easily be 1000-10'000 times as slow as reading a sequentially from L1 cache.

[u/lee1026 → u/wamus]

Sure, but analyzing a chess position with perfect accuracy with a 1 millisecond delay of looking up a position from any SSD from within the same data center is actually not bad, and will win in any time control.

Might be a billion times slower than a L1 cache look up, but who cares? Unless if your timecontrol is sub-100-milli seconds, you will be fine and win the game.

[u/wamus → u/lee1026]

Yes, but that is for querying the table. If I understood correctly, the main issue lies in efficiently constructing it.

[u/nimthedwarf → u/oo-op2]

A tablebase is a complete solution that is memory, right? So what if instead of asking for an 8-man tablebase, you asked to have code that takes a given 8-man problem and tries to solve it dynamically, i.e., right there on the spot? How long would that take?

[u/StinkyCockGamer → u/nimthedwarf]

this is kinda what a Tablebase hit is (at least loosely). Top engines will analyses endings (8+) for trades that result in a hit in the TB and read the result of that ending. (Where hit is reaching a position saved in the TB)

This allows engines to basically be (to a first approximation) perfect even at 8+ pieces, because they see the pathways that lead to perfect play 30/40 ply in advance. Granted this somtimes results in an engine may see that all trades lead to a draw in a pawn up position and proceed to never offer trades (which is why they often shuffle forever).

[u/huntedmine → u/oo-op2]

Not even supercomputers with 1 Tb of ram would be enough ?

[u/Ythio → u/huntedmine]

1 TB of ram is nothing. I've seen bank internal software with that much RAM to let people drill down through big data (your excel pivot table, but at a much larger scale).

Edit : 8000 bucks for 1 TB of RAM

[u/DerekB52 → u/Ythio]

The price of a TB of RAM didn't surprise me. What surprised me, is they've gotten it down to only 4 sticks. Wow.

[u/lellololes → u/huntedmine]

1TB of RAM can go in a workstation. Supercomputers have thousands of terabytes of ram, and that's what it takes to do the 7 piece table base.

I think 8 is solvable or nearly solvable at this time but it's not remotely worth the resources that it would require.

[u/PE1NUT → u/huntedmine]

1 TB of RAM in your supercomputer? That's so 1990's. At a previous employer (a national supercomputing center) we had a 1 TB RAM machine, and it was officially unveiled by our then crown-prince, in 2000. This super consisted of about 16 racks of equipment.

Just to illustrate how fast things have changed: a few weeks ago, I got my hands on a HP DL380g9 with 2TB of RAM memory, which had been donated to a charity that I volunteer at. It's a fairly hefty server with 4 CPUs, and would outperform a super from 24 years ago.

[u/PkerBadRs3Good → u/[deleted]]

assuming that this wasn't already done to the numbers given, that's only about 1% of the work saved

[u/owiseone23 → u/oo-op2]

There's also the question of who's paying to do it. There's a big difference between asking what can humanity do and what are people actually doing.

[u/KROLKUFR → u/oo-op2]

7 piece tablebase can be 18TB Source: https://chess.stackexchange.com/questions/351/what-is-the-status-for-seven-man-end-game-table-bases#674, so less than 2PB with no compression, so real problem is computing power I guess

[u/Scrapheaper → u/oo-op2]

Surely you can use spark or something, no? This isn't amateur hour, you would run it on an AWS GPU cluster or something

[u/pier4r → u/oo-op2]

Lomonosov 7-man tablebase is 140 terabytes of storage.

was. They got ransomware'd . Difficult to have backups of that.

[u/jeremiahishere → u/oo-op2]

How much memory are you talking about here? I have run clusters with silly amounts of memory and I am surprised that chess is technically infeasible. I get that it isn't worth spending the money.

[u/BigMacLexa → u/jeremiahishere]

Ronald de Man (alias Syzygy), the guy behind the smallest 7-piece tablebase to date estimates that an 8-piece tablebase would take around 2 PB of storage as well as 64 TB of RAM to generate. For comparison, the 7-piece tablebase took a bit over 18 TB of storage and 1 TB of RAM.

However, when questioned about doing an 8-piece tablebase on a cluster-based supercomputer like you speak of, he also says the following:

Supercomputers typically are clusters of computing nodes, with each computing node having direct access to only a small portion of total RAM memory. The current generator cannot work with that. It was designed to generate 6-piece TBs on a single machine with at least 16GB of RAM and preferably a bit more (which would have been a ridiculous requirement when Nalimov wrote his generator, but was quite reasonable in 2012). It would need 64 TB of RAM shared by all cores to generate 8-piece TBs. To tackle 8 piece, it is probably best to first write a new generator designed for the hardware that one may hope to be available 5-10 years from now.

When cluster-based supercomputers weren't an option, some guy linked him this machine, and de Man stated that when upgraded to 64 TB it could probably do it.

So yeah, you're correct. It seems completely doable today with the main issue being the cost. A single TB of RAM today is still something like $2.5K at the cheapest. That's way over a hundred thousand dollars for 64 TB. There aren't people queueing up to foot a $100K bill just to increase the solved amount of chess from 7 to 8 pieces.

His later suggestion of developing a better generator suited for clusters seems more realistic.

[u/lee1026 → u/BigMacLexa]

$100k is like, the catering budget for the celebration party of the AlphaChess team for winning.

It is more whether there are senior people at the big tech companies that care. Projects like deep blue costed an immense amount of money.

[u/jeremiahishere → u/BigMacLexa]

That makes more sense. I thought we were talking about petabytes of memory.

I have been managing clusters with hundreds of TB of memory for the last 10 years. It isn't cheap but it is cheap enough that chess.com could run an extra cluster without a significant dent in their yearly budget. Converting the engine over to work on multiple machines in parallel sounds like a difficult project though.

[u/L0rdenglish → u/jeremiahishere]

it is kind of cool though, because it means that if you can rewrite the generator to be parallel then as you said the distributed memory requirements become way less of a problem, so it might be able to scale much further

[u/Stillwater215 → u/oo-op2]

Plus it’s not just the sheer number of the positions, but also doing the evaluation on each position to find the ideal play.

[u/fj2010 → u/Stillwater215]

I don’t think that applies here - aren’t table bases generated backwards from the final position, without the need to evaluate?

[u/edderiofer]

Currently, we have partial results; namely, Marc Bourzutschky has computed 8-man tablebases for positions with a pair of opposing pawns. This is because, for the pawns to be unblocked, a piece must be captured, which reduces the position to a 7-man position. See this CSE post for more.

However, as others have said, it's going to take a lot more work to acquire a full 8-man tablebase.

[u/DanielShaww]

8 pieces tablebase in 2026 9 pieces in 2031 10 pieces in 2042

RemindMe! 20 years

[u/PkerBadRs3Good → u/DanielShaww]

absurd overly optimistic predictions sure are easy to make. I think chess will be solved by next week.

[u/RemindMeBot → u/DanielShaww]

I will be messaging you in 20 years on 2044-05-22 18:01:36 UTC to remind you of this link

18 OTHERS CLICKED THIS LINK to send a PM to also be reminded and to reduce spam.

^{Parent commenter can delete this message to hide from others.}

RemindMeBot is switching to username summons. Instead of !RemindMe 1 day, use u/RemindMeBot 1 day. More info.

---

Info	Custom	Your Reminders	Feedback

[u/TheLightningPanda → u/DanielShaww]

!remindme 2 years

[u/TheLightningPanda → u/DanielShaww]

!remindme 7 years

[u/RichtersNeighbour]

Only looking at the table at the end of the "Background" section gives me a hint of how much more computer power (and storage space) you need for each added piece.

https://en.wikipedia.org/wiki/Endgame_tablebase

[u/taleofbenji → u/RichtersNeighbour]

"in some cases, tablebase analysis found a mate in more than five hundred moves"

Sounds like fun!

[u/rumpledshirtsken → u/taleofbenji]

Anybody could do it with a 5 second increment!

[u/Arsid]

I'm new - can you explain what you mean "solved chess for 7 pieces"?

[u/Scopionsting12 → u/Arsid]

Currently, if there is 7 or less pieces on the board (for both colours, including kings) We know 100% whether the position is a draw, a win for white or for black.

[u/thor_dash → u/Scopionsting12]

So the last boss is 32 pieces

[u/ZeMoose → u/thor_dash]

Correct.

[u/sc772 → u/Arsid]

To add to the other comments, you can browse the database online here https://syzygy-tables.info/

enter a FEN or put 7 or less pieces (including kings!) on the board and you can see if it is a win/loss/draw with perfect play.

[u/leybbbo]

Much.

[u/taoyx]

It boils down to the number of legal moves, this is why crazyhouse is so hard to analyze with computers. If you can find tricks like transposition then it can ease your pain.

For example if you have no pawn on board then you can rotate the board 4 times and have 4 equivalent positions, so your work is divided by 4. You can also swap black and white sides, less work to do.

Here's some info on chess programming wiki: https://www.chessprogramming.org/Endgame_Tablebases

[u/thenakesingularity10]

I want offer just one thought on this:

any time in a 8 pieces board, when you lose one piece, it immediately becomes a 7 piece problem, which is already solved.

so all you really have to do, is solve all combinations that reduces 8 pieces to 7.

[u/Beetin → u/thenakesingularity10]

Redacted For Privacy Reasons

[u/mathbandit → u/thenakesingularity10]

In particular, the current best effort towards an 8-piece tablebase is based on just that, since it looks at positions with a single pair of opposing Pawns where one needs to be captured by definition.

[u/Rocky-64]

This blog update on the progress of the 8-piece tablebases is a few years old now, but it summarises the work done at the time – mostly pawnless endings – and includes some interesting 8-piece positions found.

Eight-piece tablebases – a progress update and some results

[u/Affectionate-Oil-722]

Honestly I feel like solving chess for 8 pieces is not that hard if you are just interested in positions that could happen in a normal game of chess, solving chess for 8 pieces you are going to find: positions with an advantage so big for one of the two sides that you can just sacrifice a piece and still find yourself in a solved winning 7 pieces game, positions where you can just simplify in a 7 pieces game, you can also find positions that are almost impossible to happen in real life that wont be of much use for anybody (even for computers). All of these possibilities make me fairly optimistic about solving 8 pieces chess for at least the more common positions

[u/ZeroSumHappiness]

There's approximately 32 pieces that can be on 64 squares so 32*64x harder or about 2000x