A Comparison of Probabilistic Search and Weighted Heuristics in a Game with Incomplete Information

Contents

Computing an effective strategy in games with incomplete information is much more difficult than in games where the status of every relevant factor is known. A weighted heuristic approach selects the move in a given position that maximizes a weighted sum of known factors, where the weights have been optimized over a large random sample of games. Probabilistic search is an alternative approach that generates a random set of scenarios, simulates how plausible moves perform under each scenario, and selects the move with the "best" overall performance. This paper compares the effectiveness of these approaches for the game of Scrabble.