電腦對局導論

研究電腦如何下棋、解謎題和進行對局是資訊科學中研究人工智慧的重要一支。電腦對局的研究課題多元且具挑戰性，又因入門的條件較低、成效評定方式明確，故吸引許多人投入研究。本書有系統地蒐集並整理相關文獻，歸納電腦對局之精華要義，有助於入門者學習參考，奠定基礎。

本書綜覽電腦對局研究，並特別注重演算法層次的引導式理解及討論，也描述演算法實作時所需的系統知識和技巧，兼顧理論和實際。

研究電腦對局，終極目標不只是希望電腦在對局上能贏人類，而是在達成這目的的過程中，深入了解相關知識及應用。因此，與其說研究者在鑽研如何讓電腦「變聰明」，不如說透過演算法，研究者激發腦力，從而開創新的科學和技術發展，便利人類的生活。

本書特色
1. 國內外第一本專門介紹電腦對局程式設計理論和實作的專書。
2. 囊括古今中外相關軼事、筆記和研究，包羅萬象，蒐集齊全。
3. 超過60個演算法，詳細說明單人對局及雙人對局之細節。
4. 超過120張說明圖示，舉實例闡述困難的觀念。

徐讚昇（Tsan-sheng Hsu）
中央研究院資訊科學研究所研究員
國立臺灣大學資訊工程學系兼任教授
主要研究領域為演算法、圖論、資訊隱私及保護、資料密集運算和電腦對局理論及實作

許舜欽（Shun-Chin Hsu）
國立臺灣大學資訊工程學系退休教授
長榮大學資訊管理學系教授（2002-2017）
台灣電腦學會理事長（2010-）
主要研究領域為電腦對局理論及實作

陳志昌（Jr-Chang Chen）
中原大學應用數學系副教授

蔣益庭（Yi-Ting Chiang）
國立臺灣大學資訊工程學系博士

陳柏年（Bo-Nian Chen）
中央研究院資訊科學研究所博士後研究員（2012-2014）
財團法人資訊工業策進會智慧網通系統研究所專案經理

劉雲青（Yun-Ching Liu）
日本東京大學工學院博士

張紘睿（Hung-Jui Chang）
國立臺灣大學資訊工程學系博士候選人

蔡數真（Sue-Chen Tsai）
中央研究院資訊科學研究所研究助理

林庭羽（Ting-Yu Lin）
中央研究院資訊科學研究所研究助理

范綱宇（Gang-Yu Fan）
中央研究院資訊科學研究所研究助理

序一
序二

第1章　電腦對局研究概論
1.1 前言
1.2 智慧
1.2.1 Turing測試
1.2.2 延伸思考
1.3 歷史
1.3.1 18世紀的第一個西洋棋機器人
1.3.2 西洋棋殘局自動機
1.3.3 東方的相關研究
1.4 學術研究
1.4.1 早期（1970年之前）
1.4.2 初期（1970～1980年）
1.4.3 中期（1980～1990年）
1.4.4 近期（1990年至今）
1.5 對局遊戲
1.5.1 對局分類
1.5.2 複雜度
1.5.3 研究新領域
1.6 結語和本書結構
1.7 練習題

第2章　單人對局之基礎搜尋演算法
2.1 前言
2.1.1 概述
2.1.2 本章常用名詞和定義
2.2 暴力搜尋
2.2.1 廣度優先搜尋
2.2.2 廣度優先搜尋之改良：利用硬碟儲存佇列
2.2.3 深度優先搜尋
2.2.4 深度優先搜尋之改良：運用兩個堆疊
2.2.5 深度優先搜尋之改良：限制搜尋的深度
2.2.6 深度優先搜尋之改良：逐層加深
2.2.7 深度優先搜尋之改良：深度限制及方向選擇
2.2.8 雙向搜尋
2.3 啟發式搜尋
2.3.1 A*搜尋
2.3.2 考量總花費門檻值之深度優先搜尋
2.3.3 如何擇出良好著手
2.3.4 逐層加深之深度優先及A*演算法的結合
2.3.5 IDA*之應用
2.4 結語
2.5 練習題

第3章　單人對局之進階搜尋演算法
3.1 前言
3.2 (n2－1)-puzzle問題
3.3 15-puzzle之狀態空間
3.3.1 基本性質
3.3.2 盤面奇偶性不因移動改變
3.3.3 延伸思考
3.4 15-puzzle之解法
3.5 樣式資料庫
3.5.1 邊緣
3.5.2 改良邊緣數
3.6 24-puzzle之解法
3.7 其他啟發式函數之設計
3.8 結語
3.9 練習題

