實(shí)驗(yàn)三：愛(ài)因斯坦棋PPT課件

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

2、子走動(dòng)方向?yàn)橄蜃?、向上、向左上，每次走?dòng)一格5.如果在棋子走動(dòng)的目標(biāo)棋位上有棋子，則要將該棋子從棋盤(pán)上移出（吃掉）。有時(shí)吃掉本方棋子也是一種策略，因?yàn)榭梢栽黾悠渌遄幼邉?dòng)的機(jī)會(huì)與靈活性6.率先到達(dá)對(duì)方出發(fā)區(qū)角點(diǎn)或?qū)?duì)方棋子全部吃掉的一方獲勝7.對(duì)弈結(jié)果只有勝負(fù)，沒(méi)有和棋3回到首頁(yè)棋盤(pán)一覽當(dāng)前可移動(dòng)棋子藍(lán)方移動(dòng)棋子策略，只能向左、向上和左斜向上。按鍵可實(shí)施移動(dòng)策略。紅方移動(dòng)棋子策略，只能向右、向下和右斜向下。按鍵可實(shí)施移動(dòng)策略。一輪結(jié)束后，勝者場(chǎng)次加一。立即開(kāi)始下一場(chǎng)比賽。45細(xì)節(jié) 棋盤(pán)左上角坐標(biāo)為（0，0），右下角坐標(biāo)為（4,，4） 紅色棋子id為1-6，藍(lán)色棋子id為7-12 由于客戶端返回

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

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

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

6、能夠在控制臺(tái)上實(shí)時(shí)顯示對(duì)戰(zhàn)日志格式: YYYY-MM-dd hh-mm-ss : content一輪結(jié)束需要明確顯示出對(duì)戰(zhàn)結(jié)果及對(duì)戰(zhàn)時(shí)長(zhǎng)對(duì)戰(zhàn)日志能夠保存在本地硬盤(pán)上文件名： YYYY-MM-dd-hh-mm-ss.log （時(shí)間為對(duì)戰(zhàn)開(kāi)始時(shí)間） 11Socket連接框架1. 監(jiān)聽(tīng)端口2. 所有參賽者連接即開(kāi)始比賽（TestServer僅有一位Socket連接者）3. 發(fā)送棋盤(pán)，接受消息，維護(hù)比賽* 隨時(shí)捕獲異常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代表本機(jī)IP，使用TestServer測(cè)試時(shí)使用本機(jī)IP即可。通信協(xié)議connect.Round End13ID當(dāng)前棋盤(pán)|骰子點(diǎn)數(shù)棋子|移動(dòng)指令當(dāng)前棋盤(pán)|骰子點(diǎn)數(shù)棋子|移動(dòng)指令客戶端服務(wù)器close數(shù)據(jù)傳輸示例 服務(wù)器發(fā)送數(shù)據(jù)類型（棋盤(pán)|骰子點(diǎn)數(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 對(duì)戰(zhàn)結(jié)束14游戲規(guī)則備注 由于返回結(jié)果較為簡(jiǎn)單，因此一旦被服務(wù)器確認(rèn)結(jié)果不正確（返回?cái)?shù)據(jù)無(wú)法分析，棋子不在棋盤(pán)中，棋子不是根據(jù)骰子點(diǎn)數(shù)選擇的，棋子移動(dòng)位置不在棋盤(pán)中等）直接判定對(duì)方勝利。 服務(wù)器設(shè)置超時(shí)時(shí)間為5s，如果服務(wù)器在發(fā)送數(shù)據(jù)5s后仍未收到任何數(shù)據(jù)判定對(duì)方勝利。 對(duì)戰(zhàn)雙方均存在無(wú)法連接或運(yùn)行失敗的問(wèn)題，哪方在對(duì)戰(zhàn)過(guò)程中先出現(xiàn)錯(cuò)誤，判定對(duì)方勝利。15評(píng)分標(biāo)準(zhǔn) PPT 30%（主

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

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

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

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

13、1）訪問(wèn)頂點(diǎn)v；（2）依次從v的未被訪問(wèn)的鄰接點(diǎn)出發(fā)，對(duì)圖進(jìn)行深度優(yōu)先遍歷；直至圖中和v有路徑相通的頂點(diǎn)都被訪問(wèn)；（3）若此時(shí)圖中尚有頂點(diǎn)未被訪問(wèn)，則從一個(gè)未被訪問(wèn)的頂點(diǎn)出發(fā)，重新進(jìn)行深度優(yōu)先遍歷，直到圖中所有頂點(diǎn)均被訪問(wèn)過(guò)為止。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)于將整個(gè)圖分層，從起始點(diǎn)u出發(fā)，u處在第0層，定義兩個(gè)點(diǎn)之間的距離d(u,v)是u到v最少通過(guò)幾條邊可以走到。那么其他點(diǎn)所在的層數(shù)就是它到起

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

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

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

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

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

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