電腦對局導論 | 誠品線上

電腦對局導論

內容簡介

內容簡介 研究電腦如何下棋、解謎題和進行對局是資訊科學中研究人工智慧的重要一支。電腦對局的研究課題多元且具挑戰性，又因入門的條件較低、成效評定方式明確，故吸引許多人投入研究。本書有系統地蒐集並整理相關文獻，歸納電腦對局之精華要義，有助於入門者學習參考，奠定基礎。本書綜覽電腦對局研究，並特別注重演算法層次的引導式理解及討論，也描述演算法實作時所需的系統知識和技巧，兼顧理論和實際。研究電腦對局，終極目標不只是希望電腦在對局上能贏人類，而是在達成這目的的過程中，深入了解相關知識及應用。因此，與其說研究者在鑽研如何讓電腦「變聰明」，不如說透過演算法，研究者激發腦力，從而開創新的科學和技術發展，便利人類的生活。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 如何TEST7.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 最初的演算法：MCSpure9.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 練習題參考文獻中文索引英文索引

商品規格