宋向飛 米思琦

【摘 要】本文主要研究和討論了國際象棋比賽的發(fā)展趨勢(shì)，UCT算法的特點(diǎn)以及tkinter的設(shè)計(jì)和實(shí)現(xiàn)。從而詳細(xì)介紹在基于Python的五子棋教學(xué)系統(tǒng)的設(shè)計(jì)與實(shí)現(xiàn)過程中，所依賴的開發(fā)環(huán)境和語言、系統(tǒng)需求、設(shè)計(jì)思路和相關(guān)算法支持等等，最終實(shí)現(xiàn)了實(shí)現(xiàn)人機(jī)游戲的單機(jī)五子棋教學(xué)系統(tǒng)。

【關(guān)鍵詞】五子棋；UCT；Python；Tkinter

中圖分類號(hào)： TP311.1-4；G642 文獻(xiàn)標(biāo)識(shí)碼： A 文章編號(hào)： 2095-2457（2018）30-0194-003

DOI：10.19694/j.cnki.issn2095-2457.2018.30.085

Design and implementation of Chess Teaching System Based on Python

SONG Xiang-fei MI Si-qi

（Hunan Normal University， Hunan Changsha 410006， China）

【Abstract】In this paper， the development trend of chess games， the characteristics of UCT algorithm and the design and implementation of Tkinter are deeply studied and discussed，and then the development environment， language， system requirements， design ideas and correlations that I relyon in the design and implementation of the Gobang teaching system based on Python are introduced in detail.Algorithm support and so on， and ultimately achieve the human-machine chess single player Gobang teaching system.

【Key words】Gobang； UCT； Python； Tkinter

1 人工智能的概念

《Machine Learning》中指出，機(jī)器學(xué)習(xí)就是指“計(jì)算機(jī)利用經(jīng)驗(yàn)自動(dòng)改善系統(tǒng)自身性能的行為”。人工智能的研究和實(shí)現(xiàn)是邏輯科學(xué)和思維科學(xué)的應(yīng)用的結(jié)合，是一個(gè)被廣泛應(yīng)用和深入研究的分支。從思維的角度來看，人工智能是邏輯思維與靈感思維相互作用的綜合設(shè)計(jì)結(jié)果。

2 系統(tǒng)分析

2.1 五子棋圍棋教學(xué)系統(tǒng)對(duì)用戶體驗(yàn)有影響，主要集中在以下幾個(gè)方面：

（1）友好便捷的人機(jī)交互系統(tǒng)

（2）登錄界面，提供賬號(hào)密碼的輸入框，忘記密碼的按鈕以及注冊(cè)界面的入口；

（3）注冊(cè)界面，提供注冊(cè)信息（賬號(hào)、密碼）的輸入框；

系統(tǒng)主界面，左側(cè)放置15×15大小的棋盤，以棕色為底色，右側(cè)設(shè)置菜單欄，包括開始、重置、悔棋、保存＼查看棋譜、玩家先后手選擇、電腦算法選擇。

2.2 五子棋教學(xué)系統(tǒng)的主要功能模塊

如上圖1所示。

3 算法分析

3.1 UCT算法

UCT算法（Upper Confidence Bound Apply to Tree），上限置信區(qū)間算法，UCT算法是一種特殊的蒙特卡羅搜索算法，它有三個(gè)部分：樹選擇策略，默認(rèn)模擬策略和模擬結(jié)果。

（1）樹內(nèi)選擇策略

如圖所示，在傳統(tǒng)的搜索樹技術(shù)中，當(dāng)搜索深度參數(shù)為d且搜索深度達(dá)到d時(shí)，評(píng)估值通過評(píng)估函數(shù)獲得，并且搜索算法基于所有評(píng)估值找到具有最大值的分支。在搜索深度相同的情況下獲得評(píng)估值的模式中，設(shè)置搜索深度[1]度數(shù)為d，分支系數(shù)為b，搜索樹中葉子節(jié)點(diǎn)的數(shù)量為N，關(guān)系式由式（1）表示。

N=bd（1）

