Belief networks

Bayesian belief networks (BBNs) are a graphical representation for reasoning under uncertainty [20]. A BBN is a directed acyclic graph with a conditional probability distribution for each node. BBNs contain nodes representing domain variables, and arcs between nodes representing probabilistic dependencies. The basic task for a BBN is to compute the posterior probability distribution for a set of query variables, given exact values for some evidence variables.

Since exact (``brute-force'') algorithms for performing inference on BBNs take exponential time (in the number of nodes) in the worst case, they cannot handle large or highly connected networks. Stochastic simulation algorithms have been developed to give approximate results for a wider variety of belief network topologies. Simulation algorithms differ from the brute-force approach in that they select only a sample of the node states, whereas a brute-force strategy selects every state. One of the simulation algorithms for BBNs, likelihood weighting [22] [11], is similar to the idea of selective sampling simulation in poker.

Likelihood weighting selects the node states based on their prior probability of occurrence. By choosing more likely states more often, this algorithm typically is able to converge much more quickly than equiprobable sampling which randomly chooses a state for each node in the network [8]. Likelihood weighting chooses a state for a node by generating a random number between 0 and 1 and using this number to select a state according to the conditional probability table of the node. For each simulation trial, the probability of the evidence given the sampled state values is used to increment the count of each event of interest. The estimated probability distribution is obtained by normalizing after all the simulation trials are completed.

By using selective sampling simulation in poker, we estimate the expected values of betting actions instead of estimating the posterior probability distribution for a set of variables. Both simulation methods have the following characteristics:

1.

They select the states to sample (node states or opponents' hands) on the basis of their probability of occurrence by using either conditional probability tables or (in our case) weight tables.

2.

Both methods can use heuristics or information available about the world to modify the tables for choosing states and bias the state selection to the most likely ones.