五子棋內(nèi)容參考

1、1最先在棋盤的橫向、豎向、斜向形成連續(xù)的相同色五個棋子的一方為勝利。3 子棋起源于古代中國，發(fā)展于日本，風(fēng)靡于歐洲。對于它與圍棋的關(guān)系有兩種 說法，一說早于圍棋，早在 “堯造圍棋”之前，民間就已有五子棋游戲；一說 源于圍棋，是圍棋發(fā)展的一個分支。在中國的文化里，倍受人們的青睞。本世紀(jì) 初五子棋傳入歐洲并迅速風(fēng)靡全歐。通過一系列的變化，使五子棋這一簡單的游 戲復(fù)雜化、規(guī)范化，而最終成為今天的職業(yè)連珠五子棋， 同時也成為一種國際比 賽棋。j 基于五子棋游戲設(shè)計：對局中拔子、中途退場均判為負(fù)6 基于五子棋游戲設(shè)計進(jìn)行游戲設(shè)計之前，首先決定的第一個問題就是，使用什 么開發(fā)環(huán)境來編寫環(huán)境 ? 自己雖然比

2、較熟悉 java 語言，但是實際開發(fā)項目經(jīng)驗 很少，所以決定用 jcreator, 其擁有高亮語法編輯、使用向?qū)б约巴耆ㄖ频挠脩?界面，最主要的是能夠自動查找文件于 main 方法或html 文件以支持 java 小 應(yīng)用程序，然后啟動相應(yīng)的工具。其.2 本課題研究的意義近次確定整個程序的結(jié)構(gòu)框架。由于 applet 運行速度較慢，如果在加上算法搜 索時間，顯然不符合程序的設(shè)計要求，決定用 java 應(yīng)用程序開發(fā) .整個程序的功 能實現(xiàn)流程是這樣的：網(wǎng)絡(luò)對戰(zhàn)涉及算法較少，所以先實現(xiàn)網(wǎng)絡(luò)部分，實現(xiàn)基本 的棋盤和棋子的類，添加判斷勝負(fù)條件，這部是基礎(chǔ)，也是很重要的，電腦 ai 也在這些基礎(chǔ)上添加

3、上來的。這個題目的 2 個功能包括 2 個重要算法，電腦ai 和勝負(fù)條件，勝負(fù)條件運算量不大，有固定的模式。難點是人工智能，可以這樣 說，人工智能的好壞決定了這個題目的完成深度。所以，大部份時間花在 ai 算 法的研究和改進(jìn)上，對于算法我掌握的不多，研究了一些國內(nèi)的五子棋算法，參 考了一些游戲設(shè)計算法，詳細(xì)比較各種算法的優(yōu)缺點，而且參考了現(xiàn)代五子棋比 賽的各種規(guī)則和技巧，盡量聯(lián)系實際，努力提高電腦 ai。1 個題目核心是人工智能和 socekt 編程，。并且人工智能中的博弈部分，由于 采用了大量的搜索算法，其中很多被利用到各方面。它的概念、方法和技術(shù)，正 在各行各業(yè)廣泛滲透。智能已經(jīng)成為當(dāng)今各

4、種新產(chǎn)品、新裝備的發(fā)展方向。所以， 趁著這個機會，對人工智能中比較容易實現(xiàn)的人機博弈進(jìn)行了解研究學(xué)習(xí)， 也是很實用且很有必要的 1關(guān)鍵詞：深度搜索；估值；電腦 ai ;五子棋；算法2來越多的具有智能的機器進(jìn)入了人類的生活，人工智能的重要性如今顯而易見。 自己對人工智能比較感興趣， 而五子棋游戲程序的開發(fā)實現(xiàn)這個課題， 正好提供 給我這樣一個研究的機會，通過對人工智能中博弈方面的研究（人機對弈），讓 我在簡單的人機對弈全局設(shè)計， 以及具體到相關(guān)算法上有了深入的了解。 人工智 能屬于計算機科學(xué)的領(lǐng)域， 它以計算機技術(shù)為基礎(chǔ)， 近幾十年來， 它的理論和技 術(shù)已經(jīng)日益成熟， 應(yīng)用領(lǐng)域也正在不斷擴(kuò)大，

