Life in the game of Go

The Oriental game of Go contains a unique method by which pieces, called stones, are captured and made safe from capture. A group of stones safe from capture is called safe, unconditionally alive, or similar terms. Life or its lack can be determined by lookahead through the game tree, at some expense. We present a graph-theoretic static analysis of the board arrangement which determines unconditional life or its lack, together with proofs of its equivalency to look ahead. An algorithm for the static evaluation is given and we argue that it is the preferable method for computer Go play. These results constitute the first realistic theorems in the theory of Go.     

采用时间差分算法的九路围棋机器博弈系统

围棋机器博弈是机器博弈中重要的分支之一,其庞大的博弈空间给机器博弈研究者带来了巨大挑战.目前围棋机器博弈多采用静态估值搜索与蒙特卡洛树搜索,故将时间差分算法引入至九路围棋机器博弈系统中,提出基于时间差分算法的围棋机器博弈系统模型,该博弈系统具有一定的自学习能力,能在不断的对弈中逐步提高博弈能力.通过与采用α-β搜索算法的博弈系统进行实际对弈,证明了该方法的可行性.     

Learning to predict life and death from Go game records

This article presents a new learning system for predicting life and death in the game of Go. It is called Gone. The system uses a multi-layer perceptron classifier which is trained on learning examples extracted from game records. Blocks of stones are represented by a large amount of features which enable a rather precise prediction of life and death. On average, Gone correctly predicts life and death for 88% of all the blocks that are relevant for scoring. Towards the end of a game the performance increases up to 99%. A straightforward extension for full-board evaluation is discussed. Experiments indicate that the predictor is an important component for building a strong full-board evaluation function.     

Soft-computing-based emotional expression mechanism for game of computer Go

The game of Go is considered one of the most complicated games in the world. One Go game is divided into three stages: the opening, the middle, and the ending stages. Millions of people regularly play Go in countries around the world. The game is played by two players. One is White and another is Black. The players alternate placing one of their stones on an empty intersection of a square grid-patterned game board. The player with more territory wins the game. This paper proposes a soft-computing-based emotional expression mechanism and applies it to the game of computer Go to make Go beginners enjoy watching Go game and keep their tension on the game. First, the knowledge base and rule base of the proposed mechanism are defined by following the standards of the fuzzy markup language. The soft-computing mechanism for Go regional alarm level is responsible for showing the inferred regional alarm level to Go beginners. Based on the inferred board situation, the fuzzy inference mechanisms for emotional pleasure and arousal are responsible for inferring the pleasure degree and arousal degree, respectively. An emotional expression mapping mechanism maps the inferred degree of pleasure and degree of arousal into the emotional expression of the eye robot. The protocol transmission mechanism finally sends the pre-defined protocol to the eye robot via universal serial bus interface to make the eye robot express its emotional motion. From the experimental results, it shows that the eye robot can support Go beginners to have fun and retain their tension while watching or playing a game of Go.     

基于WinCE应用程序的围棋游戏开发

机器博弈,也称计算机博弈,即让计算机下棋。围棋是一种策略性二人棋类游戏,使用格状棋盘及黑白二色棋子进行对弈。文中计算机围棋游戏引擎的开发采用马尔科夫决策模型,使用人工智能的知识,含有大量计算,整个计算紧密依赖于系统资源,计算量越大,引擎的选点越精确,棋力越高。针对嵌入式系统软硬件的特定性,其资源和计算能力的局限性,本文主要完成了两个工作：一是将实验室适用于PC的游戏引擎移植到WinCE,开发适合嵌入式系统的围棋游戏引擎,实现大规模计算的移植,使游戏引擎在嵌入式有限的资源上,通过精简的计算量,达到不错的效果;二是实现WinCE上围棋游戏前台界面的开发。     

一种围棋定式的机器学习方法

提出了一种围棋定式的机器学习方法。利用此方法可实现从棋谱库中自动提取定式并生成定式库。此外，对于棋谱数量较大的情况，采用分阶段学习方法，提高了学习效率。应用此方法，时34000局棋谱进行处理，得到定式点680638个。最后，还给出了1种基于组合博弈理论在计算机围棋博弈系统中使用定式的方法。     

Temporal-difference search in computer Go

