Is a game like chess solvable ?

[loseyourname]

Why does this thread have no posts in it?

 

[octelcogopod]

Heh. Weird.

 

[Greg825]

Dont know. My intended post was:

What I mean by solvable would entail some method of determining all possible outcomes from a single board configuration (most likely with computers). Theoretically this would result in only one possible outcome from the beginning of the game (white wins, loses, or a draw) if both players play optimally (like tic-tac-toe), which is why I'd call it "solved". Most estimates I've seen place the total number of chess board configurations well above the total number of atoms in the universe by many orders of magnitude(10^120 for chess vs 10^75 for atoms), but does that mean that the game can't be solved? If you think it will be solvable when do you think it will happen?

 

[chroot]

Yes, chess is theoretically solvable.

This is, in fact, one of the most naive approaches to developing a chess computer. You simply create a database of every possible board configuration, and compute the move to make in each configuration. Standard metrics can be used to compute the best move given each position. You end up with an enormous database which is the "solution" to chess, since you will have considered every possible move for every possible configuration, and determined the best for each.

The problem with this approach is that number of configurations, as you mentioned, is enormous. The problem is that computers have nowhere near enough memory to store such a database. The "solution" is simply too bulky to store in its entirety.

You can greatly reduce the size of the database with the realization that you really don't need to precompute and store ALL board configurations, only those that require lengthy computation. Most configurations have a single, obvious best move which can be quickly calculated through heuristics.

A good heuristic algorithm (to calculate the easy moves on the fly) coupled with a large precomputed database of configurations (to lookup the hard ones) would comprise an essentially perfect chess player. This hybrid approach is probably already within the grasp of modern supercomputers, and will likely eventually be able to fit in the palm of your hand.

- Warren

 

[Greg825]

I suppose it's possible that a heuristic algorithm/database hybrid might constitute a solution to chess as thorough as a complete database, I mean to the point where the game result (white ALWAYS wins/loses/draws) can be known before the game begins, but I see no reason to be sure. I'm not an expert on the subject but I doubt that "most" situations have an obvious best choice move when the immidiate goal from the onset is an unavoidable checkmate, or if that's not possible, a draw (material advantage, a piece's position, and things like center control are not directly relavent). It's possible (though highly unlikely) that white's "best" first move is moving the A column pawn up one square, because this may somehow be the only move that avoids his demise 30 turns and countless permutations later, yet it is definitely not considered a "good" first move by any current standards.

A complete database might not be necesary if one particular player can be shown to achieve any of several board configurations that lead to a check sequence resulting in a final unavoidable checkmate, but this might not be possible.

I find it interesting that the game itself may be "solvable", it almost makes playing chess to win seem as pointless as tictactoe to me. If a solution is currently achievable by super computers as you speculate might be the case I would be curious to know the outcome between two "perfect" players. I'm also curious as to why the solution hasn't already been found or published (maybe it's just not as interesting to other people as it is to me, or not worth a supercomputer's time).

 

[selfAdjoint]

I don't think the OP meant solvable through brute-force enumeration. For example checkers has a decision rule expressible in a sentence or two. Indeed one can ask questions like is chess NP-complete? For example could you show that solving chess would involve solving the traveling salesman problem (which given their definitions, doesn't seem intuitively outrageous to me)?

 

[Rach3]

I don't think the OP meant solvable through brute-force enumeration. For example checkers has a decision rule expressible in a sentence or two. Indeed one can ask questions like is chess NP-complete? For example could you show that solving chess would involve solving the traveling salesman problem (which given their definitions, doesn't seem intuitively outrageous to me)?

That doesn't make sense - chess doesn't scale on the size of an input. There's no meaning to the "computational complexity of chess" - it's simply O(1).

 

[pallidin]

Chess provides for the aspect of "selective-suicide" during a thrust towards an achieved objective. That type of involvement renders computer computation very, very dificult.

 

[Rach3]

Chess provides for the aspect of "selective-suicide" during a thrust towards an achieved objective. That type of involvement renders computer computation very, very dificult.

What do you mean?

 

[Hurkyl]

I think he's talking about sacrifices. E.G. sacrificing a pawn to obtain a positional advantage in the center, in the hopes that down the road you can turn that into a material gain.

Or, sacrificing a bishop to expose the enemy king, in hopes that you can force through a mate (or at least capture some big material) before the enemy can defend himself.

Of course, I'm told that the latter kind of sacrifice tends to be extremely risky against the better computers, since they tend to be very slippery.