5、顯示出強大的生命力。 人工智能大 致可以分成幾個學(xué)科， 它們每一個都是獨特的， 但是它們常常又互相結(jié)合起來完 成設(shè)計任務(wù)，這時，這些學(xué)科之間的差別就變的很模糊。人工智能在專家系統(tǒng)， 自然語言理解， 自動定理證明， 自動程序設(shè)計， 人工智能在機器人學(xué)、 模式識別、 物景分析、數(shù)據(jù)庫的智能檢索、機器下棋（實質(zhì)上是博弈論問題）和家用電器智 能化等領(lǐng)域都有廣泛的應(yīng)用。而這個課題就是和人工智能中的博弈論領(lǐng)域緊密相 關(guān)的。這摘要 五子棋作為一個棋類競技運動，在民間十分流行，為了熟悉五子棋規(guī)則及技巧， 以及研究簡單的人工智能，決定用 java 開發(fā)五子棋游戲。主要完成了人機對戰(zhàn) 和玩家之間聯(lián)網(wǎng)對戰(zhàn) 2 個功

6、能。網(wǎng)絡(luò)連接部分為 socket 編程應(yīng)用，客戶端和服 務(wù)器端的交互用 class message 定義，有很好的可擴(kuò)展性，客戶端負(fù)責(zé)界面維 護(hù)和收集用戶輸入的信息， 及錯誤處理。 服務(wù)器維護(hù)在線用戶的基本信息和任意 兩個對戰(zhàn)用戶的棋盤信息， 動態(tài)維護(hù)用戶列表。 在人機對弈中通過深度搜索和估 值模塊，來提高電腦棋手的智能。 分析估值模塊中的影響精準(zhǔn)性的幾個要素， 以 及提出若干提高精準(zhǔn)性的辦法， 以及對它們搜索的節(jié)點數(shù)進(jìn)行比較， 在這些算法 的基礎(chǔ)上分析一些提高電腦 ai 方案，如遞歸算法、電腦學(xué)習(xí)等。算法的研究有 助于理解程序結(jié)構(gòu)，增強邏輯思維能力，在其他人工智能方面也有很大的參考作 用。1

7、 引言1.1 課題背景五子棋是起源于中國古代的傳統(tǒng)黑白棋種之一。 現(xiàn)代五子棋日文稱之為連珠，英 譯為 renju ，英文稱之為 gobang 或 fir（five in a row 的縮寫），亦有連五子、五子 連、串珠、五目、五目碰、五格等多種稱謂。五子棋起源于古代中國，發(fā)展于日本，風(fēng)靡于歐洲。對于它與圍棋的關(guān)系有兩種 說法，一說早于圍3棋，早在 “堯造圍棋”之前，民間就已有五子棋游戲；一說 源于圍棋，是圍棋發(fā)展的一個分支。在中國的文化里，倍受人們的青睞。本世紀(jì) 初五子棋傳入歐洲并迅速風(fēng)靡全歐。通過一系列的變化，使五子棋這一簡單的游 戲復(fù)雜化、規(guī)范化，而最終成為今天的職業(yè)連珠五子棋， 同時也成

