實驗三：愛因斯坦棋PPT課件

1、實驗三：愛因斯坦棋1助教： 王子成孫銳實驗三：愛因斯坦棋一. 規(guī)則介紹二. 實驗內(nèi)容三. 實驗展示四. 實驗周期五. 算法數(shù)據(jù)結(jié)構(gòu)思路（參考）2Contents一. 規(guī)則介紹棋具：一枚六面骰5*5棋盤紅藍雙方各1到6數(shù)字的棋子規(guī)則如下：1.棋盤為55的方格形棋盤，方格為棋位，左上角為紅方出發(fā)區(qū)，右下角為藍方出發(fā)區(qū)2.紅藍方各有6枚方塊形棋子，分別標(biāo)有數(shù)字16。開局時雙方棋子在出發(fā)區(qū)的棋位可以隨意擺放3.雙方輪流擲骰子，然后走動與骰子顯示數(shù)字相對應(yīng)的棋子。如果相對應(yīng)的棋子已從棋盤上移出，便可走動大于或小于此數(shù)字的并與此數(shù)字最接近的棋子4.紅方棋子走動方向為向右、向下、向右下，每次走動一格；藍方棋

2、子走動方向為向左、向上、向左上，每次走動一格5.如果在棋子走動的目標(biāo)棋位上有棋子，則要將該棋子從棋盤上移出（吃掉）。有時吃掉本方棋子也是一種策略，因為可以增加其它棋子走動的機會與靈活性6.率先到達對方出發(fā)區(qū)角點或?qū)Ψ狡遄尤砍缘舻囊环将@勝7.對弈結(jié)果只有勝負，沒有和棋3回到首頁棋盤一覽當(dāng)前可移動棋子藍方移動棋子策略，只能向左、向上和左斜向上。按鍵可實施移動策略。紅方移動棋子策略，只能向右、向下和右斜向下。按鍵可實施移動策略。一輪結(jié)束后，勝者場次加一。立即開始下一場比賽。45細節(jié) 棋盤左上角坐標(biāo)為（0，0），右下角坐標(biāo)為（4,，4） 紅色棋子id為1-6，藍色棋子id為7-12 由于客戶端返回

3、結(jié)果較為簡單，可能存在隨機返回移動策略的可能，可以通過統(tǒng)計移動錯誤率和助教檢查的方式避免。 移動策略： 紅方：right, down, rightdown 藍方：left, up, leftup6二. 實驗內(nèi)容1. 熟悉客戶端框架代碼閱讀ClientSocket.cpp/h，了解通信過程實現(xiàn)的邏輯閱讀Einstein.cpp/h，熟悉模塊框架閱讀愛因斯坦棋規(guī)則，構(gòu)建模型2. 設(shè)計算法PPT，完成對戰(zhàn)策略模塊3. 進行組內(nèi)PK4. 每組選出五個人參加第三周課堂決賽7回到首頁項目整體劃分服務(wù)器端：負責(zé)展示棋盤，記錄游戲結(jié)果測試服務(wù)器：1-1，用于學(xué)生測試游戲策略對戰(zhàn)服務(wù)器：1-n，用于小組內(nèi)對戰(zhàn)客

4、戶端：學(xué)生使用，負責(zé)編寫AI策略，與服務(wù)器通信8CLIENTSERVER棋盤數(shù)組，骰子棋子id，移動方向 客戶端代碼框架 文件功能文件名功能Define.h定義參賽ID、服務(wù)器IP、服務(wù)器PORTClientSocket.cpp/h實現(xiàn)與服務(wù)器通信的邏輯Einstein.cpp/h實現(xiàn)整個游戲的主要邏輯。重要函數(shù)：handlehandle實現(xiàn)每一步走棋策略可自己添加其他函數(shù)（建議根據(jù)算法添加函數(shù)以劃分功能）main.cpp開始游戲9客戶端代碼框架 Einstein.cpp中待實現(xiàn)的函數(shù)函數(shù)名函數(shù)名功能功能parse觀測接受的string消息，更新棋局變化handle處理每一步策略logging

