宋向飛 米思琦

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

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

中圖分類號： TP311.1-4；G642 文獻標(biāo)識碼： A 文章編號： 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》中指出，機器學(xué)習(xí)就是指“計算機利用經(jīng)驗自動改善系統(tǒng)自身性能的行為”。人工智能的研究和實現(xiàn)是邏輯科學(xué)和思維科學(xué)的應(yīng)用的結(jié)合，是一個被廣泛應(yīng)用和深入研究的分支。從思維的角度來看，人工智能是邏輯思維與靈感思維相互作用的綜合設(shè)計結(jié)果。

2 系統(tǒng)分析

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

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

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

（3）注冊界面，提供注冊信息（賬號、密碼）的輸入框；

系統(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算法是一種特殊的蒙特卡羅搜索算法，它有三個部分：樹選擇策略，默認模擬策略和模擬結(jié)果。

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

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

N=bd（1）

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

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

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

（2）缺省仿真策略

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

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

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

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

3.2 主算法設(shè)計

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

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

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

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

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

備選落子點所具備的特點：

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

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

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

4 結(jié)果分析

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

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

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

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

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

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

【參考文獻】

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

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

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

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

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