基于HTML的五子棋AI大戰(zhàn)游戲摘要HTML5技術的發(fā)展推動了游戲行業(yè)的蓬勃發(fā)展。HTML5的五子棋游戲是一款休閑類別的棋類網頁游戲,該游戲利用了Canvas技術完成了游戲主界面的開發(fā)，再利用Canvas組件進行棋盤和棋子的繪制,最后通過JavaScript腳本語言實現(xiàn)登錄檢驗和電腦AI算法以及游戲內部邏輯實現(xiàn)。由于HTML5的跨平臺性,使得該游戲能夠方便快捷的在瀏覽器上直接運行,并且與各種瀏覽器都達到完美的兼容效果。關鍵詞游戲;五子棋;HTML5;CanvasHTML-BASEDGOBANGMAN-MACHINEWARGAMEABSTRCTThenewstandardsandtechnologiesofHTML5havedriventhedevelopmentofweb-basedcasualgames.HTML5-basedGomokuisacasualchessgamethatusesHTML5'slatestCanvastechnologytocreateanddevelopgamepages.Firstly,thematerialeditingandgameUIinterfacedesigninthedrawingsoftware,andthenuseHTML5andCSS3torealizethegeneralframeandlayoutstyleofthewholepageofthegame,thenusetheCanvascomponenttodrawtheboardandthechesspiece,andfinallyrealizethecomputerAIthroughtheJavaScriptscriptlanguage.Algorithmandgameinternallogicimplementation.Thankstothecross-platformuseofHTML5,thegamecanberundirectlyandeasilyonthebrowser,andiscompatiblewithallkindsofbrowsers.KEYWOEDSgame;Gobang;HTML5;Canvas目錄中文摘要 =1\*romanⅠ英文摘要 Ⅱ1緒論 1HYPERLINK\l"_Toc5341_WPSOffice_Level2"1.1課題研究背景 1HYPERLINK\l"_Toc23920_WPSOffice_Level2"1.2國內外研究現(xiàn)狀 1HYPERLINK\l"_Toc15272_WPSOffice_Level2"1.3研究的目的和意義 1HYPERLINK\l"_Toc5341_WPSOffice_Level1"2開發(fā)相關技術簡介 2HYPERLINK\l"_Toc7043_WPSOffice_Level2"2.1開發(fā)介紹 2HYPERLINK\l"_Toc5341_WPSOffice_Level3"2.1.1SublimeText3 2HYPERLINK\l"_Toc13790_WPSOffice_Level3"2.1.2ChromDevTools 2HYPERLINK\l"_Toc29797_WPSOffice_Level2"2.2主要技術 3HYPERLINK\l"_Toc23920_WPSOffice_Level3"2.2.1HTML、CSS 3HYPERLINK\l"_Toc15272_WPSOffice_Level3"2.2.2JavaScipt技術 3HYPERLINK\l"_Toc1058_WPSOffice_Level3"2.2.3Canvas簡介 42.3博弈算法簡介 4HYPERLINK\l"_Toc13790_WPSOffice_Level1"3需求分析 5HYPERLINK\l"_Toc30811_WPSOffice_Level2"3.1總體分析 53.2功能分析 5HYPERLINK\l"_Toc15770_WPSOffice_Level2"3.3可行性分析 5HYPERLINK\l"_Toc23920_WPSOffice_Level1"4系統(tǒng)功能設計 6HYPERLINK\l"_Toc2986_WPSOffice_Level2"4.1系統(tǒng)功能模塊設計 6HYPERLINK\l"_Toc1968_WPSOffice_Level2"4.2游戲通信協(xié)議設計 7HYPERLINK\l"_Toc1968_WPSOffice_Level2"4.3游戲服務器設計 7HYPERLINK\l"_Toc1968_WPSOffice_Level2"4.4網絡游戲功能設計 8HYPERLINK\l"_Toc15272_WPSOffice_Level1"5系統(tǒng)功能實現(xiàn) 9HYPERLINK\l"_Toc1968_WPSOffice_Level2"5.1前端界面功能 9HYPERLINK\l"_Toc1968_WPSOffice_Level2"5.2前端主界面功能 9HYPERLINK\l"_Toc5244_WPSOffice_Level3"5.2.1初始化棋盤 10HYPERLINK\l"_Toc5244_WPSOffice_Level3"5.2.2畫棋盤格 10HYPERLINK\l"_Toc5244_WPSOffice_Level3"5.2.3AI實現(xiàn)-極大極小值搜索算法 11HYPERLINK\l"_Toc5244_WPSOffice_Level3"5.2.4評估函數(shù) 12HYPERLINK\l"_Toc5244_WPSOffice_Level3"5.2.5Alpha-Beta剪枝算法 13HYPERLINK\l"_Toc5244_WPSOffice_Level3"5.2.6判斷游戲勝負 146游戲功能測試 156.1測試概要 156.1.1測試方案 156.1.2測試安排和進度 156.2測試結果及其發(fā)現(xiàn) 156.2.1Bug清單 166.3分析摘要 166.3.1軟件能力 166.3.2缺陷和限制 166.4測試結論 167HYPERLINK\l"_Toc1058_WPSOffice_Level1"總結與展望 17HYPERLINK\l"_Toc7043_WPSOffice_Level1"參考文獻 18致謝 191.緒論1.1課題研究背景五子棋是一種大眾化且比較容易上手的游戲，隨著計算機網絡技術的不斷發(fā)展，各類玩家在線對戰(zhàn)游戲如雨后春筍般不斷冒出，其中就包括五子棋類游戲。五子棋不僅能夠改善思維敏捷能力、還能開發(fā)人腦智力、手腦并用，而且蘊含哲理。游戲也逐漸從最開始的僅文字圖片游戲向如今的3D游戲發(fā)展。但是休閑類游戲仍占據著游戲市場的一席之地。而且如今有人不斷研究電腦算法，使得機器算法能與人腦對抗。其中IBM“深藍”與戰(zhàn)勝過圍棋世界冠軍柯潔的谷歌“AlphoGo”便是最具有說服力的代表。1.2國內外研究現(xiàn)狀隨著計算機網絡通信的發(fā)展，游戲產業(yè)成為了一個香饃饃。游戲文娛產業(yè)的發(fā)展讓人們得到了一種新的體驗，現(xiàn)如今游戲產業(yè)規(guī)模已達幾千億美元，國內外制作的精良游戲不勝枚舉，類似王者榮耀這種現(xiàn)象級手游，更是成為手游的代表作，游戲不僅豐富了人們的空余生活，還催生了一個巨大產業(yè)鏈。1.3研究的意義和目的本游戲重點研究實現(xiàn)電腦算法方面，研究將人工智能算法運用到五子棋的開發(fā)中去，與玩家進行人機博弈。而且五子棋的游戲規(guī)則單一，頁面的繪制也比較容易，這樣我們就可以重點研究高效率的人機算法，實現(xiàn)人機對抗，并且分設幾個不同批次的難度。希望這次通過本次畢設，結合前端技術和數(shù)據結構與算法，完成該畢業(yè)設計，從而對軟件開發(fā)的大體步驟與框架有一個全新的認識。12開發(fā)相關技術簡介2.1開發(fā)介紹本次開發(fā)項目前端界面大部分采用HTML、CSS來編寫，游戲內部的邏輯及人機博弈的用JavaScript來實現(xiàn)。且采用B/S架構，即瀏覽器與后臺服務器交互，項目通過瀏覽器的解釋，展現(xiàn)出游戲的大體界面。2.1．1SublimeText3簡介SublimeText3是一個文本代碼編輯器，其高效的性能成為了網頁開發(fā)者必不可少的工具之一SublimeText它最開始被設計為一個具有豐富擴展功能的Vim文本編輯器。SublimeText3具有優(yōu)美的用操作戶界面和強大豐富的擴展功能庫，例如代碼縮略圖，Python的插件，包管理工具，代碼段等，還可自定義鍵綁定，菜單和工具欄。SublimeText3還支持多平臺運行。SublimeText支持多種布局格式和代碼的縮略圖，其右側具有文件略縮圖和滑動條，可以方便地觀察當前窗口所屬區(qū)域。還具有按f11進入全屏免打擾模式功能。在屏幕比較大或需要同時編輯多個文件時效率特別高，一鍵進入全屏免打擾模式更是開發(fā)者的福音。SublimeText3支持文件夾直接瀏覽，可以打開文件夾，在左側會有導航欄類似于一般IDE的文件資源管理目錄，方便同時處理多個文件。SublimeText支持多位置同時編輯相同區(qū)域，只需要按住鍵盤ctrl鍵，就可以同時選擇多個位置，同時操作，提高開發(fā)效率。SublimeText3具有自動恢復上次編輯區(qū)域，比如說在上次修改文件，但忘記了保存，這個時候意外退出軟件，該軟件不會直接詢問用戶是否需要保存，等到下次啟動軟件，文檔之前的編輯狀態(tài)都會恢復。2.1.2ChromeDevTools簡介ChromeDevTools,是一種可以實時調試代碼并且內嵌在谷歌瀏覽器內部的開發(fā)者工具。DevTools可以高效的跟蹤CSS布局,設置JavaScript斷點debug調試其腳本,以及進行javascript代碼的優(yōu)化。DevTools具有檢查和實時更新頁面的功能，可以在Elements面板中檢查和實時編輯DOM容器中的任何元素。強大的Console功能，打印日志、執(zhí)行測試代碼、測量和統(tǒng)計執(zhí)行和異常報錯處理。方便好用的Network功能，可以記錄并分析所有的網絡請求、測試網絡的性能和查看加載事件等等。2.2主要技術2HTML、CSS簡介HTML是一種超文本標記語言。是一種網頁內容載體，內容就是網頁開發(fā)者寫在網頁頁面上，想讓用戶瀏覽的信息資源，可以囊括文字、圖片、超鏈接，視頻資源等。CSS樣式是網頁的外觀表現(xiàn)。就像網頁的外衣一樣。比如，標題字體大小的樣式、顏色的變化，或為頁面插入背景圖片、邊框等，這些稱之為外觀表現(xiàn)。稱為超文本標記語言，是因為一個網頁可以同時對應多個HTML文件，并且網頁文件一般以.htm為擴展名或者.html。網頁開發(fā)者可以使用任何能夠生成文本類型資源文件的編輯器來產生超文本標記語言文件，只需要在退出文件時，修改該文件名的后綴名即可。標準超文本標記語言文件類型都具有規(guī)范的整體文本結構，而且標記一般都是成對出現(xiàn)（br標簽除外），即超文本標記語言文件的開頭與結尾標志和超文本標記語言的head與body兩大部分。JavaScript簡介JavaScript是一種腳本解釋型語言，是一種動態(tài)的基于原型的語言，廣泛應用于客戶端，最早是被應用在靜態(tài)頁面上，用來給HTML網頁增加動態(tài)式的功能。為了取得技術領先，微軟推出了JScript，與JavaScript一樣可以方便的在瀏覽器上面直接運行和調試。后來開發(fā)者統(tǒng)一了其標準，JavaScript兼容于ECMA標準，因此也稱為ECMAScript。JavaScript被常常用于網頁應用開發(fā)。其增添了動態(tài)功能，提供各式各樣的網頁頁面。JavaScript一般是寫在html文件中就可以實現(xiàn)開發(fā)者需要的功能。同其它語言一樣，其有自身的基本數(shù)據類型，表達式和算術以及邏輯運算符及程序的基本流程邏輯和對應的數(shù)據結構。Javascript有四種基本數(shù)據類型用來處理數(shù)據和文字。其具有以下特點：原生、基于對象、便捷、動態(tài)性以及跨平臺性。JS主要作為本地腳本直接在用戶的瀏覽器上運行，所以不需要服務器的支持。而隨著服務器性能的發(fā)展，雖然開發(fā)者更喜歡運行于服務器端的腳本以保證安全，但JavaScript仍然憑借其跨平臺、易上手等優(yōu)勢領先與其他語言。而例如ajax還可以在一個靜態(tài)頁面上，動態(tài)得生成不同的頁面。Canvas簡介canvas是HTML5新標準出來之后提供的一種新標簽。在新標準出來之前，網頁頁面只有一些比較簡單的標簽，比如<p>、<h2>。但有了canvas技術后,Web頁面開始變得豐富多彩起來。Canvas可通過JS腳本來繪圖。還能實現(xiàn)立體圖的渲染和系統(tǒng)的優(yōu)化。canvas主要應用的領域：游戲和動畫。本次設計就是應用Canvas功能繪制游戲界面。還可用于廣告頁面的動態(tài)開發(fā)，發(fā)揮巨大的作用。還可以直接嵌入網站的內容：類似圖表echarts、音視頻、可以直接與Web融合，不需要任何的插件，直接內嵌在JS中即可達到想要的效果。博弈樹搜索算法簡介五子棋游戲，是黑白雙方輪流下子。就產生了不同的棋盤局面，不同的應對方法。比如說黑方先下子，白方就總共有224種落子的方法，如果黑方選擇了其中的一步來應對，那么白方就有223種方案和223種局面來應對下一步。這樣來看，就產生樂一個又一個的樹。3博弈樹搜索算法可以完全不需要顧及具體是什么博弈事件，只需要在算法的層面上進行研究。電腦算法是否準確我們需要借助與估值函數(shù)，奕會影響搜索算法的準確性。在整個搜索算法過程中，該函數(shù)需要不斷的，反復的被系統(tǒng)驗證，確定合理的值。43需求分析3.1總體分析本次畢業(yè)設計是需要開發(fā)出一個帶有電腦智能算法和網絡對戰(zhàn)功能的五子棋游戲，能夠在網絡上運行。五子棋電腦算法是本游戲的核心關鍵所在，應當實現(xiàn)市場上大部分同款游戲所具備的功能，例如悔棋、選擇游戲難度、開始下棋、匹配玩家、保存棋局最后頁面等。玩家對戰(zhàn)：選擇和玩家對弈操作，需要雙發(fā)同時確認才能開始游戲，也可以執(zhí)行悔棋功能，但是需要對方玩家的同意，而且需要說明黑先白后，玩家可以申請先手。并在游戲結束一方獲勝后，可查看最后勝利或者失敗的畫面。3.2功能分析（1）介紹游戲的規(guī)則：對局雙方各手執(zhí)一色棋子，空棋盤開局。先后順序為黑先、白后，雙方交替下子，而且每次只能下一子。棋子落在棋盤的橫線交叉的空白點上，棋子下定一個位置后，不得向其它點移動，奕不得從棋盤上拿掉或拿起另落他處。黑方的第一枚棋子必須下在棋盤正中央俗稱“天元”位置上。每回合輪流下子是雙方的權利，但奕不允許任何一方放棄落子權。（2）選擇對戰(zhàn)模式：游戲分為人機對戰(zhàn)和玩家對戰(zhàn)。兩種游戲模式都具有悔棋與查看最后輸贏畫面。（3）用戶注冊：注冊為玩家才可以登錄游戲，需要填寫基本注冊信息，系統(tǒng)會自動識別驗證信息填寫的規(guī)范，注冊完登錄后就可以選擇游戲對戰(zhàn)模式以及電腦AI的難度。（4）用戶登錄：玩家注冊完成后，回到頁面填寫賬號密碼，游戲將根據玩家的賬號ID以及登記自動匹配對手。3.3可行性分析技術層面：運用windows7及以上操作系統(tǒng)，以谷歌瀏覽器為用戶的主要操作平臺，開發(fā)出一款界面優(yōu)美、功能齊全的五子棋人機/雙人對戰(zhàn)游戲。經濟層面：系統(tǒng)的開發(fā)成本比較低廉，已經有的PC機就可完成開發(fā)所需的條件。操作層面：操作主要是鼠標與鍵盤搭配使用，主要憑借鼠標來確定棋子下落的位置，操作簡單明了，只需要明白游戲規(guī)則以及其他的快捷鍵即可。54系統(tǒng)詳細設計4.1系統(tǒng)功能模塊設計如今現(xiàn)有的網絡編程模式主要分成兩類：一種是基于客戶端/服務器模式，另一種是瀏覽器/服務器模式；C/S（客戶端/服務器）程序具有比較好的系統(tǒng)交互性，功能強大，但是必須要安裝平臺軟件； B/S（瀏覽器/服務器）模式下要求客戶端可以直接在瀏覽器下運行。但是必須具有一定的響應速度和安全限制，所以其交互性與功能有一些限制。五子棋系統(tǒng)的交互性要求較高，所以本系統(tǒng)選用了在 B/S模式進行實現(xiàn)。本程序中提供兩種游戲模式：玩家電腦對戰(zhàn)模式和玩家對戰(zhàn)模式。游戲開始之前，可以選擇先手確認，與電腦一決高下。在玩家對戰(zhàn)中，可以通過先手請求來確認是黑棋先還是白棋先，同時設有悔棋功能。如果沒有啟動的話，玩家是無法直接進行游戲的。如果使用計算機自動完成，那么就直接用批處理方式；信息的存儲使用的是傳統(tǒng)的文件系統(tǒng)，因為不需要儲存玩家的具體信息，只需要保留對局雙方的棋局信息即可。并且增加悔棋，美化界面，實現(xiàn)觀看電腦與電腦之間的對戰(zhàn)等功能。4.2游戲通信設計協(xié)議因為是PC線上玩的游戲，通信模式就是瀏覽器發(fā)起網絡請求，然后服務器方面響應并回復請求。避免了網絡信號不好時，玩家掉線的情況。該游戲沒有設計固定的用戶，采用的方法是游戲每次都會向服務器申請一個游戲ID，使用這個游戲ID在互聯(lián)網上和其他用戶進行對戰(zhàn)。于是報文協(xié)議設計了兩種模式：普通請求/回復報文gamequest、游戲數(shù)據報文nextquest。關于游戲請求與游戲對局時的通信，因為采用的是請求加回復的方式，服務器不能主動通知瀏覽器有新的游戲開始或是對手已經下了下一步棋，因此需要客戶端主動向服務器獲取相應的信息。于是這部分被設計為瀏覽器端定時向服務器發(fā)送更新數(shù)據的請求，服務器一旦接收到了請求，就把通過該請求的TCP連接發(fā)回去。這樣雖然增加了網絡的流量，但為了數(shù)據的穩(wěn)定性必須做出一定的犧牲。4.3游戲服務器設計這是網絡游戲最重要也是最核心的一部分。一個高效、并且穩(wěn)定的游戲服務器程序直接決定了該游戲的體驗。在實際的游戲服務器開發(fā)中，游戲內部的邏輯與網絡通信邏輯可能由不同的人員分工合作進行開發(fā)。因此，游戲邏輯與網絡通信邏輯應在保證效率的情況下實現(xiàn)盡可能的低耦合。游戲的邏輯與網絡通信需要盡可能地獨立，就我們五子棋服務器而言，網絡通信端使用PPC、epoll，并且都和游戲邏輯無關，只要能接收分類，并交給游戲進行邏輯處理，并將游戲邏輯處理好的數(shù)據發(fā)出即可。關于服務器的游戲邏輯，首先我們要明白服務器要做哪些事情：1、用戶游戲ID的申請與管理2、對局數(shù)據的處理與管理6大致就以上這兩種事情。但是因為游戲的客戶端數(shù)量很多，不同的瀏玩家之間進行對局，必須要清晰地處理與管理這些數(shù)據。我這里建立了一個GameIdPool，用于游戲id的儲存與申請，以防發(fā)生錯誤，給用戶分配了無效或者是重復的id。對局數(shù)據的處理與管理：在兩個用戶都分配到id的情況下，雙方都能申請進行游戲。這時服務端做的就是匹配好這些用戶，并通知這些用戶已經可以開始游戲。由于篇幅的原因，我就省略了服務器的代碼。大致說一下各種函數(shù)的用途。PlayerToPlayer:它的作用就是用來匹配玩家。當有用戶客戶端申請玩家對戰(zhàn)進行游戲時，服務器會先調用相應的匹配函數(shù)來尋找可以進行匹配的另一個玩家，如果找到了合適的玩家，接下來就會調用SetPTP來檢查這兩個玩家是否有對局關系。如果沒有匹配到相應的玩家，則會調用setwait函數(shù)來繼續(xù)等待其他的用戶進行匹配。該函數(shù)使用的數(shù)據結構為簡單的hash映射。SetPlayerStatues:用于存放玩家的對局數(shù)據，使用pool方式，本地下棋的信息將會儲存在這里，用以客戶端得到對方的落棋信息。PlayerTPlayer的info會直接映射到pool的對應下標。不同id的瀏覽器查找數(shù)據會相當?shù)匮杆佟?.4網絡游戲功能設計現(xiàn)在我們回到游戲的客戶端（瀏覽器）上，前面已經實現(xiàn)了單機游戲的設計?，F(xiàn)在要做的就是加入網絡功能，其實就是把單機部分的AI接到服務器上。首先是游戲id數(shù)值的獲取。我們先向服務器發(fā)送一個GetId的網絡請求，然后就會得到服務器分配的id數(shù)值。然后瀏覽器就會將這個id當成自己的游戲id，直到告知服務器玩家退出游戲，或者是服務器在長時間沒有得到該id的情況下自動釋放前都是有效的。當客戶端分配到該id數(shù)字后，就可以向服務器發(fā)起游戲匹配請求GetNewGame。為了防止系統(tǒng)匹配不到玩家這種情況發(fā)生，設置發(fā)送匹配的網絡請求最多會維持一分鐘，在這一分鐘結束后，瀏覽器便會向服務器發(fā)出停止匹配的請求。當同時有兩個客戶端在這段交叉時間進行匹配，便能夠匹配在一起進行游戲。游戲匹配成功后，瀏覽器端將會收到服務器發(fā)過來的對局基本信息，其中囊括了了對手id、玩家1，2是否申請先手還是后手。等到游戲開始后，先手先下棋然后將數(shù)據提交到服務器，由后手來更新數(shù)據，按照這樣依次循環(huán)下去直到達成游戲勝利條件，游戲就會結束。75系統(tǒng)界面實現(xiàn)5.1前端界面功能前端界面主要的功能是：游戲說明、單人模式、雙人模式。（圖5-1）圖5-1功能演示5.2前端主界面模塊界面在整個游戲界面起著很大的作用，它將直接影響到玩家對游戲界面美觀的評價。界面是整個人機交互（玩家對戰(zhàn)）的平臺，所以在設計時盡量往用戶友好方向考慮。提供一個操作簡便和友好界面。以下是下棋對戰(zhàn)使用的界面，還有很多地方需要改進和操作的功能需要完善。但是總體來說已經基本能夠滿足游戲的需要。擁有較為良好的交互功能。如圖5-2所示。8圖5-2下棋界面5.2.2初始化棋盤function InitializeGobangBoard(){//初始化棋盤函數(shù)代碼，表示將用來處理Paint的Control事件的方法。gobangBoardGroupBox.Paint+= newPaintEventHandler (gobangBoardGroupBox_Paint);Var x,y;for (x=0;x<15;x++)for (y=0;y<15;y++){//初始化棋盤界面，每次開始時調用5.2.3畫棋盤格functiongobangBoardGroup_Paint(objectsender,PaintEventArgs e){Var i;//獲得畫筆Graphicsgr=e.Graphics;PenmyPen= newPen(Color.Black,2);SolidBrush brush= newSolidBrush(Color.Red);for (i=0;i<15;i++){//繪制棋盤gr.DrawLine(myPen,30+i*40,30,30+i*40,590);gr.DrawLine(myPen,30,30+i*40,590,30+i*409}圖5-3畫棋盤格5.2.4AI實現(xiàn)-極大極小值搜索算法五子棋看起來有各式各樣的走法，但是實際上把所有走法一步一步的展開，就是一棵巨大的博弈樹結構。在這個樹中，從根節(jié)點為0開始，奇數(shù)層表示電腦的所有可能的走法，偶數(shù)層則表示玩家所有可能的走法。假設電腦先手落子，那么第一層就是電腦的所有可能的走法，第二層就是玩家的所有可能走法，以此類推。我們首先假設平均每一步有50種可能的走法（首先不考慮優(yōu)化），那么從根節(jié)點開始，往下面每一層的節(jié)點的數(shù)量就是上一層的50倍，假設我們只進行4層的往下思考，也就是電腦和玩家隨機各走兩步，那么這顆博弈樹的葉子節(jié)點數(shù)為50^4=625萬個。我們先不考慮這么多個節(jié)點要多久能計算出來。首先可以用遞歸來遍歷這一棵樹。而且我們需要一個評估函數(shù)對當前整個局勢作出評估，返回一個得分數(shù)。我們規(guī)定對電腦越有利，這個分數(shù)就越大，對玩家越有利，這個分數(shù)就越小，分數(shù)的起點是從0開始。我們遍歷這顆博弈樹的時候，就很明顯可以看出具體如何選擇分支了：電腦走棋的層我們稱之為MAX層，這一層電腦要保證自己利益最大化，那么就需要選擇得分數(shù)最高的節(jié)點。玩家走棋的層我們稱之為MIN層，這一層玩家要保證自己的利益最大化，那么就會選擇得分數(shù)最低的節(jié)點。這也就是極大極小值搜索算法的名稱由來。這是維基百科上的一張圖5-4：10圖5-4極大極小搜索算法此圖中我們假設甲是電腦，乙是玩家，那么在甲層的時候，總是選其中值最大的節(jié)點，乙層的時候，總是選擇其中最小的節(jié)點。而每一個節(jié)點的分數(shù)，都是由其孩子節(jié)點決定的，因此我們對博弈樹只能進行深度優(yōu)先搜索（DFS）而無法進行廣度優(yōu)先搜索。深度優(yōu)先搜索用遞歸非常容易實現(xiàn)，然后剩下的主要工作其實是完成一個評估函數(shù)和對該搜索算法進行一定的優(yōu)化，這個函數(shù)需要對當前局勢給出一個比較準確的評分。五子棋是一個15×15的棋盤，因為棋盤大小是不會變動的，所以目前來看用15×15的二維靜態(tài)數(shù)組來存儲，效果是最好的。極小化極大值搜索算法，正常需要兩個函數(shù)，一個搜索極小值，一個搜索極大值。因為其實大部分邏輯是一樣的，完全可以把這兩個函數(shù)合并成一個。然后把對手的分數(shù)變成負的，就是我方的分數(shù)。這種實現(xiàn)就是負極大值搜索。代碼如下：varr=function(deep,alpha,beta,role,step,steps,spread){var_e=board.evaluate(role)varleaf={score:_e,step:step,returnleaf}varbest={score:MIN,step:step,steps:steps}//雙方個下兩個子之后，開啟starspread模式//省略剪枝代碼}115.2.5評估函數(shù)有了搜索策略，我們還需要進行局勢的評估。我們簡單的用一個整數(shù)表示當前局勢，分數(shù)越大，則自己優(yōu)勢越大，分數(shù)越小，則對方優(yōu)勢越大，分數(shù)為0是表示雙方局勢相當。它接受一個角色，因為分數(shù)是相對角色而言的，返回一個整型數(shù)。比如如果對電腦是1000分，那么同樣的局勢對人類棋手就會返回-1000分。我們對五子棋的評分是簡單的把棋盤上的各種連子的分值加起來得到的，對各種連子的基本評分規(guī)則如下：·連五，100000·活四,10000·活三1000·活二100·活一10如果一側被封死但是另一側沒有，則評分降一個檔次，也就是死四和活三是相同的分·死四,1000·死三100·死二10按照這個規(guī)則把棋盤上電腦的所有棋子打分，之和即為電腦的單方面得分scoreComputer，然后對玩家的棋子同樣打分得到scoreHuma。scoreHuman即為當前局勢的總分數(shù)。那么如何找出所有的連子呢，目前我的方式是遍歷數(shù)組，一個個的數(shù)。因為代碼量比較大，在這里我不會貼出代碼，他就是對單個點進行評分的模塊。5.2.6AlphaBeta剪枝算法可以做一個簡單的計算，平均一步考慮50種可能性的話，思考到第四層，那么搜索的節(jié)點數(shù)就是50^4=6250000，在我的電腦上一秒鐘能計算的節(jié)點不超過5W個，那么625W個節(jié)點需要的時間在100秒以上。電腦一步思考100秒肯定是不能接受的，實際上最好一步能控制在5秒以內。AlphaBeta剪枝算法是一種安全的剪枝策略，也就是不會對棋力產生任何負面影響。它的基本依據是：棋手不會做出對自己不利的選擇。依據這個前提，如果一個節(jié)點明顯是不利于自己的節(jié)點，那么就可以直接剪掉這個節(jié)點。前面講到過，AI會在MAX層選擇最大節(jié)點，而玩家會在MIN層選擇最小節(jié)點。那么如下兩種情況就是分別對雙方不利的選擇：1.在MAX層，假設當前層已經搜索到一個最大值X，如果發(fā)現(xiàn)下一個節(jié)點的下一層（也就是MIN層）會產生一個比X還小的值，那么就直接剪掉此節(jié)點。解釋一下，也就是在MAX層的時候會把當前層已經搜索到的最大值X存起來，如果下一個節(jié)點的下一層會產生一個比X還小的值Y，那么之前說過玩家總是會選擇最小值的。也就是說這個節(jié)點玩家的分數(shù)不會超過Y，那么這個節(jié)點顯然沒有必要進行計算了。通俗點來講就是，AI發(fā)現(xiàn)這一步是對玩家更有利的，那么當然不會走這一步。2.在MIN層，假設當前層已經搜索到一個最小值Y，如果發(fā)現(xiàn)下一個節(jié)點的下一層（也就是MAX層）會產生一個比Y還大的值，那么就直接剪掉此節(jié)點。如圖5-5所示。12圖5-5剪枝算法示意圖如上圖所示，在第二層，也就是MIN層，當計算到第二層第三個節(jié)點的時候，已知前面有一個3和一個6，最大值至少是6。在計算第三個節(jié)點的時候，發(fā)現(xiàn)它的第一個孩子的結果是5，因為當前是MIN節(jié)點，會選擇孩子中的最小值，所以此節(jié)點值不會大于5。而第二層已經有一個6了，第二層第三個節(jié)點肯定不會被選擇。因此此節(jié)點的后序孩子就沒有必要計算了。這是MAX節(jié)點的剪枝，MIN節(jié)點的剪枝也是同樣的道理，就不再講了。AlphaBeta剪枝的Alpha和Beta分別指的是MAX和MIN節(jié)點。代碼實現(xiàn)如下。varr=function(deep,alpha,beta,role,step,steps,spread){//對max和min函數(shù)都增加一個alpha和beta參數(shù)。//在max函數(shù)中如果發(fā)現(xiàn)一個子節(jié)點的值大于alpha，則不再計算后序節(jié)點，此為Alpha剪枝。//在min函數(shù)中如果發(fā)現(xiàn)一個子節(jié)點的值小于beta，則不再計算后序節(jié)點，此為Beta剪枝。var_e=board.evaluate(role)varleaf={score:_e,step:step,steps:steps}returnleaf}varbest={score:MIN,step:step,steps:steps}//雙方個下兩個子之后，開啟starspread模式按照wiki上的說法，最大優(yōu)化效果應該達到1/2次方。也就是如果你本來需要計算10000個節(jié)點，那么最好的效果是，你只需要計算100個點就夠了。13這是建立在所有的節(jié)點排序都是完美的假設上的。因為我們不可能完美排序，所以我們的優(yōu)化效果達不到那么好。但是依然可以達到約3/4次方的優(yōu)化效果。5.2.7判斷游戲勝負五子棋游戲的勝負，是要判斷棋盤上是否有這樣一個點，從這個點為中心的橫、豎、左斜和右斜四個方向是否有連續(xù)的五個同色棋子出現(xiàn)，則為游戲勝利。具體代碼如下。functionCheckWin( int color ){var x, y;// 判斷橫向for ( y = 0; y < 15; y++ ){for ( x = 0; x < 11; x++ ){ if ( color == m_data[x][y] && color == m_data[x + 1][y] &&color == m_data[x + 2][y] &&color == m_data[x + 3][y] &&color == m_data[x + 4][y] ) { return TRUE;}}}}// 不滿足勝利條件return FALSE;}由于這個算法所遵循的搜索順序是從左到右、自上而下，因此在每次循環(huán)的時候，都有一些坐標無需納入考慮范圍。例如對于橫向判斷而言，由于右邊界所限，因而所有橫坐標大于等于11的點，都構不成達到五子連珠的條件，所以橫坐標的循環(huán)上界也就定為11，這樣也就提高了搜索的速度。146功能測試6.1測試概要6.1.1測試方案1.測試方法：黑盒測試2.測試內容：測試“新游戲”，“退出”，“選項”，“選擇難度”這幾個功能的實現(xiàn)和正確性。3.測試用例設計方法：基于具體場景設計測試用例6.1.2測試安排和進度（表6-1）表6-1測試項計劃開始時間計劃結束時間新游戲2019.3.302019.3.31選項（AI先手）2019.4.12019.4.2選項（玩家先手）2019.4.22019.4.3選項（玩家對戰(zhàn)）2019.4.42019.4.5選擇難度2019.4.102019.4.11退出2019.4.1220測試結果及其發(fā)現(xiàn)邊緣落子測試結果如圖所示（圖6-1）圖6-1測試邊緣落子圖6-2電腦先手落子152.1BUG清單表6-2bug清單Bug編號測試用例編號錯誤原因缺陷分析Bug-001006-邊緣落子007-邊緣落子008-邊緣落子白子沒對落在棋盤邊緣的黑子進行封堵，當黑子先形成五子連珠是提示白子獲勝產生這一缺陷的原因就是沒有添加“禁手判定”算法Bug-002010-算法問題白子沒對黑子進行封堵，提示黑子獲勝產生這一缺陷的原因可能是算法不太恰當Bug-003015-天元落子016-天元落子黑棋應該在天元落下第一個子，但實際結果是黑棋可以不在天元落子沒有增加天元落子算法6.3分析摘要6.3.1軟件能力《基于html的五子棋AI大戰(zhàn)》 游戲作為棋牌類休閑游戲基本可以滿足玩家的需求，但是如果想往競技游戲發(fā)展，則需要更多的改進和相應的完善。6.3.2缺陷和限制1.《基于html的五子棋AI大戰(zhàn)》游戲的功能還不夠完善，需要完善其功能。2.《基于html的五子棋AI大戰(zhàn)》源代碼中，沒有編寫“天元落子”的算法。這會導致在“AI先手”和“玩家先手”模式中進行游戲，黑棋先手可以不在天元落子，不符合游戲規(guī)則。3.《基于html的五子棋AI大戰(zhàn)》源代碼中，沒有對邊緣落子進行算法判定，導致一旦有邊緣落子而形成五子連珠，AI就不會進行封堵，影響了游戲的難度。6.4測試結論該《基于html的五子棋AI大戰(zhàn)》游戲存在很大的問題，但是由于針對的玩家群體不同，具體情況，還是由玩家需求來決定，畢竟該游戲只是人們工