[發明專利]愛恩斯坦棋博弈系統

在審

• 申請號: 201710735661.2
• 申請日: 2017-08-24
• 公開（公告）號: CN107684714A
• 公開（公告）日: 2018-02-13
• 發明（設計）人: 李學俊;王春;陸夢軒
• 申請（專利權）人: 安徽大學
• 主分類號: A63F3/00
• 分類號: A63F3/00
• 代理公司: 南京知識律師事務所32207
• 代理人: 高玲玲

技術領域

本發明屬于電子棋類游戲技術領域，特別涉及一種利用信心上限樹UCT算法對其進行更新和選擇節點的愛恩斯坦棋博弈系統。

背景技術

愛恩斯坦棋在2005年被用作愛因斯坦年的官方游戲進入到公眾視野，它是由德國一個應用數學方向的教授Ingo在2004年根據他之前設計的一個需要很大概率的足球小游戲設計的，原名是EinStein würfelt nicht！，中文意思是愛因斯坦不投骰子。游戲的名字的來源是因為愛因斯坦的一句著名的話：我確信上帝不會投骰子。

規則簡介：棋盤為5*5的方格，紅方的出發區在棋盤的左上角，藍方的出發區在棋盤的右下角。初始紅方與藍方各有6枚棋子對應數字1～6且在出發區隨意擺放。走棋的過程中，雙方交替擲骰子，然后走動匹配骰子數的棋子。若匹配的棋子被吃掉，那么走動與篩子數的相近棋子。雙方棋子每次只能走動一格，紅方走棋的規則為向右、向下、向右下，藍方走棋的規則為向左、向上、向左上。當己方的棋子到達對方的角位置，或消滅對方全部棋子，那么己方獲勝，對弈結果只有勝負，沒有和棋。

目前愛恩斯坦棋所采用的技術，多為Alpha-Beta與期望極大極小算法。棋類游戲通常是根據當前對弈局面，對存在的可能情況向下進行模擬，由此構造出一顆模擬的樹狀圖，稱之為博弈樹。該算法是對當前棋局節點的估值，因此必有一個估值函數。通過估值函數將不同的棋盤狀態量化，通過比較量化后的數字來判斷落子的好壞。愛恩斯坦棋屬于隨機特征的博弈，每次行棋通過輪流擲骰子來決定走動的棋子，因此對于愛恩斯坦棋來說傳統的方法并不完全適用。同時愛恩斯坦棋在開局時紅方與藍方的棋子可以在出發區隨意擺放，因此估值函數的設計相對比較復雜。

蒙特卡羅方法，是以概率統計為指導的計算方法，這種方法是對當前棋盤所有可能出現的落子方式進行統計可以解決愛恩斯坦棋難估值且隨機性強的問題。為了實現概率估值的搜索方式，使用信心上限樹算法亦稱UCT(Upper Confidence Tree)算法。作為蒙特卡洛算法的一種延伸，UCT算法通過對博弈樹的落子進行大量快速模擬，計算出UCB(Upper Confidence Bound)值，通過選擇最優的UCB節點作為最佳走法。

綜上所述目前的愛恩斯坦棋博弈算法存在的問題，其一估值函數不好設計，其二傳統的博弈樹并不完全適用。

發明內容

本發明目的是針對現有技術的缺陷，提出了一種愛恩斯坦棋游戲系統，該系統采用信心上限樹算法進行博弈樹搜索。

為了實現上述目的，本發明采用以下技術方案：一種愛恩斯坦棋博弈系統，包括：輸入裝置、外部顯示裝置和內部處理單元；

其中所述輸入裝置用于用戶設置參數和對弈過程中的策略選擇，并且與內部處理單元建立通訊，進行游戲或者選擇自動測試；

所述外部顯示裝置用于和內部處理單元建立通訊，實時顯示棋盤上的狀態信息和對弈過程；

內部處理單元用于采用了智能博弈技術實現了愛恩斯坦棋的智能化，實現智能博弈技術之間的自動對弈，以及人與智能博弈技術之間的對弈。

進一步的，內部處理單元包括：

搜索模塊，采用UCT算法，利用蒙特卡洛方法對當前棋盤信息進行搜索和模擬，并根據UCB公式進行節點的選擇，選擇出最優的落子方式；

存儲模塊：將棋盤上的信息利用5×5的數組進行存儲，當棋盤上棋子發生變化時，通過改變對應數組的數據值實現對棋盤信息的更新；

信息交互模塊：用于實現輸入裝置、外部顯示裝置和內部處理單元之間的數據傳輸，并對愛恩斯坦棋系統進行控制；

互動模塊：通過在外部顯示裝置彈出選擇對話框來讓用戶進行游戲模式選擇，用于人人對弈、人機對弈與機機對弈的選擇入口。

進一步的，基于UCT算法的搜索和模擬包括以下步驟：

(1)選擇節點：對愛恩斯坦棋模擬產生的博弈樹，從根節點開始選擇UCB值最大的子節點，一直到葉子節點；

(2)展開節點：父節點在選擇子節點時，如果當前子節點沒有葉節點，對當前子節點的模擬，達到了設定的次數，那么為該節點的拓展子節點；

(3)模擬棋局：對所有的拓展節點采取同樣的方式，進行棋盤的模擬下棋，直到結束為止，然后統計節點的數據；

(4)回饋更新：根據模擬棋局得到的數據，計算博弈樹中節點的值，將模擬棋局的勝負結果和訪問次數沿著父節點反饋更新整個搜索樹。

進一步的，步驟1中節點的選擇，采用以下步驟：

(1)在節點中加一變量‘dice’，初值為0；