Search

Shogi is a major chess variant in Japan. This article presents two shogi competitions: the World Computer Shogi Championship, the largest annual competition held by the Computer Shogi Association, and The Floodgate, which is a complementary internet competition held voluntarily by researchers. Notable technical contributions made by participants and useful resources for prospective developers are also presented. The techniques and therefore playing strength are still improving, partly because both competitions have attracted active participants, even after the playing strength of computer programs has apparently surpassed that of human players.

AlphaZero achieved superhuman performance in Go, chess, and shogi, supported by massive computational re-sources. This paper investigates policy learning in AlphaZero, aiming at improving its learning efficiency. AlphaZero trains policy and value networks that are similar to those in a standard reinforcement learning setting, but in a different way closely coupled with game tree search in self-play. Inspired by recent studies that investigate policy optimization in tree search, we apply PPO, which is a state-of-the method for learning policy in reinforcement learning, into AlphaZero’s style learning. Then, we show its effectiveness in a small but interesting game where the database made by retrograde analysis is available. The results support that our method improves the sample efficiency in the learning.

Catan is a strategic board game with many interesting properties, including multi-player, imperfect information, stochasticity, a complex state space structure (hexagonal board where each vertex, edge and face has its own features, cards for each player, etc.), and a large action space (including trading). Therefore, it is challenging to build AI agents by Reinforcement Learning (RL), without domain knowledge nor heuristics. In this paper, we introduce cross-dimensional neural networks to handle a mixture of information sources and a wide variety of outputs, and empirically demonstrate that the network dramatically improves RL in Catan. We also show that, for the first time, a RL agent can outperform jsettler, the best heuristic agent available.

Recently, a key challenge of deep reinforcement learning (Deep-RL) is to handle a large amount of samples and learning time in domains with large state and action space. To remedy these problems, we focus on improving the sample efficiency of Deep-RL. We incorporate SIL into the state-of-the-art algorithm IMPALA in learning mini-games of StarCraft II, which has been a challenge to Deep-RL. Our results show that our agents achieve better performance with faster and more stable learning than those trained by the plain IMPALA on two mini-games of StarCraft II.

Making decisions based more on the crucial objects which are closely connected to the reward in a given visual input is advantageous in reinforcement learning. In this work, we incorporate an attention-based structure into the network structure of Importance Weighted Actor-Learner Architecture (IMPALA) to help the model find out the crucial objects and propose Deep Residual Attention Reinforcement Learning (DRARL). Experiments in Atari games and special environments which have more irrelevant objects than usual demonstrate the superiority of DRARL in the multi-objects environment compared to the original IMPALA. Furthermore, the visualization of trained agents’ attention indicates that the additional attention mechanism helps IMPALA concentrate on the crucial objects and therefore improves the performance of IMPALA.

Counterfactual Regret Minimization (CFR) is proposed to be an effective method to find approximate Nash Equilibrium for large zero-sum imperfect information games. Deep neural networks make it possible for CFR to be applied in large games by extending tabular CFR to Deep CFR. While there is little research on applying CFR to board games, in this paper, we propose a variant of Deep CFR for board games and apply it to the game Geister. We show that our proposed method can train agents with an appropriate strategy.

In this paper, we propose Rogue-Gym, a simple and classic style roguelike game built for evaluating generalization in reinforcement learning (RL). Combined with the recent progress of deep neural networks, RL has successfully trained human-level agents without human knowledge in many games such as those for Atari 2600. However, it has been pointed out that agents trained with RL methods often overfit the training environment, and they work poorly in slightly different environments. To investigate this problem, some research environments with procedural content generation have been proposed. Following these studies, we propose the use of roguelikes as a benchmark for evaluating the generalization ability of RL agents. In our Rogue-Gym, agents need to explore dungeons that are structured differently each time they start a new game. Thanks to the very diverse structures of the dungeons, we believe that the generalization benchmark of Rogue-Gym is sufficiently fair. In our experiments, we evaluate a standard reinforcement learning method, PPO, with and without enhancements for generalization. The results show that some enhancements believed to be effective fail to mitigate the overfitting in Rogue-Gym, although others slightly improve the generalization ability., Comment: 8 pages, 14 figures, 4 tables, accepted to IEEE COG 2019