第4章　雙人對局概論
4.1 前言
4.2 本章常用名詞和定義
4.3 1990年對局程式棋力估測
4.4 雙人對局分類
4.4.1 收斂型對局
4.4.2 發散型對局
4.4.3 連接型對局
4.5 10或11路六貫棋
4.5.1 基本性質
4.5.2 策略盜用論點
4.5.3 延伸思考
4.6 其他相關議題
4.6.1 對局複雜度
4.6.2 先手優勢
4.6.3 2000年對局程式棋力估測
4.7 結語
4.8 練習題

第5章　由西洋棋論雙人對局程式之設計
5.1 前言
5.1.1 西洋棋棋規及相關知識
5.1.2 西洋棋之對局複雜度
5.2 審局函數
5.2.1 完美審局函數
5.2.2 近似審局函數
5.2.3 審局函數之設計
5.3 基於審局函數之搜尋策略
5.3.1 A型策略
5.3.2 B型策略
5.4 對弈、棋風及策略之變化
5.5 結語
5.6 練習題

第6章　Alpha-Beta切捨演算法與分析
6.1 前言
6.1.1 位置與搜尋樹
6.1.2 樹節點編號法
6.2 最小最大化搜尋演算法
6.3 正反最大演算法
6.4 Alpha-Beta切捨演算法
6.4.1 改進的契機
6.4.2 Alpha剪枝
6.4.3 Beta剪枝
6.4.4 深層Alpha-Beta切捨
6.4.5 Alpha-Beta切捨演算法的實作
6.4.6 搜尋順序與切捨之關係
6.5 效能分析
6.5.1 最佳可預期之狀況
6.5.2 節點分類與節點間之關係
6.5.3 最佳可預期狀況之效率分析
6.5.4 平均狀況之效率分析
6.5.5 完美排序與最佳排序
6.6 Alpha-Beta搜尋的變形
6.6.1 硬式失敗版
6.6.2 軟式失敗版
6.6.3 演算法F2與F3的比較
6.7 結語
6.8 練習題

第7章　斥候與正反斥候
7.1 前言
7.2 斥候演算法
7.2.1 基本概念
7.2.2 如何TEST
7.2.3 斥候演算法之結構
7.3 斥候演算法的效能分析
7.3.1 TEST成功與失敗對搜尋節點數的影響
7.3.2 TEST演算法拜訪之節點數
7.3.3 完美排序樹中斥候演算法所拜訪之節點數
7.3.4 與Alpha-Beta切捨演算法之比較
7.3.5 斥候演算法之效能分析
7.4 斥候演算法之實作
7.4.1 回顧Alpha-Beta切捨搜尋演算法
7.4.2 正反斥候演算法：最小最大版
7.4.3 正反斥候演算法
7.4.4 延伸思考
7.5 結語
7.6 練習題

第8章　同形表和其他的改進方法
8.1 前言
8.2 同形表
8.2.1 同形表之更新規則
8.2.2 加入同形表之正反斥候演算法
8.3 Zobrist雜湊函數
8.3.1 理論基礎
8.3.2 雜湊函數之設計
8.3.3 錯誤叢集
8.3.4 使用時之參數設定
8.4 動態調整搜尋區間大小
8.5 著手排序之改進
8.5.1 知識捷思法
8.5.2 利用歷史資訊找出好的著手次序
8.5.3 主要變化路徑
8.5.4 否議表
8.5.5 殺手捷思法
8.5.6 歷史捷思法
8.6 實驗數據
8.7 動態調整搜尋深度
8.7.1 虛手切捨
8.7.2 較晚考慮著手之搜尋裁減
8.8 動態搜尋延伸
8.8.1 動態深度延伸
8.8.2 寧靜搜尋
8.9 結語
8.10 練習題

第9章　蒙地卡羅樹搜尋演算法
9.1 前言
9.2 簡易圍棋規則
9.3 最初的演算法：MCSpure
9.4 MCSpure之首要問題
9.4.1 K臂吃角子老虎問題
9.4.2 信賴上界
9.4.3 以標準差修正信賴上界值
9.5 MCSpure的第二個問題
9.5.1 優先樹擴展
9.5.2 蒙地卡羅最小最大化樹搜尋
9.6 信賴上界的樹搜尋
9.7 程式實作時之技巧
9.8 結語
9.9 練習題

