AI遊戲開發和深度學習進階（簡體書）

本書以各種各樣的實例剖析遊戲AI手法，並以此為目標，幫助讀者學習構築遊戲AI的技術。另外，也闡述了遊戲AI中的深層學習、機械學習、強化學習技術。

伊庭齊志 （Hitoshi Iba）

工學博士，東京大學大學院情報理工學系研究科電子信息學專業教授，也是Genetic Programming and Evolvable Machines（GPEM）的副主編。他從事人工智能和人工生命的研究，主要研究領域包括進化系統、基因組信息處理、金融工程和複雜系統。

◆ 譯者簡介 ◆

曹 旸

2017年獲得日本早稻田大學綜合機械工學博士學位。博士求學期間，研究將模式識別應用於手術機器人操作的技術。目前就職於歐姆龍（中國）有限公司，主要在工業自動化和農業自動化領域中從事基於深度學習和計算機視覺的產品研發管理工作。

深度學習這門技術在機器視覺領域大規模應用，採用深度學習的圖像識別AI 算法在識別精度上已經超過人眼精度，如今我們日常生活中的掃臉支付也基於深度學習強大的圖像特徵提取能力。人們覺得AlphaGo 才是AI 時代到來的標志，之所以這樣覺得或許是因為人們普遍承認下圍棋是一種高級別的智能過程，也是一個絞盡腦汁的過程—可以切身感受到“動腦”。

伊庭教授在本書中強調了研究遊戲AI 的意義——或許是解密人類大腦思考方式的方法之一。我個人十分讚同伊庭教授的這一看法，我們的生活、工作 和學習過程中的糾結一直都建立在著眼於眼前還是未來的權衡當中。但正是因為我們具有智能，所以我們才會具有這種權衡能力（或者說是生活中充滿了糾結）。

相信當讀者從章堅持讀到後一章時，不僅會覺得遊戲AI 有趣，還會覺得人腦思維本身就有很多有趣的地方。或許研究遊戲AI 的意義不是為了創作出更加聰明、強大的AI，而是把它當作一面鏡子，來進行對人腦思維研究的自我啟發和探索。

深度學習開始被關注的標志性事件，就是一個採用深度卷積神經網絡的模型AlexNet在2012年ImageNet圖像識別大賽上獲得冠軍。自此，深度學習這門技術在機器視覺領域開始大規模應用。如今，採用深度學習的圖像識別AI算法在識別精度上已經超過人眼的精度，我們日常生活中的掃臉支付也基於深度學習強大的圖像特徵提取能力。盡管深度學習的應用為圖像領域帶來了飛躍性的發展，但2012年的那場突破並沒有引起全社會的廣泛關注，當時人們並沒有普遍意識到人工智能領域的崛起即將到來。我覺得之所以這樣，是因為深度學習給機器視覺帶來的飛躍只能算是開發出了某種高級圖像傳感器。當這個傳感器收到“汽車”圖像時會輸出“汽車”這樣的識別結果，當收到“花朵”圖像時則會輸出“花朵”這樣的識別結果。雖然看起來很強大，但人們普遍沒有感受到“智能”的存在。因為我們或許覺得，在對映入眼簾中的事物進行識別的整個過程中，我們感受不到自己在“動腦”。
之所以覺得AlphaGo才是AI時代到來的標志，或許是因為人們普遍承認下圍棋是一種高級別的智能過程，也是一個絞盡腦汁的過程—我們可以切身感受到“動腦”。下圍棋比拼的就是誰預見的步數更遠更深，在這裡我們或許會想到傳統計算機算法可以用暴力枚舉方法預估所有的走棋可能性，但這個方法在圍棋中行不通，因為圍棋的棋局存在10171種可能性，人類目前或許找不出能夠枚舉出所有可能性的計算機。人腦也同樣無法實現對所有走棋可能性的“掃描”。這個時候，人類的直覺發揮著強大的作用。當看到眼前的棋局時，人類能夠依靠直覺快速給出多種落子方案。經驗越是豐富，直覺越是準確。當考慮如何用計算機復現這種直覺時，我們的視野聚焦到了深度學習上。深度學習擅長解決圖像問題，它的本質是處理矩陣數據，而圍棋棋盤本身就是一種完美的矩陣。通過深度學習，我們對棋盤這個矩陣不斷地進行特徵提取並對其進行壓縮，通過多層深度卷積處理後，擁有某種落子的“直覺”。用深度學習來學習的棋譜數據越多，這種落子的“直覺”就會越可靠。AlphaGo通過蒙特卡羅算法使用不同的落子方案進行預演，不斷刷新不同的落子方案，從而提高終結果的勝率，完全像是一個圍棋高手一樣—在落子之前已在腦海中完成了多種落子方案後續結果的預演。當然，蒙特卡羅算法並非新鮮方法，但正是深度學習的出現，AlphaGo才能實現針對眼前棋局的落子直覺和終導向勝利的完美權衡。一個強大的圍棋AI不僅需要有專家的直覺，也需要像專家那樣深謀遠慮。
伊庭教授在本書中強調了研究遊戲AI的意義—或許是解密人類大腦思考方式的方法之一。我個人十分讚同伊庭教授的這一看法，我們的生活、工作和學習過程中的糾結一直都建立在著眼於眼前還是未來的權衡當中。但正是因為我們具有智能，所以我們才會具有這種權衡能力（或者說是生活中充滿了糾結）。遊戲領域裡的經典算法—A*算法在構造上相對近期的算法簡單很多，但它一邊著眼於眼前的資源消耗量，一邊還要注意是否靠近終點，這種簡單的路線規劃原理已經具有了初步的著眼於眼前與未來的權衡能力。
本書的後一章描述如何讓遊戲AI表現得像個人類玩家，並量化了一些因素，從而對類人程度進行函數化。我相信當讀者堅持讀到後一章時，不僅會覺得遊戲AI有趣，還會覺得人腦思維本身就有很多有趣的地方。或許研究遊戲AI的意義不是為了創作出更加聰明、強大的AI，而是把它當作一面鏡子，來進行對人腦思維研究的自我啟發和探索。