8、為一種國際比 賽棋。java 語言是當(dāng)今最為流行的程序設(shè)計語言之一 作為一門非常優(yōu)秀和極為健壯的 編程語言， 它同時具有的面向?qū)ο?，與平臺無關(guān)，分布式應(yīng)用，安全，穩(wěn)定和多 線程等優(yōu)良的特征，使用 java 語言，不僅可以開發(fā)出功能強大的大型應(yīng)用程序，而且 java 語言本身突出的跨平臺的特性也使得它特別適合于 internet 上的應(yīng)用 開發(fā)，可以這樣說， java 的出現(xiàn)使得所開發(fā)的應(yīng)用程序“一次編寫，處處可用”的 實現(xiàn)成為了可能。1.2 本課題研究的意義 近來隨著計算機的快速發(fā)展，各種各樣的電腦游戲?qū)映霾桓F，使得我們能有更多 的娛樂項目，而棋類游戲能起到鍛煉人的思維和修身養(yǎng)性的作用， 而且

9、棋類游戲 水平頗高，大有與人腦分庭抗禮之勢。其中戰(zhàn)勝過國際象棋世界冠軍-卡斯帕羅夫的“深藍(lán)”便是最具說服力的代表；其它像圍棋的“手淡”、象棋的“將族”等也以其 優(yōu)秀的人工智能深受棋迷喜愛。越來越多的具有智能的機器進(jìn)入了人類的生活，人工智能的重要性如今顯而易 見。自己對人工智能比較感興趣， 而五子棋游戲程序的開發(fā)實現(xiàn)這個課題， 正好 提供給我這樣一個研究的機會， 通過對人工智能中博弈方面的研究 （人機對弈）， 讓我在簡單的人機對弈全局設(shè)計， 以及具體到相關(guān)算法上有了深入的了解。 人工 智能屬于計算機科學(xué)的領(lǐng)域， 它以計算機技術(shù)為基礎(chǔ)， 近幾十年來，它的理論和 技術(shù)已經(jīng)日益成熟， 應(yīng)用領(lǐng)域也正在不

10、斷擴(kuò)大， 顯示出強大的生命力。 人工智能 大致可以分成幾個學(xué)科， 它們每一個都是獨特的， 但是它們常常又互相結(jié)合起來 完成設(shè)計任務(wù)， 這時，這些學(xué)科之間的差別就變的很模糊。 人工智能在專家系統(tǒng)， 自然語言理解， 自動定理證明， 自動程序設(shè)計， 人工智能在機器人學(xué)、 模式識別、 物景分析、數(shù)據(jù)庫的智能檢索、機器下棋（實質(zhì)上是博弈論問題）和家用電器智 能化等領(lǐng)域都有廣泛的應(yīng)用。而這個課題就是和人工智能中的博弈論領(lǐng)域緊密相 關(guān)的。這個題目核心是人工智能和 socekt 編程，。并且人工智能中的博弈部分，由于 采用了大量的搜索算法，其中很多被利用到各方面。它的概念、方法和技術(shù)，正 在各行各業(yè)廣泛滲透。

11、 智能已經(jīng)成為當(dāng)今各種新產(chǎn)品、 新裝備的發(fā)展方向。 所以， 趁著這個機會， 對人工智能中比較容易實現(xiàn)的人機4博弈進(jìn)行了解研究學(xué)習(xí)， 也是 很實用且很有必要的。1.3 本課題的研究方法在進(jìn)行游戲設(shè)計之前， 首先決定的第一個問題就是， 使用什么開發(fā)環(huán)境來編寫環(huán) 境 ? 自己雖然比較熟悉 java 語言，但是實際開發(fā)項目經(jīng)驗很少，所以決定用 jcreator, 其擁有高亮語法編輯、使用向?qū)б约巴耆ㄖ频挠脩艚缑?，最主要的?能夠自動查找文件于 main 方法或 html 文件以支持java 小應(yīng)用程序，然后啟 動相應(yīng)的工具。其次確定整個程序的結(jié)構(gòu)框架。由于 applet 運行速度較慢，如果在加上算法

