7 ms·

What Is Complexity in Chess?

111 points by fzliu 1y ago

SubiculumCode 1y ago
I was disappointed in the article, as I was primed for some 'complexity theory' type discussion, e.g. emergence,
FacelessJim 1y 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 https://github.com/ghyatzo/stockfish-line-sharpness
- mtlmtlmtlmtl 1y 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).
  - DougBTX 1y ago
    > Whereas complexity is a measure of how far ahead I can reasonably expect to calculate So complexity is something like: high branching factor after culling “obvious” branches?
- toolslive 1y ago
  isn't sharpness just the opposite of quiescence ? https://www.chessprogramming.org/Quiescence_Search https://www.chessprogramming.org/Quiescence_Search
nomilk 1y ago
Interested to read the code, but the link provided 404s https://github.com/Amethyst-Cat/ChessComplexity/blob/master/A%20Metric%20of%20Chess%20Complexity.pdf https://github.com/Amethyst-Cat/ChessComplexity/blob/master/...
- tromp 1y 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.com/Amethyst-Cat/ChessComplexity/ https://web.archive.org/web/20201226113203/https://github.co... [2] https://web.archive.org/web/20240316015417/https://github.com/davidtpeng/ChessComplexity https://web.archive.org/web/20240316015417/https://github.co...
janalsncm 1y 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.
- nilslindemann 1y ago
  Seems like an excellent definition, mainly because I have no idea how to measure it otherwise. "Complexity is the time needed to solve a problem", why not.
  - Taek 1y ago
    Well, there are a lot of shortcuts built into engines like stockfish that don't perfectly mirror how beginners vs advanced players think. For example, certain types of piece forks are easy for newer players to spot (knight forking a king+rook on the back rank) and others are harder (bishop forking a king and a pawn in the late game when nobody is on the back rank), but stockfish is going to find both just as easily. So if you want to get deep into complexity you do need a model of different players and what types of advantages are easy to see for them.
    - nilslindemann 1y ago
      It could be done with e.g. the Maia engine, which was trained on Lichess games and plays like humans on different skill levels – https://www.maiachess.com/ https://www.maiachess.com/ – but I do not know if it supports different ponder depths. Edit: it seems it does not – https://github.com/CSSLab/maia-chess#:~:text=a%20nodes%20limit%20of%201%20is%20what%20we%20use https://github.com/CSSLab/maia-chess#:~:text=a%20nodes%20lim...
- chongli 1y ago
  evaluate positions at low depth and high depth and select positions where the best move switches. Won’t that bias in favour of common sacrifices in the endgame? The issue with using depth is that humans don’t struggle with depth uniformly. Humans can calculate to a lot more depth with a sequence of obvious moves (recaptures, pawn races) than they can in more complex situations (closed positions in the midgame).