曹旸
2021年2月於上海

譯者序
前言
第1章　謎題與遊戲AI的過去和現在 1
1.1　關於AI的預言成真了嗎 1
1.2　遊戲AI的歷史和背景 2
1.3　遊戲AI是否會剝奪人類的樂趣 7
1.4　遊戲AI的意義 9
1.5　遊戲的深奧程度與“先下手為強”定理 10
第2章　解謎的AI 14
2.1　搜索樹 14
2.1.1　樹的構造和圖形表達 14
2.1.2　深度優先搜索 21
2.1.3　寬度優先搜索 28
2.1.4　A*搜索 32
2.2　推箱子 40
2.3　數字連線 43
2.4　日式華容道 46
2.5　孔明棋 48
2.6　嘗試用數學知識解決數獨問題 51
第3章　依賴約束的謎題和非單調推理 58
3.1　縱向搜索與回溯 58
3.2　數學家弄錯的國際象棋謎題 58
3.3　線條圖的解釋與錯覺畫 63
3.4　ATMS與四色問題 71
3.5　解開國際象棋謎題 83
3.5.1　盡可能放置多個棋子 84
3.5.2　盡可能攻擊多個區域 86
3.6　Knuth的謎題與位棋盤 88
第4章　會玩遊戲的AI 90
4.1　井字棋與樹 90
4.2　遊戲的樹搜索 91
4.3　黑白棋與Fool’s mate 104
4.4　A*馬裡奧 110
4.5　蒙特卡羅樹搜索 114
4.6　立體四子棋 118
4.7　黑白棋的蒙特卡羅算法和NegaScout算法 123
4.8　如何贏得博弈 124
4.9　消滅幽靈：AI吃豆人 132
第5章　學習、進化和遊戲AI 140
5.1　來自AlphaGo的震撼 140
5.2　DQN和街機遊戲 151
5.3　進化的馬裡奧 155
5.4　神經進化 158
5.5　吃豆人的神經進化 161
5.6　充滿好奇心的馬裡奧 166
第6章　遊戲AI與類人化 174
6.1　為什麼需要類人化的AI 174
6.2　通用遊戲是什麼 175
6.3　圖靈測試和類人化的AI 178
6.4　不使用“類人化”函數的類人化遊戲AI 182
6.5　使用“類人化”函數的類人化遊戲AI 190
參考文獻 199

