注册 登录  
 加关注
   显示下一条  |  关闭
温馨提示!由于新浪微博认证机制调整,您的新浪微博帐号绑定已过期,请重新绑定!立即重新绑定新浪微博》  |  关闭

ydc的博客

 
 
 

日志

 
 

蒙特卡洛+UCT博弈  

2017-04-29 00:08:51|  分类: 大学 |  标签: |举报 |字号 订阅

  下载LOFTER 我的照片书  |
正好点开博客,发现几百年没有更过了。
OI的东西肯定是更不动了,倒不如来写一点大学学的东西。
不过面向人群就很尴尬了吧。
现在在看这个博客的应该大多是oier?那对oi考试似乎没什么帮助。
当初看我博客的人,现在看到这些东西,应该哑然失笑:“这么水的东西也写?”

不过如果是签了THU的高三党高二党,说不定过几年会大呼造福人类呢23333

先从人智导课上讲的这个开始吧。
我们的大作业是一个重力四子棋,指的是每次只能下在某一列的最底下一排,然后四子棋。
由于大家都没接触过,所以是一个比较公平的作业。
我使用的算法是蒙特卡洛法+UCT

http://fanhq666.blog.163.com/blog/static/8194342620111381349534/
第一次看到这个问题是来自于范爷的这篇博客,我当时很惊讶,随便乱下能下赢?
然而算法真的是随便乱下。

每次下棋时,把当前局面当做根。
然后开始模拟下棋,双方都是随机乱下,下到游戏结束为止。
计算收益,回溯时更新每个状态的权重(这个局面下了几次、收益是多少)
这就叫一次模拟。
然后模拟很多次。
最后按收益和下的次数的比值来选。
那么涉及到的状态数肯定不超过模拟次数*一盘棋最多多少个子,这个是能接受的。
所以hash一下就好。

说实话我是觉得这个算法很傻逼的。
比如下围棋的人就知道,有个技巧叫征子,征子要想杀掉对方,就会连续几十步只有唯一下法。
个人认为直接蒙特卡洛法是肯定看不到征子的。

但是重力四子棋毕竟不是围棋,没有这么巧妙的下法。
所以蒙特卡罗法还是能看的。
能看到什么程度呢?
说出来很丢人,反正我下不赢(逃)

虽然如此,但是仍然不够优,把这个作业交上去估计分数会很低。
所以我们就有一种算法叫UCT算法。

UCT算法基于一种叫UCB的算法,UCB的算法大概基于一些概率论的知识?
反正我看不懂。

我们蒙特卡洛的时候,可能会觉得,都下到这个局面了,为什么还要随机啊!很明显要走某一步啊!
我一开始也想过蒙特卡洛和dp结合,比如dp他个3层啥的(dp法很水,略去),但是毫无卵用,毕竟3层太少了,能看到的都能被蒙出来。还极其浪费时间。
所以有人就会想了,能不能不随机,而是选“收益/模拟次数”最优的点?
这样会很蛋疼,因为一开始都是0。而且很容易由于刚开始几步运气好就陷入了一个不够优的方法。
即使感性上我们认为这样子很好,但是小情况却不太会判断。

所以有人就来帮我们总结了。
定义bestChild函数为,对于状态s,来找一个决策。如果有个决策没有使用过,就直接使用这个决策;否则,对于某个决策,假设走到状态v。定义N(x)表示状态x被访问过多少次,val(x)表示收益,选一个val(v)/N(v)+c*sqrt(2*ln(N(v))/N(s))最大的点v,其中c是自己调的参,我也不知道几比较好,否则我拿了个1,2都试了下。
前面的val(v)/N(v)就是我们感性上的结果,后面加的那个偏移量是大神用概率论倒腾出来的结果,直接用就好了。

当然如果所有的随机都换成这个就很傻逼了(直接变成搜索),所以算法是这样的。
假设现在我要下棋,当前局面是s。开始模拟,模拟过程如下:
如果当前局面没有没用过的决策,就选择bestChild。
一直选到游戏结束或者选到一个有“没有用过的决策”的状态。
前者很容易,后者的话,就从这个“没有用过的决策到达的状态”开始,蒙特卡洛。

如此一来,这个算法感性上就很靠谱了。反正我觉得迭代次数趋于无穷大的时候这个显然是模拟了最优解的(只是我觉得),但是蒙特卡洛明显做不到。

然后调参的话,可以选择把“如果有个决策没有用过就用”改成“如果有个决策没有用过x次就用”,效果还行
  评论这张
 
阅读(98)| 评论(0)
推荐 转载

历史上的今天

在LOFTER的更多文章

评论

<#--最新日志,群博日志--> <#--推荐日志--> <#--引用记录--> <#--博主推荐--> <#--随机阅读--> <#--首页推荐--> <#--历史上的今天--> <#--被推荐日志--> <#--上一篇,下一篇--> <#-- 热度 --> <#-- 网易新闻广告 --> <#--右边模块结构--> <#--评论模块结构--> <#--引用模块结构--> <#--博主发起的投票-->
 
 
 
 
 
 
 
 
 
 
 
 
 
 

页脚

网易公司版权所有 ©1997-2017