Solving Chess

[Folly]

Chess is solvable in theory, even if we lack the computing power to do it. The comments earlier in the thread about how we'll never be able to do it remind me of those famous comments from the middle of the last century about the limitations of computing power. Like some of these.

But chess is solvable, which really makes it just a really complicated version of checkers, which really is in turn just a really complicated version of tic tac toe. Which is why backgammon is the better game.

Who said it wasn't? Every two player zero-sum perfect information game of finite length is solvable in the same way tic-tac-toe is. This includes Go, and also backgammon, where the chance events are all public information. Perhaps you were thinking of multi-player poker?

So, yes, chess is solvable. But... that wasn't the original questions. From the OP

'm curious to know if anyone is anywhere close to solving chess, like they did with checkers not too long ago. Wikipedia doens't have too much info on it. Is it even possible to solve chess using today's technology?

It is very, very, very unlikely that it is possible to solve chess with today's technology. The simple fact remains that a proof will involve at least a million times as many positions as the checkers proof considered, and there's no reason to suspect that the decision complexity of chess is significantly less than checkers, Processors haven't increased in speed by a million times in the last couple of years (and the checkers proof was largely bottlenecked by disk access speed in any case, which hasn't been decreasing very quickly at all.) and it's not really possible to get an exabyte of disk per CPU in a cluster. You can try to skew the usage of CPU or storage to reduce one requirement, but it just increases the other.

In 40 years, maybe hardware will have caught up to this factor of a million, and someone will think it's worth trying. However, unless mature high performance quantum computers becomes a reality before then, and there aren't any gotchas that rule out the currently theoretical algorithms, it'll be worse than just that factor of a million, and it's probably at least 100 years away.

 

[linusrichard]

Who said it wasn't? Every two player zero-sum perfect information game of finite length is solvable in the same way tic-tac-toe is. This includes Go, and also backgammon, where the chance events are all public information. Perhaps you were thinking of multi-player poker?

Go is solvable. Backgammon is not solvable, at least not in the sense that chess, checkers, tic-tac-toe, and go are. It may be solvable in the sense that, given a board position and given a dice roll, it is possible to determine what move is the most likely to give you the best result. But with those other games, perfect play will give you the same result every time. With backgammon, there is no such thing as perfect play - unless you define perfect play as making the best move under every circumstance, and even if you do that - and even if the other player doesn't, you can still lose.

So - either it is not true that every two player zero-sum perfect information game of finite length is solvable in the same way tic-tac-toe is, or it is not true that backgammon is a two player zero-sum perfect information game of finite length. I'm not sure what precisely is meant by "perfect information" or "finite length." Backgammon is a game of symmetrical information (unlike, say, poker), but unlike chess, there is a lot of information that is unknown to either player. Also, a backgammon game can last indefinitely.

 

[Prometheus]

Backgammon is not "perfect information" because you don't get to choose your own dice rolls.

 

[Folly]

Go is solvable. Backgammon is not solvable, at least not in the sense that chess, checkers, tic-tac-toe, and go are. It may be solvable in the sense that, given a board position and given a dice roll, it is possible to determine what move is the most likely to give you the best result. But with those other games, perfect play will give you the same result every time. With backgammon, there is no such thing as perfect play - unless you define perfect play as making the best move under every circumstance, and even if you do that - and even if the other player doesn't, you can still lose.

It's solvable the same way as tic-tac-toe in that if you propagate expected values from the leaves to the roots, choosing an action with the maximum expected value at each player choice node and averaging over chance nodes, you will get a pair of strategies that achieve the maximum possible expected value, against any opponent (minimax search.) That is perfect play. No, it doesn't necessarily get the same value in every instance of play, but what else do you expect in a stochastic game? There will be no other strategy that will do any better. The difference between a deterministic and non-deterministic game is not nearly as interesting as many other distinctions (eg zero-sum/non-zero-sum, two player/>2 player, perfect information/hidden information.)

