Artificial Intelligence Based Board Game: Backgammon

Abstract

In 1979, the backgammon program BKG 9.8 won an exhibition match in Monte Carlo against the then-world-champion Luigi Villa by a score of 7-1. Although analysis of the match makes it clear that BKG had some good luck with the dice, and made several small errors, there is little doubt that the program is a very good backgammon player. The BKG program does not rely primarily upon tree searching to select a move, but upon a large base of backgammon knowledge coded in the form of an evaluation function. This function is applied to the positions resulting from each legal move in a given position to determine the best move to make, resulting in a fixed-depth, 1 ply search with terminal evaluation. During die course of the development of the evaluation function, several key ideas emerged as central to the success of the endeavour. Collectively, these ideas were referred to as the SNAC method of evaluation, standing for Smoothness, Nonlinearity, with Application Coefficients. The goal of the BKG project was to develop a fast program with a very high level of competence. To achieve speed, the evaluation function was written in a compiled language and in such a manner as to avoid expensive or unnecessary constructions wherever possible. The original goal of the PROGRAM2 project, which was begun in 1980, was to augment the BKG system with an explanation-generating component, to allow it to defend its choice of moves and comment on suggested moves.