Current challenges in multi-player game search

Abstract. Years of work have gone into algorithms and optimizations for twoplayer perfect-information games such as Chess and Checkers. It is only more recently that serious research has gone into games with imperfect information, such as Bridge, or game with more than two players or teams of players, such as Poker. This work focuses on multi-player game search in the card games Hearts and Spades, providing an overview of past research in multi-player game search and then presents new research results regarding the optimality of current search techniques and the need for good opponent modeling in multi-player game search. We show that we are already achieving near-optimal pruning in the games Hearts and Spades.