Mastering Board Games by External and Internal Planning with Language Models

• URL: http://arxiv.org/abs/2412.12119v1
• Date: Mon, 02 Dec 2024 18:56:51 GMT
• Title: Mastering Board Games by External and Internal Planning with Language Models
• Authors: John Schultz, Jakub Adamek, Matej Jusup, Marc Lanctot, Michael Kaisers, Sarah Perrin, Daniel Hennes, Jeremy Shar, Cannada Lewis, Anian Ruoss, Tom Zahavy, Petar Veličković, Laurel Prince, Satinder Singh, Eric Malmi, Nenad Tomašev,
• Abstract summary: We show that search-based planning can significantly improve LLMs' playing strength across several board games. In external search, the model guides Monte Carlo Tree Search rollouts and evaluations without calls to an external engine, and in internal search, the model directly generates in-context a linearized tree of potential futures. Both build on a language model pre-trained on relevant domain knowledge, capturing the transition and value functions across these games.
• Score: 30.782334791241556
• License:
• Abstract: While large language models perform well on a range of complex tasks (e.g., text generation, question answering, summarization), robust multi-step planning and reasoning remains a considerable challenge for them. In this paper we show that search-based planning can significantly improve LLMs' playing strength across several board games (Chess, Fischer Random / Chess960, Connect Four, and Hex). We introduce, compare and contrast two major approaches: In external search, the model guides Monte Carlo Tree Search (MCTS) rollouts and evaluations without calls to an external engine, and in internal search, the model directly generates in-context a linearized tree of potential futures and a resulting final choice. Both build on a language model pre-trained on relevant domain knowledge, capturing the transition and value functions across these games. We find that our pre-training method minimizes hallucinations, as our model is highly accurate regarding state prediction and legal moves. Additionally, both internal and external search indeed improve win-rates against state-of-the-art bots, even reaching Grandmaster-level performance in chess while operating on a similar move count search budget per decision as human Grandmasters. The way we combine search with domain knowledge is not specific to board games, suggesting direct extensions into more general language model inference and training techniques.

Related papers

• Multi-Step Alignment as Markov Games: An Optimistic Online Gradient Descent Approach with Convergence Guarantees [91.88803125231189]
  Multi-step Preference Optimization (MPO) is built upon the natural actor-critic frameworkciteprakhlin2013online,joulani17a. We show that OMPO requires $mathcalO(epsilon-1)$ policy updates to converge to an $epsilon$-approximate Nash equilibrium. We also validate the effectiveness of our method on multi-turn conversations dataset and math reasoning dataset.
  arXiv  Detail & Related papers  (2025-02-18T09:33:48Z)
• Explore the Reasoning Capability of LLMs in the Chess Testbed [45.12891789312405]
  We propose improving the reasoning capability of large language models in chess by integrating annotated strategy and tactic. We finetune the LLaMA-3-8B model and compare it against state-of-the-art commercial language models in the task of selecting better chess moves.
  arXiv  Detail & Related papers  (2024-11-11T01:42:56Z)
• Emergent World Models and Latent Variable Estimation in Chess-Playing Language Models [0.0]
  We train a GPT model on Othello games and find that the model learned an internal representation of the board state. We extend this work into the more complex domain of chess, training on real games and investigating our model's internal representations. Unlike Li et al.'s prior synthetic dataset approach, our analysis finds that the model also learns to estimate latent variables like player skill to better predict the next character.
  arXiv  Detail & Related papers  (2024-03-21T18:53:23Z)
• Steering Language Models with Game-Theoretic Solvers [43.023261136434876]
  We introduce a framework that allows equilibrium solvers to work over the space of natural language dialogue generated by large language models (LLMs) Specifically, by modelling the players, strategies and payoffs in a "game" of dialogue, we create a binding from natural language interactions to the conventional symbolic logic of game theory. We focus on three domains that require different negotiation strategies: scheduling meetings, trading fruit and debate, and evaluate an LLM's generated language when guided by solvers.
  arXiv  Detail & Related papers  (2024-01-24T22:22:00Z)
• SPRING: Studying the Paper and Reasoning to Play Games [102.5587155284795]
  We propose a novel approach, SPRING, to read the game's original academic paper and use the knowledge learned to reason and play the game through a large language model (LLM) In experiments, we study the quality of in-context "reasoning" induced by different forms of prompts under the setting of the Crafter open-world environment. Our experiments suggest that LLMs, when prompted with consistent chain-of-thought, have great potential in completing sophisticated high-level trajectories.
  arXiv  Detail & Related papers  (2023-05-24T18:14:35Z)
• PaLM-E: An Embodied Multimodal Language Model [101.29116156731762]
  We propose embodied language models to incorporate real-world continuous sensor modalities into language models. We train these encodings end-to-end, in conjunction with a pre-trained large language model, for multiple embodied tasks. Our largest model, PaLM-E-562B with 562B parameters, is a visual-language generalist with state-of-the-art performance on OK-VQA.
  arXiv  Detail & Related papers  (2023-03-06T18:58:06Z)
• Improving Chess Commentaries by Combining Language Models with Symbolic Reasoning Engines [31.87260568733666]
  We show how to combine symbolic reasoning engines with controllable language models to generate chess commentaries. We conduct experiments to demonstrate that our approach generates commentaries preferred by human judges over previous baselines.
  arXiv  Detail & Related papers  (2022-12-15T23:38:31Z)
• Learning Chess Blindfolded: Evaluating Language Models on State Tracking [69.3794549747725]
  We consider the task of language modeling for the game of chess. Unlike natural language, chess notations describe a simple, constrained, and deterministic domain. We find that transformer language models can learn to track pieces and predict legal moves with high accuracy when trained solely on move sequences.
  arXiv  Detail & Related papers  (2021-02-26T01:16:23Z)
• Deep Reinforcement Learning with Stacked Hierarchical Attention for Text-based Games [64.11746320061965]
  We study reinforcement learning for text-based games, which are interactive simulations in the context of natural language. We aim to conduct explicit reasoning with knowledge graphs for decision making, so that the actions of an agent are generated and supported by an interpretable inference procedure. We extensively evaluate our method on a number of man-made benchmark games, and the experimental results demonstrate that our method performs better than existing text-based agents.
  arXiv  Detail & Related papers  (2020-10-22T12:40:22Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.