Nothing Special   »   [go: up one dir, main page]
Skip to main content
Springer Nature Link
Log in

CadiaPlayer: Search-Control Techniques

  • Fachbeitrag
  • Published:
KI - Künstliche Intelligenz Aims and scope Submit manuscript

Abstract

Effective search control is one of the key components of any successful simulation-based game-playing program. In General Game Playing (GGP), learning of useful search-control knowledge is a particularly challenging task because it must be done in real-time during online play. In here we describe the search-control techniques used in the 2010 version of the GGP agent CadiaPlayer, and show how they have evolved over the years to become increasingly effective and robust across a wide range of games. In particular, we present a new combined search-control scheme (RAVE/MAST/FAST) for biasing action selection. The scheme proves quite effective on a wide range of games including chess-like games, which have up until now proved quite challenging for simulation-based GGP agents.

This is a preview of subscription content, log in via an institution to check access.

Access this article

Log in via an institution

Subscribe and save

Springer+ Basic
$34.99 /Month
  • Get 10 units per month
  • Download Article/Chapter or eBook
  • 1 Unit = 1 Article or 1 Chapter
  • Cancel anytime
Subscribe now

Buy Now

Price excludes VAT (USA)
Tax calculation will be finalised during checkout.

Instant access to the full article PDF.

Institutional subscriptions

Fig. 1
Fig. 2
Fig. 3

Similar content being viewed by others

Explore related subjects

Discover the latest articles, news and stories from top researchers in related subjects.

