0
| 本文作者： 三川 | 2017-05-23 16:42 |
雷鋒網(wǎng)按：本文作者夏飛，清華大學與卡內(nèi)基梅隆大學畢業(yè)，現(xiàn)于谷歌從事技術(shù)研發(fā)工作。本文是對《自然》上發(fā)表的知名論文“Mastering the game of Go with deep neural networks and tree search”進行的總結(jié)，對 AlphaGo 的算法結(jié)構(gòu)進行了概括。原總結(jié)文用英語寫就，經(jīng)雷鋒網(wǎng)編譯，閱讀原文請點此。
下文概括了圍棋借助人工智能在 2016 年實現(xiàn)的突破。
圍棋是一個完全信息博弈問題。而完全信息博弈，通常能被簡化為尋找最優(yōu)值的樹搜索問題。它含有 b 的 d 次方個可能分支，在國際象棋中 b≈35，d≈80；而在圍棋中 b≈250，d≈150。很顯然，對于圍棋，用窮舉法或簡單的尋路算法（heuristics）是行不通的。但有效的方法是存在的：
從策略（policy） P(a|s) 中取樣 action，降低搜索廣度
通過位置評估降低搜索深度
把策略和值用蒙特卡洛樹搜索（MCTS）結(jié)合起來。
用一個 13 層的 CNN，直接從人類棋步中訓練一個監(jiān)督學習策略網(wǎng)絡(luò) Pσ。輸入為 48 x 19 x 19 的圖像（比方說，它的組成棋子顏色 是 3 x 19 x 19），輸出是使用 softmax 層預測的全部落子的概率。精確度是 55.7%。
訓練一個能在運行時快速取樣 action 的快速策略 Pπ。這會用一個基于小型模式特征的線性 softmax。精確度是 24.2%，但它計算一次落子只用 2 微秒，而不像 Pσ 需要 3 毫秒。
訓練一個增強學習策略網(wǎng)絡(luò) Pρ ，通過優(yōu)化博弈結(jié)果來進一步提升監(jiān)督策略網(wǎng)絡(luò)。這把策略網(wǎng)絡(luò)向贏棋優(yōu)化，而不是優(yōu)化預測精確度。本質(zhì)上，Pρ 與 Pσ 的結(jié)構(gòu)是一樣的。它們的權(quán)重使用相同值 ρ=σ 初始化。對弈的兩個選手，是當前策略網(wǎng)絡(luò) Pρ 和隨機（防止過擬合）選擇的此前的策略網(wǎng)絡(luò)迭代。
訓練一個價值網(wǎng)絡(luò)（value network）Vθ，來預測強化學習策略網(wǎng)絡(luò)自己和自己下棋的贏家。該網(wǎng)絡(luò)的架構(gòu)和策略網(wǎng)絡(luò)類似，但多出一個特征平面（當前玩家的顏色），并且輸出變成了單一預測（回歸，均方差損失）。根據(jù)完整棋局來預測對弈結(jié)果，很容易導致過擬合。這是由于連續(xù)落子位置之間高度相關(guān)，只有一子之差。因此，這里使用了強化學習策略網(wǎng)絡(luò)自己與自己對弈新生成的數(shù)據(jù)。該數(shù)據(jù)從包含 3000 萬個不同位置的獨立棋局中抽取。
把策略網(wǎng)絡(luò)、價值網(wǎng)絡(luò)、快速策略和蒙特卡洛樹搜索結(jié)合起來。一個標準的蒙特卡洛樹搜索過程包含四步：選擇、擴展、評估、備份。為了讓大家更容易理解，我們只粗略講了講它如何在模擬中選擇狀態(tài)的部分（如對數(shù)學感興趣，請到原始論文中找公式）。
狀態(tài)分數(shù)=價值網(wǎng)絡(luò)輸出+快速運行（fast rollout）的策略結(jié)果+監(jiān)督學習策略網(wǎng)絡(luò)輸出
高狀態(tài)得分（或者說落子）會被選擇。價值網(wǎng)絡(luò)輸出和快速運行策略結(jié)果是評估函數(shù)，在葉子節(jié)點進行評估（注意，為了評估快速運行，需要一直到最后一步）。監(jiān)督學習策略網(wǎng)絡(luò)輸出是一個當前階段的 action 概率，充作選取分數(shù)的獎勵分。該分數(shù)會隨訪問次數(shù)而退化，以鼓勵探索。注意強化學習策略網(wǎng)絡(luò)只被用于輔助，來生成價值網(wǎng)絡(luò)，并沒有直接在蒙特卡洛樹搜索中使用。
到這就結(jié)束了，以上就是戰(zhàn)勝了人類的 AlphaGo 算法！
via zhihu，雷鋒網(wǎng)編譯
相關(guān)文章：
4.5小時鏖戰(zhàn)，柯潔1/4 子惜敗AlphaGo
王小川評AlphaGo 2.0：和1.0原理大不同 更接近于人
雷峰網(wǎng)版權(quán)文章，未經(jīng)授權(quán)禁止轉(zhuǎn)載。詳情見轉(zhuǎn)載須知。