第10章　蒙地卡羅搜尋演算法的改進
10.1 前言
10.2 線上知識
10.2.1 漸進式剪枝
10.2.2 手順不羈法
10.2.3 模擬數值快速估計法
10.2.4 節點展開策略
10.2.5 模擬退火法
10.2.6 固定深度全展開
10.2.7 各種方法的整合
10.3 離線學習
10.3.1 MM法與模擬平衡法
10.3.2 擴展階段：類神經網路與深度學習
10.4 結語
10.5 練習題

第11章　平行化對局樹搜尋
11.1 前言
11.2 平行化之評估
11.2.1 Amdahl定律
11.2.2 超線性加速
11.3 共有記憶體之使用與管理
11.4 平行化Alpha-Beta切捨設計
11.4.1 主變化分割
11.4.2 弟節點等候
11.4.3 動態樹分割
11.5 平行化蒙地卡羅樹搜尋設計法
11.5.1 葉節點平行化
11.5.2 根節點平行化
11.5.3 整體同步之樹平行法
11.5.4 局部同步之樹平行法
11.5.5 延伸思考
11.6 結語
11.7 練習題

第12章　開局和殘局知識庫
12.1 前言
12.2 開局庫
12.2.1 開局庫之需求
12.2.2 開局庫製作
12.2.3 開局庫之建構方式
12.3 中局使用之布局
12.4 建構大型殘局庫
12.5 只使用主記憶體之回溯分析演算法
12.5.1 反覆前向檢查
12.5.2 分層反向傳遞與前向檢查
12.5.3 反向傳遞與未知子節點計數法
12.5.4 分層反向傳遞與未知子節點計數法
12.6 使用主記憶體和磁碟之回溯分析演算法
12.7 結語
12.8 練習題

第13章　進階研究課題
13.1 前言
13.2 圖形歷史交互作用
13.3 對手模型
13.4 隨機行為節點搜尋
13.5 證明數搜尋
13.5.1 二元值對局樹
13.5.2 證明數與反證數
13.5.3 多元值對局樹
13.5.4 延伸思考
13.6 結語
13.7 練習題

第14章　對局系統實作考量
14.1 前言
14.2 對局程式系統之研製
14.2.1 資源使用技巧
14.2.2 對局系統之製作
14.3 實戰驗證分析
14.4 結語
14.5 練習題

參考文獻
中文索引
英文索引

第1章 電腦對局研究概論（摘錄）

1.1　前言

自古以來，人類對於自身能力與靈魂存在等議題便抱持相當大的好奇心與幻想，大多數的宗教普遍認為人類具有靈魂，而靈魂賦予我們思考、感官、精神等。從人類具有靈魂的想法，進一步延伸到人類能夠思考並得到智慧的這個行為，開始探討「智慧」對於人類的重要性，認為靈魂和智慧具有一定的關係。西方文學在1818年就出現了科學幻想小說《Frankenstein》（科學怪人），內容便是講述生命體具智慧之創造概念，而1993年的科幻小說《The Positronic Man》（正子人）和2001年電影《A.I.人工智慧》（A.I. Artificial Intelligence）也都是描述賦予機器人智慧並進入人類生活中的未來世界。人們之所以會對這樣的議題感興趣，是因為我們認為，人類之所以能夠對社會有幫助，乃源於人類具有智慧，同時也可以進一步地假定，愈有智慧的電腦對人類的幫助愈大。

電腦被發明出來以後，因為其具有強大的運算能力，讓我們認為賦予電腦智慧是可行的，希望能夠藉由讓電腦得到智慧的這個行為，帶給人類更多的幫助。人工智慧（artificial intelligence）就是研究如何創造智慧，並將之賦予給電腦，讓電腦獲得智慧的學問。

電腦對局是人工智慧研究的顯學之一。選擇以電腦對局來研究電腦如何展現智慧的原因在於：自古以來下棋被看成是有智慧的行為，讓電腦學會下棋，是表現其智慧行為可能的方式之一。此外，智慧必須建築在充分的先備知識之上，但下棋看起來並不需要非常大量的先備知識即可進行，而且很容易藉由棋局的勝利與否來評斷電腦對於智慧行為的表現是否成功，因此我們以電腦對局作為本書課題。

本章一開始會從智慧所包含的意義開始討論，之後會介紹東方和西方研究電腦對局的歷史及一些會自動下棋的機器。電腦發明以後，我們才真正將對局技巧，結合演算法和搭配電腦硬體，讓電腦展現出下棋的能力。最後會針對各種對局進行分類，除了根據對局玩家的人數之外，最主要是根據對局規則產生的性質進行分類。

