從0實(shí)現(xiàn)基于Alpha zero的中國(guó)象棋AI

0.0、前言

? 題主對(duì)于阿爾法狗的實(shí)現(xiàn)原理好奇，加上畢業(yè)在即，因此選擇中國(guó)象棋版的阿爾法zero，阿爾法zero是阿爾法狗的升級(jí)版。在完成代碼編寫(xiě)的歷程中，深刻感受到深度學(xué)習(xí)環(huán)境的惡劣，網(wǎng)絡(luò)上固然資料繁多，但要么水平不行，不知所云，要么國(guó)外課程，門(mén)檻過(guò)高。因而碰壁良多，才想著自己寫(xiě)一篇博文，完整詳細(xì)的闡述作為普通人的我以及大家如何去一步步實(shí)現(xiàn)中國(guó)象棋AI。

? 同時(shí)，預(yù)先說(shuō)明：題主認(rèn)為學(xué)習(xí)深度學(xué)習(xí)一定要有目標(biāo)，如完成一個(gè)垃圾檢測(cè)等等，具體落實(shí)到項(xiàng)目，以完成項(xiàng)目為驅(qū)動(dòng)力，無(wú)關(guān)知識(shí)了解即可，切勿系統(tǒng)學(xué)習(xí)，貪多。深度學(xué)習(xí)龐大而深?yuàn)W，一個(gè)小方向就足以研究一生。

? 總體而言，想要基于python編寫(xiě)阿爾法zero需要使用到如下知識(shí)：

• 熟悉python語(yǔ)法
• 知道如何使用pytorch完成卷積神經(jīng)網(wǎng)絡(luò)與殘差神經(jīng)網(wǎng)絡(luò)
• 會(huì)使用Anaconda創(chuàng)建虛擬環(huán)境

默認(rèn)讀者有以上三者基礎(chǔ)，沒(méi)有也無(wú)所吊謂，只是無(wú)法敲出代碼，理論才是最重要的。

? 阿爾法zero算法主要由兩部分組成：殘差神經(jīng)網(wǎng)絡(luò)與蒙特卡洛樹(shù)搜索。這二者也是下面會(huì)詳細(xì)闡述的內(nèi)容，同時(shí)會(huì)擴(kuò)展到卷積神經(jīng)網(wǎng)絡(luò)與原生蒙特卡洛樹(shù)搜索。

0.1、阿爾法狗 和 阿爾法 zero區(qū)別

阿爾法狗：需要預(yù)先收集大量棋局信息制作成數(shù)據(jù)集，對(duì)神經(jīng)網(wǎng)絡(luò)進(jìn)行訓(xùn)練，然后在人機(jī)對(duì)弈時(shí)會(huì)結(jié)合神經(jīng)網(wǎng)絡(luò)的輸出與蒙特卡洛樹(shù)搜索進(jìn)行落子

阿爾法zero：無(wú)需事先準(zhǔn)備棋局?jǐn)?shù)據(jù)，通過(guò)自我對(duì)弈，在對(duì)弈過(guò)程中收集棋局信息，然后將信息制作成數(shù)據(jù)集對(duì)神經(jīng)網(wǎng)絡(luò)進(jìn)行訓(xùn)練，在自我對(duì)弈與人機(jī)對(duì)弈中同樣使用神經(jīng)網(wǎng)絡(luò)與蒙特卡洛樹(shù)搜索進(jìn)行落子

很顯然，對(duì)于普通人來(lái)講，不需要額外數(shù)據(jù)的阿爾法zero更適合

1.0、原生蒙特卡洛樹(shù)搜索

? 鑒于阿爾法zero所需知識(shí)過(guò)多，若直接概覽全局，反而不知所云。因此題主邊提出問(wèn)題邊講解，讓讀者知道為啥要這樣做，而不是這樣做就行了。

1.1、窮舉法

? 我們以最簡(jiǎn)單的井字棋為例，在一個(gè)空白的棋盤(pán)上選擇哪一步落子為當(dāng)前方最優(yōu)捏？