Notes

  1. Skirmish is a chess-like game. We used the variation played in the 2007 GGP finals where each player has two knights, two bishops, two rooks, and four pawns (can only move by capturing). The objective is to capture as many of the opponent’s pieces as possible. Breakthrough is played on a chess board where the players, armed with two ranks of pawns, try to be the first to break through to reach the opponent’s back rank. The pawns can move forward and diagonally, but can only capture diagonally. Chinook is a variant of Breakthrough played with checkers pawns and the added twist that two independent games are played simultaneously, one on the white squares and another on the black ones. 3D Tic-Tac-Toe and Nine Board Tic-Tac-Toe are variants of Tic-Tac-Toe; the former is played on a 4×4×4 cube, and in the latter 9 Tic-Tac-Toe boards are placed in a 3×3 grid formation, and on each turn a player can play only on the board having the same coordinate as the last cell marked by the opponent (e.g., if the opponent marked a center cell in one of the boards, the player must on his turn play in the Tic-Tac-Toe board in the center). TTCC4 is a hybrid of several games where each player has a chess pawn, a chess knight, and a checkers king—these pieces respawn on their start square if captured. Instead of moving a piece a player can choose to drop a disk onto the board like in Connect 4 (captured disks do not respawn). The goal is to form a 3-in-a-row formation with your pieces anywhere on the 3×3 center squares of the table. Full game descriptions can be found on the Dresden GGP server (http://euklid.inf.tu-dresden.de:8180/ggpserver).

References

  1. Banerjee B, Stone P (2007) General game learning using knowledge transfer. In: Veloso MM (ed) 20th IJCAI, pp 672–677

    Google Scholar 

  2. Björnsson Y, Finnsson H (2009) CADIAPlayer: a simulation-based general game player. IEEE Trans Comput Intell AI in Games 1(1):4–15

    Article  Google Scholar 

  3. Chaslot G, Winands M, van den Herik JH, Uiterwijk J, Bouzy B (2007) Progressive strategies for Monte-Carlo tree search. In: 10th JCIS, heuristic search and computer game playing session

    Google Scholar 

  4. Clune J (2007) Heuristic evaluation functions for general game playing. In: Holte RC, Howe A (eds) 22nd AAAI. AAAI Press, Menlo Park, pp 1134–1139

    Google Scholar 

  5. Coulom R (2006) Efficient selectivity and backup operators in Monte-Carlo tree search. In: van den Herik HJ, Ciancarini P, Donkers HHLM (eds) CG2006. Springer, Berlin, pp 72–83

    Google Scholar 

  6. Cox E, Schkufza E, Madsen Ryan MG (2009) Factoring general games using propositional automata. In: GIGA’09 the IJCAI workshop on general game playing

    Google Scholar 

  7. Enzenberger M, Müller M (2009) Fuego—an open-source framework for board games and Go engine based on Monte-Carlo tree search. Tech Rep 09-08, Dept of Computing Science, University of Alberta

  8. Finnsson H, Björnsson Y (2008) Simulation-based approach to general game playing. In: Fox D, Gomes CP (eds) 23rd AAAI. AAAI Press, Menlo Park, pp 259–264

    Google Scholar 

  9. Finnsson H, Björnsson Y (2010) Learning simulation-control in general game-playing agents. In: Fox M, Poole D (eds) 24th AAAI. AAAI Press, Menlo Park, pp 954–959

    Google Scholar 

  10. Gelly S, Silver D (2007) Combining online and offline knowledge in UCT. In: Ghahramani Z (ed) 24th ICML, vol 227. ACM, New York, pp 273–280

    Chapter  Google Scholar 

  11. Gelly S, Wang Y, Munos R, Teytaud O (2006) Modification of UCT with patterns in Monte-Carlo Go. Technical Report 6062, INRIA

  12. Genesereth MR, Love N, Pell B (2005) General game playing: overview of the AAAI competition. AI Mag 26(2):62–72

    Google Scholar 

  13. Günther M, Schiffel S, Thielscher M (2009) Factoring general games. In: GIGA’09 the IJCAI workshop on general game playing

    Google Scholar 

  14. Kirci M, Schaeffer J, Sturtevant N (2009) Feature learning using state differences. In: GIGA’09 the IJCAI workshop on general game playing

    Google Scholar 

  15. Kocsis L, Szepesvári C (2006) Bandit based Monte-Carlo planning. In: ECML, pp 282–293

    Google Scholar 

  16. Kuhlmann G, Dresner K, Stone P (2006) Automatic heuristic construction in a complete general game player. In: 21st AAAI, pp 1457–1462

    Google Scholar 

  17. Kuhlmann G, Stone P (2007) Graph-based domain mapping for transfer learning in general games. In: 18th ECML

    Google Scholar 

  18. Lorentz RJ (2008) Amazons discover Monte-Carlo. In: van den Herik HJ, Xu X, Ma Z, Winands MHM (eds) CG2008. Lecture notes in computer science, vol 5131. Springer, Berlin, pp 13–24

    Google Scholar 

  19. Love N, Hinrichs T, Genesereth M (2006) General game playing: game description language specification. Technical Report, Stanford University, 4 April 2006

  20. Pell B (1996) A strategic metagame player for general chess-like games. Comput Intell 12:177–198

    Article  Google Scholar 

  21. Schiffel S (2010) Symmetry detection in general game playing. In: Fox M, Poole D (eds) 24th AAAI, pp 980–985. AAAI Press, Menlo Park

    Google Scholar 

  22. Schiffel S, Thielscher M (2007) Automatic construction of a heuristic search function for general game playing. In: Veloso MM (ed) 7th IJCAI workshop on nonmontonic reasoning, action and change (NRAC07)

    Google Scholar 

  23. Schiffel S, Thielscher M (2007) Fluxplayer: a successful general game player. In: Holte RC, Howe A (eds) 22nd AAAI, AAAI Press, Menlo Park, pp 1191–1196

    Google Scholar 

  24. Schiffel S, Thielscher M (2009) Automated theorem proving for general game playing. In: Boutilier C (ed) 21st IJCAI. Morgan Kaufmann, San Francisco, pp 911–916

    Google Scholar 

  25. Sharma S, Kobti Z, Goodwin S (2008) Knowledge generation for improving simulations in UCT for general game playing. In: AI 2008: advances in artificial intelligence. Springer, Berlin, pp 49–55

    Chapter  Google Scholar 

  26. Sutton RS (1988) Learning to predict by the methods of temporal differences. Mach Learn 3:9–44

    Google Scholar 

  27. Thielscher M (2010) A general game description language for incomplete information games. In: Fox M, Poole D (eds) 24th AAAI. AAAI Press, Menlo Park, pp 994–999

    Google Scholar 

  28. Thielscher M, Voigt S (2010) A temporal proof system for general game playing. In: Fox M, Poole D (eds) 24th AAAI. AAAI Press, Menlo Park, pp 1000–1005

    Google Scholar 

  29. Waugh K (2009) Faster state manipulation in general games using generated code. In: GIGA’09 the IJCAI workshop on general game playing

    Google Scholar 

Download references

Author information

Authors and Affiliations

  1. Reykjavík University, Menntavegur 1, 101, Reykjavík, Iceland

    Hilmar Finnsson & Yngvi Björnsson

Authors
  1. Hilmar Finnsson
    View author publications

    You can also search for this author in PubMed Google Scholar

  2. Yngvi Björnsson
    View author publications

    You can also search for this author in PubMed Google Scholar

Corresponding author

Correspondence to Yngvi Björnsson.

Rights and permissions

Reprints and permissions

About this article

Cite this article

Finnsson, H., Björnsson, Y. CadiaPlayer: Search-Control Techniques. Künstl Intell 25, 9–16 (2011). https://doi.org/10.1007/s13218-010-0080-9

Download citation

  • Received:

  • Accepted:

  • Published:

  • Issue Date:

  • DOI: https://doi.org/10.1007/s13218-010-0080-9

Keywords

Search

Navigation