A Search Optimization Method for Rule Learning in Board Games

摘要

A general game playing (GGP) system aims to play previously unknown board games with changeable rules without human intervention. Taking changeable game rules into consideration, a game description language presents formal descriptions of a game. Based on this description, legal moves can be automatically generated so that each player in GGP system only needs to solve the problems of searching and learning for playing well. Traditional search methods demand the player to compute all legal moves, which can be very time consuming. In GGP, the coordinate of cells in the game board is very important in board game rules. Thus we address the relationship among cell coordinates. Borrowing an idea from rule learning to prune the board game search tree, we propose a new search optimization method to reduce running time when searching a large search space. We further prove that this method can effectively improve the searching efficiency through a comparative experiment with Gomoku game in GGP system.