Arrow Research search

Author name cluster

Jonathan Schaeffer

Possible papers associated with this exact author name in Arrow. This page groups case-insensitive exact name matches and is not a full identity disambiguation profile.

32 papers
1 author row

Possible papers

32

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.

PDF Details DOI

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.

PDF Details

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.

PDF Details

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.

PDF Details

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*.

PDF Details

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.

PDF Details

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.

PDF Details

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.

PDF Details

IJCAI Conference 2009 Conference Paper

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

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.

PDF Details

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.

PDF Details

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.

PDF Details

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.

PDF Details

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.

PDF

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.

PDF Details

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.

PDF Details

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.

PDF Details

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.

PDF