Evaluation functions are crucial for building strong computer players in two-player games, such as chess, Go, and shogi. Although a linear combination of a large number of features has been popular representation of an evaluation function in shogi, deep neural networks (DNNs) are recently considered to be more promising by the success of AlphaZero in multiple domains, chess, Go, and shogi. This paper shows that three loss functions, loss in comparison training, temporal difference (TD) errors and cross entropy loss in win prediction, are effective for the training of evaluation functions in shogi, presented in deep neural networks. For the training of DNNs in AlphaZero, the main loss function only consists of win prediction, though it is augmented with move prediction for regularization. On the other hand, for training in traditional shogi programs, various losses including loss in comparison training, TD errors, and cross entropy loss in win prediction, have contributed to yield accurate evaluation functions which are the linear combination of a large number of features. Therefore, it is promising to combine these loss functions and to apply them to the training of modern DNNs. In our experiments, we show that training with combinations of loss functions improved the accuracy of evaluation functions represented by DNNs. The performance of trained evaluation functions is tested through top-1 accuracy, 1-1 accuracy, and self-play.

For the game of Go, Chess, and Shogi (Japanese Chess), deep neural networks (DNNs) have contributed to building accurate evaluation functions, and many studies have attempted to create the so-called value network, which predicts the reward of a given state. A recent study of the value network for the game of Go has shown that a two-headed neural network with two different objectives can be trained effectively and performs better than a single-headed network. One of the two heads is called a value head and the other head, the policy head, predicts the next move at a given state. This multitask training makes the network more robust and improves the generalization performance. In this paper, we show that a simple discriminator network is an alternative target of multitask learning. Compared to the existing deep neural network, our proposed network can be designed more easily because of its simple output. Our experimental results showed that our discriminative target also makes the learning stable and the evaluation function trained by our method is comparable to the training of existing studies in terms of predicting the next move and playing strength.

Werewolf, also known as Mafia, is a kind of game with imperfect information. Werewolf game agents must cope with two kinds of problems, "decision on who to trust or to kill", and "decision on information exchange". In this paper, we focus on the first problem. We apply techniques in Deep Q Network in building werewolf agents. We also improve representation of states and actions based on existing agents trained by Q learning method. Our proposed agents were compared with existing agents trained by Q learning method and with existing agents submitted to the AIWolf Contest, the most famous werewolf game agents contest in Japan. For every role, we prepared four agents with proposed method and investigated average win ratio of four agents in our experiments. Experimental results showed that when agents learned and played with the same group of players, our proposed agents have better player performances than existing agents trained by Q learning method and a part of agents submitted to the AIWolf Contest. We obtained promising results by using reinforcement learning method to solve "decision on who to trust or to kill" problem without using heuristic methods.

Reinforcement Learning is a kind of machine learning method which learns through agents' interaction with the environment. Deep Q-Network (DQN), which is a model of reinforcement learning based on deep neural networks, succeeded in learning human-level control policies on various kinds of Atari 2600 games with image pixel inputs. Because an input of DQN is the game frames of the last four steps, DQN had difficulty on mastering such games that need to remember events earlier than four steps in the past. To alleviate the problem, Deep Recurrent Q-Network (DRQN) and Deep Attention Recurrent Q-Network (DARQN) were proposed. In DRQN, the first fully-connected layer just after convolutional layers is replaced with an LSTM to incorporate past information. DARQN is a model with visual attention mechanisms on top of DRQN. We propose two new reinforcement learning models: Deep Recurrent Q-Network with Truncated History (T-DRQN) and Deep Attention Recurrent Q-Network with Truncated History (T-DARQN). T-DRQN uses a truncated history so that we can control the length of history to be considered. T-DARQN is a model with visual attention mechanism on top of T-DRQN. Experiments of our models on six games of Atari 2600 shows a level of performance between DQN and D(A) RQN. Furthermore, results show the necessity of using past information with a truncated length, rather than using only the current information or all of the past information.

As shown in AlphaGo, AlphaGo Zero, and AlphaZero, reinforcement learning is effective in learning of evaluation functions (or value networks) in Go, Chess and Shogi. In their training, two procedures are repeated in parallel; self-play with a current evaluation function and improvement of the evaluation function by using game records yielded by recent self-play. Although AlphaGo, AlphaGo Zero, and AlphaZero have achieved super human performance, the method requires enormous computation resources. To alleviate the problem, this paper proposes to incorporate a checkmate solver in self-play. We show that this small enhancement dramatically improves the efficiency of our experiments in Minishogi, via the quality of game records in self-play. It should be noted that our method is still free from human knowledge about a target domain, though the implementation of checkmate solvers is domain dependent.

