King's Gambit refuted (almost)

[SuperAdventurer]

Technically it's not refuted because after black accepts the gambit, white can still draw with 3. Be2. But all other white moves including the most common, 3. Nf3 have been shown to lose by force. This is based on months of computer analysis by Vasik Rajlich, the creator of the chess program Rybka. Article here:

http://www.chessbase.com/newsdetail.asp?newsid=8047

Pretty stunning stuff. Will chess be a solved game soon, like Checkers?

[Jason McCullough]

I doubt it'll ever be solved; the search space is just too big. I expect heuristics that are virtually impossible to beat within 20 years, though.

[SuperAdventurer]

Well according to the article, the position after 1. e4 e5 2. f4 exf4 has already been solved (it's a draw after 3. Be2, and a win for black otherwise). Except with the qualifier that positions where Rybka evaluates one side to have an advantage of > 5.12 are treated as wins, so the "solution" has some chance of being wrong. But still, if that's right, how much harder would it be to do the same thing for the initial position of chess, and therefore solve chess? Doesn't seem like that big of a leap to me.

As for heuristics that are virtually impossible to beat, I've got that on my phone already. At least for me, and I'd cross out the "virtually" part as well.

[ReptileHouse]

Note that the analysis used isn't, mathematically speaking, complete. As you note, the tree is pruned aggressively. While in practical terms, that's almost certainly a valid technique, it does mean the demonstration is not mathematically complete in the sense of making the position truly solved.

As to using the techniques on the starting position, that's a much, much larger step than it would seem. The article touches on it a bit.

[Tom Chick]

Chess? Pfft. Now do Starcraft II.

-Tom

[Shimarenda]

Will chess be a solved game soon, like Checkers?
I don't believe so. Even if there is an optimal move which is then refuted by another optimal move, all that needs to happen is for the first person to make a different move. It may not be optimal, but it frustrates the other person's expectations unless he has every possible answer at his mental disposal.

[AaronSofaer]

Chess? Pfft. Now do Starcraft II.

-Tom


Efforts to provably solve Starcraft I using routines developed by the Berkeley Overmind guys are in progress. Several people expect to get PhDs out of it.

Interestingly, it does look like mass muta is essentially unbeatable because perfect micro on worker units versus a rush build results in a loss for the rush, and Zerg's superior strategic mobility and vision are just so powerful.

Starcraft II is more computationally intensive to do a similar analysis for, and the power differential between various unit types is less severe; it's likely that it cannot be solved in the same way.

[TurinTur]

Efforts to provably solve Starcraft I using routines developed by the Berkeley Overmind guys are in progress. Several people expect to get PhDs out of it.



Uh?

To "solve", computationally speaking, a game like Starcraft, is worlds above solving chess or checkers. And we still haven't solved chess.

[SamS]

I have never played a game where someone used King's Gambit. It's basically white making life difficult for itself. Solve King's Indian and I will be impressed.

[Aceris]

Does noone else find the first paragraph suspicious?

"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, in spite of the bustle of moving boxes and setting up phone and Internet connections Vas, kindly agreed to the following interview, which had been planned some months ago."

[Zenchess]

I just wrote out a long response to this 'refutation' of the king's gambit, but instead I'm going to do more research first.

However, here are some things to be aware of:

a) rybka is no longer the strongest chess engine, houdini is
b) There is not enough processing power in the entire known universe as we know it to 'solve' chess. This has been discussed in various places by mathematicians. The closest we are to solving anything in chess is in certain endgames with small numbers of pieces. These are called tablebases.
c) Saying you've 'solved' an entire freaking opening tree using your commercial chess engine is a great publicity stunt.

Anyways, when I read this article it threw me back to when I was reading a bit of chess history and read Bobby Fischer's 'King's Gambit is busted' article.



d) was this article released on april 1st by any chance? :)

[Miramon]

I doubt it'll ever be solved; the search space is just too big. I expect heuristics that are virtually impossible to beat within 20 years, though.

Huh? It's already virtually impossible to beat the top-ranking program, as Kasparov found out quite some time ago.

[CLWheeljack]

