Monte Carlo Tree Search for a single target search game on a 2-D lattice

• URL: http://arxiv.org/abs/2011.14246v1
• Date: Sun, 29 Nov 2020 01:07:45 GMT
• Title: Monte Carlo Tree Search for a single target search game on a 2-D lattice
• Authors: Elana Kozak and Scott Hottovy
• Abstract summary: This project imagines a game in which an AI player searches for a stationary target within a 2-D lattice. We analyze its behavior with different target distributions and compare its efficiency to the Levy Flight Search, a model for animal foraging behavior.
• Score: 0.0
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: Monte Carlo Tree Search (MCTS) is a branch of stochastic modeling that utilizes decision trees for optimization, mostly applied to artificial intelligence (AI) game players. This project imagines a game in which an AI player searches for a stationary target within a 2-D lattice. We analyze its behavior with different target distributions and compare its efficiency to the Levy Flight Search, a model for animal foraging behavior. In addition to simulated data analysis we prove two theorems about the convergence of MCTS when computation constraints neglected.

Related papers

• Online Test Synthesis From Requirements: Enhancing Reinforcement Learning with Game Theory [1.363146160329157]
  We consider the automatic online synthesis of black-box test cases from functional requirements specified as automata for reactive implementations. We develop an approach based on Monte Carlo Tree Search, which is a classical technique in reinforcement learning for efficiently selecting promising inputs.
  arXiv  Detail & Related papers  (2024-07-26T07:59:59Z)
• LiteSearch: Efficacious Tree Search for LLM [70.29796112457662]
  This study introduces a novel guided tree search algorithm with dynamic node selection and node-level exploration budget. Experiments conducted on the GSM8K and TabMWP datasets demonstrate that our approach enjoys significantly lower computational costs compared to baseline methods.
  arXiv  Detail & Related papers  (2024-06-29T05:14:04Z)
• AlphaZeroES: Direct score maximization outperforms planning loss minimization [61.17702187957206]
  Planning at execution time has been shown to dramatically improve performance for agents in both single-agent and multi-agent settings. A family of approaches to planning at execution time are AlphaZero and its variants, which use Monte Carlo Tree Search together with a neural network that guides the search by predicting state values and action probabilities. We show that, across multiple environments, directly maximizing the episode score outperforms minimizing the planning loss.
  arXiv  Detail & Related papers  (2024-06-12T23:00:59Z)
• Monte-Carlo Tree Search for Multi-Agent Pathfinding: Preliminary Results [60.4817465598352]
  We introduce an original variant of Monte-Carlo Tree Search (MCTS) tailored to multi-agent pathfinding. Specifically, we use individual paths to assist the agents with the the goal-reaching behavior. We also use a dedicated decomposition technique to reduce the branching factor of the tree search procedure.
  arXiv  Detail & Related papers  (2023-07-25T12:33:53Z)
• Learning To Dive In Branch And Bound [95.13209326119153]
  We propose L2Dive to learn specific diving structurals with graph neural networks. We train generative models to predict variable assignments and leverage the duality of linear programs to make diving decisions.
  arXiv  Detail & Related papers  (2023-01-24T12:01:45Z)
• A Fast Evolutionary adaptation for MCTS in Pommerman [0.0]
  We propose our novel Evolutionary Monte Carlo Tree Search (FEMCTS) agent. It borrows ideas from Evolutionary Algorthims (EA) and Monte Carlo Tree Search (MCTS) to play the game of Pommerman.
  arXiv  Detail & Related papers  (2021-11-26T23:26:33Z)
• Monte Carlo Tree Search: A Review of Recent Modifications and Applications [0.17205106391379024]
  Monte Carlo Tree Search (MCTS) is a powerful approach to designing game-playing bots or solving sequential decision problems. The method relies on intelligent tree search that balances exploration and exploitation. The method has become a state-of-the-art technique for games, however, in more complex games.
  arXiv  Detail & Related papers  (2021-03-08T17:44:15Z)
• Learning to Stop: Dynamic Simulation Monte-Carlo Tree Search [66.34387649910046]
  Monte Carlo tree search (MCTS) has achieved state-of-the-art results in many domains such as Go and Atari games. We propose to achieve this goal by predicting the uncertainty of the current searching status and use the result to decide whether we should stop searching.
  arXiv  Detail & Related papers  (2020-12-14T19:49:25Z)
• Learning Optimal Tree Models Under Beam Search [27.92120639502327]
  Existing tree models suffer from the training-testing discrepancy. We develop the concept of Bayes optimality under beam search and calibration under beam search. We propose a novel algorithm for learning optimal tree models under beam search.
  arXiv  Detail & Related papers  (2020-06-27T17:20:04Z)
• On Effective Parallelization of Monte Carlo Tree Search [51.15940034629022]
  Monte Carlo Tree Search (MCTS) is computationally expensive as it requires a substantial number of rollouts to construct the search tree. How to design effective parallel MCTS algorithms has not been systematically studied and remains poorly understood. We demonstrate how proposed necessary conditions can be adopted to design more effective parallel MCTS algorithms.
  arXiv  Detail & Related papers  (2020-06-15T21:36:00Z)
• Single-Agent Optimization Through Policy Iteration Using Monte-Carlo Tree Search [8.22379888383833]
  Combination of Monte-Carlo Tree Search (MCTS) and deep reinforcement learning is state-of-the-art in two-player perfect-information games. We describe a search algorithm that uses a variant of MCTS which we enhanced by 1) a novel action value normalization mechanism for games with potentially unbounded rewards, 2) defining a virtual loss function that enables effective search parallelization, and 3) a policy network, trained by generations of self-play, to guide the search.
  arXiv  Detail & Related papers  (2020-05-22T18:02:36Z)

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.