What Is Complexity in Chess?

This discussion revolves around the concepts of "sharpness" and "complexity" in chess, and broader philosophical points about "solving chess."

Defining Sharpness and Complexity

A core theme is the attempt to define and differentiate between "sharpness" and "complexity" in chess positions. Participants generally agree that these are distinct but often related concepts.

• Sharpness: This is often described as the measure of the potential consequences of a miscalculation.

  • "As a player I like to think of sharpness as a measure of the potential consequences of a miscalculation," says mtlmtlmtlmtl.
  • mtlmtlmtlmtl elaborates, "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."
  • toolslive questions, "isn't sharpness just the opposite of quiescence?" referencing a fishing concept.
  • FinnLobsien observes, "Things like sacrifice lines. Those feel complicated, but the calculation eventually becomes pretty deterministic."

• Complexity: This is viewed as the difficulty in calculating ahead, often related to the branching factor of possible moves.

  • mtlmtlmtlmtl states, "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."
  • DougBTX offers a defining question: "> Whereas complexity is a measure of how far ahead I can reasonably expect to calculate\n\nSo complexity is something like: high branching factor after culling “obvious” branches?"
  • mtlmtlmtlmtl contrasts it with sharpness using examples: "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)."
  • mtlmtlmtlmtl also categorized other openings: "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)."
  • juujian describes difficult positions as those where "at the surface it seems that there are many viable moves to be analyzed." They also mention scenarios like "when you're in a closed position and there are many, many micro adjustments you could make."

The Goal of Solving Chess and AI Approaches

A significant portion of the discussion centers on the feasibility and current efforts towards "solving chess." Users debate whether it's possible, what it truly means, and how current AI approaches contribute or fall short.

• Ambition vs. Current Practice: Several users express a belief that chess should be solved, and that current efforts are misdirected.

  • GistNoesis makes a bold statement: "> We should have solved chess already.\nWe should be aiming to solve chess, but we are not even trying."
  • GistNoesis further criticizes current engines: "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."
  • GistNoesis proposes a method: "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."

• The Scale of Chess and Practicality: Counterarguments highlight the immense scale of chess and the practical impossibility of brute-force solutions or perfect calculation.

  • mysecretaccount pushes back: "> We should have solved chess already.\n> We should be aiming to solve chess, but we are not even trying.\n\nWe 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."
  • throw-qqqqq reinforces this point: "I’ll make an even stronger assertion:\nThere are more legal chess games in 40 moves or less, than there are atoms in the universe."
  • WJW likens it to reaching Mars: "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." WJW also points out the unaddressed engineering challenges in creating a "finite time oracle."

• Defining "Solved": The discussion touches on what a "solved" game truly entails.

  • GistNoesis defines it as: "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"." This function must satisfy the Bellman equation.
  • tsimionescu offers a different perspective on current capabilities: "We know exactly how to solve chess, we have known for decades. The function f is called min-max, and can be optimized with things like alpha pruning. Given that chess is a bounded game, this is a bounded time and bounded space algorithm." However, they note the prohibitive computational time: "it would still take some few thousand years of computation time to actually run it to solve chess."

• AI Training and Evaluation: The methods of training AI for chess are also debated, particularly regarding achieving "perfection."

  • GistNoesis argues that current AI "are not aiming for perfection." They suggest a focus on "hard mining samples, game states which define the frontier," implying a more targeted approach to finding counterexamples and retraining.
  • tsimionescu suggests that for most people, the interest lies not in a perfectly playing machine, but in the human-like strategies and entertainment value. "The whole interest was in beating human players with human-like strategies, which has thoroughly been achieved."

Code and Resource Availability

A minor but present theme is the lack of access to the cited code and research.

• nomilk notes, "Interested to read the code, but the link provided 404s."
• tromp provides details about the difficulties in accessing the original work: "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]."

Other Related Concepts

• Player Skill Differentiation: janalsncm suggests that the author of the original article might be looking for positions that reveal differences in skill levels: "The author is looking for positions which are difficult for low rated players and easier for high rated players." They propose a method of comparing evaluations at low and high depths.
• State Space and "Getting Lost": chii references a video that uses state space to explain game difficulty: "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."
• Go as an Alternative: jrimbault expresses a fondness for Go and a wish for more skilled players and attention to it in the West, citing it as a "beautiful game with a really nice balance."
• Beginner vs. Advanced Concepts: FinnLobsien contrasts what looks hard to beginners (like sacrifice lines) with what is truly hard for them (positional advantages like piece activity).