*-Minimax Performance in Backgammon

摘要

This paper presents the first performance results for Bal-lard's *-Minimax algorithms applied to a real-world domain: backgammon. It is shown that with effective move ordering and probing the Star2 algorithm considerably outperforms Expectimax. Star2 allows strong backgammon programs to conduct depth-5 full-width searches (up from 3) under tournament conditions on regular hardware without using risky forward-pruning techniques. We also present empirical evidence that with today's sophisticated evaluation functions good checker play in backgammon does not require deep searches.