5、將對戰(zhàn)記錄依次輸出到終端，并存儲在list容器中writelog存儲當(dāng)前棋局信息到txt中，用于復(fù)盤可自行根據(jù)算法設(shè)計，構(gòu)建更多用于策略的函數(shù)10閱讀main.cpp與Einstein.h，了解上述函數(shù)使用接口與數(shù)據(jù)結(jié)構(gòu)。除define.h中的參數(shù)和Einstein.cpp外，不可更改其他代碼，作業(yè)提交僅需要Einstein.cpp要求實現(xiàn)功能能夠作為紅方或藍方連接服務(wù)器進行對戰(zhàn)至少3局從服務(wù)器接收數(shù)據(jù)，分析接收的文本，編寫規(guī)則生成下一步，發(fā)送給服務(wù)器客戶端需要能夠根據(jù)分析的文本數(shù)據(jù)判定能夠移動的棋子和棋子移動的方向能夠根據(jù)棋盤數(shù)組發(fā)生較大的變化判定本局結(jié)束，下局開始，服務(wù)器不傳輸判定勝負數(shù)據(jù)

6、能夠在控制臺上實時顯示對戰(zhàn)日志格式: YYYY-MM-dd hh-mm-ss : content一輪結(jié)束需要明確顯示出對戰(zhàn)結(jié)果及對戰(zhàn)時長對戰(zhàn)日志能夠保存在本地硬盤上文件名： YYYY-MM-dd-hh-mm-ss.log （時間為對戰(zhàn)開始時間） 11Socket連接框架1. 監(jiān)聽端口2. 所有參賽者連接即開始比賽（TestServer僅有一位Socket連接者）3. 發(fā)送棋盤，接受消息，維護比賽* 隨時捕獲異常1. 接收Socket2. AI產(chǎn)生Step3. 發(fā)送SocketServerPlayer BPlayer ASocketSocket1. 接收Socket2. AI產(chǎn)生Step3. 發(fā)

7、送Socket12 Define.h文件中定義連接的目標(biāo)服務(wù)器的IP和端口，其中127.0.0.1代表本機IP，使用TestServer測試時使用本機IP即可。通信協(xié)議connect.Round End13ID當(dāng)前棋盤|骰子點數(shù)棋子|移動指令當(dāng)前棋盤|骰子點數(shù)棋子|移動指令客戶端服務(wù)器close數(shù)據(jù)傳輸示例 服務(wù)器發(fā)送數(shù)據(jù)類型（棋盤|骰子點數(shù)）： 0, 6, 2, 0, 0, 5, 1, 0, 0, 0, 4, 0, 0, 0, 8, 0, 0, 0, 10, 7, 0, 0, 9, 11, 12|1 客戶端發(fā)送數(shù)據(jù) 1|rightdown 或 1|right 或 1|down 1, 4, 0

8、, 0, 0, 6, 2, 0, 5, 0, 0, 0, 10, 0, 9, 0, 3, 0, 0, 7, 0, 0, 0, 11, 12|10 10|leftup 或 10|left 或 10|up close 對戰(zhàn)結(jié)束14游戲規(guī)則備注 由于返回結(jié)果較為簡單，因此一旦被服務(wù)器確認結(jié)果不正確（返回數(shù)據(jù)無法分析，棋子不在棋盤中，棋子不是根據(jù)骰子點數(shù)選擇的，棋子移動位置不在棋盤中等）直接判定對方勝利。 服務(wù)器設(shè)置超時時間為5s，如果服務(wù)器在發(fā)送數(shù)據(jù)5s后仍未收到任何數(shù)據(jù)判定對方勝利。 對戰(zhàn)雙方均存在無法連接或運行失敗的問題，哪方在對戰(zhàn)過程中先出現(xiàn)錯誤，判定對方勝利。15評分標(biāo)準(zhǔn) PPT 30%（主

