Skip to content

使用Easy-X实现界面,alpha-beta剪枝算法作为搜索引擎

Notifications You must be signed in to change notification settings

Carlos-yyt/Renju

Folders and files

NameName
Last commit message
Last commit date

Latest commit

 

History

5 Commits
 
 
 
 

Repository files navigation

简单五子棋AI

背景

  1. 人工智能正处热门。

  2. 不少大学开设了人工智能专业。

  3. 以上两条催生了一些面向全国大学生的棋类AI竞赛。

参考资料

  1. 《PC游戏编程(人机博弈)》,作者:王小春。(主要参考资料)

  2. 象棋巫师。(http://www.xqbase.com/

  3. 技术博客。

成果

  1. 使用Easy-X实现界面,alphabate剪枝算法作为搜索引擎。

  2. 在一秒钟内可以产生一步走法,棋力超过初学者。

  3. 易于拓展其他搜索引擎(其他算法)。

  4. 添加了一些简单的小功能。如:悔棋、走法估值。

实现细节

总体思路是:把五子棋看成一棵博弈树,然后调用静态估值函数对每一个局面进行估值,通过各种算法对于博弈树进行剪枝、对于寻找走法的过程进行优化,从而在可接受的时间内遍历更深的层数,以提高AI的棋力。

其中,静态函数指的是,针对当前棋局,在不考虑将来走法的情况下,单纯通过棋型以及棋子之间的位置,给出一个评分的函数。本质上是对五子棋本身特性的理解,和程序本身没有太大关系。

首先要生成博弈树。生成博弈树的过程是通过CmoveGenerator这个类实现的。五子棋落子规则比较简单,为了简化情况还没有考虑禁手,所以只要是空白的地方都是可能的落子点。值得一提的是,并不是在内存中一次性生成整棵博弈树,因为这种做法的消耗是无法忍受的。事实上,内存中同时存在的局面组数(一组为一个局面的下一步走法,即一个movelist)和所设定的depth(搜索深度)是一样的。这样,时间复杂度和空间复杂度都从O($$225^{n}$$)降到了O($$n$$),让加大搜索深度成可能。

其次,就是对博弈树进行搜索。优化搜索第一步是剪枝处理,这也是不一次性生成整棵博弈树有意义的保证。我写了一个虚类CsearchEngine,目前只实现了CalphaBetaEngine这一种搜索引擎。CalphaBetaEngine使用alphabeta剪枝算法对生成的博弈树进行剪枝,将depth从1提升到了2,也就是可以往后看三步。

最后,做了一些简单的小功能。一个是悔棋,其实就是一个栈。还有一个下法打分,其实就是调用一下CEvaluation::evaluate。

关于界面:是用Easy-X写的,比较原始。

可能的改进方向

  1. 增加搜索引擎的内容。比如:Aspirationi Search,Minimal Window Search/PVS、Transpostion Table、Hash Table、The History Huristic……

  2. 使用开局库。网上有很多爱好者公布了的开局库。可以跑数据优化一下静态估值函数。

  3. 做成网页对练平台。利用原有的程序,学习过网络相关的技术之后,可以将二者结合起来。

  4. 用Qt重写界面。Easy-X只提供了简单的绘图功能(http://www.easyx.cn),随着程序越来越复杂,已经不能胜任了。用Qt重写之后就可以当作一个稳定的版本,在上面深耕了。

2018年8月31日

About

使用Easy-X实现界面,alpha-beta剪枝算法作为搜索引擎

Topics

Resources

Stars

Watchers

Forks

Releases

No releases published

Packages

No packages published