Is Chess with Queen Odds a Provable Win?(arvindn.livejournal.com)
arvindn.livejournal.com
Is Chess with Queen Odds a Provable Win?
http://arvindn.livejournal.com/129555.html
7 comments
Moravec's "Paradox" isn't really paradoxical at all. What makes us say that computers are "strong" in some area? Answer: the fact that they are good there relative to our prior expectations. Where do those expectations come from? From looking at ourselves. Similarly: what determines where we say we're "weak"? Answer: seeing other things being strong relative to us. Computers, for instance.
Now, of course there are other points of reference for deciding where we're "weak". Doesn't that invalidate my argument? Why, no, because actually if we use those other points of reference the paradox rather goes away. For instance: Computers do arithmetic very, very fast. Is that an area where we're weak? Only if we compare ourselves against computers; we do arithmetic much better than chickens or tigers do.
Now, of course there are other points of reference for deciding where we're "weak". Doesn't that invalidate my argument? Why, no, because actually if we use those other points of reference the paradox rather goes away. For instance: Computers do arithmetic very, very fast. Is that an area where we're weak? Only if we compare ourselves against computers; we do arithmetic much better than chickens or tigers do.
[deleted]
Arimaa is a great game. I've been playing with friends for a couple of months and I'm always amazed by how complex gameplay can emerge from such simple rules.
about two weeks ago:
http://news.ycombinator.com/item?id=2054039
http://news.ycombinator.com/item?id=2054039
> Indeed, if you start from a closed position where strategy dominates and tactics are of relatively little use, top human players can still trounce computers
I haven't been following computer chess as much as I used to be I suspect this is actually untrue. Computer speed has been increasing as always but there has also been massive gains in chess program strength (e.g. compared to old programs when running on the same hardware). For example, Rybka 4 would absolutely crush programs from 10 years ago.
Those combined gains make computer chess programs so strong that I doubt even top players can hold them off even with the position looks quiet. Rybka can defeat GMs even when they have pawn plus first move odds[1]. In one match Rybka had a tiny opening book so the GM had every opportunity to steer the game in a strategic direction.
1. <http://en.wikipedia.org/wiki/Rybka#Odds_matches_versus_grand...;
I haven't been following computer chess as much as I used to be I suspect this is actually untrue. Computer speed has been increasing as always but there has also been massive gains in chess program strength (e.g. compared to old programs when running on the same hardware). For example, Rybka 4 would absolutely crush programs from 10 years ago.
Those combined gains make computer chess programs so strong that I doubt even top players can hold them off even with the position looks quiet. Rybka can defeat GMs even when they have pawn plus first move odds[1]. In one match Rybka had a tiny opening book so the GM had every opportunity to steer the game in a strategic direction.
1. <http://en.wikipedia.org/wiki/Rybka#Odds_matches_versus_grand...;
Good point. When I wrote that what I had in mind is puzzle-like positions where strategic planning is required. For example see http://en.wikipedia.org/wiki/Fortress_(chess)#Defense_perime... (Petrosian vs Hazai).
My real point here is that no chess program incorporates strategy the way humans do, and that it is unfortunate that this goal isn't being pursued.
My real point here is that no chess program incorporates strategy the way humans do, and that it is unfortunate that this goal isn't being pursued.
On the other hand you have beautiful games like this one:
http://www.chessgames.com/perl/chessgame?gid=1124533
where the computer has a lot of trouble finding the best move. Clearly programs still do not understand at the level that was hoped for in the 60's. Furthermore top human players with computer assistance can still exploit the weaknesses engines have in closed positions.
http://www.chessgames.com/perl/chessgame?gid=1124533
where the computer has a lot of trouble finding the best move. Clearly programs still do not understand at the level that was hoped for in the 60's. Furthermore top human players with computer assistance can still exploit the weaknesses engines have in closed positions.
If anyone is serious about proving things about chess I would suggest they start by proving things about simpler chess variants.
The variant of chess "wild 5" where your pawns start on the 7th rank and pieces on the 8th (so pawns promote in one move) has far fewer choices than in chess. It's a simpler game. It has a significant advantage for white, much larger than in normal chess. Humans came somewhat near to proving it's a win for white just by learning the (relatively few) openings out to 20 or so moves. At each step there's usually only a couple moves that aren't terrible. For the first six moves there is a single way of playing which is considered best for both sides.
Yet even in this much simpler game which humans are near cracking, I think a pure math type approach would have a very hard time getting anywhere.
If you can't do anything there, you could always try an even simpler game. There is a game called pawns where you start with only your pawns. If you promote you win instantly. Math ought to be able to solve that one. If you crack that, move on to little chess (normal chess but only with pawns and kings). Little chess should no doubt be a draw (you can waste moves with your king unlike in pawns where it's less clear) but proving that would be a good accomplishment I think.
The variant of chess "wild 5" where your pawns start on the 7th rank and pieces on the 8th (so pawns promote in one move) has far fewer choices than in chess. It's a simpler game. It has a significant advantage for white, much larger than in normal chess. Humans came somewhat near to proving it's a win for white just by learning the (relatively few) openings out to 20 or so moves. At each step there's usually only a couple moves that aren't terrible. For the first six moves there is a single way of playing which is considered best for both sides.
Yet even in this much simpler game which humans are near cracking, I think a pure math type approach would have a very hard time getting anywhere.
If you can't do anything there, you could always try an even simpler game. There is a game called pawns where you start with only your pawns. If you promote you win instantly. Math ought to be able to solve that one. If you crack that, move on to little chess (normal chess but only with pawns and kings). Little chess should no doubt be a draw (you can waste moves with your king unlike in pawns where it's less clear) but proving that would be a good accomplishment I think.
Game researchers don't ignore all Chess-like games that are more difficult for computers. It's just that they've met with very, very limited success in Go. Combined with Go's relative unpopularity outside of southeast Asia, this means you don't hear about it very much.
For example, according to Wikipedia, a computer actually beat a professional Go player for the first time in 2008.
For example, according to Wikipedia, a computer actually beat a professional Go player for the first time in 2008.
I think, from the viewpoint of a mathematician, there has been more progress in solving Go than in solving chess. http://math.berkeley.edu/~berlek/cgt/go.html shows some progress on generic Go endgames; I've never seen something similar for chess. It all is either a smart exhaustive search, or the use of heuristics that humans think can be used to value positions. I am not aware of any research on the validity of such heuristics.
Because of that, I think chances are we will solve Go before we solve chess in the mathematical sense (at the same time, I think chances are effectively zero that I'll live to see either happen). Yes, chess has a much smaller search tree, but it is inconceivably large to start with, and its rules are ugly. That means that any mathematical breakthrough will likely have lots of ugly special cases (even ignoring rochade and en passant). Go, in contrast, has a much simpler structure.
Because of that, I think chances are we will solve Go before we solve chess in the mathematical sense (at the same time, I think chances are effectively zero that I'll live to see either happen). Yes, chess has a much smaller search tree, but it is inconceivably large to start with, and its rules are ugly. That means that any mathematical breakthrough will likely have lots of ugly special cases (even ignoring rochade and en passant). Go, in contrast, has a much simpler structure.
Sure, perhaps with a huge handicap or on a 9x9 board. There exists no computer that could ever beat any professional go player in an even 19x19 game, even if you gave the professional as many beers as he could drink.
Well, that's what it says on Wikipedia -- though as it happens, the citations are both dead links, so your guess is as good as mine.
edit: Trivial search turned this up: http://www.sciencedaily.com/releases/2009/05/090514083931.ht...
Wikipedia was apparently talking about a handicap match. Still, it's very telling that 2008 was the first time a computer beat a pro even in a handicap match.
edit: Trivial search turned this up: http://www.sciencedaily.com/releases/2009/05/090514083931.ht...
Wikipedia was apparently talking about a handicap match. Still, it's very telling that 2008 was the first time a computer beat a pro even in a handicap match.
well, handicaps can be arbitrarily large. so a bot could have beaten a pro with handi even 40 years ago, as long as you make the handi large enough.
recently bots have gotten a lot better at go - they just passed 3dan rank, which is above where most amateurs ever reach. http://www.lifein19x19.com/forum/viewtopic.php?f=18&t=13...
But they still have a ways to go.
Here is a (fake money) future prediction market on whether a bot will beat a pro in an even game by 2020 - running at 20% right now. http://www.ideosphere.com/fx-bin/Claim?claim=GoCh
recently bots have gotten a lot better at go - they just passed 3dan rank, which is above where most amateurs ever reach. http://www.lifein19x19.com/forum/viewtopic.php?f=18&t=13...
But they still have a ways to go.
Here is a (fake money) future prediction market on whether a bot will beat a pro in an even game by 2020 - running at 20% right now. http://www.ideosphere.com/fx-bin/Claim?claim=GoCh
In this case, they were fairly reasonable handicaps -- six to eight stones, though certainly large, is not unheard of. You could see that kind of difference between a low-level and a high-level amateur, for example.
Sure, it's not unheard of, but it's still huge! It's extremely hard to become six or eight stones better from that level, and by all appearances, it represents an enormous gap in ability. The most talented and smartest humans take years of constant study and practice in their teens and 20s (at the height of their cognitive power) to go from 2d or 3d amateur -- the strongest programs -- to become a high-dan professional. Further perspective: Various professionals have remarked that they believe the best humans are only about 3 handicap stones weaker than God.
Consider this. Perhaps you play chess; David Levy's famous chess AI bet was that no computer by 1978 could beat him, a chess international master, in a match (I don't know his exact strength, but presumably 2400-2500 Elo -- much, much stronger than an expert!) Now, in 1978 the best computer could not beat him in a match. But it did win a game, and draw a game. However, it took nearly another 20 years from there before a computer could beat the world champion.
But Go computers, relatively speaking are not even as good at Go as the 1978 computer was at chess. The equivalent of a 2d amateur at Go might be a 2100 Elo human at chess, a strong expert; certainly not an IM! So it's not obvious to me that Go computers will be at a world-class level in a shorter timeframe than 20 years. Indeed, I believe more effort has gone into computer Go circa 2010 than had gone into computer chess circa 1978, so it might be reasonable to expect progress to continue even slower.
Consider this. Perhaps you play chess; David Levy's famous chess AI bet was that no computer by 1978 could beat him, a chess international master, in a match (I don't know his exact strength, but presumably 2400-2500 Elo -- much, much stronger than an expert!) Now, in 1978 the best computer could not beat him in a match. But it did win a game, and draw a game. However, it took nearly another 20 years from there before a computer could beat the world champion.
But Go computers, relatively speaking are not even as good at Go as the 1978 computer was at chess. The equivalent of a 2d amateur at Go might be a 2100 Elo human at chess, a strong expert; certainly not an IM! So it's not obvious to me that Go computers will be at a world-class level in a shorter timeframe than 20 years. Indeed, I believe more effort has gone into computer Go circa 2010 than had gone into computer chess circa 1978, so it might be reasonable to expect progress to continue even slower.
So it's not obvious to me that Go computers will be at a world-class level in a shorter timeframe than 20 years.
Don't get me wrong: I agree with you 100% on this. I'd more likely go further and wager against that happening. Go has an absolutely silly branching factor, no solid method of pruning, and no straightforward position evaluation function. Material doesn't work nearly as well as it does in Chess, and the sheer amount of information contained in the board makes the "mean value of this board position in past grandmaster games" approach completely infeasible.
My only point is that researchers are, indeed, making progress. It's just very limited.
Don't get me wrong: I agree with you 100% on this. I'd more likely go further and wager against that happening. Go has an absolutely silly branching factor, no solid method of pruning, and no straightforward position evaluation function. Material doesn't work nearly as well as it does in Chess, and the sheer amount of information contained in the board makes the "mean value of this board position in past grandmaster games" approach completely infeasible.
My only point is that researchers are, indeed, making progress. It's just very limited.
No his guess is better than yours. Go programs are still trying to compete with amateurs.
+1 for funding issues.
When I was working on my undergraduate thesis on applying machine learning techniques to board games, I developed the basis of a new method of analyzing board games (using graphs of games and graph isomorphism) but I wasn't able to find anyone who could finance me doing a research masters in it. Although I think part of my issue was that it wasn't obviously Computer Science, nor was it obviously Mathematics.
When I was working on my undergraduate thesis on applying machine learning techniques to board games, I developed the basis of a new method of analyzing board games (using graphs of games and graph isomorphism) but I wasn't able to find anyone who could finance me doing a research masters in it. Although I think part of my issue was that it wasn't obviously Computer Science, nor was it obviously Mathematics.
The old saw still rings true: turn your research problem into a military application and the DoD will likely fund it. Perhaps instead modeling a chess board as a graph you model passable routes in a mountainous terrain. Instead of chess pieces, maybe the forces you're modeling are small groups with different movement characteristics?
Which chess piece is the guys with guns, and which chess piece is the airstrike?
"In this paper we assume all forces are ground-based and beyond any hope of air-support or resupply. Historical analysis of battle-field circumstance will reveal numerous instances--even in the modern period--of such occurrences. A more general result is beyond the scope or intention of this paper."
Sounds interesting. Is an overview of your new method available to the public?
No, mostly I just had a whole bunch of vaguely related ideas to do with analyzing the graphs of games, but I really need to find some time to hammer out the details to get something I could actually publish.
I spent a lot of time while writing my thesis on machine learning thinking about the different approaches that have been taken to board games and most tend to involve some sort of analysis of the board, and it occurred to me that rather than studying the board it might make sense to study the graph that shows how those different board states are connected.
After all you could have two games that superficially from their boards and rules look completely different but have identical graphs. Now what if we could solve one of the games easily but the other game was hard, if the graphs are identical you could covert any game state between the two games, thus using the easy game to solve the hard game.
So then you can look at things at how to create an easy game which has the same graph as a hard game, obviously for something like chess this is hard, but you don't have to replicate the whole game graph, you can do it in chunks breaking the big graph into a series of smaller graphs and then attacking them.
There's all sort of other interesting things you can do with game graphs, for example you can start enumerating all games with a certain complexity (in terms of node and vertices) and ask questions like "are some game graphs fundamentally more difficult than others" and perhaps more importantly "why?". I think the area has a big potential for deepening our understanding of board games and also raising some interesting complexity and information theory problems.
I spent a lot of time while writing my thesis on machine learning thinking about the different approaches that have been taken to board games and most tend to involve some sort of analysis of the board, and it occurred to me that rather than studying the board it might make sense to study the graph that shows how those different board states are connected.
After all you could have two games that superficially from their boards and rules look completely different but have identical graphs. Now what if we could solve one of the games easily but the other game was hard, if the graphs are identical you could covert any game state between the two games, thus using the easy game to solve the hard game.
So then you can look at things at how to create an easy game which has the same graph as a hard game, obviously for something like chess this is hard, but you don't have to replicate the whole game graph, you can do it in chunks breaking the big graph into a series of smaller graphs and then attacking them.
There's all sort of other interesting things you can do with game graphs, for example you can start enumerating all games with a certain complexity (in terms of node and vertices) and ask questions like "are some game graphs fundamentally more difficult than others" and perhaps more importantly "why?". I think the area has a big potential for deepening our understanding of board games and also raising some interesting complexity and information theory problems.
Was it anything like the 'Method of Analogies' from KAISSA?
There is another closely related field that has plenty of real applications: formal verification. Essentially the task is to ensure no reachable state violates some property. The problem is the same as in chess, the reachable state space is enormous. There is probably more funding available for this take on the problem than chess, but it has been studied for decades and there are no easy answers.
Out of curiosity, I wonder how long it'll be before we can simply compute every possible valid game, inserting every valid move into some type of tree structure, and have a computer simply walk the tree structure always aiming for a "win" leaf.
Anybody have any ideas on how big the data for that would be? (I suspect there could be some optimizations as some games that start differently could end up in the same state as some other games -- i.e. optimize for board state collisions).
Anybody have any ideas on how big the data for that would be? (I suspect there could be some optimizations as some games that start differently could end up in the same state as some other games -- i.e. optimize for board state collisions).
It's possible we never will. Although we take Moore's law for granted, eventually we'll hit the natural limits of computation and storage per m^3, and solving chess completely may well be beyond that (but maybe not, as well).
From Wikipedia (http://en.wikipedia.org/wiki/Shannon_number):
"Allis also estimated the game-tree complexity to be at least 10^123, "based on an average branching factor of 35 and an average game length of 80". As a comparison, the number of atoms in the observable universe, to which it is often compared, is estimated to be between 4×10^79 and 10^81."
From Wikipedia (http://en.wikipedia.org/wiki/Shannon_number):
"Allis also estimated the game-tree complexity to be at least 10^123, "based on an average branching factor of 35 and an average game length of 80". As a comparison, the number of atoms in the observable universe, to which it is often compared, is estimated to be between 4×10^79 and 10^81."
I'm wondering if that number is for every possible game valid or invalid, or just valid games.
In case anybody is interested
http://en.wikipedia.org/wiki/Solved_game
In case anybody is interested
http://en.wikipedia.org/wiki/Solved_game
Unless quantum computing pays off in unexpected ways I would wager 'never'.
> 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.
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.
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.
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).
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.
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.
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.
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
It is utterly, utterly inconceivable that a search-based approach will ever prove victory with Queen odds.
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.
it is not allowed to prune any positions at all
https://secure.wikimedia.org/wikipedia/en/wiki/Alpha-beta_pr...
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.
https://secure.wikimedia.org/wikipedia/en/wiki/Alpha-beta_pr...
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.
>> "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.
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.
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].
1. http://www.newscientist.com/article/dn12296-checkers-solved-...
2. http://en.wikipedia.org/wiki/Tic-tac-toe
3. http://mathworld.wolfram.com/Chess.html
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-...
2. http://en.wikipedia.org/wiki/Tic-tac-toe
3. http://mathworld.wolfram.com/Chess.html
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!)
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!)
And from the linked article by Kasparov (http://www.nybooks.com/articles/archives/2010/feb/11/the-che...) comes this gem: