Exploring optimization strategies in board game Abalone for Alpha-Beta search
- Resource Type
- Conference
- Authors
- Papadopoulos, Athanasios; Toumpas, Konstantinos; Chrysopoulos, Antonios; Mitkas, Pericles A.
- Source
- 2012 IEEE Conference on Computational Intelligence and Games (CIG) Computational Intelligence and Games (CIG), 2012 IEEE Conference on. :63-70 Sep, 2012
- Subject
- Computing and Processing
Games
Estimation
Reliability
Sorting
Algorithm design and analysis
Search problems
Layout
- Language
- ISSN
- 2325-4270
2325-4289
This paper discusses the design and implementation of a highly efficient MiniMax algorithm for the game Abalone. For perfect information games with relatively low branching factor for their decision tree (such as Chess, Checkers etc.) and a highly accurate evaluation function, Alpha-Beta search proved to be far more efficient than Monte Carlo Tree Search. In recent years many new techniques have been developed to improve the efficiency of the Alpha-Beta tree, applied to a variety of scientific fields. This paper explores several techniques for increasing the efficiency of Alpha-Beta Search on the board game of Abalone while introducing some new innovative techniques that proved to be very effective. The main idea behind them is the incorporation of probabilistic features to the otherwise deterministic Alpha-Beta search.