Jonathan Schaeffer

IJCAI Conference 2025 Conference Paper

Set-Based Retrograde Analysis: Precomputing the Solution to 28-card Bridge Double Dummy Deals

• Isaac Stone
• Nathan R. Sturtevant
• Jonathan Schaeffer

Among the most popular games played worldwide, Bridge stands out for having had little AI progress for over 25 years. Ginsberg's Partition Search algorithm (1996) was a breakthrough for double-dummy Bridge play, allowing a program to reason about sets of states rather than individual states. Partition Search supports the current state of the art for both bidding and cardplay. In the time since, virtually no progress has been made in Bridge bidding. Inspired by Ginsberg's idea, this paper presents Setrograde Analysis, a new set-based algorithm for perfectly solving Bridge hands. Using this approach, we have solved all 7-trick (28-card) hands — 10^30 states, which can be reduced to 10^17 unique states using preexisting techniques. This was done by considering five orders of magnitude fewer sets than the traditional state-based Retrograde Analysis algorithm. This work suggests that the entire 13-trick (52-card) state space can be solved with modern technology using this new approach. The 7-trick computation represents the largest endgame database to date in any game.

IJCAI Conference 2016 Conference Paper

Improved Heuristic and Tie-Breaking for Optimally Solving Sokoban

• Andr
• eacute; G. Pereira
• Robert Holte
• Jonathan Schaeffer
• Luciana S. Buriol
• Marcus Ritt

We present a novel admissible pattern database heuristic (D) and tie-breaking rule (L) for Sokoban, allowing us to increase the number of optimally solved standard Sokoban instances from 20 to 28 and the number of proved optimal solutions from 25 to 32 compared to previous methods. The previously best heuristic for Sokoban (I) used the idea of an intermediate goal state to enable the effective use of pattern database heuristics in transportation domains, where the mapping of movable objects to goal locations is not fixed beforehand. We extend this idea to allow the use of multiple intermediate goal states and show that heuristic I is no longer effective. We solve this problem and show that our heuristic D is effective in this situation. Sokoban is a well-known single-agent search domain characterized by a large branching factor, long solution lengths, and the presence of unsolvable states. Given the exponential growth in the complexity of standard Sokoban instances, the increase in the number of optimally solved instances represents a major advance in our understanding of how to search in extremely large search spaces.

AAAI Conference 2014 Conference Paper

Worst-Case Solution Quality Analysis When Not Re-Expanding Nodes in Best-First Search

• Richard Valenzano
• Nathan Sturtevant
• Jonathan Schaeffer

The use of inconsistent heuristics with A∗ can result in increased runtime due to the need to re-expand nodes. Poor performance can also be seen with Weighted A∗ if nodes are reexpanded. While the negative impact of re-expansions can often be minimized by setting these algorithms to never expand nodes more than once, the result can be a lower solution quality. In this paper, we formally show that the loss in solution quality can be bounded based on the amount of inconsistency along optimal solution paths. This bound holds regardless of whether the heuristic is admissible or inadmissible, though if the heuristic is admissible the bound can be used to show that not re-expanding nodes can have at most a quadratic impact on the quality of solutions found when using A∗. We then show that the bound is tight by describing a process for the construction of graphs for which a best-first search that does not re-expand nodes will find solutions whose quality is arbitrarily close to that given by the bound. Finally, we will use the bound to extend a known result regarding the solution quality of WA∗ when weighting a consistent heuristic, so that it also applies to other types of heuristic weighting.

AAAI Conference 2012 Conference Paper

Partial-Expansion A* with Selective Node Generation

• Ariel Felner
• Meir Goldenberg
• Guni Sharon
• Roni Stern
• Tal Beja
• Nathan Sturtevant
• Jonathan Schaeffer
• Robert Holte

