将棋ソフトウェアにおける棋譜データの利用と機械学習

Transcription

1 2013/12/16-18 NINSコロキウム 分 科 会 1 将 棋 ソフトウェアにおける 棋 譜 データの 利 用 と 機 械 学 習 佐 藤 佳 州 筑 波 大 学 システム 情 報 工 学 研 究 科 パナソニック 株 式 会 社 先 端 技 術 研 究 所

2 2013/12/16-18 NINSコロキウム 分 科 会 2 目 次 コンピュータ 将 棋 の 現 状 とこれまでの 歴 史 ゲームの 基 本 的 なアルゴリズム 将 棋 における 棋 譜 を 利 用 した 知 識 獲 得 今 後 の 研 究 動 向 まとめ

3 2013/12/16-18 NINSコロキウム 分 科 会 3 目 次 コンピュータ 将 棋 の 現 状 とこれまでの 歴 史 ゲームの 基 本 的 なアルゴリズム 将 棋 における 棋 譜 を 利 用 した 知 識 獲 得 今 後 の 研 究 動 向 まとめ

4 2013/12/16-18 NINSコロキウム 分 科 会 4 コンピュータ 将 棋 とは 人 間 の 指 示 なしに,コンピュータ 自 身 が 考 え, 指 し 手 を 返 すプログラム 様 々な 将 棋 ソフトが 存 在 Bonanza,GPS 将 棋, 激 指,YSS(AI 将 棋 ),Ponanza, 年 に1 回, 世 界 一 のプログラムを 決 定 するための, 世 界 コンピュータ 将 棋 選 手 権 が 開 催 されている 今 年 はBonanzaが 優 勝 ハードウェア 制 限 なし (GPS 将 棋 : 東 大 の 教 育 用 計 算 機 で 参 加 :3000コア 以 上 ) 学 問 的 には, 人 工 知 能 の 一 分 野

5 2013/12/16-18 NINSコロキウム 分 科 会 5 電 王 戦 コンピュータ 将 棋 が 一 躍 注 目 を 集 めたイベント 第 一 回 (2012 年 ) 米 長 永 世 棋 聖 にコンピュータが 勝 利 かつての 名 人 を 破 る 第 二 回 (2013 年 ) 現 役 プロとの 対 局 において,コンピュータが3 勝 1 敗 1 分 初 めて 現 役 のプロに 勝 利 たった10 人 しかいない A 級 棋 士 に 勝 利

6 2013/12/16-18 NINSコロキウム 分 科 会 6 コンピュータ 将 棋 の 歴 史 ( 現 在 ) 強 さ ルール 通 りに 指 す アマチュア 低 級 者 アマチュア 高 段 者 プロ 中 級 初 めての プログラム 手 作 業 による 評 価 関 数 選 択 探 索 技 術 動 向 詰 将 棋 アルゴリズム 実 現 確 率 探 索 枝 狩 り 手 法 の 充 実 評 価 関 数 の 機 械 学 習 並 列 探 索 クラスタ 探 索 (チェス)Deep Blueが 人 間 のチャンピョンを 破 る 合 議 2000 年 代 後 半 から 急 速 に 強 くなる 機 械 学 習 の 成 功 + 並 列 探 索 の 導 入

7 2013/12/16-18 NINSコロキウム 分 科 会 7 目 次 コンピュータ 将 棋 の 現 状 とこれまでの 歴 史 ゲームの 基 本 的 なアルゴリズム 将 棋 における 棋 譜 を 利 用 した 知 識 獲 得 今 後 の 研 究 動 向 まとめ

8 2013/12/16-18 NINSコロキウム 分 科 会 8 ゲームの 基 本 的 なアルゴリズム 人 間 は, 読 み と 大 局 観 で 指 し 手 を 決 定 コンピュータの 場 合,それぞれ 探 索 と 評 価 関 数 で 実 現

9 2013/12/16-18 NINSコロキウム 分 科 会 9 ゲームの 基 本 的 なアルゴリズム 人 間 は, 読 み と 大 局 観 で 指 し 手 を 決 定 コンピュータの 場 合,それぞれ 探 索 と 評 価 関 数 で 実 現 考 えられる 手 を 7 六 歩 2 六 歩 すべて 展 開 していく ( 図 では 省 略 ) 探 索 深 さ = 1

10 2013/12/16-18 NINSコロキウム 分 科 会 10 ゲームの 基 本 的 なアルゴリズム 人 間 は, 読 み と 大 局 観 で 指 し 手 を 決 定 コンピュータの 場 合,それぞれ 探 索 と 評 価 関 数 で 実 現 考 えられる 手 を すべて 展 開 していく ( 図 では 省 略 ) 7 六 歩 2 六 歩 3 四 歩 2 六 歩 3 四 歩 5 二 玉 探 索 深 さ = 2

