前瞻深度对演化象棋的影响
Effect of Look-Ahead Depth in Evolutionary Checkers
-
摘要: 直观上, 被允许对博弈树进行更深度的搜索的一方会优胜于只允许进行固定深度搜索的一方。当然, 对树进行更深度的搜索会增加计算代价, 这也是开发树搜索算法中必须被考虑进去的一种权衡。目前, 已经有一些关于评估函数或者搜索深度是否是影响演化出的下跳棋程序的表现的主要因子的讨论。之前的一些工作也对这个问题进行了研究(在国际象棋和黑白棋上), 并得到了不同的结论。从这些研究可以看出, 不同的博弈对着两个因子有不同的侧重。本文针对演化跳棋提供了一些证据, 并显示向前看(像国际象棋一样, 可能并不令人惊讶)是重要的。这是第一次对演化象棋进行的深入研究, 也是在已有的提供给国际象棋和黑白棋的证据支持基础上对另一类博弈提供证据支持。我们通过演化大量的不同深度层的下象棋程序并让它们仍然在不同的深度层进行一对一博弈得出结论。这和已经对向前看对演化出的下象棋程序的重要性提供很强证据支持的两个移动选票(允许更多和演化出的下象棋程序的博弈发生)结合起来。Abstract: It is intuitive that allowing a deeper search into a game tree will result in a superior player to one that is restricted in the depth of the search that it is allowed to make. Of course, searching deeper into the tree comes at increased computational cost and this is one of the trade-offs that has to be considered in developing a tree-based search algorithm. There has been some discussion as to whether the evaluation function, or the depth of the search, is the main contributory factor in the performance of an evolved checkers player. Some previous research has investigated this question (on Chess and Othello), with differing conclusions. This suggests that different games have different emphases, with respect to these two factors. This paper provides the evidence for evolutionary checkers, and shows that the look-ahead depth (like Chess, perhaps unsurprisingly) is important. This is the first time that such an intensive study has been carried out for evolutionary checkers and given the evidence provided for Chess and Othello this is an important study that provides the evidence for another game. We arrived at our conclusion by evolving various checkers players at different ply depths and by playing them against one another, again at different ply depths. This was combined with the two-move ballot (enabling more games against the evolved players to take place) which provides strong evidence that depth of the look-ahead is important for evolved checkers players.