chii 1y ago
This reminds me of this nice video : https://www.youtube.com/watch?v=YGLNyHd2w10 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.
- knuckleheads 1y ago
  That video has become an instant classic to me when it came out, very well made and explained. Very much influencing my thoughts as of late. Related to the article, I've also spent a few months before working on chess line/complexity visualization and explanation as a side project. The main outcome of this was https://www.schachzeit.com/en/openings/sicilian-defense https://www.schachzeit.com/en/openings/sicilian-defense. I haven't touched it beyond keeping it barely running for most of 2025, so a strong breeze would surely knock it over, but the experience of making it did teach me a lot about chess and computerized chess. The way the table at the bottom of these pages works is by running stockfish on not only the current position, but on the position after every possible legal move the first player could make. This increases the amount of computation needed by one or two orders of magnitude, as stockfish often does not explore every possible legal move so deeply. I was only doing it for lichess' openings lines, and it cost maybe $200 worth of computer processing time (can't recall the exact numbers). As far as I know (and I'm only someone who has spent a couple dozen hours with stockfish, a stockfish dev would know more) stockfish does not allow you easy access to the hash table that contains all the evaluations. I could not figure out how to get it to print out it's hash tables at all in order to get at the values deeper down in the complexity. I've considered forking stockfish and trying to get those values to be accessible somehow, in order to try and make visualizations like that video, and maybe someday I will. For now though, I think that's the technical piece missing, because otherwise one is forced to recompute every single node of the graph at the desired depth rather than running it once and getting back the values that have already been computed. Maybe someday, when I have more time, I'll take a shot at it, but not anytime soon I don't think.
  - le-mark 1y ago
GistNoesis 1y 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.
juujian 1y 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.
jrimbault 1y ago
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.
- imurray 1y ago
  Some things that may be of interest. First relevant to the posted article: A site that has used neural nets to classify go moves that good players would probably make that weaker players (of varying ranks) would probably not: https://neuralnetgoproblems.com/ https://neuralnetgoproblems.com/ (code available on github) https://ai-sensei.com/challenge https://ai-sensei.com/challenge (behind login wall, and in future possibly a pay wall) is a similar idea, but the difficulty of evaluating the position is determined by how users of the site perform in practice. And more generally, but relevant to your comment: Players can play humans at an appropriate rank on OGS https://online-go.com/ https://online-go.com/ (not as popular as the Eastern servers, but probably popular enough) -- or against calibrated rank "human-like" AI players by painfully setting up the right katago models themselves, or by paying for a subscription on ai-sensei.com A go education site that's currently largely by and pitched at Westerners: https://gomagic.org/ https://gomagic.org/ for leveling up from the basics. And a lot of books are now available easily and electronically in English (and some in German): https://gobooks.com/ https://gobooks.com/ --- I'd recommend "graded go problems for beginners", "tesuji", and "attack and defense". Some good sites aren't (fully) available in English, like https://www.101weiqi.com/ https://www.101weiqi.com/ -- but there are chrome and firefox extensions to translate just enough of it to make it usable. [To help search engines: go is also known as weiqi and baduk]
  - jrimbault 1y ago
    Thanks for the first link it's really fun game :) I've been playing lots on OGS (with my friend in particular), under my pseudonym erelde
FinnLobsien 1y ago
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.
- icelancer 1y ago
  > Those are the truly hard things in chess. Maybe this changes if you're a high-level player, but I'm not. They remain pretty difficult. Ben Finegold said it best when doing a lecture on middlegame technique; a novice complained that it's hard to figure out what to do in a positional battle and where to put all the pieces: "I got bad news for you - that's hard for us, too."
shelajev 1y ago
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 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
- icelancer 1y ago
  It is shockingly difficult to use LLMs in chess study. I don't need it to be a better (or worse) Stockfish; an LLM should be great at taking a FEN or multiple lines from Stockfish via MCP or tool call and explain why positions are evaluated the way they are, typical plans in the position (drawing from pretraining knowledge of a vast archive of games), and how to explain to a human to study these positions. I suspect that the large amount of chess pretraining data is not well synchronized with positions, because in books and articles the text is typically accompanied by pictures of the positions, NOT FENs / PGNs. So the training on the text is decoupled from the representation of the position. Regarding your tool call thing with stockfish/maia, I made a tool like this for myself called Blunder Sniper which iteratively feeds positions - that I'm likely to get given my openings - and recursively calls the lichess DB and finds the first time in the top 80% played moves in each chain where the opponents in the rating range blunder as the most common move in the chain. It was a fun way to use an alternative to engine-based preparation that many strong players use, which is something like Nibbler + lc0 and using contempt high values to find higher variance lines rather than game theory optimal ones. Some day I'll expand on the gpt-chess articles [0] that I found super interesting, fine-tune models... well, I keep telling myself that, anyway... [0]: https://dynomight.net/more-chess/ https://dynomight.net/more-chess/
EMM_386 1y ago
Check this out, it's quite a funny chess engine. Yes, funny! Good moves against Stockfish. https://boristrapsky.com/ https://boristrapsky.com/ > 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.
bambax 1y ago
> 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...
- branko_d 1y ago
  > ...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).
  - LegionMammal978 1y ago
    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/Stockfish-FAQ.html https://official-stockfish.github.io/docs/stockfish-wiki/Sto...
- 1y ago
jll29 1y ago
The "algorithm in the full proposal here" pointing to: https://github.com/Amethyst-Cat/ChessComplexity/blob/master/A%20Metric%20of%20Chess%20Complexity.pdf seems gone.
- mdaniel 1y ago
  Wayback spotted some of it, but after bouncing through its 302 capture one ends up here, but yes, the actual repo is still gone and the "in page" snapshot doesn't render the actual pdf: https://web.archive.org/web/20220917133741/https://github.com/davidtpeng/ChessComplexity/blob/master/A%20Metric%20of%20Chess%20Complexity.pdf https://web.archive.org/web/20220917133741/https://github.co... Also, after some url surgery it seems Wayback did grab the .tar.gz of a release <https://web.archive.org/web/20201226113237/https://codeload.github.com/Amethyst-Cat/ChessComplexity/tar.gz/v1.2-alpha https://web.archive.org/web/20201226113237/https://codeload....> but sadly it does not include the pdf, only some .png and a helpfully named "Software/blank", and also an "asset" of ChessOracle1.2.zip containing the .h5 weights but no pdf to be seen
hamilton-wp 1y ago
Almost all amateur chess games are decided by a mistake at six ply or less. So to emulate lower rated players just occasionally flip the evaluation after a depth of 4-6 ply.

