Is Chess with Queen Odds a Provable Win?
arvindn.livejournal.com
arvindn.livejournal.com
And from the linked article by Kasparov (http://www.nybooks.com/articles/archives/2010/feb/11/the-che...) comes this gem:
In what Rasskin-Gutman explains as Moravec’s Paradox, in chess, as in so many
things, what computers are good at is where humans are weak, and vice versa.
This gave me an idea for an experiment. What if instead of human versus machine
we played as partners? My brainchild saw the light of day in a match in 1998
in León, Spain, and we called it “Advanced Chess.” Each player had a PC at hand
running the chess software of his choice during the game. The idea was to
create the highest level of chess ever played, a synthesis of the best of man
and machine.
....
In 2005, the online chess-playing site Playchess.com hosted what it called a
“freestyle” chess tournament in which anyone could compete in teams with other
players or computers. Normally, “anti-cheating” algorithms are employed by
online sites to prevent, or at least discourage, players from cheating with
computer assistance. (I wonder if these detection algorithms, which employ
diagnostic analysis of moves and calculate probabilities, are any less
“intelligent” than the playing programs they detect.)
Lured by the substantial prize money, several groups of strong grandmasters
working with several computers at the same time entered the competition. At
first, the results seemed predictable. The teams of human plus machine
dominated even the strongest computers. The chess machine Hydra, which is a
chess-specific supercomputer like Deep Blue, was no match for a strong human
player using a relatively weak laptop. Human strategic guidance combined with
the tactical acuity of a computer was overwhelming.
The surprise came at the conclusion of the event. The winner was revealed to be
not a grandmaster with a state-of-the-art PC but a pair of amateur American
chess players using three computers at the same time. Their skill at
manipulating and “coaching” their computers to look very deeply into positions
effectively counteracted the superior chess understanding of their grandmaster
opponents and the greater computational power of other participants. Weak human
+ machine + better process was superior to a strong computer alone and, more
remarkably, superior to a strong human + machine + inferior process.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.
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...;
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.
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.
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.
For example, according to Wikipedia, a computer actually beat a professional Go player for the first time in 2008.
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.
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.
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
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.
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.
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.
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.
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).
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."
In case anybody is interested
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.
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.
>> "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.
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.
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.
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-...
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!)
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.
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).
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.
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.