Hybrid Minimax-MCTS and Difficulty Adjustment for General Game Playing

• URL: http://arxiv.org/abs/2310.16581v1
• Date: Wed, 25 Oct 2023 12:13:40 GMT
• Title: Hybrid Minimax-MCTS and Difficulty Adjustment for General Game Playing
• Abstract summary: We present a general approach to implement an artificial intelligence opponent with difficulty levels for zero-sum games. We propose a Minimax-MCTS hybrid algorithm, which combines the minimax search process with GGP of MCTS. This approach was tested in our mobile application LoBoGames, which is friendly to visually-impaired users.
• Score: 0.1657441317977376
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: Board games are a great source of entertainment for all ages, as they create a competitive and engaging environment, as well as stimulating learning and strategic thinking. It is common for digital versions of board games, as any other type of digital games, to offer the option to select the difficulty of the game. This is usually done by customizing the search parameters of the AI algorithm. However, this approach cannot be extended to General Game Playing agents, as different games might require different parametrization for each difficulty level. In this paper, we present a general approach to implement an artificial intelligence opponent with difficulty levels for zero-sum games, together with a propose of a Minimax-MCTS hybrid algorithm, which combines the minimax search process with GGP aspects of MCTS. This approach was tested in our mobile application LoBoGames, an extensible board games platform, that is intended to have an broad catalog of games, with an emphasis on accessibility: the platform is friendly to visually-impaired users, and is compatible with more than 92\% of Android devices. The tests in this work indicate that both the hybrid Minimax-MCTS and the new difficulty adjustment system are promising GGP approaches that could be expanded in future work.

Related papers

• GameWorld: Towards Standardized and Verifiable Evaluation of Multimodal Game Agents [76.60994803070436]
  GameWorld is a benchmark for evaluation of Multimodal Large Language Model (MLLM) game agents in browser environments.<n>Two game agent interfaces are studied: (i) computer-use agents that directly emit keyboard and mouse controls, and (ii) generalist multimodal agents that act in a semantic action space.<n>Results across 18 model-interface pairs suggest that even the best performing agent is far from achieving human capabilities on video games.
  arXiv  Detail & Related papers  (2026-04-08T17:49:03Z)
• AI Gamestore: Scalable, Open-Ended Evaluation of Machine General Intelligence with Human Games [63.29377274531968]
  We introduce the AI GameStore, a scalable and open-ended platform to synthesize new representative human games.<n>We generate 100 such games based on the top charts of Apple App Store and Steam, and evaluate seven frontier vision-language models (VLMs) on short episodes of play.<n>The best models achieved less than 10% of the human average score on the majority of the games, and especially struggled with games that challenge world-model learning, memory and planning.
  arXiv  Detail & Related papers  (2026-02-19T18:17:25Z)
• From Frustration to Fun: An Adaptive Problem-Solving Puzzle Game Powered by Genetic Algorithm [1.0098114696565863]
  This paper explores adaptive problem solving with a game designed to support the development of problem-solving skills.<n>Using an adaptive, AI-powered puzzle game, our adaptive problem-solving system dynamically generates pathfinding-based puzzles using a genetic algorithm.<n>A player-modeling system records user interactions and informs the generation of puzzles to approximate a target difficulty level based on various metrics of the player.
  arXiv  Detail & Related papers  (2025-09-28T10:40:14Z)
• FlashAdventure: A Benchmark for GUI Agents Solving Full Story Arcs in Diverse Adventure Games [56.81554611870848]
  We introduce FlashAdventure, a benchmark of 34 Flash-based adventure games designed to test full story arc completion.<n>We also propose CUA-as-a-Judge, an automated gameplay evaluator, and COAST, an agentic framework leveraging long-term clue memory.<n> Experiments show current GUI agents struggle with full story arcs, while COAST improves milestone completion by bridging the observation-behavior gap.
  arXiv  Detail & Related papers  (2025-09-01T01:33:16Z)
• Neural Population Learning beyond Symmetric Zero-sum Games [52.20454809055356]
  We introduce NeuPL-JPSRO, a neural population learning algorithm that benefits from transfer learning of skills and converges to a Coarse Correlated (CCE) of the game. Our work shows that equilibrium convergent population learning can be implemented at scale and in generality.
  arXiv  Detail & Related papers  (2024-01-10T12:56:24Z)
