小明思考

高性能服务器端计算
posts - 70, comments - 428, trackbacks - 0, articles - 0
  C++博客 :: 首页 :: 新随笔 :: 联系 :: 聚合  :: 管理

黑白棋算法设计

Posted on 2012-09-20 12:50 小明 阅读(9937) 评论(11)  编辑 收藏 引用 所属分类: Game Development

介绍

黑白棋,又叫反棋(Reversi)、奥赛罗棋(Othello)、苹果棋或翻转棋。黑白棋在西方和日本很流行。游戏通过相互翻转对方的棋子,最后以棋盘 上谁的棋子多来判断胜负。它的游戏规则简单,因此上手很容易,但是它的变化又非常复杂。有一种说法是:只需要几分钟学会它,却需要一生的时间去精通它。

黑白棋的棋盘是一个有8*8方格的棋盘。下棋时将棋下在空格中间,而不是像围棋一样下在交叉点上。开始时在棋盘正中有两白两黑四个棋子交叉放置,黑棋总是先下子。   

下子的方法:
把自己颜色的棋子放在棋盘的空格上,而当自己放下的棋子在横、竖、斜八个方向内有一个自己的棋子,则被夹在中间的全部翻转会成为自己的棋子。并且,只有在可以翻转棋子的地方才可以下子。

估价函数

黑白棋中最重要的是电脑对局势的判断,如何写好这样的估价函数是黑白棋人工智能程序的重点。

所谓的“金角银边草肚皮”,说明了子的位置的重要性是不同的。最最要的点是四个角,而和角相邻的三个点,则是不应该占领的,其次是四条边,占领后的好处也很多。

当然了除了子的位置,自由度也比较重要。
你的目标是限制对手的自由度(即棋步数量),同时增加自己的自由度




搜索算法

如果只是凭估价函数来走棋,是很难赢的,好的AI必须能够向前看几步,看得越深,棋力就越强。

这就涉及到博弈树搜索了,最经典是极大极小算法。

 

Minimax算法常用于棋类等由两方较量的游戏和程序。该算法是一个零总和算法,即一方要在可选的选项中选择将其优势最大化的选择,另一方则选择令对手优势最小化的方法。而开始的时候总和为0。
伪代码:
function minimax(node, depth)
   
if node is a terminal node or depth = 0
       
return the heuristic value of node
   
if the adversary is to play at node
       let α :
= +
       foreach child of node
           α :
= min(α, minimax(child, depth-1))
   
else {we are to play at node}
       let α :
= -
       foreach child of node
           α :
= max(α, minimax(child, depth-1))
   
return α

 


实现

 

用javascript和html5写了一个黑白棋,实现了人机对战,有还不错的智能, 我自己已经很难下赢了。

请用chrome或者firefox打开,chrome的javascript性能更好~

演示地址:  https://yshan.github.io/othello/

 


Feedback

# re: 黑白棋算法设计  回复  更多评论   

2015-03-07 17:29 by 祁慧娟
可以发一下黑白棋算法设计的整个代码文件给我吗,非常感谢的哈,1329388934@qq.com

# re: 黑白棋算法设计[未登录]  回复  更多评论   

2015-04-29 13:02 by ming
同求,非常感谢, sm940226@gmail.com

# re: 黑白棋算法设计  回复  更多评论   

2015-06-01 20:58 by emma
能把代码给我吗,多谢。想问一下用数据结构的知识实现这个功能思路是什么啊,就是做智能aI的话328690449@qq.com

# re: 黑白棋算法设计[未登录]  回复  更多评论   

2015-06-02 22:50 by haha
刚刚下了两把,真的挺厉害的呀!!能把黑白棋算法发给我一下吗? 1358729249@qq.com 非常感谢!

# re: 黑白棋算法设计  回复  更多评论   

2015-06-05 15:44 by Aman
大神求代码~~~3204627625@qq.com

# re: 黑白棋算法设计  回复  更多评论   

2015-06-26 18:42 by 766382692
求算法代码,邮箱766382692@qq.com,目前对这个游戏的算法深感兴趣,感谢!
另外试了一下你的程序,执黑子Normal模式,13步秒杀……别的模式还没试。

# re: 黑白棋算法设计  回复  更多评论   

2015-08-09 16:16 by er
能把代码发我一下吗?1003309869@qq.com

# re: 黑白棋算法设计  回复  更多评论   

2015-11-06 09:15 by 小魏
能提供一下c++代码吗,1161292997@qq.com
谢谢!

# re: 黑白棋算法设计[未登录]  回复  更多评论   

2015-12-27 14:49 by 皮皮
麻烦问一下,对于位棋盘有没有简单的估价方式(不用开局库)
我是学生,现在有一个AI对抗赛,只能提交cpp,不能使用开局库(额,期末来了,时间略紧)

# re: 黑白棋算法设计  回复  更多评论   

2016-01-28 14:11 by dz
你好,谢谢你的指点。我终于能用代码下赢你的最高难度了。不过这局没有真正意义上结束。我只是进行到终局搜索确定可以胜了就结束了。因为你的页面在搜索最后一步的时候停了。

# re: 黑白棋算法设计  回复  更多评论   

2016-03-11 14:13 by BetaGo
你好,请问除了minimax,也用了alpha beta pruning吧?有没有用opening book, transposition table或者bitboard呢?Heuristic function里面mobility, positional weights, stability, parity等等具体是怎么设置的呢?在开局和中后期有什么变化?除此以外,有没有用别的算法,比如Monte Carlo搜索?最大搜索深度在开局时和中后期分别达到了几层?

问题有点多,可是你这个AI真的很棒,而且算得也很快,非常吸引人。

只有注册用户登录后才能发表评论。
【推荐】超50万行VC++源码: 大型组态工控、电力仿真CAD与GIS源码库
网站导航: 博客园   IT新闻   BlogJava   知识库   博问   管理