Pages in this blog

Thursday, March 7, 2024

AI, Chess, and Language 1: Two VERY Different Beasts

Chess has been with AI since the beginning. In fact, computer chess all but beats the origins of the term “artificial intelligence,” which was coined for the well-known 1956 Dartmouth summer research program. According to this timeline in Wikipedia the possibility of a mechanical chess device dates back to the 18th century with a chess-playing automaton which, however, was operated by a human concealed inside it. A number of other mechanical hacks appeared before Norbert Wiener, Claude Shannon, and Alan Turing theorized about computational chess engines. John McCarthy invented the alpha-beta search algorithm in 1956, the same year as the AI conference, and the first programs to play a full game emerged a year later, in 1957. That was also the year that Chomsky published Syntactic Structures and the Russians launched Sputnik (which I was able to observe from my backyard).

Meanwhile, in 1949 Roberto Busa got IBM to sponsor a project to create a computer-generated concordance to the works of Thomas Acquinas, the Index Thomisticus. Thus the so-called digital humanities were born. That same year Warren Weaver, who was head of the Rockefeller Foundation at the time, wrote a memorandum in which he proposed a statistical rationale for machine translation. In 1952 Yehoshua Bar-Hillel, an Israeli logician, organized the first conference in machine translation at MIT’s Research Laboratory for Electronics and two years later IBM demonstrated the automatic translation of bits of Russian text into English (Nilsson 2010, p. 148).

The chess gang theorized that, as chess exemplified the highest form of human intelligence, when AI had succeeded in beating the best humans at chess, full artificial intelligence would have been achieved. In 1997 IBM’s Deep Blue beat Garry Kasparov decisively. Ever since then computers have been the best chess players in the world. But computer performance on language tasks has lagged far behind chess performance. The recent development of transformer-based large language models (LLMs) has resulted in a quantum leap in linguistic performance for computers, but the writing, though fluent, is also pedestrian (with various exceptions we need not go into). It would seem that there is a profound difference between the computational requirements of chess and those of language.The difference is not simply a matter of raw compute, with language requiring more, much more. There is also a fundamental, and perhaps even irreducible, difference in the way that compute is orchestrated computationally.

This post offers some quick observations about that difference. I discuss chess first, then language. While I’m a fluent speaker and writer of English, and know a bit about computational linguistics as well, I don’t play chess (though I do know the rules) and I know little about computer chess. I had a brief session with ChatGPT about chess. I’ve included that as an appendix.

Chess as a computational problem

While chess is a fairly cerebral game, it is a game played in the physical world using a board and game pieces. Let us call that chess’s geometric footprint. When we get to language we’ll talk about language’s geometric footprint, which is quite different from chess’s. The rules of chess can be defined with respect to its geometric footprint:

  • There are two players, who alternate moves.
  • It is played on an 8 by 8 board.
  • Each player has 8 16 pieces distributed over 7 types.
  • The moves of each type are rigidly and unambiguously specified.
  • There are other rules regarding games play among those pieces on the board.

The only constraint the players are subject to is the constraint that they obey the rules of the game. Any move that is consistent with the rules is permitted.

Given that the number of squares on the board is finite, the number of pieces is finite, that each play involves finite movement on the board, and that a convention is adopted to terminate play in the case no pieces are being exchanged, the total number of possible chess games is finite and takes the form of a tree.

To play chess at even a quite modest level one must have a repertoire of tactics and strategies that are not specified by the rules. Chess is a game where there is a game where there is a strict distinction between the basic rules and what we might call the elaboration, that is, the tactics and strategies governing games play. As a practical matter, large ill-defined areas of the chess tree are unexplored because, once a player moves into any of those areas, they will lose to a superior opponent. In particular, the opening of a game is quite restricted, not by the rules, but by well-known tactical considerations.

Given that the game is defined in terms of its geometric footprint, and that all possible chess games can be enumerated in the form of a tree, it follows that a person’s ability to play chess depends on how well they know the chess tree. However it is that they represent this tree in their minds is, at this point, a secondary issue. Given two players, if one of them knows a larger and more interesting (however one specifies interesting, a difficult problem) region of the chess board than the other, they will consistently win over the other.

It follows therefore, that since computers now consistently beat even the best of human players, they have explored regions of the chess tree that no human player has.

Language as a computational problem

