Recognizing Seki in Computer Go
Seki is a situation of coexistence in the game of Go, where neither player can profitably capture the opponent's stones. This paper presents a new method for deciding whether an enclosed area is or can become a seki. The method combines local search with global-level static analysis. Local search is used to identify possible seki, and reasoning on the global level is applied to determine which stones are safe with territory, which coexist in a seki and which are dead. Experimental results show that a safety-of-territory solver enhanced by this method can successfully recognize a large variety of local and global scale test positions related to seki. In contrast, the well-known program GNU Go can only solve easier problems from a test collection.

title: Lambda Depth-First Proof Number Search and Its Application to Go
abstract: Thomsen's λ search and Nagai's depth-first proof-number (DFPN) search are two powerful but very different AND/OR tree search algorithms. Lambda Depth-First Proof Number search (LDFPN) is a novel algorithm that combines ideas from both algorithms. λ search can dramatically reduce a search space by finding different levels of threat sequences. DFPN employs the notion of proof and disproof numbers to expand nodes expected to be easiest to prove or disprove. The method was shown to be effective for many games. Integrating λ order with proof and disproof numbers enables LDFPN to select moves more effectively, while preserving the efficiency of DFPN. LDFPN has been implemented for capturing problems in Go and is shown to be more efficient than DFPN and more robust than an algorithm based on classical λ search.

title: Action Elimination and Plan Neighborhood Graph Search: Two Algorithms for Plan Improvement
abstract: 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.

title: Automating Layouts of Sewers in Subdivisions
abstract: 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.

title: A General Solution to the Graph History Interaction Problem
abstract: 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.

title: Monte-Carlo Exploration for Deterministic Planning
abstract: 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.

title: Weblogs, Legitimacy and Organizations
abstract: The last decades have seen a movement of production to less economically developed countries. These countries often don’t meet Western social and environmental standards. Non-governmental organizations (NGOs) have challenged poor conditions such as child labor, discrimination or environmental pollution caused by suppliers. Purchasers are criticized in the public realm, which leads to damage to their reputation [Hansen and Schrader 2005; Gilbert 2003]. Nike, Dole Foods and GM have experienced such campaigns [Lawrence 2002]. Focal companies with direct contact to the end customer and big labels are most vulnerable to this strategy. A loss of reputation may weaken their ability to compete and result in decreasing sales volume [Hansen and Schrader 2005].

title: TabVer: A Case Study in Table Verbalization
abstract: 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.

title: PAN - The Prolog Analyzer