5 ms·
> Chess, in theory, with absolutely perfect play, is a draw. While this is highly likely and essentially agreed upon by all experts on the matter, it's not pro
by fouronnes3 4y ago
> Chess, in theory, with absolutely perfect play, is a draw.
While this is highly likely and essentially agreed upon by all experts on the matter, it's not proven yet.
- nhumrich 4y agoChess is still no-hard, so "proving this" will be near impossible. The closest we have is statistics. I remember watching a "bot battle." A chess tournament for bots only, algorithms playing eachother. Nearly 70% of these games ended in draw.
- adrianN 4y agoChess on an infinite board is asymptotically difficult in the worst case. Chess on an 8x8 board can be solved in constant time.
- scaredginger 4y agoI invite you to sit down and solve it then
- simiones 4y agoA hundred billion years is still constant time. That doesn't mean it's doable.
- sweezyjeezy 4y agoNot sure if this was sarcasm, but that's like saying NP-hardness is no big deal because we only care about finite problems.
- dskloet 4y agoChess on an 8x8 board is not NP-hard. That doesn't mean it's easy but invoking NP-hardness is kind of meaningless.
- bawolff 4y agoLike parent was saying - that is true of all problems in practise since the earth has finite resources. That doesn't make complexity classes a useless concept. In other news, no point in needing pi, because perfect circles dont actually exist in the real world.
- pessimizer 4y agoI don't think people are trying to claim it's unimportant in general, to anyone, they're suggesting that it's completely unimportant in this conversation about how slow and boring championship chess matches are.
- sweezyjeezy 4y agoYes and saying a problem is finite is also kind of meaningless. That narrows it down to everything except infinity. I also did not say that chess is NP-hard, it was an analogy.
- deleted 4y ago[deleted]
- adrianN 4y agoNP-hardness is indeed often not a big deal in practice because NP-hardness is a statement about asymptotic worst case complexity. In practice you have some finite size problems that are often of average difficulty, not of worst case difficulty. For example, we solve instances of SAT every day, some of them quite large. Even humans are able to solve many Sudoku puzzles, even though Sudoku is NP-hard. If you hang with the right crowds (for example people into software correctness), PSPACE completeness is easy and you even solve undecidable problems every day.
- throwaway09223 4y agoI solve the TSP every time I run errands.
- sabageti 4y agoHow Sudoku is NP-Hard?
- CJefferson 4y agoIf you generalise sudoku to a board with sides length, with subsquares with sides length n, then sudoku is no complete.
- jstanley 4y agoThe reason chess is hard to solve is not because it's NP-hard (which it is not, being a constant-sized problem), it's because chess is a big problem. It can simultaneously be true both that NP-hardness matters, and that constant-sized problems can be hard.
- sweezyjeezy 4y agoI never said chess was NP hard, it was an analogy. The equivalent would be some kind of chess on an NxN or Nx8 board I guess, I don't know how hard would be.
- piva00 4y agoWhy hasn't it been done then?
- adrianN 4y agoWe haven't build enough Dyson spheres to power a computer of the right size yet.
- bluGill 4y agoThere are more states to calculate than atoms in the universe so it isn't possible to brute force the problem. Maybe it can be solved, but it will require math.
- sgjohnson 4y agoTo be fair, on this scale, “the total number of atoms in observable universe” is quite a small number. Even 52! comes pretty close to it, and that’s just one deck of cards. Saying there are merely “more” states is almost insulting to the depth of a chess game :)
- noSyncCloud 4y agohttps://tcec-chess.com/ https://tcec-chess.com/ 70% draws is a very small number, really. Not conclusive at all.
- EvgeniyZh 4y agoTCEC is forced to choose very imbalanced openings to make sure there are some non-drawn games. From starting position it'd be 100 draws out of 100 (also all very similar o each other)
- aaron695 4y ago> While this is highly likely and essentially agreed upon by all experts on the matter Can you cite this? I can't see anything on this. It's not something a chess champion would know on their own for instance. Basically you have to get a good understanding that the advantage of being white can't be leveraged enough to win. Obviously it can't be proved, but to even get an idea will be very mathematical or computational.
- Someone 4y agoI think no expert will claim it’s a win for either player, but I don’t think all experts agree it’s a draw. There will be some that don’t claim to know either way. (If they had to bet, I think all experts would bet on “it’s a draw”, but some experts won’t be wanting to bet, even if they think that’s almost certain)
- asdajksah2123 4y agoI don't see why anyone would agree to that. In fact, I can see it being far more likely that chess experts believe it ends in a win for white considering that today white is favored, to the point where if offered a quick draw, black will almost certainly take it (unless they need a win to move up a rank in a tournament, etc).
- sgjohnson 4y agoThis is flat out false. Virtually all of the experts agree on this, and in top engine and human play the percentage of games drawn is increasing, not decreasing. AlphaZero on autoplay @ 1 minute per move draws 98% of the games. > if offered a quick draw, black will almost certainly take it [citation needed], and 1200 elo games on lichess aren’t a valid citation
- ChrisLomont 4y ago>AlphaZero on autoplay While Alpha Zero is good, this is not very good proof. Alpha Zero is not perfect, so if there are tiny ways to win that Alpha Zero misses, it will miss it on both sides (being the same engine), so would never explore that path. It's like claiming inbreeding will result in perfection :)