? 最簡(jiǎn)單的方法就是窮舉、如紅方落在左上角位置，黑方落在旁邊，一直交替落子最終分出勝負(fù)，然后棋局回歸到紅方落子在左上角位置，此時(shí)黑方再選擇不同地方落子，再次交替落子，再次分出勝負(fù)。直到黑方無(wú)未重復(fù)落子位置，則記錄模擬次數(shù)以及這些次數(shù)中紅勝利的次數(shù)形成，紅落子在左上角的勝率，仿照上述行為，模擬出空棋盤(pán)下紅方所有可以落子的行動(dòng)以及行動(dòng)對(duì)應(yīng)的勝率，最終選擇勝率最大的作為真實(shí)落子。

? 可以看到，上述方法確實(shí)是有用的，但缺點(diǎn)也很明顯，需要龐大的算力支持，如果將游戲改為象棋或者圍棋，是不可能支撐如此龐大的運(yùn)算。

? 因此，我們需要一種算法，能夠減少計(jì)算量，使其更加高效。

? 蒙特卡洛樹(shù)搜索應(yīng)運(yùn)而生。

1.2、原生蒙特卡洛樹(shù)搜索

? 原生的蒙特卡洛樹(shù)搜索會(huì)從開(kāi)始到隨機(jī)策略，逐漸過(guò)渡到有一定選擇性的策略。具體如下：

? 原生蒙特卡洛樹(shù)搜索有四步驟：選擇，擴(kuò)展，模擬，反向傳播、

? 先大致講一下原生蒙特卡洛樹(shù)搜索：

? 通過(guò)算法選擇輸入局面的所有可能落子中一個(gè)，生成子節(jié)點(diǎn)（子節(jié)點(diǎn)被選擇次數(shù)加一，總搜索次數(shù)加一），以子節(jié)點(diǎn)開(kāi)始模擬紅黑方交替落子，直至分出勝負(fù)，若紅勝且子節(jié)點(diǎn)為紅方落子，則子節(jié)點(diǎn)價(jià)值設(shè)置為1，然后重新以初始局面選擇所有落子可能中一個(gè)，且某些動(dòng)作已生成子節(jié)點(diǎn)且存在價(jià)值，則計(jì)算此動(dòng)作的最終值需加入此節(jié)點(diǎn)價(jià)值進(jìn)行計(jì)算。然后重復(fù)以上步驟，最終輸出被選擇次數(shù)多的落子動(dòng)作為真實(shí)落子。

? 再詳細(xì)講解（以井字棋為例）：

1、初始局面為3X3的空棋盤(pán)。創(chuàng)建全局變量all_count：記錄總搜索次數(shù)，輸入此局面下應(yīng)該為哪一方落子，這里默認(rèn)紅方

初始化一顆樹(shù)的數(shù)據(jù)結(jié)構(gòu)（后續(xù)以 A 表示此初始節(jié)點(diǎn)與棋盤(pán)），樹(shù)中存儲(chǔ)：

• a_count=0（表示此節(jié)點(diǎn)被選中次數(shù)，但是初始節(jié)點(diǎn)用不到，后面節(jié)點(diǎn)才用得到）
• 一個(gè)二維數(shù)組，表示空棋盤(pán)
• value：表示此節(jié)點(diǎn)價(jià)值（初始節(jié)點(diǎn)用不到）
• play：表示是紅方還是黑方（初始節(jié)點(diǎn)用不到）

2、計(jì)算此局面下紅方所有可能都落子動(dòng)作，很顯然有9種。

3、使用 上置信界算法 計(jì)算每一種落子動(dòng)作的最終價(jià)值（此價(jià)值與節(jié)點(diǎn)中存儲(chǔ)的價(jià)值不是一個(gè)東西），并選擇值最大的動(dòng)作生成子節(jié)點(diǎn)**(擴(kuò)展**)

---------------------------------------------------------------------------------上置信界算法---------------------------------------------------------------------------------------

上置信界算法：

? 核心：兼顧探索與價(jià)值。