A* is often described as being ‘optimal’, in that it expands the minimum number of unique nodes. But, A* may generate many extra nodes which are never expanded. This is a performance loss, especially when the branching factor is large. Partial Expansion A* (PEA*) (Yoshizumi, Miura, and Ishida 2000) addresses this problem when expanding a node, n, by generating all the children of n but only storing children with the same f-cost as n. n is re-inserted into the OPEN list, but with the f-cost of the next best child. This paper introduces an enhanced version of PEA* (EPEA*). Given a priori domain knowledge, EPEA* generates only the children with the same f-cost as the parent. EPEA* is generalized to its iterative-deepening variant, EPE-IDA*. For some domains, these algorithms yield substantial performance improvements. State-of-the-art results were obtained for the pancake puzzle and for some multi-agent pathfinding instances. Drawbacks of EPEA* are also discussed.

AAAI Conference 2011 Conference Paper

Block A*: Database-Driven Search with Applications in Any-Angle Path-Planning

• Peter Yap
• Neil Burch
• Robert Holte
• Jonathan Schaeffer

We present three new ideas for grid-based path-planning algorithms that improve the search speed and quality of the paths found. First, we introduce a new type of database, the Local Distance Database (LDDB), that contains distances between boundary points of a local neighborhood. Second, an LDDB-based algorithm is introduced, called Block A*, that calculates the optimal path between start and goal locations given the local distances stored in the LDDB. Third, our experimental results for any-angle path planning in a wide variety of test domains, including real game maps, show that Block A* is faster than both A* and the previously best gridbased any-angle search algorithm, Theta*.

AIJ Journal 2011 Journal Article

Inconsistent heuristics in theory and practice

• Ariel Felner
• Uzi Zahavi
• Robert Holte
• Jonathan Schaeffer
• Nathan Sturtevant
• Zhifu Zhang

In the field of heuristic search it is usually assumed that admissible heuristics are consistent, implying that consistency is a desirable attribute. The term “inconsistent heuristic” has, at times, been portrayed negatively, as something to be avoided. Part of this is historical: early research discovered that inconsistency can lead to poor performance for A⁎ (nodes might be re-expanded many times). However, the issue has never been fully investigated, and was not re-considered after the invention of IDA⁎. This paper shows that many of the preconceived notions about inconsistent heuristics are outdated. The worst-case exponential time of inconsistent heuristics is shown to only occur on contrived graphs with edge weights that are exponential in the size of the graph. Furthermore, the paper shows that rather than being something to be avoided, inconsistent heuristics often add a diversity of heuristic values into a search which can lead to a reduction in the number of node expansions. Inconsistent heuristics are easy to create, contrary to the common perception in the AI literature. To demonstrate this, a number of methods for achieving effective inconsistent heuristics are presented. Pathmax is a way of propagating inconsistent heuristic values in the search from parent to children. This technique is generalized into bidirectional pathmax (BPMX) which propagates values from a parent to a child node, and vice versa. BPMX can be integrated into IDA⁎ and A⁎. When inconsistent heuristics are used with BPMX, experimental results show a large reduction in the search effort required by IDA⁎. Positive results are also presented for A⁎ searches.

AAAI Conference 2011 Conference Paper

The Compressed Differential Heuristic

• Meir Goldenberg
• Nathan Sturtevant
• Ariel Felner
• Jonathan Schaeffer

The differential heuristic (DH) is an effective memory-based heuristic for explicit state spaces. In this paper we aim to improve its performance and memory usage. We introduce a compression method for DHs which stores only a portion of the original uncompressed DH, while preserving enough information to enable efficient search. Compressed DHs (CDH) are flexible and can be tuned to fit any size of memory, even smaller than the size of the state space. Furthermore, CDHs can be built without the need to create and store the entire uncompressed DH. Experimental results across different domains show that, for a given amount of memory, a CDH significantly outperforms an uncompressed DH.

AAAI Conference 2010 Conference Paper

Single-Frontier Bidirectional Search

• Ariel Felner
• Carsten Moldenhauer
• Nathan Sturtevant
• Jonathan Schaeffer