12、搜 索時間，顯然不符合程序的設(shè)計要求，決定用 java 應(yīng)用程序開發(fā) .整個程序的功 能實現(xiàn)流程是這樣的： 網(wǎng)絡(luò)對戰(zhàn)涉及算法較少， 所以先實現(xiàn)網(wǎng)絡(luò)部分， 實現(xiàn)基本 的棋盤和棋子的類，添加判斷勝負(fù)條件，這部是基礎(chǔ)，也是很重要的，電腦 ai 也在這些基礎(chǔ)上添加上來的。這個題目的 2 個功能包括 2 個重要算法，電腦ai和勝負(fù)條件，勝負(fù)條件運算量不大，有固定的模式。難點是人工智能，可以這樣說，人工智能的好壞決定了這個題目的完成深度。所以，大部份時間花在ai 算法的研究和改進(jìn)上， 對于算法我掌握的不多， 研究了一些國內(nèi)的五子棋算法， 參 考了一些游戲設(shè)計算法， 詳細(xì)比較各種算法的優(yōu)缺點， 而且參考了現(xiàn)

13、代五子棋比 賽的各種規(guī)則和技巧，盡量聯(lián)系實際，努力提高電腦 ai。1：黑棋先行，白棋隨后。從天元開始相互順序落子。 2：最先在棋盤的橫向、豎向、斜向形成連續(xù)的相同色五個棋子的一方為勝利。3： 黑棋禁手判負(fù)、 白棋無禁手。 黑棋禁手包括 “三、 三 ”； “四、四 ”；“長連”。黑 方只能用 “四、三 ”去取勝。4：如分不出勝負(fù)，則定位平局。 5：對局中拔子、中途退場均判為負(fù) 6：五連與禁手同時形成，先五為勝。7：黑方禁手形成時，白方應(yīng)立即指出。若白方未發(fā)現(xiàn)或發(fā)現(xiàn)后不立即指正，反 而繼續(xù)落子，則不能判黑方負(fù)。五子棋是由兩個人在一盤棋上進(jìn)行對抗的競技運動。 在對局開始時， 先由執(zhí)黑棋 的一方將一枚

14、棋子的落在 “天元 ”上，然后由執(zhí)白棋的一方在黑棋周圍的交叉點上 落子。如此輪流落子直到某一方首先在棋盤的直線 橫線或斜線上形成連續(xù)的五 子或五子以上， 則該方就算獲勝。 但是五子棋的特點是先行的一方優(yōu)勢很大。 因 此，在職業(yè)比賽種對黑方做了種種限制， 以利公平競爭。 黑白雙5方的勝負(fù)結(jié)果必 須按照職業(yè)五子棋的規(guī)則要求來決定。.1 課題背景 五子棋是起源于中國古代的傳統(tǒng)黑白棋種之一。 現(xiàn)代五子棋日文稱之為連珠， 英 譯為renju ，英文稱之為 gobang 或 fir（five in a row 的縮寫），亦有連五子、五子 連、串珠、五目、五目碰、五格等多種稱謂。五 ava 語言是當(dāng)今最為流

15、行的程序設(shè)計語言之一 作為一門非常優(yōu)秀和極為健壯 的編程語言， 它同時具有的面向?qū)ο?，與平臺無關(guān)，分布式應(yīng)用，安全，穩(wěn)定和 多線程等優(yōu)良的特征，使用 java 語言，不僅可以開發(fā)出功能強大的大型應(yīng)用程 序， 而且 java 語言本身突出的跨平臺的特性也使得它特別適合于 internet 上的 應(yīng)用開發(fā)，可以這樣說， java 的出現(xiàn)使得所開發(fā)的應(yīng)用程序 “一次編寫，處處可 用”的實現(xiàn)成為了可能。1 來隨著計算機的快速發(fā)展，各種各樣的電腦游戲?qū)映霾桓F，使得我們能有更多 的娛樂項目， 而棋類游戲能起到鍛煉人的思維和修身養(yǎng)性的作用，而且棋類游戲 水平頗高， 大有與人腦分庭抗禮之勢。其中戰(zhàn)勝過國際象棋

