空间有限条件下博弈搜索算法的优化

Approach of optimizing adversarial search in a limited space

alpha-beta剪枝算法是一种传统的搜索算法,它大大减少了相同搜索深度下的计算量,但其仍然不能满足有限时间内进行搜索的需求。为此,有很多针对该算法的优化方法,但这些优化方法大都是以消耗更多空间为代价的。本文从博弈程序的全局考虑,提出几种优化策略,在有限的空间条件下,以较少的计算量,获得较高智能性。经过实验测试,在PC机中对相同的搜索层次、使用相同空间的算法所消耗的时间进行对比,发现优化方法的算法可以大幅度降低消耗的时间,最多可以节省10%的时间。

alpha-beta algorithm is a kind of typical method for optimizing adversarial search, which reduces the computation amount obviously in the same search depth, but it still does not meet the requirement of searching in a limited time. So, there are many enhancements on its optimization, but most of those enhancements consume more space. This paper presents some strategies of enhancement from a microscopically angle, and those methods could use less computation amount and get more intelligence at the same time. The experiment shows that the optimized algorithm could reduce almost 10 percent time compared to the non-optimized algorithm at the same condition with equal depth and space.