If the game is not zero sum, this process doesn't guarantee that you will both achieve the best expected payoff. If there are lines of play in the game that do not end (e.g. you can play forever, as in chess or checkers if you remove all rules about repeated positions) or there are infinitely many states, you may not necessarily be able to compute a value and strategy for the game. Imperfect information games must be dealt with using much more cumbersome techniques.

So - either it is not true that every two player zero-sum perfect information game of finite length is solvable in the same way tic-tac-toe is, or it is not true that backgammon is a two player zero-sum perfect information game of finite length. I'm not sure what precisely is meant by "perfect information" or "finite length." Backgammon is a game of symmetrical information (unlike, say, poker), but unlike chess, there is a lot of information that is unknown to either player. Also, a backgammon game can last indefinitely.

Ahh. Well, if backgammon games can possibly last forever, that does make it slightly more different. I don't actually play backgammon, and I only skimmed through the rules. Sorry. If it's due to chance events, however, you can still get a good approximation of optimal play and the value of the game, assuming the values of the outcomes are bounded (or at least grow slowly enough) by doing the same minimax process, but stopping whenever the chance event gets sufficiently unlikely. There's some sort of doubling rule, so I don't know whether that holds true in backgammon...

As to the other terms, in a perfect information game, all players know the complete current state of the game. This is still true in backgammon: I don't know what random events will happen in the future, but I don't normally know what my opponent will do either. I do know all the moves my opponent made and the results of all the die rolls.

In an imperfect information game, you don't know exactly where you are in the game. In poker, you don't know your opponent's cards, even though they are an event that has already occurred. In rock paper scissors, you don't know your opponent's choice of action, even if it has already been made. While this is true, you can not treat the subtrees independently, which means you can't just propagate values back from the end of the game as in tic-tac-toe.

A finite game is just one with a finite number of states, although without further context it might also be implied that all lines of play are also finite. Possibly I should have actually said finite, terminating game.

 

[Folly]

Backgammon is not "perfect information" because you don't get to choose your own dice rolls.

Sorry, no. Perfect information is a technical term, and unless I've missed yet another rule in backgammon, it is a perfect information game. It just means that there's no hidden information.

... and possibly that explanation didn't help either. Consider a game. For any game, we can generate a graph (a series of vertices and edges, not a pie chart) where each vertex represents a state in the game, and the edges represent transitions from one state to another. This is called an extensive form game. Each vertex is controlled by a single player or a chance event (which means there are (at least) two different ways of representing rock paper scissors.)

Each vertex/state also belongs to a set, called an information set, which might only contain that single state. A player does not know their current state, they only know which information set contains the current state. That is, the information set represents what the player knows about the current state of the game. In Hold'em poker, for example, in the first round of a hand, player one might know they're in the information set contaning 2450 states reached by the betting sequence "check" where player one has Js2h. Because a player does not know their current state, they must play the same way for every state in the information set.

In a perfect information game, every state is in an information set which only contains itself. You may not know what the final state will be, because you do not control all future actions, but that's true regardless of whether some future states are controlled by an opponent or by chance.

 

[Prometheus]

Sorry, no. Perfect information is a technical term, and unless I've missed yet another rule in backgammon, it is a perfect information game. It just means that there's no hidden information.

...

Yeah, I realized my mistake and crossed out the post, probably while you were typing that.

 

[Folly]

Yeah, I realized my mistake and crossed out the post, probably while you were typing that.

I had wondered whether the longer explanation should have been there anyway. Your post was just the one with the apology for too many insufficiently defined terms and a definition

 

[linusrichard]

It's solvable the same way as tic-tac-toe in that if you propagate expected values from the leaves to the roots, choosing an action with the maximum expected value at each player choice node and averaging over chance nodes, you will get a pair of strategies that achieve the maximum possible expected value, against any opponent (minimax search.)

But that's a big difference from tic-tac-toe. In tic-tac-toe, you don't average over chance nodes (if I understand what that phrase means). Perfect play by one player will guarantee a draw or win every time for that player. Perfect play by both players will guarantee a draw every time.

