Adversarial search with procedural knowledge heuristic

ABSTRACT

We introduce an adversarial planning algorithm based on game tree search, which is applicable in large-scale multiplayer domains. In order to tackle the scalability issues of game tree search, the algorithm utilizes procedural knowledge capturing how individual players tend to achieve their goals in the domain; the information is used to limit the search only to the part of the game tree that is consistent with pursuing players' goals. We impose no specific requirements on the format of the procedural knowledge; any programming language or agent specification paradigm can be employed. We evaluate the algorithm both theoretically and empirically, confirming that the proposed approach can lead to a substantial search reduction with only a minor negative impact on the quality of produced solutions.

REFERENCES

• 1: D. Billings, A. Davidson, T. Schauenberg, N. Burch, M. Bowling, R. C. Holte, J. Schaeffer, and D. Szafron. Game-tree search with adaptation in stochastic imperfect-information games. In Computers and Games, volume 3846 of LNCS, pages 21--34. Springer, 2004.
• 2: D. Carmel and S. Markovitch. Learning and using opponent models in adversary search. Technical Report CIS9609, Technion, 1996.
• 3: Tolga Könik , John E. Laird, Learning goal hierarchies from structured observations and expert annotations, Machine Learning, v.64 n.1-3, p.263-287, September 2006 [doi>10.1007/s10994-006-7734-8]
• 4: A. Kovarsky and M. Buro. Heuristic search applied to abstract combat games. In Canadian Conference on AI, pages 66--78, 2005.
• 5: C. Luckhardt and K. B. Irani. An algorithmic solution of n-person games. In Proc. of the National Conference on Artificial Intelligence (AAAI-86), Philadelphia, Pa., August, pages 158--162, 1986.
• 6: K. J. Mock. Hierarchical heuristic search techniques for empire-based games. In Proceedings of the International Conference on Artificial Intelligence (IC-AI), pages 643--648, 2002.
• 7: F. Sailer, M. Buro, and M. Lanctot. Adversarial planning through strategy simulation. In IEEE Symposium on Computational Intelligence and Games (CIG), pages 80--87, 2007.
• 8: E. Semsch, V. Lisý, B. Bošanský, M. Jakob, D. Pavlíček, J. Doubek, and M. Pechoucek. Adversarial behavior testbed. Technical Report GLR 90/09, CTU, FEE, Gerstner Lab., 2009. http://agents.felk.cvut.cz/publications.
• 9: S. J. J. Smith, D. S. Nau, and T. A. Throop. Computer bridge - a big win for AI planning. AI Magazine, 19(2):93--106, 1998.
• 10: Michael van Lent , John E. Laird, Learning procedural knowledge through observation, Proceedings of the 1st international conference on Knowledge capture, October 22-23, 2001, Victoria, British Columbia, Canada [doi>10.1145/500737.500765]
• 11: D. E. Wilkins. Using patterns and plans in chess. Artificial Intelligence, 14(2):165--203, 1980.
• 12: Steven Willmott , Julian Richardson , Alan Bundy, Applying adversarial planning techniques to go, Theoretical Computer Science, v.252 n.1-2, p.45-82, Feb. 6, 2001 [doi>10.1016/S0304-3975(00)00076-1]

INDEX TERMS

Primary Classification:
  I. Computing Methodologies
  I.2 ARTIFICIAL INTELLIGENCE
      I.2.8 Problem Solving, Control Methods, and Search
          Subjects: Plan execution, formation, and generation

Additional Classification:
  I. Computing Methodologies
  I.2 ARTIFICIAL INTELLIGENCE
      I.2.8 Problem Solving, Control Methods, and Search
          Subjects: Heuristic methods

General Terms:
Algorithms

Keywords:
agents, artificial intelligence, complex domain, experimental (systems/architectures), game tree search, goals, procedural knowledge