Du jeu de Go au Havannah : variantes d'UCT et coups décisifs

Fabien Teytaud 1, 2, 3 Olivier Teytaud 2, 3
1 TANC - Algorithmic number theory for cryptology
Inria Saclay - Ile de France, LIX - Laboratoire d'informatique de l'École polytechnique [Palaiseau]
3 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
Résumé : Les algorithmes de type fouille d'arbre Monte-Carlo et UCT (upper confidence tree) ont révolutionné le jeu de Go par ordinateur depuis 2006/2007. Quelques applications, encore rares, ont montré la généralité de ces approches, en particulier quand l'espace d'actions est trop grand pour les autres techniques, et quand l'état est complètement observable. Dans ce papier, nous testons cette généralité, en expérimentant UCT dans un autre jeu, le Havannah. Ce jeu est connu spécialement difficile pour les ordinateurs. Nous montrons que cette approche donne de bons résultats tout comme pour le jeu de Go, même si on peut noter quelques différences et en particulier la notion de coup décisif, inexistante en Go.
Complete list of metadatas

Cited literature [19 references]  Display  Hide  Download

https://hal.inria.fr/inria-00454541
Contributor : Fabien Teytaud <>
Submitted on : Monday, February 8, 2010 - 5:08:08 PM
Last modification on : Wednesday, March 27, 2019 - 4:41:29 PM
Long-term archiving on : Friday, June 18, 2010 - 7:36:16 PM

File

havRFIA_1_.pdf
Files produced by the author(s)

Identifiers

  • HAL Id : inria-00454541, version 1

Collections

Citation

Fabien Teytaud, Olivier Teytaud. Du jeu de Go au Havannah : variantes d'UCT et coups décisifs. RFIA, Jan 2010, Caen, France. ⟨inria-00454541⟩

Share

Metrics

Record views

519

Files downloads

374