M2ICAL Analyses HC-Gammon

Abstract

We analyse Pollack and Blair’s HC-Gammon backgam-mon program using a new technique that performs Monte Carlo simulations to derive a Markov Chain model for Imperfect Comparison ALgorithms, called the M2ICAL method, which models the behavior of the algorithm using a Markov chain, each of whose states represents a class of players of similar strength. The Markov chain transition matrix is populated using Monte Carlo simulations. Once generated, the matrix allows fairly accurate predictions of the expected solu-tion quality, standard deviation and time to convergence of the algorithm. This allows us to make some observa-tions on the validity of Pollack and Blair’s conclusions, and also shows the application of the M2ICAL method on a previously published work.