人工智能概論實(shí)驗(yàn)指導(dǎo)：博弈樹搜索與剪枝

《人工智能概論》實(shí)驗(yàn)指導(dǎo)實(shí)驗(yàn)二博弈樹搜索與剪枝(3學(xué)時)實(shí)驗(yàn)題目：博弈樹搜索與剪枝實(shí)驗(yàn)?zāi)康模杭由顚Σ┺臉渌阉髋c剪枝的理解，能夠通過實(shí)驗(yàn)工具驗(yàn)證博弈樹搜索與剪枝原理。實(shí)驗(yàn)要求：(1)井字棋游戲的博弈樹搜索井字棋游戲由黑白雙方輪流落子，黑方先行，如果下一步該黑方走棋，用博弈樹搜索算法判斷應(yīng)該把棋子放在哪一個空格內(nèi)，并畫出相應(yīng)的搜索樹，然后使用實(shí)驗(yàn)工具加以驗(yàn)證?！稹窨衫脤ΨQ性刪除相似棋局?！瘛瘛瘛稹稹?a)(b)實(shí)驗(yàn)步驟：步驟一.用博弈樹搜索算法判斷棋局(a)(b)中應(yīng)該把黑方棋子放在哪一個空格內(nèi)，并畫出相應(yīng)的搜索樹。可采取以下任意一種估價函數(shù)。1.估價函數(shù)定義如下：設(shè)棋局為P，估價函數(shù)為e(P)。(1)若P是黑方必勝的棋局，則e(P)=+128。(2)若P是白方必勝的棋局，則e(P)=-128。(3)若P是勝負(fù)未定的棋局，則e(P)=e(+P)-e(-P)e(+P)：棋局P上有可能使黑方成為三子成一線的數(shù)目；e(-P)：棋局P上有可能使白方成為三子成一線的數(shù)目。2.h2（n）＝（黑方一階路－白方一階路）＋4×（黑方二階路－白方二階路）＋其中＋2，若黑方占領(lǐng)白方二階路＝－2，若白方占領(lǐng)黑方二階路0，其他若n為終局節(jié)點(diǎn)：+128黑方勝h2（n）＝－128白方勝0和局步驟二.運(yùn)行實(shí)驗(yàn)工具TicTacToe，界面如下圖所示。用鼠標(biāo)在相應(yīng)位置點(diǎn)擊，形成棋局（a）和棋局（b）.注意：黑方先行，黑白交替落子。步驟三.點(diǎn)擊Game菜單下SearchTree菜單項(xiàng)。步驟四.點(diǎn)擊右側(cè)的”Search”按鈕步驟五鼠標(biāo)右鍵點(diǎn)擊白色區(qū)域，記錄相應(yīng)的博弈搜索樹，并與步驟一中的博弈搜索樹和結(jié)果進(jìn)行比較和分析。(2)剪枝原理步驟一.對于以下博弈樹，在倒推過程中進(jìn)行α-β剪枝，并標(biāo)出剪枝類型。圖中a,b,c,d用自己學(xué)號的后四位數(shù)字代替，如1026，則對應(yīng)為1，0，2，6.步驟二.運(yùn)行實(shí)驗(yàn)工具TicTacToe。步驟三.點(diǎn)擊Choice菜單下Demo菜單項(xiàng),界面如下圖所示。其中矩形節(jié)點(diǎn)為或節(jié)點(diǎn)，圓形節(jié)點(diǎn)為與節(jié)點(diǎn)。步驟四.在下方的下拉列表框中選擇輸入步驟一中博弈樹