Game-tree search plays an important role in the field of Artificial Intelligence （AI）. In this paper, we characterize one parallel game-tree search workload in chess： the latest version of Crafty, a state of art pr...Game-tree search plays an important role in the field of Artificial Intelligence （AI）. In this paper, we characterize one parallel game-tree search workload in chess： the latest version of Crafty, a state of art program, on two Intel Xeon shared-memory multiprocessor systems. Our analysis shows that Crafty is latency-sensitive and the hash-table and dynamic tree splitting used in Crafty cause large scalability penalties. They consume 35%-50% of the running time on the 4-way system. Furthermore, Crafty is not bandwidth-limited.展开更多
Teaching computer programs to play games through machine learning has been an important way to achieve better artificial intelligence (AI) in a variety of real-world applications. Monte Carlo Tree Search (MCTS) is one...Teaching computer programs to play games through machine learning has been an important way to achieve better artificial intelligence (AI) in a variety of real-world applications. Monte Carlo Tree Search (MCTS) is one of the key AI techniques developed recently that enabled AlphaGo to defeat a legendary professional Go player. What makes MCTS particularly attractive is that it only understands the basic rules of the game and does not rely on expert-level knowledge. Researchers thus expect that MCTS can be applied to other complex AI problems where domain-specific expert-level knowledge is not yet available. So far there are very few analytic studies in the literature. In this paper, our goal is to develop analytic studies of MCTS to build a more fundamental understanding of the algorithms and their applicability in complex AI problems. We start with a simple version of MCTS, called random playout search (RPS), to play Tic-Tac-Toe, and find that RPS may fail to discover the correct moves even in a very simple game position of Tic-Tac-Toe. Both the probability analysis and simulation have confirmed our discovery. We continue our studies with the full version of MCTS to play Gomoku and find that while MCTS has shown great success in playing more sophisticated games like Go, it is not effective to address the problem of sudden death/win. The main reason that MCTS often fails to detect sudden death/win lies in the random playout search nature of MCTS, which leads to prediction distortion. Therefore, although MCTS in theory converges to the optimal minimax search, with real world computational resource constraints, MCTS has to rely on RPS as an important step in its search process, therefore suffering from the same fundamental prediction distortion problem as RPS does. By examining the detailed statistics of the scores in MCTS, we investigate a variety of scenarios where MCTS fails to detect sudden death/win. Finally, we propose an improved MCTS algorithm by incorporating minimax search to overcome prediction distortion. Our simulation has confirmed the effectiveness of the proposed algorithm. We provide an estimate of the additional computational costs of this new algorithm to detect sudden death/win and discuss heuristic strategies to further reduce the search complexity.展开更多
针对蒙特卡洛树搜索算法(Monte Carlo tree search,MCTS)收敛速度过慢,且在博弈过程中关键节点会出现信息丢失等问题,以中国象棋为载体,构建适用于中国象棋博弈系统的策略价值网络,提出了一种基于统计数据的并行蒙特卡洛树搜索算法(para...针对蒙特卡洛树搜索算法(Monte Carlo tree search,MCTS)收敛速度过慢,且在博弈过程中关键节点会出现信息丢失等问题,以中国象棋为载体,构建适用于中国象棋博弈系统的策略价值网络,提出了一种基于统计数据的并行蒙特卡洛树搜索算法(parallel Monte Carlo tree search based on statistics,SPMCTS)。将并行化的重点设置在MCTS四个步骤中最耗时的扩展和模拟步骤,有效避免了算法执行过程中的等待时差。并且引入一组新统计数据,这些数据用于在MCTS的选择步骤中修改节点的选择策略,保证在进行节点选择时获取和利用更多的可用信息,缓解信息丢失对精度造成的影响。实验结果表明,与现有并行蒙特卡洛树算法相比,SPMCTS在搜索速度上加快了约34%,且在对弈实验中,博弈胜率也能保持在80%左右。验证了SPMCTS的有效性。展开更多
文摘Game-tree search plays an important role in the field of Artificial Intelligence （AI）. In this paper, we characterize one parallel game-tree search workload in chess： the latest version of Crafty, a state of art program, on two Intel Xeon shared-memory multiprocessor systems. Our analysis shows that Crafty is latency-sensitive and the hash-table and dynamic tree splitting used in Crafty cause large scalability penalties. They consume 35%-50% of the running time on the 4-way system. Furthermore, Crafty is not bandwidth-limited.
文摘Teaching computer programs to play games through machine learning has been an important way to achieve better artificial intelligence (AI) in a variety of real-world applications. Monte Carlo Tree Search (MCTS) is one of the key AI techniques developed recently that enabled AlphaGo to defeat a legendary professional Go player. What makes MCTS particularly attractive is that it only understands the basic rules of the game and does not rely on expert-level knowledge. Researchers thus expect that MCTS can be applied to other complex AI problems where domain-specific expert-level knowledge is not yet available. So far there are very few analytic studies in the literature. In this paper, our goal is to develop analytic studies of MCTS to build a more fundamental understanding of the algorithms and their applicability in complex AI problems. We start with a simple version of MCTS, called random playout search (RPS), to play Tic-Tac-Toe, and find that RPS may fail to discover the correct moves even in a very simple game position of Tic-Tac-Toe. Both the probability analysis and simulation have confirmed our discovery. We continue our studies with the full version of MCTS to play Gomoku and find that while MCTS has shown great success in playing more sophisticated games like Go, it is not effective to address the problem of sudden death/win. The main reason that MCTS often fails to detect sudden death/win lies in the random playout search nature of MCTS, which leads to prediction distortion. Therefore, although MCTS in theory converges to the optimal minimax search, with real world computational resource constraints, MCTS has to rely on RPS as an important step in its search process, therefore suffering from the same fundamental prediction distortion problem as RPS does. By examining the detailed statistics of the scores in MCTS, we investigate a variety of scenarios where MCTS fails to detect sudden death/win. Finally, we propose an improved MCTS algorithm by incorporating minimax search to overcome prediction distortion. Our simulation has confirmed the effectiveness of the proposed algorithm. We provide an estimate of the additional computational costs of this new algorithm to detect sudden death/win and discuss heuristic strategies to further reduce the search complexity.
文摘针对蒙特卡洛树搜索算法(Monte Carlo tree search,MCTS)收敛速度过慢,且在博弈过程中关键节点会出现信息丢失等问题,以中国象棋为载体,构建适用于中国象棋博弈系统的策略价值网络,提出了一种基于统计数据的并行蒙特卡洛树搜索算法(parallel Monte Carlo tree search based on statistics,SPMCTS)。将并行化的重点设置在MCTS四个步骤中最耗时的扩展和模拟步骤,有效避免了算法执行过程中的等待时差。并且引入一组新统计数据,这些数据用于在MCTS的选择步骤中修改节点的选择策略,保证在进行节点选择时获取和利用更多的可用信息,缓解信息丢失对精度造成的影响。实验结果表明,与现有并行蒙特卡洛树算法相比,SPMCTS在搜索速度上加快了约34%,且在对弈实验中,博弈胜率也能保持在80%左右。验证了SPMCTS的有效性。