• Hardness of Independent Learning and Sparse Equilibrium Computation in Markov Games [70.19141208203227]
  We consider the problem of decentralized multi-agent reinforcement learning in Markov games. We show that no algorithm attains no-regret in general-sum games when executed independently by all players. We show that our lower bounds hold even for seemingly easier setting in which all agents are controlled by a centralized algorithm.
  arXiv  Detail & Related papers  (2023-03-22T03:28:12Z)
• Exploring Adaptive MCTS with TD Learning in miniXCOM [0.0]
  In this work, we explore on-line adaptivity in Monte Carlo tree search (MCTS) without requiring pre-training. We present MCTS-TD, an adaptive MCTS algorithm improved with temporal difference learning. We demonstrate our new approach on the game miniXCOM, a popular commercial franchise consisting of several turn-based tactical games.
  arXiv  Detail & Related papers  (2022-10-10T21:04:25Z)
• Towards General Function Approximation in Zero-Sum Markov Games [126.58493169301012]
  This paper considers two-player zero-sum finite-horizon Markov games with simultaneous moves. Provably efficient algorithms for both decoupled and coordinated settings are developed.
  arXiv  Detail & Related papers  (2021-07-30T15:25:13Z)
• Generating Diverse and Competitive Play-Styles for Strategy Games [58.896302717975445]
  We propose Portfolio Monte Carlo Tree Search with Progressive Unpruning for playing a turn-based strategy game (Tribes) We show how it can be parameterized so a quality-diversity algorithm (MAP-Elites) is used to achieve different play-styles while keeping a competitive level of play. Our results show that this algorithm is capable of achieving these goals even for an extensive collection of game levels beyond those used for training.
  arXiv  Detail & Related papers  (2021-04-17T20:33:24Z)
• Playing Against the Board: Rolling Horizon Evolutionary Algorithms Against Pandemic [3.223284371460913]
  This paper contends that collaborative board games pose a different challenge to artificial intelligence as it must balance short-term risk mitigation with long-term winning strategies. This paper focuses on the exemplary collaborative board game Pandemic and presents a rolling evolutionary algorithm for this game.
  arXiv  Detail & Related papers  (2021-03-28T09:22:10Z)
• Collaborative Agent Gameplay in the Pandemic Board Game [3.223284371460913]
  Pandemic is an exemplar collaborative board game where all players coordinate to overcome challenges posed by events occurring during the game's progression. This paper proposes an artificial agent which controls all players' actions and balances chances of winning versus risk of losing in this highly Evolutionary environment. Results show that the proposed algorithm can find winning strategies more consistently in different games of varying difficulty.
  arXiv  Detail & Related papers  (2021-03-21T13:18:20Z)
• TotalBotWar: A New Pseudo Real-time Multi-action Game Challenge and Competition for AI [62.997667081978825]
  TotalBotWar is a new pseudo real-time multi-action challenge for game AI. The game is based on the popular TotalWar games series where players manage an army to defeat the opponent's one.
  arXiv  Detail & Related papers  (2020-09-18T09:13:56Z)
• Finding Game Levels with the Right Difficulty in a Few Trials through Intelligent Trial-and-Error [16.297059109611798]
  Methods for dynamic difficulty adjustment allow games to be tailored to particular players to maximize their engagement. Current methods often only modify a limited set of game features such as the difficulty of the opponents, or the availability of resources. This paper presents a method that can generate and search for complete levels with a specific target difficulty in only a few trials.
  arXiv  Detail & Related papers  (2020-05-15T17:48:18Z)
• Efficient exploration of zero-sum stochastic games [83.28949556413717]
  We investigate the increasingly important and common game-solving setting where we do not have an explicit description of the game but only oracle access to it through gameplay. During a limited-duration learning phase, the algorithm can control the actions of both players in order to try to learn the game and how to play it well. Our motivation is to quickly learn strategies that have low exploitability in situations where evaluating the payoffs of a queried strategy profile is costly.
  arXiv  Detail & Related papers  (2020-02-24T20:30:38Z)

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.