Temporal-difference learning is one of the most successful and broadly applied solutions to the reinforcement learning problem; it has been used to achieve master-level play in chess, checkers and backgammon. The key idea is to update a value function from episodes of real experience, by bootstrapping from future value estimates, and using value function approximation to generalise between related states. Monte-Carlo tree search is a recent algorithm for high-performance search, which has been used to achieve master-level play in Go. The key idea is to use the mean outcome of simulated episodes of experience to evaluate each state in a search tree. We introduce a new approach to high-performance search in Markov decision processes and two-player games. Our method, temporal-difference search, combines temporal-difference learning with simulation-based search. Like Monte-Carlo tree search, the value function is updated from simulated experience; but like temporal-difference learning, it uses value function approximation and bootstrapping to efficiently generalise between related states. We apply temporal-difference search to the game of 9×9 Go, using a million binary features matching simple patterns of stones. Without any explicit search tree, our approach outperformed an unenhanced Monte-Carlo tree search with the same number of simulations. When combined with a simple alpha-beta search, our program also outperformed all traditional (pre-Monte-Carlo) search and machine learning programs on the 9×9 Computer Go Server.     

强化学习及其在电脑围棋中的应用

强化学习是一类特殊的机器学习, 通过与所在环境的自主交互来学习决策策略, 使得策略收到的长期累积奖赏最大. 最近, 在围棋和电子游戏等领域, 强化学习被成功用于取得人类水平的操作能力, 受到了广泛关注. 本文将对强化学习进行简要介绍, 重点介绍基于函数近似的强化学习方法, 以及在围棋等领域中的应用.     

Real-Time Path Planning Algorithm for Autonomous Border Patrol: Design,Simulation, and Experimentation

This paper presents an online path planning algorithm for unmanned vehicles in charge of autonomous border patrol. In this Pursuit-Evasion game, the unmanned vehicle, acting as the pursuer, is required to capture multiple trespassers on its own before any of them reach a target safe house where they are safe from capture. The problem formulation is based on Isaacs’ Target Guarding problem, but extended to the case of multiple evaders. The proposed path planning method is based on Rapidly-exploring random trees (RRT) and is capable of producing trajectories within seconds to capture 2 or 3 evaders. Simulations are carried out to demonstrate that the resulting trajectories approach the optimal solution produced by a nonlinear programming-based numerical optimal control solver. Experiments are also conducted on unmanned ground vehicles to show the feasibility of implementing the proposed online path planning algorithm on physical applications.     

In the News

This paper discusses how some artificial intelligence (AI) researchers and search experts are using AI methods to try to improve the accuracy of video search results. One example is a University of Oxford project in which researchers use statistical machine learning, specifically computer vision methods for face detection and facial feature localization, to provide automatic annotation of video with information about all the content of the video. Another example is the video search engine from Blinkx that objectively analyzes video content using speech recognition and matches the spoken words to context gleaned from a massive database. Finally, researchers at Dartmouth University are working on a technology that shows whether images or video clips have been doctored. This technique uses support vector machines to differentiate computer-generated images from photographic images. The paper goes on to discuss computer Go programs. Go is an ancient Asian board game which has become a challenge for AI researchers around the world. Go is resistant to Deep Blue's brute-force search of the game tree; the number of possible moves is too large. This inspires researchers to develop hybrid methods combining different methods and algorithms     

基于模糊聚类的神经网络求解围棋死活博弈

围棋死活求解非常消耗计算资源,博弈树的节点数随分支因子和深度的增加而呈指数级增长,使得传统的完全遍历博弈树的搜索不足以胜任.文中提出了一种基于模糊聚类的神经网络方法,利用模式识别和模糊属性检测,为涉及到外部劫争、循环规避、哈希置换、证明树等多方面问题的围棋博弈死活求解,构建了基于神经网络的棋型聚类分析器,快速又有效地极大减小了博弈树的分支因子,节约了死活求解所耗费的计算时间和内存空间.实验证明取得了比较理想的结果,研究表明把自学习能力赋予程序是提高计算机围棋博弈性能的有效途径.     

“Reliving my Childhood Dream of being a Pokémon Trainer”: An Exploratory Study of College Student Uses and Gratifications Related to Pokémon Go

Pokémon Go is an interactive mobile game that was launched in July 2016. The current exploratory study recruited college students (n = 278) who currently played, no longer played, or had never played Pokémon Go to understand their lived experiences with this game and determine differences in perceived behavioral outcomes of playing between current and past players. The research team implemented a Uses and Gratifications (U&G) theoretical framework and qualitative research design. Three themes were identified through qualitative content analysis and included: (a) limitations to playing Pokémon Go, (b) motivations for playing Pokémon Go, and (c) social consequences of playing Pokémon Go. Results are discussed in connection with U&G.     

A cooperative pursuit-evasion game in wireless sensor and actor networks

This paper studies the problem of the pursuit-evasion game under the wireless sensor and actor networks (WSANs). In order to plan paths for pursuers to capture an evader in the pursuit-evasion game, a novel multi-step cooperative strategy is presented. Under this strategy, the pursuit-evasion game is studied in two stages. In the first stage we assume that the evader is always static in the workplace, and in the second stage the evader will move once it senses the existence of pursuers. A Daisy-Chain Formation algorithm and a sliding mode-based method are presented to control the pursuit. Based on Lyapunov stability theory, the proposed algorithm is proved to be convergent. At last, simulation results are provided to demonstrate the effectiveness of the proposed method.     