That is perfect play. No, it doesn't necessarily get the same value in every instance of play, but what else do you expect in a stochastic game? There will be no other strategy that will do any better.

The bolded part, to me, means that backgammon is not solvable, or at least not solvable in the same way tic-tac-toe is. You can use "perfect play" in this way, but I prefer the term you use below, "optimal play." I don't have the vocabulary you do for this stuff, but I would use "perfect play" for games like tic-tac-toe and chess, and "optimal play" for games like backgammon and poker.

The difference between a deterministic and non-deterministic game is not nearly as interesting as many other distinctions (eg zero-sum/non-zero-sum, two player/>2 player, perfect information/hidden information.)

That may be, but in this context, it's a pretty important difference.

Ahh. Well, if backgammon games can possibly last forever, that does make it slightly more different.

Only slightly though, I think. Backgammon games can possibly last forever, but I've never played one that has. Seriously though, I've never even played one that seemed like it was going to last forever, never had to agree to a draw because I didn't have time to finish, etc., etc.

I don't actually play backgammon, and I only skimmed through the rules. Sorry. If it's due to chance events, however, you can still get a good approximation of optimal play and the value of the game, assuming the values of the outcomes are bounded (or at least grow slowly enough) by doing the same minimax process, but stopping whenever the chance event gets sufficiently unlikely. There's some sort of doubling rule, so I don't know whether that holds true in backgammon...

In order for a game to last forever, you would indeed need increasingly improbable series of dice rolls, so I think what you're talking about would work.

As to the other terms, in a perfect information game...

Thank you. You are right that backgammon fits this definition.

A finite game is just one with a finite number of states, although without further context it might also be implied that all lines of play are also finite. Possibly I should have actually said finite, terminating game.

Thank you. I believe backgammon is a finite game then. It could be argued that it is not, since the cube can be doubled indefinitely, and the value of the cube is part of the game state. However, I believe the value of the cube is not relevant to optimal play in money play, and it is not relevant in tournament play once it goes beyond the number of points needed to win the tournament, which is a finite number of points, of course.

 

[drkitten]

Wouldn't it be more accurate then, to say that most theoreticians PRAY that chess is a forced win for white?

Especially if it's like tic tac toe and it's a forced win for black due to being able to choose a proper response to whatever move white begins with.

No, no, and no.

First, the theoreticians believe that white has the win because white has such an advantage in high-level tournament play.

Second, a forced-win for black would be just as good for tree pruning as a forced win for white.

Third, tic-tac-toe is not a forced win for black. It's a forced draw, which is both rare and harder to analyze.

 

[Folly]

But that's a big difference from tic-tac-toe. In tic-tac-toe, you don't average over chance nodes (if I understand what that phrase means). Perfect play by one player will guarantee a draw or win every time for that player. Perfect play by both players will guarantee a draw every time.

That's not the usual meaning of perfect play, and even with this unusual caveat about the result being a constant value, it's certainly not true that perfect play by both players always results in a draw. Some games, like hex, do not even have a draw. (Hex is also interesting in that you can prove, without examining a single position, or knowing what the strategy is, that the first player has a winning strategy.)

That is perfect play. No, it doesn't necessarily get the same value in every instance of play, but what else do you expect in a stochastic game? There will be no other strategy that will do any better.

The bolded part, to me, means that backgammon is not solvable, or at least not solvable in the same way tic-tac-toe is. You can use "perfect play" in this way, but I prefer the term you use below, "optimal play." I don't have the vocabulary you do for this stuff, but I would use "perfect play" for games like tic-tac-toe and chess, and "optimal play" for games like backgammon and poker.

I agree that there is a distinction that can be made, constant value versus a distribution over outcomes, but it's not one I've seen made. Perfect play is following a strategy which has the maximum expected outcome against the toughest opponent (ie one that knows your strategy, but not which action you will pick if you randomise actions: your own personal nemesis.) This naturally covers two player games with and without random elements or hidden information, and is not an entirely useless concept even with more players.

