alt Hacker NewsWhat Is Complexity in Chess?
Comments
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.
I recently was trying to build an AI assistant to help with various chess things, which took shape of an MCP server: https://github.com/shelajev/mcp-stockfish
it builds as a docker image which has stockfish and maia (maiachess.com) together with different weights so it can simulate lower-level players.
It was a fun exercise, I tried a bunch of local models with this MCP server, which isn't particularly optimized, but also doesn't seem that bad. And the results were quite disappointing, they often would invent chess related reasoning and mess up answering questions, even if you'd expect them to rely on the tools and have true evaluation available.
It was also fun to say things: fetch a random game by username 'X' from lichess, analyze it and find positions which are good puzzles for a player rated N.
and see it figure out the algorithm of tool calls: - fetch the game - feed the moves to stockfish - find moves where evaluation changed sharply - feed it to maia at strength around N and to stockfish - if these disagree, it's probably a good puzzle.
I don't think I got to have a working setup like that even with managed cloud models. Various small issues, like timeouts on the MCP calls, general unreliability, etc. Then lost interest and abandoned the idea.
I should try again after seeing this thread
I've been quite taken with Go these last few months and I wish the western world had more skilled players. The Asian servers do not do much (if any) i18n, they don't need to, they aren't many players outside Asia.
I've been fortunate that one of my high school friends is a 4 dan EGF player and that he has taken lots of time to play with me and teach me. But I can see other beginners struggling with the basics because they're only playing other low-skilled players.
I wish the western world paid Go more attention, it's a beautiful game with a really nice balance.
> 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...
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.
I always thought that there's some stuff that looks hard in chess, but is actually not so difficult. Things like sacrifice lines. Those feel complicated, but the calculation eventually becomes pretty deterministic.
The things that don't look hard to beginners (because there's no immediate danger) are usually questions around activity and positional advantages. Should you get rid of your opponent's central knight, but give them your long-range bishop? Should you take with the pawn in the center and explode the position or bring the rook behind it first?
Those are the truly hard things in chess. Maybe this changes if you're a high-level player, but I'm not.
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.
Interested to read the code, but the link provided 404s
https://github.com/Amethyst-Cat/ChessComplexity/blob/master/...
The "algorithm in the full proposal here" pointing to:
https://github.com/Amethyst-Cat/ChessComplexity/blob/master/A%20Metric%20of%20Chess%20Complexity.pdf
Check this out, it's quite a funny chess engine. Yes, funny!
Good moves against Stockfish.
> Here, most bots would play a very strong 11. c7d5 NxPch. Ha! Why drag things out? Instead, I played 11. e3e4 P-K4, guessing that black---with only two minutes left on his clock---might grab the king pawn, and suffer an immediate checkmate. Black did not. I was so enraged that I shouted "110111001110111101000", which I admit was unsportsmanlike conduct.
I was disappointed in the article, as I was primed for some 'complexity theory' type discussion, e.g. emergence,
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.
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.