Completeness of Unbounded Best-First Game Algorithms
This work addresses the theoretical completeness of game search algorithms for AI and game theory, but it appears incremental as it extends known algorithms to multiplayer contexts.
The authors proved that unbounded best-first minimax with completion and descent with completion algorithms are complete, meaning they find the best game strategy given sufficient time, and generalized these to perfect information multiplayer games, showing they find an equilibrium point.
In this article, we prove the completeness of the following game search algorithms: unbounded best-first minimax with completion and descent with completion, i.e. we show that, with enough time, they find the best game strategy. We then generalize these two algorithms in the context of perfect information multiplayer games. We show that these generalizations are also complete: they find one of the equilibrium points.