[en] We consider the move generation in a modern board game where the set of all the possible moves is too large to be generated. The idea is to provide a set of simple abstract tactics that would allow enough combinations to provide strong opposition. The reduced search space is then traversed using the alpha beta search. We also propose a technique that allows us to remove the stochasticity from the search space. The model was tested in a game called Axis and Allies: a modern, turn-based, perfect information, non-deterministic, strategy board game. We first show that a tree search technique based on a restrained set of moves can beat the actual scripted AI engine --- E.Z. Fodder. We can conclude from the experiments that searching deeper generates complex maneuvers which in turn significantly increase the likelihood of victory.
Disciplines :
Computer science
Author, co-author :
Lupien St-Pierre, David ; Université de Liège - ULiège > Dép. d'électric., électron. et informat. (Inst.Montefiore) > Dép. d'électric., électron. et informat. (Inst.Montefiore)
Winands, M.H.M.
Watt, D.A.
Language :
English
Title :
A Selective Move Generator for the Game Axis and Allies
S. Russel and P. Norvig, Artificial Intelligence: A Modern Approach, 2nd ed. New Jersey, USA: Pearson Education inc., 2003.
D. E. Knuth and R. W. Moore, "An Analysis of Alpha-Beta Pruning," Artificial Intelligence, vol. 6, no. 4, pp. 293-326, 1975.
M. P. D. Schadd, M. H. M. Winands, and J. W. H. M. Uiterwijk, "CHANCEPROBCUT: Forward Pruning in Chance Nodes," in IEEE Symposium on Computational Intelligence and Games (CIG 2009), P. L. Lanzi, Ed., 2009, pp. 178-185.
J. J. Smith and D. S. Nau, "An Analysis of Forward Pruning," in AAAI-94, 1994, pp. 138-1391.
J. Schaeffer, "Experiments in Search and Knowledge," Ph.D. dissertation, Departement of Computing Science, University of Waterloo, Waterloo, Canada, 1986.
H. Berliner, G. Goetsch, M. S. Campbell, and C. Ebeling, "Measuring the Performance Potential of Chess Programs," Artificial Intelligence, vol. 43, no. 1, pp. 7-20, 1990. (Pubitemid 20717232)
A. Junghanns and J. Schaeffer, "Search versus Knowledge in Game-Playing Programs Revisited," in IJCAI-97, 1997, pp. 692-697.
M. Müller, "Computer Go," Artificial Intelligence, vol. 134, no. 1-2, pp. 145-179, 2002. (Pubitemid 34086582)
B. Brügmann, "Monte Carlo Go," Physics Department, Syracuse University, Tech. Rep., 1993.
J. von Neumann, "Zur Theorie der Gesellschaftsspiele," Mathematis-che Annalen 100, pp. 295-320, 1928, translated by Bargmann (1959).
L. Kocsis and C. Szepesvári, "Bandit based Monte-Carlo Planning," in Proceedings of the EMCL 2006, ser. LNCS, J. Fürnkranz, T. Scheffer, and M. Spiliopoulou, Eds., vol. 4212. Berlin: Springer-Verlag, Heidelberg, Germany, 2006, pp. 282-293. (Pubitemid 44618839)
S. Gelly and Y. Wang, "Exploration exploitation in Go: UCT for Monte-Carlo Go," in NIPS Workshop on Online Trading of Exploration and Exploitation, 2006.
I. Millington, Artificial Intelligence for Games. San Francisco, CA: Morgan Kaufmann, 2006.
J. Schaeffer, "Long-range planning in computer chess," in ACM '83: Proceedings of the 1983 annual conference on Computers: Extending the human resource. New York, NY, USA: ACM, 1983, pp. 170-179.
D. Wilkins, "Using patterns and plans in chess," Artificial intelligence, vol. 14, no. 2, pp. 165-203, 1980.
J. Pitrat, "A chess combination program which uses plans," Artificial Intelligence, vol. 8, no. 3, pp. 275-321, 1977.
G. Trippen, "Plans, patterns, and move categories guiding a highly selective search," in Advances in Computer Games (ACG 2009), ser. LNCS, H. J. van den Herik and P. Spronck, Eds., vol. 6048, 2010, pp. 111-122.
R. C. Bell, Board and Table Games from Many Civilizations, 2nd ed. New York, USA: Dover Publications inc., 1950
D. L. St-Pierre, "Mind Games: Axis and Allies," Master's thesis, Glasgow University, Glasgow, Scotland, 2009.
S. J. Johansson, "On using Multi-Agent Systems in Playing Board Games," in Fifth International Joint Conference on Autonomous Agents and MultiAgent Systems, Hakodate, Japan, 2006, pp. 569-576. (Pubitemid 46609519)
F. Olsson, "A Multi-Agent System for Playing the Board Game Risk," Master's thesis, Blekinge Institute of Technology, Karlskrona, Sweden, 2005.
D. E. Loeb, "Challenge in Multi-player Gaming by Computers," The Diplomatic PouchZine, vol. S1995M, 1995.
C. E. Shannon, "Programming a Computer for Playing Chess," Philosophical Magazine, vol. 41, no. 4, pp. 256-275, 1950.
I. Szita, G. M. J.-B. Chaslot, and P. Spronck, "Monte-Carlo Tree Search in Settlers of Catan," in Advances in Computer Games (ACG 2009), ser. LNCS, H. J. van den Herik and P. Spronck, Eds., vol. 6048, 2010, pp. 21-32.
R. Lorentz, "Amazons Discover Monte-Carlo," in Computers and Games (CG 2008), ser. LNCS, H. J. van den Herik, X. Xu, Z. Ma, and M. H. M. Winands, Eds., vol. 5131, 2008, pp. 13-24.
R.-K. Balla and A. Fern, "UCT for Tactical Assault Planning in RealTime Strategy Game," in IJCAI-09, 2009, pp. 40-45.
P. Ciancarini and G. P. Favini, "Representing Kriegspiel States with Metapositions," in IJCAI-07, 2007, pp. 2450-2455.
A. Junghanns, "Are there Practical Alternatives to Alpha-Beta in Computer Chess?" ICCA, vol. 21, no. 1, pp. 14-32, 1998.
G. M. J.-B. Chaslot, M. H. M. Winands, J. W. H. M. Uiterwijk, H. J. van den Herik, and B. Bouzy, "Progressive Strategies for Monte-Carlo Tree Search," New Mathematics and Natural Computation, vol. 4, no. 3, pp. 343-357, 2008.
R. Coulom, "Efficient Selectivity and Backup Operators in Monte-Carlo Tree Search," in Computers and Games (CG 2006), ser. LNCS, H. J. van den Herik, P. Ciancarini, and H. H. L. M. Donkers, Eds., vol. 4630. Springer-Verlag, Heidelberg, Germany, 2007, pp. 72-83.
D. Michie, "Game-Playing and Game-Learning Automata," in Advances in Programming and Non-Numerical Computation, L. Fox, Ed., Pergamon, New York, USA, 1966, pp. 183-200.
B. W. Ballard, "The *-Minimax Search Procedure for Trees Containing Chance Nodes," Artificial Intelligence, vol. 21, no. 3, pp. 327-350, 1983.
T. Hauk, M. Buro, and J. Schaeffer, "*-Minimax Performance in Backgammon," in Computers and Games (CG 2004), ser. LNCS, H. J. van den Herik, Y. Björnsson, and N. S. Netanyahu, Eds., vol. 3846. Springer-Verlag, 2006, pp. 51-66.
M. Müller, M. Enzenberger, and J. Schaeffer, "Temperature Discovery Search," in Nineteenth National Conference on Artificial Intelligence (AAAI 2004), San Jose, CA, 2004, pp. 658-663.
M. Pfeiffer, "Reinforcement learning of strategies for Settlers of Catan," in International Conference on Computer Games: Artificial Intelligence, Design and Education, Reading, UK, 2004, pp. 384-388.
This website uses cookies to improve user experience. Read more
Save & Close
Accept all
Decline all
Show detailsHide details
Cookie declaration
About cookies
Strictly necessary
Performance
Strictly necessary cookies allow core website functionality such as user login and account management. The website cannot be used properly without strictly necessary cookies.
This cookie is used by Cookie-Script.com service to remember visitor cookie consent preferences. It is necessary for Cookie-Script.com cookie banner to work properly.
Performance cookies are used to see how visitors use the website, eg. analytics cookies. Those cookies cannot be used to directly identify a certain visitor.
Used to store the attribution information, the referrer initially used to visit the website
Cookies are small text files that are placed on your computer by websites that you visit. Websites use cookies to help users navigate efficiently and perform certain functions. Cookies that are required for the website to operate properly are allowed to be set without your permission. All other cookies need to be approved before they can be set in the browser.
You can change your consent to cookie usage at any time on our Privacy Policy page.
