Catálogo de publicaciones - libros

Who is the best chess player of all time? Chess players are often interested in this question that has never been answered authoritatively, because it requires a comparison between chess players of different eras who never met across the board. In this contribution, we attempt to make such a comparison. It is based on the evaluation of the games played by the World Chess Champions in their championship matches. The evaluation is performed by the chess-playing program Crafty . For this purpose we slightly adapted Crafty . Our analysis takes into account the differences in players’ styles to compensate the fact that calm positional players in their typical games have less chance to commit gross tactical errors than aggressive tactical players. Therefore, we designed a method to assess the difficulty of positions. Some of the results of this computer analysis might be quite surprising. Overall, the results can be nicely interpreted by a chess expert.

While recently the strength of chess-playing programs has grown immensely, their capability of explaining in human understandable terms why some moves are good or bad has enjoyed little attention. Progress towards programs with an ability to provide intelligent commentary on chess games, either played by a program or by a human, has been negligible in comparison with the progress concerning playing strength. The typical style of a program’s “comments” (in terms of the best variations and their numerical scores) is of little use to a human who wants to learn important concepts behind the variations. In this paper, we present some core mechanisms for automated commenting in terms of relevant goals to be achieved or preserved in a given position. By combining these mechanisms with an actual chess engine we were able to transform this engine into a chess tutor/annotator that is capable of generating rather intelligent commentary. The main advantages of our work over related approaches are: (a) it has the ability to act as a tutor for the whole game of chess, and (b) it has a relatively solid chess understanding and is thus able to adequately comment on positional aspects.

We propose a highly selective heuristic search algorithm for capturing problems in Go. This iterative deepening search works on the crucial chain in which the prey block is located. The algorithm starts using three order liberties of the chain as the basis of the position evaluation, the value is then adjusted by the presence of few liberty-surrounding opponent blocks. The algorithm solved most capturing problems in Kano’s four volumes of graded Go problems. Moreover, it is fast enough to be used by Go programs in real time.

This paper presents Safety Solver 2.0 , a safety-of-territory solver for the game of Go that can solve problems in areas with open boundaries. Previous work on assessing safety of territory has concentrated on regions that are completely surrounded by stones of one player. Safety Solver 2.0 can identify open boundary problems under real game conditions, and generate moves for invading or defending such areas. Several search enhancements improve the solver’s performance. The experimental results demonstrate that the solver can find good moves in small to medium-size open boundary areas.

In the last decade, proof-number search and Monte-Carlo methods have successfully been applied to the combinatorial-games domain. Proof-number search is a reliable algorithm. It requires a well defined goal to prove. This can be seen as a disadvantage. In contrast to proof-number search, Monte-Carlo evaluation is a flexible stochastic evaluation for game-tree search. In order to improve the efficiency of proof-number search, we introduce a new algorithm, Monte-Carlo Proof-Number search. It enhances proof-number search by adding the flexible Monte-Carlo evaluation. We present the new algorithm and evaluate it on a sub-problem of Go, the Life-and-Death problem. The results show a clear improvement in time efficiency and memory usage: the test problems are solved two times faster and four times less nodes are expanded on average. Future work will assess possibilities to extend this method to other enhanced Proof-Number techniques.

In games, Monte-Carlo simulations can be used as an evaluation function for Alpha-Beta search. Assuming w is the width of the search tree, d its depth, and g the number of simulations at each leaf, then the total number of simulations is at least $g \times (2 \times w^{\frac{d}{2}}$ ). In games where moves permute, we propose to replace this algorithm by a new algorithm, Virtual Global Search , that only needs g ×2^ d simulations for a similar number of games per leaf. The algorithm is also applicable to games where moves often but not always permute, such as Go. We specify the application for 9×9 Go.

A Monte-Carlo evaluation consists in estimating a position by averaging the outcome of several random continuations. The method can serve as an evaluation function at the leaves of a min-max tree. This paper presents a new framework to combine tree search with Monte-Carlo evaluation, that does not separate between a min-max phase and a Monte-Carlo phase. Instead of backing-up the min-max value close to the root, and the average value at some depth, a more general backup operator is defined that progressively changes from averaging to min-max as the number of simulations grows. This approach provides a fine-grained control of the tree growth, at the level of individual simulations, and allows efficient selectivity. The resulting algorithm was implemented in a 9×9 Go-playing program, Crazy Stone , that won the 10th KGS computer-Go tournament.

We present several results concerning the number of positions and games of Go. We derive recurrences for L ( m , n ), the number of legal positions on an m × n board, and develop a dynamic programming algorithm which computes L ( m , n ) in time O ( m ^3 n ^2 λ ^ m ) and space O ( m λ ^ m ), for some constant λ < 5.4. An implementation of this algorithm enables us to list L ( n , n ) for n  ≤ 17. For larger boards, we prove the existence of a base of liberties $\lim \sqrt[mn]{L(m,n)}$ of ~2.9757341920433572493. Based on a conjecture about vanishing error terms, we derive an asymptotic formula for L ( m , n ), which is shown to be highly accurate. We also study the Game Tree complexity of Go, proving an upper bound on the number of possible games of ( mn )^ L ( m , n ) and a lower bound of $2^{2^{n^2/2\,-O(n)}}$ on n × n boards and $2^{2^{n-1}}$ on 1 × n boards, in addition to exact counts for mn  ≤ 4 and estimates up to mn  = 9. Most proofs and some additional results had to be left out to observe the page limit. They may be found in the full version available at [8].

Expert knowledge is crucial for improving the strength of computer Chinese-Chess programs. Although a great deal of expert knowledge is available in text format that using natural languages, manually transforming it into computer readable forms is time consuming and difficult. Written expert annotations of Chinese-Chess games show different styles. By analyzing and collecting commonly used phrases and patterns from experts’ annotations, we introduce a novel pattern matching strategy. It automatically epitomises knowledge from a large number of annotated game records. The results of the experiments on the analysis of the middle phase of games indicate that our strategy achieves a low error rate. We hope to exploit this approach to collect automatically a great diversity of Chinese-Chess knowledge that is currently in text format.

We present a concise and/or-tree notation for describing Hex strategies together with an easily implemented algorithm for verifying strategy correctness. To illustrate our algorithm, we use it to verify Jing Yang’s 7×7 centre-opening strategy.