Experiences in Evaluation with BKG - A Program that Plays Backgammon

Abstract

Because of very high branching factors, a backgammon program must rely on knowledge rather than search for performance. We here disc.uss insights gained about the s tructure of evaluation functions for a large domain s uch as backgammon. Evaluation began as a single linear polynomial of backgammon features . Later, we introduced s tat e-c lasses, each with its own evaluation function .. This · improved the play, but cau se.d problems with e dge-effects between state -c lasses. Our latest effort use s models of position potential to select across the set of best members of each represented sta te-class. This has produced a significant jump in performance of BKG. Because of the localization of knowledge, state-classes permit relatively easy modification of knowledge used in evaluati on ,. They also permit the building of opponent models ba se d upon what evidence shows the opponent knows in each state-class. Ou r program plays a generally competent game at an intermediate level of skill. It correctly solves a high percentage of intermediate level problems in books