Artificial Intelligence Project The Othello Game NTU CSIE B87506017, Chen-hsiu Huang ( 黃 振 修 ) 執 行 畫 面 本 程 式 使 用 Borland C++ Builder 製 作, 在 任 何 Windows 平 台 皆 可 執 行 解 開 壓 縮 檔 之 後 位 於 Run\ 子 目 錄 下 的 Othello.exe 即 是 執 行 檔, 直 接 執 行 即 可 黑 白 棋 遊 戲 規 則 黑 白 棋 的 主 要 用 具 是 一 塊 8x8 空 格 的 Othello board ( 多 數 是 綠 底 ), 另 外 有 64 個 圓 形 棋 子 ( 正 式 尺 寸 是 直 徑 3.5 cm), 兩 面 分 別 為 一 黑 一 白 香 港 坊 間 有 一 種 質 素 劣 的 棋 盤, 棋 子 是 用 紅 色 和 綠 色 的, 但 兩 者 完 全 是 沒 有 分 別 的
圖 1 初 期 配 置 下 子 方 法 圖 2 黑 F5 之 後 盤 面 的 初 期 配 置 可 參 看 圖 1, 值 得 留 意 的 是, 兩 顆 黑 子 都 是 在 E4 D5 兩 個 方 格 上, 請 不 要 弄 錯, 否 則 棋 盤 就 看 得 不 舒 服 了 放 好 棋 子 後, 雙 方 就 輪 流 下 子, 注 意 黑 棋 永 遠 是 先 下 的 一 方 下 子 的 方 法 是 : 把 自 己 顏 色 的 棋 子 放 在 棋 盤 上 的 空 格 上, 而 當 自 己 放 下 的 棋 子 在 橫 直 斜 八 個 方 向 內 有 令 一 個 自 己 的 棋 子, 則 被 夾 在 中 間 的 全 部 會 成 為 自 己 的 棋 子 例 如 在 圖 1, 黑 如 果 下 F5, 因 為 D5 的 黑 子, 中 間 在 E5 原 本 為 白 色 的 棋 子 會 變 成 黑 色, 成 了 圖 2 的 模 樣 當 然, 黑 棋 除 了 下 F5 以 外, 也 可 以 下 E6 C4 D3 之 其 中 一 處, 但 因 為 它 們 都 是 對 稱 的 關 係, 因 此 為 方 便 起 見, 很 多 時 候 都 會 以 F5 作 為 第 一 手 棋 之 後, 白 棋 可 以 有 更 多 下 子 選 擇 了 例 如, 白 棋 下 D6 便 可 以 將 位 於 D5 變 成 白 子 ( 圖 3a), 而 白 棋 下 不 同 的 地 方, 就 會 有 不 同 的 效 果 ( 圖 3b,c) 圖 3a 白 棋 下 D6 後 的 盤 面 圖 3b 白 棋 下 F6 圖 3c 白 棋 下 F4 隨 著 棋 盤 上 的 子 越 來 越 多, 你 可 以 在 一 步 內 反 到 的 棋 子 也 多 了 假 如 下 棋 的 一 方 在 橫 直 斜 同 時 有 自 己 的 棋 子, 中 間 的 所 有 棋 子 都 會 轉 為 我 色 棋 子, 例 如 在 圖 4, 白 棋 如 下 F5, 則 D3-E4 E5 D7-E6 F3-F4 F6-F7 G5 G4 和 G6 間 的 黑 子 都 被 夾 住 了, 它 們 都 全 部 成 為 白 棋 的 棋 子 成 了 圖 4b 正 因 為 如 此, 在 一 局 棋 最 後 的 數 手 內, 雙 方 棋 子 的 數 目 可 以 有 很 大 的 改 變
圖 4a 此 時 如 果 白 棋 下 F5 位 圖 4b 白 棋 多 了 十 個 棋 子 了 ( 以 上 資 料 取 自 黑 白 棋 中 文 主 題 網 頁 Hello! Othello ) 黑 白 棋 的 技 巧 角 點 C-squares 和 X-squares 在 黑 白 棋 中 最 受 注 目 的 地 方, 都 不 離 開 這 三 種 點 : 角 C-squares 和 X-squares 圖 10 角, 就 正 如 上 節 所 提, 是 建 立 Stable disc 的 好 地 方, 價 值 很 高 但 是, 黑 白 棋 除 了 四 個 角 外, 還 有 其 他 很 值 得 留 意 的 地 方, 包 括 X-square 和 C-squares, 它 們 的 位 置 就 如 左 圖 10 所 示 右 圖 中 的 小 藍 點 就 是 角 了 大 家 可 以 見 到, C-square 和 X-square 都 是 在 它 的 周 圍, 因 此 下 這 些 方 格 有 一 定 的 危 險 性 現 在 就 解 釋 一 下 : C-square 是 在 邊 上 (edge) 和 角 相 鄰 的 方 格, 下 這 些 方 格 有 時 並 不 代 表 即 時 的 危 險, 因 為 如 果 可 以 同 時 佔 到 一 條 邊 上 的 兩 個 C-square 且 對 稱, 那 多 數 是 邊 上 的 好 形 ( 有 關 邊 上 的 好 形, 我 們 會 留 待 以 後 章 節 再 討 論 ) 此 外, 就 算 只 佔 了 一 個 C-square, 角 上 亦 未 有 即 時 危 險 舉 個 例 子, 圖 10 中 的 白 子 在 一 條 邊 只 佔 到 了 一 個 C-squqare, 假 如 黑 棋 來 子 ( 圖 11), 希 望 在 下 一 步 取 到 角 ( 三 角 形 位 ), 但 下 步 白 子 只 需 要 吃 掉 它 就 可 以 了, 黑 棋 以 後 亦 無 計 可 施 ( 圖 12) 假 如 黑 棋 再 下 A 位, 則 白 B 位 取 角, 黑 吃 大 虧
圖 10 圖 11 黑 棋 想 拿 角 的 時 候.. 圖 12 白 棋 的 反 擊 當 然, C-square 始 終 都 在 角 的 左 右, 下 C-square 雖 然 不 能 令 對 方 立 刻 取 得 角, 可 是 這 樣 下 會 令 對 方 在 其 他 地 方 有 手 段 ( 例 如 換 角 等 ), 籍 威 脅 角 地 在 其 他 地 方 取 利 棋 力 高 的 讀 者, 一 定 知 道 甚 麼 是 Stoner Traps, 這 就 是 利 用 C-square 取 利 的 好 例 子 當 然 大 家 繼 續 看 的 時 後, 就 會 知 道 一 些 利 用 C-square 的 手 筋 至 於 X-square 就 是 指 在 對 角 線 上 和 角 相 鄰 的 方 格, 全 個 棋 盤 上 總 共 有 四 個 論 危 險 性, X-square 就 比 C-square 高 得 多 因 為 只 要 你 下 X-square, 對 方 就 差 不 多 可 以 肯 定 得 到 了 一 隻 角 圖 13 中, 黑 棋 佔 了 右 上 X-squares, 雖 然 白 棋 不 能 即 時 取 角 ( 三 角 形 位 ), 但 是 只 要 白 棋 做 些 準 備 工 夫 ( 圖 14), 黑 棋 就 沒 有 辦 法 阻 止 對 方 得 角, 於 是 白 棋 便 勝 定 了 圖 13 黑 棋 佔 了 X-squares 圖 14 右 上 角 必 然 為 白 棋 所 有 Mobility Mobility 是 指 一 方 可 以 下 子 的 空 格 數 目, Mobility 越 高, 自 已 的 形 勢 就 越 好 棋 中 段 如 取 太 多 子,Mobility 多 數 會 因 而 降 低 以 下 所 提 的 都 是 黑 白 棋 的 好 形 : 棋 子 不 太 多 自 己 的 棋 子 凝 成 一 團 ( 這 正 好 和 圍 棋 相 反, 是 不 是? ) 相 反, 有 關 Mobility 惡 形 就 是 : 大 量 棋 子 所 形 成 的 棋 形 自 己 棋 子 各 散 四 周 的 棋 形 形 成 厚 壁 的 棋 形
( 以 上 資 料 取 自 黑 白 棋 中 文 主 題 網 頁 Hello! Othello ) 穩 定 子 (Stability) 有 一 些 下 黑 白 棋 經 驗 的 人 都 知 道, 占 住 棋 格 的 四 個 角 落 很 重 要, 因 為 下 在 角 落 的 子 不 會 被 別 人 吃 掉, 是 穩 定 的 這 一 點 對 於 最 多 吃 子 法 和 最 少 吃 子 法 來 說 都 是 一 樣 的 防 止 對 手 取 得 角 落 的 方 法 是, 不 要 在 靠 近 角 落 的 三 個 格 子 內 下 子 (X-Square, C-Square) 當 然, 接 近 終 局 時 有 時 會 犧 牲 角 落 來 換 得 其 他 地 方 的 優 勢 在 邊 上 的 棋 子 只 能 被 一 個 方 向 吃 掉, 而 遊 戲 初 期 是 很 難 吃 掉 對 方 邊 上 的 子 的, 所 以 最 多 吃 子 法 會 儘 量 佔 據 棋 格 的 四 條 邊 而 最 少 吃 子 法 則 不 會, 因 為 在 邊 上 的 子 如 果 沒 有 貼 著 角 落, 就 是 不 穩 定 的 棋 子 圖 一 很 好 的 說 明 了 這 一 點, 白 棋 佔 據 了 四 條 邊, 但 最 後 都 被 吃 光 了 那 麼 什 麼 叫 穩 定 子 呢? 一 個 簡 單 的 判 定 方 法 是, 在 棋 子 的 橫 豎 撇 捺 四 條 線 上, 如 果 線 的 一 個 方 向 全 是 自 己 的 棋 子 或 邊 界, 或 是 線 的 兩 個 方 向 都 填 滿 了 棋 子, 則 稱 這 條 線 是 穩 定 的 如 果 棋 的 四 條 線 是 穩 定 的, 則 稱 這 個 棋 子 是 穩 定 的 如 圖 二 示, 黑 方 已 經 有 33 個 穩 定 子, 就 是 說 不 會 被 別 人 吃 掉 的 子, 因 此 在 接 下 來 的 比 賽 中, 想 輸 掉 都 沒 有 可 能 了 ( 因 為 33>64/2) 圖 一 圖 二 ( 以 上 資 料 取 自 黑 白 棋 世 界 )
程 式 演 算 法 程 式 主 要 利 用 MinMax Algorithm 來 作 為 搜 尋 的 演 算 法 在 簡 單 的 模 式 中 我 們 往 下 推 兩 層, 普 通 模 式 中 往 下 推 四 層, 高 難 度 模 式 則 是 往 下 推 六 層 主 要 的 程 式 寫 在 TOthello.cpp 中, 以 一 個 TOthello 物 件 代 表 遊 戲 狀 態 在 每 一 個 回 合 中, 搜 尋 函 式 Search(), 依 次 序 呼 叫 alphasearch() 以 及 betasearch() 函 數 分 別 代 表 白 棋 以 及 黑 棋 所 選 擇 的 下 法 : void TOthello::Search() { int i, j; int best_x = -1, best_y = -1; int score, maxscore = -99999; bool done = false; deep = 0; TOthello saved_state; saved_state = *this; for(i = 0; i < 8; i++) for(j = 0; j < 8; j++) if(checkallow(j, i)) { board[i][j] = OTHELLO_WHITE; changeboard(j, i); score = alphasearch(*this, 0); if(score > maxscore) { maxscore = score; best_x = j; best_y = i; // restore last board *this = saved_state; // determine the best decision if(best_x!= -1 && best_y!= -1) { PutDown(best_x, best_y); done = true; if(!done) turn *= -1; int TOthello::alphaSearch(TOthello state, int d) { int i, j, value = 0; int score, maxscore = 1000000; if(d >= depth) return state.evail(othello_white);
for(i = 0; i < 8; i++) for(j = 0; j < 8; j++) { if(checkallow(j, i)) { state.board[i][j] = OTHELLO_WHITE; state.changeboard(j, i); value = state.evail(othello_white); score = value + state.alphasearch(state, d + 1); maxscore = score > maxscore? score: maxscore; return maxscore; int TOthello::betaSearch(TOthello state, int d) { int i, j, value = 0; int score, minscore = 1000000; if(d >= depth) return state.evail(othello_black); for(i = 0; i < 8; i++) for(j = 0; j < 8; j++) { if(checkallow(j, i)) { state.board[i][j] = OTHELLO_BLACK; state.changeboard(j, i); value = state.evail(othello_black); score = state.alphasearch(state, d + 1) - value; minscore = score > minscore? score: minscore; return minscore; 估 值 函 數 (Evaluation Function) 在 設 計 AI 的 程 式 中, 遊 戲 的 好 壞 取 決 於 估 值 函 數 的 好 壞 因 此 我 根 據 網 路 上 找 到 有 關 下 黑 白 棋 的 技 巧 ( 如 上 述 ) 自 行 設 計 估 值 函 數 我 的 估 值 函 式 是 以 加 權 方 式 計 算, 落 子 在 越 好 的 地 方 加 的 分 數 越 高 ( 例 如 角 點 ), 而 一 開 始 盡 量 不 要 去 下 C-Square 點 ( 因 為 很 有 可 能 因 此 角 點 被 對 方 搶 走 ), 所 以 如 果 是 落 在 C-Square 或 是 X-Square 上 面 的 點 會 以 扣 分 方 式 處 理 而 邊 上 的 點 更 是 重 要, 加 的 分 數 也 很 高 另 外 就 是 如 果 我 方 佔 住 角 點, 該 角 點 的 C-Square 和 X-Square 就 應 該 去 下, 這 裡 乘 上 負 號 以 達 到 加 分 效 果 另 外 穩 定 線 也 是 很 重 要 的 我 們 給 予 棋 面 上 的 穩 定 線 額 外 的 加 分, 讓 於 是 程 式 就 會 試 著 去 製 造 穩 定 線, 並 試 著 去 打 破 對 方 的 穩 定 線 ( 這 部 分 的 效 果 很 好, 但 卻 是 我 的 黑 白 棋 程 式 致 命 的 弱 點, 容 後 再 敘 )
一 旦 程 式 每 佔 到 一 個 角 點, 就 應 該 盡 可 能 的 促 使 穩 定 線 的 行 程, 所 以 每 佔 到 一 個 角 點 都 會 提 高 穩 定 線 加 分 CORNER = 3000; MOBILITY = 30; STABLE = 25; XSTABLE = 50; C_SQUARE = -1000; X_SQUARE = -900; EDGE = 900; THIRD_SQUARE = 500; 以 上 是 我 預 設 的 計 分 方 式, 部 分 加 權 會 隨 著 局 勢 改 變 估 值 函 數 為 TOthello::evail(), 每 回 合 的 盤 面 局 勢 是 以 己 方 減 去 對 方 的 分 數 為 考 量 程 式 評 估 感 覺 上 這 個 程 式 好 像 會 蠻 厲 害 的, 其 實 不 然 稍 微 善 用 技 巧 的 人 通 常 可 以 藉 由 佔 邊 或 是 角 點 而 取 得 優 勢 因 為 穩 定 邊 及 盤 面 棋 數 的 考 量, 程 式 往 往 會 在 開 局 及 中 局 拼 命 製 造 穩 定 邊, 所 以 開 局 或 是 中 局 電 腦 棋 數 往 往 很 多, 進 而 忽 略 對 邊 和 角 點 的 攻 佔, 等 對 方 佔 到 邊 或 是 角 點 之 後, 往 往 就 被 豬 羊 變 色, 因 而 慘 敗 那 麼 我 試 著 調 高 對 邊 和 角 點 的 加 權 分 數, 但 是 這 裡 會 遇 到 一 個 問 題 : 因 為 邊 的 加 分 太 高, 讓 程 式 選 擇 去 下 該 死 的 C-Square 點, 因 為 這 個 加 分 機 制, 往 往 可 以 刻 意 製 造 陷 阱 騙 程 式 去 下 C-Square 點, 然 後 程 式 上 當 之 後 對 方 就 很 容 易 佔 到 角 點, 於 是 又 是 一 次 豬 羊 變 色 我 發 現 這 裡 的 加 分 機 制 間 的 差 距 扮 演 相 當 重 要 的 角 色, 角 點 比 邊 點 重 要, 那 麼 他 的 分 數 應 該 是 邊 點 的 幾 倍? C-Square 以 及 X-Square 點 應 該 扣 多 少 才 會 讓 程 式 不 去 下 這 兩 點, 確 又 不 會 因 為 扣 分 過 多 讓 程 式 不 去 搶 邊 點? 程 式 寫 好 之 後 我 為 了 調 整 這 些 數 字 花 了 兩 天 的 時 間, 總 是 無 法 調 出 一 個 滿 意 的 數 值, 往 往 是 顧 此 失 彼, 邊 角 一 旦 失 守, 製 造 再 多 的 穩 定 邊 也 沒 用, 盤 面 上 的 棋 數 更 是 不 準 確 我 和 室 友 討 論 一 整 夜 的 結 論 是 : 這 樣 的 加 分 方 式 很 難 躲 過 技 巧 性 的 欺 騙, 多 下 幾 次 就 可 以 猜 出 程 式 在 想 什 麼, 會 去 搶 什 麼 位 置, 優 先 次 序 是 怎 樣, 總 是 可 以 找 到 破 解 方 式 我 們 在 想 也 許 這 時 候 就 需 要 有 棋 譜 的 幫 忙 吧? 累 積 經 驗 幫 助 程 式 不 易 受 騙 可 是 這 個 專 題 沒 有 時 間 讓 我 去 作 這 樣 的 大 工 程
比 後 來 我 找 了 網 路 上 其 他 的 黑 白 棋 程 式, 發 現 都 我 的 程 式 強, 我 找 了 一 個 程 式 來 看 的 的 原 始 碼, 發 現 他 的 估 值 函 式 非 常 簡 單, 只 有 判 斷 角 點 和 邊 點, 其 他 的 全 靠 盤 面 上 的 棋 子 數 定 勝 負 ( 而 我 的 棋 子 數 卻 是 加 權 最 低 的 ), 然 後 剩 下 的 就 靠 搜 尋 去 找 出 最 佳 解 既 然 找 不 到 最 好 的 加 分 方 式, 就 乾 脆 不 要 理 他, 讓 搜 尋 和 盤 面 結 果 去 決 定 一 切, 這 反 而 是 最 直 接 了 當 的 作 法, 我 過 分 考 慮 各 種 狀 況 ( 當 然 考 慮 這 些 狀 況 都 是 對 的 ), 反 而 因 為 找 不 出 最 佳 的 加 分 方 式 而 吃 大 虧 ( 由 此 可 見 Evaluation Function 的 重 要 性 ) 後 來 繼 續 跟 室 友 討 論, 即 使 找 到 最 佳 的 加 分 方 式, 對 邊 角 點 有 最 好 的 攻 防, 只 要 玩 家 不 去 裡 那 些 邊 角 之 爭, 拼 命 找 穩 定 邊 穩 定 子, 還 是 有 機 會 贏 的 心 得 感 想 雖 然 花 了 好 幾 天 的 心 力 寫 出 一 個 笨 笨 的 黑 白 棋 程 式, 心 裡 有 點 沮 喪, 但 總 還 是 知 道 到 底 問 題 出 在 哪 裡, 用 最 直 接 單 純 的 作 法 反 而 最 好 不 過 因 為 期 末 的 關 係, 也 沒 什 麼 時 間 在 去 重 寫, 重 新 測 試 了 就 把 這 個 笨 笨 的 黑 白 棋 程 式 當 成 是 個 紀 念 吧! 參 考 網 站 1. 黑 白 棋 評 論 Disco Othello World (http://www.disco.com.hk/) 2. 黑 白 棋 中 文 主 題 網 頁 Hello! Othello (http://web.hku.hk/~h0014282/index.htm) 3. 黑 白 棋 世 界 (http://go7.163.com/~blacwet/index.html)