Now let us consider human language. It has a geometric footprint as well, which is given in language’s relationship to the natural world. The meaning of a good many words is given directly by physical phenomena; much of so-called common-sense knowledge is like this. Unlike the geometric footprint of chess, which is small, simple, and well-defined, the geometric footprint of language is large, complex, and poorly defined. I would note further that words that are not given their primary meaning in physical terms as given in the human sensorium can be given meaning by various means, including patterns of words and patterns which include formal symbols as well, symbols from mathematics, chemistry, physics, and so forth. On this last point, see various posts tagged metalingual definition, and two papers that I wrote with David Hays:

William Benzon and David Hays, Metaphor, Recognition, and Neural Process, The American Journal of Semiotics, Vol. 5, No. 1 (1987), 59-80, https://www.academia.edu/238608/Metaphor_Recognition_and_Neural_Process

William Benzon and David Hays, The Evolution of Cognition, Journal of Social and Biological Structures. 13(4): 297-320, 1990, https://www.academia.edu/243486/The_Evolution_of_Cognition

It is thus difficult to make a firm distinction between the basic rules of language and the elaboration. While the number of possible chess games is finite, though it is so large that we cannot list it. It makes little sense to talk of listing all possible language texts. The number is unbounded and the set is not enumerable.

The basic rules of chess are so simple that computers need not play chess by moving physical pieces around on a board; a purely symbolic notation is entirely adequate. The training of LLMs does not involve access to the physical world. But the geometric footprint of language so constrains semantic relationships that LLMs can induce a suitable approximation of those relationships given a sufficiently large training corpus. But we have no way of determining whether or not an LLM can generate any possible text. Nor do we have any reason to believe that LLMs can generate any text that can be generated by human having full access to the physical world. In fact, given the problems that LLMs have with common-sense knowledge, we have reason to believe that LLMs are more limited in their capacities than the collectivity of humans.

Computationally, chess and natural language are very different beasts. The former is tractable and considered solved while the latter is still somewhat mysterious. Chess was solved by the methods of classical symbolic computing, methods which we understand. We know how classical chess engines work. But the newer neural network chess engines are black boxes, as are LLMs. We don’t (yet) know how they work. Moreover, while it is clear the LLMs are more generally successful with language than the old symbolic systems were, it does seem that the older symbolic systems are better at some kinds of reasoning and planning tasks and it is not obvious that LLMs can acquire those capacities.

Two kinds of computing and an exercise for the reader

I have written various posts about the work of Miriam Yevick. See, for example: Toward a Theory of Intelligence: Did Miriam Yevick know something in 1975 that Bengio, LeCun, and Hinton did not know in 2018? In particular, Yevick proved that in the task of visual identification, symbolic systems (like old-style chess engines) are better than neural nets. Does her result generalize across the whole range of tasks we would require of our intelligence engines? If so, then it means that we cannot reach AGI (whatever that is) simply by making larger and larger LLMs.

Appendix: ChatGPT on computer chess

Is there any evidence that good computer chess programs sometimes play differently than the best humans?

Yes, there is evidence that computer chess programs, especially the strongest ones, can play differently than the best human players. Computer chess engines rely on brute-force calculations and sophisticated algorithms to evaluate positions and make decisions, while human players often rely on intuition, pattern recognition, and strategic understanding.


Some key differences between computer and human chess play include:

  1. Depth of Calculation: Computers can analyze a much larger number of positions per second than humans. They can explore deeper into variations and calculate more accurately, especially in tactical positions. Humans may rely more on intuition and general principles when faced with complex positions.
  2. Endgame Precision: Computer chess engines are known for their exceptional endgame play. They can navigate complex endgame positions with precise calculations, exploiting even the smallest advantages. Humans may struggle more in certain endgames due to the complexity of certain positions.
  3. Opening Knowledge: Computer programs have access to extensive opening databases and can memorize vast amounts of opening theory. Humans may not have the same level of memorization and might rely on understanding the underlying principles of the openings.
  4. Evaluation of Material imbalances: Computers are generally better at evaluating positions with material imbalances and determining the dynamic factors that compensate for these imbalances. Human players might have a different approach and rely on their understanding of typical plans and piece activity.
  5. Style of Play: Computer programs don't have a distinct playing style like humans. They can switch between aggressive and defensive strategies based on the position and evaluation. Humans, on the other hand, may have a unique playing style influenced by their personal preferences and strengths.