Huh? It's already virtually impossible to beat the top-ranking program, as Kasparov found out quite some time ago.

I'm not sure if this is what Jason meant, but I think those are based on databases of known outcomes rather than heuristics (I could be wrong about that though).

[peterb]

Huh? It's already virtually impossible to beat the top-ranking program, as Kasparov found out quite some time ago.

For Chess to be "solved" requires a higher standard than "machines can beat people every time." It's like a mathematical proof - even if something is shown to be true for the first 4 million trillion trillion trillion trillion trillion trillion trillion integers, it still might not "proven" for the set of all integers.

[Miramon]

For Chess to be "solved" requires a higher standard than "machines can beat people every time." It's like a mathematical proof - even if something is shown to be true for the first 4 million trillion trillion trillion trillion trillion trillion trillion integers, it still might not "proven" for the set of all integers.

No one claimed it was solved. I was responding to a suggestion that chess might not be winnable by humans in 20 years; IMO it's not winnable by humans now.

[Miramon]

I'm not sure if this is what Jason meant, but I think those are based on databases of known outcomes rather than heuristics (I could be wrong about that though).

Yes, you are :)

Obviously the openings are in databases as are some end-games, but the rest is heuristic-guided search with fancy tree-shaking and various other kinds of cleverness.

[Zenchess]

Miramon humans still beat computers in individual games of chess. They lose matches, however. And Kasparov's match against deep blue was not a good example of your theory- kasparov won at least one of those games and had a draw in one of the positions he resigned.

[Miramon]

Miramon humans still beat computers in individual games of chess. They lose matches, however. And Kasparov's match against deep blue was not a good example of your theory- kasparov won at least one of those games and had a draw in one of the positions he resigned.

I understand that. But if the world champion loses a challenge match, then IMO the game is now essentially unwinnable by humans. Perhaps there would only have been 5 people in the whole planet who could ever have won a single game against Deep Blue back in 1997. Also consider that match was 15 years ago, with steady hardware improvement, and no great advances in human evolution....

[ReptileHouse]

I just wrote out a long response to this 'refutation' of the king's gambit, but instead I'm going to do more research first.

However, here are some things to be aware of:

a) rybka is no longer the strongest chess engine, houdini is

Cool. Didn't know that, but very glad to hear it. I've had a bad taste in my mouth about Rybka since the whole cheating thing.


b) There is not enough processing power in the entire known universe as we know it to 'solve' chess. This has been discussed in various places by mathematicians. The closest we are to solving anything in chess is in certain endgames with small numbers of pieces. These are called tablebases.

Yes, absolutely right. What's been done here, taking the article at face value, is much weaker. It's still very interesting, but it doesn't even approach a mathematical solution to the problem.


c) Saying you've 'solved' an entire freaking opening tree using your commercial chess engine is a great publicity stunt.

Also very true and likely why the hyperbole. Unfortunate, as what he's actually done (again, assuming the reported information is actually accurate) is very interesting in and of itself.


Anyways, when I read this article it threw me back to when I was reading a bit of chess history and read Bobby Fischer's 'King's Gambit is busted' article.

Perhaps not surprisingly, that's the reported inspiration behind choosing the King's Gambit for the work.

Supposedly looking at the Najdorf next. That could be fun. ;)

[FieryBalrog]

Efforts to provably solve Starcraft I using routines developed by the Berkeley Overmind guys are in progress. Several people expect to get PhDs out of it.
They have not, however, come anywhere close to developing an AI that actually plays competitive Starcraft, or done much beyond some basic build order analysis.

[Lazy Shiftless Bastard]

This seems like an oddly good place for this command stream interception Starcraft AI video. Warning, may cause epileptic seizures!
http://www.youtube.com/watch?v=FBZT2ukipkc

[AaronSofaer]

They have not, however, come anywhere close to developing an AI that actually plays competitive Starcraft, or done much beyond some basic build order analysis.


You're joking, right? Read up on the Berkeley Overmind. Even before many, many improvements, it was beating pro-level Korean players. As it stands, it's easily the best Starcraft I "player" in the world.

