Avoiding Game-Tree Pathology in Multi-player Games

Game-tree pathology is a phenomenon where searching a game-tree deeper gives results in worse decision. There are several solutions to dealing with game-tree pathology in two-players games, however there is no algorithmic solution available for coping with game-tree pathology in multi-player games. In this work we present the EMMN and EMMNv, two algorithms that overcome pathology in multi-player games. Our presentation includes a theoretical analysis and an extensive empirical work on the multi-player version of the Nim board game.