Comment by bambax | Hacker News Reader

Comment by bambax | Hacker News Reader

Parent Full thread

> What is complexity in chess?

If there is only one possible move then arguably the complexity of the position is zero (not counting when there are no more possible moves, which means the game is over).

But complexity can't be measured only by the number of possible moves. If there is a mate in 1, but lots of possible moves, then complexity of the position is also very low for a player with any familiarity with the game, and potentially, moderately high for someone who has never played any game (but knows the rules).

Yet it should be possible to measure "absolute complexity", ie, complexity that doesn't depend on the experience of the player.

So, complexity is a factor of the size of the tree, and the minimal number of moves between the current position and winning. (Because chess is entirely deterministic, that distance always exists. We are (currently) unable to measure it in most cases, but we can be sure it does exist.)

It should be possible to estimate the size of the tree heuristically, even without enumerating all possible moves. But then I'm not sure where to go from there...

> "If there is a mate in 1, but lots of possible moves, then complexity of the position is also very low for a player with any familiarity with the game"

This is one reason I think the concept of complexity will probably never be formalized. Because even when a position is mate in 1, the complexity varies wildly. For instance here [1] is a game between Carlsen and Nakamura where Carlsen, perhaps the strongest player of all time, failed to see a mate in 1, and for that matter Nakamura, not exactly a weaker player himself, help-mated himself by playing one of the only moves that allowed Carlsen a mate in 1! And both players still had tons of time on their clock.

But to understand how they both missed it you need to go back in the position and see that both saw black's queen was defending against the mate, and Nakamura's blunder interfered with that protection in a rather unusual way. So you can't even assess it on a positional basis, since it's dependent upon what was played before, let alone all of the poorly defined terms I'm using like 'rather unusual.'

[1] - https://www.chess.com/events/2024-titled-tuesday-blitz-may-7...

I agree that complexity can vary widely even with mate in 1. Lots of mate in 1 chess puzzles to prove that.

But in the case of this game, I wouldn’t say that they missed the mate in 1 due to the complexity of the position or the previous moves. They both just had the same blind spot, happens every so often.

Yeah but in this position Qh7# was literally the main idea in the position. It wasn't like some surprising idea. But I think it's logically explainable. When you're playing the game, each move you're considering what changed with your opponent's move, and after black plays h6 your mind naturally considers the pawn rather than the square. So it's easier to miss that h7 has become weaker.

If Magnus, or probably any player over ~2300, saw this position in a vacuum, they'd all literally instantly see Qh7#. It's basically impossible to miss, except for this weird nuance!

> ...between the current position and winning. (Because chess is entirely deterministic, that distance always exists. We are (currently) unable to measure it in most cases, but we can be sure it does exist.)

Can we?

Just because it's deterministic doesn't mean it always leads to a win - there may be strategies that always lead to a draw, we may just not know about them. Tic-tac-toe is deterministic and we know it always leads to a draw if played correctly - we know about it because it's a much simpler game (much smaller tree of possibilities).

Indeed, in Stockfish, a 100-centipawn advantage for a player is calibrated to mean "a 50% chance of a win (as opposed to a draw or a loss) from the current position" [0].

In endgame tablebases, the distinction can get interesting, since one player may in principle have a forced mate, but it would take so many moves that the opponent could force a draw by the 50-move rule.

[0] https://official-stockfish.github.io/docs/stockfish-wiki/Sto...

Reply on news.ycombinator.com