I don't know why he brought this up, though.

 

[Renge Ishyo]

From my understanding, what has limited chess programs to this point is their inability to think in the abstract. Even if you decided what is statistically the "best" move in every given situation there are other moves you can make that gain long term advantages that can be exploited. Someone already mentioned sacrifices to control the center. Other things you can do are seemingly poor trades that open up an area of the opponents line that make it difficult for them to defend and then pressing the hole...tying up pieces defending it which gives you openings for a different front elsewhere on the board, etc. This is why (well...until Deep Blue came along) super computers have been largely unable to beat the pro players at chess. They may have an advantage in processor power, but they lack the flexibility...or something of the human mind to improvise and plan for the endgame.

 

[Hurkyl]

Even if you decided what is statistically the "best" move in every given situation there are other moves you can make that gain long term advantages that can be exploited.

If there are other moves that you can make that gain long term advantages that can be exploited, then it's not statistically the "best" move, now, is it?

Someone already mentioned sacrifices to control the center.

Computers can do that, by the way. The scoring systems computers use account for a lot more than just material value. For example, see http://www.frayn.net/beowulf/theory.html.

 

[chroot]

If you presented all the members of the grandmaster community with an entire chessboard in some specific state, would they generally all be in agreement about which move to make next?

- Warren

 

[-Job-]

That doesn't make sense - chess doesn't scale on the size of an input. There's no meaning to the "computational complexity of chess" - it's simply O(1).

I don't agree. In this case the input to the problem is the algorithm(s) that each player is using. The problem of determining which player wins, black or white, is solvable in a deterministic manner (assuming that no player is running a randomized algorithm) and its complexity is dependent on the size of the algorithms.

To simplify, suppose each player runs the same deterministic algorithm. The problem of determining who will win is solvable, and its complexity is f(n), where n is the number of bits used to represent the algorithm in some predefined architecture.

 

[Renge Ishyo]

If there are other moves that you can make that gain long term advantages that can be exploited, then it's not statistically the "best" move, now, is it?

The "best" move is simply the one that when compared to other possible moves yields the highest stastical probability of leading to a sequence that will win the game. This is largely how computers on "master" levels pick their moves today from how I understand it, they run through all the different possible pathways from a move to the end and choose the one that has the highest probability of leading to a win. The problem is that the computer "re-evaluates" the entire situation after every move. It cannot say to itself, "making this move puts me in a disadvantage in this way, but I want to get rid of both his knights early on anyways so that I can build my pawn line freely without worrying about them jumping it." That sort of thing. If the computer ran through the scenarios it would generally pick the "best" move to make in any given situation, and that is both it's strength and it's weakness. It wins on percentages, it loses to creativity.

 

[Hurkyl]

I don't agree. In this case the input to the problem is the algorithm(s) that each player is using.

No it's not -- they were talking about perfect play. It takes O(1) time to, given a board position, return one of the following:

(1) A move from which a perfect player can guarantee a win.
(2) A proof that a perfect opponent will win no matter what you do.
(3) A move that will guarantee at least a tie, and a proof that a perfect opponent can avoid losing.

The problem of determining which player wins, black or white, is solvable in a deterministic manner (assuming that no player is running a randomized algorithm) and its complexity is dependent on the size of the algorithms.

No it's not -- the size of an algorithm has little bearing on how long the algorithm will run.

The "best" move is simply the one that when compared to other possible moves yields the highest stastical probability of leading to a sequence that will win the game.

A computer can't compute that (yet). They simply compute something they hope is a decent approximation.

The problem is that the computer "re-evaluates" the entire situation after every move.

No it doesn't. A decent chess program will remember all of the relevant analysis it did from the previous turns, and continue analysis from that point.


But I think you meant the idea of choosing a plan and sticking with it. You have to remember that advice is meant for weaker players (and this is essentially true for any game, and even real life). A common problem is that the beginner might come up with a new idea in the middle of a game, and try it out even though it doesn't work in the current board position. By sticking to a plan, it makes it more likely that you will take advantage of the current situation.

But the expert has the experience to realize which ideas won't work from the current situation, and the expertise to fully exploit the current position when switching over to a new plan. For the expert, choosing a plan and sticking to it will degrade his game.

It cannot say to itself, "making this move puts me in a disadvantage in this way, but I want to get rid of both his knights early on anyways so that I can build my pawn line freely without worrying about them jumping it."

