Three types of forward pruning techniques to apply the alpha beta algorithm to turn-based strategy games
Three types of forward pruning techniques to apply the alpha beta algorithm to turn-based strategy games
复制标题
将alpha beta算法应用于回合制策略游戏的三种前向剪枝技术
DOI：
10.1109/cig.2016.7860427
复制
发表时间：
2016
期刊：
影响因子：
--
通讯作者：
Kokolo Ikeda
中科院分区：
文献类型：
--
作者：
Naoyuki Sato;Kokolo Ikeda
回合制策略游戏是开发人工玩家的有趣测试平台，因为它们的规则向开发者呈现了一些挑战。目前，蒙特卡罗树搜索变体经常用于解决这些挑战。然而，我们认为引入带有修剪技术的极大极小搜索变体是值得的，因为基于回合的策略在某些方面类似于国际象棋和Shogi游戏，其中极大极小变体是已知有效的。因此，我们引入了三种前向修剪技术，使我们能够将alpha - beta搜索（作为极大极小搜索变体）应用于回合制策略游戏。这种类型的搜索包括固定单位行动顺序，选择性地生成单位行动，以及限制搜索中移动单位的数量。我们通过在我们研究所的回合制策略学术包（TUBSTAP）开放平台中实现基于alpha beta的人工玩家来应用我们提出的修剪方法。这位选手在2016年的TUBSTAP AI比赛中与一、二线选手竞争。我们建议的玩家在5个不同的地图中战胜其他玩家，平均胜率超过70%。
Turn-based strategy games are interesting testbeds for developing artificial players because their rules present developers with several challenges. Currently, Monte-Carlo tree search variants are often utilized to address these challenges. However, we consider it worthwhile introducing minimax search variants with pruning techniques because a turn-based strategy is in some points similar to the games of chess and Shogi, in which minimax variants are known to be effective. Thus, we introduced three forward-pruning techniques to enable us to apply alpha beta search (as a minimax search variant) to turn-based strategy games. This type of search involves fixing unit action orders, generating unit actions selectively, and limiting the number of moving units in a search. We applied our proposed pruning methods by implementing an alpha beta-based artificial player in the Turn-based strategy Academic Package (TUBSTAP) open platform of our institute. This player competed against first- and second-rank players in the TUBSTAP AI competition in 2016. Our proposed player won against the other players in five different maps with an average winning ratio exceeding 70%.
使用极小极大搜索对评估函数进行大规模优化
影响因子：
5
作者：
K. Hoki;S. Omori;and T. Ito;K. Hoki and T. Kaneko
通讯作者：
K. Hoki and T. Kaneko