Improving heuristic mini-max search by supervised learning

摘要

This article surveys three techniques for enhancing heuristic game-tree search pioneered in the author's Othello program Logistello, which dominated the computer Othello scene for several years and won against the human World-champion 6–0 in 1997. First, a generalized linear evaluation model (GLEM) is described that combines conjunctions of Boolean features linearly. This approach allows an automatic, data driven exploration of the feature space. Combined with efficient least squares weight fitting, GLEM greatly eases the programmer's task of finding significant features and assigning weights to them. Second, the selective search heuristic ProbCut and its enhancements are discussed. Based on evaluation correlations ProbCut can prune probably irrelevant sub-trees with a prescribed confidence. Tournament results indicate a considerable playing strength improvement compared to full-width α-β search. Third, an opening book framework is presented that enables programs to improve upon previous play and to explore new opening lines by constructing and searching a game-tree based on evaluations of played variations. These general methods represent the state-of-the-art in computer Othello programming and begin to attract researchers in related fields.