【正文】 16 18 alpha 剪枝示例 beta 剪枝示例 取極大值的節(jié)點(diǎn) 取極小值的節(jié)點(diǎn) α裁減 在考慮輪到棋手下棋的一個(gè)親節(jié)點(diǎn)及輪到對(duì)手下棋的一個(gè)子節(jié)點(diǎn)時(shí)，如果該子節(jié)點(diǎn)的數(shù)值已經(jīng)小于或等于其親節(jié)點(diǎn)的回溯值，那么就不需要對(duì)該節(jié)點(diǎn)或者其后續(xù)節(jié)點(diǎn)做更多的處理了。 將上述這個(gè)情形推廣一下，設(shè)想有如下圖左部所示的一棵極大極小樹(shù)的片斷，節(jié)點(diǎn)數(shù)字為該節(jié)點(diǎn)的值，節(jié)點(diǎn) B 的值為 18，節(jié)點(diǎn) D 的值為 16，由此我們可以判斷節(jié)點(diǎn) C 的值將小于等于 16（取極小值）；而節(jié)點(diǎn) A 的值為 20 節(jié)點(diǎn) MAX（ B， C），為 18，也就是說(shuō)不再需要估節(jié)點(diǎn) C 的其他子節(jié)點(diǎn)如 E，F(xiàn) 的值就可以得出父節(jié)點(diǎn) A 的值。 α β 剪枝的方法如下： （ 1） MAX 節(jié)點(diǎn)的 α 值為當(dāng)前子節(jié)點(diǎn)的最大倒推值； （ 2） MIN 節(jié)點(diǎn)的 β 值為當(dāng)前子節(jié)點(diǎn)的最小倒推值； （ 3） α β 剪枝的規(guī)則如下： ① 任何 MIN 節(jié)點(diǎn) n 的 β 值大于或等于它先輩節(jié)點(diǎn) 的 α 值，則 n 以下的分枝可停止搜索，并令節(jié)點(diǎn) n 的倒推值為 β 。 AlphaBeta 剪枝 (AlphaBeta Purning) 對(duì)于一般的最大最小搜索，即使每一步只有很少的下法，搜索的位置也會(huì)增長(zhǎng)非?？欤辉诖蠖鄶?shù)的中局棋形中，每步平均有十個(gè)位置可以下棋，于是假設(shè)搜索九步 (程序術(shù)語(yǔ)稱為搜索深度為九 )，就要搜索十億個(gè)位置 (十的九 次方 )，極大地限制了電腦的棋力。 在上面的博弈樹(shù)中，如果我們令甲勝的局面的為 1，乙勝的局面值為1，而各局的值為 0。對(duì)于 MIN 節(jié)點(diǎn)，由于 MIN 方總是選擇使估值最小的走步，因此 MIN 節(jié)點(diǎn)的倒退值應(yīng)取其后繼節(jié)點(diǎn)的最小值。一種可行的方法是用當(dāng)前正在考慮的節(jié)點(diǎn)生成一棵部分博弈樹(shù)，由于該博弈樹(shù)的葉節(jié)點(diǎn)一般不是哪一方面的獲勝點(diǎn)，因此需要利用估價(jià)函數(shù)對(duì)葉節(jié)點(diǎn)進(jìn)行靜態(tài)估值。 18 博弈樹(shù)中的節(jié)點(diǎn)是逐層交替出現(xiàn)的。 我們可以依此構(gòu)建一個(gè)博弈樹(shù)，將所有的走法羅列出來(lái)。假設(shè)博弈的一方為 MAX，另一方為 MIN。所謂機(jī)遇性博弈，是指存在不可測(cè)性的博弈，如擲幣。博弈分為雙人完備信息博弈和機(jī)遇性博弈。 16 第四章 系統(tǒng)結(jié)構(gòu)與模型 五子棋人機(jī)對(duì)弈程序流程圖 用來(lái)實(shí)現(xiàn)計(jì)算機(jī)下棋的方法是 :將棋盤(pán)看成一條條的線 ,然后就開(kāi)始試著在各個(gè)點(diǎn)上放上棋子 ,看看有沒(méi)有五連 ,長(zhǎng)連 ,四三 ,四四等情況出現(xiàn)。啟發(fā)式搜索也是邊走邊試探，每走一步，都設(shè)法計(jì)算當(dāng)前棋局的各種可能走法及對(duì)手各種反應(yīng)的得分，然后立足于對(duì)方應(yīng)棋以后自己 面臨的最壞局勢(shì)，尋找那種能夠爭(zhēng)取到的最好的結(jié)果，然后倒推回去選擇滿意的棋步，因而也叫做“極大極小分析法”。然后，把兵力優(yōu) 勢(shì)和棋局優(yōu)勢(shì)用加權(quán)求和的數(shù)學(xué)式聯(lián)系起來(lái)，構(gòu)成某種形式的“估值函數(shù)”。 估值函數(shù) 問(wèn)題求解空間中每一個(gè)節(jié)點(diǎn)對(duì)應(yīng)于一個(gè)子目標(biāo)。我們還可以有這樣的想法：如果 A*算法的估值函數(shù)可以做到差不離的話，也許我們就可以找到一個(gè)比較好的走法。 在各種搜索算法中，有一個(gè) A*搜索算法，也叫做最佳搜索算法，實(shí)際是一種啟發(fā)式搜索 ， 它是對(duì)于問(wèn)題的各種情況設(shè)定一個(gè)估值函數(shù)，假設(shè)我們選擇的是值最小的道路，在搜索的時(shí)候， A*算法根據(jù)估值函數(shù)判斷下一步應(yīng)選擇的道路，并不停地用走過(guò)的實(shí)際路線的價(jià)值加上下一點(diǎn)的估值函數(shù)作為新的估值。 ①棋子的價(jià)值評(píng)估 棋子的價(jià)值評(píng)估，簡(jiǎn)單的說(shuō)就是評(píng)估雙方都有哪些棋子在棋盤(pán)上。 C、 “ a”這一點(diǎn)有可能被看作是三三。 五手兩打 ：是指黑棋在下盤(pán)面上關(guān)鍵的第 5 手棋時(shí)，必須下兩步棋，讓白棋在這兩步棋中任選一步，然后再繼續(xù)對(duì)弈。 四四 ：由于黑方走一著 在無(wú)子交叉點(diǎn)上同時(shí)形成二個(gè)或二個(gè)以上黑方“四”的局面。 B、跳三 ：中間僅間隔一個(gè)無(wú)子交叉點(diǎn)的連三，但兩端延長(zhǎng)線均至少有一個(gè)無(wú)子的交叉點(diǎn)與此三子相連。（如下圖） B、沖四 ：除“活四”外的，再下一著棋便可形成五連，并且存在五連的可能性的局面。 五連 ：在棋盤(pán)上形成的 5 個(gè)同色棋子的“連”。如“天元” H8，四個(gè)“星”分別為 D D1 L1L4 等。天元和星應(yīng)在棋盤(pán)上用直徑約為 厘米的實(shí)心小圓點(diǎn)標(biāo)出。 9 第三章 要解決的幾個(gè)關(guān)鍵問(wèn)題 五子棋棋盤(pán)介紹 五子棋棋盤(pán) ：棋盤(pán)正中一點(diǎn)為“天元”。因此，窮舉搜索所有的可能走法，面對(duì)的組合數(shù)將達(dá)到 38 的 84 次方之巨，它大于 10 的 132 次方， 即 1 后面有 132個(gè) 0，與整個(gè)世界中原子的總數(shù)相近。也就是說(shuō)，電腦若想找到當(dāng)前最優(yōu)的走法，需要全廣度全深度地搜索雙方棋子所有的可能走法。仔細(xì)思考一下，就會(huì)發(fā)現(xiàn)這種想法實(shí)在太幼稚。在決策過(guò)程中要對(duì)形勢(shì)做出恰當(dāng)?shù)墓烙?jì)，搜尋各種可能的策略組合，通過(guò)對(duì)比分析確定對(duì)自己最有利的策略。早期人工智能的研究實(shí)踐，正是從電腦下棋發(fā)端；人工智能的第一大應(yīng)用成就，就是發(fā)展了能夠求解難題的下棋程序。目前人工智能在發(fā)展過(guò)程中既有突破但也面臨很大的困難。而且這類(lèi)軟件個(gè)個(gè)水平頗高，大有與人腦分庭抗禮之勢(shì)。現(xiàn)代五子棋日文稱之為“連珠”，英譯為“ Renju”，英文稱之為“ Gobang”或“ FIR” (Five in a Row 的縮寫(xiě) )，亦有“連五子”、“五子連”、“串珠”、“五目”、“五目碰”、“五格”等多種稱謂。 1 五子棋人機(jī)對(duì)弈程序 摘要： 五子棋程序由兩個(gè)主要部分組成：一個(gè)估值函數(shù)和一個(gè)樹(shù)狀搜索算法。 關(guān)鍵詞： 五子棋 人工智能 估值函數(shù) 樹(shù)狀搜索算法 極大極小法 2 The program for Renju in man vs puter Abstract: The program for Renju is posed of two parts: a evaluation function and a hashtable treesearching algorithm. The evaluation function is used to judge the advantage or disadvantage situation for each part, the hashtable treesearching algorithm is used to search almost all the possible steps and find out the best pathway for the program. The puter of Artificial Intelligence (AI) imitate the intelligence of human, its inspiring search way is Go and Explore, namely, Minimax. Key words: Renju Artificial Intelligence (AI) evaluation function hashtable treesearching algorithm Minimax 3 五子棋人機(jī)對(duì)弈程序目錄 中文摘要 英文摘要 第一章 引言?????????????????????????? 5 ????????????????????? 5 本論文的目的、內(nèi)容及作者的任務(wù)?????????????? 5 第二 章 研究現(xiàn)狀及設(shè)計(jì)目標(biāo)??????????????????? 7 ?????????????? 7 ??????????????? 7 ?????????????????? 8 第三章 要解決的幾個(gè)關(guān)鍵問(wèn)題?????????????????? 9 ?????????????????? 9 ???????????????????? 9 ???? ???????????? 9 ????????????????? 13 ?????????????????????? 13 ????????????????????? 13 ?????????? 14 第四章 系統(tǒng)結(jié)構(gòu)與模型???????????????????? 16 ???????????????? 16 ???????????????? 16 ??????????????????????? 16 4 極大極小值算法（ Minimax Algorithm）????????? 18 AlphaBeta 剪枝 (AlphaBeta Purning) ???????? 19 ??????????????????? 21 ??????????????????? 21 ????????????????? 22 第五章 系統(tǒng)實(shí)現(xiàn)技術(shù)????????? ???????????? 25 ????????????? 25 ??????????????????????? 25 ??????????????????? 28 ?????????????????????? 29 ????????????????? 31 ?????????????????????? 31 ????????????????????? ? 33 ????????????????????? 37 第六章 性能測(cè)試與分析???????????????????? 41 系統(tǒng)運(yùn)行所需的軟件、硬件環(huán)境?????????????? 41 ???????????????????????? 41 ????????????????? 41 ??????????????????? 42 ???????????????????????? 42 第七章 結(jié)束 語(yǔ)???????????????????????? 47 參考文獻(xiàn)??????????????????????????? 48 附錄：程序清單（附光盤(pán)） 5 第一章 引 言 五子棋是起源于中國(guó)古代的傳統(tǒng)黑白棋種之一。它是中西文化的交流點(diǎn)，是古今哲理的結(jié)晶 近來(lái)隨著計(jì)算機(jī)的快速發(fā)展，各種棋類(lèi)游戲被紛紛請(qǐng)進(jìn)了電腦，使得那些喜愛(ài)下棋，又常常苦于沒(méi)有對(duì)手的棋迷們能隨時(shí)過(guò)足棋癮。 、內(nèi)容及作者的任務(wù) 人工智能是一門(mén)廣泛的交叉和前沿科學(xué)，從 1956 年正式提出人工智能 6 學(xué)科算起，已有 40 多年歷史。 7 第二章 研究現(xiàn)狀及設(shè)計(jì)目標(biāo) 博弈，歷來(lái)是人工智能（ AI）的一個(gè)重要的研究領(lǐng)域 。博弈是研究使自己取勝、戰(zhàn)勝對(duì)手的策略。當(dāng)時(shí)電腦下象棋之所以難突破，大概是計(jì)算 機(jī)速度太慢的緣故。然后，對(duì)應(yīng)著每 8 一種可能的回合，都必須分別一步步推算下去，一直算到能把人類(lèi)棋手的“ 王 ” 殺死的那一步為止。有人曾作過(guò)這樣的估算：國(guó)際象棋大師之間對(duì)弈的平均總棋步約為 84 步，任一種棋局狀態(tài)下又有 38 種合乎規(guī)則的可能走法。本程序不 采用棋譜庫(kù) ，用啟發(fā)式搜索， 做到前瞻 6 步棋 ，盡力擊敗對(duì)手。從兩條端線和兩條邊線向正中發(fā)展而縱橫交叉在第四條線形成的四個(gè)點(diǎn)稱為“星”?？v橫軸上的橫縱線交叉點(diǎn)分別用橫縱線標(biāo)記的名稱合寫(xiě)成。 連 ：在棋陽(yáng)線和陰線的任意一條線上形成的有 5 個(gè)或 5 個(gè)以上的同色棋子不間隔地緊緊相連。 A、活四 ：在棋盤(pán)某一條陽(yáng)線或陰線上有同色 4 子不間隔地緊緊相連，且在此 4 子兩端延長(zhǎng)線上各有一個(gè)無(wú)子的交叉點(diǎn)與此 4 子緊密相連。 A、連三 ：在棋盤(pán)某一條陽(yáng)線或陰線上有同色三子相連，且在此三子兩端延長(zhǎng)線上有一端至少有一個(gè)，另一端至少有兩個(gè)無(wú)子的交叉點(diǎn)與此三子 11 緊密相連。 三三 ：由于黑方走一著在無(wú)子交叉點(diǎn)上同時(shí)形成二個(gè)或二個(gè)以上黑方“活三”的局面。 三手可交換 ：是指黑棋下盤(pán)面第 3 著棋后，白方在應(yīng)白④之前，如感覺(jué)黑方棋形不利于己方，可提出交換，即執(zhí)白棋一方變?yōu)閳?zhí)黑棋一方，而黑方不可以不換。 B、 “ a”這一點(diǎn)也不是三三，因?yàn)闄M向也不是活三，而是一個(gè)假活三 (此形狀日本稱之為“下 止” )。這一過(guò)程對(duì)具體的棋類(lèi)知識(shí)依賴程度很深，但是仍有一般性的規(guī)律可循。以下以A*搜索 為例進(jìn)行說(shuō)明。但這樣太困難。實(shí)際上這就是對(duì) A*算法估值函數(shù)的一種設(shè)想。在五子棋程序中，需要計(jì)算雙方的棋局優(yōu)勢(shì)，在哪些地方布防哪類(lèi)棋子具有更大的威懾力。這是因?yàn)榇_定估價(jià)函數(shù)所依據(jù)的知識(shí)往往是經(jīng)驗(yàn)的和直觀判斷的知識(shí)，這類(lèi)知識(shí)通常稱為啟發(fā)式知識(shí)。順便提一句，在下棋策略中放棄“尋求最優(yōu)”而代之“尋求滿意”的思想，后來(lái)又被西蒙教授發(fā)揚(yáng)光大，使之成為現(xiàn)代經(jīng)濟(jì)決策理論的重要基石。 博弈樹(shù) 博弈是一類(lèi)富有智能行為的競(jìng)爭(zhēng)活動(dòng)，如下棋、打牌、戰(zhàn)爭(zhēng)等。這類(lèi)博弈我主要談五子棋人機(jī)對(duì)弈程序。因此，當(dāng)任何一方走步時(shí)，都選擇自己最為有利，而對(duì)另一方最為不利的行動(dòng)方案。反之 MIN 也是如此。 博弈樹(shù)具有如下特點(diǎn)： 博弈的初始狀態(tài)是初始節(jié)點(diǎn)。但對(duì)于復(fù)雜的博弈，如國(guó)際象棋，大約有 10