No subject

[Eric B. Baum]

Preprint: Best Play for Imperfect Players and Game Tree Search

The following preprint is available via the NEC Research
Institute ftp archive external.nj.nec.com. Instructions for
retrieval from the archive follow the summary.

-----------------------------------------------------------------

Best Play for Imperfect Players and Game Tree Search
 
         Eric B. Baum and Warren D. Smith
         NEC Research Institute
         4 Independence Way
         Princeton NJ 08540

                ABSTRACT

We propose a new approach to game tree search. We train up an 
evaluation function which returns, rather than a single number
estimating the value of a position, a probability distribution 
$P_L(x)$. $P_L(x)$ is the probability that if we expanded
leaf $L$ to some depth, the backed up value of leaf $L$ 
would then be found to be $x$. We describe how to propagate 
these distributions efficiently up the tree so that at any node n 
we compute without approximation the probability node n's negamax 
value is x given that a value is assigned to each leaf from its 
distribution. After we are done expanding the tree, the best move 
is the child of the root whose distribution has highest mean. Note 
that we take means at the child of the root {\it after} propagating, 
whereas the normal (Shannon) approach  takes the mean at the leaves 
before propagating, which throws away information.

Now we model the expansion of a leaf as selection of one
value from its distribution. The total utility of all possible 
expansion is defined as the ensemble sum over those possible leaf 
configurations for which the current favorite move is inferior to 
some alternate move, weighted by the probability of the leaf
configuration and the amount the current favorite move is
inferior. We propose as the natural measure of the expansion
importance of leaf L, the expected absolute change in
this utility when we expand leaf L. We support this
proposal with several arguments including an approximation
theorem valid in the limit that one expands until the remaining
utility of expansion becomes small.

In summary, we gather distributions at the leaves, propagate exactly 
all this information to the root, and incrementally grow a tree 
expanding approximately the most interesting leaf at each step. 
Under reasonable conditions, we accomplish all of this
in time $O(N)$, where N is the number of leaves in the tree 
when we are done expanding. That is, we pay only a small constant
factor overhead for all of our bookkeeping.


----------------------------------------------------------------------

                          FTP INSTRUCTIONS

                unix> ftp external.nj.nec.com (138.15.10.100)
                Name: anonymous
                Password: (your_userid at your_site)
                ftp> cd pub/eric/papers
                ftp> binary
                ftp> get game.ps.Z
                ftp> quit
                unix> uncompress game.ps.Z


-----------------------------------------------------------------------


                                  Eric Baum
                                  NEC Research Institute
                                  4 Independence Way
                                  Princeton NJ 08540

Inet:   eric at research.nj.nec.com
UUCP:   princeton!nec!eric  
MAIL:   4 Independence Way, Princeton NJ 08540
PHONE:  (609) 951-2712
FAX:    (609) 951-2482