16、世界冠軍-卡斯帕羅夫的“深藍(lán)”便是最具說服力的代表； 其它像圍棋的 “手淡”、象棋的“將族”等也以其 優(yōu)秀的人工智能深受棋迷喜愛。越.3 本課題的研究方法在 .1.1 規(guī)則及解釋1：黑棋先行，白棋隨后。從天元開始相互順序落子。 2：黑棋禁手判負(fù)、白棋無禁手。黑棋禁手包括 “三、三 ”；“四、四 ”；“長連”。黑 方只能用 “四、三 ”去取勝。4：如分不出勝負(fù)，則定位平局。 5：五連與禁手同時形成，先五為勝。 7：黑方禁手形成時，白方應(yīng)立即指出。若白方未發(fā)現(xiàn)或發(fā)現(xiàn)后不立即指正，反 而繼續(xù)落子，則不能判黑方負(fù)。五子棋是由兩個人在一盤棋上進(jìn)行對抗的競技運動。 在對局開始時， 先由執(zhí)黑棋 的一方將一枚

17、棋子的落在 “天元 ”上，然后由執(zhí)白棋的一方在黑棋周圍的交叉點上 落子。如此輪流落子直到某一方首先在棋盤的直線 橫線或斜線上形成連續(xù)的五 子或五子以上， 則該方就算獲勝。 但是五子棋的特點是先行的一方優(yōu)勢很大。 因 此，在職業(yè)比賽種對黑方做了種種限制， 以利公平競爭。 黑白雙方的勝負(fù)結(jié)果必 須按照職業(yè)五子棋的規(guī)則要求來決定。近來隨著計算機的快速發(fā)展， 各種棋類游戲被紛紛請進(jìn)了電腦， 使得那些喜愛下棋， 又常常 苦于沒有對手的棋迷們能隨時過足棋癮。 而且這類軟件個個水平頗高， 大有與人腦分庭抗禮 之勢。其中戰(zhàn)勝過國際象棋世界冠軍-卡斯帕羅夫的 “深藍(lán) ”便是最具說服力的代表；其它像 圍棋的“手淡

18、”、象棋的 “將族”等也以其優(yōu)秀的人工智能深受棋迷喜愛；而我們今天將向大家 介紹的是五子棋的算法。當(dāng)我們與電腦對戰(zhàn)時， 您知道這些軟件是怎樣象人腦一樣進(jìn)行思考的嗎？前不久我曾編 寫過一個五子棋的游戲，在這里就以此為例和大家一起探討探討?？偟膩碚f（我們假定您熟悉五子棋的基本規(guī)則） ，要讓電腦知道該在哪一點下子，就要 根據(jù)盤面的形勢，為每一可能落子的點計算其重要程度，也就是當(dāng)這子落下后會形成什么棋 型（如：“沖四 ”、“活三 ”等），然后通覽全盤選出最重要的一點，這便是最基本的算法。當(dāng) 然，僅靠當(dāng)前盤面進(jìn)行判斷是遠(yuǎn)遠(yuǎn)不夠的， 這樣下棋很容易掉進(jìn)玩家設(shè)下的陷阱， 因為它沒 有考慮以后的變化。 所以在

19、此基礎(chǔ)上我們加入遞歸調(diào)用，即：在電腦中預(yù)測出今后幾步的各 種走法，以便作出最佳選擇，這也是我們下棋時常說的 “想了幾步 ”。如此一來您的程序便具 有一定的水平了。什么？不信！過來試試吧！總體思路弄清之后，下面進(jìn)行具體討論： 一：數(shù)據(jù)結(jié)構(gòu) 先來看看數(shù)據(jù)結(jié)構(gòu)，我們需要哪些變量？ 首先得為整個棋盤建立一張表格用以記錄棋子信息，我們使用一個15*15的二維數(shù) 組Table1515 （15*15是五子棋棋盤的大?。瑪?shù)組的每一個元素對應(yīng)棋盤上的一個交 叉點，用 0表示空位、 1代表己方的子、 2代表對方的子；這張表也是今后分析的基礎(chǔ)。在此 之后還要 為電腦和玩家雙方 各建立一張棋型 表Computer1

