[發(fā)明專利]一種蒙特卡洛樹搜索方法、系統(tǒng)及應(yīng)用

有效

• 申請?zhí)枺?/td>: 202110264682.7
• 申請日: 2021-03-11
• 公開（公告）號(hào): CN113127704B
• 公開（公告）日: 2022-11-01
• 發(fā)明（設(shè)計(jì)）人: 高晶亮;張澤陽;郭網(wǎng)媚;李永康;朱晨晨;邊卓琳;王萌萌;于恒蘇
• 申請（專利權(quán)）人: 西安電子科技大學(xué)
• 主分類號(hào): G06F16/903
• 分類號(hào): G06F16/903;G06F16/901
• 代理公司: 西安長和專利代理有限公司 61227
• 代理人: 何畏

1.一種蒙特卡洛樹搜索方法，其特征在于，所述蒙特卡洛樹搜索方法包括：在多線程進(jìn)行收集棋譜的自對弈訓(xùn)練中，同一進(jìn)程繼承同一顆蒙特卡洛搜索樹，根據(jù)每盤棋結(jié)束后蒙特卡洛搜索樹的節(jié)點(diǎn)判斷是否進(jìn)行落葉，根據(jù)策略剪去蒙特卡洛搜索樹中的葉子節(jié)點(diǎn)，進(jìn)而繼續(xù)開始下一局棋，直到本代棋譜收集完成；

所述蒙特卡洛樹搜索方法包括以下步驟：

步驟一，根據(jù)線程總數(shù)和內(nèi)存實(shí)際情況確定落葉的上下界值，記為Node_up，Node_down；

步驟二，開始當(dāng)前代的棋譜自對弈，每一線程從開始到結(jié)束均繼承同一顆蒙特卡洛搜索樹，在每一局棋進(jìn)行過程中記錄葉子節(jié)點(diǎn)的列表Leave_list，并在每一局棋結(jié)束后記錄當(dāng)前蒙特卡洛搜索樹的節(jié)點(diǎn)總數(shù)，記為Node_count；

步驟三，判斷當(dāng)前搜索樹上的節(jié)點(diǎn)總數(shù)Node_count是否大于落葉的上界值Node_up；若否，則在本線程繼續(xù)開啟下一盤棋；若是，則進(jìn)行落葉過程，結(jié)束后開啟本線程的下一盤棋；

步驟三中，所述落葉過程，包括：

(1)計(jì)算得到本次落葉過程須落下的節(jié)點(diǎn)總數(shù)Fall_count；其中，所述節(jié)點(diǎn)總數(shù)Fall_count與樹節(jié)點(diǎn)總數(shù)Node_count和落葉下界值Node_down關(guān)系為：Fall_count＝Node_count–Node_down；

(2)根據(jù)步驟二 記錄得到的Leave_list，從該列表的頭部，即索引為0處取出當(dāng)前要落下的葉子節(jié)點(diǎn)，記為Node_current；

(3)從Node_current開始做節(jié)點(diǎn)中數(shù)據(jù)的反向更新，即從Node_current開始，將需要更新的值層層回溯給此節(jié)點(diǎn)的父節(jié)點(diǎn)，直到回溯到根節(jié)點(diǎn)為止；

(4)當(dāng)更新完成該葉子節(jié)點(diǎn)后，判斷其父節(jié)點(diǎn)是否成為新的葉子節(jié)點(diǎn)；若是，則將該父節(jié)點(diǎn)加入葉子節(jié)點(diǎn)列表Leave_list；

(5)在蒙特卡洛搜索樹上刪除該葉子節(jié)點(diǎn)，繼續(xù)跳至步驟(2)執(zhí)行，直到Fall_down個(gè)節(jié)點(diǎn)全部落下為止。

2.如權(quán)利要求1所述的蒙特卡洛樹搜索方法，其特征在于，步驟(3)中，設(shè)置需要更新的值為節(jié)點(diǎn)的搜索總次數(shù)N，該點(diǎn)的價(jià)值Node_value，每一個(gè)父節(jié)點(diǎn)具體的更新細(xì)節(jié)為：

子節(jié)點(diǎn)位置處的N＝N–1；

子節(jié)點(diǎn)位置處的Q＝Q–Node_value；

子節(jié)點(diǎn)位置處的W＝Q/N。

3.如權(quán)利要求1所述的蒙特卡洛樹搜索方法，其特征在于，所述蒙特卡洛樹搜索方法，還包括：

對于某一步利用蒙特卡洛樹搜索方法的預(yù)測過程，進(jìn)行的搜索次數(shù)以生成n個(gè)新的子節(jié)點(diǎn)為準(zhǔn)，即進(jìn)行一步搜索后蒙特卡洛搜索樹上理論會(huì)增加n個(gè)新的節(jié)點(diǎn)。

4.如權(quán)利要求1所述的蒙特卡洛樹搜索方法，其特征在于，所述蒙特卡洛樹搜索方法，還包括：

對于單一線程，從本代自對弈開始，每一盤棋均繼承同一顆蒙特卡洛搜索樹，即此蒙特卡洛搜索樹的高度和樹上節(jié)點(diǎn)總數(shù)Node_count會(huì)隨著收集棋譜的過程增加而持續(xù)增加。

5.一種計(jì)算機(jī)設(shè)備，其特征在于，所述計(jì)算機(jī)設(shè)備包括存儲(chǔ)器和處理器，所述存儲(chǔ)器存儲(chǔ)有計(jì)算機(jī)程序，所述計(jì)算機(jī)程序被所述處理器執(zhí)行時(shí)，使得所述處理器執(zhí)行權(quán)利要求1～4任意一項(xiàng)所述的蒙特卡洛樹搜索方法。

6.一種計(jì)算機(jī)可讀存儲(chǔ)介質(zhì)，存儲(chǔ)有計(jì)算機(jī)程序，所述計(jì)算機(jī)程序被處理器執(zhí)行時(shí)，使得所述處理器執(zhí)行權(quán)利要求1～4任意一項(xiàng)所述的蒙特卡洛樹搜索方法。

7.一種信息數(shù)據(jù)處理終端，其特征在于，所述信息數(shù)據(jù)處理終端用于實(shí)現(xiàn)權(quán)利要求1～4任意一項(xiàng)所述的蒙特卡洛樹搜索方法。

8.一種實(shí)施權(quán)利要求1～4任意一項(xiàng)所述的蒙特卡洛樹搜索方法的蒙特卡洛樹搜索系統(tǒng)，其特征在于，所述蒙特卡洛樹搜索系統(tǒng)包括：

落葉界值確定模塊，用于根據(jù)線程總數(shù)和內(nèi)存實(shí)際情況確定落葉的上下界值，記為Node_up，Node_down；

棋譜自對弈模塊，用于開始當(dāng)前代的棋譜自對弈，每一線程從開始到結(jié)束均繼承同一顆蒙特卡洛搜索樹，在每一局棋進(jìn)行過程中記錄葉子節(jié)點(diǎn)的列表Leave_list，并在每一局棋結(jié)束后記錄當(dāng)前蒙特卡洛搜索樹的節(jié)點(diǎn)總數(shù)，記為Node_count；

判斷模塊，用于判斷當(dāng)前搜索樹上的節(jié)點(diǎn)總數(shù)Node_count是否大于落葉的上界值Node_up；若否，則在本線程繼續(xù)開啟下一盤棋；若是，則進(jìn)行落葉過程，結(jié)束后開啟本線程的下一盤棋。