連珠模式棋類博弈的搜索優(yōu)化.pdf

1、機器搏弈是人工智能的“果蠅”，同時也是該領(lǐng)域公認(rèn)的最具挑戰(zhàn)性的研究課題之一。人工智能的著名學(xué)者們認(rèn)為如果可以掌握博弈的本質(zhì)，同時也就意味著掌握了人類智能活動的核心所在。因為存在于棋類博弈的原則或許就存在于人類的智能活動中。近年來，國內(nèi)外計算機博弈比賽，極大的推動了計算機博弈問題的研究，促進(jìn)了計算機博弈理論和技術(shù)的發(fā)展。計算機博弈涉及的棋種較多，包括五子棋、六子棋、圍棋、象棋等。各種搜索算法在計算機博弈中已經(jīng)得到廣泛的應(yīng)用。
　　傳

2、統(tǒng)的機器博弈模型是以棋盤上的交叉點為基本單位來設(shè)計數(shù)據(jù)結(jié)構(gòu)的，局面的狀態(tài)描述也依賴于交叉點，而K子棋的局面可以與若干個連珠建立一一對應(yīng)關(guān)系，局面的狀態(tài)可由模式庫中的抽象知識來描述，稱為連珠模式。連珠的抽象知識最大程度的描述連珠內(nèi)各棋子聯(lián)合所形成的整體效果。模式之間存在演化關(guān)系，高效的博弈應(yīng)該合理的推動模式的演化。
　　為了提高搜索速度，K子棋的搜索算法基本都是以Alpha-Beta剪枝算法為基礎(chǔ)來進(jìn)行設(shè)計的。博弈樹搜索的深度越大，

3、獲得的著法最佳，但是受計算機博弈比賽的時間約束，搜索深度不可能無限大，而只能在有限的范圍內(nèi)，搜索技術(shù)需進(jìn)一步優(yōu)化。
　　本文以K子棋為研究對象，研究了機器博弈技術(shù)，包括一些基本概念和搜索算法;以五子棋和六子棋為實例進(jìn)行連珠模式棋類的設(shè)計，包括相關(guān)棋形、數(shù)據(jù)結(jié)構(gòu)及估值函數(shù)的設(shè)計;對棋形進(jìn)行定義、分析，并設(shè)計基于棋形掃描的搜索算法;分析了基于“路”的全局掃描方式的計算規(guī)則和估值分析，然后將博弈樹搜索算法中的全局掃描方式改進(jìn)為局部掃描方

4、式，并給出其計算規(guī)則和估值分析，接著設(shè)計了基于局部掃描方式的博弈樹生成算法，并集成到Alpha-Beta剪枝算法中。
　　從搜索效率和搏弈水平兩個角度進(jìn)行實驗可得:相對于無棋形掃描，基于棋形的掃描在搜索效率方面無顯著提高，但是博弈水平卻有明顯提高。相對于全局掃描，局部掃描大幅度提高搜索效率，博弈水平也有明顯提高。本文僅在開局和中局階段采用局部掃描方式，提高搜索效率，如何在殘局階段改進(jìn)估值提高效率，有待進(jìn)一步研究。
　　本文的

5、創(chuàng)新點如下:
　　(1)將博弈樹擴展時對棋盤進(jìn)行全局“路”掃描改進(jìn)為局部“路”掃描，忽略無用路數(shù)，減少了掃描的路數(shù)，提高了搜索效率;通過對全局掃描和局部掃描的估值定量分析對比，確定局部掃描完全可以等價代替全局掃描擴展博弈樹，不會降低精確度。
　　(2)設(shè)計了基于局部“路”掃描方式的博弈樹搜索算法，將該算法應(yīng)用于Alpha-Beta剪枝搜索時，和基于全局“路”掃描方式的博弈樹搜索算法相比，可以顯著提高博弈水平。
　　(3