與傳統(tǒng)的搜索算法相比，UCT算法在不同搜索分支中的不同搜索深度上存在最大差異。

UCT 算法在不同的深度獲取評(píng)估值。根據(jù)算法具體設(shè)計(jì)邏輯，在執(zhí)行過程中，先評(píng)估分支的“希望”值，值越高，然后UCT算法的搜索深度越深（遠(yuǎn)大于d），結(jié)果能較大限度的擬合最優(yōu)解[2]；相反，值越低，丟棄的可能性越大。

從根節(jié)點(diǎn)開始進(jìn)行搜索并由其算法得到評(píng)估值，您可以知道葉節(jié)點(diǎn)的到達(dá)，在每個(gè)非葉節(jié)點(diǎn)n子ni∈ch（n）的過程中，樹選擇策略計(jì)算評(píng)估值ri，并且評(píng)估值可以用作選擇標(biāo)準(zhǔn)，并且選擇子節(jié)點(diǎn)以進(jìn)行下一選擇。ri 的計(jì)算公式見式（2）：

（2）缺省仿真策略

當(dāng)搜索進(jìn)行到葉節(jié)點(diǎn)時(shí)，UCT算法執(zhí)行擴(kuò)展操作（擴(kuò)展）：使用此節(jié)點(diǎn)作為根節(jié)點(diǎn)，可以找到所有允許的和合法的子節(jié)點(diǎn)，并將這些子節(jié)點(diǎn)作為新葉節(jié)點(diǎn)添加到當(dāng)前搜索樹。對(duì)其V值和T值進(jìn)行正確的初始化。應(yīng)當(dāng)注意，UCT算法使用默認(rèn)模擬策略進(jìn)行搜索直到結(jié)束，并且不使用其他評(píng)估函數(shù)來獲得新葉節(jié)點(diǎn)的評(píng)估值。

此時(shí)，棋盤中棋子狀態(tài)明確，有嚴(yán)格對(duì)應(yīng)的位置坐標(biāo)、次序和對(duì)應(yīng)棋手，可以容易算出獲勝方。當(dāng)葉子節(jié)點(diǎn)的評(píng)估值為1時(shí)，黑色獲勝，而當(dāng)它為0時(shí)，白色獲勝[3]。

（3）仿真結(jié)果回傳

通過仿真算法，所有葉節(jié)點(diǎn)得到相應(yīng)的V和T值，UCT算法通過結(jié)果返回將V和T值更新到路徑上的所有內(nèi)部節(jié)點(diǎn)。

3.2 主算法設(shè)計(jì)

由緒論部分分析可知，傳統(tǒng)五子棋算法過于僵硬、套路死板，計(jì)算機(jī)端下棋套路固定，無法根據(jù)棋盤局勢(shì)對(duì)下棋策略做出優(yōu)化，UCT算法用于Go使其發(fā)光，因此本設(shè)計(jì)采用UCT算法作為五子棋的主要算法。在不同的棋局下，使用算法將棋盤上的空子進(jìn)行大量的模擬，再由評(píng)估函數(shù)評(píng)估出勝率最高的若干落子點(diǎn)[4]，保存作為備選項(xiàng)。

在上圖4中，是否存在可連五落子點(diǎn)指的是，己方或?qū)κ址皆谙乱徊狡蹇赏瓿蛇B五局勢(shì)，即必勝。

UCT算法實(shí)現(xiàn)設(shè)當(dāng)前棋盤棋局狀態(tài)（落子位置和對(duì)應(yīng)棋手）為A，根據(jù)棋局狀態(tài)A以及相關(guān)規(guī)則，確定備選落子點(diǎn)，并將這些落子點(diǎn)組成列表B。假設(shè)列表B中的每個(gè)點(diǎn)都是下一步，并以此繼續(xù)模擬下去直到一方獲勝為止。在進(jìn)行模擬時(shí)，由樹內(nèi)選擇策略獲取“期望”，這一“期望”應(yīng)用于搜索深度d的確定，是指當(dāng)算法模擬棋子次數(shù)達(dá)到d時(shí)，UCT算法從評(píng)價(jià)函數(shù)中得到相應(yīng)的權(quán)重值，由不同的搜索深度d，U并且在不同的深度獲取評(píng)估值，“期望”越高，搜索深度越大，求解結(jié)果更加符合最優(yōu)解。根據(jù)評(píng)價(jià)函數(shù)統(tǒng)計(jì)每個(gè)點(diǎn)的勝率，選取勝率最高的那個(gè)點(diǎn)作為落子點(diǎn)[5]。