Building evaluation functions for chess variants is a challenging goal. At this time, only AlphaZero succeeded with millions of self-play records produced by using thousands of tensor processing units (TPUs), which are not available for most researchers. This paper presents the challenge of training evaluation functions on the basis of deep convolutional neural networks using decent data and computing resources, where regularization is crucial as complex models trained with limited data are more prone to overfitting. We present a novel training scheme by introducing a uniformity regularization (UR) network. In the proposed approach, a value network and a discriminator network share common convolutional layers and both networks are trained simultaneously. Loss functions for them are based on the difference between the score of a random move and that of an experts’ move as a comparison training method. The value network is expected to give precise scores for all positions, while the discriminator makes qualitative evaluations for move pairs, and acts as a regularizer that penalizes differences in evaluation results to ensure all samples are uniformly discriminated. Due to the existence of shared layers, such regularization is beneficial for improving the overall accuracy of the value network. Experimental results for chess and shogi demonstrate the proposed method surpassed the standard L 2 regularization method, and successfully helped obtain decently accurate value networks.

Using advanced deep learning methods, artificial intelligence is able to achieve unprecedented high performance in playing complex board games. However, in conventional practice, models for different games require separate training with domain-specific datasets, which is not conducive to enable the full use of the correlation between tasks and may cause unnecessary consumption of computing resources. This paper presents a novel multi-task learning framework for the training of deep-convolutional-neural-network-based evaluation functions for two heterogeneous but related games – chess and shogi. Experimental results show that the application of the proposed framework improved the prediction accuracy for both networks with limited training steps.

For imitation learning in games, AI programs commonly learn thinking and evaluating methods from professional players' game records. However, compared to the total number of all possible game states, top players' records are extremely insufficient. The limited amount of high-quality learning materials may become the bottleneck of training artificial intelligence. We proposed to introduce the idea of Generative Adversarial Networks into game programming, and validated its effectiveness in playing Shogi, a Japanese Chess game. The proposed method is experimentally proved to be capable to alleviate the data insufficiency problem and build more competitive AI programs than conventional supervised training methods.

This paper presents a new method, Minimax Tree Optimization (MMTO), to learn a heuristic evaluation function of a practical alpha-beta search program. The evaluation function may be a linear or non-linear combination of weighted features, and the weights are the parameters to be optimized. To control the search results so that the move decisions agree with the game records of human experts, a well-modeled objective function to be minimized is designed. Moreover, a numerical iterative method is used to nd local minima of the objective function, and more than forty million parameters are adjusted by using a small number of hyper parameters. This method was applied to shogi, a major variant of chess in which the evaluation function must handle a larger state space than in chess. Experimental results show that the large-scale optimization of the evaluation function improves the playing strength of shogi programs, and the new method performs signicantly better than other methods. Implementation of the new method in our shogi program Bonanza made substantial contributions to the program's rst-place nish in the 2013 World Computer Shogi Championship. Additionally, we present preliminary evidence of broader applicability of our method to other two-player games such as chess.

UCT is a standard method of Monte Carlo tree search (MCTS) algorithms, which have been applied to various domains and have achieved remarkable success. This study proposes a family of Leaf-LinUCT, which are improved LinUCT algorithms incorporating LinUCB into MCTS. LinUCB outperforms UCB1 in contextual multi-armed bandit problems, owing to a kind of online learning with ridge regression. However, due to the minimax structure of game trees, ridge regression in LinUCB does not always work well in the context of tree search. In this paper, we remedy the problem and extend our previous work on LinUCT in two ways: (1) by restricting teacher data for regression to the frontier nodes in a current search tree, and (2) by adjusting the feature vector of each internal node to the weighted mean of the feature vector of the descendant nodes. We also present a new synthetic model, incremental-random-feature tree, by extending the standard incremental random tree model. In our model, each node has a feature vector that represents the characteristics of the corresponding position. The elements of a feature vector in a node are randomly changed from those in its parent node by each move, as the heuristic score of a node is randomly changed by each move in the standard incremental random tree model. The experimental results show that our Leaf-LinUCT outperformed UCT and existing LinUCT algorithms, in the incremental-random-feature treeand a synthetic game studied in [1].

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 new Monte-Carlo tree search method that focuses on identifying the best move. UCT which minimizes the cumulative regret, has achieved remarkable success in Go and other games. However, recent studies on simple regret reveal that there are better exploration strategies. To further improve the performance, a leaf to be explored is determined not only by the mean but also by the whole reward distribution. We adopted a hybrid approach to obtain reliable distributions. A negamax-style backup of reward distributions is used in the shallower half of a search tree, and UCT is adopted in the rest of the tree. Experiments on synthetic trees show that this presented method outperformed UCT and similar methods, except for trees having uniform width and depth.

