There is quite specific machining to difficult positions in chess that should be mentioned. A difficult position occurs when at the surface it seems that there are many viable moves to be analyzed. Think of being a kid and thinking which pawn to move first. Then you learn opening theory and it gets a little easier.
But you can still encounter a position where you could take multiple pieces, all leading to different trades or some forces moves. Another scenario is when you're in a closed position and there are many, many micro adjustments you could make. An ai might know that you should move the A pawn and you might not even be considering it.
Basically, positions where GothamChess starts speaking with a Russian accent to channel the Russian grandmasters.
janalsncm
4 hours ago
[ - ]
The author is looking for positions which are difficult for low rated players and easier for high rated players.
Poor man’s version of this which requires no training would be to evaluate positions at low depth and high depth and select positions where the best move switches.
Training neural nets to model behavior at different levels is also possible but high rated players are inherently more difficult to model.
basically, the state space of the game can produce some intuition on why certain games are hard, and is demonstrated as a clustering of various states that are only linked to the winning state by a very small number of edges. So a player can easily "get lost" in the maze.
FacelessJim
5 hours ago
[ - ]
This reminds me of a little project [1] I had fun with to try and compute the sharpness of a position and/or evaluate whole lines. Indeed, the notion of sharpness (which I believe it’s different from complexity) although easy to intuit I’ve never found a satisfactory implementation.
As a player I like to think of sharpness as a measure of the potential consequences of a miscalculation. In a main line dragon, the consequence is often getting checkmated in the near future, so maximally sharp. In a quiet positional struggle, the consequence might be something as minor as the opponent getting a strong knight, or ending up with a weak pawn.
Whereas complexity is a measure of how far ahead I can reasonably expect to calculate. This is something non-players often misunderstand, which is why they like to ask me how many moves ahead I can see. It depends on the position.
And I agree, these concepts are orthogonal. Positions can be sharp, complex, both or neither. A pawn endgame is typically very sharp; the slightest mistake can lead to the opponent queening and checkmating. But it's relativity low in complexity because you can calculate far ahead using ideas like counting, geometric patterns(square of the pawn, zone of the pawn, distant opposition etc) to abstract over long lines of play. On the opposite side, something like a main line closed Ruy Lopez is very complex(every piece still on the board), but not especially sharp(closed position, both kings are safe, it's more of a struggle for slight positional edges).
Something like a king's indian or benoni will be both sharp and complex. Whereas an equal rook endgame is neither(it's quite hard to lose a rook endgame, there always seems to be a way to save a draw).
nomilk
4 hours ago
[ - ]
Interested to read the code, but the link provided 404s
Amethyst-Cat apparently erased their github account, but the internet archive still has one snapshot [1]. The pdf link from there redirected to the davidtpeng account, but
that github user no longer has a ChessComplexity repo and the internet archive only has a broken snapshot [2].
We should be aiming to solve chess, but we are not even trying.
If the complexity of chess is finite this is possible.
Chess AI have become so good that maybe there is no more progress to be made.
We must abandon the concept of "valuation".
Here is the criterium for solving chess.
A chess engine is a constant (or bounded) time, (and memory bounded) function f which takes any position and return either 1 "white win", 0 "draw", -1 "white lose".
A chess engine solve chess if we can't find any violation in the Bellman equation :
f(gamestate) = max over legal moves of ( -f(gamestate+move) ) if there are legal moves
or f(gamestate) = result if there are no legal moves
This function f can be encoded either by a neural network or some code, but it must be computable in constant (or bounded) time.
The whole problem of solving chess is now simplified to mining the gamestate space for counter examples.
Like in math you can conjecture that your chess engine has solved the game and it stands until someone else find a violation of your game engine (either it doesn't compute in bounded time, or the bellman equation is invalid).
To verify a chess engine you can just sample a random gamestate, or a known to be difficult gamestate and check if the equation holds, that's at most max number of legal moves + 1, function evaluation.
You can try applying this concept to simple games like tic-tac-toe, or trying to compress endgame table with a neural network.
We can find such a candidate function by training a neural network by minimizing the current expected number of violation in the bellman equation over various dataset of gamestate. Once we "grok" it to zero we are done. To soften the problem you can train an auxilliary continuous function g which output the probability of 1, 0, or -1 (with a softmax) and add a discount factor like in Reinforcement Learning, but the final result is the discrete argmax of it (like in "deterministic policy gradient") with no discount factor.
Once you have this finite time oracle, playing chess is just wandering along the graph of drawable position to push your adversary into a position where his engine will have a violation of the bellman equation aka a mis-evaluation of the position where if he goes into it you will get into the winnable positions where you stay until the end. (Not all violations can be exploited as the adversary can sometime avoid going into "uncertain" positions).
A simpler (less strong) chess strategy may avoid going into "uncertain" positions as long as the position is unreachable because previous legal positions have a preferred choice. (4 state logic with win, draw, lose, uncertain). Or ordered list of moves. They make the problem easier but complexify the corresponding bellman equation.
So the game becomes once again exploring the space of "drawable" game positions in order to find positions which the adversary can't escape going into a uncertain (and losing) position. Aka playing the adversary and not the board which is an harder problem except if the adversary can play perfectly. Aka playing for the win.
mysecretaccount
1 hour ago
[ - ]
> We should have solved chess already.
> We should be aiming to solve chess, but we are not even trying.
We are trying and we should not expect to solve it because the search space is massive. There are more legal games of chess than atoms in the universe.
GistNoesis
7 minutes ago
[ - ]
This is the precisely the point I am trying to make :
A candidate solution function can take a very small finite space : much smaller than the number of gamestates.
And we can invalidate a candidate solution by finding a single counter example.
Current chess engine can't be invalidated quickly : they are not trying to solve chess. They are not falsifiable. They are not attempting to precisely define the frontier which is what I think where remaining efforts should be made.
We are just trying to encode the frontier like we would with a mandelbrot fractal.
Proving that a solution is valid is harder than finding a solution. Here I am suggesting we find the solution first.
Proving can also be done without exploring all legal chess positions. For example you can use branch and bound to cull vast amount of state space once you have your function. You just have to partition the state space and prove on each partition that the function is constant, for example when one side has 8 queen and the other has only a king with freedom of movement the position is winnable and you don't have to check every gamestate.
I am stating that there is a good chance that by searching for a function we will stumble upon one which has no counter example, because precisely the complexity of chess is not infinite (unproven conjecture (no-turing completeness of adversarial chess) ). We should be looking for it.
throw-qqqqq
41 minutes ago
[ - ]
> There are more legal games of chess than atoms in the universe
I’ll make an even stronger assertion:
There are more legal chess games in 40 moves or less, than there are atoms in the universe.
> If the complexity of chess is finite this is possible.
This is like saying the distance to Mars is finite so it should be possible to just go and live there. It's not theoretically impossible, but at the time it is practically impossible. There are real engineering challenges between here and there that have not yet been solved and from the looks of it, it will be at least several more decades before we get there.
In your example, you gloss over the construction of a "finite time oracle" by just saying "just train it until it is perfect". If humanity knew how to do that we could solve a whole other (more interesting) set of problems, but we don't.
taneq
29 minutes ago
[ - ]
"We should have solved Busy Beaver, if the complexity of BB(n) is finite this is possible."
I mean yeah, chess isn't THAT bad but still not directly tractable and besides, brute forcing it is boring.
SubiculumCode
5 hours ago
[ - ]
I was disappointed in the article, as I was primed for some 'complexity theory' type discussion, e.g. emergence,
What Is Complexity in Chess?
(lichess.org)
54 points
by: fzliu
8 hours ago
14 comments
juujian
20 minutes ago
[ - ]
There is quite specific machining to difficult positions in chess that should be mentioned. A difficult position occurs when at the surface it seems that there are many viable moves to be analyzed. Think of being a kid and thinking which pawn to move first. Then you learn opening theory and it gets a little easier.
But you can still encounter a position where you could take multiple pieces, all leading to different trades or some forces moves. Another scenario is when you're in a closed position and there are many, many micro adjustments you could make. An ai might know that you should move the A pawn and you might not even be considering it.
Basically, positions where GothamChess starts speaking with a Russian accent to channel the Russian grandmasters.
janalsncm
4 hours ago
[ - ]
The author is looking for positions which are difficult for low rated players and easier for high rated players.
Poor man’s version of this which requires no training would be to evaluate positions at low depth and high depth and select positions where the best move switches.
Training neural nets to model behavior at different levels is also possible but high rated players are inherently more difficult to model.
chii
3 hours ago
[ - ]
This reminds me of this nice video : https://www.youtube.com/watch?v=YGLNyHd2w10
basically, the state space of the game can produce some intuition on why certain games are hard, and is demonstrated as a clustering of various states that are only linked to the winning state by a very small number of edges. So a player can easily "get lost" in the maze.
FacelessJim
5 hours ago
[ - ]
This reminds me of a little project [1] I had fun with to try and compute the sharpness of a position and/or evaluate whole lines. Indeed, the notion of sharpness (which I believe it’s different from complexity) although easy to intuit I’ve never found a satisfactory implementation.
[1] https://github.com/ghyatzo/stockfish-line-sharpness
mtlmtlmtlmtl
3 hours ago
[ - ]
As a player I like to think of sharpness as a measure of the potential consequences of a miscalculation. In a main line dragon, the consequence is often getting checkmated in the near future, so maximally sharp. In a quiet positional struggle, the consequence might be something as minor as the opponent getting a strong knight, or ending up with a weak pawn.
Whereas complexity is a measure of how far ahead I can reasonably expect to calculate. This is something non-players often misunderstand, which is why they like to ask me how many moves ahead I can see. It depends on the position.
And I agree, these concepts are orthogonal. Positions can be sharp, complex, both or neither. A pawn endgame is typically very sharp; the slightest mistake can lead to the opponent queening and checkmating. But it's relativity low in complexity because you can calculate far ahead using ideas like counting, geometric patterns(square of the pawn, zone of the pawn, distant opposition etc) to abstract over long lines of play. On the opposite side, something like a main line closed Ruy Lopez is very complex(every piece still on the board), but not especially sharp(closed position, both kings are safe, it's more of a struggle for slight positional edges).
Something like a king's indian or benoni will be both sharp and complex. Whereas an equal rook endgame is neither(it's quite hard to lose a rook endgame, there always seems to be a way to save a draw).
nomilk
4 hours ago
[ - ]
Interested to read the code, but the link provided 404s
https://github.com/Amethyst-Cat/ChessComplexity/blob/master/...
tromp
4 hours ago
[ - ]
Amethyst-Cat apparently erased their github account, but the internet archive still has one snapshot [1]. The pdf link from there redirected to the davidtpeng account, but that github user no longer has a ChessComplexity repo and the internet archive only has a broken snapshot [2].
[1] https://web.archive.org/web/20201226113203/https://github.co...
[2] https://web.archive.org/web/20240316015417/https://github.co...
GistNoesis
1 hour ago
[ - ]
We should have solved chess already.
We should be aiming to solve chess, but we are not even trying.
If the complexity of chess is finite this is possible.
Chess AI have become so good that maybe there is no more progress to be made.
We must abandon the concept of "valuation".
Here is the criterium for solving chess.
A chess engine is a constant (or bounded) time, (and memory bounded) function f which takes any position and return either 1 "white win", 0 "draw", -1 "white lose".
A chess engine solve chess if we can't find any violation in the Bellman equation :
f(gamestate) = max over legal moves of ( -f(gamestate+move) ) if there are legal moves or f(gamestate) = result if there are no legal moves
This function f can be encoded either by a neural network or some code, but it must be computable in constant (or bounded) time.
The whole problem of solving chess is now simplified to mining the gamestate space for counter examples.
Like in math you can conjecture that your chess engine has solved the game and it stands until someone else find a violation of your game engine (either it doesn't compute in bounded time, or the bellman equation is invalid).
To verify a chess engine you can just sample a random gamestate, or a known to be difficult gamestate and check if the equation holds, that's at most max number of legal moves + 1, function evaluation.
You can try applying this concept to simple games like tic-tac-toe, or trying to compress endgame table with a neural network.
We can find such a candidate function by training a neural network by minimizing the current expected number of violation in the bellman equation over various dataset of gamestate. Once we "grok" it to zero we are done. To soften the problem you can train an auxilliary continuous function g which output the probability of 1, 0, or -1 (with a softmax) and add a discount factor like in Reinforcement Learning, but the final result is the discrete argmax of it (like in "deterministic policy gradient") with no discount factor.
Once you have this finite time oracle, playing chess is just wandering along the graph of drawable position to push your adversary into a position where his engine will have a violation of the bellman equation aka a mis-evaluation of the position where if he goes into it you will get into the winnable positions where you stay until the end. (Not all violations can be exploited as the adversary can sometime avoid going into "uncertain" positions).
A simpler (less strong) chess strategy may avoid going into "uncertain" positions as long as the position is unreachable because previous legal positions have a preferred choice. (4 state logic with win, draw, lose, uncertain). Or ordered list of moves. They make the problem easier but complexify the corresponding bellman equation.
So the game becomes once again exploring the space of "drawable" game positions in order to find positions which the adversary can't escape going into a uncertain (and losing) position. Aka playing the adversary and not the board which is an harder problem except if the adversary can play perfectly. Aka playing for the win.
mysecretaccount
1 hour ago
[ - ]
> We should have solved chess already. > We should be aiming to solve chess, but we are not even trying.
We are trying and we should not expect to solve it because the search space is massive. There are more legal games of chess than atoms in the universe.
GistNoesis
7 minutes ago
[ - ]
This is the precisely the point I am trying to make :
A candidate solution function can take a very small finite space : much smaller than the number of gamestates. And we can invalidate a candidate solution by finding a single counter example.
Current chess engine can't be invalidated quickly : they are not trying to solve chess. They are not falsifiable. They are not attempting to precisely define the frontier which is what I think where remaining efforts should be made.
We are just trying to encode the frontier like we would with a mandelbrot fractal.
Proving that a solution is valid is harder than finding a solution. Here I am suggesting we find the solution first.
Proving can also be done without exploring all legal chess positions. For example you can use branch and bound to cull vast amount of state space once you have your function. You just have to partition the state space and prove on each partition that the function is constant, for example when one side has 8 queen and the other has only a king with freedom of movement the position is winnable and you don't have to check every gamestate.
I am stating that there is a good chance that by searching for a function we will stumble upon one which has no counter example, because precisely the complexity of chess is not infinite (unproven conjecture (no-turing completeness of adversarial chess) ). We should be looking for it.
throw-qqqqq
41 minutes ago
[ - ]
> There are more legal games of chess than atoms in the universe
I’ll make an even stronger assertion:
There are more legal chess games in 40 moves or less, than there are atoms in the universe.
https://en.wikipedia.org/wiki/Shannon_number
https://skeptics.stackexchange.com/questions/4165/are-there-...
WJW
50 minutes ago
[ - ]
> If the complexity of chess is finite this is possible.
This is like saying the distance to Mars is finite so it should be possible to just go and live there. It's not theoretically impossible, but at the time it is practically impossible. There are real engineering challenges between here and there that have not yet been solved and from the looks of it, it will be at least several more decades before we get there.
In your example, you gloss over the construction of a "finite time oracle" by just saying "just train it until it is perfect". If humanity knew how to do that we could solve a whole other (more interesting) set of problems, but we don't.
taneq
29 minutes ago
[ - ]
"We should have solved Busy Beaver, if the complexity of BB(n) is finite this is possible."
I mean yeah, chess isn't THAT bad but still not directly tractable and besides, brute forcing it is boring.
SubiculumCode
5 hours ago
[ - ]
I was disappointed in the article, as I was primed for some 'complexity theory' type discussion, e.g. emergence,