Beta
×

Welcome to the Slashdot Beta site -- learn more here. Use the link in the footer or click here to return to the Classic version of Slashdot.

Thank you!

Before you choose to head back to the Classic look of the site, we'd appreciate it if you share your thoughts on the Beta; your feedback is what drives our ongoing development.

Beta is different and we value you taking the time to try it out. Please take a look at the changes we've made in Beta and  learn more about it. Thanks for reading, and for making the site better!

Rybka Solves the King's Gambit Chess Opening

Unknown Lamer posted about 2 years ago | from the big-blue-shall-crush-you dept.

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

cancel ×

206 comments

Sorry! There are no comments related to the filter you selected.

The extraordinary conclusions? Only one move! (5, Informative)

QuasiSteve (2042606) | about 2 years ago | (#39553431)

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

We now know the exact outcome of this position, assuming perfect play, of course. I know your next question, so I am going to pre-empt it: there is only one move that draws for White, and that is, somewhat surprisingly, 3.Be2. Every other move loses by force.

Anybody really interested in the details will still RTFA anyway and the rest of us won't be left hanging with a teaser.

Re:The extraordinary conclusions? Only one move! (4, Informative)

Anonymous Coward | about 2 years ago | (#39553535)

Also, it's a nonrigorous "proof":

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.

Re:The extraordinary conclusions? Only one move! (3, Insightful)

Anonymous Coward | about 2 years ago | (#39553797)

Evaluating something to a 99.9999999% confidence is non-rigorous? You should go tell the CERN guys that they're doing it wrong.

Re:The extraordinary conclusions? Only one move! (4, Funny)

marcosdumay (620877) | about 2 years ago | (#39553861)

For matematicians, yes it is.

Re:The extraordinary conclusions? Only one move! (1)

Yvan256 (722131) | about 2 years ago | (#39554055)

It doesn't seem to apply to english, however.

Re:The extraordinary conclusions? Only one move! (5, Funny)

Anonymous Coward | about 2 years ago | (#39554331)

He's talking about chess, so "matematicians" is correct here.

Re:The extraordinary conclusions? Only one move! (2)

HybridST (894157) | more than 2 years ago | (#39555321)

If it were for physicists rather than mathematicians the chess-pieces would be approximated by spheres and 6 sigma would be regarded as a theory having been proven. Mathematical proofs are "somewhat" more rigourous and a sigma rating at all would invalidate the proof.. This lies somewhere between those two extremes.

Re:The extraordinary conclusions? Only one move! (1)

Anonymous Coward | more than 2 years ago | (#39555339)

It doesn't seem to apply to english, however.

But this guy's Polish.

Re:The extraordinary conclusions? Only one move! (2, Insightful)

EvanED (569694) | about 2 years ago | (#39554925)

First off, yes, it's not a proof.

However, probabilistic does not mean nonrigorous, even to a mathematician.

Re:The extraordinary conclusions? Only one move! (1)

retchdog (1319261) | about 2 years ago | (#39555069)

it does if you don't define the sigma-algebra [wikipedia.org] and probability measure, which he didn't, because it would be pointless to try.

Re:The extraordinary conclusions? Only one move! (2)

martin-boundary (547041) | more than 2 years ago | (#39555911)

It's hard to know if you mean that statement technically or somewhat more generally. The Probabilistic Method [wikipedia.org] is rigorous because it is certain. There's no chance involved in the result, only in a highly technical sense during the proof.

It's certainly not like checking a few (or even a lot of) cases that all seem to work.

Re:The extraordinary conclusions? Only one move! (1)

Ohrion (814105) | about 2 years ago | (#39555083)

I see what you did there.

Re:The extraordinary conclusions? Only one move! (5, Informative)

blueg3 (192743) | about 2 years ago | (#39553927)

That's the difference between an experiment and a proof.

Re:The extraordinary conclusions? Only one move! (1)

Kjella (173770) | more than 2 years ago | (#39555943)

Yep, for example all evidence suggest that chess is either a draw or a win for white. However, there's no proof that black can't win. In theory, all of the 20 opening moves (8x2 pawn moves and 2x2 knight moves) could expose a subtle weakness in white's defense that black could use to force checkmate with perfect play. That's a 0.00000001% chance but until it's proven otherwise, it's still possible.

Re:The extraordinary conclusions? Only one move! (5, Insightful)

tobiah (308208) | about 2 years ago | (#39555021)

Rajlich analyzed a small subset of the ~10^100 possible continuations to the point that Rybka (Rajlich's chess program) showed a score of +/- 5.12, which he describes as "99.99999999% certain" of the outcome. Assigning percentages to scores like that is tricky, often impossible, so it's hard to say how accurate the statement is. I'm sure Rajlich didn't intend the statement to be interpreted strictly. But if we take it at face-value where there is a 1/10^10 chance a line might go the other way and 10^100 opportunities for that to happen, we don't need a fancy statistics degree to see that it is highly probable not all of those conclusions are accurate. This analysis of the King's gambit isn't anything like Appel and Haken's computer proof of the four color problem, which is exhaustive and grudgingly accepted by the mathematical community.

Re:The extraordinary conclusions? Only one move! (1)

retchdog (1319261) | more than 2 years ago | (#39556301)

the thing is, particles aren't out there to trick us (or so we've been thinking for the past few centuries, and there's no much reasonable doubt of this). their uncertainty is "known" (sort of), and as long as you sample with the right kind of distribution of starting configurations, you're fine.

however, in this case they are basically saying "whenever rybka thinks a branch is hard enough, there is no way to win at that branch, and we know there's no way to win because rybka can't win." well, uh, yeah.

i'm sure rybka is very strong and this guy is probably better than me at chess, mathematics, and programming, but this "proof" is, shall we say, a bit solipsistic.

All lines...? (5, Informative)

Anonymous Coward | about 2 years ago | (#39553435)

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

Re:All lines...? (0)

Anonymous Coward | about 2 years ago | (#39553601)

It doesn't seem to be a bad assumption though, as it seems akin to saying that (for instance) particle physicists determining that a particle exists given a 99.999999% probability is an assumption.

Re:All lines...? (1)

Anonymous Coward | about 2 years ago | (#39553605)

So this means that the result is not 100% certain, it is just a hypothesis.

That is technically correct, similar to the assertion that a position where one side is more than two pieces down, without any compensation, is considered lost, even if you cannot calculate it to a forced mate against any defence. Sure, there theoretically might be a way to save the game, but if Rybka is displaying +5.12 or more the outcome is 99.99999999% secure. That is approximately the confidence number we give to our King's Gambit results: 99.99999999%. It might be that there is a flaw somewhere, but if there is it will not be discovered in the course of this universe – that would require more computational power than could ever be provided. And of course it is possible, and in fact very, very likely, that there is no flaw.

The interviewer beat you to it.

+ / - 5.12 is a lot of difference (5, Informative)

Lonewolf666 (259450) | about 2 years ago | (#39553725)

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:+ / - 5.12 is a lot of difference (3, Insightful)

john83 (923470) | about 2 years ago | (#39553943)

The score is about equivalent to being a rook down without compensation. Even strong club players could beat computers from such positions. Of course, what it really hinges on is Rybka's ability to evaluate the notion of compensation, but I can believe that the percentage of positions Rybka evaluates at -5.12 or worse in which there exists a win for the 'weaker' side is very small. So, yes, not a proof, but a strong practical indicator.

Re:+ / - 5.12 is a lot of difference (0)

Hentes (2461350) | about 2 years ago | (#39554271)

Well I can imagine positions where one player can win without a rook, in fact chess puzzles are full of scenarios like that. I'm not saying they appear often in a real game, but their mere existence means that there are problems with this assumption.

Re:+ / - 5.12 is a lot of difference (1)

Anonymous Coward | about 2 years ago | (#39554361)

They are not just counting pieces on the board. Position is also factored in. In those problems, the side without the rook would likely be scored as having a big advantage due to position.

+ / - 5.12 is not enough (1, Insightful)

frank_adrian314159 (469671) | about 2 years ago | (#39554551)

Let's assume that White is down by 5+ points in evaluation. Even in this case, Black may still want to force perpetual check (e.g., because not doing so would lead to a forced line where he might lose even more points further down the line) or White may still be able to force stalemate. You cannot assume that just because an intermediate search tree node in the game search has an arbitrary value (other than specifically a win, loss, or draw), that the tree below it can be pruned. You can limit the issues by ensuring that the position is quiescent before the evaluation is pruned, but even then there may be resources further down the tree. This research is deeply flawed.

That being said, the King's Gambit is still probably a highly dubious opening for White.

Re:+ / - 5.12 is not enough (0)

Anonymous Coward | more than 2 years ago | (#39556061)

Being both tedious and stupid, Twitter is the perfect communications medium for the modern corporation.

Obviously, you've never heard of yammer. Even more tedious, and more stupid, and therefore much better for the modern corporation.

Re:All lines...? (2)

AshtangiMan (684031) | about 2 years ago | (#39553863)

The bigger assumption is where they "assume proper play". I can tell you that when I play Kings Gambit against various opponents, I win more than I lose.

Re:All lines...? (3, Insightful)

jfengel (409917) | about 2 years ago | (#39554467)

This is just telling you that you'd lose against Rybka. But then, unless you're a top grandmaster having a good day, you already knew that. Even then, if you decided to play King's Gambit, Rybka's letting you know in advance that you are not having a good day.

Re:All lines...? (1)

TheCarp (96830) | more than 2 years ago | (#39555519)

Well... More accurately Rybka has, most probably, already beaten you. Unless you allow it to use the entire result tree as an "opening book", then it still needs to calculate each move... meaning it needs those 2800 cores plus support cluster... well... assuming you are a top grandmaster having a good day, that is.

Re:All lines...? (2)

Kjella (173770) | more than 2 years ago | (#39555893)

This is just telling you that you'd lose against Rybka. But then, unless you're a top grandmaster having a good day, you already knew that.

They lose too and hardly anyone bothers anymore because it's like asking whether a human or a dragster would win the 100m dash. Even a mobile phone plays at a grandmaster level these days, with a regular desktop humans would occasionally make a draw and if you made a dedicated supercomputer again like Deep Blue they'd lose every game. The last recorded human win without handicap I could find was back in 2004 when Karjakin beat Deep Junior. Everyone would know the competition would be like "if we just let the dragster fire on one cylinder and drag a 100kg rock after it, it'll be an even match".

Re:All lines...? (1)

Anonymous Coward | about 2 years ago | (#39553923)

This may pose another interesting problem: Find a wining position that is evaluated at minus 5.12 or less.

Re:All lines...? (0)

Anonymous Coward | about 2 years ago | (#39554889)

Not that interesting I'm afraid, there are gazillions.

Re:All lines...? (0)

Anonymous Coward | more than 2 years ago | (#39556123)

But are there really? Is that a known fact? Because if it is, it seriously weakens Mr. Rajlich's argument.

Re:All lines...? (0)

Anonymous Coward | more than 2 years ago | (#39556183)

Oh, ok, never mind, I've looked into position evaluation and indeed, it is trivial to build wining positions evaluated at very low scores. Of course, they are all very pathological positions. I'm unsure of what to think of his cutoff at 5.12 though.

Re:All lines...? (0)

MaskedSlacker (911878) | more than 2 years ago | (#39556243)

Depends on how the algorithm evaluates position. It's trivial to find positions at more than -6 in piece value that are one move from check mate.

Re:All lines...? (1)

osu-neko (2604) | about 2 years ago | (#39554045)

It's more "proof" in the scientific sense than the mathematical one. Over five sigma... that sort of thing.

fake (1)

DrD8m (307736) | about 2 years ago | (#39553461)

April's fool day!

Re:fake (2, Funny)

Anonymous Coward | about 2 years ago | (#39553501)

You're right... that can't possible be that guy's wife. ;-)

Re:fake (1)

digitig (1056110) | about 2 years ago | (#39553859)

You'd think -- but then, she is a chess geek, and he's probably pretty wealthy by Eastern European standards.

Re:fake (0)

Anonymous Coward | more than 2 years ago | (#39556327)

Yes, for any chess player it is obvious, from statements about how Be2 white can hold a draw regardless what black does. It is a passive move in a very attacking opening. To hold a draw as white is a joke. In (advanced level) chess black is trying to draw and white is trying to win.

So NO. Chess is still unsolved as long as there are more than 7-8 pieces on the board.

Just stop playing chess, play go (5, Insightful)

tp1024 (2409684) | about 2 years ago | (#39553475)

... so long as you still have a chance. The computers haven't reached professional level yet and certainly won't be able to compute the whole of the game in advance, even after a given opening, in the next decades.

Re:Just stop playing chess, play go (0)

Anonymous Coward | about 2 years ago | (#39553549)

Nonsense, we'll repurpose some of the NSA's machines to help us crack it. We can't allow for a strategy game gap between us and China, just like how we developed DeepBlue to defeat that notorious Soviet Comrade Kasparov.

Re:Just stop playing chess, play go (1)

Hentes (2461350) | about 2 years ago | (#39553717)

Or Fischer chess [wikipedia.org] .

Re:Just stop playing chess, play go (1)

million_monkeys (2480792) | about 2 years ago | (#39553807)

Or Fischer chess [wikipedia.org] .

From that page:

In 2005, chess program The Baron played two Chess960 games against Chess960 World Champion Peter Svidler; Svidler won 1½–½. The chess program Shredder, developed by Stefan Meyer-Kahlen of Germany, played two games against Zoltán Almási from Hungary; Shredder won 2–0.

Seems Fischer chess isn't going to save you from computer dominance.

Re:Just stop playing chess, play go (0)

Anonymous Coward | more than 2 years ago | (#39556233)

I agree with you, but the computers ARE up to professional levels, like around 4-5 dan I think. Also this article http://spectrum.ieee.org/computing/software/cracking-go

A probabilistic algorithm (5, Informative)

Hentes (2461350) | about 2 years ago | (#39553511)

They didn't calculate all possible moves, but skipped every branch where analysation showed an advantage high enough for one party to be "absolutely sure" to win. So while the algorithm is very sophisticated, it technically didn't solve King's Gambit.

Re:A probabilistic algorithm (-1, Redundant)

Volante3192 (953645) | about 2 years ago | (#39553699)

Technically particle physicists never see subatomic particles, they just see the results from collisions and work backward.

What's the difference?

Re:A probabilistic algorithm (3, Funny)

brian_tanner (1022773) | about 2 years ago | (#39553775)

The difference is that solve in this context is not a general English word but rather a specific and well defined term. I'm pretty sure the technical meaning of "solving" a game or position within a game requires a proof. The meaning of proof is somewhat stronger than overwhelming evidence. We are pretty sure P!=NP, but we don't have a proof. You cannot publish a paper or write a thesis that says "I'm pretty sure P!=NP".

Note: I'm not saying this work is uninteresting, just that those pointing out that solve is being used incorrectly are justified.

Re:A probabilistic algorithm (3, Informative)

EvanED (569694) | about 2 years ago | (#39553831)

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:A probabilistic algorithm (1)

brian_tanner (1022773) | about 2 years ago | (#39553947)

For sure! That's why I was sure to make the point about there being value in the work. Again I wanted to say a few words about how "solving" is different from "making a very convincing argument about".

Re:A probabilistic algorithm (1)

EvanED (569694) | about 2 years ago | (#39554373)

You also said 'You cannot publish a paper or write a thesis that says "I'm pretty sure P!=NP",' which isn't an even remotely good charactization of this.

You certainly could publish a paper, for instance, that showed that P != NP with 99.999999% probability.

Re:A probabilistic algorithm (1)

brian_tanner (1022773) | more than 2 years ago | (#39555421)

I think that paper would not get accepted. A probabilistic statement would indicate there is a random aspect that determines the outcome. Reviewers would probably ask what is the random event that would determine if P does or does not equal NP.

Re:A probabilistic algorithm (1)

adavies42 (746183) | about 2 years ago | (#39554419)

perhaps a couple examples are in order:

tic-tac-toe: solved (on paper, by bright grade-schoolers everywhere)
checkers: weakly solved (from the standard start, assuming perfect play)

Re:A probabilistic algorithm (4, Funny)

tincho_uy (566438) | about 2 years ago | (#39554095)

Re:A probabilistic algorithm (1)

Jorl17 (1716772) | about 2 years ago | (#39554765)

That is AMAZING! I couldn't top laughing! I seriously hope that *was* meant as a joke.

Re:A probabilistic algorithm (0)

Volante3192 (953645) | about 2 years ago | (#39554111)

Ahh, a "theory (scientific) vs theory (layman)" debate.

But, then again, particle physics simply 'requires' 5 sigma of confidence (7 9s I believe?). I can't say whether Rybka's confidence is that good or not, but let's assume for the sake of argument, it is. Would the use of 'solve' still require quotes in that case? If it does, would you require every paper on quarks to be equally asterisked?

Re:A probabilistic algorithm (2, Insightful)

brian_tanner (1022773) | about 2 years ago | (#39554223)

I'm definitely not making the confusion you think I am. I have studied Computer Science at the PhD level at the University of Alberta, which I believe has the strongest games research group in the world. I will admit to not being an expert in games myself, but I am quite confident that when people in this area say solved, it means something specific, something stronger than "obviously true to everyone in the world". It requires proof in the rigorous, mathematical/algorithmic sense. I'm pretty sure, anyway.

Re:A probabilistic algorithm (0)

Anonymous Coward | more than 2 years ago | (#39555879)

You cannot publish a paper or write a thesis that says "I'm pretty sure P!=NP".

Doesn't pretty much every paper on cryptography basically start with exactly that statement?

Re:A probabilistic algorithm (1)

brian_tanner (1022773) | more than 2 years ago | (#39555913)

Sorry. You cannot publish a paper whose conclusion is "I'm pretty sure P!=NP". This is different from assuming it's true in order to make other statements, such as, "assuming P!=NP, my cool new crypto method has features people would care to have."

Re:A probabilistic algorithm (1)

marcosdumay (620877) | about 2 years ago | (#39553917)

The difference is that physicists do physics research, where some words like "proof" and "solve" have different meanings from mathematical research.

Re:A probabilistic algorithm (1)

Hentes (2461350) | about 2 years ago | (#39554193)

You mean what's the difference between math and science? Mathematical truths are known for sure, scientific models are just approximations based on experiments and may or may not hold up under a certain set of specific conditions.

the Lesser Bishop's Gambit or Tartakower Gambit (0)

Anonymous Coward | about 2 years ago | (#39553527)

There is only one move that draws for White, and that is, somewhat surprisingly, 3.Be2. Every other move loses by force.
Hate it when the summary leaves you wondering, just like every level you achieve in Scientology (unless you commit the High Crime of reading entheta on the internet)

Rybka was made by plagiarizing a GPL program. (5, Interesting)

Anonymous Coward | about 2 years ago | (#39553533)

Rybka was stripped of its world computer chess championship after it was found that the author plagiarized the chess engines fruit (free software, GPL, the current base of GNUchess) and crafty (opensource). Even so, chessbase keeps selling this stolen engine.

Slashdot ought to be ashamed to give publicity to cheats and thieves.

Re:Rybka was made by plagiarizing a GPL program. (5, Funny)

Anonymous Coward | about 2 years ago | (#39553689)

...the author plagiarized...chessbase keeps selling this stolen engine.... Slashdot ought to be ashamed to give publicity to cheats and thieves.

Oh, but didn't you know "you can't steal information"?

Re:Rybka was made by plagiarizing a GPL program. (0)

Anonymous Coward | about 2 years ago | (#39554567)

All downstream users are deprived of the sourcecode they would otherwise have. This ain't making a copy of a publically available piece of information.

Re:Rybka was made by plagiarizing a GPL program. (1, Informative)

Fned (43219) | about 2 years ago | (#39554627)

Plagarism isn't theft, dumbfuck. It's fraud.

Re:Rybka was made by plagiarizing a GPL program. (0)

Anonymous Coward | about 2 years ago | (#39554049)

Information wants to be free, dude. Piracy isn't stealing. If they have a problem with it, their business model is outdated.

Re:Rybka was made by plagiarizing a GPL program. (4, Informative)

Anonymous Coward | about 2 years ago | (#39554833)

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:Rybka was made by plagiarizing a GPL program. (0)

Anonymous Coward | more than 2 years ago | (#39555309)

There's also the whole accusing Strelka of being a clone of Rybka even though it appears to be an admitted modification of Fruit.

Re:Rybka was made by plagiarizing a GPL program. (5, Funny)

kamapuaa (555446) | about 2 years ago | (#39555003)

If you read Slashdot, you know that stealing is OK, because
1) It costs more than is reasonable
2) You disagree with their license or copy protection scheme
3) The MPAA/RIAA are a bunch of jerks
4) You promise you will support the artist directly by some kind of donation or going to their show or referring your friends
5) It's a try before you buy situation, and you'll pay later if you like the program
6) Stealing software doesn't deprive others of the product

Re:Rybka was made by plagiarizing a GPL program. (0)

postbigbang (761081) | more than 2 years ago | (#39556133)

Who peed in Your beer? There's a large community of /. users that aren't thieves. More of us still believe that the MPAA/RIAA have the IQ of a box of rocks, and the morals of a politician.

Lots of pay for what we use, and we still hack, disassemble, reverse engineer, and concoct our own stuff, slip in free code, and have a merry time of it. Don't cast everyone by your edicts. We're all different. You hear lots of interesting signal, and lots of noise. Learn the difference.

Re:Rybka was made by plagiarizing a GPL program. (0)

Anonymous Coward | more than 2 years ago | (#39555443)

It's still the best engine in the world. Its creator was dishonest in not crediting the FOSS engines that he used as a launching point, but that doesn't change the absolute fact that Rybka is the strongest chess engine ever created. If Rybka says "white only has one move to force a draw after 1.e4 e5 2.f4 exf4", then that statement is interesting and likely to be correct, regardless of the personal failings of Rybka's creator.

The fact that Hans Reiser killed his wife doesn't make his file system any less reliable.

Re:Rybka was made by plagiarizing a GPL program. (1)

Anonymous Coward | more than 2 years ago | (#39555645)

Houdini dethroned rybka a while ago. And Robbolito/Ippolito were better than rybka even before that but weren't included in any ranking list because the creator of rybka claimed that they were clones of rybka.

Re:Rybka was made by plagiarizing a GPL program. (1)

Anonymous Coward | more than 2 years ago | (#39555853)

Fine. "One of" the best then. Doesn't matter. Does anyone dispute the accuracy of its calculations? The OP is essentially using an ad hominem attack against a computer program. People in this cluster of posts are literally claiming that Slashdot should not publish mathematical facts because we don't like the person who found them.

Re:Rybka was made by plagiarizing a GPL program. (0)

Anonymous Coward | more than 2 years ago | (#39555871)

If you think those are "mathematical facts" then you don't know much about mathematics.

"There's always a BIGGER FISH" - Qui-gon Jinn (-1)

Anonymous Coward | more than 2 years ago | (#39555859)

Even if it's a baby fish ("Rybka", in Polish &/or Russian, means "little fish") that ate up the "bigger older fish" you speak of then.

APK

P.S.=> I am assuming you have some proof/documentation of what you speak of, can you produce it? It'd lend a LOT more credence to your words, and in my eyes, believability (sorry - it's just what this site's made me like is all - ala "the show me state" of Missouri is all, but I am genuinely interested as well) - thanks!... apk

One question. (2, Funny)

Anonymous Coward | about 2 years ago | (#39553543)

Can I still move the horsie?

Gotard already posted? (0)

Anonymous Coward | about 2 years ago | (#39553627)

Dang, I'm late. Someone piped up about Go already.

Solved from Black's point of view (4, Interesting)

jfengel (409917) | about 2 years ago | (#39553819)

Right on the surface, the King's Gambit doesn't look like a very good idea for white, throwing away a well-placed pawn on your second move. Apparently this was considered a good idea for a long time, though I (a mediocre-at-best player) don't see how it could work.

As white, the only advice you need from this study is "Don't do it." As black, the advice appears to be "Take the pawn if offered. The best they can do at that point is a draw, and if they differ from that line at all, they lose."

Assuming you're a great player, of course. I'm sure that I'd still get massacred if a real player were to play the King's Gambit against me.

Re:Solved from Black's point of view (1)

AshtangiMan (684031) | about 2 years ago | (#39553909)

Yes. Technically this is Kings Gambit Accepted. I don't remember where I got this, but it is stated that black should always accept the gambits.

Re:Solved from Black's point of view (3, Informative)

ed1park (100777) | more than 2 years ago | (#39555639)

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]

Re:Solved from Black's point of view (2)

Kjella (173770) | more than 2 years ago | (#39555675)

Apparently this was considered a good idea for a long time, though I (a mediocre-at-best player) don't see how it could work.

For a long time declining a gambit was not considered very good sportsmanship, if the opponent offered you to go on a roller coaster ride you were supposed to take it. Go through The Immortal Game [wikipedia.org] and see what they considered a masterpiece in 1851. Oh and as relevant to the story - it's King's Gambit Accepted and won by white.

I'm more of a Ruy Lopez guy.... (1, Insightful)

mark-t (151149) | about 2 years ago | (#39553841)

I don't think I've ever played the king's gambit opening, at least not while I'm playing white. I don't care for how open it leaves my kingside bank ranks before they are defended.

Re:I'm more of a Ruy Lopez guy.... (0)

Anonymous Coward | about 2 years ago | (#39555103)

The King's Gambin has been considered a rather dubious opening for decades. It just happens to be the 'simplest' of modern day openings, as it is so aggressive. A similar computation of the Ruy Lopez would be orders of magnitude slower.

Re:I'm more of a Ruy Lopez guy.... (0)

Anonymous Coward | more than 2 years ago | (#39555579)

I am personally simultaneously relieved and SHOCKED to know that if White makes a second move that compromises their kingisde and pawn structure and leaves Black with an advantageous position, that in the long-run, White is in a hole that requires "perfect play" to draw.

(Computational) SCIENCE!

Fools (0)

negrace (984807) | about 2 years ago | (#39554171)

come on, this one is an obvious April 1 joke. By the way, this guy is a thief. He violated GPL because Rybka is based on a GPL program Fruit.

A thief? (0, Insightful)

Anonymous Coward | about 2 years ago | (#39555055)

I thought copyright infringement wasn't theft?

I'm not convinced by some of their statements. (1)

jd (1658) | about 2 years ago | (#39554185)

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

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. 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. 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 unknowns. Chaotic systems aren't nearly so nice, but there will still be a finite number of inequalities to determine every unknown.

So? Chaos forbids you from knowing the outcome for a specific system without iterating through it.

True, but it does not prohibit you from classifying it. For a given point on the Mandelbrot Set, for example, you can say what the probability of escaping vs. not escaping is, and you can say that the probability of a specific escape velocity is, even though you CANNOT say what that point will actually do in practice. A minor variant on the scoring system in the article, nothing more, based on exactly the same reasoning.

The classifications will also follow a chaotic system (just as the Julia Set does for each position in the Mandelbrot Set).

This is the system that interests me. If you can solve the unknowns for the classification system of equations, then you can have a perfect board evaluation function. If you have that, then you need look only one move ahead and know that the move you make is the best possible move from that position, even though because this is a chaotic function of a chaotic function, you do NOT know why it is the best possible move or how the game will play out.

Re:I'm not convinced by some of their statements. (1)

Anonymous Coward | about 2 years ago | (#39554349)

If that post made sense to me, am I schizophrenic ?

Re:I'm not convinced by some of their statements. (1, Funny)

jd (1658) | about 2 years ago | (#39554495)

Only half of your personalities need to be.

Re:I'm not convinced by some of their statements. (1)

Anonymous Coward | about 2 years ago | (#39554875)

Schizophrenia does not imply split personalities.

Re:I'm not convinced by some of their statements. (0)

Anonymous Coward | more than 2 years ago | (#39555177)

chess is .. sensitive to initial conditions.

Is there variation among those initial conditions? I think the premise of this entire analysis is that he's looking at one exact set of initial conditions.

Re:I'm not convinced by some of their statements. (1)

jd (1658) | more than 2 years ago | (#39555649)

"Initial conditions" in mathematics refers to when you start analyzing the system, not to when the system starts to exist. Since each board position is a fresh calculation, each board position is an initial condition. So although the first board is common, he's not really looking at only one initial condition. Yes, I know, mathspeak isn't intuitive and is often contrary to "common usage", but there ya go.

Re:I'm not convinced by some of their statements. (2, Informative)

Anonymous Coward | more than 2 years ago | (#39556153)

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 unknowns. Chaotic systems aren't nearly so nice, but there will still be a finite number of inequalities to determine every unknown.

The score is neither determined by knowing what happens far after (i.e. the ending), nor by using statistics on uncorrelated. That's not a widely used model (possibly not used at all).

Here comes the shocker: the score is determined heuristically by weighting "positional landmarks", "space advantage", etc and combining it with tactical "spearfishing". Similar to that silly X=Y+Z+W calculation above. And it works. They tested it extensively with full tree calculations and consistently failed to produce any kind of indication of a flaw.

So? Chaos forbids you from knowing the outcome for a specific system without iterating through it.

True, but it does not prohibit you from classifying it. For a given point on the Mandelbrot Set, for example, you can say what the probability of escaping vs. not escaping is, and you can say that the probability of a specific escape velocity is, even though you CANNOT say what that point will actually do in practice.

Well, there's your problem. In chess, it is widely believed that you can. Because the models currently employed are way nearer to the soccer example than to a Mandelbrot instance. A position trait (for example central dominance, or wing initiative) doesn't suddenly change in unforseen ways (OK, for novice players it probably does). And while closed positions can be opened, attack paths shifted etc. you don't really get something completely different from what you had before.

Just for illustration and laughs: gravity also hasn't been proven starting from the Peano axioms, yet it still enjoys quite an undisputed status of existence ;)

A minor variant on the scoring system in the article, nothing more, based on exactly the same reasoning.

The classifications will also follow a chaotic system (just as the Julia Set does for each position in the Mandelbrot Set).

This is the system that interests me. If you can solve the unknowns for the classification system of equations, then you can have a perfect board evaluation function. If you have that, then you need look only one move ahead and know that the move you make is the best possible move from that position, even though because this is a chaotic function of a chaotic function, you do NOT know why it is the best possible move or how the game will play out.

Now while that would be awesome, it's completely unlikely anything that has been tried in chess algorithmics that I'm aware of. And I'm afraid I don't see how the whole way of thinking could be shoehorned into a concept let alone implementation... but if you do, by all means do it and earn your well deserved millions ;)

I can't seem to find the article... (0)

Anonymous Coward | about 2 years ago | (#39554275)

All that keeps coming up is the guy's personal face-shot gallery.... oh wait...

What that article needs... (0)

Anonymous Coward | about 2 years ago | (#39554441)

What that article needs is more photos of him, maybe a few of him staring out into the distance, or looking deeply pensive like he is solving some impossible conundrum.

this word 'exhaustively'... (1)

Anonymous Coward | about 2 years ago | (#39554867)

this word 'exhaustively,' I don't think it means what you think it means.

The update is innacurate. (0)

Anonymous Coward | more than 2 years ago | (#39555733)

Rybka plagiarized crafty in its earlier versions and fruit in its later versions. Up to version 2.1 fruit was GPL2 and later versions were released under a commercial license for some time. In 2011 GNU Chess released version 6 which is based on fruit 2.1. Previous versions of GNU Chess are not based on fruit and are much weaker. Rybka never plagiarized GNU Chess because it wasn't strong enough to bother.

A Few Notes (5, Informative)

routerl (976394) | more than 2 years ago | (#39555959)

First, the King's Gambit has not technically been "solved", for the most rigorous definition of "solved". Unlike, say, checkers, there are still lines (i.e. series of moves) within the King's Gambit that have not formally been examined.

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:A Few Notes (2)

rpresser (610529) | more than 2 years ago | (#39556309)

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.

If chess is so hard that WORLD CHAMPIONS frequently and regularly make dumb moves -- yes, that's what not playing perfectly is defined as -- then why should it attract any interest as a discipline at all? It's like wheelchair ballet.

As a GAME -- an opportunity for excitement, aggression, a way to humiliate your opponent -- sure, it makes sense to play chess. But so does poker. As a mathematical discipline -- we're outclassed as a species. We have no business studying chess anymore.

Load More Comments
Slashdot Login

Need an Account?

Forgot your password?

Submission Text Formatting Tips

We support a small subset of HTML, namely these tags:

  • b
  • i
  • p
  • br
  • a
  • ol
  • ul
  • li
  • dl
  • dt
  • dd
  • em
  • strong
  • tt
  • blockquote
  • div
  • quote
  • ecode

"ecode" can be used for code snippets, for example:

<ecode>    while(1) { do_something(); } </ecode>