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

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

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

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

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

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