Retrograde analysis is used in game-playing programs to solve states at the end of a game, working backwards toward the start of the game. The algorithm iterates through and computes the perfect-play value for as many states as resources allow. We introduce setrograde analysis which achieves the same results by operating on sets of states that have the same game value. The algorithm is demonstrated by computing exact solutions for Bridge double dummy card-play. For deals with 24 cards remaining to be played ( 10 27 states, which can be reduced to 10 15 states using preexisting techniques), we strongly solve all deals. The setrograde algorithm performs a factor of 10 3 fewer search operations than a standard retrograde algorithm, producing a database with a factor of 10 4 fewer entries. For applicable domains, this allows retrograde searching to reach unprecedented search depths. 1 Introduction Some of the early high-performance game-playing programs relied on retrograde analysis and endgame databases for strong play. The most notable example is Checkers, where 39 trillion endgame positions, all those with 10 or fewer pieces, were used as part of the C HINOOK program (Scha-effer et al. 1992), and for solving Checkers (Schaeffer et al. 2007). Endgame databases are also used widely in Chess programs (Chess 2024), as well as in many other games (e.g., for solving A wari (Romein and Bal 2003)). Endgame databases are most effective in games where there are far fewer positions at the end of the game than elsewhere. As a result, they have not been applied in games that do not have this property. For instance, Sturtevant (2003) noted that in 3-player Chinese Checkers a winning arrangement of a single player's pieces in the game has approximately 10 23 possible permutations of the other player's pieces, making it infeasible to store all the variations of even a single winning configuration. While in Chinese Checkers each player has a unique endgame configuration (the other side's piece locations are irrelevant), in Go the locations of both side's pieces in a terminal state are important. Hence these games require significantly different analysis (Berlekamp and Wolfe 1994). In a 4-player trick-based card game such as Bridge, the last two tricks have null 52 2 nullnull 50 2 nullnull 48 2 nullnull 46 2 null = 1 . However, there are only 16 ways for each deal to play out, meaning it is trivial to solve but storing all states (as done in Checkers) is difficult.

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 re-expanded. 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.

GBFS-based satisficing planners often augment their search with knowledge-based enhancements such as preferred operators and multiple heuristics. These techniques seek to improve planner performance by making the search more informed. In our work, we will focus on how these enhancements impact coverage and we will use a simple technique called epsilon-greedy node selection to demonstrate that planner coverage can also be improved by introducing knowledge-free random exploration into the search. We then revisit the existing knowledge-based enhancements so as to determine if the knowledge these enhancements employ is offering necessary guidance, or if the impact of this knowledge is to add exploration which can be achieved more simply using randomness. This investigation provides further evidence of the importance of preferred operators and shows that the knowledge added when using an additional heuristic is crucial in certain domains, while not being as effective as random exploration in others. Finally, we demonstrate that random exploration can also improve the coverage of LAMA, a planner which already employs multiple enhancements. This suggests that knowledge-based enhancements need to be compared to appropriate knowledge-free random baselines so as to ensure the importance of the knowledge being used.

As the video game industry grows, both developers and creative authors seek new ways to simplify the process of controlling story content using scripts. This paper describes a story model and its software implementation, ScriptEase II, designed to solve this game design bottleneck. ScriptEase II is the second generation of the ScriptEase system, whose goal was to enable game authors with no programming ability to generate scripting code from high-level game patterns. ScriptEase II differs from the original in two important ways. First, ScriptEase II uses game-dependent translators to generate scripts for any game engine. Second, ScriptEase II uses a drag-and-drop interface that simplifies the story component creation menus that grew cumbersome in the original ScriptEase. The feasibility of code generation has been validated using three different game engines and the advantages of the simple drag-and-drop interface have been validated by a user study.

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

Several variants of A* have been recently proposed for find-ing optimal solutions for the multi-agent pathfinding (MAPF)problem. However, these variants have not been deeply com-pared either quantitatively or qualitatively. In this paper weaim to fill this gap. In addition to obtaining a deeper under-standing of the existing algorithms, we describe in detail theapplication of the new enhanced partial-expansion techniqueto MAPF and show how pattern databases can be applied ontop of this technique.

Path planning is a critical part of modern computer games; rare is the game where nothing moves and path planning is unneeded. A* is the workhorse for most path planning applications. Block A* is a state-of-the-art algorithm that is always faster than A* in experiments using game maps. Unlike other methods that improve upon A*'s performance, Block A* is never worse than A* nor require any knowledge of the map. In our experiments, Block A* is ideal for games with randomly generated maps, large maps, or games with a highly dynamic multi-agent environment. Furthermore, in the domain of grid-based any-angle path planning, we show that Block A* is an order of magnitude faster than the previous best any-angle path planning algorithm, Theta*. We empirically show our results using maps from Dragon Age: Origins and Starcraft. Finally, we introduce ``populated game maps'' as a new test bed that is a better approximation of real game conditions than the standard test beds of this field. The main contributions of this paper is a more rigorous set of experiments for Block A*, and introducing a new test bed (populated game maps) that is a more accurate representation of actual game conditions than the standard test beds.

This demonstration describes ScriptEase II, a tool that allows game story authors to generate scripts that control objects in video games by manipulating high level story patterns and game objects. ScriptEase II can generate scripting code for any game engine for which a translator is written. Currently there are translators for Neverwinter Nights and real Pinball games.

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 grid-based any-angle search algorithm, Theta*.

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.