我们已经知道UCB算法能够更快地找到靠谱的着手点,续上一篇的问,能不能再优化?
首先要知道的是,为什么UCB算法比盲目的蒙特卡罗局面评估收敛得更快?我的理解,是因为在算法执行的过程中,UCB算法能不断根据之前的结果调整策略,选择优先评估哪一个可下点。其实这是一种在线的机器学习策略。对于上一篇提到过的多臂匪徒问题,可以用UCB算法很好地解决。对于围棋博弈问题而言,UCB算法相比于朴素的蒙特卡罗局面评估方法,收敛速度有很大的提高,但确实存在可进一步优化的地方。
上一篇中,把围棋棋盘上的可下点比作了角子机,但他们之间有什么不同呢?
答案是——多臂匪徒问题只有一层角子机,围棋博弈问题则是多层角子机构成的博弈树!
终于提到博弈树了,需知在绝大多数棋类博弈问题中,博弈树是必不可少的工具。这里简单介绍一下博弈树搜索中用到的最基本搜索方法——最大最小搜索(如果对博弈树毫无概念,请自行google)。在一个二人零和博弈游戏中,参与博弈的双方所作出的每一个决策都是为了己方利益的最大化(废话~)。假设我们把黑方获胜时的棋局形势设为一个正数值v,白方获胜则是-v(其他情况下局势介于v和-v之间),则黑棋的每一手棋都是为了使局势尽可能的大,白棋反之。表现在博弈树中,则黑棋层总是选择局势值最大的结点作为结果返回上一层,白棋层反之——这就是最大最小搜索。
有了以上的科普,这里就给出上一篇的答案——更优化的算法,UCT算法(UCB for tree)。以下是算法描述:
给定一棵博弈树。
1) 从博弈树的根点开始向下搜索,执行2)。
2)遇到节点a后,若a存在从未评估过的子节点,执行3),否则执行4)。
3) 通过MonteCarlo方法评估该子节点,得到收益值后更新该子节点至根节点路径上所有节点的平均收益值,执行1)。
4) 计算每个子节点的UCB值,将UCB值最高的子节点作为节点a,执行2)。
5) 算法可随时终止,通常达到给定时间或尝试次数后终止。
根节点下平均收益值最高的子节点作为算法的输出。
对于这个算法,有几点需要解释:
1)博弈树的根节点指的是当前的局面。
2)评估过的节点及其平均收益值将在程序运行过程中保存及更新。
3)收益值可自行设定合适的值。我知道MOGO的做法是将其设为1(胜)或0(负),我的程序Foolish Go的做法是,所得地域 / 总地域。
4)这个算法是现代围棋博弈程序的基石。
个人对这个算法的理解是,本质上是一种迭代加深的DFS。
为了更好地理解UCT算法的收敛性,不妨思考,这个算法会怎样“意识”到下一手棋应该征子?
理论的东西差不多介绍完了,下一篇将进入实战。
分享到:
相关推荐
给需要参考UCT搜索算法的人提供参考,提高自己设计的棋类的棋力
- 此项目的核心算法是强化学习——基于蒙特卡洛树搜索地UCT算法,参考了AlphoGo的算法原理实现了基本的MCTS算法和UCT算法,同时也创造性地对算法框架、回报函数、超参数等进行了改进,从而更适用于围棋死活题求解。...
说是围棋程序,但是直接编译是按五子棋下的。
井字棋基于UCT算法实现代码,亲测无敌
UCT算法的实现,,,[文].pdf
实现了POMDPs.jl的 PO-UCT 在线树搜索算法。PO-UCT 是 [1] 中描述的 POMCP 算法中最有用的组件。POMCP 的另一个组件,即重用树中的粒子以进行信念更新,由于下面的信念更新部分中描述的原因 关键字参数 max_depth::...
当今电脑围棋的最新最强的算法 用Delphi实现
( 1) 己方棋子数量 X1,对方棋子数量 X2 ( 2) 己方王棋数量 X3,对方王棋数量 X4 ( 3) 当己方棋子构成一列时,对方棋子不易对 ( 4) 当
对于有一定基础或热衷于研究的人来说,可以在这些基础代码上进行修改和扩展,实现其他功能。 【沟通交流】: 有任何使用上的问题,欢迎随时与博主沟通,博主会及时解答。 鼓励下载和使用,并欢迎大家互相学习,共同...
这是我写的算法设计与分析结课论文,用的蒙特卡洛算法搜索树,写的是一个虽然代码简易但是下棋能力强大的四子棋AI,你们可以用pycharm运行我的代码,玩下试试,如果你们电脑可以并行处理的话,只要模拟次数够大,只要...
当今电脑围棋的最新最强的算法用Java实现
四子棋AI 的UCT实现。卡时间4.5s. 主要部分在strategy文件中
如何为Rave增加新的控件,是英文版的。哪位能翻译一下就好了。在http://www.nevrona.com/上下载的。
不围棋中常用算法就是UCT ,但是UCT前期有着模拟次数低,性能差的缺点,在UCT中加入RAVE ,可以很好地解决上述问题,这也是参加国际比赛的选手的心得!
弗雷德里克·马尔尚德州扑克这是单挑限制德州扑克的命令行实现。 已实施 UCT 蒙特卡罗搜索算法。
matlab里面的单位阶越函数u(t)文件
uct 具有不同并行化实现的UCT。 测试域包括Nim,Othello / Reversi和Gobang。
法采用信心上限树算法(UCT 树)及蒙特卡洛模拟,这种算法适用于通过不断的模拟给出结论的场合,不需要很强的先验知识,对于蒙特卡洛方法和 UCT 的思想有了更深的认识,体会到了随机模拟的效率和效果 序中主要包含一...
uctimsclient1.0.14.tar.gz 测试IMS必备
UCT算法实现,可设置每步棋的时间。具体见readme