基于電阻電路評(píng)估策略的分階段?？怂蛊宀┺姆椒ǖ难芯?/h1>
2019-05-16 01:40:04張志禮段金龍羅鋒駿勾亮亮
智能計(jì)算機(jī)與應(yīng)用 2019年2期
張志禮，丁 濛，段金龍，羅鋒駿，勾亮亮
（北京信息科技大學(xué)計(jì)算機(jī)學(xué)院，北京100101）
0 引 言
?？怂蛊澹?］，亦稱六貫棋，最初是在丹麥報(bào)紙Politiken發(fā)表的一篇文章里出現(xiàn)，當(dāng)時(shí)稱為Polygon。1948年，John Nash卻又將其重新獨(dú)立發(fā)明出來(lái)，而熱衷于此的玩家們隨即就將其稱作Nash。稍后于1952年P(guān)arker Brothers發(fā)行了一個(gè)版本，將其稱為Hex，從此這個(gè)名字就固定了下來(lái)。六貫棋是在六邊形格的棋盤(pán)上競(jìng)技的圖版游戲，亦是數(shù)學(xué)游戲，通常使用10×10或11×11的菱形棋盤(pán)，而John Nash采用的卻是14×14的棋盤(pán)。
?？怂蛊宓囊?guī)則為：
（1）由2個(gè)人共同參與，棋盤(pán)為平行四邊形，有2種顏色，通常是紅、藍(lán)或黑、白。4個(gè)邊平行填上兩方的顏色。
（2）雙方輪流走棋，先后手自行選擇，每次只能下一個(gè)棋子，每次占領(lǐng)一處空白格，在空白格放上自己顏色的棋子。
（3）整個(gè)比賽中，雙方均不能吃掉對(duì)方或已方的棋子。
（4）最先將棋盤(pán)屬于自己的顏色的邊連成一線的一方為勝。
在棋類博弈比賽中沒(méi)有統(tǒng)一的棋盤(pán)和棋譜格式，為了能夠標(biāo)準(zhǔn)化導(dǎo)出棋譜并保留博弈數(shù)據(jù)，2018年中國(guó)大學(xué)生計(jì)算機(jī)博弈大賽為每種棋類項(xiàng)目發(fā)布了統(tǒng)一標(biāo)準(zhǔn)［2］，本次研究則嚴(yán)格按照中國(guó)大學(xué)生計(jì)算機(jī)博弈大賽棋譜標(biāo)準(zhǔn)說(shuō)明書(shū)要求編寫(xiě)了?？怂蛊宀┺能浖?。此外，比賽程序BistuHex2提出了UCT、α-β剪枝和電阻電路評(píng)估策略配合使用的搜索方法，在往屆中國(guó)大學(xué)生計(jì)算機(jī)博弈比賽中取得優(yōu)異成績(jī)。對(duì)此，本文擬展開(kāi)研究論述如下。
1 評(píng)估策略設(shè)計(jì)與應(yīng)用
?？怂蛊瀚@勝的方法是將棋盤(pán)屬于自己的顏色的邊連成一線，而且每個(gè)棋子的行棋都要考慮攻防兼?zhèn)?，因此雙方每次落子都至關(guān)重要，棋類游戲的搜索算法大同小異，這時(shí)，一個(gè)較優(yōu)的評(píng)估策略，及其與搜索算法的合理結(jié)合，則成了決勝的關(guān)鍵。BistuHex2程序是利用UCT算法、α-β剪枝算法與電阻電路評(píng)估策略［3］進(jìn)行分階段式配合使用，評(píng)估策略是利用電路電阻的特點(diǎn)，將其用來(lái)作為海克斯棋局面的評(píng)估函數(shù)，以棋局的局面特征作為輸入，評(píng)估值及較優(yōu)的可走棋子作為輸出，為搜索算法進(jìn)一步縮小搜索范圍，并提供判斷局面優(yōu)劣的依據(jù)。
1.1 UCT、α-β剪枝與評(píng)估策略分階段式結(jié)合
UCT算法（Upper Confidence Bound Apply to Tree），即上限置信區(qū)間算法，是一種博弈樹(shù)搜索算法，該算法將蒙特卡洛樹(shù)搜索（Monte—Carlo Tree Search，MCTS）方法與UCB公式結(jié)合，在超大規(guī)模博弈樹(shù)的搜索過(guò)程中相對(duì)于傳統(tǒng)的搜索算法有著時(shí)間和空間方面的優(yōu)勢(shì)。之前使用的程序僅基于UCT，搜索時(shí)間長(zhǎng)、范圍廣，而且不準(zhǔn)確，當(dāng)前使用程序?yàn)锽istuHex2，則是將UCT、α-β剪枝與電阻電路評(píng)估策略進(jìn)行分階段式結(jié)合。
通過(guò)上述評(píng)估算法可以得出許多可以減少已方電阻的點(diǎn)。將這些點(diǎn)作為UCT模擬的對(duì)象，就避免了盲目搜索，極大地提高了搜索效率。在開(kāi)局時(shí)，需要搜索的點(diǎn)很多，用UCT模擬的效果很差，因此在開(kāi)局的時(shí)候采用α-β剪枝算法與基于電阻電路評(píng)估策略結(jié)合的方法，使得程序在開(kāi)局時(shí)依然可以非常強(qiáng)大。當(dāng)評(píng)估算法獲得的點(diǎn)較少時(shí)，再采用UCT搜索算法與基于電阻電路評(píng)估策略的結(jié)合，可以在后期有效地把控全局。
1.2 電阻電路評(píng)估策略
評(píng)估策略是用電路和電阻的思路結(jié)合海克斯棋的特點(diǎn)進(jìn)行設(shè)計(jì)，對(duì)?？怂蛊鍋?lái)說(shuō)，一個(gè)合理的估值函數(shù)應(yīng)該估計(jì)黑棋方建立一條獲勝黑鏈的程度比白棋方要建立一條獲勝的白鏈更接近。
衡量玩家建立鏈條的接近程度的一種流行方法是計(jì)算該玩家需要添加的最小數(shù)量的棋子以連接棋盤(pán)的兩側(cè)，但是這種方法沒(méi)有考慮潛在鏈的數(shù)量。試圖通過(guò)Hex位置的電路表示來(lái)修復(fù)這個(gè)缺陷。將4個(gè)多邊形邊界帶視為附加單元，如圖1所示。
假設(shè)黑色邊界永久地被黑色棋子部分占據(jù)，并且白色邊界永久地被白色棋子占據(jù)。對(duì)于每個(gè)?？怂蛊宓奈恢茫瑢⑵渑c電路相關(guān)聯(lián)。對(duì)于電路板的每個(gè)位置c，按以下方式分配電阻r，對(duì)此可闡釋如下。
圖1 白色棋子連接白色的兩邊邊界，贏得了比賽Fig.1 The chain of white pieces connects white boundaries， White has won the game
（1）對(duì)于黑色電路，研究可得規(guī)則表述為：
① 如果該位置為空，rB（c）＝1。
②如果該位置被黑色棋子占據(jù)，rB（c）＝0。
③如果該位置被白色棋子占據(jù)，rB（c）＝+∞。
（2）對(duì)于白色電路，研究可得規(guī)則表述為：
① 如果該位置為空，rW（c）＝1。
② 如果該位置被白色棋子占據(jù)，rW（c）＝0。
③ 如果該位置被白色棋子占據(jù)，rW（c）＝+∞。
接下來(lái)，對(duì)于每對(duì)相鄰位置（c1，c2），將電路與電阻相關(guān)聯(lián)，對(duì)此可闡釋如下。
（1）對(duì)于黑色電路，研究可得數(shù)學(xué)計(jì)算公式如下：
（2）對(duì)于白色電路，研究可得數(shù)學(xué)計(jì)算公式如下：
現(xiàn)在向相對(duì)的邊界施加電壓并測(cè)量?jī)烧咧g的總電阻，研究得到的測(cè)試電路詳見(jiàn)圖2。
圖2 黑色棋電路和白色棋電路Fig.2 Black＇s and White＇s circuits
根據(jù)基爾霍夫電流定律，總電阻估算了為連接電路板的兩側(cè)而需要添加到電路板的棋子數(shù)，以及可以完成的方式。為此，定義一個(gè)估值函數(shù)，相應(yīng)計(jì)算公式如下：
其中，如果存在獲勝的黑鏈，E＝0；如果存在獲勝的白鏈，E＝+∞；E越小，表示黑色棋子位置越好，白色棋子位置越差。
已知UCT的公式也會(huì)得出一個(gè)值，讓E和此值按照一定的比例計(jì)算得出一個(gè)可以衡量落子好壞的值，并用此值去尋出最優(yōu)點(diǎn)進(jìn)行落子。
2 評(píng)估策略實(shí)現(xiàn)流程
評(píng)估策略先接受當(dāng)前狀態(tài)的棋盤(pán)，根據(jù)棋盤(pán)上棋子情況選出所有可走棋子，用電阻電路評(píng)估策略選出對(duì)已方較為有利的可走棋子，而且每個(gè)可走的棋子點(diǎn)都由評(píng)估策略算出權(quán)值，而后判斷當(dāng)前選出的可走棋子個(gè)數(shù)，如果小于30，選用α-β剪枝算法得出最優(yōu)點(diǎn)行棋，否則，選用UCT算法得出最優(yōu)點(diǎn)行棋，從而轉(zhuǎn)入輸出環(huán)節(jié)操作。分析后可得設(shè)計(jì)步驟如圖3所示。
圖3 評(píng)估策略流程圖Fig.3 The flow chart of evaluation strategy
3 ?？怂蛊褰换ソ缑嬖O(shè)計(jì)與實(shí)現(xiàn)
3.1 海克斯棋棋譜標(biāo)準(zhǔn)簡(jiǎn)介
參照?？怂蛊迤遄V標(biāo)準(zhǔn)可知［2］，海克斯棋盤(pán)由11×11個(gè)六邊形單元格組成，如圖4所示，坐標(biāo)原點(diǎn)位于左下角，橫坐標(biāo)從 A到K，縱坐標(biāo)從1到11。
圖4 ?？怂蛊迤灞P(pán)Fig.4 Hex chess board
在此基礎(chǔ)上，將給出海克斯棋棋譜的具體要求如下：棋譜文件為純文本文件，文件名的格式為：“HEX-先手參賽隊(duì) R vs后手參賽隊(duì) B-先（后）手勝-比賽時(shí)間地點(diǎn)-賽事名稱”，文件的擴(kuò)展名為txt。棋譜中的所有指令和定界符號(hào)的字符都應(yīng)是英文輸入法輸入的字符，參賽隊(duì)名等參數(shù)也可以使用中文漢字，棋譜所采用的字符集為GB2312，?？怂蛊遄V輸出格式樣例如下：
｛［HEX］［先手參賽隊(duì) R］［后手參賽隊(duì) B］［先手勝］［2017.07.29 14：00 重慶］［2017 CCGC］； R（E，7）；B（E，6）；R（F，7）；B（G，7）；R（D，6）；B（F，6）；R（C，6）；B（G，6）｝
3.2 交互界面的實(shí)現(xiàn)效果
界面程序能夠?qū)崿F(xiàn)基本的人人交互博弈、人機(jī)交互博弈以及AI與AI交互博弈，其中的人人交互博弈界面效果如圖5所示，而且也能夠?qū)С鰳?biāo)準(zhǔn)化棋譜，棋譜效果如圖6所示。
圖5 交互博弈界面效果Fig.5 Interactive game interface effect
圖6 棋譜Fig.6 Chess
4 實(shí)驗(yàn)結(jié)果與分析
本文將基于UCT、α-β剪枝和電阻電路評(píng)估函數(shù)的?？怂蛊宄绦蚺c基于UCT的海克斯棋程序進(jìn)行了對(duì)弈。測(cè)試50局，各先手25局，后手25局。測(cè)試結(jié)果見(jiàn)表1。
表1 對(duì)弈比賽結(jié)果統(tǒng)計(jì)Tab.1 Game result statistics
實(shí)驗(yàn)表明，改進(jìn)后的程序勝率很大，證實(shí)了本程序改進(jìn)的有效性。對(duì)BistuHex2程序算法的修改能夠提高算法搜索精確度，在一定程度上增加了找到最優(yōu)落子坐標(biāo)的概率。通過(guò)加大α-β剪枝算法搜索的深度，以及更改UCT搜索可走棋子的個(gè)數(shù)可以讓搜索更加準(zhǔn)確，從而大幅提升了算法效率。
5 結(jié)束語(yǔ)
通過(guò)對(duì)之前僅用UCT算法的程序進(jìn)行了改進(jìn)，根據(jù)α-β剪枝算法的特點(diǎn)與UCT和電阻電路評(píng)估策略合理結(jié)合，很好地提高了最優(yōu)點(diǎn)的搜索效率。但是本程序并沒(méi)有體現(xiàn)深度學(xué)習(xí)的算法及思路，在今后的工作中，研究將會(huì)繼續(xù)豐富界面程序功能，添加更為人性化的交互界面，學(xué)習(xí)參考Alpha Go和Alpha Zero思想與方法，旨在進(jìn)一步完善?？怂蛊宄绦?。
猜你喜歡
人到晚年宜“剪枝”保健醫(yī)苑(2022年5期)2022-06-10 07:47:22 第六章 珀克斯的生日瘋狂英語(yǔ)·新讀寫(xiě)(2021年11期)2021-11-24 10:21:11 ?？怂箍?7.5億美元收購(gòu)Infor EAM智能制造(2021年4期)2021-11-14 18:56:41 基于YOLOv4-Tiny模型剪枝算法成都信息工程大學(xué)學(xué)報(bào)(2021年6期)2021-02-12 03:00:54 充分滿足K歌電影兩大需求 Linx(林克斯)CRMS-SERIES 5.1音響系統(tǒng)家庭影院技術(shù)(2020年12期)2021-01-18 03:26:50 馬丁的夢(mèng)幻象棋之旅之得到棋譜小學(xué)生學(xué)習(xí)指導(dǎo)(高年級(jí))(2019年11期)2019-11-11 01:34:20 圍棋棋譜的著作權(quán)問(wèn)題探析視聽(tīng)(2018年11期)2018-04-02 15:52:45 剪枝天津詩(shī)人(2017年2期)2017-03-16 03:09:39 Glaucus/格勞克斯 GL609（DLCS01A）世界汽車(2016年8期)2016-09-28 12:15:44 一種面向不平衡數(shù)據(jù)分類的組合剪枝方法計(jì)算機(jī)工程(2014年6期)2014-02-28 01:26:33
張志禮，丁 濛，段金龍，羅鋒駿，勾亮亮
（北京信息科技大學(xué)計(jì)算機(jī)學(xué)院，北京100101）
0 引 言
?？怂蛊澹?］，亦稱六貫棋，最初是在丹麥報(bào)紙Politiken發(fā)表的一篇文章里出現(xiàn)，當(dāng)時(shí)稱為Polygon。1948年，John Nash卻又將其重新獨(dú)立發(fā)明出來(lái)，而熱衷于此的玩家們隨即就將其稱作Nash。稍后于1952年P(guān)arker Brothers發(fā)行了一個(gè)版本，將其稱為Hex，從此這個(gè)名字就固定了下來(lái)。六貫棋是在六邊形格的棋盤(pán)上競(jìng)技的圖版游戲，亦是數(shù)學(xué)游戲，通常使用10×10或11×11的菱形棋盤(pán)，而John Nash采用的卻是14×14的棋盤(pán)。
?？怂蛊宓囊?guī)則為：
（1）由2個(gè)人共同參與，棋盤(pán)為平行四邊形，有2種顏色，通常是紅、藍(lán)或黑、白。4個(gè)邊平行填上兩方的顏色。
（2）雙方輪流走棋，先后手自行選擇，每次只能下一個(gè)棋子，每次占領(lǐng)一處空白格，在空白格放上自己顏色的棋子。
（3）整個(gè)比賽中，雙方均不能吃掉對(duì)方或已方的棋子。
（4）最先將棋盤(pán)屬于自己的顏色的邊連成一線的一方為勝。
在棋類博弈比賽中沒(méi)有統(tǒng)一的棋盤(pán)和棋譜格式，為了能夠標(biāo)準(zhǔn)化導(dǎo)出棋譜并保留博弈數(shù)據(jù)，2018年中國(guó)大學(xué)生計(jì)算機(jī)博弈大賽為每種棋類項(xiàng)目發(fā)布了統(tǒng)一標(biāo)準(zhǔn)［2］，本次研究則嚴(yán)格按照中國(guó)大學(xué)生計(jì)算機(jī)博弈大賽棋譜標(biāo)準(zhǔn)說(shuō)明書(shū)要求編寫(xiě)了?？怂蛊宀┺能浖?。此外，比賽程序BistuHex2提出了UCT、α-β剪枝和電阻電路評(píng)估策略配合使用的搜索方法，在往屆中國(guó)大學(xué)生計(jì)算機(jī)博弈比賽中取得優(yōu)異成績(jī)。對(duì)此，本文擬展開(kāi)研究論述如下。
1 評(píng)估策略設(shè)計(jì)與應(yīng)用
?？怂蛊瀚@勝的方法是將棋盤(pán)屬于自己的顏色的邊連成一線，而且每個(gè)棋子的行棋都要考慮攻防兼?zhèn)?，因此雙方每次落子都至關(guān)重要，棋類游戲的搜索算法大同小異，這時(shí)，一個(gè)較優(yōu)的評(píng)估策略，及其與搜索算法的合理結(jié)合，則成了決勝的關(guān)鍵。BistuHex2程序是利用UCT算法、α-β剪枝算法與電阻電路評(píng)估策略［3］進(jìn)行分階段式配合使用，評(píng)估策略是利用電路電阻的特點(diǎn)，將其用來(lái)作為海克斯棋局面的評(píng)估函數(shù)，以棋局的局面特征作為輸入，評(píng)估值及較優(yōu)的可走棋子作為輸出，為搜索算法進(jìn)一步縮小搜索范圍，并提供判斷局面優(yōu)劣的依據(jù)。
1.1 UCT、α-β剪枝與評(píng)估策略分階段式結(jié)合
UCT算法（Upper Confidence Bound Apply to Tree），即上限置信區(qū)間算法，是一種博弈樹(shù)搜索算法，該算法將蒙特卡洛樹(shù)搜索（Monte—Carlo Tree Search，MCTS）方法與UCB公式結(jié)合，在超大規(guī)模博弈樹(shù)的搜索過(guò)程中相對(duì)于傳統(tǒng)的搜索算法有著時(shí)間和空間方面的優(yōu)勢(shì)。之前使用的程序僅基于UCT，搜索時(shí)間長(zhǎng)、范圍廣，而且不準(zhǔn)確，當(dāng)前使用程序?yàn)锽istuHex2，則是將UCT、α-β剪枝與電阻電路評(píng)估策略進(jìn)行分階段式結(jié)合。
通過(guò)上述評(píng)估算法可以得出許多可以減少已方電阻的點(diǎn)。將這些點(diǎn)作為UCT模擬的對(duì)象，就避免了盲目搜索，極大地提高了搜索效率。在開(kāi)局時(shí)，需要搜索的點(diǎn)很多，用UCT模擬的效果很差，因此在開(kāi)局的時(shí)候采用α-β剪枝算法與基于電阻電路評(píng)估策略結(jié)合的方法，使得程序在開(kāi)局時(shí)依然可以非常強(qiáng)大。當(dāng)評(píng)估算法獲得的點(diǎn)較少時(shí)，再采用UCT搜索算法與基于電阻電路評(píng)估策略的結(jié)合，可以在后期有效地把控全局。
1.2 電阻電路評(píng)估策略
評(píng)估策略是用電路和電阻的思路結(jié)合海克斯棋的特點(diǎn)進(jìn)行設(shè)計(jì)，對(duì)?？怂蛊鍋?lái)說(shuō)，一個(gè)合理的估值函數(shù)應(yīng)該估計(jì)黑棋方建立一條獲勝黑鏈的程度比白棋方要建立一條獲勝的白鏈更接近。
衡量玩家建立鏈條的接近程度的一種流行方法是計(jì)算該玩家需要添加的最小數(shù)量的棋子以連接棋盤(pán)的兩側(cè)，但是這種方法沒(méi)有考慮潛在鏈的數(shù)量。試圖通過(guò)Hex位置的電路表示來(lái)修復(fù)這個(gè)缺陷。將4個(gè)多邊形邊界帶視為附加單元，如圖1所示。
假設(shè)黑色邊界永久地被黑色棋子部分占據(jù)，并且白色邊界永久地被白色棋子占據(jù)。對(duì)于每個(gè)?？怂蛊宓奈恢茫瑢⑵渑c電路相關(guān)聯(lián)。對(duì)于電路板的每個(gè)位置c，按以下方式分配電阻r，對(duì)此可闡釋如下。
圖1 白色棋子連接白色的兩邊邊界，贏得了比賽Fig.1 The chain of white pieces connects white boundaries， White has won the game
（1）對(duì)于黑色電路，研究可得規(guī)則表述為：
① 如果該位置為空，rB（c）＝1。
②如果該位置被黑色棋子占據(jù)，rB（c）＝0。
③如果該位置被白色棋子占據(jù)，rB（c）＝+∞。
（2）對(duì)于白色電路，研究可得規(guī)則表述為：
① 如果該位置為空，rW（c）＝1。
② 如果該位置被白色棋子占據(jù)，rW（c）＝0。
③ 如果該位置被白色棋子占據(jù)，rW（c）＝+∞。
接下來(lái)，對(duì)于每對(duì)相鄰位置（c1，c2），將電路與電阻相關(guān)聯(lián)，對(duì)此可闡釋如下。
（1）對(duì)于黑色電路，研究可得數(shù)學(xué)計(jì)算公式如下：
（2）對(duì)于白色電路，研究可得數(shù)學(xué)計(jì)算公式如下：
現(xiàn)在向相對(duì)的邊界施加電壓并測(cè)量?jī)烧咧g的總電阻，研究得到的測(cè)試電路詳見(jiàn)圖2。
圖2 黑色棋電路和白色棋電路Fig.2 Black＇s and White＇s circuits
根據(jù)基爾霍夫電流定律，總電阻估算了為連接電路板的兩側(cè)而需要添加到電路板的棋子數(shù)，以及可以完成的方式。為此，定義一個(gè)估值函數(shù)，相應(yīng)計(jì)算公式如下：
其中，如果存在獲勝的黑鏈，E＝0；如果存在獲勝的白鏈，E＝+∞；E越小，表示黑色棋子位置越好，白色棋子位置越差。
已知UCT的公式也會(huì)得出一個(gè)值，讓E和此值按照一定的比例計(jì)算得出一個(gè)可以衡量落子好壞的值，并用此值去尋出最優(yōu)點(diǎn)進(jìn)行落子。
2 評(píng)估策略實(shí)現(xiàn)流程
評(píng)估策略先接受當(dāng)前狀態(tài)的棋盤(pán)，根據(jù)棋盤(pán)上棋子情況選出所有可走棋子，用電阻電路評(píng)估策略選出對(duì)已方較為有利的可走棋子，而且每個(gè)可走的棋子點(diǎn)都由評(píng)估策略算出權(quán)值，而后判斷當(dāng)前選出的可走棋子個(gè)數(shù)，如果小于30，選用α-β剪枝算法得出最優(yōu)點(diǎn)行棋，否則，選用UCT算法得出最優(yōu)點(diǎn)行棋，從而轉(zhuǎn)入輸出環(huán)節(jié)操作。分析后可得設(shè)計(jì)步驟如圖3所示。
圖3 評(píng)估策略流程圖Fig.3 The flow chart of evaluation strategy
3 ?？怂蛊褰换ソ缑嬖O(shè)計(jì)與實(shí)現(xiàn)
3.1 海克斯棋棋譜標(biāo)準(zhǔn)簡(jiǎn)介
參照?？怂蛊迤遄V標(biāo)準(zhǔn)可知［2］，海克斯棋盤(pán)由11×11個(gè)六邊形單元格組成，如圖4所示，坐標(biāo)原點(diǎn)位于左下角，橫坐標(biāo)從 A到K，縱坐標(biāo)從1到11。
圖4 ?？怂蛊迤灞P(pán)Fig.4 Hex chess board
在此基礎(chǔ)上，將給出海克斯棋棋譜的具體要求如下：棋譜文件為純文本文件，文件名的格式為：“HEX-先手參賽隊(duì) R vs后手參賽隊(duì) B-先（后）手勝-比賽時(shí)間地點(diǎn)-賽事名稱”，文件的擴(kuò)展名為txt。棋譜中的所有指令和定界符號(hào)的字符都應(yīng)是英文輸入法輸入的字符，參賽隊(duì)名等參數(shù)也可以使用中文漢字，棋譜所采用的字符集為GB2312，?？怂蛊遄V輸出格式樣例如下：
｛［HEX］［先手參賽隊(duì) R］［后手參賽隊(duì) B］［先手勝］［2017.07.29 14：00 重慶］［2017 CCGC］； R（E，7）；B（E，6）；R（F，7）；B（G，7）；R（D，6）；B（F，6）；R（C，6）；B（G，6）｝
3.2 交互界面的實(shí)現(xiàn)效果
界面程序能夠?qū)崿F(xiàn)基本的人人交互博弈、人機(jī)交互博弈以及AI與AI交互博弈，其中的人人交互博弈界面效果如圖5所示，而且也能夠?qū)С鰳?biāo)準(zhǔn)化棋譜，棋譜效果如圖6所示。
圖5 交互博弈界面效果Fig.5 Interactive game interface effect
圖6 棋譜Fig.6 Chess
4 實(shí)驗(yàn)結(jié)果與分析
本文將基于UCT、α-β剪枝和電阻電路評(píng)估函數(shù)的?？怂蛊宄绦蚺c基于UCT的海克斯棋程序進(jìn)行了對(duì)弈。測(cè)試50局，各先手25局，后手25局。測(cè)試結(jié)果見(jiàn)表1。
表1 對(duì)弈比賽結(jié)果統(tǒng)計(jì)Tab.1 Game result statistics
實(shí)驗(yàn)表明，改進(jìn)后的程序勝率很大，證實(shí)了本程序改進(jìn)的有效性。對(duì)BistuHex2程序算法的修改能夠提高算法搜索精確度，在一定程度上增加了找到最優(yōu)落子坐標(biāo)的概率。通過(guò)加大α-β剪枝算法搜索的深度，以及更改UCT搜索可走棋子的個(gè)數(shù)可以讓搜索更加準(zhǔn)確，從而大幅提升了算法效率。
5 結(jié)束語(yǔ)
通過(guò)對(duì)之前僅用UCT算法的程序進(jìn)行了改進(jìn)，根據(jù)α-β剪枝算法的特點(diǎn)與UCT和電阻電路評(píng)估策略合理結(jié)合，很好地提高了最優(yōu)點(diǎn)的搜索效率。但是本程序并沒(méi)有體現(xiàn)深度學(xué)習(xí)的算法及思路，在今后的工作中，研究將會(huì)繼續(xù)豐富界面程序功能，添加更為人性化的交互界面，學(xué)習(xí)參考Alpha Go和Alpha Zero思想與方法，旨在進(jìn)一步完善?？怂蛊宄绦?。
猜你喜歡
保健醫(yī)苑(2022年5期)2022-06-10 07:47:22
瘋狂英語(yǔ)·新讀寫(xiě)(2021年11期)2021-11-24 10:21:11
智能制造(2021年4期)2021-11-14 18:56:41
成都信息工程大學(xué)學(xué)報(bào)(2021年6期)2021-02-12 03:00:54
家庭影院技術(shù)(2020年12期)2021-01-18 03:26:50
小學(xué)生學(xué)習(xí)指導(dǎo)(高年級(jí))(2019年11期)2019-11-11 01:34:20
視聽(tīng)(2018年11期)2018-04-02 15:52:45
天津詩(shī)人(2017年2期)2017-03-16 03:09:39
世界汽車(2016年8期)2016-09-28 12:15:44
計(jì)算機(jī)工程(2014年6期)2014-02-28 01:26:33
