Next: How simulation works Up: Probabilities and Simulations in Previous: Summary

# Selective sampling simulation

The general structure of a program for a perfect information game, such as chess or checkers, contains an evaluation function and a search algorithm. Loki's knowledge-based betting strategy is, in fact, analogous to a static evaluation function. If deterministic perfect information games are used as a model then the obvious extension is to add search'' to Loki's evaluation function.

In checkers or chess, the average branching factor is 3 and 30-40 respectively. One can consider all possible moves as deeply as resources permit. However, in poker the existence of hidden information, uncertainty and multiple players makes the same approach infeasible. There are too many possibilities to consider. In a two-player Texas Hold'em game there are possible states at the beginning of the flop and possible opponent's hole cards (see Figure 4.2 in [19]) plus multiple possibilities for each betting round. Therefore, computing the complete game tree for poker is prohibitively expensive in real-time. If exhaustive search is out of the question, how do we add search'' to Loki?

We can examine (simulate) a representative sample, as large as resources permit, from all the possible game scenarios. The larger the sample and the more informed the selection process, the higher the chances to deduce meaningful conclusions.

A simulation consists of playing out a hand in many likely scenarios, from the current state of the game through to the end, to determine how much money each decision will win or lose. Every time Loki-2 faces a decision, it performs a simulation to get an estimate of the expected value (EV) of each betting action and then chooses the action with the greatest expectation. Inside each simulation, Loki-2 uses probability triples (PTs) to generate actions for all the opponents and itself, as well as, opponent modeling information (weight tables) to bias the selection of opponent's cards.

Next: How simulation works Up: Probabilities and Simulations in Previous: Summary
Lourdes Pena
1999-09-10