Or, put another way, it's play where when the game is finished, you have no regret for playing the way you did. Sure, maybe some crazy chance event happened, and you could have done something else beforehand, but you couldn't know beforehand, and this alternate play would have been worse usually. There's no point reserving the term perfect play for something which makes decisions based on the outcome of future chance events: it's not actually achievable, and therefore not very interesting... This might be another case where the technical term veers slightly away from popular usage, but I think it might just be your preferences here because poker players will also sometimes talk about playing perfectly, but losing the hand: you expect to lose with a strong second best hand!

Or possibly you're also thinking of some sort of "perfect game" where all the chance falls in your favour, and you get the maximum possible score?

That may be, but in this context, it's a pretty important difference.

I'll accept that it is important to you. I would ask "why?" though. If a game has random events, why would you expect anything other than randomness in the outcomes?

 

[drkitten]

I agree that there is a distinction that can be made, constant value versus a distribution over outcomes, but it's not one I've seen made.

I, on the other hand, have seen that, and in exactly this context. It's possible to prove that tic-tac-toe is a forced draw and that Nim is a forced win for the first player (or second player, or whatever, depending upon the rules). It's not possible to prove that craps is a "forced" win for the house, even if the house has a long-term edge.

It's possible for a stochastic game to be a forced win for one player --- if I roll seven dice and you roll one, my pip total will always beat yours --- but I've never seen a non-trivial example of such a game.

 

[quarky]

In perfect play, how could first move (white) not always win?
if the best player in the world could somehow play against himself/herself, wouldn't he necessarily win as white?

I've played a bit of 'fairy chess' as my dad called it. I wish I'd taken more notes. We played games with no pawns, for instance, in which case, first move always won (I think)

More complex was chess with only pawns and king.

 

[gnome]

In perfect play, how could first move (white) not always win?
if the best player in the world could somehow play against himself/herself, wouldn't he necessarily win as white?

I've played a bit of 'fairy chess' as my dad called it. I wish I'd taken more notes. We played games with no pawns, for instance, in which case, first move always won (I think)

More complex was chess with only pawns and king.

That assumes that by making the first move that White has the advantage. If there is a win-or-draw response for every move White makes, White cannot force a win.

If there is a win-or-draw response for every response Black makes, Black cannot force a win.

 

[drkitten]

In perfect play, how could first move (white) not always win?

Ever played tic-tac-toe? It may be that black needs to make a mistake to allow white to win, while white needs to make two mistakes to allow black to win.... This would explain both white's advantage while still making the game technically a forced draw.

 

[Folly]

I, on the other hand, have seen that, and in exactly this context. It's possible to prove that tic-tac-toe is a forced draw and that Nim is a forced win for the first player (or second player, or whatever, depending upon the rules). It's not possible to prove that craps is a "forced" win for the house, even if the house has a long-term edge.

It's possible for a stochastic game to be a forced win for one player --- if I roll seven dice and you roll one, my pip total will always beat yours --- but I've never seen a non-trivial example of such a game.

If by "forced win" you mean that every single outcome is a win for the house, then yeah, it's pretty obvious craps isn't a forced win: you don't always lose on every single possible set of die rolls (is it even possible to construct any strategy for craps that always loses money on every game?) Where was this an interesting distinction? Some sort of non-uniform utility on top of payouts? If you have utility for different values, that should properly be treated by changing the values of the game, not by doing post-hoc adjustments to the expected game rewards. Or did you mean something else by a forced win?

 

[dudalb]

I presume if Backgammon is probably unsolvable, we can forget about Monopoly.

 

[Cuddles]

In perfect play, how could first move (white) not always win?
if the best player in the world could somehow play against himself/herself, wouldn't he necessarily win as white?

