題-1_100_100.jpg)
基本信息
- 項(xiàng)目名稱：
- 六子棋
- 來(lái)源：
- 第十二屆“挑戰(zhàn)杯”省賽作品
- 小類：
- 信息技術(shù)
- 大類：
- 科技發(fā)明制作B類
- 簡(jiǎn)介：
- 目前已經(jīng)出現(xiàn)六子棋的論壇以及比賽的平臺(tái)，但只限于人人對(duì)弈。真正對(duì)于六子棋計(jì)算機(jī)博弈算法以及系統(tǒng)的研究還不多。六子棋的發(fā)明者臺(tái)灣吳毅成教授給出了六子棋的公平性問(wèn)題以及基于迫著(Threats)的勝利策略，但是對(duì)于其計(jì)算機(jī)博弈問(wèn)題沒(méi)有給出更加深刻的闡述，同時(shí)也沒(méi)有全面解決六子棋計(jì)算機(jī)博弈問(wèn)題。本文正是對(duì)六子棋計(jì)算機(jī)博弈技術(shù)的一個(gè)探索。
- 詳細(xì)介紹：
- 1.研究目標(biāo) 六子棋計(jì)算機(jī)博弈系統(tǒng)可以分為四個(gè)主要部分：搜索引擎、走法生成、評(píng)估函數(shù)和開局庫(kù)。搜索引擎模塊包含了比較成熟的搜索算法，以及對(duì)他們的結(jié)合和優(yōu)化；走法生成模塊是對(duì)搜索的結(jié)果進(jìn)行比較處理，確定當(dāng)前的走法；評(píng)估函數(shù)模塊中本文根據(jù)棋型特征構(gòu)建了著子棋力的評(píng)估函數(shù)并提出用 算法來(lái)做評(píng)估函數(shù)參數(shù)的調(diào)整與優(yōu)化的方法；開局庫(kù)存儲(chǔ)了大量的專家棋譜，可以避免在開局時(shí)由于搜索深度的不足而帶來(lái)戰(zhàn)略上的失誤，同時(shí)大大提高了對(duì)戰(zhàn)的效率。 2.內(nèi)容介紹 六子棋是“信息完備”的游戲，因?yàn)橛螒螂p方面對(duì)的局面是同一個(gè)局面，任何一方所掌握的棋子及其位置的信息是一樣的。除了六子棋，象棋、圍棋等也可屬于這一范疇。 人機(jī)對(duì)弈的程序, 至少應(yīng)具備以下5個(gè)部分: ①某種在機(jī)器中表示棋局的方法，能夠讓程序知道博弈的狀態(tài)； ②產(chǎn)生合法走法的規(guī)則，以使博弈公正地進(jìn)行，并可判斷人類對(duì)手是否亂走； ③從所有合法的走法中選擇最佳的走法技術(shù)(博弈搜索)； ④一種評(píng)估局面優(yōu)劣的方法(評(píng)估函數(shù))，用以同上面的技術(shù)配合做出智能的選擇； ⑤一個(gè)人機(jī)界面，計(jì)算機(jī)博弈程序才能使用。 2.開發(fā)與運(yùn)行環(huán)境 針對(duì)上述介紹的六子棋的特性，利用現(xiàn)有資源選用如下的配置，當(dāng)然在正式比賽中最好選用配置更高的計(jì)算機(jī)，以便系統(tǒng)在有限的時(shí)間里可以搜索更深的深度。特別指出，為方便演示，本論文中提到的源碼搜索深度最多只到第四層，采用如下配置運(yùn)行該系統(tǒng)，搜索時(shí)間最多不超過(guò)10秒。 開發(fā)環(huán)境 ? Intel PentiumⅣ? 2.8GHz CPU 1.00G內(nèi)存 100G硬盤 ? Microsoft Windows? XP Professional Service Pack3 ? Microsoft Visual Studio.NET 2005 運(yùn)行環(huán)境(最低配置) ? Intel PentiumⅢ? 以上733MHz CPU 256M以上內(nèi)存 4G以上硬盤 ? Microsoft Windows98 操作系統(tǒng) ? 800*600或以上的屏幕分辨率 3. 系統(tǒng)功能設(shè)計(jì) 六子棋博弈程序的可以分為五個(gè)部分：數(shù)據(jù)表示，走法生成，搜索引擎，核心估值和用戶界面。下面我們將概要介紹一下各部分的實(shí)現(xiàn)過(guò)程。 3.1人機(jī)界面 任何計(jì)算機(jī)博弈程序都需要一個(gè)人機(jī)界面，由于六子棋剛剛興起，還沒(méi)有類似象棋中的UCCI之類的統(tǒng)一的界面協(xié)議和引擎，現(xiàn)在都還是六子棋愛(ài)好者單獨(dú)開發(fā)的?？傮w來(lái)說(shuō)，人機(jī)界面是為了方便棋手的操作，并且提供難度選擇、計(jì)時(shí)器、走棋記錄等功能。 3.2棋盤表示 要讓計(jì)算機(jī)下棋首先需要解決的就是棋盤和棋局的數(shù)字表示。目前所有棋類常用的表示方法有比特表示(又稱位棋盤)和矩陣表示，本文中提到的程序采用的是矩陣表示。比如棋盤是由9路9行形成81個(gè)交叉點(diǎn), 它很容易用9×9 的棋盤數(shù)組矩陣 表示出棋子與坐標(biāo)的對(duì)應(yīng)關(guān)系。要表示棋局則首先要給棋子編碼，應(yīng)該說(shuō)編碼的方法是任意的，只要能夠滿足棋局表示的唯一性和可區(qū)分性，都是可行的編碼。如果考慮和追求棋局處理的節(jié)儉與快捷，那么在編碼上還是有研究的余地。 以六子棋為例，我們需要把屏幕上看到的棋子位置、顏色、價(jià)值等信息、用計(jì)算機(jī)語(yǔ)言表示出來(lái)。本程序的棋盤數(shù)據(jù)表示如圖2-1所示，棋盤數(shù)據(jù)由一個(gè)19*19的二位數(shù)組表示，其中用 1 代表黑子，2 表示白子，而 0代表該節(jié)點(diǎn)沒(méi)有棋子。 3.3著法生成 當(dāng)前流行的著法生成方法有棋盤掃描法、模板匹配法和預(yù)置表法，通常還結(jié)合使用。六子棋中，合法走法是棋盤上沒(méi)有落子的結(jié)點(diǎn)，即m_Dream6Board[i][j]=0。簡(jiǎn)述如下： ①模板匹配法：通常是一些優(yōu)秀的走法定式，期盼數(shù)組按照這種方法落子，贏得機(jī)會(huì)很大。這些大多是一些大師公認(rèn)的棋譜，存儲(chǔ)在數(shù)據(jù)庫(kù)中，方便迅速落子，節(jié)約時(shí)間。 ②預(yù)置表法：它是最為經(jīng)常的著法生成方法，基本思想是用空間換時(shí)間，為了節(jié)省博弈過(guò)程中的生成著法的掃描時(shí)間，將動(dòng)子在棋盤任何位置(提址)，針對(duì)棋子的全部可能分布，事先給出可能的吃子走法和非吃子走法。當(dāng)然，六子棋無(wú)吃子情況，但是確存在已經(jīng)有三個(gè)或四個(gè)連成一條線的棋子，把這些地方引入預(yù)置表是一種常見思路。 ③棋盤掃描法：在著法生成的過(guò)程中需要在棋盤上反復(fù)掃描有效區(qū)域、制約條件和落子狀況，確定有哪些結(jié)點(diǎn)可以落子。根據(jù)六子棋的規(guī)則，棋盤有效區(qū)域內(nèi)的所有空白的交點(diǎn)都是可行落子點(diǎn)。目前的規(guī)則中還不存在禁手(五子棋對(duì)弈有三?三、四?四等禁手的規(guī)則)，即所有未落棋子點(diǎn)都是掃描區(qū)域。在著法的表達(dá)上，棋盤掃描法最為直觀，但時(shí)間開銷巨大。 所以本程序中把上述三種方法結(jié)合起來(lái)運(yùn)用，尤其是對(duì)棋盤掃描法，本程序中分別采用壓縮存儲(chǔ)空間(根據(jù)對(duì)稱性)和縮小掃描范圍(根據(jù)脫離戰(zhàn)場(chǎng)必?cái)〉乃枷?兩種獨(dú)特的方法，在開局不久尤為有效。 3.4 博弈樹 任何棋類游戲都要定義一棵有根的樹(即博弈樹)，一個(gè)結(jié)點(diǎn)就代表棋類的一個(gè)局面，子結(jié)點(diǎn)就是這個(gè)局面走一步可以到達(dá)的一個(gè)局面。 搜索引擎的作用就是借助評(píng)估函數(shù)從“上往下搜”，然后從“后(葉)往前看”，最終選出一條“最佳”路徑。如果在競(jìng)賽時(shí)間固定的情況下，通過(guò)衡量剩余時(shí)間來(lái)分配每一步的搜索時(shí)間，以此來(lái)約束搜索深度。通常情況下，開局時(shí)調(diào)用開局庫(kù)中已有的模式可以節(jié)約時(shí)間，但是后期由于局面較復(fù)雜，可能必須安排更多的時(shí)間加強(qiáng)搜索深度。 一般來(lái)說(shuō)，博弈樹的根結(jié)點(diǎn)應(yīng)該有很多子結(jié)點(diǎn)，先根據(jù)對(duì)稱性去掉一些結(jié)點(diǎn)(俗稱剪枝)來(lái)壓縮存儲(chǔ)空間，然后把這顆普通樹轉(zhuǎn)化成完全二叉樹，便于計(jì)算機(jī)處理。如果同樣的棋盤是由兩個(gè)不同的搜索引擎同時(shí)搜索形成的，那么我們就建立兩棵普通樹，然后把這兩棵樹組成的森林轉(zhuǎn)化成完全二叉樹。假設(shè)博弈樹是有限的，這樣我們就不會(huì)遇到永無(wú)止境的棋局或者一步有無(wú)限多種著法的棋局。 一般搜索樹中有三種類型的結(jié)點(diǎn)(當(dāng)乙執(zhí)黑時(shí))： ①偶數(shù)層的中間結(jié)點(diǎn)，代表棋手甲要走的局面； ②奇數(shù)層的中間結(jié)點(diǎn)，代表棋手乙要走的局面； ③葉子結(jié)點(diǎn)，代表棋局結(jié)束的局面，即棋手甲或棋手乙獲勝，或者是和局。 我們由圖2－2可見，本程序采用的算法是“兩步并一步”的方法，所以也會(huì)有上述其他棋類中提到的奇數(shù)層和偶數(shù)層棋手交替表示的方法。 3.5搜索算法 搜索算法是博弈樹求解的靈魂，有效的搜索算法能在有限的時(shí)間內(nèi)找到正確的結(jié)點(diǎn)。我們無(wú)法搜索到最終的勝負(fù)狀態(tài)，于是搜索的目標(biāo)便成為如何在有限深度的博弈樹中找到評(píng)估值最高而又不劇烈波動(dòng)的最佳狀態(tài)(棋局)，從當(dāng)前狀態(tài)出發(fā)到達(dá)最佳狀態(tài)的路徑便為最佳路徑(Principal Continuation)，它代表著理智雙方精彩對(duì)弈的系列著 法。而最佳路徑上的第一步棋便成為當(dāng)前局面的最佳著法(The best move)。所謂 “不劇烈波動(dòng)”就是說(shuō)最佳棋局不是在進(jìn)行子力交換與激烈拼殺的過(guò)程當(dāng)中。 3.6評(píng)估函數(shù) 對(duì)于博弈樹求解有了良好的搜索算法還只是問(wèn)題的一個(gè)方面，問(wèn)題的另一個(gè)方面就是評(píng)估函數(shù)。只有有了優(yōu)秀的評(píng)估函數(shù)才能保證較快地找到合適結(jié)點(diǎn)。而評(píng)估函數(shù)是對(duì)棋局的綜合評(píng)估，該函數(shù)的好壞直接決定棋力的強(qiáng)弱。通常一個(gè)優(yōu)秀的棋手總有一個(gè)良好的對(duì)棋局的判斷能力，能夠協(xié)調(diào)各棋子的關(guān)系、恰當(dāng)取舍，合理組織棋子的進(jìn)攻步調(diào)，控制棋局的發(fā)展。因此如果要把這一整套的思維物化成一個(gè)數(shù)值函數(shù)來(lái)評(píng)估，本身就是一個(gè)相當(dāng)復(fù)雜的問(wèn)題。 (1)整體考慮 評(píng)估函數(shù)綜合了大量跟具體棋類有關(guān)的知識(shí)，把局面的情況衡量成一個(gè)數(shù)字，這同樣也是評(píng)估函數(shù)在該結(jié)點(diǎn)的返回值。評(píng)估的指標(biāo)取決于對(duì)六子棋的熟練程度，評(píng)估越復(fù)雜，包含的代碼可能越多，時(shí)空復(fù)雜度也可能就越大。 (2) 組合評(píng)估要素 把評(píng)估要素組合起來(lái)，評(píng)估函數(shù)就成為一個(gè)多項(xiàng)式的和，每一項(xiàng)又可能是一個(gè)函數(shù)，它負(fù)責(zé)找到局面中的某個(gè)特定因素，絕大多數(shù)學(xué)者主張?jiān)谶@里運(yùn)用模糊數(shù)學(xué)中的層析分析法來(lái)解決類似綜合的問(wèn)題。通常來(lái)說(shuō)，棋類程序的評(píng)估函數(shù)是在不斷嘗試中逐漸修正、磨合出來(lái)的，包括快攻獲勝和殘局獲勝中的很多“不確定”因素。如果黑方很快獲勝的可能性用 bs 表示，而白方用 ws，在很多回合以后獲勝(即不是很快獲勝)的可能性是 bm 或 wm，而在殘局中獲勝的可能性是 be 或 we，那么整個(gè)獲勝的可能性就是： 黑方：bs + (1 - bs - ws) * bm + (1 - bs - ws - bm - wm) * be 白方：ws + (1 - bs - ws) * wm + (1 - bs - ws - bm - wm) * we 通過(guò)和類似上面的公式把若干單獨(dú)概率結(jié)合起來(lái)，在評(píng)估函數(shù)中是一種常見的估計(jì)概率的思路。每種概率是否估計(jì)得好，這就需要用程序的估計(jì)來(lái)和開局庫(kù)中棋局的真實(shí)結(jié)果來(lái)做比較，同時(shí)需要讓程序具有基本判斷的能力。 (3)評(píng)估函數(shù)的指標(biāo) 有必要把下列不同類型的評(píng)判指標(biāo)組合起來(lái)： ①子力(Material)：在國(guó)際象棋中，它是子力價(jià)值的和，在圍棋或黑白棋中，它是雙方棋盤上棋子的數(shù)量。這種評(píng)價(jià)通常是有效的，但其他像六子棋這樣的游戲，子力是沒(méi)有多大作用的，因?yàn)槠辶Φ暮脡膬H僅取決于棋子在棋盤上的位置； ②空間(Space)：在某些棋類中，棋盤可以分為一方控制的區(qū)域，另一方控制的區(qū)域，以及有爭(zhēng)議的區(qū)域?？臻g的評(píng)價(jià)就是把這些區(qū)域加起來(lái)，如果某個(gè)結(jié)點(diǎn)比其他結(jié)點(diǎn)重要的話，那么就用必須添加加區(qū)域重要性的因素，比如調(diào)整該結(jié)點(diǎn)的權(quán)重； ③機(jī)動(dòng)(Mobility)：具備越多選擇余地的著法，越有可能找到最優(yōu)落子點(diǎn)能取得較好的局勢(shì)，也即強(qiáng)迫算法不要在“死角”或者更本不可能贏的區(qū)域落棋子； ④著法(Tempo)：這與機(jī)動(dòng)性有密切聯(lián)系，它指的是在黑白棋或連四子棋中(以及某些國(guó)際象棋殘局中)，某方被迫作出使局面變得不利的著法，這種思路更多運(yùn)用在對(duì)己方不利的殘局，“無(wú)奈之下的落子”迫使局面更加混亂，當(dāng)然出現(xiàn)這樣的狀況對(duì)雙方都不利，但是在發(fā)現(xiàn)贏棋已經(jīng)無(wú)望的時(shí)候，逼和總是比束手就擒要好的多。 ⑤威脅(Threat)：對(duì)一些已經(jīng)被大家公認(rèn)的具有威脅的棋的套數(shù)出來(lái)的時(shí)候，必須提高這種局面的優(yōu)先級(jí)，讓搜索引擎首先檢索這些結(jié)點(diǎn)，或者采用一些預(yù)先存儲(chǔ)在數(shù)據(jù)庫(kù)中的定式，直接避過(guò)搜索，套用歷史上一致公認(rèn)的好棋路，直接落子。這種情況很常見，不如被對(duì)方棋子逼入死角或者對(duì)方已經(jīng)有可能形成三?三、四?四等局面； ⑥形狀(Shape)：與威脅類似，局面中的棋子已經(jīng)出現(xiàn)某種特殊的形狀，必須優(yōu)先處理，或者己方局面有利于形成某種比較好的定式的形狀，優(yōu)先分析這些結(jié)點(diǎn)。當(dāng)然某些形狀就是一個(gè)陷阱的警告，必須提醒系統(tǒng)有效回避。 (4)獲取評(píng)估函數(shù)的數(shù)值解的方法 以下給出一些獲取評(píng)估函數(shù)中數(shù)值的方法： ①爬山法(Hill-Climbing)：通過(guò)不斷的對(duì)弈，調(diào)整局面和棋形的權(quán)重，每次對(duì)權(quán)重作很小的改變，測(cè)試改變后的表現(xiàn)，僅當(dāng)成績(jī)提高時(shí)才采納這個(gè)改變，需要重復(fù)很多次。于此類似的是模擬退火法(Simulated Annealing)。也是對(duì)權(quán)重做出改變來(lái)提高成績(jī)，即使改變沒(méi)有提高成績(jī)，有時(shí)候也采納改變，這種方法試圖跳出全局最優(yōu)的情況； ②神經(jīng)網(wǎng)絡(luò)(Neural Networks)：這種方法的好處在于它不需要很懂得太多的棋類知識(shí)，就可以讓程序有個(gè)比較好的評(píng)價(jià)函數(shù)。實(shí)際上這更多地是一種評(píng)價(jià)函數(shù)的類型，而不僅是用來(lái)選擇權(quán)重的，于此類似的方法有遺傳算法，它可以得到幾組不同的好的權(quán)重值，并且不斷增加新的組合跟原來(lái)的結(jié)果做比較，通過(guò)淘汰壞的組合來(lái)控制種群的數(shù)量。在后文中將簡(jiǎn)要描述這種方法在本程序中的應(yīng)用。
作品圖片
作品專業(yè)信息
設(shè)計(jì)、發(fā)明的目的和基本思路、創(chuàng)新點(diǎn)、技術(shù)關(guān)鍵和主要技術(shù)指標(biāo)
- 本文中提出的六子棋計(jì)算機(jī)博弈系統(tǒng)可以分為四個(gè)主要部分：搜索引擎、走法生成、評(píng)估函數(shù)和開局庫(kù)。搜索引擎模塊包含了比較成熟的搜索算法，以及對(duì)他們的結(jié)合和優(yōu)化；走法生成模塊是對(duì)搜索的結(jié)果進(jìn)行比較處理，確定當(dāng)前的走法；評(píng)估函數(shù)模塊中本文根據(jù)棋型特征構(gòu)建了著子棋力的評(píng)估函數(shù)并提出用 算法來(lái)做評(píng)估函數(shù)參數(shù)的調(diào)整與優(yōu)化的方法。
科學(xué)性、先進(jìn)性
- 本文對(duì)六子棋計(jì)算機(jī)博弈系統(tǒng)進(jìn)行了測(cè)試與評(píng)價(jià)，包括評(píng)估函數(shù)的準(zhǔn)確度、搜索算法的效率以及系統(tǒng)的整體性能，同時(shí)簡(jiǎn)單分析了運(yùn)用更高性能的服務(wù)器，通過(guò)互聯(lián)網(wǎng)與棋類愛(ài)好者實(shí)現(xiàn)人機(jī)對(duì)弈的可操作性。
獲獎(jiǎng)情況及鑒定結(jié)果
- 無(wú)
作品所處階段
- 生產(chǎn)階段
技術(shù)轉(zhuǎn)讓方式
- 可以代理轉(zhuǎn)讓
作品可展示的形式
- 實(shí)物 產(chǎn)品 圖紙 現(xiàn)場(chǎng)演示 圖片 錄像
使用說(shuō)明,技術(shù)特點(diǎn)和優(yōu)勢(shì),適應(yīng)范圍,推廣前景的技術(shù)性說(shuō)明,市場(chǎng)分析,經(jīng)濟(jì)效益預(yù)測(cè)
- 這套六子棋程序采用C++開發(fā)，可以嵌入到手機(jī)里做為手機(jī)游戲，可以進(jìn)行人機(jī)對(duì)抗，機(jī)-機(jī)對(duì)抗?？梢酝茝V到手機(jī)的桌面小游戲的行列中。
同類課題研究水平概述
- 在過(guò)去的半個(gè)世紀(jì)里,世界各地的學(xué)者花費(fèi)了大量的心血對(duì)于計(jì)算機(jī)博弈包括奧賽羅、checker、國(guó)際象棋、中國(guó)象棋、五子棋、 圍棋進(jìn)行研究。這是因?yàn)橛?jì)算機(jī)博弈是人工智能的一塊試金石，然而棋類游戲又是計(jì)算機(jī)博弈的一個(gè)標(biāo)準(zhǔn)性問(wèn)題，各種搜索算法、模式識(shí)別及智能方法在計(jì)算機(jī)博弈中都可以得到廣泛的應(yīng)用。在長(zhǎng)時(shí)間的研究中,涌現(xiàn)出大量令人震驚的成果,1997年“深藍(lán)”戰(zhàn)勝卡斯帕羅夫的比賽就在全世界范圍內(nèi)引發(fā)了震動(dòng)，其他很多棋類的計(jì)算機(jī)水平都已達(dá)到了世界冠軍的水平。 目前，對(duì)于像五子棋、中國(guó)象棋等棋類游戲的計(jì)算機(jī)博弈算法研究已相對(duì)成熟，六子棋作為一個(gè)剛剛興起不久的棋類游戲，其計(jì)算機(jī)博弈算法的研究還相對(duì)較少。即使目前已經(jīng)出現(xiàn)六子棋的論壇以及比賽的平臺(tái)，但只限于人人對(duì)弈。真正對(duì)于六子棋計(jì)算機(jī)博弈算法以及系統(tǒng)的研究還不多。六子棋的發(fā)明者臺(tái)灣吳毅成教授給出了六子棋的公平性問(wèn)題以及基于迫著(Threats)的勝利策略，但是對(duì)于其計(jì)算機(jī)博弈問(wèn)題沒(méi)有給出更加深刻的闡述，同時(shí)也沒(méi)有全面解決六子棋計(jì)算機(jī)博弈問(wèn)題。本文正是對(duì)六子棋計(jì)算機(jī)博弈技術(shù)的一個(gè)探索。