1.2　智慧

智慧所涵蓋的範圍相當廣泛，我們目前無法完全解釋智慧包含的所有意義，也無法展現出所有智慧的行為，而人工智慧的研究目標是要了解智慧，在了解智慧的內涵的過程中，必須要先找到一個準則來判斷電腦是否具有智慧。目前針對智慧行為表現最好的解釋方式，就是由計算理論研究巨擘Alan Turing所提出的Turing測試。

人類會專注於人工智慧研究的原因在於：人們希望能夠創造出具有智慧行為的電腦，用來改善與幫助人們的生活。或許人類的行為並不能夠表現出智慧的全部樣貌，但如果電腦能夠做出相似於人類的智慧行為，即便只是一部分智慧的行為表現，應該也能夠達到改善人類生活並幫助人類的目的。

1.2.1　Turing測試

Alan Turing於1950年提出Turing測試（Turing test）來嘗試定義何謂智慧行為。Alan Turing將智慧定義為「模仿人類的行為」，他認為如果機器具有智慧，那麼人類將無法分辨機器人與人類的差異為何，並以這個想法創造出Turing測試。利用特定的問題分別詢問受測電腦及人，詢問時觀測者無法得知回答是來自受測電腦或人，如果觀測者無法區分答案是來自人或受測電腦，則認定此受測電腦可以模擬人類行為，同時也判定其具有智慧。

Turing測試除了在人工智慧的研究中被拿來驗證電腦智慧表現的程度之外，同時也廣泛地存在於我們的生活裡。目前在線上系統或線上對局中，為了維護網站的安全與公平性，通常在某些關鍵的選項前會出現以Turing測試為概念的驗證碼測試。驗證碼為全自動區分電腦和人類的Turing測試（Completely Automated Public Turing test to tell Computers and Humans Apart, CAPTCHA）的俗稱，是用來區分操作者為電腦或人類。

Turing測試目前存在設計「Turing測試」與「反向Turing測試」兩個方向。人類的記憶、視覺、聽覺等辨識能力有一定的上限，過於繁雜的問題反而會讓人類無法或不想回答出正確的答案，隨著電腦能力的提升，如何設計出簡單且有效的Turing測試，分辨人類與電腦，是一個很不錯的研究方向。另一個研究方向則是如何讓電腦獲得智慧，並表現出更多屬於人類的行為：除了能夠正確地回答某些人類可以回答的問題，同時還要考慮到聽覺、嗅覺等，甚至於人類的情緒，在表現正確的行為時也能夠展現出人類的行為並不是那麼完美，如說謊、失誤等，達到更深一層的模擬，讓電腦的行為表現，與人類愈來愈符合。

有關於Turing測試的比賽，最著名的是自1990年開始Hugh Loebner與美國劍橋行為研究中心合作舉辦的羅布納獎（Loebner Prize）。羅布納獎一年舉辦一次，而它的競賽規則以Turing測試為基礎，讓電腦以對話的方式和裁判進行對談，若評審無法判斷對話的對象為人或電腦，則電腦獲勝，目前每年比賽冠軍均看似比歷年冠軍進步，但仍未能完全通過Turing測試。

1.2.2　延伸思考

從人類行為討論到智慧本身的存在，並且試圖對智慧作出定義，進而嘗試複製智慧，讓所有電腦都能夠獲得智慧，因為我們認為，智慧的存在能帶給人們生活更大的便利與改善，所以開始了人工智慧這門學問。然而在這樣的過程中，出現了幾個疑問：

˙ 人類所表現出來的每一個行為是否都具有智慧？
˙ 人類行為是否能夠完整地呈現出所有具有智慧的行為？
˙ 人類是否能夠與有智慧行為畫上等號？

智慧所蘊含的意義可能過於廣泛，人類對於智慧的認知也應是有限的。我們無法對智慧做出完整的定義，當然也無法呈現出所有智慧的行為。而人類所表現出來的行為，可能會因為學習認知、情緒失控、失誤等原因，無法讓每一個行為都看似有智慧，但這些反思緒反應，似乎也可以歸類成某種人類智慧的行為。