9、要考察算法使用和實現(xiàn)） 正確實現(xiàn)，測試服務(wù)器對戰(zhàn)結(jié)果 ，日志記錄情況40% 組內(nèi)競賽結(jié)果 30% 禁止使用給出的測試用例策略或者其他傻瓜策略策略（如：只向單一方向移動）16提交 僅提交Einstein.cpp和PPT，建議使用在Linux平臺進行對戰(zhàn)測試，助教使用linux平臺進行自動測試。 提交格式 1818600*-linux(win、mac).cpp(ppt)（比賽是用腳本根據(jù)文件名自動分配參賽ID，格式錯誤會導(dǎo)致無成績）17三. 實驗流程展示181. 用簡單策略（如傻瓜策略、隨機策略）完成初級對戰(zhàn)產(chǎn)品2. 使用TestServer驗證產(chǎn)品能否運行，調(diào)試bug3. 使用更加智能的策略完善

10、產(chǎn)品，并與TestServer智能機器人進行對戰(zhàn)回到首頁測試服務(wù)器的使用（TestServer）19可選參數(shù)：BetaCat1.0智能機器人Human人類對戰(zhàn)，按鍵操作Socket通信對戰(zhàn)Demo傻瓜策略機器人監(jiān)聽端口參數(shù)設(shè)置：50006四. 實驗周期第0周布置題目第1周提交設(shè)計PowerPoint，算法思路，核心函數(shù)劃分，及預(yù)期效果第2周代碼完成基本功能，可編譯單獨運行，起碼可用服務(wù)器測試模式無錯走完一輪棋局。完成logging/writelog，能夠本地記錄棋局。（無論用什么方式，能夠明了的展現(xiàn)出來即可，比如存在文件中）第3周代碼完整提交。在此周課前各小組預(yù)賽決出前5名，在課上各組出線同學(xué)

11、進行決賽。并在PowerPoint上給出用戶手冊，助教會基于手冊上功能進行檢查20回到首頁實驗提交與檢查l 每周五上午12點為最終時間點，之后系統(tǒng)關(guān)閉。提交后無法修改。l 第一周第二周，每次隨機抽取同學(xué)，在主屏幕檢查l 第三周截止日期為周三中午12點，截止時間后，組內(nèi)比賽每組選出五名參加課堂決賽l 查重認定抄襲者，該實驗整體不計分21賽制規(guī)則l 第三周上課前，由助教下載所有學(xué)生作業(yè)，在本地Linux環(huán)境下完成組內(nèi)循環(huán)賽，根據(jù)積分選出前五名。l 第三周課上，舉行三組共15個人的循環(huán)賽，根據(jù)積分決出前八名。循環(huán)賽不設(shè)置時延，一次性跑完。l 隨后舉行前八名的淘汰賽，設(shè)置時延，可以觀看每步對戰(zhàn)。22五

12、. 算法數(shù)據(jù)結(jié)構(gòu)思路（參考）一種棋類游戲算法思路：評估函數(shù)對任意棋盤打分，來評估對自己和對手的有利程度評估函數(shù)的設(shè)計某種程度上決定了棋類算法的有效性。搜索策略廣度優(yōu)先 or 深度優(yōu)先搜索幾層隨機搜索、裁剪搜索、啟發(fā)搜索？優(yōu)化算法限制條件：時間 and 空間剪枝23回到首頁五. 算法數(shù)據(jù)結(jié)構(gòu)思路（參考）1.基礎(chǔ)搜索算法I.DFSII.BFS2.博弈樹搜索算法 極大極小算法期望搜索算法隨機搜索算法UCT算法3.啟發(fā)式搜索算法A*搜索4.優(yōu)化搜索算法-剪枝5.機器學(xué)習(xí)算法24Contents1.1基礎(chǔ)搜索算法DFS最基礎(chǔ)的搜索算法之深度優(yōu)先搜索（DFS）深度優(yōu)先遍歷圖的方法是，從圖中某頂點v出發(fā)：（

