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

1. Introduction

Most of you with Computer Science training have probably been through the typical Artificial Intelligence lecture on search and planning. You are shown A*, with some trivial example (so your professor doesn't get lost while doing it) which shows all of the various parts of A*. You've also
sat through the proof of why A* generates an optimal solution when it has an admissible heuristic. If you're really lucky, you get to implement A* in Lisp or Prolog in an assignment, and solve a puzzle involving sliding tiles.

Jump ahead a few years, and you've been given the task of implementing a pathfinding algorithm for your game. You shift through your notes, trying to remember why you need a CLOSED list, and how to translate all the car() and cdr() instructions from Lisp into something that your lead programmer won't bring up during your next performance review. You study web sites on AI and pathfinding, try a few enhancements, and eventually come up with a solution that behaves in a very similar manner to the A* algorithm from your notes.

In an alternate universe, there are academics and hobbyists that concentrate on computer games of thought, such as chess, checkers and Othello. There are regular tournaments between programs, and the two main ways to outplay your opponent and win the game involve outsearching your opponent and having a smarter (but still computationally fast) evaluation of positions. I have heard each of these statements while chatting with other Othello programmers during tournaments. Do these statements sound like anything you've heard a programmer in your company mention?

• "I don't trust C++ to generate fast code, so I'm still using ANSI C."
• "I coded the inner loop in assembly. It took me two months of work, but it speeds up the program by 10%, so it was worth it."
• "I've had about eight hours of sleep in 72 hours, but I've improved the performance."

Computer chess programmers been dealing with a search algorithm (cryptically called ab) for the last 25 years. They have a library of standard enhancements that they can use to enhance ab and improve the performance of their program without having to resort to learning MIPS processor machine language, or trying to acquire knowledge about what sort of positions their program handles poorly.

Academics involved in the field often quoted the desire to beat the World Chess Champion in a game of chess to get their research funding. However, IBM and Deep Blue brought the funding train to a screeching halt. Most have moved onto games that are significantly harder for the computer to do well at, such as Poker, Bridge and Go. However, others realized that A* search really is not all that different from .

When we cast aside the superficial differences between the two algorithms, we quickly discover A* and ab are actually remarkably similar, and we can use the standard search enhancements from the typical computer chess program in your pathfinding algorithm. We will be describing the subset of the computer chess based search enhancements that we use in our pathfinding code at BioWare.

Section 2 will quickly review the standard A* algorithm (so you do not have to dig out your AI lecture notes again). Section 3 will discuss the anatomy of a computer chess search algorithm, and Section 4 shows you how to put the search enhancements into A*.

2. A Really Brief Review of A*

A* [Hart 1968, Nilsson 1971] is one of the preferred methods of dealing with the pathfinding problem. A* search starts with the initial state in a main data structure known as the OPEN list. The CLOSED list represents the positions that the algorithm has already examined, and is initially empty. For each node within the OPEN and CLOSED lists, A* maintains two heuristic values: g(n), the best-known minimum cost, and h(n), the estimate of the cost to a goal state. Thus, the best node to examine at any point in the algorithm has the lowest estimated cost: f(n) = g(n) + h(n).

The A* algorithm is an iterative process. In each step, A* takes the best state s from the OPEN list and moves it to the CLOSED list. The successors of the best state, si, are generated and examined in turn. If a successor si does not appear in either the OPEN or CLOSED list, then si is added to the OPEN list. However, if si already appears in either list, we must check to see if the minimum cost g(n) has decreased. If g(n) decreases, the node si must be deleted from its current location and reinserted into the OPEN list.

The heuristic h(n) is critical for the performance of the A* algorithm. h(n) is said to be admissible if the heuristic never overestimates the cost of travelling to the goal state. This is important because if h(n) is admissible, A* is guaranteed to generate the least cost or optimal solution the first time the goal node is generated. In the case of the typical pathfinding algorithm, h(n) is the straight line distance between the current point n and the target point.

Figure 1. A Start and Goal Position For The Sliding-Tile Puzzle.

Some of the performance information referenced in this paper refers to the sliding-tile puzzle instead of pathfinding, since this has been the most popular test in academic circles for studying A*. An example of the sliding-tile puzzle can be found in Figure 1. In the sliding-tile puzzle, the Manhattan distance (the sum of the vertical and horizontal displacements of each tile from its current square to its goal square) is an admissible and effective heuristic for use in A* search.

3. The Anatomy Of A Chess Program

Now that we have quickly reviewed A*, let us deal with a computer chess search algorithm.

Games such as chess, checkers and Othello belong to a broad group of games called two-player zero-sum games with perfect information. Zero-sum implies that if one player wins, the other player loses. Perfect information implies the entire state of the game is known at any time. Scrabble has hidden tiles, and is defined as a game of imperfect information.

Two-player zero-sum games with perfect information are well known to game theoreticians [von Neumann 1944]. In any position for a game in this category, an optimal move can be determined. An optimal move can be determined via the minimax algorithm which, for a game like chess, contains a matrix that has been estimated to contain more molecules than our entire planet! However, all hope is not lost, since there are alternative formulations of the minimax algorithm that involve searching a game tree.