Searching for solutions in games and artificial intelligence

By L. Victor Allis. 1994

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Reinforcement Learning

Citations in the corpus

Mastering Chess and Shogi by Self-Play with a General Reinforcement Learning Algorithm (2017, background): “Shogi is a significantly harder game, in terms of computational complexity, than chess (2, 15): it is played on a larger board with a wider variety of pieces; any captured opponent piece changes sides and may subsequently be dropped anywhere on the board.”
DeepStack: Expert-level artificial intelligence in heads-up no-limit poker (2017, background): “By comparison, computers have exceeded expert human performance in go (6), a perfect information game with approximately 10(170) decision points (12).”
Giraffe: Using Deep Reinforcement Learning to Play Chess (2015, methodology): “The search tree size for chess is estimated to be about 10 123 [6] (10 46 without repetitions [7]) which is more than one hundred orders of magnitudes higher than what is computationally feasible using modern computers.”
Dota 2 with Large Scale Deep Reinforcement Learning (2019, background): “Chess has a branching factor of around 35 valid actions, and Go around 250[11].”
Born to Learn: the Inspiration, Progress, and Future of Evolved Plastic Artificial Neural Networks (2017, background): “A further step in complexity is represented by high-level planning and strategies required, e.g., when applying AI to games (Allis et al., 1994; Millington and Funge, 2016) or articulated robotic tasks.”
Monte-Carlo Tree Search Solver (2008, unknown): “[2] (e.”
Multi-Agent Reinforcement Learning: A Selective Overview of Theories and Algorithms (2019, background): “It is estimated in [355] that the size of state space exceeds 10360, which forbids the usage of any traditional reinforcement learning or searching algorithms.”
Computer-Assisted Synthetic Planning: The End of the Beginning. (2016, background): “number of moves possible from a given position is 35 translating into 10123 possible 80-move games([11]) Over 4 Ö 10(19) possible configurations; more than 2 Ö 10(20) possible sequences of 18 moves([12]) On average, 80.”
Efficient Selectivity and Backup Operators in Monte-Carlo Tree Search (2006, background): “When played on a 9◊ 9 grid, the complexity of the game of Go, in terms of the number of legal positions, is inferior to the complexity of the game of chess [ 2 ,27], and the number of legal moves per position is similar.”
Deep neural networks, gradient-boosted trees, random forests: Statistical arbitrage on the S&P 500 (2017, background): “As explained in Allis (1994) and in Silver et al. (2016), such games of perfect information may be solved by recursively computing the optimal value function in a search tree.”
Programming (2004, unknown): “The state-space complexity (Allis, 1994) of mancala games can be computed from the number of holes and number of counters involved.”
DeepStack: Expert-Level Artificial Intelligence in No-Limit Poker (2017, background): “By comparison, computers have exceeded expert human performance in go (6), a perfect information game with approximately 10(170) decision points (12).”
Application of reinforcement learning to the game of Othello (2008, background): “The state space size of Othello is approximately 1028 [22,23], and its length is 60 moves at most.”
Heads-up limit hold’em poker is solved (2015, background): “Allis (26) gave three different definitions for solving a game.”
A general reinforcement learning algorithm that masters chess, shogi, and Go through self-play (2018, background): “In terms of game tree complexity, shogi is a substantially harder game than chess (13, 14): It is played on a larger boardwith awider variety of pieces; any captured opponent piece switches sides and may subsequently be dropped anywhere on the board.”