While computers have surpassed humans in terms of raw calculation and opening preparation, they may lack the intuitive and creative aspects of human play. The differences in playing style and decision-making between the two are often highlighted in matches where top-level humans compete against advanced chess engines.

Can you tell me more about #5, style of play, naming some of the computer engines involved.

Certainly! When discussing the style of play in computer chess engines, it's important to note that many modern engines are versatile and can adapt their playstyle based on the position and evaluation. However, some engines have developed reputations for certain characteristics. Here are a few examples:

  1. Stockfish:
    • Style: Stockfish is known for its extremely strong and versatile play. It excels in complex tactical positions and is known for its ability to calculate deeply. Stockfish is often considered an aggressive and dynamic engine.
  2. AlphaZero:
    • Style: AlphaZero, developed by DeepMind, takes a different approach. It uses machine learning and reinforcement learning techniques to teach itself how to play chess. AlphaZero is known for its unique and creative style, often sacrificing material for long-term positional advantages. It has a more human-like, intuitive approach to the game.
  3. Komodo:
    • Style: Komodo is known for its solid and strategic play. It places a strong emphasis on evaluation and positional understanding. Komodo is often considered a balanced engine, capable of handling various types of positions.
  4. Houdini:
    • Style: Houdini is known for its tactical strength and resourcefulness. It often excels in complicated, dynamic positions where precise calculation is required. Houdini is considered one of the top engines for tactical play.
  5. Leela Chess Zero (LCZero):
    • Style: Similar to AlphaZero, LCZero uses a neural network-based approach. It is known for its unique and creative play, often introducing novel ideas and unconventional moves. LCZero combines deep positional understanding with tactical awareness.

It's important to note that these descriptions are generalizations, and the strength of modern engines often lies in their ability to adapt to various positions. Additionally, as new versions and updates are released, the characteristics of these engines may evolve. The distinctions in playing style are more apparent when comparing games played by these engines against each other or against human players with distinct styles.

Have humans learned anything from studying how chess engines play?

Absolutely, studying how chess engines play has significantly influenced and enhanced human understanding of chess. Here are several key areas where humans have learned from analyzing chess engines:

  1. Opening Theory and Preparation:
    • Chess engines have massively expanded opening theory by exploring vast databases of games and assessing the strengths and weaknesses of various opening lines. Human players can benefit from the deep analysis provided by engines to refine and update their opening repertoire.
  2. Endgame Techniques:
    • Chess engines excel in endgame play, demonstrating precise calculations and optimal strategies. Human players have learned valuable endgame techniques, including the importance of king activity, pawn structure, and converting advantages into victories.
  3. Tactics and Calculation:
    • Chess engines are exceptionally strong in tactical play and calculations. Studying engine games helps human players improve their tactical awareness, visualization skills, and the ability to calculate variations accurately.
  4. Positional Understanding:
    • Engines have a strong grasp of positional principles, evaluating the imbalances in a position and understanding the subtleties of pawn structures. Human players can learn from the engines' ability to assess strategic plans and maneuver pieces effectively.
  5. Defense and Resourcefulness:
    • Chess engines are renowned for their defensive skills and resourcefulness. Humans can learn valuable defensive techniques by studying how engines navigate difficult positions and defend against strong attacks.
  6. Evaluation of Imbalances:
    • Chess engines are proficient at evaluating material imbalances and understanding the dynamic factors that compensate for them. Human players can gain insights into the importance of piece activity, initiative, and king safety in positions with material asymmetry.
  7. Preparation for Opponents:
    • Analyzing games between top-level human players and chess engines has become a crucial tool for players to prepare for their opponents. Understanding how engines approach different types of positions can help players anticipate and respond to specific strategic ideas.
  8. Human-Computer Collaboration:
    • Some chess players have embraced the idea of using chess engines as training partners, combining the strengths of both human intuition and computer calculations. This collaborative approach has led to new training methods and insights into how humans and computers can complement each other.

Overall, the study of chess engines has had a profound impact on the way chess is played and understood at the highest levels. It has influenced training methodologies, opening preparation, and strategic thinking, contributing to the continuous evolution of chess knowledge.

