Posted on 2012-09-20 12:50
小明 阅读(13424)
评论(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 α
实现