黑 白 棋 自 我 學 習 的 改 進 策 略 賴 泳 伶 國 立 嘉 義 大 學 資 訊 工 程 學 系 張 孝 凡 國 立 嘉 義 大 學 資 訊 工 程 學 系 摘 要 本 文 提 出 一 個 黑 白 棋 程 式 的 自 我 學 習 策 略 我 們 首 先 以 動 態 程 序 (dynamic programming) 的 方 式 改 進 alpha-beta search 的 效 率, 再 利 用 動 態 搜 尋 時 間 的 方 式 進 行 自 我 對 奕, 作 開 局 資 料 庫 與 圖 樣 辨 識 (pattern recognize) 的 學 習, 讓 程 式 的 自 我 學 習 能 夠 在 微 幅 的 失 真 度 下, 大 幅 提 昇 學 習 速 度 經 過 調 整 圖 樣 辨 識 區 域 與 測 試 後, 證 實 我 們 的 自 我 學 習 策 略 能 在 小 幅 度 的 失 真 下, 顯 著 提 昇 自 我 學 習 效 率 這 個 策 略 經 過 修 正 後, 也 可 以 應 用 在 其 它 棋 戲 程 式 上, 作 為 原 演 算 法 的 輔 助, 提 昇 棋 戲 程 式 的 棋 力 關 鍵 詞 : 黑 白 棋 機 器 學 習 自 我 學 習 人 工 智 慧 1. 研 究 動 機 與 目 的 電 腦 棋 戲 程 式 運 用 人 工 智 慧 演 算 法, 經 過 各 方 先 進 多 年 的 研 究 與 改 進, 在 部 份 的 棋 戲 中, 已 設 計 出 許 多 遠 勝 於 人 腦 的 程 式 系 統 黑 白 棋 程 式 的 演 進, 就 屬 其 中 之 一 在 黑 白 棋 的 規 則 中, 限 制 落 子 後 必 須 能 翻 對 手 棋 子, 才 是 合 法 棋 步 [5], 因 此 每 一 手 棋 的 合 法 棋 步 侷 限 在 1( 即 使 是 pass, 也 是 一 種 合 法 棋 步 ) 至 15 步 上 下 ( 超 過 15 較 少 出 現 ), 平 均 約 在 8 步 左 右 這 樣 的 分 支 度 相 較 於 其 它 的 棋 戲 ( 如 圍 棋 平 均 超 過 200 步 象 棋 概 估 至 少 超 過 50 步 ), 可 說 遠 低 得 多 因 此 一 般 以 min-max 搜 尋 法, 配 合 alpha-beta cut 來 設 計 的 黑 白 棋 程 式, 即 使 審 局 函 數 (evaluation function) 的 設 計 並 不 十 分 講 究, 在 現 今 電 腦 的 高 速 執 行 下, 經 過 多 層 的 搜 尋 後, 均 能 有 良 好 的 棋 力 表 現 此 外 由 於 黑 白 棋 每 下 完 一 手 棋, 必 須 翻 轉 對 手 被 包 夾 的 棋 子, 因 此 棋 面 上 最 多 可 產 生 20 顆 棋 子 的 變 化 ( 自 己 下 一 顆 棋 子 + 1
翻 轉 對 手 19 顆 棋 子 ), 如 此 複 雜 的 盤 面 演 化, 使 得 人 腦 難 以 推 算 多 步 以 後 的 盤 面, 更 難 以 分 析 多 步 以 後 的 利 弊 得 失 因 此, 若 以 目 前 世 界 頂 尖 的 黑 白 棋 程 式, 與 人 類 黑 白 棋 冠 軍 對 奕, 結 果 可 說 程 式 將 會 獲 得 壓 倒 性 的 勝 利 從 搜 尋 的 角 度 分 析, 黑 白 棋 從 開 局 到 終 局, 平 均 雙 方 共 落 子 60 手, 若 要 搜 尋 出 第 一 步 棋 的 最 佳 解, 其 複 雜 度 為 O(n 60 ), 依 前 述 平 均 每 一 手 分 支 度 為 8 代 入 n, 則 約 為 1.5*10 54 這 樣 的 高 複 雜 度 告 訴 我 們, 程 式 無 法 在 短 時 間 內, 以 搜 尋 的 方 式, 完 成 最 佳 解 的 搜 尋 ( 事 實 上 即 使 搜 尋 幾 百 萬 世 紀 也 搜 尋 不 完 ) 再 從 盤 面 變 化 的 組 合 來 分 析, 黑 白 棋 使 用 的 是 8*8 的 棋 盤, 每 一 格 可 以 有 空 點 黑 棋 與 白 棋 三 種 變 化, 因 此 盤 面 最 多 有 3 64 ( 約 為 3.4*10 30 ) 種 組 合, 即 使 考 慮 對 稱 性, 並 將 部 份 不 可 能 出 現 ( 不 合 理 ) 的 盤 面 扣 除 掉, 其 空 間 複 雜 度 仍 會 是 個 天 文 數 字 因 此 在 黑 白 棋 的 世 界 裏, 雖 然 人 腦 的 棋 力 早 已 遠 不 如 電 腦, 但 在 先 手 或 後 手 必 勝 還 沒 有 被 證 明 出 來 之 前, 程 式 的 棋 力, 仍 舊 有 再 進 步 的 空 間 為 追 求 程 式 棋 力 的 精 進, 最 直 接 的 做 法, 就 是 改 進 審 局 函 數 的 精 確 度, 與 增 加 搜 尋 深 度 [2] 這 二 種 做 法 是 魚 與 熊 掌, 無 法 得 兼 舉 例 來 說, 能 佔 得 棋 盤 的 角 與 邊 的 棋 步, 可 能 是 比 較 好 的 棋 步 ; 或 是 能 迫 使 對 方 無 棋 可 下 的 棋 步, 也 可 能 是 較 佳 的 選 擇 於 是 藉 由 在 審 局 函 數 中, 加 入 這 些 分 析, 使 局 勢 判 斷 更 為 精 確 但 是 這 些 被 額 外 加 入 的 分 析, 勢 必 會 增 加 審 局 函 數 的 時 間 複 雜 度 也 就 是 說, 要 達 到 原 有 的 搜 尋 深 度, 必 須 耗 費 更 多 的 搜 尋 時 間 ; 或 是 在 相 同 的 搜 尋 時 限 內, 付 出 搜 尋 深 度 減 少 的 代 價 使 程 式 棋 力 提 昇 的 另 一 種 做 法, 則 是 製 做 開 局 資 料 庫 系 統 這 個 做 法 在 象 棋 [1] 與 在 黑 白 棋 [3] 的 應 用 上 都 已 被 提 出, 且 已 知 在 象 棋 上 有 良 好 的 表 現 這 類 資 料 庫 系 統 的 目 的, 在 大 量 蒐 集 棋 譜, 藉 由 資 料 的 累 積, 統 計 出 較 好 的 著 手, 作 為 開 局 時 的 輔 助 策 略 由 於 這 種 做 法 必 須 取 得 大 量 的 對 奕 記 錄, 因 此 多 在 網 路 上 取 得, 或 設 計 成 主 從 式 的 模 組, 讓 網 路 上 的 棋 友 進 行 對 奕 然 而 此 法 受 限 於 所 取 得 2
的 棋 譜 必 須 是 高 手 的 對 奕 結 果, 否 則 即 使 累 積 了 大 量 中 低 棋 力 者 的 對 奕 記 錄, 參 考 與 運 用 後 的 結 果, 恐 怕 也 不 會 有 較 佳 的 表 現 基 於 這 個 限 制, 我 們 不 禁 要 質 疑, 在 黑 白 棋 中 既 然 人 腦 棋 力 遠 不 如 電 腦 程 式, 那 麼 大 量 蒐 集 人 腦 對 奕 後 的 棋 譜, 對 程 式 棋 力 的 提 昇, 是 不 是 真 的 有 幫 助? 目 前 己 有 許 多 黑 白 棋 的 愛 好 者, 將 一 些 頂 級 的 黑 白 棋 程 式 自 我 對 奕 後 的 棋 譜, 與 近 年 來 多 次 世 界 比 賽 的 對 奕 棋 譜, 以 wthor 資 料 庫 的 格 式 [4] 儲 存, 並 在 網 路 上 公 佈 提 供 棋 友 下 載 [6] 這 些 公 開 的 資 料 庫 的 確 是 一 個 很 好 的 學 習 資 料 來 源, 但 當 電 腦 黑 白 棋 程 式 比 賽 時, 各 程 式 系 統 都 採 用 了 這 些 開 局 資 料 庫, 在 相 同 的 立 足 點 之 下, 要 能 夠 展 現 出 更 好 的 棋 力, 除 了 在 審 局 函 數 的 設 計 上 力 求 精 確, 和 改 進 搜 尋 效 率 外, 就 是 要 加 強 自 我 學 習 的 能 力, 才 能 使 棋 力 更 加 登 峰 造 極 現 在 已 有 許 多 頂 級 的 黑 白 棋 程 式, 如 WZebra Herakles Forest 等 等, 都 已 運 用 了 自 我 學 習 的 技 術, 並 多 方 蒐 集 wthor 資 料 庫 的 棋 譜, 轉 換 為 自 己 的 學 習 經 驗 這 些 世 界 知 名 的 程 式 除 了 具 有 低 複 雜 度 高 精 確 度 的 審 局 函 數 外, 還 大 幅 改 良 了 搜 尋 效 率, 使 程 式 本 身 就 具 備 了 高 水 準 的 棋 力 表 現 然 而 這 些 程 式 在 自 我 學 習 的 應 用 上, 僅 單 純 地 記 錄 對 奕 棋 譜, 用 來 作 為 開 局 資 料 庫, 而 沒 有 在 這 方 面 多 做 改 進 與 利 用, 著 實 可 惜 本 文 的 目 的, 在 提 出 一 個 增 進 黑 白 棋 自 我 學 習 效 率 的 策 略 程 式 以 alpha-beta search 為 設 計 主 軸, 利 用 動 態 程 序 的 技 術 強 化 搜 尋 效 率, 再 令 程 式 進 行 自 我 對 奕, 累 積 棋 譜, 進 行 棋 路 修 正 為 了 強 化 自 我 學 習 的 效 率, 我 們 在 自 我 學 習 的 過 程 中, 加 入 了 動 態 搜 尋 時 間 的 設 定, 與 圖 樣 辨 識 (pattern recognition) 的 學 習, 讓 程 式 的 學 習 能 夠 在 微 幅 的 失 真 度 下, 最 大 增 加 四 千 萬 倍 的 學 習 速 度 如 此 以 子 之 矛 攻 子 之 盾 地 反 覆 進 行 對 奕 與 學 習, 能 使 程 式 更 快 找 出 落 敗 的 關 鍵 棋 步, 從 而 補 強 原 搜 尋 法 的 弱 點, 使 程 式 棋 力 獲 得 提 昇 3
2. 方 法 我 們 的 黑 白 棋 程 式, 是 以 Borland C++ builder 6 設 計 完 成, 並 在 MS Windows 系 列 平 台 上 執 行 方 法 分 析 如 下 : 2.1. 棋 力 基 礎 : 搜 尋 演 算 法 是 利 用 Alpha-Beta cut, 在 指 定 的 搜 尋 時 限 內 進 行 搜 尋 由 於 黑 白 棋 的 搜 尋 複 雜 度 遠 大 於 盤 面 的 空 間 複 雜 度 ( 如 前 一 小 節 中 所 分 析 ), 因 此 經 由 不 一 樣 的 搜 尋 路 徑, 卻 產 生 相 同 盤 面 的 情 形 勢 必 會 經 常 發 生 故 為 了 增 進 搜 尋 效 率, 我 們 利 用 動 態 程 序 的 技 術, 在 搜 尋 過 程 中 記 錄 曾 經 出 現 的 盤 面, 並 儲 存 該 盤 面 被 搜 尋 展 開 後 所 傳 回 的 評 估 值 此 後 當 搜 尋 到 曾 經 展 開 過 的 盤 面, 就 可 以 直 接 套 用 先 前 的 評 估 值, 以 省 去 重 複 向 下 展 開 所 需 花 費 的 時 間 2.2. 自 我 學 習 : 如 同 其 它 知 名 程 式 的 開 局 資 料 庫, 我 們 的 程 式 也 是 將 自 我 對 奕 的 棋 譜, 儲 存 作 為 日 後 對 奕 的 開 局 知 識 庫 所 不 同 的 是, 我 們 以 2 秒 為 基 礎 搜 尋 時 限, 進 行 自 我 對 奕, 並 記 錄 自 我 對 奕 戰 績, 再 動 態 調 整 搜 尋 時 限 調 整 方 式 如 下 : T 2, T 2 ( S S ) / 2 if S S T 2, T 2 ( S S ) / 2 if S S T T 2 if S S W B B W W B B W W B W B W B W B 其 中 T W 與 T B 分 別 代 表 白 棋 方 與 黑 棋 方, 每 下 一 步 棋 所 允 許 使 用 的 思 考 時 限, 而 S W 與 S B 則 分 別 代 表 白 棋 方 與 黑 棋 方 自 我 對 奕 後 的 勝 場 數 動 態 調 整 搜 尋 時 限 有 三 大 優 點, 第 一 個 是 在 於 逐 漸 增 加 搜 尋 的 時 間, 相 對 地 很 有 可 能 使 搜 尋 深 度 增 加, 棋 路 的 正 確 性 也 就 大 有 可 能 因 此 提 高 這 會 使 得 落 敗 的 一 方, 有 較 大 的 機 會 能 以 較 高 的 搜 尋 深 度, 找 到 真 正 導 致 落 敗 的 較 差 棋 步, 作 出 正 確 的 修 正 第 二 個 優 點, 在 於 搜 尋 未 能 觸 及 終 局 前, 盤 面 的 優 劣 都 難 以 正 確 判 定, 因 此 修 正 結 果 也 有 可 能 是 錯 誤 的 在 這 樣 的 情 形 下, 錯 誤 的 修 正 導 致 再 度 落 敗 的 機 會 就 會 加 大, 於 是 在 再 度 落 敗 後, 程 式 會 自 動 再 增 加 搜 尋 時 間, 就 有 機 會 在 更 高 的 4
搜 尋 深 度 下, 將 錯 誤 的 修 正 重 新 更 正 回 來 第 三 個 優 點, 在 於 黑 白 棋 的 對 奕 中, 前 幾 步 的 優 劣 事 實 上 是 很 難 下 定 論 的 若 是 任 由 程 式 依 固 定 的 演 算 法 進 行 對 奕, 那 麼 對 奕 結 果 有 可 能 黑 白 勝 負 場 次 數 會 產 生 很 大 的 落 差 這 會 導 致 可 能 在 開 局 時 最 初 幾 步 棋 的 判 斷 上, 認 定 某 些 棋 步 是 最 佳 棋 步, 而 每 次 都 作 出 相 同 的 選 擇 ; 或 是 認 定 某 些 棋 步 是 最 差 棋 步, 就 再 也 不 走 出 那 些 棋 步 結 果 當 程 式 以 這 個 自 我 對 奕 的 資 料 庫, 去 跟 別 的 對 手 對 奕 時, 對 手 下 出 程 式 從 未 見 過 的 棋 形 的 機 會 就 會 大 幅 增 加, 自 我 對 奕 的 效 果 也 就 相 對 地 大 打 折 扣 這 個 問 題 雖 然 可 以 加 入 一 些 隨 機 (random) 選 擇 的 設 定 來 避 免, 但 是 與 其 讓 程 式 去 隨 機 作 決 定, 不 如 一 開 始 就 以 動 態 搜 尋 時 間 進 行 自 我 對 奕, 來 平 衡 開 局 時 的 勝 負 場 次 數, 拓 展 自 我 學 習 的 廣 度, 會 較 為 合 理 2.3. 圖 樣 辨 識 學 習 : 由 於 黑 白 棋 的 空 間 複 雜 度 甚 高, 因 此 為 了 加 速 自 我 學 習 的 效 果, 我 們 在 程 式 中 加 入 了 圖 樣 辨 識 的 學 習 我 們 觀 察 了 大 量 的 對 奕 棋 譜 後, 分 析 出 對 棋 局 影 響 最 大 的 區 塊, 和 部 份 較 不 具 影 響 力 的 區 塊 如 圖 1 中, 紅 色 區 塊 內, 最 對 棋 局 最 不 具 影 響 力 的 區 塊, 藍 色 區 塊 則 是 具 小 幅 度 影 響 力 的 區 塊, 其 餘 部 份, 才 是 對 棋 局 佔 有 決 定 性 影 響 的 區 塊 圖 1: 影 響 力 區 塊 示 意 圖 於 是 我 們 將 整 個 棋 盤 中, 扣 除 掉 紅 色 區 塊 以 外 的 區 域, 視 為 一 個 樣 本 (pattern), 讓 程 式 在 自 我 對 奕 的 過 程 中, 同 時 進 行 圖 樣 辨 識 的 學 習 這 樣 的 學 習 行 為 與 自 我 學 習 很 類 似, 一 樣 是 將 累 積 下 來 的 對 奕 結 果, 作 為 樣 本 的 評 估 值, 5
加 入 到 審 局 函 數 中, 視 為 盤 面 的 評 估 之 一 圖 樣 辨 識 的 運 用 不 同 於 棋 譜 比 對 的 地 方, 在 於 棋 譜 比 對 是 將 搜 尋 第 一 層 的 棋 形 比 對 棋 譜 權 重 後, 將 權 重 套 用 於 搜 尋 展 開 該 棋 形 後 的 所 有 棋 形 上 ; 而 圖 樣 辨 識 則 是 在 搜 尋 到 限 制 最 底 層 時, 才 比 對 圖 樣 的 權 重 ( 如 圖 2) 棋 形 比 對 權 重 套 用 在 第 一 層 以 下 所 有 節 點 目 前 棋 形 圖 樣 辨 識 權 重 僅 套 用 於 搜 尋 底 層 節 點 圖 2: 棋 形 與 圖 樣 辨 識 在 搜 尋 時, 套 用 點 差 異 處 示 意 圖 我 們 不 把 棋 形 比 對 應 用 在 搜 尋 底 層 的 原 因, 在 於 自 我 學 習 即 使 給 予 數 十 年, 甚 至 上 百 年 的 長 時 間 學 習 後, 在 對 奕 中 也 可 以 在 開 局 後 二 十 手 棋 之 內, 就 出 現 不 曾 見 過 的 棋 形 若 再 將 棋 形 比 對 放 在 搜 尋 底 層, 那 麼 扣 除 掉 搜 尋 深 度, 可 能 在 開 局 後 十 步 棋 內, 就 會 搜 尋 到 不 曾 見 過 的 棋 形 這 樣 的 應 用 對 於 平 均 要 下 60 手 才 終 局 的 黑 白 棋 而 言, 棋 形 比 對 的 效 果 若 只 能 運 用 在 整 局 棋 的 前 四 分 之 一, 似 乎 就 顯 得 太 微 乎 其 微 因 此 我 們 將 它 應 用 在 搜 尋 的 第 一 層, 較 能 作 更 深 入 的 應 用 反 觀 圖 樣 辨 識, 由 於 忽 略 了 中 央 16 格 的 變 化, 因 此 每 記 錄 一 個 圖 樣, 就 等 於 是 記 錄 了 3 16 種 不 同 的 棋 形, 若 再 考 慮 對 稱 性, 並 扣 除 掉 少 部 份 不 可 能 出 現 的 棋 形, 記 錄 一 個 圖 樣, 也 相 當 於 記 錄 近 4 千 萬 個 棋 形 的 學 習 效 果 由 於 圖 樣 辨 識 忽 略 了 中 央 16 格 的 變 化, 因 此 在 少 部 份 的 盤 面 評 估 上, 會 有 些 微 的 誤 差, 因 此 我 們 將 圖 樣 辨 識 應 用 在 搜 尋 最 底 層, 作 為 審 局 函 數 的 一 個 權 值, 並 以 略 低 於 棋 形 比 對 的 權 重 作 評 估, 就 能 利 用 圖 樣 的 累 積, 大 幅 提 昇 學 習 效 果, 改 進 學 習 效 率 6
3. 結 果 與 討 論 在 Alpha-Beta search 中, 運 用 動 態 程 序 的 技 術 後, 我 們 設 定 每 一 步 的 搜 尋 時 限 為 2 秒, 進 行 自 我 對 奕 與 效 果 評 估, 成 果 如 表 1 表 1: 運 用 動 態 程 序 (dynamic programming) 加 速 的 搜 尋 效 果 第 7 手 第 14 手 第 21 手 第 28 手 第 35 手 第 42 手 第 49 手 Alpha-beta search 深 度 5 5 4 5 5 5 9 dynamic programming 加 速 後 搜 尋 深 度 6 5 5 6 6 7 12 平 均 hit rate (%) 7.4 6.6 5.3 7.1 9.4 12.8 19.6 從 表 1 中 可 以 看 得 出 來, 應 用 動 態 程 序 法 加 速 搜 尋 後, 在 開 局 與 終 局 的 搜 尋 效 果 上, 有 明 顯 的 改 進, 因 此 能 有 效 的 節 省 下 多 餘 的 展 開 時 間, 作 更 深 入 的 搜 尋 尤 其 在 接 近 終 局 附 近 的 搜 尋 中, 平 均 有 約 二 成 的 棋 形 是 搜 尋 過 的, 這 對 終 局 前 的 完 整 搜 尋 (perfect searching), 可 說 具 有 相 當 大 的 助 益 附 帶 一 提 的 是, 由 於 發 現 搜 尋 過 的 棋 形 時, 該 棋 形 就 會 直 接 套 用 評 估 值, 以 下 也 就 不 會 再 多 作 展 開, 因 此 實 際 上 重 複 的 棋 形, 在 比 例 上 會 比 表 1 中 的 正 確 率 (hit ratio) 大 得 多 在 動 態 調 整 搜 尋 時 間 方 面 的 測 試, 經 過 4 星 期 的 自 我 學 習 後, 能 有 效 平 衡 開 局 時 前 幾 步 的 勝 負 比 例, 擴 展 初 期 的 分 支 度 表 2 為 每 學 習 4 天, 與 知 名 程 式 WZebra 對 奕 時, 學 習 資 料 能 運 用 到 的 最 深 層 數 比 較 表 2: 與 WZebra 對 奕 時 開 局 資 料 運 用 深 度 第 4 天 第 8 天 第 12 天 第 16 天 第 20 天 第 24 天 第 28 天 自 我 對 奕 思 考 時 限 固 定 3 秒 動 態 調 整 自 我 對 奕 思 考 時 限 已 完 成 廣 度 學 習 的 層 數 6 7 7 6 8 8 9 7 8 9 10 10 11 11 5 5 5 6 6 6 6 表 2 中 顯 示, 利 用 動 態 調 整 自 我 對 奕 思 考 時 間 的 方 式, 可 以 使 自 我 對 奕 的 廣 度 平 均 而 穩 定 地 增 加, 同 時 由 於 動 態 調 整 思 考 時 限, 使 程 式 在 面 對 增 加 思 考 時 間 7
的 對 手 時, 就 等 於 是 在 和 棋 力 較 高 的 對 手 下 棋, 進 行 學 習, 也 就 能 汲 取 更 好 的 學 習 經 驗, 使 棋 力 提 昇 在 圖 樣 辨 識 方 面 的 學 習, 我 們 以 圖 3 中 的 三 種 圖 樣 區 塊, 進 行 分 析 與 測 試 目 的 在 確 認 出 失 真 度 最 低 可 忽 略 區 塊 最 大 的 圖 樣 區 塊 (a) (b) (c) 圖 3: 三 種 不 同 的 圖 樣 辨 識 區 塊 圖 3 中 紅 色 圓 點 表 示 被 選 用 的 辨 識 區 域, 其 餘 空 點 為 被 忽 略 變 化 的 區 域 我 們 從 網 路 上 隨 機 選 取 40 個 棋 譜, 再 將 棋 譜 分 別 以 圖 3 中 的 3 種 不 同 的 辨 識 區 域 抽 取 出 來, 最 後 在 被 忽 略 區 域 中, 以 隨 機 產 生 的 100 種 盤 面 組 合 填 入, 分 別 進 行 完 整 搜 尋 其 中 正 確 率 的 計 算, 是 取 將 前 述 的 100 種 盤 面 組 合 中, 每 一 個 盤 面 的 完 整 搜 尋 後, 黑 白 雙 方 勝 負 結 果 一 致 的 比 率, 而 失 真 度 則 是 正 確 率 的 補 值 取 平 均 值 後, 失 真 率 測 試 結 果 列 於 表 3 表 3; 辨 識 區 塊 失 真 率 測 試 結 果 第 43 手 第 46 手 第 49 手 第 52 手 第 55 手 區 塊 a 30% 27% 26% 19% 15% 區 塊 b 42% 40% 41% 33% 19% 區 塊 c 47% 43% 44% 42% 37% 從 表 3 中 可 以 清 楚 地 看 出 來, 區 塊 a 的 失 真 率 最 低, 且 越 接 近 終 局, 正 確 率 就 越 高 因 此, 我 們 將 圖 樣 辨 識 放 在 搜 尋 的 底 層, 可 在 越 接 近 終 局 時, 獲 得 良 好 的 評 估 效 果 最 後, 我 們 將 另 一 知 名 黑 白 棋 程 式 Deep green 設 定 搜 尋 深 度 為 六 層, 審 局 函 8
數 的 難 度 設 定 為 最 高, 並 將 我 們 的 程 式 設 定 搜 尋 時 限 為 2 秒, 再 進 行 對 奕 測 試 我 們 發 現 Deep green 除 了 在 開 局 前 6~8 手, 與 接 近 終 局 前 10~12 手 棋, 搜 尋 能 在 1~2 秒 內 完 成, 其 餘 中 局 的 思 考 時 間 都 超 過 2 秒, 最 多 還 會 達 到 8~10 秒, 平 均 搜 尋 時 間 約 需 4 秒 而 我 們 的 程 式 設 定 固 定 搜 尋 時 間 2 秒, 在 開 局 時 搜 尋 深 度 約 在 8~10 層, 中 局 降 至 5~7 層, 終 局 前 12 手 可 完 成 完 整 搜 尋 這 表 示 我 們 的 程 式 能 以 平 均 較 短 的 搜 尋 時 間, 達 到 比 Deep green 更 高 的 搜 尋 深 度, 顯 示 我 們 的 程 式 搜 尋 效 率 比 Deep green 佳 在 學 習 效 果 評 估 方 面, 初 期 還 沒 有 進 行 自 我 學 習 前, 我 們 的 程 式 就 能 在 50 次 先 後 手 各 半 的 對 奕 中, 取 得 35 次 的 勝 績 在 進 行 2 星 期 的 自 我 學 習 後, 再 進 行 對 奕 測 試, 我 們 的 程 式 在 50 次 的 對 奕 中, 取 得 了 42 次 的 勝 績, 顯 示 自 我 學 習 已 使 程 式 的 棋 力, 獲 得 了 明 顯 的 進 步 另 外, 在 對 世 界 級 的 程 式 Wzebra 的 對 奕 測 試 中, 我 們 的 程 式 初 期 還 沒 有 進 行 自 我 學 習 前, 50 次 的 先 後 手 各 半 的 對 奕 中, 我 們 取 得 12 次 的 勝 績 ; 經 過 2 星 期 的 學 習 後, 我 們 的 程 式 就 能 進 步 到 取 得 17 次 的 勝 績 這 個 結 果 顯 示, 我 們 的 程 式 在 評 估 函 數 的 設 計 上 不 如 Wzebra 精 確, 以 致 基 礎 棋 力 不 如 Wzebra, 但 在 進 行 學 習 後, 同 樣 能 獲 得 顯 著 的 棋 力 提 昇 4. 結 論 我 們 利 用 動 態 調 整 搜 尋 時 間 的 方 式, 與 圖 樣 辨 識 的 技 術, 研 擬 出 一 個 更 有 效 率 的 黑 白 棋 自 我 學 習 策 略 經 過 測 試 後, 我 們 證 實 利 用 這 樣 的 策 略, 能 使 整 體 自 我 學 習 效 率 大 幅 提 昇 未 來 我 們 將 再 調 整 審 局 函 數 的 精 確 性, 使 程 式 的 基 礎 棋 力 再 提 昇, 將 有 希 望 挑 戰 世 界 級 的 Wzebra 等 黑 白 棋 程 式 對 於 其 它 的 棋 戲 程 式, 可 應 用 我 們 的 自 我 學 習 策 略, 配 合 不 同 棋 戲 規 則, 作 適 度 的 修 正, 能 強 化 其 原 有 演 算 法 的 弱 點, 進 而 獲 得 更 高 的 棋 力 9
參 考 文 獻 [1] 許 舜 欽, 電 腦 象 棋 開 局 知 識 庫 系 統 之 研 製, 台 大 工 程 學 刊, 第 53 期, Oct. 1991,pp.75-86 [2] 許 舜 欽, 電 腦 對 局 的 搜 尋 技 巧, 台 大 工 程 學 刊, 第 51 期,Feb. 1991, pp. 17-31 [3] 陳 志 昌 徐 明 煒 : Othello 開 局 資 料 庫 系 統 之 研 製 台 灣 大 學 資 訊 工 程 研 究 所,TAAI2002 [4] par Sylvain Quin, Format de la base Wthor, available at http://www.ffothello.org/info/format_wthor.pdf [5] 黑 白 棋 規 則,available at http://www.othello.org.hk/ [6] 近 年 Othello 棋 戲 程 式 比 賽 記 錄 之 Wthor 資 料 庫 格 式 儲 存 檔 案,available at http://www.disco.com.hk/ 10