[發(fā)明專利]一種圍棋上的搜索博弈樹的策略改進方法

有效

• 申請?zhí)枺?/td>: 202110760145.1
• 申請日: 2021-07-06
• 公開（公告）號: CN113377779B
• 公開（公告）日: 2023-10-20
• 發(fā)明（設(shè)計）人: 寧義明;楊木潤;趙闖
• 申請（專利權(quán)）人: 沈陽雅譯網(wǎng)絡(luò)技術(shù)有限公司
• 主分類號: G06F16/22
• 分類號: G06F16/22;G06F16/2457;G06F16/248
• 代理公司: 沈陽新科知識產(chǎn)權(quán)代理事務(wù)所(特殊普通合伙) 21117
• 代理人: 李曉光

1.一種圍棋上的搜索博弈樹的策略改進方法，其特征在于包括以下步驟：

1)以當(dāng)前狀態(tài)為根節(jié)點建立搜索樹，樹建立完成，其它所有節(jié)點隱式給出；

2)選擇根節(jié)點的一個孩子節(jié)點進行模擬，如果有孩子節(jié)點還沒有被模擬過，那么從根節(jié)點的孩子節(jié)點里面隨機選擇一個孩子進行模擬；如果所有孩子節(jié)點都被模擬過至少一次，那么選擇UCB分樹最高的孩子節(jié)點；

3)從選中的孩子節(jié)點開始模擬一直到葉子節(jié)點結(jié)束；模擬策略結(jié)合均勻采樣和極小極大策略；

4)將模擬最后的結(jié)果反向傳播到根節(jié)點，路徑上所有葉子的動作價值函數(shù)Q值和N值被更新；

5)重復(fù)步驟1)-4)多次，最后選擇的結(jié)果為UCB中利用項分?jǐn)?shù)最高的節(jié)點。

2.根據(jù)權(quán)利要求1所述的圍棋上的搜索博弈樹的策略改進方法，其特征在于步驟2)中選擇UCB分?jǐn)?shù)最高的孩子節(jié)點是計算UCB并返回的孩子偽代碼，具體如下：

第一項稱為利用項，和過去的模擬情況有關(guān)，Q值取模擬結(jié)果為勝減模擬結(jié)果為負的差值；第二項稱為探索項，和每個節(jié)點模擬的次數(shù)有關(guān)，博弈時動作被選中的次數(shù)越少，對應(yīng)節(jié)點探索項的分?jǐn)?shù)就越高；c為常數(shù)項；

上述公式平衡利用項和探索項之間的關(guān)系，即使最開始獎勵值比較低的節(jié)點在足夠的時間之后也可能被選中。

3.根據(jù)權(quán)利要求2所述的圍棋上的搜索博弈樹的策略改進方法，其特征在于：更新路徑上節(jié)點的Q值和N值時使用虛擬的win值初始化Q，每個節(jié)點從較高的Q值，經(jīng)模擬完成后下降，偏向于選擇其它節(jié)點進行模擬，增加探索的幾率，最終收斂到真實的Q值。

4.根據(jù)權(quán)利要求3所述的圍棋上的搜索博弈樹的策略改進方法，其特征在于：初始Q值可根據(jù)先驗知識人工設(shè)置。

5.根據(jù)權(quán)利要求1所述的圍棋上的搜索博弈樹的策略改進方法，其特征在于：步驟3)中，每次搜索會涉及到多次模擬過程，當(dāng)模擬次數(shù)足夠多時，選擇次優(yōu)節(jié)點的概率收斂到0；將極小極大策略結(jié)合在一起，在己方行動時采用均勻采樣，而在對方行動時采用極小極大算法有效避免陷阱狀態(tài)。