|
|
|
My Pages at FUN |
|---|
|
|
|
Projects |
|
Monte-Carlo Sampling in Games with Incomplete Information: empirical investigation and analysis Ian Frank, David Basin, Hitoshi Matsubara Presented at the Workshop on Game Tree Search, Princeton, NJ, 1997. Book version now in press (to appear in March 1999).The version on these pages is a slightly earlier ETL Technical Report, ETL-TR-97-18
Abstract:We investigate Monte-carlo sampling in games with incomplete information. We show that for very simple game trees the chance of finding the optimal strategy with Monte-carlo sampling rapidly approaches zero as the number of moves in the game increases. We explain this sub-optimality by identifying the different kinds of errors that can arise and by analysing their interplay. We also relate our test results to real games, suggesting why the error rates observed in practice may not be so high. |