This paper presents a method to give a computer player an intended playing style by the machine learning of an evaluation function. Recent improvements in machine learning techniques have realized the automated tuning of the feature weight vector of an evaluation function. To make a strong player, as many moves as possible of strong players' game records are needed, though the number of available game records decreases when we focus on a specific playing style. To pursue both goals of playing style and playing strength, we present three steps of learning: classifying moves with respect to playing styles, training the weight vector of an evaluation function by using the whole set of game records to maximize its playing strength, and modifying the weight vector carefully so as to improve agreement with the moves of the intended playing style. We applied our method to realize players of defense or attack-oriented style in shogi and tested the players by self-play against the original version. The results confirmed that the presented method successfully adjusted evaluation functions in that the frequency of defensive moves is significantly increased or decreased in accordance with the game records used while keeping the winning ratio at almost 50 %.

Monte Carlo tree search (MCTS) algorithms have been applied to various domains and achieved remarkable success. However, it is relatively unclear what game properties enhance or degrade the performance of MCTS, while the largeness of search space including pruning efficiency mainly governs the performance of classical minimax search, assuming a decent evaluation function is given. Existing research has shown that the distribution of suboptimal moves and the non-uniformity of tree shape are more important than the largeness of state space in discussing the performance of MCTS. Our study showed that another property, bias in suboptimal moves, is also important, and we present an enhancement to better handle such situations. We focus on a game tree in which the game-theoretical value is even, while suboptimal moves for a player tend to contain more inferior moves than those for the opponent. We conducted experiments on a standard incremental tree model with various MCTS algorithms based on UCB1, KL-UCB, or Thompson sampling. The results showed that the bias in suboptimal moves degraded the performance of all algorithms and that our enhancement alleviated the effect caused by this property.

Rating systems are widely used to represent the players' strengths or skills in playing major games such as chess, go, and shogi. We present an alternative method for estimating a player's strength by using the moves played. While popular rating systems including Elo rating are based only on the results of games, i.e., wins, losses, and draws, there are substantial demands for evaluating the quality of the moves themselves instead of the game results. Several studies have been presented that use the evaluation scores obtained via game tree searches using a reference program for just this purpose. However, they incur some problems in terms of the computational costs of running the reference program and also the possible bias of a single or a small number of specific programs. Several weak estimations are integrated in our approach, where the estimations are made by focusing on a reference player playing against a target player, instead of using a few reliable programs as references. We assume a reference player is an ordinary program that can produce an evaluation score and a principal variation for each move. If a target player plays against various kinds of computer players, we can integrate the estimations made by each program in order to yield a stable estimation of the skill set of the target player. Our experiments demonstrated that the proposed method yields a reasonable estimation that represents the average of five estimations, each of which was computed using a hundred randomly selected game records.

東京大学教養学部における図形科学講義について学生による授業評価結果に基づいて分析を行った.主要な分析結果は以下のとおりである.1) 図形科学に対する学生の授業評価は, 他の理科系基礎科目 (物理, 化学, 生物) と同程度であり, 数学に比べてやや高い.2) 図形科学は複数の教師により講義されているが, 学生による授業評価結果には教師間にかなりの差がある.3) 「難度」, 「説明のわかりやすさ」, 「興味の持ちやすさ」と「総合評価」の間には強い相関がある (相関係数は, それぞれ, -0.55, 0.94, 0.93) .また, 「総合評価」と履修率の間には強い相関がある (相関係数: 0.73) .4) 学生による授業評価結果を教師個人に戻すだけでは授業改善に結びつきにくく, 部会会議等で議論することが必要である.

Asynchronous parallel game-tree search methods are effective in improving the playing strength by using many computers connected through relatively slow networks. In game-position parallelization, the master program manages a game-tree and distributes positions in the tree to workers. Then, each worker asynchronously searches the best move and the corresponding evaluation for its assigned position. We present a new method for constructing an appropriate master tree that provides more important moves with more workers on their sub-trees to improve the playing strength. Our contribution introduces two advantages: (1) being parameter free in that users do not need to tune parameters through trial and error, and (2) efficiency suitable even for short-time matches, such as one second per move. We implemented our method in chess with a top-level chess program Stockfish and evaluated the playing strength through self-plays. We confirm that the playing strength improves with up to sixty workers.

