Rybka Solves the King's Gambit Chess Opening 206
New submitter smarq2 writes "Chessbase reports that chess programmer IM Vasik Rajlich has solved the King's Gambit chess opening with technical means. 3000 processor cores, running for over four months, exhaustively analyzed all lines that follow after 1.e4 e5 2.f4 exf4 and came to some extraordinary conclusions."
Update: 04/02 22:11 GMT by U L : Skuto points out that this is the same person who was found guilty of plagiarizing GNU Chess and Crafty.
The extraordinary conclusions? Only one move! (Score:5, Informative)
There is only one move in which White can force a draw - and to find out what it is, you'll have to RTFA.
Nah, I'm just pulling your leg, here you go..
Anybody really interested in the details will still RTFA anyway and the rest of us won't be left hanging with a teaser.
All lines...? (Score:5, Informative)
"Whenever Rybka evaluates a position with a score of +/– 5.12 we don't need to search any further, we have our proof that in the continuation there is going to be a win or loss, and there is a forced mate somewhere deep down in the tree. We tested a random sampling of positions of varying levels of difficulty that were evaluated at above 5.12, and we never saw a solution fail. So it is safe to use this assumption generally in the search."
Hmmm... Really? The whole "solved" thing hinges on this assumption.
A probabilistic algorithm (Score:5, Informative)
Re:The extraordinary conclusions? Only one move! (Score:4, Informative)
Also, it's a nonrigorous "proof":
Re:Rybka was made by plagiarizing a GPL program. (Score:5, Informative)
Slashdot even covered that; http://games.slashdot.org/story/11/06/29/1824253/worlds-best-chess-engine-outlawed-and-disqualified [slashdot.org]
Looks like the editors have a short memory.
+ / - 5.12 is a lot of difference (Score:5, Informative)
Chess programs usually score a position in "pawn equivalents". Having one pawn more is a +1, unless your opponent has compensation in position. Having one less would be a -1. Other examples are:
-a knight or bishop is worth roughly 3 points
-a rook is worth roughly 5 points
In practice, skilled players will win a +5 position reliably. A +3 is usually enough as well. So even if Rybka's evaluation is a bit off, I would not see much chances to win the match from the inferior position.
Re:A probabilistic algorithm (Score:3, Informative)
You cannot publish a paper or write a thesis that says "I'm pretty sure P!=NP".
You can publish papers based on probabilistic proofs though. In fact, there's an entire complexity heirarchy based on such things.
Re:The extraordinary conclusions? Only one move! (Score:5, Informative)
That's the difference between an experiment and a proof.
Re:Rybka was made by plagiarizing a GPL program. (Score:1, Informative)
Plagarism isn't theft, dumbfuck. It's fraud.
Re:Rybka was made by plagiarizing a GPL program. (Score:4, Informative)
For the benefit of those reading this who are not familiar with the Rybka situation, I want to point out that the author of Rybka did do a lot of original work on it too -- it wasn't a "complete clone" like some of the more blatant plagarism cases in the computer-chess world have been. But he still did plagarize certain parts of Crafty and Fruit which gave him a significant advantage over the other competitors in the WCCC and other tournaments. These tournaments are really competitions between programmers to see who can make the best-playing engine. And in order for them to be fair, each team entering the tournament must write their engine entirely by themselves, and disclose the origins of any third-party code used in their engine. Rybka versions that contained third-party code from Crafty and Fruit were entered into several of these tournaments without declaring that this code was used, and without getting the permission of the authors of Crafty and Fruit (either explicitly, or via some sort of license grant). In fact, Rybka's use of this code violated both Crafty's license (a non-commercial-use license which also has a clause prohibiting use of Crafty code in a tournament without permission from Crafty's author, Dr. Bob Hyatt) and Fruit's license (GPL v2).
Re:Solved from Black's point of view (Score:4, Informative)
Bobby Fisher already solved it. ;)
"After Bobby Fischer lost a 1960 game[4] at Mar del Plata to Boris Spassky, in which Spassky played the Kieseritzky Gambit, Fischer left in tears[citation needed] and promptly went to work at devising a new defense to the King's Gambit. In Fischer's 1961 article, "A Bust to the King's Gambit", he brashly claimed, "In my opinion the King's Gambit is busted. It loses by force."[5] Fischer concluded the article with the famously arrogant line, "Of course White can always play differently, in which case he merely loses differently. (Thank you, Weaver Adams!)"[6] The article became famous.[7][8]
Remarkably, Fischer later played the King's Gambit himself with great success,[9] including winning all three tournament games in which he played it.[10][11][12] However, he played the Bishop's Gambit (1.e4 e5 2.f4 exf4 3.Bc4) rather than the King's Knight Gambit (3.Nf3), the only line that he analyzed in his article."
http://en.wikipedia.org/wiki/King's_Gambit,_Fischer_Defense [wikipedia.org]
A Few Notes (Score:5, Informative)
Second, we are strictly speaking about the King's Gambit Accepted. That is, white begins with e4 (King's pawn forward two spaces), black replies classically with e5 (King's pawn up two spaces), white then gambits the f-pawn (King's bishop's pawn up two spaces), and black captures the f-pawn, accepting the gambit. As TFA mentions, the King's Gambit Declined has not been examined nearly as thoroughly.
Third, all of this is only somewhat relevant to actual chess playing, and only at the very highest levels of play; the average FIDE Master (i.e. a well above average tournament player, though nowhere near being among the 1,000 best players in the world) need not remove the King's Gambit from his repertoire because it has been "solved". This has, historically, been one of the most dynamic openings in chess, with tons of opportunities for tactical tomfoolery and psychological pressure. When we talk about "perfect play", or "near perfect play", we're already reaching beyond the level of world champions.
Fourth, while not every line has been thoroughly analysed, the ones that haven't are irrelevant. An advantage, in chess, is calculated on the basis of a difference of pawns. So, if the black player has all the same pieces as his opponent, save for an extra pawn, all other things being equal, we evaluate the position as -1 (i.e. from the perspective of white, the position is minus one pawn). Pieces other than pawns are weighed differently, even when we are solely looking at material differences. Traditionally, knights/bishops are said to be worth three pawns, rooks are worth five pawns, and the queen is worth nine pawns. However, the actual position of the pieces affects their worth; a knight very near the centre of the board is, often, worth more than a rook (i.e. A knight near the centre can have up to eight possible moves, whereas a knight in a corner can only have two possible moves). Thus, a position that has been evaluated as +/- 5.12 means that one player has more than a rook's worth of advantages over his opponent. Even in low level tournament play, it is very reasonable to assume that the advantaged player will win the game; at grandmaster level, this is so certain that it is considered impolite, even downright offensive, if the disadvantaged player refuses to resign.
Fifth, while different computer chess engines do evaluate positions differently, I have yet to come across a position about which the analyses of different engines have diverged by more than 2 pawns. An evaluation of +/- 5.12 by a top-notch engine can safely be assumed to be conclusive, since since most of what I said in the above paragraph also applies to an evaluation of +/- 3.0. Whatever else it may be, Rybka is certainly a top-notch engine.
Finally, it is true that Rybka's having reached its current strength relies on what are at best described as questionable appropriations of others' source code and algorithms. Nonetheless, the presented findings have an intrinsic value that is not dependent or reliant on notions of intellectual property or publicity. I am frankly ashamed by posters who have suggested that this article ought not have been publicized by slashdot because of its source. Knowledge is knowledge, period, and while it is both sensible and necessary to place ethical restrictions on scientific methodology, it is simply insane to deprive oneself and others of data that has, for better or worse, already been gathered.
Re:I'm not convinced by some of their statements. (Score:2, Informative)
As a tournament player and mathematician (3rd year): you're looking at this in a completely wrong way :)
Their methods looks ok, their conclusion on the King's Gambit looks ok, but I hold that chess is a deterministic but non-predictable system that is sensitive to initial conditions. ie: a chaotic system. All chaotic systems can be represented by relatively simple mathematical equations, even if "relatively simple" means "still very complicated" and/or "not known at this time".
Chess isn't really chaotic. In some situations, I'd wager a lot (really a lot) that one side can't do much but lose. These situations are rated with high scores (say... +/- 5).
Let's start easy with a soccer analogy: two good national teams playing, but 5 of one team must have their shoelaces tied together from a certain point on (roughly equivalent to a -5 score I'd claim). Your bet would be? Yes, there are a lot of possible freak incidents that would skew the expected outcome, but coming across that situation in practise, what would a reasonable estimation of this position be, when there's still ~30 minutes to play and the goal score is 0:0? (in chess, the goal score usually would already be in favour of the non-handicapped team)
Their reasoning that the system will tend to some ratio of wins:draws:losses very quickly is one I can see being true for many cases, though not necessarily always.
Not sure if I understand you correctly there, but we don't care about the wins:draws:losses. A one-sided (=forced) 1:x:y is enough for me to claim the win, no matter if x=y=1e500. Not-one-sided statistics have absolutely no significance at all unless one of the numbers is 0.
However, any that don't MUST (if my reasoning is correct) go into the only other valid state for a chaotic system, which is to oscillate.
Since any board position is a direct function of a previous board position, the ratio for any given non-ending board must be a function of all possible boards leading from it.
While you're right in that the boards positions are Markov chains, ergodicity is violated in two ways: first the various rules (loss of pieces, 3 repetitive positions, 50 moves rule, heck even pawns just moving forward) put a serious limit to the depth, and second and more importantly the "common sense" employed by human players hugely limits the variation width of possible moves.
I don't see how this could be modeled by a classical chaotic system. It's both discrete and finite in the time scale.
Yes, there surprising and unintuitive winning/saving moves are all over the place, but by far the biggest chunk of the search tree is senseless stuff "moving your king left and right while the enemy takes all your pieces one by one".
When two minor pieces ahead without positional compensation or initiative for the opponent (or tactical fireworks, easily checkable with Houdini, Rybka, ...), there is strong consensus that a skilled player would not lose, even without formal proof.
This is what the +X evaluation roughly implies: at this or that point in the game, the first team binds together the shoelaces of Y players of the second team, while the goal difference is Z (1:3 -> Z=-2) and the "team motivation/morale difference" is in some way quantified by W, thus X = Y+Z+W
Again, they use this same reasoning with their score method. I don't see it necessary to produce an actual score for a game board, though, since the score must be a consequence of the underlying set of chaotic functions that tie the score of one board to the score of all boards leading from it.
Assuming that the chaotic functions have some specific standard form, then you need only know enough scores for enough unrelated board positions to determine the values of all constants in those functions. For a linear equation, it's easy - you need one inequality per unknown to define the values of all un
Re:+ / - 5.12 is a lot of difference (Score:4, Informative)