Or are you talking just about Starcrat II?

[Wolff]

The ability to simultask instead of mere multitasking I think would give AIs a huge advantage in RTS. Time to execute moves is severely hampered by the interface device for humans. The only games IMO that humans stand a chance are ones that reward creative strategies.

[SuperAdventurer]

So apparently the King's Gambit lives on. ChessBase got me good:

http://www.chessbase.com/newsdetail.asp?newsid=8051

[Robert Sharp]

I don't know why anyone reads ANY internet/news stories anywhere NEAR April 1st.

A holiday dedicated to lying is such a crap idea. But maybe that's the ethics professor in me speaking.

[Ultrazen]

No one claimed it was solved. I was responding to a suggestion that chess might not be winnable by humans in 20 years; IMO it's not winnable by humans now.

There are 2 ways to beat computers at chess, at least that I've found.

1. Sacrifice games. Most computers will always take a piece that has a higher point score. You can use that to manipulate position, which is 95% of chess. Really top end programs won't fall for this, but things like phone apps etc will.

2. Trade even pieces as often as you can, as long as your position remains in tact. Reduce the game to the least amount of pieces. Computers have a huge advantage when it comes to tabulating multiple scenarios, if you reduce the variables it's much easier to at least play to a draw.

[GloriousMess]

There are 3 ways to beat computers at chess, at least that I've found.

1. Sacrifice games. Most computers will always take a piece that has a higher point score. You can use that to manipulate position, which is 95% of chess. Really top end programs won't fall for this, but things like phone apps etc will.

2. Trade even pieces as often as you can, as long as your position remains in tact. Reduce the game to the least amount of pieces. Computers have a huge advantage when it comes to tabulating multiple scenarios, if you reduce the variables it's much easier to at least play to a draw.
3. Unplug the computer, re-arrange the pieces into checkmate, plug it back in.

[anymunym]

2. Trade even pieces as often as you can, as long as your position remains in tact. Reduce the game to the least amount of pieces. Computers have a huge advantage when it comes to tabulating multiple scenarios, if you reduce the variables it's much easier to at least play to a draw.

Really? I would have assumed the opposite to be true, i.e. that the computer's advantage became bigger the fewer pieces there were left on the board as fewer variables would allow it to look further ahead.

[vyshka]

Heh, Chessbase's April Fool's joke strikes again.

http://chessbase.com/newsdetail.asp?newsid=8051

[FieryBalrog]

You're joking, right? Read up on the Berkeley Overmind. Even before many, many improvements, it was beating pro-level Korean players. As it stands, it's easily the best Starcraft I "player" in the world.

Or are you talking just about Starcrat II?
Perhaps you can show me. As far as I know this is pure unadulterated bullshit, especially this bolded line.

The program won an AI competition. A competition amongst other AIs. It couldn't even beat a 3rd rate former Starcraft player at the same time. Its "optimal build order" is based on operating in a vacuum. I have absolutely no idea how you are confidently proclaiming it to be the "best SC1 player in the world". The best at winning a muta micro competition, uh, OK.

[AaronSofaer]

Perhaps you can show me. As far as I know this is pure unadulterated bullshit, especially this bolded line.

The program won an AI competition. A competition amongst other AIs. It couldn't even beat a 3rd rate former Starcraft player at the same time. Its "optimal build order" is based on operating in a vacuum. I have absolutely no idea how you are confidently proclaiming it to be the "best SC1 player in the world". The best at winning a muta micro competition, uh, OK.


Are you talking about the two players the AI did, in fact, beat, one of whom was a respectable ICCup player?

And yes, it won an AI competition. In 2010, with an outdated build that they had already significantly improved upon. It micros, it macros, it maintains map presence, scouts, harasses, does gas-steal shenanigans, it's far more than a "muta micro" bot.

The version they released mopped the floor with a couple of Korean pros. The versions they didn't release - because they really didn't give a shit after the competition, it's not like they're in it for the money - were apparently improved in every respect, but they didn't want to put in the time and effort to QA it.

So in sum, how bout you show me a video of someone beating even the build they released for the AIDE competition?