This paper presents a method of evaluating game tree search methods including standard min-max search with heuristic evaluation functions and Monte Carlo tree search, which recently achieved drastic improvements in the strength of Computer Go programs. The basic idea of this paper is to use an averaged win probability of positions having similar evaluation values. Accuracy measures of evaluation values with respect to win probabilities can be used to assess the performance of game tree search methods. A plot of win probabilities against evaluation values should have consistency and monotonicity if the evaluation values are produced by a good game tree search method. By inspecting whether the plot has the properties for some subset of positions, we can detect specific deficiencies in the game tree search method. We applied our method to Go, Shogi, and Chess, and by comparing the results with empirical understanding of the performance of various game tree search methods and with the results of self-plays, we show that our method is efficient and effective.
This paper presents a framework for a dynamic move generation in quiescece search, using information of game positions. In order to obtain stable evaluation, quiescence search is introduced in chess-like games. Generally, capture moves and check moves are generated, however, it is not known that what kind of move shuould be generated. In this paper, we prepare check move generator, using predictor of threatmate, as an example of dynamic move generator in Shogi. Our experiments showed the effectiveness of dynamic move generation in quiescence search, and showed that the effective moves in quiescence search are different by game phase.
Recent improvements to Monte Carlo tree search have produced strong computer Go programs. This paper presents a method of measuring the accuracy of Monte Carlo tree search in game programming. We use the win percentage of positions in a large database of game records as a benchmark and compare the win probability obtained by simulations with the benchmark. By applying our method to Monte Carlo tree search in Go, we found differences between search methods and their parameters, and the effect of the properties of positions such as the move numbers and the existence of stones in threats. This paper also introduces numerical metrics to evaluate the performance of search methods. Our experiments in Go, as well as Chess, Othello, and Shogi revealed that the metrics were quite close to our empirical understanding of the performance of various search methods and their parameters.
Recent improvements on Monte Carlo tree search have produced strong computer Go programs. This paper presents a method of measuring the accuracy of Monte Carlo tree searches in game programming. We use win percentage of positions in a large database of game records as a benchmark and compare the win probability obtained by simulations with the benchmark. By applying to Monte Carlo tree search in Go, we found out the difference between the search methods and their parameters, and the effect of property of positions such as Ko. In this paper, we also introduce numerical metrics to evaluate the performance of search methods. Our experiments in Go showed that the metrics are quite close to our empirical understanding of the performance of various search methods and their parameters.
In order to perform efficient search, we have improved methods for search control. Existing methods that use difference of evaluation values but do not use the evaluation value itself. In this paper, we present a method for margin control based on information content. We estimate a win probability by an evaluation value, and estimate information content by the win probability, then change the margin according to the information content. We applied this method to Singular Extension and Futility Pruning in Chess. Improvement is confirmed by solving problems and by self-play.
Strong game programs need accurate evaluation functions that predict win ratio for a given state. However, it is not easy to construct such functions. We propose to plot evaluation values and win ratio for some sets of states, with an existing evaluation function. If multiple curves appear, it shows that the evaluation function does not work well for states in a certain condition. Improvement is accomplished if new evaluation curves fit into one curve. We applied this method to Shogi, Chess, and Othello, and showed that by plotting values and win ratios we can visualize the faults of evaluation functions. And our experiments with Shogi showed that we can confirm improvement of evaluation function by plotting values and win ratios. Moreover, significant improvement on strength is confirmed by self-plays.
We propose a method of visualizing and adjusting the evaluation functions in game programming in this paper. It is widely recognized that an evaluation function should assign a higher evaluation-value to a position with greater probability of a win. However, this relation has not been utilized directly to tune evaluation functions because of the difficulty of measuring the probability of wins in deterministic games. We propose the use of win percentage to utilize this relation in positions having the same evaluation-value as win probability, where the positions we used were stored in a large database of game records. We introduce an evaluation-curve formed by evaluation-values and win probabilities, to enable evaluation functions to be visualized. We observed that evaluation -curves form a sigmoid in various kinds of games and that these curves may split depending on the properties of positions. Because such splits indicate that an evaluation function that is visualized misestimates positions with less probability of winning, we can improve this by fitting evaluation-curves to one. Our experiments with Chess and Shogi revealed that deficiencies in evaluation functions could successfully be visualized, and that improvements by automatically adjusting their weights were confirmed by self-plays.
In this paper, we present a new method for adjusting evaluation functions based on relation between static values and win ratios, and show its effectiveness. Accurate evaluation functions are important for strong game program, however, it is not easy to find out problems in existing evaluation functions. Incorrect evaluation functions assign incorrect prediction of win ratio for states in a certain condition. Therfore, we focus on relation between evaluation values and win ratio, and propose to plot them in a graph for each set of states. If an evaluation function works bad for states in a certain condition, a line of the relation for those states will be drawn apart from lines of the relation for other states. We applied this method for Shogi, and showed that usual evaluation functions work bad for states where the difference between king safety of both players is large. Then, we constructed a new evaluation function considering the difference between king safety of both players and automatically adjusted its weights. Significant improvement on strength is confirmed in self-play, and showed effectiveness of this method.
In this paper, we propose to apply ProbCut into quiescence search in Shogi, and show its effectiveness. ProbCut is a sophisticated technique for selective search, Insed on cork.elation between results of shallow search and deep search. It was Originally intrudeced in Othello?),and already successfully applied to Chess. However, in plevious work on Shogi, the effectiveness of ProbCut has been very limited in a sense that ProbCut has not succeeded to make significantly strong program. It is mainly because evaluation of positions are much more difficult in Shogi and the correlation is not so stlong Compared to other games. In order to resolve this difficulty, we introduced ProbCut into quiescence search instead of normal(toplevel) search. In experiments on solving standard test set of Shogi, we show that our program with PlobCut solves more Problems in less time compared to original version. Its strongness is also confirmed by self play results (50 win, 30 lose).
In this paper, we propose a heuristic method for detection of threatmate moves. Although it is important to identify threatmate in Shogi, computer players cannot afford to find out sufficient number of threatmate moves in practice because exact detection of them requires checkmate search whose computational cost is very large. Thus, we constructed an efficient method that empirically detects threatmate moves. Our method employs a linear combination of such features that analyze the properties of a move and properties of a given position. The output of our function is the confidence of threatmate, where a move is considered to be threatmate if its confidence is higher than a predetermined threshold. One can control trade-off between recall and precision by adjusting the threshold, because larger (smaller) number of moves are reported to be threatmate as lower (higher) threshold is used. We adjusted the parameters of our function by means of least squares, by using threatmate moves and non-threatmate moves appeared in real game records, and confirmed that our function is comparable or superior to existing functions in our experiments.
This material is presented to ensure timely dissemination of scholarly and technical work. Copyright and all rights therein are retained by authors or by other copyright holders. All persons copying this information are expected to adhere to the terms and constraints invoked by each author's copyright. In most cases, these works may not be reposted without the explicit permission of the copyright holder.
.AN)2008 IEEE. Personal use of this material is permitted. However, permission to reprint/republish this material for advertising or promotional purposes or for creating new collective works for resale or redistribution to servers or lists, or to reuse any copyrighted component of this work in other works must be obtained from the IEEE
AAAI hereby grants to the above authors, and the employers for whom the work was performed, royalty-free permission to:
Notice for the use of the materials listed below.
The copyright of the materials is retained by the Information Processing Society of Japan (IPSJ). The materials is published on this web site with the agreement of the author (s) and the IPSJ. Please be complied with Copyright Law of Japan and the Code of Ethics of the IPSJ if any users wish to reproduce, make derivative work, distribute or make available to the public any part or whole thereof. All Rights Reserved, Copyright (C) Information Processing Society of Japan.