研究人工智慧的過程中，漸漸發覺有些智慧的行為同時可以被人類和電腦所表現出來，但是有些行為僅有人類或電腦才比較能夠呈現，亦即只有某一方能夠將這樣的智慧行為表現得淋漓盡致，如圖1.2所示，例如：電腦程式可以透過複雜的演算法，快速認證文件之數位簽名，可視為人類難以擁有的智慧行為之一。但人類可經由閱讀文章內容，推敲出文章可能的作者為誰，即是人類行為難以被電腦取代的例證。讓電腦獲得智慧的方式，一開始只讓電腦模仿人類的行為，但在賦予該模仿能力的過程中，同時也加深我們對智慧的了解，並找到某些只屬於電腦能表現的智慧行為，讓電腦從模仿人類智慧到創造出獨特的、有智慧的行為。

目前人工智慧的研究方向，並非讓電腦獲得廣泛的智慧，而是注重在各種不同的專家系統，讓電腦的智慧表現能夠應用在各種不同的領域中，給予人類更多幫助。

1.3　歷史

本節簡述中外歷史中和電腦對局相關研究的人、事及物。

1.3.1　18世紀的第一個西洋棋機器人

第一個看似會下西洋棋（Chess）的機器人由匈牙利的Wolfgang von Kempelen在18世紀晚期（約西元1770年）推出。從1770年到1854年的84年間，Maelzel西洋棋自動機到世界各地展覽，並擊敗了不少西洋棋的棋士，其中也包括了幾位名人：西班牙的特蕾西亞女皇、美國的班傑明．富蘭克林、普魯士王國的腓特烈二世、法國的拿破崙等。Maelzel西洋棋自動機最後被收藏在美國費城的巴爾的摩博物館（Peale Museum），直到1854年7月5日被一場大火燒毀。在這84年間，一直有許多人懷疑Maelzel西洋棋自動機的真實性，認為Maelzel西洋棋自動機裡其實是有人在操作。直到1857年，Maelzel西洋棋自動機的最後一個擁有者John K. Mitchell的兒子Silas Mitchell才在西洋棋月刊發表系列文章，將Maelzel西洋棋自動機事實上是由躲藏在機器中的真人所操作之真相公諸於世。

Maelzel西洋棋自動機最終雖被認為是一個騙局，但是在電腦弈棋的發展過程中，卻存在著相當大的意義：人類從18世紀開始，就嚮往著擁有智慧的機器，而且藉由弈棋的行為來表現智慧也被認為是可以達成的，因此這場騙局才能持續長達87年。
 
1.3.2　西洋棋殘局自動機

1914年巴黎世界博覽會，西班牙著名工程師Leonardo Torres y Quevedo首次公開展示的自動西洋棋盤，被認定是第一個會下棋的機器。Leonardo Torres y Quevedo將西洋棋盤上64格棋子的活動範圍，以電路和邏輯函數的方式表示，並成功作出可以解西洋棋中一車一王攻殺王的殘局（endgame），此殘局的攻擊方必須使用一車一王，用包夾的方式將死（checkmate）對手，才能夠獲勝。

1.3.3　東方的相關研究

琴、棋、書、畫合稱「四藝」，是中國古代文人相當推崇的四門藝術，其中的「棋」就是指弈棋。但由於傳統較不重視此技藝的發展，認為「雖小道，必有可觀者焉；致遠恐泥，是以君子不為也」，因此未對對局的智慧行為研究有進一步的著述。

北宋的沈括（Shen, Kuo）曾在《夢溪筆談》第18卷中說到：「唐僧一行曾算棋局都數，凡若干局盡之。余嘗思之，此固易耳，但數多，非世間名數可能言之，今略舉大數。凡方二路，用四子，可變八十一局，方三路，用九子，可變一萬九千六百八十三局。方四路，用十六子，可變四千三百四萬六千七百二十一局。方五路，……盡三百六十一路，大約連書萬字四十三，即是局之大數。……其法：初一路可變三局，一黑、一白、一空。自後不以橫直，但增一子，即三因之。凡三百六十一增，皆三因之，即是都局數。……又法：以自法相乘，得一百三十五兆八百五十一萬七千一百七十四億四千八百二十八萬七千三百三十四局，此是兩行，凡三十八路變得此數也。下位副置之，以下乘上，又以下乘下，置為上位；又副置之，以下乘上，以下乘下；加一法，亦得上數。有數法可求，唯此法最徑捷。只五次乘，便盡三百六十一路。千變萬化，不出此數，棋之局盡矣。」分析圍棋（Go）的棋局總數，他觀察到每一路可有一黑一白一空三種不同狀態，增加一子不同狀態數便要乘以3倍，因此共有了319x19種不同的狀態。一千年前就有這種非常好的演算法分析，而且詳細記載並分析了使用自我連續相乘的技巧來快速計算3n的演算法。