On the surface, bidirectional search (BDS) is an attractive idea with the potential for significant asymptotic reductions in search effort. However, the results in practice often fall far short of expectations. We introduce a new bidirectional search algorithm, Single-Frontier Bidirectional Search (SF- BDS). Unlike traditional BDS which keeps two frontiers, SF- BDS uses a single frontier. Each node in the tree can be seen as an independent task of finding the shortest path between the current start and current goal. At a particular node we can decide to search from start to goal or from goal to start, choosing the direction with the highest potential for minimizing the total work done. Theoretical results give insights as to when this approach will work and experimental data validates the algorithm for a broad range of domains.

IJCAI Conference 2009 Conference Paper

• Zhifu Zhang
• Nathan R. Sturtevant
• Robert Holte
• Jonathan Schaeffer
• Ariel Felner

Early research in heuristic search discovered that using inconsistent heuristics with A* could result in an exponential increase in the number of node expansions. As a result, the use of inconsistent heuristics has largely disappeared from practice. Recently, inconsistent heuristics have been shown to be effective in IDA*, especially when applying the bidirectional pathmax (BPMX) enhancement. This paper presents new worst-case complexity analysis of A*’s behavior with inconsistent heuristics, discusses how BPMX can be used with A*, and gives experimental results justifying the use of inconsistent heuristics in A* searches.

IJCAI Conference 2009 Conference Paper

• Nathan R. Sturtevant
• Ariel Felner
• Max Barrer
• Jonathan Schaeffer
• Neil Burch

AIJ Journal 2008 Journal Article

Duality in permutation state spaces and the dual search algorithm

• Uzi Zahavi
• Ariel Felner
• Robert C. Holte
• Jonathan Schaeffer

Geometrical symmetries are commonly exploited to improve the efficiency of search algorithms. A new type of symmetry in permutation state spaces, duality, is introduced. Each state has a dual state. Both states share important attributes such as their distance to the goal. Given a state S, it is shown that an admissible heuristic of the dual state of S is an admissible heuristic for S. This provides opportunities for additional heuristic evaluations. An exact definition of the class of problems where duality exists is provided. A new search algorithm, dual search, is presented which switches between the original state and the dual state when it seems likely that the switch will improve the chance of reaching the goal faster. The decision of when to switch is very important and several policies for doing this are investigated. Experimental results show significant improvements for a number of applications, for using the dual state's heuristic evaluation and/or dual search.

IJCAI Conference 2007 Conference Paper

• Adi Botea
• Martin M
• uuml; ller
• Jonathan Schaeffer

Research on macro-operators has a long history in planning and other search applications. There has been a revival of interest in this topic, leading to systems that successfully combine macro-operators with current state-of-the-art planning approaches based on heuristic search. However, research is still necessary to make macros become a standard, widely-used enhancement of search algorithms. This article introduces sequences of macro-actions, called iterative macros. Iterative macros exhibit both the potential advantages (e. g. , travel fast towards goal) and the potential limitations (e. g. , utility problem) of classical macros, only on a much larger scale. A family of techniques are introduced to balance this trade-off in favor of faster planning. Experiments on a collection of planning benchmarks show that, when compared to low-level search and even to search with classical macro-operators, iterative macros can achieve an impressive speed-up in search.

AAAI Conference 2007 System Paper

A Demonstration of ScriptEase Interruptible and Resumable Behaviors for CRPGs

• Maria Cutumisu
• Jonathan Schaeffer
• Curtis Onuczko

Intelligent non-player characters that exhibit realistic ambient behaviors produce more captivating and immersive stories for the player. However, the creation of nonrepetitive and entertaining behaviors is challenging, since it involves writing complex custom scripting code for thousands of characters in a common game adventure. This demonstration describes the generation of motivational behavior scripts using generative behavior patterns with ScriptEase. We demonstrate interruptible and resumable motivational ambient and latent behaviors for a tavern scene in a custom Neverwinter Nights game module.

AAAI Conference 2007 Conference Paper

Inconsistent Heuristics

• Uzi Zahavi
• Jonathan Schaeffer

In the field of heuristic search it is well-known that improving the quality of an admissible heuristic can significantly decrease the search effort required to find an optimal solution. Existing literature often assumes that admissible heuristics are consistent, implying that consistency is a desirable attribute. To the contrary, this paper shows that an inconsistent heuristic can be preferable to a consistent heuristic. Theoretical and empirical results show that, in many cases, inconsistency can be used to achieve large performance improvements.

