[發明專利]一種基于強化學習的愛恩斯坦棋博弈算法

在審

• 申請號: 201910375250.6
• 申請日: 2019-05-07
• 公開（公告）號: CN110119804A
• 公開（公告）日: 2019-08-13
• 發明（設計）人: 袁儀馳;吳蕾;姚超超;李學俊;陸夢宣;沈恒恒
• 申請（專利權）人: 安徽大學
• 主分類號: G06N3/04
• 分類號: G06N3/04;G06N3/08;A63F11/00
• 代理公司: 合肥方舟知識產權代理事務所(普通合伙) 34158
• 代理人: 朱榮

本發明公開了一種愛恩斯坦棋中基于深度強化學習的自學習博弈算法，將BP神經網絡運用到棋盤的價值評估方法以及在蒙特卡洛樹搜索算法的動作選擇策略中，借助強化學習方法自對弈學習規則，對棋盤的特征進行學習并逐漸調整網絡參數，使得BP神經網絡對于棋盤的價值評估以及下棋動作的策略計算逐漸準確，從而使整個博弈算法的性能逐漸提升。本發明將兩個BP神經網絡分別作為愛恩斯坦棋的價值估值函數和行為策略函數，將強化學習算法作為調整BP神經網絡參數的進化機制，解決了目前愛恩斯坦棋訓練集的水平受到人類水平限制的缺陷，提高了愛恩斯坦棋博弈水平的上限。

技術領域

本發明屬于棋類游戲機器博弈的研究領域，特別涉及一種基于強化學習的愛恩斯坦棋博弈算法。

背景技術

人工神經網絡(Artificial Neural Network，即ANN)，是20世紀80年代以來人工智能領域興起的研究熱點。神經網絡是一種運算模型，由大量的節點(或稱神經元)之間交互聯接構成。每個節點表示一種特殊的處理函數，稱為激活函數(activation function)。每兩個節點間的連接都代表一個對于通過該連接信號的加權值，稱之為權重(weight)，這相當于人工神經網絡的學習經驗。網絡的輸出則依網絡的連接方式，權重值和激勵函數的不同而不同。而網絡自身通常都是對自然界某種算法或者函數的逼近，也可能是對一種邏輯策略的表達。

強化學習(reinforcement learning)是一種重要的機器學習方法，在智能控制機器人及分析預測等領域有許多應用。強化學習是智能體(Agent)以“試錯”、“反思”的方式進行學習，通過與環境進行交互獲得的獎賞指導行為，目標是使智能體獲得最大的獎賞。強化學習不同于連接主義學習中的監督學習，主要表現在學習信號上。強化學習中由環境提供的強化信號是已產生動作的好壞作為一種評價(通常為標量信號)，而不是指示強化學習系統RLS(reinforcement learning system)如何去產生正確的動作。由于外部環境提供的信息很少，RLS必須通過與環境的多次交互進行學習。通過這種方式，RLS在行動-評價的環境中獲得知識，改進行動方案以適應環境。

提升博弈系統的智能水平的基本思路是提高估值精度和提升搜索效率。在搜索方面，博弈樹搜索(Monte-Carlo Tree Search，簡稱MCTS)算法可以較好地解決博弈游戲中隨機性強的問題。MCTS算法是利用搜索結果自引導搜索方向的統計方法，有選擇地建立一棵樹，這棵樹會往價值更大的方向生長。

愛恩斯坦棋博弈規則如下：

1.棋盤為5×5的方格形棋盤，方格為棋位，左上角為紅方出發區；右下角為藍方出發區，如圖1所示；

2.紅藍方各有6枚方塊形棋子，分別標有數字1—6。開局時雙方棋子在出發區的棋位可以隨意擺放；

3.雙方輪流擲骰子，然后走動與骰子顯示數字相對應的棋子。如果相對應的棋子已從棋盤上移出，便可走動大于或小于此數字的并與此數字最接近的棋子；

4.紅方棋子走動方向為向右、向下、向右下，每次走動一格；藍方棋子走動方向為向左、向上、向左上，每次走動一格；

5.如果在棋子走動的目標棋位上有棋子，則要將該棋子從棋盤上移出(吃掉)。有時吃掉本方棋子也是一種策略，因為可以增加其它棋子走動的機會與靈活性；

6.率先到達對方出發區角點或將對方棋子全部吃掉的一方獲勝；

7.對弈結果只有勝負，沒有和棋。

8.每盤每方用時3分鐘，超時判負；每輪雙方對陣最多7盤，輪流先手(甲方一四五盤先手，乙方二三六七盤先手)，兩盤中間不休息，先勝4盤為勝方。