五子棋机器博弈系统评估函数的设计

针对五子棋机器博弈需借助棋型评估棋局产生的速度瓶颈,提出了棋型识别粒度与搜索深度相关联的多层架构评估函数设计方法。实验证实粗颗粒度估值在深层搜索时整体效率更高;多层次判读棋型能明显加快评估速度;走法生成函数引入快速评估,提前进行博弈树自然剪枝收效显著;非关键棋型依据棋局浮动分值平衡搜索深度,对五子棋亦见成效;以及估值函数针对性地延伸评估来减少地平线效应的开销更少;从而表明估值函数动态评估更加合理。     

Evasion strategies of a three-player lifeline game

This study examines a multi-player pursuit-evasion game, more specifically, a three-player lifeline game in a planar environment, where a single evader is tasked with reaching a lifeline prior to capture. A decomposition method based on an explicit policy is proposed to address the game qualitatively from two main aspects: (1) the evader’s position distribution to guarantee winning the game (i.e., the escape zone), which is based on the premise of knowing the pursuers’ positions initially, and (2) evasion strategies in the escape zone. First, this study decomposes the three-player lifeline game into two two-player sub-games and obtains an analytic expression of the escape zone by constructing a barrier, which is an integration of the solutions of two sub-games. This study then explicitly partitions the escape zone into several regions and derives an evasion strategy for each region. In particular, this study provides a resultant force method for the evader to balance the active goal of reaching the lifeline and the passive goal of avoiding capture. Finally, some examples from a lifeline game involving more than one pursuer are used to verify the effectiveness and scalability of the evasion strategies.     

Approximation Metrics for Discrete and Continuous Systems

Established system relationships for discrete systems, such as language inclusion, simulation, and bisimulation, require system observations to be identical. When interacting with the physical world, modeled by continuous or hybrid systems, exact relationships are restrictive and not robust. In this paper, we develop the first framework of system approximation that applies to both discrete and continuous systems by developing notions of approximate language inclusion, approximate simulation, and approximate bisimulation relations. We define a hierarchy of approximation pseudo-metrics between two systems that quantify the quality of the approximation, and capture the established exact relationships as zero sections. Our approximation framework is compositional for a synchronous composition operator. Algorithms are developed for computing the proposed pseudo-metrics, both exactly and approximately. The exact algorithms require the generalization of the fixed point algorithms for computing simulation and bisimulation relations, or dually, the solution of a static game whose cost is the so-called branching distance between the systems. Approximations for the pseudo-metrics can be obtained by considering Lyapunov-like functions called simulation and bisimulation functions. We illustrate our approximation framework in reducing the complexity of safety verification problems for both deterministic and nondeterministic continuous systems     

基于模糊博弈的英式拍卖动态模型

为了给竞价人或其代理的竞价提供决策支持,提出了模糊博弈的英式拍卖动态模型.以模糊参数出价意愿取代估价作为分析的基础,采用Bellman和Zadeh的模糊决策理论替代博弈论中的Nash平衡理论,分析英式拍卖中的竞价行为,建立英式拍卖静态博弈均衡模型,进而提出动态博弈模型和分析动态拍卖策略.通过仿真实验证明算法的有效性.     

A solution to the GHI problem for depth-first proof-number search

The Graph-History interaction (GHI) problem is a notorious problem that causes game-playing programs to occasionally return incorrect solutions. This paper presents a practical method to cure the GHI problem for the case of the df-pn algorithm. Results in the game of Go with the situational super-ko rule show that the overhead incurred by our method is very small, while correctness is always guaranteed.     

双人博弈问题中的蒙特卡洛树搜索算法的改进

蒙特卡洛树搜索(MCTS)是一种针对决策类博弈游戏,运用蒙特卡洛模拟方法进行评估博弈策略的启发式搜索算法。但是,在面对计算机围棋这种复杂的决策过程时,简单的蒙特卡洛树搜索过程往往由于计算量大,收敛速度非常慢。 由于双人博弈游戏中的蒙特卡洛树搜索不能收敛于双人博弈的最佳决策策略,因此提出蒙特卡洛树搜索结合极大极小值算法的改进算法,使得搜索结果不会因为蒙特卡洛方法的随机性而失真。为了进一步提高复杂双人博弈游戏中搜索算法的计算效率,还结合了几种常见的剪枝策略。实验结果说明,所提算法显著改进了蒙特卡洛树搜索的准确性和效率。