? 解釋：在此棋局中，若一味使用價(jià)值最大的作為子節(jié)點(diǎn)，會(huì)照成每次都選擇相同節(jié)點(diǎn)，因初始時(shí)價(jià)值都為0，一旦選擇一個(gè)子節(jié)點(diǎn)且價(jià)值大于0后，后續(xù)就只會(huì)選擇此節(jié)點(diǎn)，若有其他落子潛在價(jià)值大于此也不會(huì)被選中，因此需要一種算法，讓搜索次數(shù)增加的同時(shí)，選中次數(shù)小的動(dòng)作其被選中的概率增加。只要符合算法思想，怎樣設(shè)計(jì)算法都沒(méi)問(wèn)題，這里提供一個(gè)簡(jiǎn)單的：

UCB(上置信界) = value + c X 總搜索次數(shù) / 節(jié)點(diǎn)被選中次數(shù) + 1 (這里是為了方便理解，所以化繁為簡(jiǎn)，真實(shí)的算法可以適當(dāng)更改以更貼合)

value：節(jié)點(diǎn)價(jià)值，c：偏置，就是一個(gè)自定義的常數(shù)，用來(lái)平衡探索與價(jià)值的

---------------------------------------------------------------------------------回到步驟---------------------------------------------------------------------------------------------

? 由算法可知、當(dāng)前局面下的 UCB 全部一樣，都是 0，因?yàn)榇藭r(shí)沒(méi)有子節(jié)點(diǎn)生成，所有 9 種動(dòng)作都沒(méi)有價(jià)值 且都沒(méi)有被選擇，總次數(shù)也為 0 。所以我們還是會(huì)依據(jù)算法選擇一個(gè)動(dòng)作進(jìn)行擴(kuò)展，比如說(shuō)是左上角第一個(gè)，這里無(wú)關(guān)緊要因?yàn)椴⒎亲罱K落子。

? 選擇左上角第一個(gè)后，總次數(shù)加一，創(chuàng)建子節(jié)點(diǎn) B ，且其父節(jié)點(diǎn)為初始節(jié)點(diǎn)，子節(jié)點(diǎn)被選中次數(shù)加一，即：

4、模擬

? 我們以子節(jié)點(diǎn)B為起始，模擬紅黑雙方交替落子，直至分出勝負(fù)。

? 注意，交替落子不會(huì)生成子節(jié)點(diǎn)，且完全隨機(jī)。（因?yàn)槟M的落子是沒(méi)有 價(jià)值 這個(gè)變量，所以只能隨機(jī)）若最終勝方與此子節(jié)點(diǎn)落子方一致則value變?yōu)?，反之變?yōu)?1

5、反向傳播：就是上述value變?yōu)?了，由于只進(jìn)行一次搜索只有一個(gè)子節(jié)點(diǎn)，且樹(shù)深度為2，所以不能完全體現(xiàn)反向傳播，后面會(huì)再講。

6、此時(shí)才算進(jìn)行完一次搜索，接下來(lái)進(jìn)行第二次搜索，（注：總搜索次數(shù)增加應(yīng)該是在搜索完成時(shí)增加，節(jié)點(diǎn)被訪問(wèn)次數(shù)是在節(jié)點(diǎn)被訪問(wèn)或者創(chuàng)建時(shí)增加）

7、同樣以初始空棋盤(pán)為起點(diǎn)，再次計(jì)算上置信界值（常數(shù)我們?cè)O(shè)置為2，這里是為了方便演示所以盡量減少探索，注重價(jià)值），計(jì)算可知：因此，我們?cè)俅芜x擇第一排第一個(gè)作為

8、由于選擇的是已經(jīng)存在的節(jié)點(diǎn)，因此我們不進(jìn)行擴(kuò)展，而是以此節(jié)點(diǎn)局面再次計(jì)算此節(jié)點(diǎn)局面下所有可能落子動(dòng)作的UCB值，注意此時(shí)就是應(yīng)該黑方落子了，所以是求黑方所有可能落子。由此局面可知，黑方有 8 種落子方式。我們分別求取這八種方式的 UCB 值，并選擇落子動(dòng)作進(jìn)行擴(kuò)展，同樣這八種的UCB全為 2 （即此局面下不存在任何一個(gè)子節(jié)點(diǎn)，因此也就不存在價(jià)值），因此，我們選哪一個(gè)都可以，這里選第一排第二個(gè)，此時(shí)局面變?yōu)椋?/p>

