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