Why not? It's easy enough to implement a heuristic that rewards having a good pawn line when the opponent doesn't have any knights.

It wins on percentages, it loses to creativity.

Creativity is usually a bad thing. In fact, computers are well-known for punishing "creative" play.

But if you meant to talk about strategic play, then yes, humans are currently better than computers in the strategic domain for chess.

That isn't necessarily because computers are incapable of strategic play -- it's just that computers were quickly seen to excel at tactics, and most of the research was spent improving tactical play, and discovering how to include more interesting factors into its evaluation methods.

A computer, for example, will happily discover and execute an 8-move combination that sacrifices a pawn for what it believes is a greater compensation in terms of board position.

 

[-Job-]

No it's not -- they were talking about perfect play.

Are you sure? Rach3 said that chess doesn't scale on the size of an input in reply to selfAdjoint's idea of asking whether "chess is NP-Complete", while the OP put forward that:

Theoretically this would result in only one possible outcome from the beginning of the game (white wins, loses, or a draw) if both players play optimally (like tic-tac-toe), which is why I'd call it "solved".

... by which the "chess" problem, being solved in determining "who wins", is the problem of determining which player will win. So i don't see where you're coming from, but whatever, rather than get into a quote cycle, i'd rather argue the following:
Is it possible that no one will win?
Say the two kings end up by themselves, running from each other?
That seems possible, and it leads to an interesting thought.
For example, assume here that this "chess problem" is the problem of, given two algorithms and which goes first, determining who will win.
So our algorithm for solving the "chess problem", takes in two algorithms, and tries to determine who will win.
I think this is equivalent to the Halting problem, because, suppose we build an algorithm which is the sum of the player's algorithms (meaning an algorithm where algorithm A goes, then algorithm B goes, then A again, etc). Then the problem becomes that of asking whether this compound algorithm will end with A (A wins) or B (B wins) or whether they tie (the algorithm doesn't Halt).
It sounds like the halting problem (since we can build any algorithm from two algorithms), and means that no single algorithm can ever determine, for any two possible players, who will win.
Now that is interesting. Does that go against what you were saying Hurkyl?

 

[Canute]

That was my thought as well. Chess is sometimes used as an example of a formal axiomatic system, and it seems to me a stalemate equates to an undecidable theorem. Don't know if this analogy really holds up though.

 

[Curious3141]

If you presented all the members of the grandmaster community with an entire chessboard in some specific state, would they generally all be in agreement about which move to make next?

- Warren

Even if they are all in agreement on the move they perceive to be the best, they may not actually be right! It doesn't even have to be a complex midgame position, I remember a chess book with the example of an endgame with a paucity of remaining pieces. It was supposedly an "exhaustively analysed" position (by humans, of course, this was in the older days before computers were used extensively). The master writing the book had posed the problem to one of his novice students and asked him to find the best continuation for one side (to win the game and avoid stalemate). The novice came back after a day's deliberation asking what was "wrong" with Re8 (or some such move).

The master goes on to say, "As I was preparing some instructive rebuke, I suddenly realized I had none. The move was actually better than the accepted "best continuation"".

A non-intuitive solution found by a novice in a relatively simple position turned out to be better (mate in fewer moves) than the accepted wisdom of the grandmasters who came before.

Just for fun, I set my (lousy) Kasparov 2000 Chess computer this problem and asked it to continue. While that computer was very weak, it did have the strength of being able to continue computations indefinitely until the battery ran out.

When I stopped its cogitations quickly, it moved weakly. A little more "thinking time" and it replied with the accepted "best" variation. But it was only after I had let it analyse the position overnight that it managed to find the ideal continuation the novice had been able to find.

I use this instance as a reminder of how rich the game of chess really is. The move really is very counterintuitive, most players would've chosen to attack the opposing king immediately with the rook, but this contination seems to be neither here nor there at the outset, yet actually attained the goal of a victory more efficiently.

Which is why I disagree that using heuristics in a "complete solution" to the game is acceptable. Heuristics can be wrong, and one misstep in the tree of the perfect game will lead to a ruined analysis. Brute forcing every step of the way is the only sure way to solve the game completely, and we're nowhere near being able to do so computationally.

 

[ecolitan]

Chess is a boring program for computers, if you want a real challenge try to make a computer play GO.

 

[selfAdjoint]

Chess is a boring program for computers, if you want a real challenge try to make a computer play GO.

Ah, ecolitan, have you actually written
a) A program that beats "street masters" at chess?
b) A program that even plays go correctly?