111 points by fzliu 1y ago

I was disappointed in the article, as I was primed for some 'complexity theory' type discussion, e.g. emergence,

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 https://github.com/ghyatzo/stockfish-line-sharpness

mtlmtlmtlmtl 1y 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).
- DougBTX 1y ago
  > Whereas complexity is a measure of how far ahead I can reasonably expect to calculate So complexity is something like: high branching factor after culling “obvious” branches?
toolslive 1y ago
isn't sharpness just the opposite of quiescence ? https://www.chessprogramming.org/Quiescence_Search https://www.chessprogramming.org/Quiescence_Search

nomilk 1y ago

Interested to read the code, but the link provided 404s https://github.com/Amethyst-Cat/ChessComplexity/blob/master/A%20Metric%20of%20Chess%20Complexity.pdf https://github.com/Amethyst-Cat/ChessComplexity/blob/master/...

tromp 1y 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.com/Amethyst-Cat/ChessComplexity/ https://web.archive.org/web/20201226113203/https://github.co... [2] https://web.archive.org/web/20240316015417/https://github.com/davidtpeng/ChessComplexity https://web.archive.org/web/20240316015417/https://github.co...

janalsncm 1y 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.

nilslindemann 1y ago
Seems like an excellent definition, mainly because I have no idea how to measure it otherwise. "Complexity is the time needed to solve a problem", why not.
- Taek 1y ago
  Well, there are a lot of shortcuts built into engines like stockfish that don't perfectly mirror how beginners vs advanced players think. For example, certain types of piece forks are easy for newer players to spot (knight forking a king+rook on the back rank) and others are harder (bishop forking a king and a pawn in the late game when nobody is on the back rank), but stockfish is going to find both just as easily. So if you want to get deep into complexity you do need a model of different players and what types of advantages are easy to see for them.
  - nilslindemann 1y ago
    It could be done with e.g. the Maia engine, which was trained on Lichess games and plays like humans on different skill levels – https://www.maiachess.com/ https://www.maiachess.com/ – but I do not know if it supports different ponder depths. Edit: it seems it does not – https://github.com/CSSLab/maia-chess#:~:text=a%20nodes%20limit%20of%201%20is%20what%20we%20use https://github.com/CSSLab/maia-chess#:~:text=a%20nodes%20lim...
chongli 1y ago
evaluate positions at low depth and high depth and select positions where the best move switches. Won’t that bias in favour of common sacrifices in the endgame? The issue with using depth is that humans don’t struggle with depth uniformly. Humans can calculate to a lot more depth with a sequence of obvious moves (recaptures, pawn races) than they can in more complex situations (closed positions in the midgame).

chii 1y ago

This reminds me of this nice video : https://www.youtube.com/watch?v=YGLNyHd2w10 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.

