The development of a world class Othello program

摘要

In this paper we describe an Othello program, BILL, that has far surpassed the generation of Othello programs represented by IAGO. Its performance is due to a combination of factors. First, a wide variety of searching and timing techniques are used in order to increase its search depth. Furthermore, BILL efficiently uses a large amount of knowledge in its evaluation function. This efficiency is achieved through the use of pre-computed tables that can recognize hundreds of thousands of patterns in constant time. Finally, we applied Bayesian learning to combine features in BILL's evaluation function. This algorithm is automatic and optimal. It encapsulates inter-feature correlations, and directly estimates the probability of winning. These techniques are instrumental to BILL's playing strength, and we believe that they are generalizable to other domains.