A Chess Firewall at Zero? (opens in new tab)

(rjlipton.wordpress.com)

37 pointsdeweerdt10y ago9 comments

9 comments

I always find it interesting when people say things like "chess is a PSPACE problem", because in order to define it as such, you have to consider the board size to be variable, even though it's always 8x8.

dsjoerg10y ago

well you've found the right guy to ask about that because the author is a professor of Computational Complexity Theory.

tromp10y ago

But you can safely say "Ladders are PSPACE-complete" about the game of Go which is played on many different sizes, some far larger than the standard 19x19 (e.g. KGS supports 38x38 boards).

w0bb1310y ago

The number of serious games above 19x19 is basically nil, so the difference is a bit misleading (although it's definitely more common in go).

hollerith10y ago

I'm interested in the topic, but found the exposition hard to follow.

jasonmp8510y ago

Yeah, it leads with a bunch of maybe-related logic history and I'm not really sure where the thesis starts. Maybe it's just a Monday morning, but the writing was impenetrable to me (and not because of the topic, but because of the prose).

recursive10y ago

How do you read the charts? I can't make head or tail.

tromp10y ago

They show number of blunders (score dropping 1.5 or more) categorized by player strength and current position evaluation according to either Komodo or Stockfish. The conclusion is that people blunder much more in worse positions, but they blunder most in dead even positions.

At least I think that's what it says:-)

rspeer10y ago

I'm not following all of the theory involved, but this makes me wonder if the "firewall" is just an effect of the scale on which they're measuring positions.

Chess engines evaluate a large range of positions as having value 0.00. In fact, an omniscient chess engine would evaluate every position as either having value 0.00 or as being "mate in N" (where N could be unreasonably large).

So maybe the blunders from positive positions are smaller because, as evaluated by a sufficiently strong chess engine, they mostly drop you from +(small number) to 0.

j / k navigate · click thread line to collapse

9 comments

klodolph10y ago

dsjoerg10y ago

well you've found the right guy to ask about that because the author is a professor of Computational Complexity Theory.

tromp10y ago

But you can safely say "Ladders are PSPACE-complete" about the game of Go which is played on many different sizes, some far larger than the standard 19x19 (e.g. KGS supports 38x38 boards).

w0bb1310y ago

The number of serious games above 19x19 is basically nil, so the difference is a bit misleading (although it's definitely more common in go).

hollerith10y ago

I'm interested in the topic, but found the exposition hard to follow.

jasonmp8510y ago

recursive10y ago

How do you read the charts? I can't make head or tail.

tromp10y ago

At least I think that's what it says:-)

rspeer10y ago

I'm not following all of the theory involved, but this makes me wonder if the "firewall" is just an effect of the scale on which they're measuring positions.

So maybe the blunders from positive positions are smaller because, as evaluated by a sufficiently strong chess engine, they mostly drop you from +(small number) to 0.

j / k navigate · click thread line to collapse