A Principled Method for Exploiting Opening BooksReport as inadecuate

A Principled Method for Exploiting Opening Books - Download this document for free, or read online. Document in PDF available to download.

1 LRI - Laboratoire de Recherche en Informatique 2 TAO - Machine Learning and Optimisation LRI - Laboratoire de Recherche en Informatique, UP11 - Université Paris-Sud - Paris 11, Inria Saclay - Ile de France, CNRS - Centre National de la Recherche Scientifique : UMR8623

Abstract : We used in the past a lot of computational power and human expertise for having a very big dataset of good 9x9 Go games, in order to build an opening book. We improved a lot the algorithm used for gen- erating these games. Unfortunately, the results were not very robust, as i opening books are definitely not transitive, making the non-regression testing extremely difficult and ii different time settings lead to opposite conclusions, because a good opening for a game with 10s per move on a single core is very different from a good opening for a game with 30s per move on a 32-cores machine iii some very bad moves sometimes occur. In this paper, we formalize the optimization of an opening book as a matrix game, compute the Nash equilibrium, and conclude that a naturally randomized opening book provides optimal performance in the sense of Nash equilibria; surprisingly, from a finite set of opening books, we can choose a distribution on these opening books so that this random solution has a significantly better performance than each of the deterministic opening book.

Keywords : Opening book Nash equilibrium Fictitious Play Go

Author: Romaric Gaudel - Jean-Baptiste Hoock - Julien Pérez - Nataliya Sokolovska - Olivier Teytaud -

Source: https://hal.archives-ouvertes.fr/


Related documents