next up previous contents
Next: Backgammon Up: Other examples of selective Previous: Belief networks

Games

In this section, three game-playing programs that use simulations are described. These programs do not use Monte Carlo sampling to generate instances of the missing information. They use variations of selective sampling; sampling biased towards taking advantage of all the available information. They use information about the game state to skew the underlying probability distribution of the opponents' moves, cards or tiles, rather than assuming uniform or other fixed probability distributions. The general simulation algorithm used by these games to select a move from a set M of candidate moves is:

1.
Construct a set I of instances of the missing information consistent with the public information about the state of the game and the program's assumptions (information) about the opponents.
2.
For each move $m \in M$ and each instance $i \in I$, evaluate the result of making the move m in the instance i. Denote the score obtained by making this move s(m,i).
3.
Return that m for which $\sum_i s(m,i)$ is maximal.



 

Lourdes Pena
1999-09-10