20、5154和Player15154，用6來存放棋型數(shù)據(jù)，就是剛才所說的重要程度，比如用20代表 “沖四”的點，用15代表“活三”的點，那么在計算重要性時， 就可以根據(jù)20 15得出前者比后者重要，下子時電腦便會自動選擇 “沖四 ”的點。那為什么棋型表要使用三維數(shù)組呢？因為棋盤上的每 一個點都可以與橫、豎、左斜、右斜四個方向的棋子構(gòu)成不同的棋型，所以一個點總共有4個記錄；這樣做的另一個好處是可以輕易判斷出復(fù)合棋型，例如：如果同一點上有2個 15就是雙三、有一個 15和一個 20就是四三。怎么樣！3個數(shù)組構(gòu)成了程序的基本數(shù)據(jù)骨架，今后只要再加入一些輔助變量便可以應(yīng) 付自如了。應(yīng)該不會太難吧？OK！有

21、了這么多有用的數(shù)據(jù)，我們就可以深入到程序的流程 中去了。二：程序流程 我們主要討論五子棋的核心算法，即：人工智能部分，而其他像圖形顯示、鍵盤鼠標(biāo)控 制等，因較為簡單，所以就不作過多介紹了。首先，請仔細(xì)閱讀圖1：我們看到本程序由六個基本功能模塊構(gòu)成，各模塊的詳細(xì)分析如下：（1）初始化： 首先，建立盤面數(shù)組Table1515、對戰(zhàn)雙方的棋型表Computer15154和Player15154并將它們清零以備使用；然后初始化顯示器、鍵盤、鼠等輸入輸出設(shè)備 并在屏幕上畫出棋盤。（2）主循環(huán)控制模塊：控制下棋順序，當(dāng)輪到某方下子時，負(fù)責(zé)將程序轉(zhuǎn)到相應(yīng)的模 塊中去，主要擔(dān)當(dāng)一個調(diào)度者的角色。（3）玩家下子

22、：當(dāng)輪到玩家下時，您通過鍵盤或鼠標(biāo)在棋盤上落子，程序會根據(jù)該點 的位置，在Table1515數(shù)組的相應(yīng)地方記錄 2，以表明該子是玩家下的。（4）盤面分析填寫棋型表：本程序核心模塊之一，人工智能算法的根本依據(jù)！其具體 實現(xiàn)方法如下：您在下五子棋時，一定會先根據(jù)棋盤上的情況，找出當(dāng)前最重要的一些點位，如“活三 ”、“沖四 ”等；然后再在其中選擇落子點。 但是， 電腦不會像人一樣分析問題， 要讓 它知道哪是 “活三”、 哪是 “沖四”，就得在棋盤上逐點計算，一步一步的教它。先來分析己方的棋型，我們從棋盤左上角出發(fā)，向右逐行搜索，當(dāng)遇到一個空白點時，以它為中心向左挨個查找， 如果遇到己方的子則記錄然后繼續(xù)， 如果遇到對方的子、 空白點 或邊界就停止查找。左邊完成后再向右進(jìn)行同樣的操作；最后把左右兩邊的記錄合并起來， 得到的數(shù)據(jù)就是該點橫向上的棋型，然后把棋型的編號填入到Computerxyn中就行了 （x、y代表坐標(biāo)，n=0、1、2、3分別代表橫、豎、左斜、右斜四個方向） 。而其他三個方 向的棋型也可用同樣的方法得到， 當(dāng)搜索完整張棋盤后， 己方棋型表也就填寫完畢了。 然后 再用同樣的方法填寫對方棋型表。注意：所有棋型的編號都要事先定義好，越重要的號數(shù)越大！OK!怎么樣？有點累了吧？不過千萬別泄氣！因為