AAAI Conference 2006 System Paper

ScriptEase – Motivational Behaviors for Interactive Characters in Computer Role-Playing Games

• Maria Cutumisu
• Jonathan Schaeffer
• Curtis Onuczko

ScriptEase is a tool that allows authors with no programming experience to create interactive stories for computer role-playing games. Instead of writing scripting code manually, game authors select design patterns that encapsulate frequent game scenarios, creating stories at a higher level of abstraction and being shielded from the underlying scripting language. ScriptEase has been extended to support behavior patterns that generate ambient behaviors for non-player characters. This demonstration shows how ScriptEase creates intricate non-player character scripts to generate compelling and engaging character behaviors. We demonstrate our ScriptEase motivational ambient and PC-interactive behaviors for a guard character using BioWare Corp.'s Neverwinter Nights game.

IJCAI Conference 2005 Conference Paper

Dual Lookups in Pattern Databases

• Ariel Felner
• Uzi Zahavi
• Jonathan Schaeffer
• Robert C

A pattern database (PDB) is a heuristic function stored as a lookup table. Symmetries of a state space are often used to enable multiple values to be looked up in a PDB for a given state. This paper introduces an additional PDB lookup, called the dual PDB lookup. A dual PDB lookup is always admissible but can return inconsistent values. The paper also presents an extension of the well-known pathmax method so that inconsistencies in heuristic values are propagated in both directions (childto-parent, and parent-to-child) in the search tree. Experiments show that the addition of dual lookups and bidirectional pathmax propagation can reduce the number of nodes generated by IDA* by over one order of magnitude in the TopSpin puzzle and Rubik’s Cube, and by about a factor of two for the sliding tile puzzles.

AIJ Journal 2002 Journal Article

Games, computers, and artificial intelligence

• Jonathan Schaeffer
• H.Jaap van den Herik

AAAI Conference 2002 Conference Paper

Memory-Efficient A* Heuristics for Multiple Sequence Alignment

• Matthew McNaughton
• Jonathan Schaeffer

The time and space needs of an A* search are strongly influenced by the quality of the heuristic evaluation function. Usually there is a trade-off since better heuristics may require more time and/or space to evaluate. Multiple sequence alignment is an important application for single-agent search. The traditional heuristic uses multiple pairwise alignments that require relatively little space. Three-way alignments produce better heuristics, but they are not used in practice due to the large space requirements. This paper presents a memory-efficient way to represent three-way heuristics as an octree. The required portions of the octree are computed on demand. The octree-supported three-way heuristics result in such a substantial reduction to the size of the A* open list that they offset the additional space and time requirements for the three-way alignments. The resulting multiple sequence alignments are both faster and use less memory than using A* with traditional pairwise heuristics.

AIJ Journal 2002 Journal Article

The challenge of poker

• Darse Billings
• Aaron Davidson
• Jonathan Schaeffer
• Duane Szafron

Poker is an interesting test-bed for artificial intelligence research. It is a game of imperfect information, where multiple competing agents must deal with probabilistic knowledge, risk assessment, and possible deception, not unlike decisions made in the real world. Opponent modeling is another difficult problem in decision-making applications, and it is essential to achieving high performance in poker. This paper describes the design considerations and architecture of the poker program Poki. In addition to methods for hand evaluation and betting strategy, Poki uses learning techniques to construct statistical models of each opponent, and dynamically adapts to exploit observed patterns and tendencies. The result is a program capable of playing reasonably strong poker, but there remains considerable research to be done to play at a world-class level.

AIJ Journal 2001 Journal Article

Sokoban: Enhancing general single-agent search methods using domain knowledge

• Andreas Junghanns
• Jonathan Schaeffer

