Error Allowing Minimax: Getting over Indifference
Florian Wisser · 2013
We propose Error Allowing Minimax, an algorithm resolving indifferences in the choices of pure minimax players in games of perfect information, to give the opponent the biggest possible target for errors. In contrast to the usual approach of defining a domain-specific static evaluation function with an infinite codomain, we achieve fine-grained positional evaluations by general considerations of the game tree only. To achieve applicability to real-world situations we develop Error Allowing Alpha-Beta, a variant of the standard Alpha-Beta algorithm, and a variant hybridizing these two algorithms, allowing full control over the trade-off between accuracy and computational complexity. We investigate the impact of the algorithm applying it to the perfect information game Dots and Boxes.