11 2013/12/16-18 NINSコロキウム 分 科 会 11 ゲームの 基 本 的 なアルゴリズム 人 間 は, 読 み と 大 局 観 で 指 し 手 を 決 定 コンピュータの 場 合,それぞれ 探 索 と 評 価 関 数 で 実 現 考 えられる 手 を すべて 展 開 していく ( 図 では 省 略 ) 7 六 歩 2 六 歩 3 四 歩 2 六 歩 3 四 歩 5 二 玉 2 六 歩 1 八 香 7 七 角 76 歩 9 八 香 5 八 玉 探 索 深 さ = 3

12 2013/12/16-18 NINSコロキウム 分 科 会 12 ゲームの 基 本 的 なアルゴリズム 人 間 は, 読 み と 大 局 観 で 指 し 手 を 決 定 コンピュータの 場 合,それぞれ 探 索 と 評 価 関 数 で 実 現 7 六 歩 2 六 歩 3 四 歩 2 六 歩 3 四 歩 5 二 玉 2 六 歩 1 八 香 7 七 角 76 歩 9 八 香 5 八 玉 探 索 深 さ = 3 終 局 までは 探 索 できないため,ある 程 度 の 深 さで 探 索 を 打 ち 切 る

13 2013/12/16-18 NINSコロキウム 分 科 会 13 ゲームの 基 本 的 なアルゴリズム 人 間 は, 読 み と 大 局 観 で 指 し 手 を 決 定 コンピュータの 場 合,それぞれ 探 索 と 評 価 関 数 で 実 現 7 六 歩 2 六 歩 3 四 歩 2 六 歩 3 四 歩 5 二 玉 2 六 歩 1 八 香 7 七 角 76 歩 9 八 香 5 八 玉 探 索 深 さ = 3 末 端 局 面 の 優 劣 を 評 価 関 数 で 数 値 化

14 2013/12/16-18 NINSコロキウム 分 科 会 14 ゲームの 基 本 的 なアルゴリズム 人 間 は, 読 み と 大 局 観 で 指 し 手 を 決 定 コンピュータの 場 合,それぞれ 探 索 と 評 価 関 数 で 実 現 最 善 手 7 六 歩 +3 2 六 歩 四 歩 2 六 歩 3 四 歩 5 二 玉 六 歩 1 八 香 76 歩 5 八 玉 7 七 角 9 八 香 自 分 の 手 番 では, 評 価 値 が 最 大 になるノードを, 相 手 の 手 番 では, 評 価 値 が 最 小 となる( 相 手 に 取 って 最 大 になる) ノードを, 選 択 する

15 2013/12/16-18 NINSコロキウム 分 科 会 15 ゲーム 木 探 索 の 難 しさ( 研 究 内 容 ) 探 索 : よさそうな 手 を 深 く 探 索 したい ( 無 駄 な 手 は 探 索 したくない) 評 価 関 数 : 局 面 の 優 劣 を 正 確 に 数 値 化 することは 困 難 棋 譜 を 利 用 した 機 械 学 習 ( 今 回 は 評 価 関 数 に 焦 点 )

16 2013/12/16-18 NINSコロキウム 分 科 会 16 評 価 関 数 とは(1) 局 面 の 優 劣 を 数 値 化 する 関 数 評 価 関 数 評 価 値 -45 ( 互 角 )

17 2013/12/16-18 NINSコロキウム 分 科 会 17 評 価 関 数 とは(2) 評 価 関 数 の 例 従 来 は 数 千 以 上 のパラメータ を 手 作 業 で 調 整 人 間 の 知 識 を 正 確 に 数 値 に 落 としこむのは 困 難 機 械 学 習 が 成 功 [ 保 木 2006] 将 棋 プログラムの 飛 躍 的 な 性 能 向 上 に 繋 がる

18 2013/12/16-18 NINSコロキウム 分 科 会 18 目 次 コンピュータ 将 棋 の 現 状 とこれまでの 歴 史 ゲームの 基 本 的 なアルゴリズム 将 棋 における 棋 譜 を 利 用 した 機 械 学 習 今 後 の 研 究 動 向 まとめ

19 2013/12/16-18 NINSコロキウム 分 科 会 19 棋 譜 を 用 いた 評 価 関 数 の 学 習 機 械 学 習 ( 教 師 あり 学 習 )とは : 教 師 データ( 棋 譜 )を 用 いて,パラメータを 自 動 調 整 する エキスパートの 棋 譜 各 パラメータを 自 動 で 決 定 将 棋 における 評 価 関 数 の 学 習 棋 譜 と 同 じ 手 を 選 択 できるようにパラメータを 学 習 する( 人 間 の 真 似 を 目 指 す) 以 降, 具 体 的 な 学 習 手 法 の 概 要 を 説 明