模擬國際象棋和執(zhí)行統(tǒng)計(jì)贏率的流程圖如圖5所示。A點(diǎn)的最終總比賽達(dá)到6場(chǎng)比賽，勝利4勝，勝率為66.6%。

備選落子點(diǎn)的選取規(guī)則：考慮到Gomoku和Go之間的區(qū)別，在模擬Gobang游戲時(shí)你不需要全范圍的布局。搜索范圍和深度均可適度減小，選取備選落子點(diǎn)的范圍限制在棋盤中棋子一定的半徑范圍內(nèi)，超出這一范圍的落子點(diǎn)不予以考慮。

備選落子點(diǎn)所具備的特點(diǎn)：

（1）所選落子點(diǎn)為空子，狀態(tài)為-1；

（2）所選落子點(diǎn)臨近交叉點(diǎn)有棋子已經(jīng)布下（不論對(duì)方己方）；

（3）所選落子點(diǎn)三個(gè)范圍內(nèi)有棋子已經(jīng)布下（不論對(duì)方己方）。

4 結(jié)果分析

（1）整個(gè)系統(tǒng)運(yùn)行流暢，子菜單和主菜單之間相互連通，可返回；

（2）菜單欄的功能運(yùn)行正常，可以實(shí)現(xiàn)開始、重置、悔棋、保存/查看棋譜功能，個(gè)性化選擇功能；

（3）算法中在運(yùn)用 UCT 時(shí)，可與系統(tǒng)其他部分，如棋譜文件，棋盤文件交互良好，同時(shí)在設(shè)定搜索時(shí)間時(shí)，可以返回搜索深度和模擬次數(shù)；

（4）進(jìn)行多次人機(jī)對(duì)弈實(shí)驗(yàn)，系統(tǒng)運(yùn)行流暢，用戶體驗(yàn)感絕佳，對(duì)弈完成后棋盤數(shù)據(jù)也正確保存進(jìn)棋盤文件，pickle文件同步保存用戶信息。

本文設(shè)計(jì)并實(shí)現(xiàn)了五子棋象棋教學(xué)系統(tǒng)，與傳統(tǒng)算法相關(guān)。

該算法經(jīng)過改進(jìn)，可以獲得更好的用戶體驗(yàn)。目前只著重于系統(tǒng)的搭建，算法的策略有待優(yōu)化，系統(tǒng)界面也較為簡(jiǎn)陋，后續(xù)會(huì)從多角度改進(jìn)算法，優(yōu)化界面，來開發(fā)最大的系統(tǒng)功能。

【參考文獻(xiàn)】

[1]王志水.基于搜索算法的人工智能在五子棋博弈中的應(yīng)用研究[D].青島：中國石油大學(xué)，2006，16-24.

[2]袁松鶴，薛海峰.基于云計(jì)算的終身學(xué)習(xí)平臺(tái)構(gòu)建研究[J].現(xiàn)代遠(yuǎn)距離教育，2012（05）.

[3]張明亮，吳俊，李凡長.五子棋機(jī)器博弈系統(tǒng)評(píng)估函數(shù)的設(shè)計(jì)[J].計(jì)算機(jī)應(yīng)用，2012，32（7）：1969-1972.

[4]王志水.基于搜索算法的人工智能在五子棋博弈中的應(yīng)用研究[D].青島：中國石油大學(xué)，2006，16-24.

[5]李欣茹，王曉霞.對(duì)開放大學(xué)課程體系的分析——以英國開放大學(xué)工商管理專業(yè)群課程體系為例[J].北京廣播電視大學(xué)學(xué).