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

fanhq666的博客

Fan-Fun

 
 
 

日志

 
 

用随机化算法下五子棋  

2011-02-03 20:58:10|  分类: 程序 |  标签: |举报 |字号 订阅

  下载LOFTER 我的照片书  |
在冬令营,胡老师提示了一种用于博弈的蒙特卡罗算法:
假象对弈双方都随机地落子,进行100000盘,计算胜率作为局面估价。
他说这个算法在围棋中的应用秒杀了曾经的世界最高水平的计算机围棋程序。

听完课后,某同学说明年的团体对抗赛大家的程序里估计rand()漫天飞。
我决定试一下。不过,让我写一个判断围棋胜负的程序,那我宁可去登月。
怎么办呢?下五子棋吧。我假设棋盘是15*15的。
我很快写了一个用暴力法实现的随机下棋过程,测了一下速度,还有输出的稳定性(即,换个随机函数、微调一下重复次数来看输出的变化情况)。结果很不理想,大约每秒只能进行20000盘,输出超级不稳定。
怎么办呢?
我发现,之所以输出不稳定是因为有bug(窘)。于是,我先把bug修复了,输出就比较稳定了。之后,我又用树状数组和各种常数优化技巧(包括-O2),把复杂度降了下来,但速度只提高到了每秒60000盘(竟然只是常数优化的效果!)。
只能承认这个速度了。下面就是想方设法让程序能够合理地利用这个计算速度。
一个比较朴素的想法是:走一步的时候,尝试每一个位置,然后进行100000次随机过程来估价。
这个的速度比较惨,走一步要6分15秒,基本到了不可忍受的地步了。如果降低随机化的次数,那么答案的波动会比较剧烈。
这时,我有了一个比较基本的想法:很多格子很明显是不应该往那里下的(例如开局的时候走角上)。于是,就有了一种迭代的算法:
初始的时候随机过程的重复次数设为10000,对每个格子估价。之后,舍弃估价处在后一半的格子,将随机重复次数加倍,重复这个过程,直到剩下最后几个格子。
当剩下4个格子的时候,随机重复次数到达了320000,而总用时控制在3分钟左右。可以说,这个方案带来了比较大的改善。

我试着和这个程序下五子棋,总得来说,有一定的“智能的假象”。不过,这种基于概率的算法显然无法进行比较精确的计算(例如双三的情况不能很好地挖掘出来,但活四的处理还不错)。但是,最后筛选出来的格子还是比较有方向性的指导意义的。
为了让棋局更精彩,我决定在必要的时候使用人脑对程序的结果进行微调(对于两步之内就要被杀的失误情况,从它的候选结果中挑出一个能破除这种困局的走法)。
结果是,我的人脑连输两盘(我没学过五子棋,一直跟着感觉下来着(估计也就是重复1000次的随机估价),被秒很正常)。

通过和程序下,我得出了一个结论:
随机化估价能够比较好地指明“大方向”,但对于细节和比较精细的计算处理不够。
于是,可以将随机化和暴力搜索结合起来,利用随机化指明一个大方向,之后用暴力来具体考察最终应该选择这个大方向里的哪个格子。这个可以看作是对搜索的一个极大补充(启发式搜索?)
关于随机化的部分,我还想到了几个优化:
1.多线程?这显然是有希望的,因为随机化过程天然的支持并发。
2.启发式随机?我当前在随机时候的策略是从所有的空着的格子中随机挑一个,这个显然是粗糙的。能否加入些启发式的策略,例如:挨着非空格子比较多的格子给予更多的概率?只从挨着已有棋子的格子的格子中挑?还是。。。。。。

看来,明年的团体对抗赛能够多一个亮点了。
代码下载地址:http://cid-354ed8646264d3c4.office.live.com/self.aspx/.Public/MonteCarlo^_chess.cpp
  评论这张
 
阅读(1675)| 评论(2)
推荐 转载

历史上的今天

评论

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

页脚

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