9、再次以 C 節(jié)點(diǎn)的局面作為模擬初始局面，此時(shí)若模擬結(jié)果是黑贏，那么此局面最終價(jià)值應(yīng)該為：1

10、反向傳播：我們通過(guò)模擬知道了C節(jié)點(diǎn)價(jià)值，此時(shí)需要將價(jià)值回傳，即通過(guò)子節(jié)點(diǎn)尋找父節(jié)點(diǎn)，又因?yàn)楦腹?jié)點(diǎn)是另一方落子，所以父節(jié)點(diǎn)更新后價(jià)值應(yīng)該為：（父節(jié)點(diǎn)原價(jià)值 - 子節(jié)點(diǎn)價(jià)值）/ 2。也就是B節(jié)點(diǎn)更新后價(jià)值

由于B節(jié)點(diǎn)的父節(jié)點(diǎn)為初始節(jié)點(diǎn)，所以不需要再將價(jià)值傳遞給初始節(jié)點(diǎn)了。

同時(shí)，總搜索次數(shù)加一，即all_count = 2，至于節(jié)點(diǎn)被訪問(wèn)次數(shù)，則是按照關(guān)系鏈來(lái)進(jìn)行增加，比如上述節(jié)點(diǎn)C次數(shù)需要加一，其父節(jié)點(diǎn)B在反向傳播時(shí)也需要加一。所以最終結(jié)果如下：

11、此時(shí)我們?cè)俅斡?jì)算初始局面（空棋盤(pán)）時(shí)個(gè)落子動(dòng)作的UCB值：

由圖可知，我們可取第一排第二個(gè)作為節(jié)點(diǎn) D 進(jìn)行擴(kuò)展：

12、然后就是繼續(xù)模擬，反向傳播，然后再次從初始節(jié)點(diǎn)開(kāi)始進(jìn)行新一輪搜索，如此循環(huán)往復(fù)直到到達(dá)指定搜索次數(shù)。

13、最終，我們會(huì)選擇初始節(jié)點(diǎn)下的子節(jié)點(diǎn)中被訪問(wèn)次數(shù)最大的作為蒙特卡洛樹(shù)搜索的輸出，如上圖中，子節(jié)點(diǎn)有 2 個(gè)，且B節(jié)點(diǎn)次數(shù)大于D節(jié)點(diǎn)，因此我們選擇B節(jié)點(diǎn)作為輸出，也就是第一排第一個(gè)的動(dòng)作。

總結(jié)：

優(yōu)點(diǎn)：

? 縱觀全部原生蒙特卡洛樹(shù)搜索，最關(guān)鍵處就是上置信界算法和模擬這兩者去抉擇最優(yōu)解。它比窮舉法更加高效，通過(guò)算法可以不需要全部遍歷完就能選擇出相對(duì)優(yōu)解。同時(shí)又保留了一部分窮舉的特點(diǎn)，模擬操作可以真實(shí)知道對(duì)應(yīng)動(dòng)作的價(jià)值，并且在后續(xù)選擇中由開(kāi)始的注重探索過(guò)渡到注重價(jià)值。

缺點(diǎn)：

? 經(jīng)過(guò)上述過(guò)程可以看出，雖然能夠節(jié)省大部分時(shí)間，但是我們每一次搜索的模擬步驟中必須要到達(dá)終局，這對(duì)于大型棋類游戲而言還是不太適合，還是需要算力，因此，基于殘差神經(jīng)網(wǎng)絡(luò)的蒙特卡洛樹(shù)搜索應(yīng)運(yùn)而生。

1.3、基于殘差神經(jīng)網(wǎng)絡(luò)的蒙特卡洛樹(shù)搜索

在原蒙特卡洛樹(shù)搜索基礎(chǔ)上增加了兩個(gè)東西，策略與價(jià)值。

也就是原來(lái)的 上置信界算法 算法被修改為：

上述講解value值時(shí)還要細(xì)節(jié)沒(méi)提到，等下會(huì)詳細(xì)講。

先說(shuō)說(shuō)殘差神經(jīng)網(wǎng)絡(luò)的輸出，一般神經(jīng)網(wǎng)絡(luò)只輸出只有一個(gè)，但是為啥需要兩個(gè)輸出呢？

