Well, yes, but we can say that tablebases are the way to play perfect chess (without having to think about or analyses a move!).
We know we are only up to 6 piece positions and that it will take a very long time to reach 32 pieces, even with computer speeds increasing.
Again, yes, but that’s why I chose that game as an example!
Sorry, a bit too sloppy there. (I actually changed my mind after pressing post, and didn’t know the reply was posted as the page hadn’t started to load yet) You said “There are various senses of a game being “solved”; the weakest would probably be that a computer can avoid losing if it gets to choose which player to be. For any two-player turn-based game of perfect information with win, lose, draw outcomes, such a program exists, though not necessarily efficiently.”, but it should be noted that it doesn’t apply to Go. Supposedly, computers can currently only challenge beginners in Go, and so can’t be expected to avoid loss against any player, even if it gets to chose sides. And of course, since the algorithms for forcing wins on large hex boards aren’t known and draws are impossible, a computer can’t force non-loss there either, even if it gets to start. Anyway, it’s a minor, and quite irrelevant, point.
Sure, and I suppose one could use an approach like this to put an upper bound on the amount of computing power it will take to solve chess.
It would be cool if the optimal line of play contained a few bizarro moves. (1. h4 ?) But I doubt there will be any big surprises.
And it’s why I chose that game too 
But the point was such a program exists in theory. You’re just pointing out that no such program exists in fact. But that’s true of Chess as well, so it’s not saying much.
-FrL-
Yeah, what Frylock said. Put as much emphasis on my “though not necessarily efficiently” as you feel necessary, but brute-force exhaustive search always exists (for games of complete information which cannot run on infinitely), and using that, one can always avoid loss if one gets to choose which player to be (for two-player win/lose/draw games of this sort). So, yeah, I could write the program to play perfect Go right now (hell, I could just take a generic perfect play program for games of this category, and slap on a module specifying the game tree of Go); it would just take a ridiculously large amount of time, at currently normal computing speeds, to make its moves and even to choose which side to be. Longer than the entire history of the universe, perhaps, but theoretically still perfectly unbeatable, and I’m willing to hit that “though not necessarily efficiently” hard.
Well, if I want to be ultra-pedantic, I should also say that, for exhaustive brute-force search, there should only be finitely many options available to a player at a time (so that, in combination with its game tree lacking infinite branches, we get that the game tree must be finite). A game like “The first player writes a computer program; the second player guesses whether it halts. If the second player is right, he wins, otherwise the first player wins”, though clearly one where the second player can force a win, is not one which any computer program can play perfectly.
Speaking of which, more intriguingly, though this is really veering away from the chess-meat of this thread into more esoteric land (though I think it’s interesting anyway), we can consider variations on that game. For example: Players take turns writing computer programs, character by character, of the sort that can return booleans. Once a player finishes writing a program, the other player must tag that program with either ‘This program will not return True’ or ‘This program will not return False’; after that, the players go back to their writing (the one starting a new program, of course), but with simulation of the written program proceeding in the background. Specifically, on each player’s turn, all of his programs advance by one step. If, at any time, a program finally returns a value and it turns out that the tag on it was incorrect, then the player who placed that tag loses.
This is a game which can be very easily refereed (in the sense that it’s easy to tell who wins and when; you don’t need any magic knowledge of which programs halt or anything), but all the same, every computer program playing it is beatable, even when it is given the choice of whether to go first or second. It happens to be a two-player complete information win/lose finitely-branching game and all that goodness; the catch is that it is capable of running on infinitely (which is, of course, what happens with perfect play, where no one ever puts down an incorrect tag). But despite that, every computer program playing it can be beaten in a finite number of turns (easily, too, if you know the source of the program you’re up against); though the method of perfect play is easy to state (never put down an incorrect tag), no program can be written which achieves it.
On the subject of whether Black might be able to force a win in chess: It is, in fact, an excellent theory that black has the disadvantage in chess. I mean that in the technical sense of the word “theory”, the same as for the theory of evolution, or the theory of universal gravitation. But there is actually one tier of certainty which lies above a theory, that being a theorem, something which is mathematically proven without a doubt. For most questions of science, that highest tier of certainty is simply unattainable, and so a theory is the best we can do. However, for the question of whether Black can force a win, a theorem is, in principle, attainable, though it would probably be very difficult.
Yes indeed.
Tablebases are perfect, require no thought at all to use and allow cheating v human players. Sad really, considering the work that went into them. :o
I can’t prove it, but all my experience is that 1. h4 weakens White’s position so that Black is already at least equal. (For starters, White won’t want to castle K-side…)
I have faced the move once, in a British Championship qualifier, and won in 20 moves. 
Looking at tablebases can help a human work out a strategy e.g. in K,Q+p v K+Q endings.
However long series of moves (K + 2B v K + N) are desperately hard to understand and of course a tablebase cannot explain anything to us. :smack:
This is true, but of course a chess tablebase of 32 pieces plays perfectly without calculating and takes no time at all to move (although it takes a vast amount of time to create!).
Oh, yeah, I didn’t even think of it that way. Good point!
(Of course, it also takes a vast amount of space to store. Which, beyond a certain level, does somewhat imply a vast amount of time to access (when the size of the indices starts being larger than the word size of the machine, for example). But that’s something normal to gloss over.)
Probably not true, on the last part. Retrieving things from memory takes time, and we’re talking about an unfathomably huge chunk of memory, here.
Of course, data compression would help. Despite the ludicrous size of that database, it could be compressed down to only a few kilobytes. In fact, the compressed file could be constructed without need of even knowing the uncompressed table. But then, of course, the problem becomes a matter of the ludicrously long time it takes to decompress the data.
Indeed, I have a 0 byte version sitting around somewhere that I keep meaning to start decompressing one day.
That’s an interesting point.
However once you type in a starting position, the tablebase (here’s one for 6 pieces to practice on) announces for example in this position:
White King g5, Queen e5, pawn g4
Black: King b7, Queen c4
Kg5-h5 win in 45
It then gives the best Black move as:
Qc4-f7+ win in 44
The game analysis seems to continue instantly - once the tablebase has found the initial position, doesn’t it (becasue of the way the database was compiled)have links to every legal move thereafter to a won position?
Wouldn’t that speed the process up enormously?
The problem would be that as the tablebase explodes in size, the time to index any entry in it grows as well; you lose “random access”. Disk platters have to spin, tape has to spool, bits have to shuffle through limited width busses. Imagine somebody gave you the full database for perfect chess play in the form of a book, hajillions of pages long. Your opponent opens, you look up his move on page 1. It gives you a response and tells you to now flip to some page off in the middle of the book to be ready for the next turn. Considering the size of the book, that’s gonna take you some time to get to. Even the very name of the page takes you a long time to say! Things that seem almost instantaneous when the whole table fits on a few pages aren’t so instantaneous anymore.
Now consider that, for a book big enough to hold the full chess tablebase, you might have to fly out to Alpha Centauri and back to find the right page.
Expansion of previous statement: Other posters have stated that chess has a complexity of 10[sup]123[/sup]. I assume that that number reflects the number of possible states of the board. For each of those states, the lookup table has to encode the proper move to make. If, on average, there are about 30 moves available in any given position, that means that we would need about five bits to efficiently encode a move. So we need a total of 510[sup]123[/sup] bits to store our book. If we can store one bit per atom (more than which would surely require a quantum computer, in which case, why are we bothering with this monstrosity?), then we need that many atoms. If we arrange all of those atoms in a cube, that cube would be 1.710[sup]41[/sup] atoms on a side. At about 1 Angstrom per atom, that works out to a cube 1.8*10[sup]15[/sup] lightyears on a side. So you’d be incredibly lucky if you only had to fly out as far as Alpha Cen to find your page.
Though it may be the case that, with a suitable strategy, you can prevent many of those states from ever happening, thus reducing the size of the table (if all you want to do is play perfect chess from start to finish, rather than, say, allow the ability to take over playing perfect chess after someone else has already made some moves on his own). Still, every indication is that the thing is going to be huge no matter what.
Oh, also, I know it was just a throwaway comment, but there’s no real indication that a quantum computer would be any faster at brute-force chess play or any such thing. People often assume that any massively parallel computation can be easily sped up through quantum computation, but there’s no known general method for doing so. (There are actually very few problems for which we have know better quantum algorithms than classical algorithms; to my knowledge, just “search” and factorization/discrete logarithm. In the former case, a speed-up from provably optimal classical linear time to provably optimal quantum square-root-time. In the latter case, polytime quantum algorithms exist but no one’s ever proved one way or another whether polytime classical algorithms exist, even though everyone thinks they don’t.)
Sure, we currently have a weak enough understanding of quantum computers that anything we want to do, we need to construct a completely new algorithm from scratch, and chess would require a complicated enough algorithm that it’s not very high on anyone’s to-do list. But it sure seems like the sort of problem which ought to be amenable to quantum computing. Basically, if you have some quantum procedure for making a move given a board state, then make a move which is a superposition of all legal moves, then make the next state a superposition of all legal moves from there, and so on. Which, of course, leaves out a bunch of important details, without which I won’t claim to have a quantum chess algorithm, or even claim any more strongly than “a hunch” that it’s possible.