knuckleheads 1y ago
That video has become an instant classic to me when it came out, very well made and explained. Very much influencing my thoughts as of late. Related to the article, I've also spent a few months before working on chess line/complexity visualization and explanation as a side project. The main outcome of this was https://www.schachzeit.com/en/openings/sicilian-defense https://www.schachzeit.com/en/openings/sicilian-defense. I haven't touched it beyond keeping it barely running for most of 2025, so a strong breeze would surely knock it over, but the experience of making it did teach me a lot about chess and computerized chess. The way the table at the bottom of these pages works is by running stockfish on not only the current position, but on the position after every possible legal move the first player could make. This increases the amount of computation needed by one or two orders of magnitude, as stockfish often does not explore every possible legal move so deeply. I was only doing it for lichess' openings lines, and it cost maybe $200 worth of computer processing time (can't recall the exact numbers). As far as I know (and I'm only someone who has spent a couple dozen hours with stockfish, a stockfish dev would know more) stockfish does not allow you easy access to the hash table that contains all the evaluations. I could not figure out how to get it to print out it's hash tables at all in order to get at the values deeper down in the complexity. I've considered forking stockfish and trying to get those values to be accessible somehow, in order to try and make visualizations like that video, and maybe someday I will. For now though, I think that's the technical piece missing, because otherwise one is forced to recompute every single node of the graph at the desired depth rather than running it once and getting back the values that have already been computed. Maybe someday, when I have more time, I'll take a shot at it, but not anytime soon I don't think.
- le-mark 1y ago

GistNoesis 1y 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.

juujian 1y 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.

jrimbault 1y ago

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.

imurray 1y ago
Some things that may be of interest. First relevant to the posted article: A site that has used neural nets to classify go moves that good players would probably make that weaker players (of varying ranks) would probably not: https://neuralnetgoproblems.com/ https://neuralnetgoproblems.com/ (code available on github) https://ai-sensei.com/challenge https://ai-sensei.com/challenge (behind login wall, and in future possibly a pay wall) is a similar idea, but the difficulty of evaluating the position is determined by how users of the site perform in practice. And more generally, but relevant to your comment: Players can play humans at an appropriate rank on OGS https://online-go.com/ https://online-go.com/ (not as popular as the Eastern servers, but probably popular enough) -- or against calibrated rank "human-like" AI players by painfully setting up the right katago models themselves, or by paying for a subscription on ai-sensei.com A go education site that's currently largely by and pitched at Westerners: https://gomagic.org/ https://gomagic.org/ for leveling up from the basics. And a lot of books are now available easily and electronically in English (and some in German): https://gobooks.com/ https://gobooks.com/ --- I'd recommend "graded go problems for beginners", "tesuji", and "attack and defense". Some good sites aren't (fully) available in English, like https://www.101weiqi.com/ https://www.101weiqi.com/ -- but there are chrome and firefox extensions to translate just enough of it to make it usable. [To help search engines: go is also known as weiqi and baduk]
- jrimbault 1y ago
  Thanks for the first link it's really fun game :) I've been playing lots on OGS (with my friend in particular), under my pseudonym erelde

FinnLobsien 1y ago

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.

icelancer 1y ago
> Those are the truly hard things in chess. Maybe this changes if you're a high-level player, but I'm not. They remain pretty difficult. Ben Finegold said it best when doing a lecture on middlegame technique; a novice complained that it's hard to figure out what to do in a positional battle and where to put all the pieces: "I got bad news for you - that's hard for us, too."

shelajev 1y ago

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 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

icelancer 1y ago
It is shockingly difficult to use LLMs in chess study. I don't need it to be a better (or worse) Stockfish; an LLM should be great at taking a FEN or multiple lines from Stockfish via MCP or tool call and explain why positions are evaluated the way they are, typical plans in the position (drawing from pretraining knowledge of a vast archive of games), and how to explain to a human to study these positions. I suspect that the large amount of chess pretraining data is not well synchronized with positions, because in books and articles the text is typically accompanied by pictures of the positions, NOT FENs / PGNs. So the training on the text is decoupled from the representation of the position. Regarding your tool call thing with stockfish/maia, I made a tool like this for myself called Blunder Sniper which iteratively feeds positions - that I'm likely to get given my openings - and recursively calls the lichess DB and finds the first time in the top 80% played moves in each chain where the opponents in the rating range blunder as the most common move in the chain. It was a fun way to use an alternative to engine-based preparation that many strong players use, which is something like Nibbler + lc0 and using contempt high values to find higher variance lines rather than game theory optimal ones. Some day I'll expand on the gpt-chess articles [0] that I found super interesting, fine-tune models... well, I keep telling myself that, anyway... [0]: https://dynomight.net/more-chess/ https://dynomight.net/more-chess/

EMM_386 1y ago

Check this out, it's quite a funny chess engine. Yes, funny! Good moves against Stockfish. https://boristrapsky.com/ https://boristrapsky.com/ > 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.

bambax 1y ago

> 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...

branko_d 1y ago
> ...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).
- LegionMammal978 1y ago
  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/Stockfish-FAQ.html https://official-stockfish.github.io/docs/stockfish-wiki/Sto...
1y ago

jll29 1y ago

The "algorithm in the full proposal here" pointing to: https://github.com/Amethyst-Cat/ChessComplexity/blob/master/A%20Metric%20of%20Chess%20Complexity.pdf seems gone.

mdaniel 1y ago
Wayback spotted some of it, but after bouncing through its 302 capture one ends up here, but yes, the actual repo is still gone and the "in page" snapshot doesn't render the actual pdf: https://web.archive.org/web/20220917133741/https://github.com/davidtpeng/ChessComplexity/blob/master/A%20Metric%20of%20Chess%20Complexity.pdf https://web.archive.org/web/20220917133741/https://github.co... Also, after some url surgery it seems Wayback did grab the .tar.gz of a release <https://web.archive.org/web/20201226113237/https://codeload.github.com/Amethyst-Cat/ChessComplexity/tar.gz/v1.2-alpha https://web.archive.org/web/20201226113237/https://codeload....> but sadly it does not include the pdf, only some .png and a helpfully named "Software/blank", and also an "asset" of ChessOracle1.2.zip containing the .h5 weights but no pdf to be seen

hamilton-wp 1y ago

Almost all amateur chess games are decided by a mistake at six ply or less. So to emulate lower rated players just occasionally flip the evaluation after a depth of 4-6 ply.