前 言
或許可以說“人生就像玩紙牌，洗牌和發牌完全靠運氣。”……更恰當的說法是，人生就像下棋。
Arthur Schopenhauer，《人生的智能》
本書是一本關於遊戲AI和謎題AI的書籍。書中對基礎理論、深度學習、強化學習以及使用進化計算的方法進行了介紹，並通過具體示例進行了詳細的解釋說明。此外，本書不僅涵蓋算法，還涵蓋與AI相關的主題、歷史背景和數學主題等各種內容。介紹這麼多，是因為研究遊戲本身與和AI相關的各種各樣的課題及挑戰有關。實際上，對遊戲AI的研究不單純是針對遊戲，它還有助於解決許多優化理論和系統工程相關問題。不知不覺中，遊戲還可能會影響我們的人生。
但是，本書不一定涵蓋的數據和強大的算法，因為本書的目的在於從一開始就提供易於理解的解釋。本書將更多的重點放在描述普通但很實用的AI技術上。或許讀者知道我還沒有注意到的能夠高效解決問題的AI方法，如果讀者能夠告訴我這些新信息，有機會的情況下我將進行更新和修訂。
正如第1章所述，我在學生時代購買了SciSys公司的Kasparov國際象棋計算機Travel Mate II（1986）。回想起來，它是商業化遊戲AI的先驅。這臺機器仍然奇跡般地運轉著，孩子偶爾還會與之對弈。它對我來說是很強大的對手，很不好意思地說，我就算不斷提高水平也依然無法擊敗它。Kasparov本人在該機手冊的末尾有以下聲明：
“請盡情享受Kasparov國際象棋計算機。也許有一天，你可以獲得與我對弈的實力！”
可惜的是，我認為這是不可能的，但是讀者應該通過參考這本書進行擴展並挑戰。一定要在其他遊戲和謎題中尋求更強大的能力。
本書源於我在大學裡的關於人工智能和系統工程基礎的課程。在我的課程中，課題報告相當奇怪，有時難度會達到幾乎無解的程度。但是，在學生提交的報告中有許多令人印象深刻的陳述和有趣的考量，每次閱讀學生提交的報告，我都樂在其中。我對這些報告進行了添加和修改，並作為書中的組成部分。在這裡我不能說出所有報告的作者的名字，但是我要感謝所有努力創建有趣報告的學生。實驗室的川畑直之、鈴木遼、橫山智之和冢田涼太郎對源代碼的修改做出了貢獻。另外，計良宥志先生編寫了一個程序，以代數方式解決數獨問題。平井健太郎和齋藤真魚在畢業論文中對遊戲AI和人類進行了研究，並為第6章提供了數據。我還要感謝東京大學信息科學與技術研究生院電子情報學系伊庭實驗室的教職員工以及學生。
我與自己學生時代時所屬的實驗室（東京大學研究生院工程研究生院信息工程學系井上實驗室）以及電子技術綜合實驗室（Electronic Technical Laboratory, ETL）的各位同人探討過的各種有趣的關於AI哲學層面的內容成了本書的核心。松原仁（既是我大學時代的學長，也是ETL推理實驗室（開創性遊戲AI實驗室）的同人）告訴了我很多關於將棋AI的對戰、國際象棋的遊戲AI等有趣的內容。我當時還沒有從事和遊戲AI相關的研究，但後來在大學任職，聽了學生關於遊戲AI的研究，閱讀了課題報告中關於製作遊戲的內容以後，我決定開始學習相關的內容。另外，我一直喜歡解謎，並且一直對使用AI解決Martin Gardner和Samuel Loyd的謎題很感興趣，而這一系列的挑戰和本書中的許多課題都是有關聯的。撰寫本書時，我參考了松原的許多文檔，並進行了引用，這讓我回想起令人懷念的ETL時代。此外，東京大學研究生院電子情報學系的鶴岡慶雅老師會在研究發表會等場合分享很多關於遊戲AI的有趣話題。我想通過這次機會對所有老師、前輩、後生以及同事表達深深的謝意。
後由衷地感謝在背後默默支持我的妻子—由美子，以及孩子們（滉基、滉乃、滉豐）。

伊庭　齊志
2018年8月於巴厘島