20 2013/12/16-18 NINSコロキウム 分 科 会 20 Comparison Training [Tesauro 2001] 評 価 関 数 学 習 の 最 も 一 般 的 な 学 習 手 法 棋 譜 中 のエキスパートの 指 し 手 とその 他 の 合 法 手 を 比 較 教 師 局 面 棋 譜 中 の 指 し 手 その 他 の 合 法 手 αβ 探 索 末 端 局 面 ( 評 価 局 面 ) エキスパートの 指 し 手 の 評 価 が,その 他 の 合 法 手 の 評 価 を 十 分 に 上 回 るよう に 評 価 関 数 を 学 習

21 2013/12/16-18 NINSコロキウム 分 科 会 21 Comparison Training [Tesauro 2001] 目 的 関 数 Alpha-beta search Leaf positions Experts move J 1 (P, v) = Training position Other M legal moves p p P m=2 その 他 の 合 法 手 の 評 価 値 T ξ p m, v ξ p 1, v P : 学 習 局 面 の 集 合 M p : 局 面 p における 合 法 手 の 数 p m : 局 面 p において 指 し 手 m を 選 択 した 時 の 局 面 (m = 1: 棋 譜 中 の 指 し 手 ) ξ p m, v : p m において,αβ 探 索 を 行 った 時 の 結 果 ( 評 価 値 ) v : 評 価 局 面 の 特 徴 T(x) : シグモイド 関 数 棋 譜 中 の 指 し 手 の 評 価 値 チェスでも 一 部 同 様 の 手 法 が 取 り 入 れられる(Deep Blue) 将 棋 への 応 用 [ 保 木 2006]で 大 きな 効 果

22 2013/12/16-18 NINSコロキウム 分 科 会 22 学 習 データの 規 模 将 棋 の 評 価 関 数 に 用 いられている 学 習 データの 規 模 見 た 目 以 上 にずっと 大 きい 数 万 局 の 棋 譜 から 学 習 1 棋 譜 に 百 局 面 程 度 含 まれる 一 般 的 な 認 識 それってビッグデータなの? 実 際 には 数 百 万 局 面 から 学 習 1 局 面 に 数 百 手 含 まれる 数 億 手 から 学 習 実 際 には 膨 大 なデータを 処 理 手 作 業 では 不 可 能 だった, 数 十 万 以 上 のパラメータ 調 整 が 可 能 に 計 算 機 の 性 能 向 上 が, 機 械 学 習 成 功 の 大 きな 後 押 し

23 2013/12/16-18 NINSコロキウム 分 科 会 23 目 次 コンピュータ 将 棋 の 現 状 とこれまでの 歴 史 ゲームの 基 本 的 なアルゴリズム 将 棋 における 棋 譜 を 利 用 した 知 識 獲 得 今 後 の 研 究 動 向 まとめ

