OPEN ACCESS
This article describes WoodStock, the first general game player modeling each game from the General Game Playing (GGP) by a stochastic constraint network (SCSP). Each action played is decided by the resolution of this last one by the algorithm MAC-UCB. After the translation of an instance described in Game Description Language (GDL) in a network representative of the state of the game at any time, WoodStock solves each state by the maintening arc-consistency algorithm (MAC) iteratively guided by the bandit-based stochastic sampling (UCB) of the next states. Thanks to this algorithm, WoodStock is since march 2016, the leader of the GGP Tiltyard continuous tournament. Moreover, in its last version exploiting the game symmetries finding by the constraint symmetry detection, the search space associated with a game is significatively reduced. With that, WoodStock is now the GGP champion after its victory at the International General Game Playing Competition 2016 (IGGPC 2016).
international general game playing competition (IGGPC), stochastic constraint satisfaction problem (SCSP), bandit-based stochastic sampling (UCB)
Browne C., Powley E., Tavener S. (2012). A survey of monte carlo tree search methods. Intelligence and AI, vol. 4, no 1, p. 1–49.
Cazenave T., Mehat J. (2010). Ary - a general game playing program. In Proc. of board games studies colloquium.
Clune J. (2007). Heuristic evaluation functions for general game playing. In Proc. of AAAI’07, p. 1134–1139.
Cohen D. A., Jeavons P., Jefferson C., Petrie K. E., Smith B. M. (2006). Symmetry definitions for constraint satisfaction problems. Constraints, vol. 11, no 2-3, p. 115–137.
Cox E., Schkufza E., Madsen R., Genesereth M. (2009). Factoring general games using propositional automata. In Ijcai’09 workshop on general game playing (giga’09), p. 13-20.
Darga P. T., Sakallah K. A., Markov I. L. (2008). Faster symmetry discovery using sparsity of symmetries. In Dac’08, p. 149–154. ACM.
Debruyne R., Bessière C. (1997). Some practicable filtering techniques for the constraint satisfaction problem. In Ijcai’97, p. 412–417.
Draper S., Rose A. (2014). Sancho. http://sanchoggp.blogspot.fr/2014/07/sancho-is-ggp-champion-2014.html.
Emslie R. (2015). Galvanise. https://bitbucket.org/rxe/galvanise_v2.
Finnsson H., Björnsson Y. (2008). Simulation-based approach to General Game Playing. In Aaai’08, p. 259–264. AAAI Press.
Finnsson H., Björnsson Y. (2011). Cadiaplayer: Search-control techniques. KI - Künstliche Intelligenz, vol. 25, no 1, p. 9–16.
Genesereth M., Björnsson Y. (2013). The international general game playing competition. AI Magazine, vol. 34, no 2, p. 107-111.
Genesereth M., Love N. (2005). General game playing: Overview of the aaai competition. AI Magazine, vol. 26, p. 62–72.
Koriche F., Lagrue S., Piette É., Tabary S. (2015). Résolution de scsp avec borne de confiance pour les jeux de stratégie. In Jfpc’15, p. 160-169.
Koriche F., Lagrue S., Piette É., Tabary S. (2016). General game playing with stochastic csp. Constraints, vol. 21, no 1, p. 95–114.
Lecoutre C., Likitvivatanavong C., Yap R. H. C. (2015). STR3: A path-optimal filtering algorithm for table constraints. Artificial Intelligence, vol. 220, p. 1–27.
Lifschitz V., Yang F. (2011). Eliminating function symbols from a nonmonotonic causal theory. In Knowing, reasoning, and acting: Essays in honour of hector j. levesque. College Publicaions.
Littman M. L., Majercik S. M., Pitassi T. (2001). Stochastic boolean satisfiability. Journal of Automated Reasoning, vol. 27, no 3, p. 251–296.
Love N., Genesereth M., Hinrichs T. (2006). General game playing: Game description language specification. Rapport technique no LG-2006-01. Stanford University.
McKay B. D., Piperno A. (2014). Practical graph isomorphism, {II}. Journal of Symbolic Computation, vol. 60, no 0, p. 94 - 112.
Mehat J., Cazenave T. (2008). An account of a participation to the 2007 general game playing competition. http://www.ai.univ-paris8.fr/~jm/ggp/ggp2008-2.pdf. (unpublished)
Möller M., Schneider M. T., Wegner M., Schaub T. (2011). Centurio, a general game player: Parallel, Java- and ASP-based. Künstliche Intelligenz, vol. 25, no 1, p. 17-24.
Méhat J., Cazenave T. (2011). A parallel general game player. KI - Künstliche Intelligenz, vol. 25, no 1, p. 43-47.
Sabin D., Freuder E. C. (1994). Contradicting conventional wisdom in constraint satisfaction. In ECAI’94, p. 125–129.
Schiffel S., Thielscher M. (2007). Fluxplayer: A successful general game player. In Aaai’07, p. 1191–1196. AAAI Press.
Schreiber S. (2014). Ggp.org - tiltyard gaming server. http://tiltyard.ggp.org/. (CS227b class at Stanford University)
Silver D., Huang A., Maddison C. J., Guez A., Sifre L., Driessche D. v. d. et al. (2016). Mastering the game of go with deep neural networks and tree search. Nature, vol. 529, p. 484–503.
Sturtevant N. R. (2008). An analysis of UCT in multi-player games. International Computer Games Association Journal, vol. 31, no 4, p. 195–208.
Thielscher M. (2005). Flux: A logic programming method for reasoning agents. Theory Pract. Log. Program., vol. 5, no 4-5, p. 533-565.
Thielscher M. (2010). A general game description language for incomplete information games. In Aaai’10.
Thielscher M. (2011a). GDL-II. KI - Künstliche Intelligenz, vol. 25, no 1, p. 63–66.
Thielscher M. (2011b). The general game playing description language is universal. In Ijcai’11, p. 1107–1112. AAAI Press.
Ullmann J. R. (2007). Partition search for non-binary constraint satisfaction. Information Sciences, vol. 177, no 18, p. 3639–3678.
Walsh T. (2009). Stochastic constraint programming. Computing Research Repository, vol. abs/0903.1152.
Zobrist A. (1990). A new hashing method with application for game playing. International Computer Games Association Journal, vol. 13, no 2, p. 69–73.