Artificial intelligence (AI) research has developed an extensive collection of methods to solve state-space problems. Using the challenging domain of Sokoban, this paper studies the effect of general search enhancements on program performance. We show that the current state of the art in AI generally requires a large research and programming effort to use domain-dependent knowledge to solve even moderately complex problems in such difficult domains. The application of domain-specific knowledge to exploit properties of the search space can result in large reductions in the size of the search tree, often several orders of magnitude per search enhancement. This application-specific knowledge is discovered and applied using application-independent search enhancements. Understanding the effect of these enhancements on the search leads to a new taxonomy of search enhancements, and a new framework for developing single-agent search applications. This is used to illustrate the large gap between what is portrayed in the literature versus what is needed in practice.

TCS Journal 2001 Journal Article

Sokoban: improving the search with relevance cuts

• Andreas Junghanns
• Jonathan Schaeffer

Humans can effectively navigate through large search spaces, enabling them to solve problems with daunting complexity. This is largely due to an ability to successfully distinguish between relevant and irrelevant actions (moves). In this paper we present a new single-agent search pruning technique that is based on a move's influence. The influence measure is a crude form of relevance in that it is used to differentiate between local (relevant) moves and non-local (irrelevant) moves, with respect to the sequence of moves leading up to the current state. Our pruning technique uses the m previous moves to decide if a move is relevant in the current context and, if not, to cut it off. This technique results in a large reduction in the search effort required to solve Sokoban problems.

IJCAI Conference 1999 Conference Paper

Domain-Dependent Single-Agent Search Enhancements

• Andreas Junghanns
• Jonathan Schaeffer

AAAI Conference 1999 Conference Paper

Using Probabilistic Knowledge and Simulation to Play Poker

• Darse Billings
• Lourdes Peña
• Jonathan Schaeffer
• Duane Szafron
• University of Alberta

Until recently, artificial intelligence researchers who use games as their experimental testbed have concentrated on games of perfect information. Many of these games have been amenable to so-called brute-force search techniques. In contrast, games of imperfect information, such as bridge and poker, contain hidden knowledge making similar search techniques impractical. This paper describes recent progress in developing a high-performance poker-playing program. The advances come in two forms. First, we introduce a new betting strategy that returns a probabilistic betting decision, a probability triple, that gives the likelihood of a fold, call or raise occurring in a given situation. This routine unifies all the expert knowledge used in the program, does a better job of representing the type of decision making needed to play strong poker, and improves the way information is propagated throughout the program. Second, real-time simulations are used to compute the expected values of betting decisions. The program generates an instance of the missing data, subject to any constraints that have been learned, and then simulates the rest of the game to determine a numerical result. By repeating this a sufficient number of times, a statistically meaningful sample can be obtained to be used in the program’s decision-making process. Experimental results show that these enhancements each represent major advances in the strength of computer poker programs.

AAAI Conference 1998 Conference Paper

Opponent Modeling in Poker

• Darse Billings
• Jonathan Schaeffer

Poker is an interesting test-bed for artificial intelligence research. It is a game of imperfect knowledge, where multiple competing agents must deal with risk management, agent modeling, unreliable information and deception, much like decision-making applications in the real world. Agent modeling is one of the most difficult problems in decision-making applications and in poker it is essential to achieving high performance. This paper describes and evaluates Loki, a poker program capable of observing its opponents, constructing opponent models and dynamically adapting its play to best exploit patterns in the opponents’ play.

AIJ Journal 1996 Journal Article

Best-first fixed-depth minimax algorithms

• Aske Plaat
• Jonathan Schaeffer
• Wim Pijls
• Arie de Bruin

This article has three main contributions to our understanding of minimax search: First, a new formulation for Stockman's SSS∗ algorithm, based on Alpha-Beta, is presented. It solves all the perceived drawbacks of SSS∗, finally transforming it into a practical algorithm. In effect, we show that SSS∗ = Alpha-Beta + transposition tables. The crucial step is the realization that transposition tables contain so-called solution trees, structures that are used in best-first search algorithms like SSS∗. Having created a practical version, we present performance measurements with tournament game-playing programs for three different minimax games, yielding results that contradict a number of publications. Second, based on the insights gained in our attempts at understanding SSS∗, we present a framework that facilitates the construction of several best-first fixed-depth game-tree search algorithms, known and new. The framework is based on depth-first null-window Alpha-Beta search, enhanced with storage to allow for the refining of previous search results. It focuses attention on the essential differences between algorithms. Third, a new instance of this framework is presented. It performs better than algorithms that are currently used in most state-of-the-art game-playing programs. We provide experimental evidence to explain why this new algorithm, MTD(f), performs better than other fixed-depth minimax algorithms.