24 2013/12/16-18 NINSコロキウム 分 科 会 24 現 在 の 評 価 関 数 の 性 能 評 価 関 数 の 性 能 = 局 面 の 優 劣 を 正 しく 判 断 する 能 力 理 想 的 な 評 価 関 数 があれば, 探 索 は 不 要 ( 極 論 ) 参 考 Floodgate ( 東 大 : コンピュータ 同 士 を 自 動 対 局 させ,レーティングを 出 すサーバー プログラム レーティング 本 番 用 約 3000~ gps_l ( 学 習 / 古 いマシン) 2523 gps_normal ( 手 調 整 / 古 いマシン) 2150 gps500 (ほとんど 探 索 しない) 1583 学 習 による 強 さの 向 上 も 大 きいものの, 実 際 には 探 索 による 強 さの 向 上 はレーテ ィング 的 にはそれ 以 上 現 在 の 将 棋 プログラムの 強 さ = 評 価 関 数 ( 以 前 より 人 間 に 近 づく) + 探 索 ( 人 間 を 凌 駕 ) まだ 改 良 の 余 地 は 大 きい

25 2013/12/16-18 NINSコロキウム 分 科 会 25 今 後 の 研 究 動 向 (+ 自 分 の 研 究 ) 将 棋 の 場 合, 近 いうちに 人 間 のプレイヤに 勝 つことは 確 実 ただし, 評 価 関 数 については, 人 間 の 評 価 能 力 ( 大 局 観, 表 現 力 )を 獲 得 したというわけではなく,さらなる 研 究 の 余 地 は 大 きい 今 後 の 研 究 課 題 ( 例 ) 特 徴 学 習 (Feature Learning,Representation Learning) データから,どのような 特 徴 を 評 価 するかという 特 徴 自 体 を 学 習 ( 参 考 )Deep Learning 強 いプログラムを 学 習 するための 目 的 関 数 の 学 習 どのような 学 習 棋 譜 が 強 いプログラムを 生 み 出 すか? 同 じ 学 習 棋 譜 でも, 学 習 方 法 が 異 なれば, 得 られる 知 識 は 全 く 異 なる

26 2013/12/16-18 NINSコロキウム 分 科 会 26 目 的 関 数 の 学 習 [Sato et al. 2013] 単 純 なComparison Trainingが 学 習 してくれることはそれほど 多 くない = プロの 棋 譜 ( 指 し 手 )との 全 体 的 な 一 致 率 の 向 上 のみ 課 題 J 1 (P, v) = M p p P m=2 T ξ p m, v ξ p 1, v 勝 敗 に 直 結 する 局 面 で 最 善 手 を 指 したい 評 価 値 の 差 の 制 御 が 考 慮 されていない 手 法 学 習 局 面 の 性 質 に 応 じて, 一 致 の 重 要 度, 正 解 手 と 不 正 解 手 の 評 価 値 の 差 を 制 御 するパラメータ 等 を 目 的 関 数 に 導 入 導 入 されたパラメータは, 学 習 されたプログラムの 強 さを 適 応 度 とした 進 化 的 計 算 で 学 習 強 くなるように 棋 譜 を 真 似 する 目 的 関 数 を 学 習 従 来 手 法 と 比 較 して,6 割 程 度 の 勝 率 を 得 る

27 2013/12/16-18 NINSコロキウム 分 科 会 27 どのような 学 習 棋 譜 が 有 用 か?( 戦 術 ) 順 位 戦 術 重 要 度 の 平 均 1 四 間 飛 車 穴 熊 - 銀 冠 居 飛 穴 模 様 - 藤 井 システム 森 下 システム - 9 五 歩 8 四 歩 型 七 銀 3 七 桂 - 金 矢 倉 相 掛 かり 2 六 飛 - 5 四 歩 型 居 飛 車 穴 熊 - 本 美 濃 矢 倉 - 引 き 角 左 美 濃 - 高 美 濃 角 交 換 型 - ゴキゲン 中 飛 車 相 腰 掛 け 銀 - 6 五 歩 型 穴 熊, 銀 冠, 矢 倉 など 囲 いを 発 展 させる 戦 術 が 上 位 に

28 2013/12/16-18 NINSコロキウム 分 科 会 28 実 際 の 対 局 における 戦 術 選 択 の 比 較 提 案 手 法 と 従 来 手 法 の 対 局 実 験 において,それぞれのプログ ラムが 選 択 した 戦 術 を 比 較 戦 術 各 戦 術 の 選 択 回 数 従 来 手 法 提 案 手 法 本 美 濃 高 美 濃 銀 冠 流 れ 矢 倉 金 矢 倉 居 飛 車 穴 熊 四 間 飛 車 穴 熊 三 間 飛 車 穴 熊 提 案 手 法 勝 率 提 案 手 法 では, 囲 いを 発 展 させる 戦 術 や 固 い 囲 いが 選 択 されやすく なっている 重 要 度 を 導 入 すること により,コンピュータに とって 勝 ちやすい 戦 術 の 選 択 を 実 現 28

29 2013/12/16-18 NINSコロキウム 分 科 会 29 目 次 ゲーム 研 究 の 流 れとコンピュータ 将 棋 の 現 状 ゲームの 基 本 的 なアルゴリズム 将 棋 における 棋 譜 を 利 用 した 知 識 獲 得 今 後 の 研 究 動 向 まとめ

30 2013/12/16-18 NINSコロキウム 分 科 会 30 まとめ(1) 棋 譜 を 用 いた 評 価 関 数 の 機 械 学 習 棋 譜 を 教 師 とした 機 械 学 習 の 成 功 により,コンピュー タ 将 棋 は, 人 間 のトッププレイヤに 迫 る 強 さを 得 る ほぼ 確 実 に, 数 年 以 内 に 人 間 を 上 回 る ただし, 評 価 関 数 は 人 間 の 大 局 観 以 上 のものが 得 ら れているとはいえず, 今 後 も 改 良 の 余 地 は 大 きい 同 じ 学 習 データを 用 いても,その 活 用 方 法 ( 学 習 方 法 )によって 得 られる 知 識 は 全 く 異 なる さらなる 機 械 学 習 技 術 の 研 究 が 重 要

31 2013/12/16-18 NINSコロキウム 分 科 会 31 まとめ(2) ビッグデータ 研 究 としての 意 義 将 棋, 囲 碁 等 のゲームでは 数 万 局 (その 背 後 に 隠 れている 数 億 手 の 教 師 データ)を 容 易 に 入 手 可 能 個 人 情 報, 著 作 権 等 が 絡 まないオープンなデータ ビッグデータに 基 づく 機 械 学 習 の 基 礎 研 究 対 象 とし て,ゲームは 今 後 も 果 たすべき 役 割 は 大 きい

32 2013/12/16-18 NINSコロキウム 分 科 会 32