Editor's note: This paper was originally published in the 2000 Game Developer's Conference proceedings

Contents

1. Introduction

3.1 Game Trees and Minimax Search

3.2 Iterative Deepening

4.0 Reimplementing A*

4.3 The History of Heuristic

4.3 The History Heuristic

We usually sort moves in IDA* based on a static move ordering: the moves that have the lowest h values are searched first. Can we do better with a dynamic move ordering? For IDA*, move ordering doesn't really do us a lot of good, except in the last (and largest) iteration, where we find the solution. If we can find the solution early in the last iteration, we can avoid searching a large number of nodes. Thus, we want to acquire information over the course of a search that will help us bias the last search owards the solution.

A sliding-tile experimentgave a description for a history heuristic for the 15-puzzle. The history heuristic was stored in a 3-dimensional array. The three dimensions were the tiles (16) in each position (16) moving in each direction (4). To install information, the experiment counted the number of times that a move led to the deepest subtree (i.e. attained the smallest h value for an examined node within its subtree). The experiment met with some success, as the IDA* algorithm searched approximately 6% less nodes when the history heuristic was used versus the version that used a static move ordering.

We could use both the static move ordering and the dynamic information gathered by the history heuristic to generate a hybrid heuristic for ordering successors. This type of hybrid heuristic could improve the ordering of moves more than either technique in isolation.

5. Conclusions

We have implemented the techniques described above, and we are currently using them to plot paths for our creatures in our soon-to-be-released role-playing game, Neverwinter Nights.

There are many caveats to using these techniques, and it is important to be able to understand the drawbacks. The speed improvements that these techniques yield will vary depending on your application (they vary dramatically when implementing them in chess, Othello and checkers programs!) ... but you now have some new enhancements that can help you search more efficiently.

To summarize the utility of adding standard enhancements to search algorithms, let us examine another problem: finding push-optimal solutions for Sokoban problems. If you have never seen the game Sokoban, a picture of one of the 90 positions is given in Figure 4. The goal is for the little worker to push all of the round stones into the goal squares (the goal squares are shaded with diagonal lines). On the surface, this may seem as easy as pathfinding, and an easy application for A*. However, all pathfinding "mistakes" are undoable by retracing the path. One wrong push of a stone could leave you in a state where you are unable to complete the task. Thus, the need to plan the path of all stones to the goal squares is paramount.

Figure 4. Puzzle 1 from Sokoban.

IDA* is incapable of solving any of the puzzles with 20 million nodes searched. If we enhance IDA* with the transposition table and the move ordering techniques, 4 of the puzzles can be solved. If we search one billion nodes, only 6 of the 90 puzzles can be solved using IDA*, transposition tables and move ordering. If we use all of the domain-dependent techniques the researchers developed (including deadlock tables, tunnel macros, goal macros, goal cuts, pattern search, relevance cuts and overestimation), the program Rolling Stone can solve 52 of the 90 problems within the billion node limit for each puzzle [Junghanns 1999]. Pathfinding is a relatively trivial problem in comparison to finding push-optimal solutions for Sokoban puzzles, and I am happy to say my bosses at BioWare haven't asked me to solve Sokoban in real time.

There's a lot of very good academic information on single-agent search (including a special issue of the journal Artificial Intelligence later this year which will be devoted to the topic), and I would encourage everyone to look up some of these references. If you have any further questions on any of the reference material, please feel free to e-mail me.

Mark Brockington is the lead research scientist at BioWare Corp. His email adress is markb@bioware.com

References

[Breuker 1996] D. M. Breuker, J. W. H. M. Uiterwijk, and H. J. van den Herik. Replacement Schemes and Two-Level Tables. ICCA Journal, 19(3):175-179, 1996.

[Greenblatt 1967] R. D. Greenblatt, D. E. Eastlake, and S.D. Crocker. The Greenblatt Chess Program. In Proceedings of the Fall Joint Computer Conference, volume 31, pages 801-810, 1967.

P. E. Hart, N. J. Nilsson, and B. Raphael. A Formal Basis for the Heuristic Determination of Minimum Cost Paths. IEEE Transactions on Systems Science and Cybernetics, SSC-4(2):100-107, 1968.

[Junghanns 1997] A. Junghanns and J. Schaeffer. Sokoban: A Challenging Single-Agent Search Problem, Workshop Using Games as an Experimental Testbed for AI Research, IJCAI-97, Nagoya, Japan, August 1997.

[Junghanns 1999] A. Junghanns. Pushing the Limits: New Developments in Single-Agent Search, PhD Thesis, Department of Computing Science, University of Alberta, 1999. URL: http://www.cs.ualberta.ca/~games/Sokoban/papers.html

D. E. Knuth and R. W. Moore. An Analysis of Alpha-Beta Pruning. Artificial Intelligence, 6(3):293-326, 1975.

R. E. Korf. Depth-First Iterative Deepening: An Optimal Admissible Tree Search. Artificial Intelligence, 27:97-109, 1985.

[Nilsson 1971] N. J. Nilsson. Problem-Solving Methods in Artificial Intelligence. McGraw-Hill Book Company, New York, NY, 1971.

A. Plaat, J. Schaeffer, W. Pijls, and A. de Bruin. Exploiting Graph Properties of Game Trees. In AAAI-1996, volume 1, pages 234-239, Portland, Oregon, August 1996.

[Reinefeld 1983] A. Reinefeld. An Improvement to the Scout Tree-Search Algorithm. ICCA Journal, 6(4):4-14, 1983.

[Reinefeld 1994a] A. Reinefeld. A Minimax Algorithm Faster than Alpha-Beta. In H.J. van den Herik, I.S. Herschberg and J.W.H.M. Uiterwijk, editors, Advances In Computer Chess 7, pages 237-250. University of Limburg, 1994.

[Reinefeld 1994b] A. Reinefeld and T. A. Marsland. Enhanced Iterative-Deepening Search. IEEE Transactions on Pattern Analysis and Machine Intelligence, PAMI-16(7):701-710,1994.

[Schaeffer 1989] J. Schaeffer. The History Heuristic and Alpha-Beta Search Enhancements In Practice. IEEE Transactions on Pattern Analysis and Machine Intelligence, PAMI-11(11): 1203-1212, 1989.

J. J. Scott. A Chess-Playing Program. In B. Meltzer and D. Michie, editors, Machine Intelligence 4, pages 255-265. Edinburgh University Press, 1969.

D. J. Slate and L. R. Atkin. Chess 4.5 - The Northwestern University Chess Program. In P.W. Frey, editor, Chess Skill in Man and Machine, pages 82-118. Springer-Verlag, New York, 1977.


G. C. Stockman. A Minimax Algorithm Better than Alpha-Beta? Artificial Intelligence, 12:179-196, 1979.

W. B. Stout. Smart Moves: Intelligent Path-Finding. Game Developer, pp. 28-35, Oct./Nov. 1996.

[von Neumann 1944] J. von Neumann and O. Morgenstern. Theory of Games and Economic Behavior. Princeton Press, Princeton, NJ, 1944

Discuss this article in Gamasutra's discussion forums

________________________________________________________

[Back To] 1. Introduction