Author |
Topic: King's Gambit chess opening claimed as solved (Read 29418 times) |
|
rbarreira
Forum Guru
Arimaa player #1621
Gender: 
Posts: 605
|
 |
King's Gambit chess opening claimed as solved
« on: Apr 2nd, 2012, 9:21am » |
 Quote  Modify
|
http://chessbase.com/newsdetail.asp?newsid=8047
Vasik Rajlich (the author of Rybka) claims to have solved the King's Gambit opening with very high certainty (99.99999999%). 1227 CPU-core-years of computations were used.
In order to tackle the enormous amount of possible continuations, the key simplifying assumption that was used is that when Rybka evaluates a position as having a score greater than 5.12, the position is really solved.
Quote:| 1.e4 e5 2.f4 exf4. 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. |
|
It was published on April 2 and not April 1 btw.
|
| « Last Edit: Apr 2nd, 2012, 9:27am by rbarreira » |
 IP Logged |
|
|
|
Adanac
Forum Guru
Arimaa player #892
Gender:
Posts: 635
|
|
Re: King's Gambit chess opening claimed as solved
« Reply #1 on: Apr 2nd, 2012, 9:46am » |
Quote Modify
|
on Apr 2nd, 2012, 9:21am, rbarreira wrote:http://chessbase.com/newsdetail.asp?newsid=8047
Vasik Rajlich (the author of Rybka) claims to have solved the King's Gambit opening with very high certainty (99.99999999%). 1227 CPU-core-years of computations were used.
In order to tackle the enormous amount of possible continuations, the key simplifying assumption that was used is that when Rybka evaluates a position as having a score greater than 5.12, the position is really solved.
It was published on April 2 and not April 1 btw. |
|
This whole story is incredible. I'm extremely surprised that it's already possible to solve an entire branch of opening theory. Not just one branch of the King's Gambit, but the entire opening!!
It's amazing that we'll soon have a perfect online database of the opening. For example, someone could play the King's Gambit in a live tournament and then, if White wins, the players could determine the precise losing move(s) in the post-mortem. Unfortunately, it will completely destroy the opening in Correspondence Chess. Since consulting opening databases is perfectly legal, anyone can win by force against every move except 3. Be2! On the bright side, that counter-intuitive move will now receive a whole lot more attention than it ever has before 
Next they're going to study the Sicilian Najdorf Bg5. Another of my favourite openings  I guess I'll play it frequently before they publish those results in 2020 or whenever it will be.
|
|
IP Logged |
|
|
|
rbarreira
Forum Guru
Arimaa player #1621
Gender:
Posts: 605
|
|
Re: King's Gambit chess opening claimed as solved
« Reply #2 on: Apr 2nd, 2012, 10:53am » |
Quote Modify
|
Still wondering if this is not a delayed April Fool's joke, which would be pretty lame...
|
|
IP Logged |
|
|
|
omar
Forum Guru
Arimaa player #2
Gender:
Posts: 1003
|
|
Re: King's Gambit chess opening claimed as solved
« Reply #3 on: Apr 2nd, 2012, 11:31am » |
Quote Modify
|
Very interesting. 2,880 cores at 4.25 GHz gives about 12.24 THz. If someone develops an application to work on chess using contributed resourses over the internet, chess might be solved within 20 years. Currently people are contributing about 10 Thash/s to bitcoin. With each hash requiring about 1000 Hz, that 10 PHz. So the King's Gambit could have been solved 1000 times faster if people threw the same compute resources to solving chess as they are to mining bitcoin. That's scary.
|
|
IP Logged |
|
|
|
omar
Forum Guru
Arimaa player #2
Gender:
Posts: 1003
|
|
Re: King's Gambit chess opening claimed as solved
« Reply #4 on: Apr 2nd, 2012, 11:42am » |
Quote Modify
|
Yes, sounds like it is a joke.
"On March 31 the author of the Rybka program, Vasik Rajlich, and his family moved from Warsaw, Poland to a new appartment in Budapest, Hungary. The next day... Vas, kindly agreed to the following interview".
http://rybkaforum.net/cgi-bin/rybkaforum/topic_show.pl?tid=24667
|
|
IP Logged |
|
|
|
Fritzlein
Forum Guru
Arimaa player #706
Gender:
Posts: 5928
|
|
Re: King's Gambit chess opening claimed as solved
« Reply #5 on: Apr 2nd, 2012, 11:48am » |
Quote Modify
|
This is mind-blowing in a couple of ways. First, because I would intuit that even in a sharp position like the King's Gambit, the space of draws is such a large proportion of the whole space that you couldn't prove anything to be a draw. (Maybe I am misunderstanding, but isn't it generally easier to prove that a won position is won than to prove that a drawn position is drawn?).
Secondly, the specific conclusions in terms of chess moves are mind-blowing. The opening is a draw, but there is only one move 3 for white that draws? 3. Nf3 is a loss, but there is only one move 3 for black that wins, and in Fischer's line, only one move 4 and only one move 5 as well??
I was taught to believe that one could play chess with good general strategic principles, and that only a minority of moves are tactically forced. Apparently exhaustive analysis gives the lie to this opinion: a move with a good idea strategic idea behind it can be flat out wrong, even if the move doesn't lose material or allow mate or anything concrete in the near future. Exhaustive analysis makes chess 100% tactics.
I have read many versions of the opinion that computers haven't ruined chess, but in my opinion chess is at best becoming an increasingly unsuitable battleground for World Championship competitions.
|
|
IP Logged |
|
|
|
Fritzlein
Forum Guru
Arimaa player #706
Gender:
Posts: 5928
|
|
Re: King's Gambit chess opening claimed as solved
« Reply #6 on: Apr 2nd, 2012, 11:51am » |
Quote Modify
|
Oh, thanks for the second link, Omar. This is the best April Fool's joke I have seen in ages. I fell for it hook, line, and sinker!
|
|
IP Logged |
|
|
|
rbarreira
Forum Guru
Arimaa player #1621
Gender:
Posts: 605
|
|
Re: King's Gambit chess opening claimed as solved
« Reply #7 on: Apr 2nd, 2012, 12:58pm » |
Quote Modify
|
on Apr 2nd, 2012, 11:51am, Fritzlein wrote:| Oh, thanks for the second link, Omar. This is the best April Fool's joke I have seen in ages. I fell for it hook, line, and sinker! |
|
I agree that it's quite cleverly written if it's a joke, but since it came out on the 2nd of April it would have to be classified as a hoax and not an April Fools' joke.
|
|
IP Logged |
|
|
|
Adanac
Forum Guru
Arimaa player #892
Gender:
Posts: 635
|
|
Re: King's Gambit chess opening claimed as solved
« Reply #8 on: Apr 2nd, 2012, 2:09pm » |
Quote Modify
|
on Apr 2nd, 2012, 12:58pm, rbarreira wrote:
I agree that it's quite cleverly written if it's a joke, but since it came out on the 2nd of April it would have to be classified as a hoax and not an April Fools' joke. |
|
I guess they have to release it on April 2nd now to avoid making people suspicious. I read it over twice to look for sarcasm or some other giveaway sign but it was so well written that I decided it must be true. 
That would have been quite a bombshell though!! Alright, I don't have to play 3. Be2 now 
|
|
IP Logged |
|
|
|
The_Jeh
Forum Guru
Arimaa player #634
Gender:
Posts: 460
|
|
Re: King's Gambit chess opening claimed as solved
« Reply #9 on: Apr 2nd, 2012, 2:45pm » |
Quote Modify
|
I should know this by now, so please forgive me, but not examining a position any deeper after a 5.12 advantage... Don't standard computer searches do something similar now? So this would be no different than letting your home computer analyze a position for 1227 years, after which the second-best move evaluates to worse than -5.12. That would be surprising enough in the King's Gambit, but you certainly couldn't show that some move is definitely a draw.
|
| « Last Edit: Apr 2nd, 2012, 2:48pm by The_Jeh » |
IP Logged |
|
|
|
Katsunami
Forum Senior Member
Gender:
Posts: 29
|
|
Re: King's Gambit chess opening claimed as solved
« Reply #10 on: Apr 6th, 2012, 7:52pm » |
Quote Modify
|
If this is a hoax, or an April 1st fool's joke, then it's a very good one. I did believe the article when I first read it a few days ago.
on Apr 2nd, 2012, 11:48am, Fritzlein wrote:
I have read many versions of the opinion that computers haven't ruined chess, but in my opinion chess is at best becoming an increasingly unsuitable battleground for World Championship competitions. |
|
In my honest opinion, the computer did ruin chess, just like it ruined draughts and checkers. Those games were basically solved around 1994, using the Chinook program.
Even the presumably greatest draughts player of all time (Dr. Marion Tinsley) was unable to defeat this program as of 1994. He only lost 7 games, 2 of which were to the Chinook computer in the 1992 match, which he did win. (Wikipedia) And that was in 1994... imagine a parallellized version of Chinook, with even more checkers knowledge than it had at that time, running on today's hardware. It would be virtually unbeatable.
In fact, even current-day chess programs on current hardware seem to be almost unbeatable for players under 2700 ELO; search with Google, and you'll find some references of chess programs winning games against >2600+ ELO players while giving material and/or move odds.
I own a DGT electronic chess board, and several versions of Fritz; my newest is Fritz 11. It comes with an opening book that extends *up to 35 moves* for for many of the most-played openings. Fritz can also handle endgame tablebases.
When playing a well known opening in such a way that Fritz can stay "in book", I've seen it happen that the program can switch to the endgame tablebase before move 50... effectively only playing around 15 moves by itself.
I am quite sure that the opening books and endgame tablebases will become bigger until they meet. If you don't follow the opening book, then most probably your moves are not the best, and the program will clobber you. If you do follow the book, the best you can hope for is a draw, if you play the endgame perfectly; the program will never let you get into an endgame of which the tablebase says that you can win it.
The end result is that I have created an opening book that is 10 moves long at most, don't use the tablebases and scaled down the program to play around 1700-1800 ELO. (I'm just an amateur player, with a maximum rating of 1825, but that was 15 years ago, when I was a teenager...)
Since Fruit 2.1 was released in the open source community around 2005, the knowledge of programming a chess engine has exploded. Almost all open source engines that can play chess at top level nowadays are either based on Fruit and using some Crafty idea's, or the other way around.
I did write a chess engine / program in Borland Delphi about 15 years ago (again, as a teenager), but it was slow, and very weak. I've always wanted to try again, but didn't because of lack of time and other priorities. Seeing that there are now *hundreds* of engines available (it seems that everybody and his grandma can write a chess engine now), I've given up this ambition, and will be taking a look at Arimaa to see if I can write an engine for this game.
In case you are wondering: I am quite a weak Arimaa player. My strong point in chess was (is) in tactics, and they don't play a large part in Arimaa. If I end up writing an Arimaa engine, it is conceivable that the very first version that can do Alpha/Beta pruning and some other extensions will be able to hansomely beat me because it can think further ahead.
To be very honest, my only interest in Arimaa is as a software engineer; to have a game in which not all engines are already at championship level. I don't intend to play Arimaa against human players, ever. After quitting all competitions for chess (and those for martial arts too, another hobby) around my 18th year, I've actually not played a game of chess against a human either: and I'm now 32.
edit: Maybe it's a paradox. My text (rant?) above states that computers did ruin chess, and now, my only interest in Arimaa is from the perspective of the computer / software engineer. So, would I be helping to ruin Arimaa, using the computer...? I don't know... but I'd try to make computer programs better. chess brought many advances in search techniques to the computer. Maybe Arimaa will do too.
|
| « Last Edit: Apr 6th, 2012, 9:01pm by Katsunami » |
IP Logged |
|
|
|
Fritzlein
Forum Guru
Arimaa player #706
Gender:
Posts: 5928
|
|
Re: King's Gambit chess opening claimed as solved
« Reply #11 on: Apr 6th, 2012, 9:27pm » |
Quote Modify
|
on Apr 6th, 2012, 7:52pm, Katsunami wrote:| [...] imagine a parallellized version of Chinook, with even more checkers knowledge than it had at that time, running on today's hardware. It would be virtually unbeatable. |
|
Not virtually unbeatable; literally unbeatable. Checkers has been proved by force to be a draw.
Quote:| I am quite sure that the opening books and endgame tablebases will become bigger until they meet. |
|
That is precisely what happened for checkers. We're still quite a ways off for chess, though. (At least so I thought until the fake article fished me in!  )
Quote:| I've given up this ambition, and will be taking a look at Arimaa to see if I can write an engine for this game. |
|
Woot!
Quote:| I don't intend to play Arimaa against human players, ever. |
|
That should give you a unique and possibly very valuable programming perspective.
Quote:| So, would I be helping to ruin Arimaa, using the computer...? |
|
Yes, indeed, you would be helping to ruin Arimaa. It is a big plus for Arimaa's popularity that the Arimaa Challenge remains unconquered. But if you try to win the Challenge and fail, you will have helped give Arimaa credibility, so on the balance I'm happy you will try. 
|
|
IP Logged |
|
|
|
Katsunami
Forum Senior Member
Gender:
Posts: 29
|
|
Re: King's Gambit chess opening claimed as solved
« Reply #12 on: Apr 7th, 2012, 3:15am » |
Quote Modify
|
on Apr 6th, 2012, 9:27pm, Fritzlein wrote:
That should give you a unique and possibly very valuable programming perspective. |
|
Maybe it will. Still, I know myself well enough to say that I might never complete the engine, for several reasons.
First is that I'm a perfectionist who tries to solve every possible problem before even starting to write a program. Sometimes, this causes me to never write the program at all, because of a (small) problem for which I can't see an immediate solution. I loathe to start writing an engine and then get stuck at 95%, for example; and I refuse to look into other people's code because I want my first engine to be my own for the full 100%.
Second is that I've seen that people have written a Master's thesis on this subject, such as LightVector. In the Netherlands, writing such a thesis (and creating the program) would take about 6-8 months of full time work. I don't have that kind of time; when coding a bot in part time, 10 hours a week (which would be a lot of time to spend on it), it would take at least 24 months to make it play well enough to stand a chance against the best bots of this moment, and then it would still be 2 years behind.
Third reason is one that may surprise you. If I am completely honest, I would have to say that I don't really like Arimaa as a game (1); my only interest in it is with regard to writing an engine. I will probably never play it extensively, as I did with chess. The reason is that Arimaa exactly embodies what I hate most in chess: extremely slow positional play. In a game of chess, I often got very nervous, agitated (and sometimes even angry) when an opponent would play only positionally, keeping a close position, and avoiding all risks.
I am known to do things like crack open a position by sacrificing a knight or bishop for one or two pawns knowing full well that it wouldn't be the best move, or to play a move solely to complicate a position and increase tactics, although the end result of such a move is far from clear. I'd rather do something like that and lose the game at move 45, than win it after playing a 127 move long end game.
A top chess player that does the same is Vassily Ivanchuck. Look at his rating chart at the FIDE site. You see huge ups and downs, because sometimes he takes huge risks and losing games because of it. It is often cited that this is the main reason for him to never break the 2800 rating mark, and also the reason why he never became world champion.
If I even get a working bot at some point, I would expect that it plays very tactical; not because I want it to, but because the evaluation rules I'd put in there make it so.
I've got the design of the bot mapped out in my head already. Maybe I should just fire up Eclipse and start coding in C++ and see where I'll end up. It would be my first Linux program too, after coding for years in Windows.
(1) Sorry Omar Maybe I should buy Fritzlein's book, so I can get a better understanding of the game more quickly. I can imagine that understanding the game better would make it more fun. But, if I do, I see myself implementing the book into the evaluation function where possible, if I ever get to that point...
|
| « Last Edit: Apr 7th, 2012, 3:22am by Katsunami » |
IP Logged |
|
|
|
christianF
Forum Moderator
Forum Guru
Arimaa player #4019
Gender:
Posts: 804
|
|
Re: King's Gambit chess opening claimed as solved
« Reply #13 on: Apr 7th, 2012, 5:26am » |
Quote Modify
|
on Apr 7th, 2012, 3:15am, Katsunami wrote:| First is that I'm a perfectionist who tries to solve every possible problem before even starting to write a program. Sometimes, this causes me to never write the program at all, because of a (small) problem for which I can't see an immediate solution. I loathe to start writing an engine and then get stuck at 95%, for example; and I refuse to look into other people's code because I want my first engine to be my own for the full 100%. |
|
That's called 'inverse strategy': just make the goal look so hard to reach that it effectively keeps you from starting.
on Apr 7th, 2012, 3:15am, Katsunami wrote:Third reason is one that may surprise you. If I am completely honest, I would have to say that I don't really like Arimaa as a game (1); my only interest in it is with regard to writing an engine. I will probably never play it extensively, as I did with chess. The reason is that Arimaa exactly embodies what I hate most in chess: extremely slow positional play.
...
If I even get a working bot at some point, I would expect that it plays very tactical; not because I want it to, but because the evaluation rules I'd put in there make it so.
I've got the design of the bot mapped out in my head already. Maybe I should just fire up Eclipse and start coding in C++ and see where I'll end up. |
|
This begs the question in how far a programmer's skills might be affected by knowledge of the game or lack thereof, and maybe also whether this relation (if any) differs in the 'traditional' evaluation function and MCTS. I'm currently getting to grips with an MC based Symple bot that as far as I'm aware doesn't incorporate any heuristic knowledge.
Of course I'm in the "please do try" camp.
|
|
IP Logged |
|
|
|
Katsunami
Forum Senior Member
Gender:
Posts: 29
|
|
Re: King's Gambit chess opening claimed as solved
« Reply #14 on: Apr 7th, 2012, 6:32am » |
Quote Modify
|
on Apr 7th, 2012, 5:26am, christianF wrote:
That's called 'inverse strategy': just make the goal look so hard to reach that it effectively keeps you from starting. |
|
Yeah, I know. Maybe I should think a bit less and code a bit more and solve the smaller, non-design related problems as I encounter them.
Quote:| This begs the question in how far a programmer's skills might be affected by knowledge of the game or lack thereof. |
|
Most people who help to write an open source chess engine such as Stockfish are not even chess masters. I think most of them are strong amateurs at best. Still, Stockfish plays at top grandmaster level. It doesn't seem to make too much of a difference. I've very recently experienced that myself.
After 6 years of full time software engineering work, I've gone back to school (part time) to finally get a master in computer science (obviously I have the bachelor already). One of the assignments was to create an AI for a somewhat simplified version of Cartagena. (The luck factor was taken out.)
I never played that game, and even didn't know of it's existence. After implementing the game in C#, using a simple iterative deepening search and some pruning, and a very simple evaluation function, it played OK, but weak.
After this initial implementation I didn't even optimize the search routine, but only extended the evaluation function to take into account some strategies I've found on the net. This resulted in me being unable to defeat my own Cartagena engine. For the record, the teacher, who was much better at this game than I was, also couldn't defeat it.
So, it is possible to write game playing software that plays acceptably, even when you don't know the game very well. If I ever finish an Arimaa engine, I expect it to be (much) stronger than I am.
Conceptually, engines for most two-player board games are the same. Programming skill is not the problem... the biggest problem is time; the second biggest is that I've never programmed in Linux, but seeing that I switched my main workstation to this OS some time ago, I intend to learn.
I've just installed Eclipse for C++, and compiled my very first Linux program: A 64-bit version of "Hello World!" Nice. I'm already 80% done. Hehe.
|
| « Last Edit: Apr 7th, 2012, 6:41am by Katsunami » |
IP Logged |
|
|
|
|
Home
Help
Search
Members
Login
Register
Reply
Notify of replies
Send Topic
Print