Best Reply Search for Multiplayer Games
Maarten P. D. Schadd, Mark H. M. Winands · IEEE Transactions on Computational Intelligence and AI in Games · 2011
This paper proposes a new algorithm, called best reply search (BRS), for deterministic multiplayer games with perfect information. In BRS, only the opponent with the strongest counter move is allowed to make a move. More turns of the root player can be searched resulting in long-term planning. We test BRS in the games of Chinese Checkers, Focus, and Rolit™. In all games, BRS is superior to the maxnalgorithm. We show that BRS also outperforms paranoid in Chinese Checkers and Focus. In Rolit, BRS is on equal footing with paranoid. We conclude that BRS is a promising search method for deterministic multiplayer games with perfect information.