IJCAI Conference 1995 Conference Paper

Best-First Fixed-Depth Game-Tree Search in Practice

• Aske Plaat
• Jonathan Schaeffer
• Wim Pijls
• Arie de Bruin

We present a new paradigm for minimax search algorithms: MT, a memory-enhanced version of Pearl's Test procedure. By changing the way MT is called, a number of practical best-first search algorithms can be simply constructed. Reformulating SSS* as an instance of MT eliminates all its perceived implementation drawbacks. Most assessments of minimax search performance are based on simulations that do not address two key ingredients of high performance game-playing programs: iterative deepening and memory usage. Instead, we use experimental data gathered from tournament checkers, Othello and chess programs. The use of iterative deepening and memory makes our results differ significantly from the literature. One new instance of our framework, MTD(/), out-performs our best Alpha-Beta searcher on leaf nodes, total nodes and execution time. To our knowledge, these are the first reported results that compare both depth-first and bestfirst algorithms given the same amount of memory.

AIJ Journal 1992 Journal Article

A world championship caliber checkers program

• Jonathan Schaeffer
• Joseph Culberson
• Norman Treloar
• Brent Knight
• Paul Lu
• Duane Szafron

The checkers program Chinook has won the right to play a 40-game match for the World Checkers Championship against Dr. Marion Tinsley. This was earned by placing second, after Dr. Tinsley, at the 1990 U. S. National Open, the biennial event used to determine a challenger for the championship. This is the first time a program has earned the right to contest for a human world championship. In an exhibition match played in December 1990, Tinsley narrowly defeated Chinook 7. 5-6. 5. This paper describes the program, the research problems encountered and our solutions. Many of the techniques used for computer chess are directly applicable to computer checkers. However, the problems of building a world championship caliber program force us to address some issues that have, to date, been largely ignored by the computer chess community.

IJCAI Conference 1991 Conference Paper

The Role of Chess in Artificial Intelligence Research Robert Levinson (Chair)

• Feng-hsiung Hsu
• T. Anthony Marsland
• Jonathan Schaeffer
• David E

AIJ Journal 1990 Journal Article

Conspiracy numbers

• Jonathan Schaeffer

McAllester's conspiracy numbers algorithm is an exciting, new minimax search procedure that builds trees to variable depths in an application-independent manner. The algorithm selectively expands nodes in the tree trying to narrow the range of plausible minimax values at the root of the search tree. It does so by computing the conspiracy number for each possible root value; the minimum number of leaf nodes that must change their score to cause the root to change to that value. This paper describes the algorithm and presents an implementation in a computer chess program. Experimental results give rise to optimism about the algorithm's future, although there are still some serious problems to be overcome.

AIJ Journal 1987 Journal Article

Low overhead alternatives to SSS∗

• T.A. Marsland
• Alexander Reinefeld
• Jonathan Schaeffer

Of the many minimax algorithms, sss∗ is noteworthy because it usually searches the smallest game trees. Its success can be attributed to the accumulation and use of information acquired while traversing the tree. The main disadvantages of sss∗ are its high storage needs and management costs. This paper describes a class of methods, based on the popular alpha-beta algorithm, that acquire and use information to guide a tree search. They retain a given search direction and yet are as good as sss∗, even while searching random trees. Further, although some of these new algorithms also require substantial storage, they are more flexible and can be programmed to use only the space available, at the cost of some degradation in performance.

IJCAI Conference 1985 Conference Paper

Information Acquisition in Minimal Window Search

• Alexander Reinefeld
• Jonathan Schaeffer
• T. A. Marsland

IJCAI Conference 1985 Conference Paper

The Utility of Expert Knowledge

• Jonathan Schaeffer
• T A. Marsland