# Completeness of Unbounded Best-First Game Algorithms

arXiv: https://arxiv.org/abs/2109.09468 · HTML: https://mlsanity.com/paper/2109.09468/

## Key facts

- Cited by 4 papers in the map (data through 14 Oct 2026).
- Builds on 3 of its 20 references that are in the map.
- First posted on arXiv 11 Sep 2021.

## Builds on (most cited first, 3 of 3)

- [Learning to Play Two-Player Perfect-Information Games without Knowledge](https://mlsanity.com/paper/2008.01188/) (2020)
- [Minimax Strikes Back](https://mlsanity.com/paper/2012.10700/) (2020)
- [Multiplayer AlphaZero](https://mlsanity.com/paper/1910.13012/) (2019)

## Built on by (most cited first, 4 of 4)

- [On some improvements to Unbounded Minimax](https://mlsanity.com/paper/2505.04525/) (2025)
- [Learning to Play Stochastic Two-player Perfect-Information Games without Knowledge](https://mlsanity.com/paper/2302.04318/) (2023)
- [Minibal: Balanced Game-Playing Without Opponent Modeling](https://mlsanity.com/paper/2603.23059/) (2026)
- [Study and Improvement of Search Algorithms in Multi-Player Perfect-Information Games](https://mlsanity.com/paper/2604.17378/) (2026)

## Abstract (arXiv)

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.