King's Gambit refuted (almost)

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:

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

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.

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.

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.

Chess? Pfft. Now do Starcraft II.

-Tom

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.

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.

Uh?

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

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.

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

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

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

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.

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.

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…

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

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.