Comment by randomwalker | Hacker News Reader

Comment by randomwalker | Hacker News Reader

Parent Full thread

I'm sorry, but that is simply incorrect.

it's a simple matter to force equal trades; black cannot avoid the exchange of pieces forever, and if white plays a perfect game he will always win, without doubt.

Yes, that's pretty much the human intuition for why no one doubts that White will win. But it is very, very far from a mathematical proof.

Okay, just calculate the moves it would take to force the equal exchange of material from a given position.

Let me remind you that each ply has a branching factor of about 20, which means each move has a branching factor of several hundred. In most positions you'd be lucky to be able to calculate even one or two forced exchanges, let alone all the way to the end of the game.

A program attempting to prove victory operates in a very different context from a normal chess playing program — it is not allowed to prune any positions at all. We haven't even found the status of all seven piece endings yet! That is despite intense effort. See http://en.wikipedia.org/wiki/Endgame_tablebase

It is utterly, utterly inconceivable that a search-based approach will ever prove victory with Queen odds.

it is not allowed to prune any positions at all

https://secure.wikimedia.org/wikipedia/en/wiki/Alpha-beta_pr...

Not that I disagree with the overall point. A search-based approach might solve the game at queen odds, but it will not be any time soon; indeed, it would require devoting more computing resources than the planet has for a pretty significant amount of time.

No. randomwalker's point is that every branch must be proved to be a win.

>> "it would require devoting more computing resources than the planet has for a pretty significant amount of time"

This is also incorrect. As mentioned in other comments, the branching factor of chess implies that it is not brute force solvable using the entire universe as a computer--let alone just Earth.

No. randomwalker's point is that every branch must be proved to be a win.

In alpha-beta pruning, branches are only eliminated when they can only be reached through suboptimal play on one player's part. Suboptimal play on either player's part can clearly result in a loss for that player, but this is not very interesting.

This is also incorrect. As mentioned in other comments, the branching factor of chess implies that it is not brute force solvable using the entire universe as a computer--let alone just Earth.

This depends on how much time you're willing to devote to the task. My laptop (or my phone even) would be able to "solve" Chess given an infinite amount of time.

Now, the entire universe used as memory would be unable to store such a solution, but that isn't really germane to the decision problem.

> Yes, that's pretty much the human intuition for why no one doubts that White will win. But it is very, very far from a mathematical proof.

White will win if he plays perfectly: this is mathematically assured because white has an advantage of nine points. The only way for white to lose or to draw is by extreme error. The article assumes a perfect game, so I too assume that white will play a perfect game.

> Let me remind you that each ply has a branching factor of about 20, which means each move has a branching factor of several hundred. In most positions you'd be lucky to be able to calculate even one or two forced exchanges, let alone all the way to the end of the game.

As I recall, Deep Blue was calculating at a depth of more than eight moves...

> The Deep Blue chess computer which defeated Kasparov in 1997 would typically search to a depth of between six and eight moves to a maximum of twenty or even more moves in some situations. -- http://en.wikipedia.org/wiki/Deep_Blue_(chess_computer)

I find it difficult to believe that this wouldn't have improved or could not be improved upon, since this was based on the technology available in 1997. It's safe to say we've made progress since then.

While you may not be able to calculate an entire game, you could certainly calculate all the exchanges required to reach a properly winnable and calculable endgame. This is pretty damn close to being able to calculate a whole game...and you're assured victory.

As I said, once you get to a point of two kings and a queen, it's trivial.

I think one important point you're missing is that a chess engine looking to mathematically prove a victory is very different from the ones that play against grand masters. Deep Blue may have been able to calculate 6 to 8 moves in advance, but that was after it pruned all the moves that were obviously incorrect. When you're trying to prove something mathematically however, you have to assume that even something as silly as sacrificing a queen for a pawn with no obvious positional gains is a valid move and calculate all possible branches taken from that move until checkmate some 30 moves down the road.

For example, checkers is a vastly simpler game than chess. Yet, it took 18 years of constant computation to solve it [1]. Even a game as simple as tic-tac-toe has 255,168 possible games [2]. The estimated number of chess games is 10^10^50 [3].

1. http://www.newscientist.com/article/dn12296-checkers-solved-...

2. http://en.wikipedia.org/wiki/Tic-tac-toe

3. http://mathworld.wolfram.com/Chess.html

It is important to remember that "the value of 1 Queen is equivalent the value to 9 Pawns" is only an heuristic. It helps the players to make decisions but nobody wins only because he has more points.

And the values are not written in stone. For example, Knights and Bishops usually have the same value, that is like tree pawns for each one. But if the position is open the Bishops are usually more valuable and if the position is closed the Knight are more valuable.

I'm also completely sure that in "Chess with Queen" White has a wining strategy, but being completely sure is not a proof. (I have been wrong before!)

Reply on news.ycombinator.com