基于python的棋類教學系統設計實現

宋向飛 米思琦

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

【關鍵詞】五子棋；UCT；Python；Tkinter

中圖分類號： TP311.1-4；G642 文獻標識碼： 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》中指出，機器學習就是指“計算機利用經驗自動改善系統自身性能的行為”。人工智能的研究和實現是邏輯科學和思維科學的應用的結合，是一個被廣泛應用和深入研究的分支。從思維的角度來看，人工智能是邏輯思維與靈感思維相互作用的綜合設計結果。

2 系統分析

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

（1）友好便捷的人機交互系統

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

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

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

2.2 五子棋教學系統的主要功能模塊

如上圖1所示。

3 算法分析

3.1 UCT算法

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

（1）樹內選擇策略

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

N=bd（1）

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

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

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

（2）缺省仿真策略

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

此時，棋盤中棋子狀態明確，有嚴格對應的位置坐標、次序和對應棋手，可以容易算出獲勝方。當葉子節點的評估值為1時，黑色獲勝，而當它為0時，白色獲勝[3]。

（3）仿真結果回傳

通過仿真算法，所有葉節點得到相應的V和T值，UCT算法通過結果返回將V和T值更新到路徑上的所有內部節點。

3.2 主算法設計

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

在上圖4中，是否存在可連五落子點指的是，己方或對手方在下一步棋可完成連五局勢，即必勝。

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

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

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

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

（1）所選落子點為空子，狀態為-1；

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

（3）所選落子點三個范圍內有棋子已經布下（不論對方己方）。

4 結果分析

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

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

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

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

本文設計并實現了五子棋象棋教學系統，與傳統算法相關。

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

【參考文獻】

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

[2]袁松鶴，薛海峰.基于云計算的終身學習平臺構建研究[J].現代遠距離教育，2012（05）.

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

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

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