As you know, chess is a finite game when played with a convention for stopping play if no pieces have been exchanged after so many moves. Given that, all possible chess games can be organized in the form of a tree. But the tree is far too large to be explored completely. Does the fact that computer engines sometimes employ different styles of play mean that they’ve explored regions of the chess tree that humans haven’t?

ChatGPT generated two responses to this prompt. I have included both of them.


RESPONSE ONE

Yes, the fact that computer chess engines sometimes employ different styles of play compared to humans can indeed be attributed to the engines exploring regions of the chess tree that humans may not have extensively explored or fully understood. The vastness of the game tree in chess, even with its finite number of possible positions, makes it practically impossible for humans to explore every branch thoroughly.

Chess engines, particularly the more advanced ones using powerful hardware and sophisticated algorithms, have the capability to explore deeper and analyze more positions in a shorter amount of time. This allows them to uncover subtleties, novelties, and strategic nuances that might be beyond the reach of human players. Here are a few reasons why computer engines might explore different regions of the chess tree:

  1. Deep Tactical Calculations:
    • Chess engines excel in deep tactical calculations, enabling them to uncover intricate tactical possibilities and combinations that might be overlooked by humans. This leads to more accurate and resourceful play, especially in complex positions.
  2. Novel Opening Ideas:
    • Computer engines have significantly expanded opening theory by exploring less conventional or even novel lines. These lines might be less explored by human players, and the engines can introduce fresh ideas that challenge established norms.
  3. Objective Evaluation:
    • Engines provide objective evaluations based on concrete calculations and positional assessments. They can accurately evaluate positions with material imbalances, dynamic factors, and strategic subtleties, often leading to different judgments compared to human intuition.
  4. Positional Understanding:
    • The engines' ability to understand and navigate intricate positional nuances can lead to different strategic plans and approaches. They may uncover plans and maneuvers that humans might not have considered due to the complexity of certain positions.
  5. Resourcefulness and Defense:
    • Chess engines are known for their resourcefulness in defense. They can find subtle defensive resources and counterplay in difficult positions, influencing their playing style in ways that might differ from human players.

While computer engines explore vast portions of the chess tree, it's essential to highlight that their play is not inherently "better" than human play. Rather, it represents a different approach and a complementary tool for human players to enhance their understanding of the game. The collaboration between humans and computers in chess has led to a deeper and more nuanced exploration of the game's possibilities.

RESPONSE TWO

Yes, the fact that computer chess engines sometimes employ different styles of play does suggest that they may have explored regions of the chess tree that humans haven't extensively covered. The vast size of the chess game tree makes it impossible for humans to explore all possible variations thoroughly. Computer engines, with their ability to perform massive calculations and analyze positions deeply, can venture into uncharted territory and discover novel ideas and plans.

Here are a few reasons why computer engines might explore different regions of the chess tree compared to humans:

  1. Deep Calculation and Exhaustive Analysis:
    • Computers can evaluate positions much deeper than humans, exploring variations that may involve complex tactical sequences or intricate positional ideas. This allows them to uncover resources and strategic concepts that might be overlooked by human players.
  2. Unconventional Moves and Plans:
    • Chess engines, particularly those based on neural networks like AlphaZero and LCZero, can exhibit more creative and unconventional play. They may introduce novel moves or plans that defy traditional human understanding, leading to innovative approaches in certain positions.
  3. Objective Evaluation:
    • Computers assess positions objectively based on mathematical evaluations rather than subjective human biases. This objectivity allows them to consider unconventional ideas that may not align with established human theories or principles.
  4. Learning from Self-Play:
    • Machine learning-based engines, such as AlphaZero, can learn from self-play, continuously refining their understanding of the game. This iterative learning process enables them to discover new strategies and improve their play over time.
  5. Exploration of Openings and Endgames:
    • Chess engines contribute significantly to opening theory by exploring vast databases of games and evaluating positions objectively. They can also delve deeply into endgames, uncovering optimal strategies and techniques.

It's important to note that while computer engines can explore vast portions of the chess tree, human intuition, creativity, and strategic understanding remain essential aspects of chess play. The styles of play exhibited by engines often serve as sources of inspiration for human players, encouraging them to consider unconventional ideas and broaden their understanding of the game. The interplay between human and computer analysis contributes to the continuous evolution of chess theory and practice.

No comments:

Post a Comment