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