Enhancing History-Based Move Ordering in Game Playing Using Adaptive Data Structures

-

Novel threat-based AI strategies that incorporate adaptive data structures for multi-player board games

This paper considers the problem of designing novel techniques for multi-player game playing, in a range of board games and configurations. Compared to the well-known case of two-player game playing, multi-player game playing is a more complex problem with unique requirements. To address the unique challenges of this domain, we examine the potential of employing techniques inspired by Adaptive Data Structures (ADSs) to rank opponents based on their relative threats, and using this information to achieve gains in move ordering and tree pruning. We name our new technique the Threat-ADS heuristic. We examine the Threat-ADS’ performance within a range of game models, employing a number of diffe…

Novel AI Strategies for Multi-Player Games at Intermediate Board States

-

Challenging Established Move Ordering Strategies with Adaptive Data Structures

On Addressing the Challenges of Complex Stochastic Games Using “Representative” Moves

The problem of achieving competitive game play in a board game, against an intelligent opponent, is a well-known and studied field of Artificial Intelligence (AI). This area of research has seen major breakthroughs in recent years, particularly in the game of Go. However, popular hobby board games, and particularly Trading Card Games, have unique qualities that make them very challenging to existing game playing techniques, partly due to enormous branching factors. This remains a largely unexamined domain and is the arena we operate in. To attempt to tackle some of these daunting requirements, we introduce the novel concept of “Representative” Moves (RMs). Rather than examine the complete l…

On Achieving History-Based Move Ordering in Adversarial Board Games using Adaptive Data Structures

-

On Applying Adaptive Data Structures to Multi-Player Game Playing

In the field of game playing, the focus has been on two-player games, such as Chess and Go, rather than on multi-player games, with dominant multi-player techniques largely being an extension of two-player techniques to an \(N\)-player environment. To address the problem of multiple opponents, we propose the merging of two previously unrelated fields, namely those of multi-player game playing and Adaptive Data Structures (ADS). We present here a novel move-ordering heuristic for a dominant multi-player game playing algorithm, namely the Best-Reply Search (BRS). Our enhancement uses an ADS to rank the opponents in terms of their respective threat levels to the player modeled by the AI algori…

Space and depth-related enhancements of the history-ADS strategy in game playing

-