On Pruning Techniques for Multi-Player Games

摘要: Max n (Luckhardt and Irani, 1986) is the extension of minimax backup rule to multi-player games. We have shown that only a limited version alpha-beta pruning, shallow can be applied max search tree. extend this work by calculating exact bounds needed use pruning technique. In addition, we show branch-and-bound using monotonic heuristic, has same limitations as in present hybrid these algorithms, which combines heuristic backed-up values prune even more effectively. also briefly discuss reduction n-player game ‘paranoid’ 2-player game. Sergeant Major, 3-player card game, averaged node expansions over 200 height 15 trees. Shallow each reduced factor about 100. Alpha-beta an additional 19. The was 3 better than branchand-bound. Using another 12.