コンピュータ 囲 碁 に 起 きた 革 命 2008 年 3 月 末 パリ 囲 碁 トーナメントのエキシビショ ンでプロ 対 コンピュータの 対 戦 が 実 現 (http://paris2008.jeudego.org/) プロ:タラヌ カタリン 五 段 ( 日 本 棋 院 中 部 総 本 部 所

コンピュータ 囲 碁 における モンテカルロ 法 ~ 理 論 編 ~ 美 添 一 樹

コンピュータ 囲 碁 に 起 きた 革 命 2008 年 3 月 末 パリ 囲 碁 トーナメントのエキシビショ ンでプロ 対 コンピュータの 対 戦 が 実 現 (http://paris2008.jeudego.org/) プロ:タラヌ カタリン 五 段 ( 日 本 棋 院 中 部 総 本 部 所 属 ) コンピュータ:MoGo 9 路 盤 はハンデなしで3 局 対 戦 MoGoの1 勝 2 敗 19 路 盤 はMoGoが9 子 のハンデをもらい 1 局 対 戦 カタリン 五 段 の 勝 利 ここが 革 命 です 念 のため

コンピュータの 強 さ 囲 碁 だけが 弱 かった 主 な 二 人 零 和 完 全 情 報 ゲームの 中 で 囲 碁 だけが 他 と 比 較 し て 際 立 って 人 間 優 勢 だった コンピュータが 勝 利 したのは 正 式 に 用 いられる19 路 盤 ではなく コ ンピュータ 有 利 と 思 われる9 路 盤 だが 公 の 場 でプロにコンピュータが 勝 利 するというのは3 年 前 の 状 況 からは 想 像 できない 快 挙 である チェッカー オセロ チェス 将 棋 囲 碁 1994 年 に 世 界 チャンピオンに 勝 利 (2007 年 に 初 期 配 置 の 引 き 分 け 証 明 ) 1996 年 に 世 界 チャンピオンに 完 勝 1997 年 にIBMのDeepBlueが 当 時 世 界 チャンピオンのKasparovを 破 る アマトップレベルの 強 さと 言 われている アマ 初 段 をようやく 超 えた 程 度 主 なゲームにおける コンピュータの 強 さ

快 挙 の 原 動 力 は? 2006 年 に 登 場 した 画 期 的 なアルゴリズム 通 称 モンテカルロ 木 探 索 評 価 関 数 不 要 な 探 索 アルゴリズム どのようなアルゴリズムか? なぜ 囲 碁 に 有 効 なのか?

コンピュータプレイヤーの 進 歩 囲 碁 だけが 難 しかった つまり 他 のゲームで 有 効 だった 手 法 が 囲 碁 に は 通 用 しなかった なぜか? まず 他 のゲームのコンピュータプレイヤー のアルゴリズムについて 説 明 する

mini-max 探 索 +αβ 枝 刈 り 50 50 47 αカット βカットにより 探 索 が 省 略 される 候 補 手 が 理 想 的 な 順 番 にソー トされていれば 探 索 ノード 数 は 元 のツリーのノード 数 のほ ぼsqrtになる[Moore and Knuth 1975] 50 70 47 67 Max node 50 24 70 25 47 15 67 65 探 索 順 序 Min node

囲 碁 のルール 黒 白 交 互 に 交 点 に 石 を 置 いていく 19x19の 盤 が 普 通 最 終 的 に 地 が 大 きいほうが 勝 ち 地 とは 一 方 の 色 の 石 だけで 囲 われた 範 囲 のこ と

囲 碁 のルール : 囲 んだら 取 れる のところに 黒 が 打 つ と 白 石 を 取 れる 空 点 が 無 くなると 取 ら れる 空 点 のことを 呼 吸 点 ダメ などと 言 う つながっている 石 は 一 蓮 托 生 になっている 取 られるときはまとめて 取 られる つながっている 石 の 集 合 を 連 という

囲 碁 のルール : 着 手 禁 止 点 と 例 Aに 打 つと 反 則 そのまま 取 られる 場 所 には 打 てない Bには 打 って 良 い 打 った 瞬 間 に 黒 石 を 取 れるから 外

囲 碁 のルール : 同 型 反 復 禁 止 右 図 の 形 になったら 簡 単 に 無 限 反 復 が 生 じる 取 られてもすぐに 取 り 返 して はいけない 取 り 返 すと 反 則

生 き 死 に という 概 念 着 手 禁 止 点 が 二 つある 石 は 絶 対 に 取 られる 事 はない 絶 対 に 取 られない 石 を 生 きてい る と 言 う 着 手 禁 止 点 のことを 眼 と 言 う 二 眼 あると 生 き

実 戦 例 とある 商 用 ソフトと 私 が 打 った 例 これは 終 局 図 先 手 の 黒 が 有 利 なた め それを 是 正 するた めに 黒 にハンデを 負 わせるのが 普 通 それをコミという 19 路 盤 でも9 路 盤 でも 6.5 目 か7.5 目 が 普 通

囲 碁 の 難 しさ その1 探 索 空 間 が 大 きい 19 路 盤 囲 碁 は 探 索 空 間 が 巨 大 チェッカーは 初 期 局 面 が 引 き 分 けになることが 解 明 された(2007 年 ) 同 様 に 5 路 盤 の 囲 碁 は 最 善 手 順 が 完 全 解 明 されている チェッカー オセロ チェス 20 10 28 10 50 10 ところで 9 路 盤 の 探 索 空 間 はチェス 以 下 それでも2005 年 までは 弱 かった どっちもアマ 初 段 くらい おかしい だって 他 のゲームだと 性 質 の 似 たゲームなら 探 索 空 間 が 小 さい 方 が コンピュータ 有 利 将 棋 チェス 中 国 将 棋 などの 比 較 チェッカー(8 路 )とドラフト(10 路 )の 比 較 なぜ 19 路 盤 と9 路 盤 の 強 さに 差 が 無 いの? 将 棋 囲 碁 (9 路 盤 ) 囲 碁 (19 路 盤 ) 71 10 38 10 171 10 探 索 空 間 ( 可 能 な 局 面 数 )

この 数 値 はゲームのスコア 囲 碁 の 難 しさ その2 評 価 関 数 が 作 れない しかし 実 際 のスコアは 勝 敗 が つくまで 深 く 探 索 しなければ 分 からない 50 50 47 50 70 47 67 よって 探 索 を 途 中 で 打 ち 切 り その 時 点 でのスコアを 近 似 する 評 価 関 数 を 用 意 する 50 24 70 25 47 15 67 65 評 価 関 数 はどうやって 作 るもの?

オセロ 評 価 関 数 の 例 囲 碁 以 外 のゲーム 隅 や 辺 の 重 要 な 箇 所 のパターンを 学 習 して 評 価 関 数 を 作 成 チェスや 将 棋 駒 の 価 値 玉 の 安 全 度 駒 が 自 由 に 動 けるか 等 チェスの 例 :ポーン1 点 ビショップとナイト3 点 ルーク 5 点 クイーン9 点 キング 点 ボナンザメソッドなどもあり

囲 碁 の 評 価 関 数 の 難 しさ 石 の 価 値 は 平 等 駒 の 価 値 などは 用 いることができない 領 域 の 広 さを 競 うなら 広 さを 基 準 にする? 領 域 が 確 定 するのはゲームの 最 後 オセロのような 明 らかに 特 徴 のある 箇 所 が 少 ない 特 に19 路 盤 で 顕 著 局 所 的 な 最 善 手 が 全 局 的 な 最 善 手 になりにくい 石 を 取 るのは 局 所 的 には 得 捨 石 は 基 本 的 なテクニッ ク

人 間 はどうやってプレイしてるの? 説 明 不 能 です 特 に 中 盤 は 難 しいです 石 が 厚 かったり 薄 かったり 形 が 良 かったり 悪 かったり 味 が 良 かったり 悪 かったり 石 が 軽 かったり 重 かったり 初 段 くらい 無 いと 用 語 の 意 味 が 通 じません

つまり 囲 碁 は 難 しい チェスや 将 棋 の 駒 得 のような 明 らかな 評 価 基 準 がない 何 かの 要 素 の 足 し 算 で 局 面 の 優 劣 を 評 価 す るのは 難 しい 評 価 関 数 は 速 く 正 確 である 必 要 がある 囲 碁 の 評 価 関 数 は 遅 いか 不 正 確 である 両 方 という 説 も

従 来 の 囲 碁 プログラムの 例 GNU Go 商 用 ソフトの 中 身 は 分 からないので オープ ンソースの 囲 碁 プログラム GNU Goについて 説 明 GNU Goは 最 強 の 商 用 プログラムよりも 少 し 弱 い 多 数 の 複 雑 な 評 価 関 数 を 用 いている コードはCで 約 80,000 行 パターンデータベースがテキストで 約 52,000 行 棋 力 はアマ 初 段 より 少 し 弱 い 19 路 でも9 路 でも

GNU Goの 着 手 選 択 職 人 芸 の 結 晶 (?) 盤 面 の 状 況 を 分 析 する 連 絡 切 断 をある 程 度 調 査 それから 石 の 安 全 度 を 調 査 パターンデータベースにマッチする 手 を 発 見 し 評 価 値 を 割 当 てる 着 手 の 目 的 別 に 候 補 手 を 生 成 し 評 価 値 を 割 当 てる 目 的 : 自 分 の 石 を 守 る / 相 手 の 石 を 攻 める / 自 分 の 領 域 を 広 げる など 複 数 の 評 価 値 の 依 存 関 係 を 調 査 一 番 評 価 値 の 高 い 手 をプレイする

モンテカルロ 木 探 索 によるプログラム 囲 碁 の 評 価 関 数 は 難 しい これは 本 当 であ る しかし 囲 碁 でも 終 局 した 状 態 なら 簡 単 に 勝 敗 の 判 定 が 可 能 この 性 質 をうまく 利 用 したプログラムが2006 年 に 登 場 した CrazyStone

原 始 モンテカルロ 囲 碁 乱 数 を 用 いて 囲 碁 をプレイする [Brügmann][Bouzy][Cazenave] 囲 碁 は 終 盤 に 近 づくに 連 れて 合 法 手 が 減 少 する 合 法 手 の 中 からランダムに 選 んで 打 つだけのプ レイヤーでも 終 局 可 能 ただし 少 し 制 約 が 必 要 自 分 の 眼 には 打 たないようにする 二 つ 眼 を 持 つ 石 は 取 られない

プレイアウトとは 乱 数 を 用 いて 終 局 までプレイすることをプレ イアウトと 呼 ぶ

プレイアウトによる 局 面 評 価 要 するに たくさんプレイアウトを 行 って 勝 て そうな 手 を 選 ぶ

もちろん 原 始 モンテカルロは 弱 い 深 さが2 段 以 上 の 木 に 対 しては 最 善 手 を 返 す 保 証 は 無 い 相 手 がミスをしたら 得 だが 正 しく 応 じられると 損 をする 手 があるとする 正 解 の 手 が 少 なければプレイアウト 中 には 正 解 を 打 つ 確 率 は 低 い 相 手 がミスをすることに 期 待 して その 手 を 打 つ どれくらい 弱 いのか 調 べた 論 文 あり GNU Go 相 手 の 勝 率 は1 割 くらいでした H. Yoshimoto, K. Yoshizoe, T. Kaneko, A. Kishimoto and K. Taura, Monte Carlo Go Has a Way to Go, AAAI-06, pp 1070-1075

CrazyStone 2006 年 のComputer Olympiad 囲 碁 9 路 盤 部 門 優 勝 プログラム [Rémi Coulom 2006] 原 始 モンテカルロ 囲 碁 を 改 良 したアルゴリズムを 用 いた それがモンテカルロ 木 探 索

モンテカルロ 木 探 索 Monte Carlo Tree Search 変 更 点 は2つ 有 利 な 手 に 多 くのプレイアウ トを 割 当 てる プレイアウトの 回 数 が 閾 値 を 超 えたら 木 が 生 長 する さらに 以 下 の 工 夫 が 重 要 プレイアウトが 返 す 値 は ス コアでなく 勝 ち/ 負 け スコア 差 ではなく 勝 率 を 最 大 化 するようにプレイする リードしているときは 安 全 に 負 けている 時 は 無 理 な 手 も 勝 率 最 大 化 により 対 GNU Go 勝 率 が3 割 台 から6 割 以 上 に 跳 ね 上 がった

理 論 的 背 景 Multi-Armed Bandit 問 題 統 計 学 や 機 械 学 習 の 分 野 で 研 究 されてきた Multi-Armed Bandit とは? 腕 が 複 数 あるスロットマシンのこと( 空 想 上 の 存 在 ) One-Armed Bandit とはスロットマシンの 俗 称

Multi-Armed Bandit 問 題 与 えられた 枚 数 のコインで できるだけ 多 くの 報 酬 を 得 るための 戦 略 を 考 えよ

最 善 の 戦 略 は? Multi-Armed Bandit 問 題 の 最 善 の 戦 略 は 知 られている [Lai and Robbins 1985] しかし 計 算 量 メモリ 消 費 ともに 大 きいために 実 際 にはあまり 用 いられない 各 確 率 分 布 同 士 のKL 情 報 量 を 計 算 する 必 要 がある よって 計 算 量 が 小 さく かつ 性 能 もそれほど 悪 くない 戦 略 が 求 められる

全 部 に 同 じ 枚 数 を 投 入 しよう! そして 平 均 を 比 べればいい? 原 始 モンテカルロ 囲 碁 と 同 様 の 戦 略 つまり 全 然 ダメ

UCB1という 戦 略 各 マシンについてUCB1 値 という 値 (Upper Confidence Bound)を 計 算 [Auer, Cesa-Bianchi, Fischer 2002] UCB1 値 が 最 大 になるマシンにコインを 投 入 X j : j 番 目 のマシンの 報 酬 の 期 待 値 X j + c 2log n n j n :それまでに 投 入 したコイン 数 の 合 計 n j : j 番 目 のマシンに 投 入 したコインの 数 c : 期 待 値 の 値 域 によって 決 まる 定 数

有 望 なマシンにたくさんコインを 投 入 しよう! それがつまりUCB1 有 望 な 手 に 多 くの プレイアウトを 割 当 てる

UCT (UCB applied to Trees) CrazyStoneの 成 功 を 受 けて 提 案 された 木 探 索 アル ゴリズム [Kocsis and Szepesvári 2006] UCB1を 木 探 索 に 応 用 UCB1 値 の 高 い 候 補 手 を 辿 って 探 索 を 行 う 末 端 の 候 補 手 でプレイアウトの 回 数 が 閾 値 を 超 えると そ の 手 を 展 開 する 探 索 回 数 nが 大 きくなると UCB1 値 が 以 下 のように 期 待 値 に 収 束 することが 証 明 されている X j 2log n æ log n ö + c X + ç n j O è n ø j

UCTを 使 えば 深 さ2 以 上 の 木 でも 最 善 手 に 到 達 する! 最 初 にUCTを 取 り 入 れた 囲 碁 プログラムが MoGo ( 冒 頭 でプロと 対 戦 ) [Gelly et al. 2006]

その 後 の 進 歩 MoGoがUCTを 採 用 して 猛 威 を 奮 って 以 降 CrazyStoneを 含 め 多 くのプログラムがUCTを 採 用 Computer Olympiad 電 通 大 で 開 催 されたUEC 杯 コンピュータ 囲 碁 大 会 などでモンテカルロ 木 探 索 を 用 いたプログラムが 上 位 を 独 占 全 て UCTか 又 は 同 様 に 木 が 成 長 するモンテカルロ 木 探 索 を 用 いて いる 19 路 盤 でも 強 くなった 当 初 は9 路 盤 はアマ3 級 程 度 19 路 盤 では 非 常 に 弱 かった 現 在 では19 路 盤 でもアマ 有 段 者 並 み(CrazyStoneはKGSという 囲 碁 サイトで2 級 = 普 通 の 碁 会 所 なら 二 段?) 何 が 改 良 されたのか 説 明 したい

探 索 部 分 の 改 良 Progressive Widening 囲 碁 の 知 識 を 用 い 良 さそうな 手 から 順 に 候 補 手 をソート しておく それを 徐 々に 探 索 木 に 加 えていく AMAF (All Moves As First) プレイアウト 中 に 打 たれた 初 手 のみを 用 いるのが 通 常 の 考 え 方 だが AMAFでは 全 ての 手 を 初 手 に 打 ったとみな す UCTのパラメータの 調 整 UCTよりも 最 善 手 を 優 遇 する 探 索 手 法

プレイアウトの 改 良 初 期 のCrazyStoneのプレイアウトは 単 純 19 路 盤 では 非 常 に 弱 かった パターンを 用 いてプレイアウトを 改 良 速 度 は 数 分 の1になったが 棋 力 は 大 幅 に 向 上 初 期 のCrazyStone ( 秒 間 4 万 回 程 度?) 強 化 版 CrazyStone ( 秒 間 1 万 回 程 度?)

なぜ 囲 碁 に 有 効 なの? プレイアウトで 普 通 に 終 局 するゲームだから チェスや 将 棋 では 普 通 に 終 局 を 迎 えるのは 難 しい 現 在 プレイアウトと 探 索 を 組 み 合 わせる 研 究 などが 行 われてい る オセロや 五 目 並 べは 終 局 に 至 る 囲 碁 同 様 に 有 効 であると 思 われるがまだ 研 究 途 上 囲 碁 では 最 善 手 と 次 善 手 の 価 値 の 差 が 小 さい(ことが 多 い) 手 順 に 関 係 なくある 位 置 を 占 めておけば 有 利 という 点 が 多 い

モンテカルロ 木 探 索 の 弱 点 細 く 長 い 正 解 手 順 がある 場 合 最 善 手 が1 手 だけある という 局 面 が 長 手 順 連 続 すると 確 率 的 に 正 解 にたどり 着 かない 例 シチョウ : プレイアウトをパターンで 強 化 して 回 避 死 活 攻 め 合 い : まだ 対 処 法 は 不 明 山 下 さんは 探 索 との 組 合 せなどを 試 しているらしい

今 後 の 展 望 モンテカルロ 木 探 索 の 利 点 単 純 に 強 い プログラミングの 労 力 が 少 ない 探 索 部 分 とプレイアウトの 実 装 だけ プレイアウトの 強 化 には 機 械 学 習 も 有 効 多 くの 研 究 者 が 参 入 機 械 学 習 のプロなど 並 列 化 の 研 究 も 行 われている 冒 頭 のMoGoは256コアのクラスタを 用 いていた 現 在 も 日 々 強 化 されている 今 後 が 非 常 に 楽 しみです

参 考 文 献 P. Auer, N. Cesa-Bianchi and P. Fischer, Finite-time analysis of the multi-armed bandit problem, Machine Learning, vol. 47, pp 235-256, 2002. R. Coulom, Computing Elo Ratings of Move Patterns in the Game of Go, Computer Games Workshop, 2007. S. Gelly, Y. Wang, R. Munos and O. Teytaud, Modification of UCT with patterns in Monte-Carlo Go, Technical Report No.6062, INRIA, 2006. L. Kocsis and C. Szepesvári, Bandit Based Monte-Carlo Planning, LNCS vol.4212 (ECML 2006), pp. 282-293, 2006. T. L. Lai and H. Robbins, Asymptotically efficient adaptive allocation rules, Advances in Applied Mathematics, vol. 6, pp. 4-22, 1985. H. Yoshimoto, K. Yoshizoe, T. Kaneko, A. Kishimoto and K. Taura, Monte Carlo Go Has a Way to Go, AAAI-06, pp. 1070-1075, 2006.