13、1）訪問頂點v；（2）依次從v的未被訪問的鄰接點出發(fā)，對圖進行深度優(yōu)先遍歷；直至圖中和v有路徑相通的頂點都被訪問；（3）若此時圖中尚有頂點未被訪問，則從一個未被訪問的頂點出發(fā)，重新進行深度優(yōu)先遍歷，直到圖中所有頂點均被訪問過為止。25最基礎(chǔ)的搜索算法之深度優(yōu)先搜索（DFS）深度優(yōu)先搜索順序深度優(yōu)先搜索順序:A - C - B - D - F - G - E261.1基礎(chǔ)搜索算法DFS1.2基礎(chǔ)搜索算法BFS最基礎(chǔ)的搜索算法之廣度優(yōu)先搜索（BFS）bfs相當(dāng)于將整個圖分層，從起始點u出發(fā)，u處在第0層，定義兩個點之間的距離d(u,v)是u到v最少通過幾條邊可以走到。那么其他點所在的層數(shù)就是它到起

14、始點u的距離。Bfs訪問點的順序就是逐層訪問271.2基礎(chǔ)搜索算法BFS最基礎(chǔ)的搜索算法之廣度優(yōu)先搜索（BFS）第第1步步：訪問A。第第2步步：依次訪問C,D,F。在訪問了A之后，接下來訪問A的鄰接點。前面已經(jīng)說過，在本文實現(xiàn)中，頂點ABCDEFG按照順序存儲的，C在D和F的前面，因此，先訪問C。再訪問完C之后，再依次訪問D,F。第第3步步：依次訪問B,G。在第2步訪問完C,D,F之后，再依次訪問它們的鄰接點。首先訪問C的鄰接點B，再訪問F的鄰接點G。第第4步步：訪問E。在第3步訪問完B,G之后，再依次訪問它們的鄰接點。只有G有鄰接點E，因此訪問G的鄰接點E。因此訪問順序是：A - C - D

15、 - F - B - G - E282.博弈樹搜索算法思路博弈樹博弈樹是指由于動態(tài)博弈參與者的行動有先后次序，因此可以依次將參與者的行動展開成一個樹狀圖形。對于任何一種博弈競賽，我們可以構(gòu)成一個博弈樹。它類似于狀態(tài)圖和問題求解搜索中使用的搜索樹。博弈樹的結(jié)點對應(yīng)于某一個棋局，其分支表示走一步棋；根部對應(yīng)于開始位置，其葉表示對弈到此結(jié)束。在葉節(jié)點對應(yīng)的棋局中，競賽的結(jié)果可以是贏、輸或者和局。 292.1博弈樹搜索極大極小算法 在二人博弈問題中，為了從眾多可供選擇的行動方案中選出一個對自己最為有利的行動方案，就需要對當(dāng)前的情況以及將要發(fā)生的情況進行分析，通過某搜索算法從中選出最優(yōu)的走步?；舅枷牖?/p>

16、算法是：(1) 設(shè)博弈的雙方中一方為MAX，另一方為MIN。然后為其中的一方尋找一個最優(yōu)行動方案。(2) 為了找到當(dāng)前的最優(yōu)行動方案，需要對各個可能的方案所產(chǎn)生的后果進行比較,具體地說，就是要考慮每一方案實施后對方可能采取的所有行動，并計算可能的得分。(3) 為計算得分，需要根據(jù)問題的特性信息定義一個估價函數(shù)，用來估算當(dāng)前博弈樹端節(jié)點的得分。此時估算出來的得分稱為靜態(tài)估值。(4) 當(dāng)端節(jié)點的估值計算出來后，再推算出父節(jié)點的得分，推算的方法是：對“或”節(jié)點，選其子節(jié)點中一個最大的得分作為父節(jié)點的得分，這是為了使自己在可供選擇的方案中選一個對自己最有利的方案；對“與”節(jié)點，選其子節(jié)點中一個最小的得

