How a Bayesian Approaches Games Like Chess

摘要: The point of game tree search is to insulate oneself from errors in the evaluation function. standard approach grow a full width as deep time allows, and then value if leaf evaluations were exact. This has been effective many games because computational efficiency alpha-beta algorithm. A Bayesian would suggest instead train model one’s uncertainty. adds extra information addition Within such formal model, there an optimal growth procedure method valueing tree. We describe how optimally tree, approximate on line search. Our provably approximates contribution each utility limit where we large taking explicit account interactions between expanding different leaves. That say, our estimates relevance iteratively expands most relevant algorithms run (under reasonable assumptions) linear hence except for small constant factor, are efficient alphabeta.