I'm not sure what this game is actually called, but here's a very simple example. Start off with a pile of tokens (I can't remember how many you need exactly, I think it has to be a prime number, and obviously bigger than five). Each turn you can remove 1, 2 or 3 tokens. Whoever takes the last token loses.

Do you think the first player is guaranteed to win if played perfectly? If you do, you'd be wrong. Whoever plays first is guaranteed to lose unless the other player screws up. Even if the best player in the world plays against himself, he will still lose (you know what I mean).

The point is, going first is not necessarily an advantage. With chess, it certainly appears to be an advantage, but there are two problems. Firstly, we haven't proven that it's actually an advantage. It could turn out that there's a perfect play which would mean black always wins. Secondly, even if there is an advantage, that does not guarantee you a win. If may be that black cannot win given perfect play by white, but that perfect play by black can still result in a draw.

 

[drkitten]

If by "forced win" you mean that every single outcome is a win for the house,

Yes. Just like every single outcome in Nim is a win for the first player (assuming the right variant of Nim).

then yeah, it's pretty obvious craps isn't a forced win: you don't always lose on every single possible set of die rolls (is it even possible to construct any strategy for craps that always loses money on every game?)

No, it's not possible to construct such a strategy. Of course, there's not much "strategy" in craps (in a game-theoretic sense) to begin with. You bet, you roll, you usually lose.

Where was this an interesting distinction?

Where? Baltimore, IIRC, at a game theory seminar at Hopkins.

Why? Because analysis of the variance in outcomes determines, among other things, how deep your pockets should be if you intend to play repeated measures. A "forced win" has no variance; you don't need any pocket money besides what you need to play the game for the first time. But if you've got variance, you need to have some reserve stakes in case you lose the first game.

This also gets into cheating detection (I saw an interesting paper on that a few years in the context of online gambling; how do you know the casino or player is honest?) Obviously, cheating detection is much easier if there's no chance that you can lose honestly.

 

[drkitten]

I'm not sure what this game is actually called, but here's a very simple example. Start off with a pile of tokens (I can't remember how many you need exactly, I think it has to be a prime number, and obviously bigger than five). Each turn you can remove 1, 2 or 3 tokens. Whoever takes the last token loses.

The game is usually called "Nim" and it comes in approximately as many variants as there are published papers on it. With "normal" Nim, where the person who takes the last token loses, it's a win for the second player if there are 4N +5 (or 1, but that's silly) tokens in the pile at the start of the game.

Basically, whatever move the first player makes (call it X), I remove 4-X tokens. This means that eventually there will be five in the heap at the end. I do the same thing once more, so he has one at the end that he is forced to take.

Turning it around, it is a win for the first player if there is any number other than 4N+1 at the start; the first player just removes enough to make it 4N+1.

With the variation that the player to take the last token wins, the magic number is 4N. It's a second player win if it starts at 4N, a first player win otherwise.

Other variants involve multiple piles and unrestricted number of tokens that can be removed from a single pile, or removal from multiple piles under various restrictions.

 

[Folly]

Why? Because analysis of the variance in outcomes determines, among other things, how deep your pockets should be if you intend to play repeated measures. A "forced win" has no variance; you don't need any pocket money besides what you need to play the game for the first time. But if you've got variance, you need to have some reserve stakes in case you lose the first game.

If there are multiple possible outcomes, but they are all positive, you're still guaranteed to walk away with more money. If there is any possibility of a negative outcome, no initial stake will guarantee you a positive outcome. If there is a constant outcome, repeated games aren't exactly interesting. What was the larger context that made it interesting to distinguish cases which make repeated games trivial? Some larger system where you have to be able to solve just a single game?

This also gets into cheating detection (I saw an interesting paper on that a few years in the context of online gambling; how do you know the casino or player is honest?) Obviously, cheating detection is much easier if there's no chance that you can lose honestly.

Well, it's certainly true that if you will walk away from every single game with less money unless you cheat, finding someone with more money is a pretty clear signal of cheating :/ Things like trying to see if their play changes based on information they shouldn't have seems more interesting...