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].
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.
10869144
Reinforcement Learning of Local Shape in the Game of Go
We explore an application to the game of Go of a reinforcement learning approach based on a linear evaluation function and large numbers of binary features. This strategy has proved effective in game playing programs and other reinforcement learning applications. We apply this strategy to Go by creating over a million features based on templates for small fragments of the board, and then use temporal difference learning and self-play. This method identifies hundreds of low level shapes with recognisable significance to expert Go players, and provides quantitive estimates of their values. We analyse the relative contributions to performance of templates of different types and sizes. Our results show that small, translation-invariant templates are surprisingly effective. We assess the performance of our program by playing against the Average Liberty Player and a variety of computer opponents on the 9×9 Computer Go Server. Our linear evaluation function appears to outperform all other static evaluation functions that do not incorporate substantial domain knowledge.
16720277
Depth-First Discovery Algorithm for incremental topological sorting of directed acyclic graphs
We study the problem of incrementally maintaining a topological sorting in a large DAG. The Discovery Algorithm of Alpern et al. [Proc. 1st Annual ACM-SIAM Symp. on Discrete Algorithms, 1990, pp. 32–42] computes a cover K f nodes such that a solution to the modified problem can be found by changing node priorities within K only. It achieves a runtime complexity that is polynomially bounded in terms of the minimal cover size k. The temporary space complexity of DA grows quickly with increasing number of added edges and cover size. We in the Depth-First Discovery Algorithm (DFDA), which uses depth-first search to reduce the temporary space of D O(|A| × ‖K‖) to O(|A| + ‖K‖), where|A| is the number of edges to add and ‖K‖ is theextended size of the cover. DFDA is simpler than DA and performs better in our empirical tests.  2003 Elsevier B.V. All rights reserved.
36197283
Using Artificial Boundaries in the Game of Go
Local search in the game of Go is easier if local areas have well-defined boundaries. An artificial boundary consists of temporarily added stones that close off an area. This paper describes a new general framework for finding boundaries in a way such that existing local search methods can be used. Furthermore, by using a revised local UCT search method, it is shown experimentally that this framework increases performance on local Go problems with open boundaries.
2893516
Fast Planning with Iterative Macros
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 macrooperators 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.
39962861
Weblogs, Legitimacy and Organizations
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].
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.