Implicit Search via Discrete Diffusion: A Study on Chess

• URL: http://arxiv.org/abs/2502.19805v1
• Date: Thu, 27 Feb 2025 06:25:15 GMT
• Title: Implicit Search via Discrete Diffusion: A Study on Chess
• Authors: Jiacheng Ye, Zhenyu Wu, Jiahui Gao, Zhiyong Wu, Xin Jiang, Zhenguo Li, Lingpeng Kong,
• Abstract summary: We propose DiffuSearch, a model that does textitimplicit search by looking into the future world via discrete diffusion modeling.<n>We instantiate DiffuSearch on a classical board game, Chess, where explicit search is known to be essential.<n>We show DiffuSearch outperforms both the searchless and explicit search-enhanced policies.
• Score: 104.74301574891359
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: In the post-AlphaGo era, there has been a renewed interest in search techniques such as Monte Carlo Tree Search (MCTS), particularly in their application to Large Language Models (LLMs). This renewed attention is driven by the recognition that current next-token prediction models often lack the ability for long-term planning. Is it possible to instill search-like abilities within the models to enhance their planning abilities without relying on explicit search? We propose DiffuSearch , a model that does \textit{implicit search} by looking into the future world via discrete diffusion modeling. We instantiate DiffuSearch on a classical board game, Chess, where explicit search is known to be essential. Through extensive controlled experiments, we show DiffuSearch outperforms both the searchless and explicit search-enhanced policies. Specifically, DiffuSearch outperforms the one-step policy by 19.2% and the MCTS-enhanced policy by 14% on action accuracy. Furthermore, DiffuSearch demonstrates a notable 30% enhancement in puzzle-solving abilities compared to explicit search-based policies, along with a significant 540 Elo increase in game-playing strength assessment. These results indicate that implicit search via discrete diffusion is a viable alternative to explicit search over a one-step policy. All codes are publicly available at \href{https://github.com/HKUNLP/DiffuSearch}{https://github.com/HKUNLP/DiffuSearch}.

Related papers

• Planning In Natural Language Improves LLM Search For Code Generation [5.370466208990696]
  We propose PlanSearch, a novel search algorithm for solving problems in natural language. PlanSearch shows strong results across HumanEval+, MBPP+, and LiveCodeBench. We show that, across all models, search algorithms, and benchmarks analyzed, we can accurately predict performance gains due to search.
  arXiv  Detail & Related papers  (2024-09-05T17:44:49Z)
• Tree Search for Language Model Agents [69.43007235771383]
  We propose an inference-time search algorithm for LM agents to perform exploration and multi-step planning in interactive web environments. Our approach is a form of best-first tree search that operates within the actual environment space. It is the first tree search algorithm for LM agents that shows effectiveness on realistic web tasks.
  arXiv  Detail & Related papers  (2024-07-01T17:07:55Z)
• Stream of Search (SoS): Learning to Search in Language [29.841835308845948]
  We show how language models can be taught to search by representing the process of search in language as a flattened string. We propose a unified language for search that captures an array of different symbolic search strategies. Our results indicate that language models can learn to solve problems via search, self-improve to flexibly use different search strategies, and potentially discover new ones.
  arXiv  Detail & Related papers  (2024-04-01T06:50:52Z)
• Hybrid Search for Efficient Planning with Completeness Guarantees [63.02803974708516]
  We propose an efficient approach to augment a subgoal search method to achieve completeness in discrete action spaces. This solution achieves the best of both worlds: the practical efficiency of high-level search and the completeness of low-level search.
  arXiv  Detail & Related papers  (2023-10-19T15:16:43Z)
• RetroGraph: Retrosynthetic Planning with Graph Search [101.92603715499112]
  Retrosynthetic planning aims to find a reaction pathway to synthesize a target molecule. We propose a graph-based search policy that eliminates the redundant explorations of any intermediate molecules. Our method can search a batch of targets together in the graph and remove the inter-target duplication in the tree-based search methods.
  arXiv  Detail & Related papers  (2022-06-23T05:01:29Z)
• Deep Reinforcement Agent for Efficient Instant Search [14.086339486783018]
  We propose to address the load issue by identifying tokens that are semantically more salient towards retrieving relevant documents. We train a reinforcement agent that interacts directly with the search engine and learns to predict the word's importance. A novel evaluation framework is presented to study the trade-off between the number of triggered searches and the system's performance.
  arXiv  Detail & Related papers  (2022-03-17T22:47:15Z)
• Exposing Query Identification for Search Transparency [69.06545074617685]
  We explore the feasibility of approximate exposing query identification (EQI) as a retrieval task by reversing the role of queries and documents in two classes of search systems. We derive an evaluation metric to measure the quality of a ranking of exposing queries, as well as conducting an empirical analysis focusing on various practical aspects of approximate EQI.
  arXiv  Detail & Related papers  (2021-10-14T20:19:27Z)
• Scalable Online Planning via Reinforcement Learning Fine-Tuning [25.27878823988181]
  Tabular search methods do not scale well with the size of the search space. We replace this with online model-based fine-tuning of a policy neural network via reinforcement learning. In particular, we use our search algorithm to achieve a new state-of-the-art result in self-play Hanabi.
  arXiv  Detail & Related papers  (2021-09-30T17:59:11Z)
• Neural Extractive Search [53.15076679818303]
  Domain experts often need to extract structured information from large corpora. We advocate for a search paradigm called extractive search'', in which a search query is enriched with capture-slots. We show how the recall can be improved using neural retrieval and alignment.
  arXiv  Detail & Related papers  (2021-06-08T18:03:31Z)
• Searching for a Search Method: Benchmarking Search Algorithms for Generating NLP Adversarial Examples [10.993342896547691]
  We study the behavior of several black-box search algorithms used for generating adversarial examples for natural language processing (NLP) tasks. We perform a fine-grained analysis of three elements relevant to search: search algorithm, search space, and search budget.
  arXiv  Detail & Related papers  (2020-09-09T17:04:42Z)

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.