> What if we make things easier for the machine? It is obvious to a rank beginner that a perfect game with a rook handicap is a win for the side with the material advantage. No, make it a queen! Surely that must be a provable win?
Hm, I'm sure it must be. Although I don't know how you go about proving it, it's a simple matter to force equal trades; black cannot avoid the exchange of pieces forever, and if white plays a perfect game he will always win, without doubt.
> Not so fast. Even against a crushing asymmetry in material, it is not too hard to avoid mate for a couple of dozen moves, which means that calculating all the way to the end of the game is beyond the reach of search-based algorithms.
Okay, just calculate the moves it would take to force the equal exchange of material from a given position. Generally as the game progresses and the board opens up it becomes inescapable.
After a certain point, when enough material has been removed from the board, looking for mate becomes trivial. Esp if you operate with such a commanding advantage as a queen...assuming you can force the equal exchange of all other material, it is possible to calculate checkmate within a couple of moves.
it's a simple matter to force equal trades; black cannot avoid the exchange of pieces forever, and if white plays a perfect game he will always win, without doubt.
Yes, that's pretty much the human intuition for why no one doubts that White will win. But it is very, very far from a mathematical proof.
Okay, just calculate the moves it would take to force the equal exchange of material from a given position.
Let me remind you that each ply has a branching factor of about 20, which means each move has a branching factor of several hundred. In most positions you'd be lucky to be able to calculate even one or two forced exchanges, let alone all the way to the end of the game.
A program attempting to prove victory operates in a very different context from a normal chess playing program — it is not allowed to prune any positions at all. We haven't even found the status of all seven piece endings yet! That is despite intense effort. See http://en.wikipedia.org/wiki/Endgame_tablebase
It is utterly, utterly inconceivable that a search-based approach will ever prove victory with Queen odds.
Not that I disagree with the overall point. A search-based approach might solve the game at queen odds, but it will not be any time soon; indeed, it would require devoting more computing resources than the planet has for a pretty significant amount of time.
No. randomwalker's point is that every branch must be proved to be a win.
>> "it would require devoting more computing resources than the planet has for a pretty significant amount of time"
This is also incorrect. As mentioned in other comments, the branching factor of chess implies that it is not brute force solvable using the entire universe as a computer--let alone just Earth.
No. randomwalker's point is that every branch must be proved to be a win.
In alpha-beta pruning, branches are only eliminated when they can only be reached through suboptimal play on one player's part. Suboptimal play on either player's part can clearly result in a loss for that player, but this is not very interesting.
This is also incorrect. As mentioned in other comments, the branching factor of chess implies that it is not brute force solvable using the entire universe as a computer--let alone just Earth.
This depends on how much time you're willing to devote to the task. My laptop (or my phone even) would be able to "solve" Chess given an infinite amount of time.
Now, the entire universe used as memory would be unable to store such a solution, but that isn't really germane to the decision problem.
> Yes, that's pretty much the human intuition for why no one doubts that White will win. But it is very, very far from a mathematical proof.
White will win if he plays perfectly: this is mathematically assured because white has an advantage of nine points. The only way for white to lose or to draw is by extreme error. The article assumes a perfect game, so I too assume that white will play a perfect game.
> Let me remind you that each ply has a branching factor of about 20, which means each move has a branching factor of several hundred. In most positions you'd be lucky to be able to calculate even one or two forced exchanges, let alone all the way to the end of the game.
As I recall, Deep Blue was calculating at a depth of more than eight moves...
> The Deep Blue chess computer which defeated Kasparov in 1997 would typically search to a depth of between six and eight moves to a maximum of twenty or even more moves in some situations. -- http://en.wikipedia.org/wiki/Deep_Blue_(chess_computer)
I find it difficult to believe that this wouldn't have improved or could not be improved upon, since this was based on the technology available in 1997. It's safe to say we've made progress since then.
While you may not be able to calculate an entire game, you could certainly calculate all the exchanges required to reach a properly winnable and calculable endgame. This is pretty damn close to being able to calculate a whole game...and you're assured victory.
As I said, once you get to a point of two kings and a queen, it's trivial.
I think one important point you're missing is that a chess engine looking to mathematically prove a victory is very different from the ones that play against grand masters. Deep Blue may have been able to calculate 6 to 8 moves in advance, but that was after it pruned all the moves that were obviously incorrect. When you're trying to prove something mathematically however, you have to assume that even something as silly as sacrificing a queen for a pawn with no obvious positional gains is a valid move and calculate all possible branches taken from that move until checkmate some 30 moves down the road.
For example, checkers is a vastly simpler game than chess. Yet, it took 18 years of constant computation to solve it [1]. Even a game as simple as tic-tac-toe has 255,168 possible games [2]. The estimated number of chess games is 10^10^50 [3].
It is important to remember that "the value of 1 Queen is equivalent the value to 9 Pawns" is only an heuristic. It helps the players to make decisions but nobody wins only because he has more points.
And the values are not written in stone. For example, Knights and Bishops usually have the same value, that is like tree pawns for each one. But if the position is open the Bishops are usually more valuable and if the position is closed the Knight are more valuable.
I'm also completely sure that in "Chess with Queen" White has a wining strategy, but being completely sure is not a proof. (I have been wrong before!)
Serious chess player here. I'm sure that Rook or Queen odds is a win but it is not a simple matter to force equal trades in chess games. It may be easier to force them with those odds (I never studied odds games much so I don't know a ton about how the dynamics change -- but neither have you), but I don't see why.
In general in chess the opening determines how easy it is to trade pieces and who has the option to trade how much. In some openings you cannot easily trade any pieces even if you want to. In others you can trade several if you want.
It's easy to give examples. White can trade his f1 bishop off easily in many e4 openings (not just against e5 but also against c5 nf3 d6/nc6). Or in d4/d5 openings with Bf4, black can play Bd6 to trade. There are also plenty of opportunities for white to play Bg5 and trade for a knight in various openings. But if you take other openings, like a closed French it's hard to trade pieces. Or a French with black trading his bishop on c3, it's hard to trade the other pieces. Or in a king's indian you don't necessarily have any good way to trade pieces without taking on some disadvantage. Or in a Najdorf obviously you can force some trading if you want to play Nd5 in some lines for example (I mean lines with e5 by black, not the piece sac lines) but when you do so it's not actually very good for white. This is one of many examples where going after a piece trade gets you some disadvantage.
Sorry for details, but really you can't comment on this stuff without knowing a hell of a lot more details than I just wrote. There are plenty of openings that do not allow convenient trading of many minor pieces, and trades of majors aren't all that common. Another good example is all IQP openings for either side which allow some trading but also get dynamic and interesting positions (and of course they are also positions where you're completely screwed down a queen). IQP positions are also interesting in that the IQP side must avoid trades b/c he has a losing endgame, and conservative players think it's bad for the IQP player but actually those positions are fine.
The strategy "just trade stuff and get to the end game" in normal chess is not easy to implement if your opponent doesn't want it.
tl;dr in chess it's usually pretty easy for white to trade one set of minor pieces but not necessarily any more, and doing so may be (slightly) bad for him.
Even in games with a huge advantage you can get in to situations where the other party can force a draw through the 3 repeated moves rule unless you offer some piece to break their possibility of forcing the draw. That can be expensive.
There are so many exceptions and pitfalls to work out that I'm sure that there is no 'shortcut' to the answer, but I do lean to support the idea that a queen advantage should be a win, in fact, I think that any piece or even just a pawn advantage should be a win, witness how many grand master games literally turned to watershed losses once that precarious balance was lost by as much as a single pawn.
Even so, the risk a of a draw is significant, the risk of an opponents win much less so.
Chess is all about the 'mate', not about who has the most points on the board anyway. Woe the player that forgets this even for a moment.
It's funny how the '3 repeating moves' rule makes chess actually much harder to reason about in terms of guaranteed endings because it means that a definite material advantage may still result in a draw, is there a factor known for how much this rule adds to the complexity of proving a win?
Another question that might be interesting is if a pawn advantage would be enough to cancel whites advantage by starting the game, I suspect that a single pawn is worth more than whites advantage but I'm not sure about this, and it might depend on the pawn (some pawns gone would allow white to deploy much faster with the price of the pawn only appearing later on in the game).
Repetition issues are rare in practice. I see why it could be important to a proof. But if I was playing a queen up against anyone I wouldn't repeat, I'd just make progress until I won. Repetition wouldn't come up, it's rare enough in close games. It's most common in (near or exactly even material) end games which queen odds games won't reach without hanging a queen.
A minor piece odds is a win for sure, any chess play can tell you that. But a pawn up .. that is unclear. You speak of GM games being decided by a pawn which of course happens but what you do not speak of is material sacrifices in GM games which are common too. And there's all those endgames which the pawn-down player wins (often by superior play, sometimes other reasons). And there's all those well known ways an extra pawn in an end game can be a draw, including for example king+pawn vs king is drawn unless it's set up so you can force promotion quickly (e.g. defending king is out of position). King+rook+pawn vs king+rook is common and this is also drawn in general (the defense is called the philidor position) unless the pawn-up side starts in an advantageous position (something equivalent to the lucena position)
One of the interesting facts about pawn odds is that you now have an open file b/c of your missing pawn. And pawns restrict moving out your pieces so having one missing can save time. The worst thing you could do is take away black's f7 pawn at the start. That is, first guess, a loss for black. Take away some other pawn and do it from white and it's a lot harder to guess.
The rule of thumb taught to beginners is that a pawn is worth 3 moves in the early game (and a knight is 3 pawns so you might think it's worth 9 moves, but that conversion doesn't work well, with 9 free moves you could set up checkmate). I think a pawn is worth somewhat less than 3 moves but it really varies and the comparison doesn't entirely make sense.
BTW there do exist well known openings leading to an unclear/unknown result that involve a piece sacrifice (lines in the King's Gambit or Najdorf for example). Losing a piece for nothing is a clear loss but various kinds of compensation are possible.
> Serious chess player here. I'm sure that Rook or Queen odds is a win but it is not a simple matter to force equal trades in chess games. It may be easier to force them with those odds (I never studied odds games much so I don't know a ton about how the dynamics change -- but neither have you), but I don't see why.
Seriously? Tournament chess player here with experience playing a range of levels up to and including grandmasters. You've got to be off your rocker if you think that it isn't easier to force trades with a QUEEN advantage.
White needs but play to the center. Play to open up the board will be inescapable. Black's only recourse (to avoid exchanges) would be to effectively give up the center or attempt some kind of closed defense like the Sicilian Dragon. Even in the case of the latter, he'll be forced into positions that will allow for the equal exchange of material or near equal material.
Assuming black moves only with the intent to avoid exchanges, he'll land himself in a terrible tactical position.
Lastly why are you comparing this kind of game to STANDARD lines that would involve balanced material? This is not a standard game. Did you seriously spend a paragraph talking about the French, King's Indian, and Najdorf? Of these, exchanges are not only highly probable, they are INEVITABLE regardless of, "...some lines for example (I mean lines with e5 by black, not the piece sac lines) but when you do so it's not actually very good for white." Virtually no standard line can be bad for white when he is up a QUEEN.
The point being: even if white is down a pawn or two pawns or even three pawns, he is STILL ahead. White has a considerable advantage in making exchanges because they are implicitly better for him even when he may lose minor material.
To anyone here saying that a queen is just a theoretical advantage: you know nothing about chess if you seriously believe that. I'd challenge you to play against a master, not even a grandmaster, with those odds and I guarantee you'll lose every game. You won't even stand a chance of drawing. Forget that. You will lose, horribly.
It isn't just a heuristic, the queen is an extremely powerful piece, with black down a queen the remainder of play is EXTREMELY unbalanced.
Whether or not you can prove this completely is another matter, but who cares? It's an obvious win in a perfect world. There's little to no mystery there. And it's hardly a reflection of the mechanics of an actual game, given how unbalanced it becomes.
Hm, I'm sure it must be. Although I don't know how you go about proving it, it's a simple matter to force equal trades; black cannot avoid the exchange of pieces forever, and if white plays a perfect game he will always win, without doubt.
> Not so fast. Even against a crushing asymmetry in material, it is not too hard to avoid mate for a couple of dozen moves, which means that calculating all the way to the end of the game is beyond the reach of search-based algorithms.
Okay, just calculate the moves it would take to force the equal exchange of material from a given position. Generally as the game progresses and the board opens up it becomes inescapable.
After a certain point, when enough material has been removed from the board, looking for mate becomes trivial. Esp if you operate with such a commanding advantage as a queen...assuming you can force the equal exchange of all other material, it is possible to calculate checkmate within a couple of moves.