This paper describes Akara 2010, the distributed shogi system that has defeated a professional shogi player in a public game for the first time in history. The system employs a novel design to build a high-performance computer shogi player for standard tournament conditions. The design enhances the performance of the entire system by means of distributed computing. To utilize a large number of computers, a majority-voting method using four existing programs is combined with a distributed-search method. Although the performance of the entire system could not be tested, the majority-voting component increased the winning percentage from 62% to 73%, and the distributed-search component increased it from 50% to 70% or more.

In this paper, we present the newly obtained solution for variants of Connect-Four played on an infinite board. We proved this result by introducing never-losing strategies for both players. The strategies consist of a combination of paving patterns, which are follow-up, follow-in-CUP, and a few others. By employing the strategies, both players can block their opponents to achieve the winning condition. This means that optimal play by both players leads to a draw in these games.

The landscape of an objective function for supervised learning of evaluation functions is numerically investigated for a limited number of feature variables. Despite the importance of such learning methods, the properties of the objective function are still not well known because of its complicated dependence on millions of tree-search values. This paper shows that the objective function has multiple local minima and the global minimum point indicates reasonable feature values. Moreover, the function is continuous with a practically computable numerical accuracy. However, the function has non-partially differentiable points on the critical boundaries. It is shown that an existing iterative method is able to minimize the functions from random initial values with great stability, but it has the possibility to end up with a non-reasonable local minimum point if the initial random values are far from the desired values. Furthermore, the obtained minimum points are shown to form a funnel structure.

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.

We propose a new threat-base search algorithm which takes into account threats by both players. In full-board Semeais in Go or Shogi endgames, making naive attack moves often result in losing the game. The reason is that a player must first make a defense move if the opponent has a better attack move than his own. Some attack moves weaken the defense of the player who made the move. Thus, players must be aware of the threats by both players to avoid such naive attack moves. However, existing threat-based search algorithms are only aware of threats by one player, and cannot detect such naive attacks efficiently. We propose a solution to this problem, by applying λ-search mutually recursively so that it searches the best move by taking into account threats by both players. We call this search algorithm dual λ-search. Dual λ-search can handle inversions efficiently compared to previous algorithms by making passes for both players. We implemented dual λ-search with Df-pn as the driver, and made experiments with difficult Shogi-endgame problems. We showed the effectiveness of our algorithm by solving 32 problems out of 97. It includes solving problems that even one of the strongest Shogi program had not yet been able to solve correctly.

This paper proposes a general and automated method that generates accurate evaluation functions, without expert players’ knowledge of a target game. Patterns (which are partial descriptions of a game state) are widely used as primitives of evaluation functions in game programming. They have to be carefully selected in order to generate accurate evaluation functions. Our approach consists of three steps: (1) generation of logic formulae by using the specifications of a target game, (2) translation of the formulae into patterns, and (3) selection of a set of suitable patterns from those generated. The problem, in the automated identification of suitable patterns, is that it is difficult either to generate only useful patterns or to examine all possible patterns. The latter obstacle is due to the prohibitive numbers involved. We solved this dilemma by a combination of two methods, where one method generates patterns of good quality, and the other method entails a lightweight selection based on statistics that could handle a large number of candidates. Experiments in Othello revealed that about 100,000 patterns from more than eight million automatically generated patterns could be successfully selected with our method, and that accurate evaluation functions were constructed. This accuracy is comparable to that of specialized Othello programs and is much better than that of the evaluation functions generated by existing general methods.

A good evaluation function is needed for a good game program, and good features, which are primitive metrics of a state, are needed for a good evaluation function. In order to obtain good features, automatic generation of features by machine learning is promising. However, the generated features are usually written in logic programs, whose evaluation is much slower than that of other native expressions due to the interpretive evaluation of the logic programs. In order to solve this problem, we propose a method which constructs a specialized evaluator using a combination of techniques: partial evaluation, Boolean tables, and incremental calculation. It exhaustively unfolds logical programs until they can be represented as simple Boolean tables. The constructed specialized evaluator is elRcient since it consults only these compiled tables. Experiments with Othello showed that speed can be increased approximately 2,000 times.