Using Resource-Limited Nash Memory to Improve an<i>Othello</i>Evaluation Function

Abstract

Finding the best strategy for winning a game using self-play or coevolution can be hindered by intransitivity among strategies and a changing fitness landscape. Nash Memory has been proposed as an archive for coevolution, to counter intransitivity and provide a more consistent fitness landscape. A lack of bounds on archive size might impede its use in a large, complex domain, such as the game of <i xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">Othello</i> , with strategies described by <i xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">n</i> -tuple networks. This paper demonstrates that even with a bounded-size archive, an evolving population can continue to show progress past the point where self-play no longer can. Characteristics of Nash equilibria are shown to be valuable in the measurement of performance. In addition, a technique for automated selection of features is demonstrated for the <i xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">n</i> -tuple networks.