18731885
A solution to the GHI problem for depth-first proof-number search
The Graph-History interaction (GHI) problem is a notorious problem that causes game-playing programs to occasionally return incorrect solutions. This paper presents a practical method to cure the GHI problem for the case of the df-pn algorithm. Results in the game of Go with the situational super-ko rule show that the overhead incurred by our method is very small, while correctness is always guaranteed.
6537199
Monte-Carlo Exploration for Deterministic Planning
Search methods based on Monte-Carlo simulation have recently led to breakthrough performance improvements in difficult game-playing domains such as Go and General Game Playing. Monte-Carlo Random Walk (MRW) planning applies Monte-Carlo ideas to deterministic classical planning. In the forward chaining planner ARVAND, Monte-Carlo random walks are used to explore the local neighborhood of a search state for action selection. In contrast to the stochastic local search approach used in the recent planner Identidem, random walks yield a larger and unbiased sample of the search neighborhood, and require state evaluations only at the endpoints of each walk. On IPC-4 competition problems, the performance of ARVAND is competitive with state of the art systems.
13487020
Action Elimination and Plan Neighborhood Graph Search: Two Algorithms for Plan Improvement
Compared to optimal planners, satisficing planners can solve much harder problems but may produce overly costly and long plans. Plan quality for satisficing planners has become increasingly important. The most recent planning competition IPC-2008 used the cost of the best known plan divided by the cost of the generated plan as an evaluation metric. This paper proposes and evaluates two simple but effective methods for plan improvement: Action Elimination improves an existing plan by repeatedly removing sets of irrelevant actions. Plan Neighborhood Graph Search finds a new, shorter plan by creating a plan neighborhood graph PNG(π) of a given plan π, and then extracts a shortest path from PNG(π). Both methods are implemented in the ARAS postprocessor and are empirically shown to improve the result of several planners, including the top four planners from IPC-2008, under competition conditions.
14046564
Automating Layouts of Sewers in Subdivisions
An important part of the creation of a housing subdivision is the design and layout of sewers underneath the road. This is a challenging cost optimization problem in a continuous threedimensional space. In this paper, heuristic-search-based techniques are proposed for tackling this problem. The result is new algorithms that can quickly find near optimal solutions that offer important reductions in the cost of design and construction.
16970275
An Improved Safety Solver for Computer Go
Most Go-playing programs use a combination of search and heuristics based on an influence function to determine whether territories are safe. However, to assure the correct evaluation of Go positions, the safety of stones and territories must be proved by an exact method. 
 
The first exact algorithm, due to Benson [1], determines the unconditional safety of stones and completely surrounded territories. Muller [3] develops static rules for detecting safety by alternating play, and introduces search-based methods. 
 
This paper describes new, stronger search-based techniques including region-merging and a new method for efficiently solving weakly dependent regions. In a typical final position, more than half the points on the board can be proved safe by our current solver. This almost doubles the number of proven points compared to the 26.4% reported in [3].
1488238
A General Solution to the Graph History Interaction Problem
Since the state space of most games is a directed graph, many game-playing systems detect repeated positions with a transposition table. This approach can reduce search effort by a large margin. However, it suffers from the so-called Graph History Interaction (GHI) problem, which causes errors in games containing repeated positions. This paper presents a practical solution to the GHI problem that combines and extends previous techniques. Because our scheme is general, it is applicable to different game tree search algorithms and to different domains. As demonstrated with the two algorithms αβ and df-pn in the two games checkers and Go, our scheme incurs only a very small overhead, while guaranteeing the correctness of solutions.
11516969
PAN - The Prolog Analyzer
31682567
Automated Modular Termination Proofs for Real Prolog Programs
We present a methodology for checking the termination of Prolog programs that can be automated and is scalable. Furthermore, the proposed method can be used to locate errors. It has been successfully implemented as part of a tool that uses static analysis based on formal methods in order to validate Prolog programs. This tool is aimed at supporting the design and maintenance of Prolog programs.
34011032
TabVer: A Case Study in Table Verbalization
The purpose of this paper is to give a brief overview of TabVer, a front-end component that verbalizes large tables generated by a commercial expert system.