周洋，邓莉，谢煜

（武汉科技大学计算机学院，武汉 430065）

一种五子棋博弈算法的分析

周洋，邓莉，谢煜

（武汉科技大学计算机学院，武汉 430065）

博弈是用来解决一组决策者之间冲突或合作问题的数学方法。在实现玩家和电脑之间的五子棋对弈时，常常使用博弈方法来确定电脑的走法步骤。经过对五子棋的一种博弈算法设计和实现的分析，总结出五子棋问题求解的算法思路，并分析出算法的性能瓶颈及相应的解决方案。

极大极小搜索算法；Alpha-beta剪枝；博弈；五子棋

0 引言

五子棋是一种深受大家喜爱的棋类游戏，其规则简单，变化多样，为其增加了更多的趣味性。五子棋起源于中国古代棋类，而对其发展起重大作用的是日本。18世纪五子棋在日本流行起来，后来发现五子棋有执黑先行必胜定律，为了让其能更公平，在比赛中添加了许多禁手规则，而在业余人士的游戏中则一般不设置这些规则。五子棋发展至今禁手规则已逐渐削弱了执黑先行的优势。在1997年计算机就下赢了当时的国际象棋冠军。而对五子棋一直以来都没有发展出一种可以绝对取胜算法。原因就在于五子棋（15×15）的搜索空间比国际象棋（8×8）更大。想在有限的时间找出一种必胜的策略显然是件非常困难的事。博弈是在一定条件下，遵守一定的规则，一个或几个拥有绝对理性思维的人或团队，从各自允许选择的行为或策略进行选择并加以实施，并从中各自取得相应结果或收益的过程。……