Arimaa Forum - Print Page


    
      
        Arimaa Forum
        (http://arimaa.com/arimaa/forum/cgi/YaBB.cgi)
      

        Arimaa >> Off Topic Discussion >> King's Gambit  chess opening claimed as solved
        
(Message started by: rbarreira on Apr 2^nd, 2012, 9:21am)

Title: King's Gambit chess opening claimed as solved
Post by rbarreira on Apr 2^nd, 2012, 9:21am

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.

Title: Re: King's Gambit chess opening claimed as solved
Post by Adanac on Apr 2^nd, 2012, 9:46am

on 04/02/12 at 09:21:38, rbarreira wrote:

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.

Title: Re: King's Gambit chess opening claimed as solved
Post by rbarreira on Apr 2^nd, 2012, 10:53am

Still wondering if this is not a delayed April Fool's joke, which would be pretty lame...

Title: Re: King's Gambit chess opening claimed as solved
Post by omar on Apr 2^nd, 2012, 11:31am

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.

Title: Re: King's Gambit chess opening claimed as solved
Post by omar on Apr 2^nd, 2012, 11:42am

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

Title: Re: King's Gambit chess opening claimed as solved
Post by Fritzlein on Apr 2^nd, 2012, 11:48am

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.

Title: Re: King's Gambit chess opening claimed as solved
Post by Fritzlein on Apr 2^nd, 2012, 11:51am

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! :)

Title: Re: King's Gambit chess opening claimed as solved
Post by rbarreira on Apr 2^nd, 2012, 12:58pm

on 04/02/12 at 11:51:24, 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.

Title: Re: King's Gambit chess opening claimed as solved
Post by Adanac on Apr 2^nd, 2012, 2:09pm

on 04/02/12 at 12:58:45, 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 8)

Title: Re: King's Gambit chess opening claimed as solved
Post by The_Jeh on Apr 2^nd, 2012, 2:45pm

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.

Title: Re: King's Gambit chess opening claimed as solved
Post by Katsunami on Apr 6^th, 2012, 7:52pm

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 04/02/12 at 11:48:15, 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 (http://en.wikipedia.org/wiki/Marion_Tinsley)) 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.

Title: Re: King's Gambit chess opening claimed as solved
Post by Fritzlein on Apr 6^th, 2012, 9:27pm

on 04/06/12 at 19:52:45, 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! :D)

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

Title: Re: King's Gambit chess opening claimed as solved
Post by Katsunami on Apr 7^th, 2012, 3:15am

on 04/06/12 at 21:27:24, 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. (http://ratings.fide.com/id.phtml?event=14100010) 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...

Title: Re: King's Gambit chess opening claimed as solved
Post by christianF on Apr 7^th, 2012, 5:26am

on 04/07/12 at 03:15:43, 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 04/07/12 at 03:15:43, 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. :)

Title: Re: King's Gambit chess opening claimed as solved
Post by Katsunami on Apr 7^th, 2012, 6:32am

on 04/07/12 at 05:26:03, 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.

Title: Re: King's Gambit chess opening claimed as solved
Post by christianF on Apr 7^th, 2012, 9:21am

on 04/07/12 at 06:32:27, Katsunami wrote:

Conceptually, engines for most two-player board games are the same.

I'm not sure what you mean by that. My gut feeling tells me that MCTS isn't the way to go in Arimaa, whereas the traditional approach looks very unprospective in Havannah. This would suggests that different classes of games may be approached better by the one or the other method.

Title: Re: King's Gambit chess opening claimed as solved
Post by clyring on Apr 7^th, 2012, 9:39am

on 04/07/12 at 03:15:43, 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. 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.

Believe me when I say that not every game of arimaa is tidy with little room for tactical fuss. Endgames in particular tend to feature difficult tactical skirmishes- a "127 move long endgame" in arimaa would in all likelihood be the most active 127 moves you ever play. ;)

Title: Re: King's Gambit chess opening claimed as solved
Post by Katsunami on Apr 7^th, 2012, 11:17am

christianF: Too big of a mind jump; I tend to do that. Sorry :) What I meant is that most board games have game playing engines with comparable structure: They all have a board representation, a move generator, a search function, and an evaluation function, and so on. Implementation of these functions is a detail.

