6 ms·

> 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 materi

> 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.

randomwalker 16y ago
I'm sorry, but that is simply incorrect. 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 http://en.wikipedia.org/wiki/Endgame_tablebase It is utterly, utterly inconceivable that a search-based approach will ever prove victory with Queen odds.
- shinkansen 16y ago
  > 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) 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.
  - _flag 16y ago
    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]. 1. http://www.newscientist.com/article/dn12296-checkers-solved-after-years-of-number-crunching.html http://www.newscientist.com/article/dn12296-checkers-solved-... 2. http://en.wikipedia.org/wiki/Tic-tac-toe http://en.wikipedia.org/wiki/Tic-tac-toe 3. http://mathworld.wolfram.com/Chess.html http://mathworld.wolfram.com/Chess.html
xenophanes 16y ago
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.
- jacquesm 16y ago
  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).

randomwalker 16y ago

I'm sorry, but that is simply incorrect. 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 http://en.wikipedia.org/wiki/Endgame_tablebase It is utterly, utterly inconceivable that a search-based approach will ever prove victory with Queen odds.

shinkansen 16y ago
> 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) 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.
- _flag 16y ago
  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]. 1. http://www.newscientist.com/article/dn12296-checkers-solved-after-years-of-number-crunching.html http://www.newscientist.com/article/dn12296-checkers-solved-... 2. http://en.wikipedia.org/wiki/Tic-tac-toe http://en.wikipedia.org/wiki/Tic-tac-toe 3. http://mathworld.wolfram.com/Chess.html http://mathworld.wolfram.com/Chess.html

xenophanes 16y ago

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.

jacquesm 16y ago
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).