博弈算法理论学习:第1篇 了解博弈搜索以及学习过程
其实网上关于博弈树的内容是相当多的,我们要做的是找到适合自己的材料
这段时间也在跟着老师做论文工作,期间也是需要参考大量的论文文献,因此即使是参加博弈赛,目前这个阶段了也还是希望可以尽可能地多看一些文档,以及掌握一些专业术语,提高专业修养,2333 其实是怕比赛的时候被抽中答辩QAQ
后面也将会结合六子棋(19路连六子)一个规则相对简单的棋类,进行分析,,,
先说说一个很有意思的词语:
零和博弈一个对抗者的损失对另一个对抗者来说是受益,故此这类的博弈游戏称为零和博弈(zero-sum game).
用博弈树来表示两个对抗者在博弈过程可能遇到的状态和移动选择.在对抗树(adversarytree)或者博弈树(gametree)中,两个对抗者交替移动.处于树底层的结点称为叶结点(leaf node),叶结点的祖先称为内部结点(interior node)
化用大佬里的话
博弈算法
很多游戏都是"博弈"的,比如五子棋是双方博弈,斗地主也是。有些是双方竞争,有些会包含合作。在《人工智能-一种现代方法》一书中的第五章 《对抗搜索》中,介绍了博弈论专家们对博弈的一种定义:
有完备信息的,确定性的,轮流行动的,两个游戏者的零和游戏
这也是我们这套算法适用的场景,注意其中任何一个条件不满足,那么将无法直接使用这套算法进行设计。比如这些游戏就不行:
- 斗地主和德州等大部分牌类游戏,因为不是完备信息,看不到对方玩家的牌,而且还有随机性(摸牌不确定)
- 四国军棋,不是完备信息,不是双人游戏
- DOTA,不是完备信息,不是双人游戏,而且不是轮流行动
而五子棋,围棋,黑白棋,象棋等都是满足这些条件的,因此都可以用这套算法来实现。
围棋难题
主要这次比赛,选的是六子棋,然后捏...
对六子棋而言,因为公平性不是问题,所以棋盘是可以任意地大,甚至是无限大亦可。以上述的十九路棋盘为例,所谓状态空间复杂度可达 {\displaystyle 10^{172}} ,与围棋相当。而博弈树(Game tree)复杂度,亦可达: ( 300 × 300 2 ) 30 {\displaystyle ({\frac {300\times 300}{2}})^{30}} 至 10 140 {\displaystyle 10^{140}} ,远大于五子棋。
那么为什么在神经网络出现前,围棋AI的棋力那么弱呢?要回答这个问题,我们先要了解下棋类游戏的复杂度。以下内容摘自*:
名称 | 复杂度 |
---|---|
五子棋 | 70 |
六子棋 | 170 |
国际象棋 | 123 |
中国象棋 | 150 |
围棋 | 360 |
表格中的复杂度是的是以10为底数的对数,也就是10的次方
可以看到,哪怕是简单的五子棋,其状态空间的复杂度也是一个天文数字,而围棋的复杂度远远高于前面的几种棋类。我们把这个复杂度叫做空间复杂度,由于围棋的复杂度太高,因此很难在较短的步骤内评估出合适的走法,而且也很难搜索到较深的深度。 更直观点说,围棋的难点在于两部分:
- 围棋本身的局面评估很复杂,不像象棋一样可以简单的给每个子打一个分。围棋更注重“局势”,非常难用常规手段打分。由于连评分都不准,因此搜索的基础都不可靠
- 围棋很难达到较深的深度。围棋每一步的可能性非常多,平均一步需要考虑100+种可能,因此很难达到较深的搜索深度。
- 其中下面的Policy network是指策略网络,右边为分值网络
- 价值网络可以比较准确的进行局势的评分
- 策略网络可以让产生更少的分支,预测更合理的着法
如果现在不是很好理解这段话没关系,等你读完接下来的文章,再回头看这一段,就可以理解了。
理论学习方面,将从以下几个方面去学习:
基本搜索算法:
搜索算法的改进
估值核心的优化
- 博弈算法基础知识
- 博弈树、极大极小值(Minimax Algorithm)、深度优先搜索(Depth First Search)、负极大值算法(Negamax Algorithm)
- Alpha-Beta 剪枝
- 迭代加深
- Zobrist缓存
- 启发式评估函数
- 置换表、哈希表
- 算杀、MTD(f)算法
- 开局库
- 单元测试
- 速度优化
看到一篇有趣的博客,通过阅读国外文献学习...大佬 膜拜...
使用的[2]术语,一个问题空间(problem space)看以看做是一个状态(state)和实现状态之间映射的操作(state)的集合.在博弈问题中,博弈树上的一个内部结点或叶结点就是一个状态,一般使用位置(position)来表述.移动(move)就是将一个位置转化为其子位置(successor position)的操作.如果一个位置是博弈树的叶结点,可以用评价者(evaluator)来对其优劣进行评分(evaluate).有了评价者,博弈树中的每个叶结点都有一对应值(value).
博弈树搜索或者对抗搜索的目的就是找出博弈树的值(game tree value).博弈树的值(gametree value,下面简称博弈值)指的是博弈树中一个子结点的值,该值对于博弈双方都是最优的.博弈树的子树(subtree)在该子树搜索完成之后也会返回一个博弈值,虽然该值对于该子树来说最优的,但是对整个博弈树来说并不是全局最优的.
找出一棵博弈树的博弈值,可以使用基本的Min-Max方法.为了减少Min-Max方法需要搜索的结点个数,可以使用Alpha-Beta算法进行剪枝.根据博弈树的性质,在Alpha-Beta算法的基础上,各种改进方法被先后提出来.为了进一步提高搜索速度,Alpha-Beta算法又可以基于不同的思想进行并行化.在博弈树搜索算法方面,前人做了许多丰富而充满意义的研究工作.
[1] Valavan Manohararajah(2001). Parallel Alpha-Beta Search on SharedMemory Multiprocessors. Master’s thesis, Graduate Department of Electrical andComputer Engineering, University of Toronto, Canada.
[2] A. Newell and H.A. Simon (1972). Human Problem Solving.Prentice-Hall, 1972
参考资料:
https://blog.csdn.net/fsdev/article/details/7294857
这个博主的学习方法,2333,和老师要求的一样,感觉可以先在这里膜拜一下大佬 2333