alt Hacker News> 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...
Replies
> ...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).
> "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...