Posted on 2012-09-20 12:50
小明 閱讀(13578)
評論(11) 編輯 收藏 引用 所屬分類:
Game Development
介紹
黑白棋，又叫反棋（Reversi）、奧賽羅棋（Othello）、蘋果棋或翻轉(zhuǎn)棋。黑白棋在西方和日本很流行。游戲通過相互翻轉(zhuǎn)對方的棋子，最后以棋盤 上誰的棋子多來判斷勝負(fù)。它的游戲規(guī)則簡單，因此上手很容易，但是它的變化又非常復(fù)雜。有一種說法是：只需要幾分鐘學(xué)會它，卻需要一生的時間去精通它。黑白棋的棋盤是一個有8*8方格的棋盤。下棋時將棋下在空格中間，而不是像
圍棋一樣下在交叉點(diǎn)上。開始時在棋盤正中有兩白兩黑四個棋子交叉放置，黑棋總是先下子。
下子的方法：把自己顏色的棋子放在棋盤的空格上，而當(dāng)自己放下的棋子在橫、豎、斜八個方向內(nèi)有一個自己的棋子，則被夾在中間的全部翻轉(zhuǎn)會成為自己的棋子。并且，只有在可以翻轉(zhuǎn)棋子的地方才可以下子。
估價函數(shù)
黑白棋中最重要的是電腦對局勢的判斷，如何寫好這樣的估價函數(shù)是黑白棋人工智能程序的重點(diǎn)。
所謂的“金角銀邊草肚皮”,說明了子的位置的重要性是不同的。最最要的點(diǎn)是四個角，而和角相鄰的三個點(diǎn)，則是不應(yīng)該占領(lǐng)的，其次是四條邊，占領(lǐng)后的好處也很多。
當(dāng)然了除了子的位置，自由度也比較重要。
你的目標(biāo)是限制對手的自由度（即棋步數(shù)量），同時增加自己的自由度
搜索算法
如果只是憑估價函數(shù)來走棋，是很難贏的，好的AI必須能夠向前看幾步，看得越深，棋力就越強(qiáng)。
這就涉及到博弈樹搜索了，最經(jīng)典是極大極小算法。
Minimax算法常用于棋類等由兩方較量的游戲和程序。該算法是一個零總和算法，即一方要在可選的選項(xiàng)中選擇將其優(yōu)勢最大化的選擇，另一方則選擇令對手優(yōu)勢最小化的方法。而開始的時候總和為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 α
實(shí)現(xiàn)
用javascript和html5寫了一個黑白棋，實(shí)現(xiàn)了人機(jī)對戰(zhàn)，有還不錯的智能， 我自己已經(jīng)很難下贏了。
請用chrome或者firefox打開，chrome的javascript性能更好～
演示地址:
https://yshan.github.io/othello/