Ordinarily I wouldn't ask such an impertinent question, but your statement that chess is a "boring" program kind of raised my hackles.

 

[raven1]

http://en.wikipedia.org/wiki/Chinook_(draughts_player)
this is related
Chinook is an attempt to solce checkers, and is most likly closer then any attwmp at chess

 

[Delzac]

hmm... say we have a quantum computer with us. What we happen if we try to solve a whole game of chess, using brute force, starting from the beginning move number one. Is it possible to achieve :

1) white will surely win.
2) black will surely win.
3) The game will surely be a draw.

We shall assume that we have a lot of time to let the computyer run.
The computer ran through every possible move in the game.(10^120 for chess?)
The computer has limitless memory space.

Given all these conditions can the quantum computer also solve GO(weiqi), i find i very hard to imagine it being able to solve GO.(i dun think it is able to do that, maybe Chess but not GO)

 

[kant]

A badly formulated question that merit zero thought. I would pressume any possible meaning of that question would be obvious.

 

[ile]

Yes, chess is theoretically solvable.

This is, in fact, one of the most naive approaches to developing a chess computer. You simply create a database of every possible board configuration, and compute the move to make in each configuration. Standard metrics can be used to compute the best move given each position. You end up with an enormous database which is the "solution" to chess, since you will have considered every possible move for every possible configuration, and determined the best for each.

If there was such a database, and the best possible chess program used that to play against the best possible human player, could the computer ever lose (even if it used white pieces)?

 

[Jimmy Snyder]

But if you meant to talk about strategic play, then yes, humans are currently better than computers in the strategic domain for chess.

This is not the case. Here's from wiki:

After convincing victories in two matches in 2005 and 2006, it appears that chess programs can now defeat even the strongest chess players.

http://en.wikipedia.org/wiki/Human-computer_chess_matchesHuman-computer chess matches
It appears that in order to give humans a winning chance, the computer has to give odds (an opening advantage) to its opponent. This is also from the wiki article (Rybka is the name of a chess playing program):

Since 2007 Rybka has played some odds matches against grandmasters. Jan Ehlvest first lost a pawn-odds match, then later lost a match when given time, color, opening, and endgame advantages.[citation needed] Roman Dzindzichashvili then drew a match when given pawn and move odds.[citation needed]

In September 2008, Rybka played an odds match against Vadim Milov, its strongest opponent yet in an odds match. (Milov at the time had an Elo rating of 2705, 28th in the world). The result was a narrow victory to Milov: He had won 1½-½ when given pawn-and-move, and 2½-1½ (1 win, 3 draws) when given exchange odds but playing black. In two standard games (Milov had white, no odds), Rybka won 1½-½.

 

[Hurkyl]

This is not the case.

I didn't say "humans are better than computers" -- I said "humans are better than computers at strategic play". Conversely, computers are better at tactical play.

See this link; it describes something I was saying earlier.

 

[Jimmy Snyder]

I don't think the game is solvable in any practical sense. It's not a storage issue. Those $10^{125}$ positions all need to be evaluated. In tournament play some branches can be pruned once they reach a 'hopeless' position. However, since the point of this exercise is to determine the difference between a position that it truly hopeless and one that is merely probably so, they can't.

 

[Jimmy Snyder]

See this link; it describes something I was saying earlier.

This article is almost, but not quite relevant to your point. It would be relevant if the human-computer team (computer for tactics, human for strategy) consistently beat pure (strategy deficient) computer. However, that is not what the article is about.

 

[fluidistic]

Well some people are working on to solve chess entirely and they know they won't be alive when the work they have started will end if it does so one day. Nowadays we entirely solved chess when only 7 (if I'm not wrong!) pieces are remaining on the board. Search for Nalimov tablebases on the internet. For those who are interested in an easy consultable endgame tablebase (up to 6 pieces remaining), check out http://www.shredderchess.com/online-chess/online-databases/endgame-database.html.
I personally think the game will end in a draw whether 1.e4 or 1.d4 is played. And probably also 1.Nf3, etc... Did you know that the 8x8 checker game has been solved recently? Chess is much more complicated and will probably take more than 100 years from now.

 

[Dmitry67]

Can quantum computers analyze all the combinations?

 

[Pythagorean]

here's my thread on this subject:
https://www.physicsforums.com/showthread.php?t=274471

and here's a site where you can play people online (minimum 3 days a move) and they keep a database of all the different games that have been played:
http://www.gameknot.com