正常情況其實(shí)我們只需要價(jià)值輸出即可，即value值，在模擬時(shí)用到，但是這里還加了一個(gè)概率輸出。

說(shuō)實(shí)話，有用，但是具體為啥一定需要就找不到很有說(shuō)服力的依據(jù)。

再說(shuō)說(shuō)策略輸出到底輸出的是啥？

若將空棋盤(pán)輸入到殘差神經(jīng)網(wǎng)絡(luò)。因?yàn)閯傞_(kāi)始紅方有9種可能落子，所以策略網(wǎng)絡(luò)最終會(huì)輸出每一個(gè)可能動(dòng)作被選擇的概率，如下：

其和應(yīng)該是1，這里只是示例，隨便設(shè)置了幾個(gè)數(shù)值。

策略輸出相當(dāng)于神經(jīng)網(wǎng)絡(luò)對(duì)當(dāng)前局面的預(yù)判，它認(rèn)為某些落子動(dòng)作更有價(jià)值，就會(huì)提高對(duì)應(yīng)概率，這樣在計(jì)算此局面所有動(dòng)作的UCB值時(shí)加入，可提高對(duì)應(yīng)動(dòng)作的值，使最優(yōu)解能夠更明顯，這也是為啥我說(shuō)有用的地方。

價(jià)值網(wǎng)絡(luò)輸出：就是輸出一個(gè)值，這個(gè)值可以當(dāng)做當(dāng)前局面的價(jià)值來(lái)看（可以看作當(dāng)前局面對(duì)于落子方的有利程度）。但是一般我們不直接將此局面的價(jià)值設(shè)置為此節(jié)點(diǎn)價(jià)值。而是通過(guò)模擬這個(gè)步驟獲得節(jié)點(diǎn)最終價(jià)值。

模擬步驟會(huì)與原生蒙特卡洛樹(shù)搜索不同！

原生蒙特卡洛樹(shù)搜索一定是要達(dá)到終究，無(wú)論雙方交替落子多少次，但是基于殘差神經(jīng)網(wǎng)絡(luò)的蒙特卡洛樹(shù)搜索由于殘差神經(jīng)網(wǎng)絡(luò)可以輸出每個(gè)局面的價(jià)值，即每次交替落子的局面價(jià)值，這樣存儲(chǔ)每個(gè)局面價(jià)值，然后交替落子一定步驟后，即使未到達(dá)終局也可以使用反向傳播的方式求取平均價(jià)值作為此子節(jié)點(diǎn)價(jià)值。當(dāng)然，在指定次數(shù)中若出現(xiàn)終局則價(jià)值以終局價(jià)值為準(zhǔn)。

總結(jié)：基于殘差神經(jīng)網(wǎng)絡(luò)的蒙特卡洛樹(shù)搜索，有兩方面提示：

1、神經(jīng)網(wǎng)絡(luò)會(huì)輸出每個(gè)動(dòng)作的概率，這樣可以更加準(zhǔn)確找到最優(yōu)解，因?yàn)楦怕试酱笞罱K值越大。

2、由于神經(jīng)網(wǎng)絡(luò)還可以輸出某個(gè)局面價(jià)值，使用我們?cè)谀M步驟時(shí)，不需要一定到達(dá)終局就能夠獲得價(jià)值。

且隨著神經(jīng)網(wǎng)絡(luò)訓(xùn)練次數(shù)的增加，概率與價(jià)值的值會(huì)越貼近正確值。如上，也是為何需要?dú)埐钌窠?jīng)網(wǎng)絡(luò)輔助的原因。文章來(lái)源地址http://www.zghlxwxcb.cn/news/detail-741704.html

到了這里，關(guān)于從0實(shí)現(xiàn)基于Alpha zero的中國(guó)象棋AI（會(huì)分為多個(gè)博客，此處講解蒙特卡洛樹(shù)搜索）的文章就介紹完了。如果您還想了解更多內(nèi)容，請(qǐng)?jiān)谟疑辖撬阉鱐OY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關(guān)文章，希望大家以后多多支持TOY模板網(wǎng)！