17、分作為父節(jié)點的得分，這是為了立足于最壞的情況。這樣計算出的父節(jié)點的得分稱為倒推值。(5) 如果一個行動方案能獲得較大的倒推值，則它就是當(dāng)前最好的行動方案。302.1博弈樹搜索極大極小算法311. 當(dāng)MAX（我方）走步時，MAX總是考慮最好的情況，選擇f(p)值最大的走步2. 當(dāng)MIN（敵方）走步時，MAX總是考慮最好的情況，選擇f(p)值最小的走步2.2博弈樹搜索期望搜索算法32 期望搜索算法來源于極大極小算法，通常被運用于雙人零和隨機性博弈。 它在極大極小算法的基礎(chǔ)上，通過在MAX層與MIN層之間加入PRO（概率）層，其中PRO層用來模擬隨機性博弈過程中隨機事件的期望值。2.3博弈樹搜索隨機

18、搜索算法33 根據(jù)計算步驟的確定與否，可將算法分為確定性算法和隨機性算法。若確定了步驟，即為確定性算法；若容許算法在運行中可隨意選擇下一個計算步驟，即隨機性算法。通常來講，算法運行中面對多個選擇的時候，隨機性算法比確定性算法更加節(jié)省時間，大大降低算法的時間復(fù)雜度。 目前，隨機搜索算法中主要有拉斯維加斯算法和蒙特卡洛算法，其基本思想是在有限的采樣中獲得最優(yōu)解。在相同的采樣越多的情況下，拉斯維加斯算法強調(diào)的是每一次迭代都在進步就越接近最優(yōu)解；蒙特卡洛算法則是越有可能找到最優(yōu)解，強調(diào)的是直接找到最優(yōu)解。 蒙特卡洛算法是計算機博弈研究過程中運用最多的隨機搜索算法，它主要是通過建立一個概率模型或者隨機過

19、程并采用抽樣實驗的方法來獲得最優(yōu)值。其基本思想就是通過大量且反復(fù)的抽樣來得到結(jié)果，也就是說，蒙特卡洛算法的精確性前來依賴于隨機模擬的次數(shù)。算法流程如圖。2.4博弈樹搜索算法UCT算法UCT算法UCT算法（Upper Confidence Bound Apply to Tree），即上限置信區(qū)間算法，是一種博弈樹搜索算法，最初是為了限制圍棋博弈樹的搜索空間而產(chǎn)生的。該算法將蒙特卡洛樹搜索(MonteCarlo Tree Search，MCTS)方法與UCB公式結(jié)合，在超大規(guī)模博弈樹的搜索過程中相對于傳統(tǒng)的搜索算法有著時間和空間方面的優(yōu)勢。2006年UCT算法的出現(xiàn)改變了計算機圍棋博弈領(lǐng)域止步不前的局面，互聯(lián)網(wǎng)上有大量的資料可自行學(xué)習(xí)。因較為復(fù)雜，在此不再贅述。343.啟發(fā)式搜索算法A* 搜索A* 搜索一種啟發(fā)式搜索方法一般的棋盤格子多，棋子個數(shù)多，每個位置都有紅棋藍棋或者無棋的3個狀態(tài)，總共狀態(tài)數(shù)非常巨量，完全搜索訪問肯定是無法進行的。本題愛因斯坦棋盤在棋類游戲中較為簡單，但是狀態(tài)數(shù)仍然是天量。A*搜索可以幫助自己優(yōu)先朝著自己所認為的更優(yōu)的方向進行搜索。353.啟發(fā)式搜索算法A* 搜索A* 搜索啟發(fā)式信息：用于幫助減少搜索量的與問題有關(guān)的信息或知識。啟發(fā)式搜索：使用啟發(fā)信息指導(dǎo)的搜索過程叫做啟發(fā)式搜索。估價函數(shù) g：定義在狀態(tài)空間上的實值函數(shù)。open表