clyring: I've never experienced that; the not so many games I played against other bots, where mostly very positional. Could also be me, of course, not seeing the tactical stuff :)

Title: Re: King's Gambit chess opening claimed as solved
Post by clauchau on Apr 14^th, 2012, 12:54pm

To me the most interesting problem in developing game engines lies in the evaluation function in some specific way...

Are you going to fiddle with a few geometric, algorithmic or intuitive local ideas proper to the game and your particular grasp of it and then feel good about the original result outgrowing your own understanding of the game and others' as well? That was my motivation 15 years ago.

Or are you going to try some original idea with the evaluation function or the overall search structure that may find applications to other games and fields, such as resistive networks or Monte Carlo Tree Searches? It grew up as my main motivation along the years, and Arimaa researchers here are quite oriented that way too.

Or are you even going to help mankind better understand games strategy in some general and well-structured way, with the help of special cases such as Arimaa? I don't see much of that, except with the Abstract Game Theory of Berlekamp and al and general search algorithms, but I'm not satisfied with them when I want to understand and evaluate most games we know. There is some good science waiting to emerge there and that's what seem's the most exciting to me today.

What do you think?

Title: Re: King's Gambit chess opening claimed as solved
Post by Katsunami on Apr 14^th, 2012, 1:14pm

The evaluation function seems to be by far the most important part of most game-playing programs.

When I wrote an engine for the game of Cartagena a few months ago (a bit simplified: all cards open, so it became a complete information game without luck). I tested this by having two engines play against each other: one with a very simple evaluation function ("Take the biggest steps possible"), but set to think 8 ply deep. The other engine had a much better evaluation function taking several things into account ("Closer to the end of the board is better", "Make sure the opponent cannot goal a piece", etc), and it was limited to 4 ply. It won every time, despite the huge depth-handicap

It can also be seen in chess. Run Fritz 13 on an old 2001 Pentium 3 computer, and have it compete against Deep Fritz 7, running on a 2012 computer. Most probably, Fritz 13 will be able to beat the computationally much more powerful setup running the older Fritz. The newer version is just way, way smarter.

As Arimaa prohibits deep thinking, I think that knowledge (so, the evaluation function) will be all important. This is already proven by P1-bots being stronger than some P2-bots in the game-room.

Thinking well, but less deep seems to be better than thinking deep without having much of a plan.

The entire problem with Arimaa is that not many people know how to play it well; and even the strongest players of today may be proven to play the game "wrong". Many idea's in chess that were thought to be good and were practiced for a long time were later proven not to be the best way to go about the game.

Title: Re: King's Gambit chess opening claimed as solved
Post by christianF on Apr 14^th, 2012, 3:51pm

on 04/14/12 at 13:14:25, Katsunami wrote:

The entire problem with Arimaa is that not many people know how to play it well; and even the strongest players of today may be proven to play the game "wrong". Many idea's in chess that were thought to be good and were practiced for a long time were later proven not to be the best way to go about the game.

That may not be the entire problem with Arimaa (a broad player base with a relatively high summit considering its age) and at the same time it is a generic problem. I'm glad you address it.

The game for the next CodeCup Challenge (http://www.codecup.nl/intro.php) will be Symple.

So I asked myself the question what would happen. Thirty or forty programs compete and one will win, eventually, no special gifts of prophecy required.

Such a result doesn’t mean much regarding the game’s ‘resistance’ to programmability if there’s no human opposition to provide a context.
So I started to play Symple to provide that context, as far as my limited abilities allow, after the Challenge has been completed, by playing against the winner.

Certain simple games (I'm referring to structure here) are difficult to program beyond the human level of play, and the question is why. Our vision on that is blurred by the fact that computer programs, MCTS in particular, often play a fairly good game without a particularly strong effort on the programmers' side. So beginners lose against the programs and the question doesn't emerge again unless humans are beating the programs. That in turn requires strong players. That in turn requires games players find worth playing. And where hypes and tactical funnies take their rightful place in this Fancy Fair, it may take a long time for a game that suits humans but defies programming, to emerge.

P.S. The Havannah Challenge is just a piece of that puzzle. If I can beat the bots ten out of ten it doesn't say bots won't win, eventually. But it says were not quite there yet, and there may be other havannah's, or arimaa's for that matter ;)