The 28th Annual Conference of the Japanese Society for Artificial Intelligence, 2014
- 1 -
抽象的
木探索
対
因果的価値関数
有効性
Effectiveness of Causal Value Function for Game Tree Search
大用
庫智
*
１
川
翔
郎
*
2
高橋
遉
*
2
Kuratomo Oyo Shoutarou Ogawa Tatsuji Takahashi
*1
東京電機大学大学院
*2
東京電機大学
Graduate School of Tokyo Denki University Tokyo Denki University
Classical search methods on game trees are based on an evaluation function that enables quantitative treatment of the state and a strategy that utilizes the function such as Mini-Max method. Construction of the evaluation can be quite hard, especially for a game with huge search space like the game of Go. Recently, UCT, a Monte Carlo tree search method with bandit-like sampling allocation, has been shown to be very effective. We propose LST that utilizes an action value function implementing causal intuition of human. With tuning of an intuitive parameter, it enables faster search of the optimal actions with a kind of satisficing behavior.
1.
はじめ
1950 前 碁 将棋等 人ゼ 和確定情
報 研究 人間 強い AI 作 一
目標 研究 進 [人工知能学会 08] 研究
当 初 有 益 探 索 方 法 研 究 あ 現 在 効 率 的
探索方法 強い AI 作 要 要因 い
1990 代 2014 現在 ッ バ
将棋等 AI 人間 プ 遥 強 い
AI 研究 商業的 有益 あ ッ 善
手 引 [Schaeffer 07] Science 掲載さ
い 学問的 要 研究 あ
AI 着手 探索法 局面 点数
評 価 関 数 評 価 活 戦 略 Mini-Max 法 基
本 い 人 工 知 能 研 究 歴 史 中
功 収 探索法 碁 AI 全 役
立 碁 比 較 評 価 関
数 作 困 あ 探 索 空 間 膨 大 あ 主
要 因 あ 汎 用 的 効 率 的 探 索 方 法
場 望 い
問 題 点 解 決 [Bruegmann 93] ン
着 手 初 期 局 面 ノ 子 ノ 終 局
繰 返 ンプ ン 行う原始 ン 法 提案
方法 評価関数 必要 終局 勝 1 負
0 情 報 計 算 さ 価値 実 際 着 手 行 動 価 値
い 当初 終局 差 得点差等 用い い
勝率 追求 方 遥 強い AI 知
い [美添 2012]
方 法 ン プ ン 無 駄 多 強 い 碁
AI 作 困 あ 方 法 木 探 索 ン
ンプ ン 工 バン ッ 問題
組 合 わ ン 木 探 索 場 特 着 手 行 動
価 値 関 数 部 バ ン ッ 問 題 標 準 的 あ
UCB 組 合わ 方法 UCT (UCB applied to trees)
[Kocsis 06] 呼 い 40 以 進展
碁 研究 UCT 劇的 進展 [美添 2012]
UCT 着手 行動価値関数 UCB 要 あ
本 研 究 UCT 代 案 LST (loosely symmetric
model applied to trees) 提案 本研究 UCT
行動価値関数部 人間 因果的直感 正確 記述
価値関数 緩い対称性 LS 用い あ 本研究
碁や将棋 等 固有 知識 利用 い
抽 象 的 木 用 い 木 利 用 [Kocsis 06]
行 わ 様 ョ ン 通 適 解 収 束 速 さ
振 舞い 方 両方 観点 LST UCT 比較
2.
抽象的
ゲーマ木
Kocsis Szepesv 抽象的 木[Smith 94] 利用
UCT 善手 収束 理論 ョン 観点
示 [Kocsis 06] 本研究 [Kocsis 06] 同様 1 う
木 用い 木 MAX MIN 人
プ 交 互 進 MAX 自 身
有望 着手 選択 逆 MIN MAX
利 選択 う 戦略 Mini-Max法 あ
終局 意味 葉ノ 終局 評価値 一定
範 一定 確率 え 評価値 一定 基準
高 MAX 勝利 1 赤い部 基準
以 あ MAX 敗 1 青い部
人 プ 着 手 行 動 価 値 葉 ノ 到 遉
得 勝 1 負 0 情 報 計 算 さ
現 在 局 面 直 接 子 ノ 行 動 価 値 高 い 方 選
択 葉 ノ 交 互 着 手 繰 返 注 意 点 人
プ Mini-Max 値 行動価値 出来 い
行 動 勝 負 情 報 ン プ ン 本 来 ン
終 局 着 手 繰 返 プ 呼 ぶ
本研究 記 ンプ ン プ 呼ぶ プ
実際 着手選択 UCT バン ッ 問
連 絡先 ：大 用 庫 智、e ai: rao ooyo[a]g ai co
2N5-OS-03b-3
図 1:深 さが2 子 ノー ド数 が 2 ゲー ム木 . 赤 青 点 線 MAX プ レ イ ヤ ー 勝 ち 負 け を 意 味 し い
The 28th Annual Conference of the Japanese Society for Artificial Intelligence, 2014
- 2 -
題 利用さ
2.1 バンヅァッテ問題 逐次的意思決定
バ ン ッ 問 題 当 確 率 明 複 数
腕 持 一 ッ ン 一 度 一 腕 選 択
続 目 的 累 積 獲 得 報 酬 大 あ 問 題
探 索 知 識 利 用 ン 速 さ 正 確 さ
表 現 強 学 習 基 本 的 問 題 見 さ い
[Sutton 98] 探索 良い結果 得 即時 結
果 結 び 限 い 情 報 収 集 あ 知 識 利 用
得 情報 局所的 適 主観的 ベ 選択
肢 選 ぶ 報 酬 獲 得 あ バ ン ッ 問 題 強 学 習
問題 比較 単純 あ 探索 知識利用 ッ
ン バ ン ン 行う 研究 盛 行わ
い [e.g. Auer 02] バン ッ 問題 専門用語 あ 腕
木 い 着 手 子 ノ 対 応 ン 有 無 勝
負 対応 勝 負 1 0 対応付
探 索 知 識 利 用 バ ン 取
碁 AI 研究 劇的 進展 遂
(1) UCB (upper confidence bound) ゠ラゴヨズマ
バ ン ッ 問 題 現 在 標 準 的 UCB1
あ [Auer 02] 価 値 関 数 い
十 選 択 回 数 許 さ 高 い 績 示 期 待 損 失
界 保 証 即 適 解 収 束 保 証 い UCB1
初 全 子ノ 選択 い
価値関数UCB1 � 値 高い子ノ 選択
UCB1� =�!+ 2ln�/�!
,
(1).�! 子ノ � 期待値 条件付 確率 P(1|j) 一
あ �! 子 ノ � 選 択 回 数 � � 限 各 深 さ
到遉 選択回数 意味 UCB MoGo 等
碁AI ン 木探索 応用さ い [Gelly 06]
(2) 因果的価値関数 緩い対称性モヅラ
知心理学や行動経済学 確率規則や論理法則
規範 逸脱 知バ 研究 行わ 々人間 ヒ
来 考 え 知 バ 強
持 知 [e.g., Tversky 81] 本 研 究 着 手 行 動 価 値 関 数 人 間 因 果 的 直 感 再 現 緩 い 対 称
性 loosely symmetric：LS 呼 条件付 確率的
関数 注目 LS 篠原 知バ 特 幼児
語 彙 獲 得 必 要 さ い 対 称 性 相 互 排 性 バ
定 的 扱 う 経 験 的 見 さ [篠 原
07] LS [Takahashi10, Takahashi 11a, 11b] 析さ
い LS 条 件 付 確 率 含 い い 特
(�!= ��/(�+�) and �!= ��/(�+�)) 用 い 知 バ
調整
�� 1� =
�+ �!
�+ �+�!+�!=
�(�,1)+ �!′
�(�)+�!′+�!′ , (2).
�� 1� =
�+ �!
�+ �+�!+�!=
�(�,1)+ �!′
�(�)+�!′+�!′ , (3). �!! =�
!/(�+�+�+�) �!! =�!/(�+�+�+�) あ
� � 1 様 子ノ A B 対応 共変動情報
� 1 � 共 生 頻度 意味 �(�,1) あ 同様
�,�,� �(�,0) �(�,1), �(�,0) 意味
原 因 結 果 共 変 動 情 報 �,�,�,� 帰 納
的 因 果 関 推 論 因 果 帰 納 実 験 析 い
人 間 因 果 的 直 感 高 い 相 関 関 �=0.96 持 示 さ い [Oyo 13] 因 果 関 学 習 結 果 意 思 決
定 一貫 い 調査 実験 い LS 高い相関
関 �=0.98 持 示さ 因果帰納 意
思 決 定 課 題 使 う 正 当 性 示 さ い [大 用 14]
因 果 的 価 値 行 動 価 値 関 数 バ ン ッ 問 題 用 い
従来 方法 �-greedy法やSoftmax法 UCB 高 績 示 い [Oyo 13, 14, 大用 14]
々人間 持 一定 基準 満足 選択肢 探
満足 原理[Simon 56] や振 舞い 心理的 決
定 参 照 点[Tversky 81] 複 数 選 択 肢 付 容
易 相 対 評 価[Kahneman 79] ヒ
人間的特性 実装 い [大用 14] 満足 基準� 持
LS 計算 �, � 対 2(1−�) 乗算 �,� 対 2�
乗算 良い 基準 0.5 あ LS 満
足 基準 従い振 舞い 変 [大用 14]
ン 木 探 索 LS 実 装 方 法 容 易 あ
UCT 行動価値UCB1 � LS 置 換え UCB1 初期方
策 削 あ UCT 疑似 [Kocsis 06] 参照 LS 計算 共通 含 見 目 簡単 あ
3.
シポュリーション
[Kocsis 06] 同様 設定 用い 適解収束 速
さ 振 舞い 方 観点 LST UCT 比較
3.1 設定と指標
抽 象 的 木 深 さ 一 親 ノ 持 子 ノ
数 20 2 終局 意味 葉ノ
確率�
! 設定さ い 葉ノ 確率�
! [128, 254] 1−�! [0, 127] 評 価 値 割 振 終 局
評価値 128 以 あ MAX 勝敗 勝利 1
様 子ノ A以降 葉ノ �
! 子ノ B以降 葉
ノ �
! 確 率 設 定 さ い 即 �
! 高
MAX 有利 局面 意味 設定 従い 100 種
類 木 生 木 対 1000 プ
100回実行 均 結果
指標 正解率 え率 用い 正解率
Mini-max 的 適 ノ 選択 割合 あ 体例 1
参 照 え 率 前 回 選 択 選 択 肢 変 え 割 合 あ
指標 各プ 回数 計算さ
初期設定 UCB1 先頭打着緊急度[Gelly 06] 考
え方 用い UCB1 初期方策 実現 LS 共変動情報
初期値 1 代入さ い 設定 LS UCB1
方法 比較 相対的 利 設定 あ
LS 性能 示 本論文 設定 あ [Oyo 13]
3.2 結果1
高 確 率 環 境 単 高 確 率 環 境 確 率 環 境 種 類
確率設定毎 結果 示 高確率環境 �
! �! 0.8 0.6
単高確率環境 �
! �! 0.6 0.4 確率環境 �
! �!
0.4 0.2 高確率環境 MAX 常 勝利
う 有 利 局 面 想 定 設 定 あ 確 率 環 境
常 敗 う う 利 局 面 想 定 設 定 あ
単 高 確 率 環 境 一 選 択 肢 唯 一 勝 利 能 局 面
想 定 設 定 あ 確 率 設 定 LS 基 準 あ
0.5 基準 い
記 様 環境毎 LS UCB1 結果 2 示 2
結 果 UCB1 環 境 毎 殆 え 率 変 え 正 解
率 殆 同 あ 一 方 LS 環 境 毎 え 率 変 さ
The 28th Annual Conference of the Japanese Society for Artificial Intelligence, 2014
- 3 -
確 率 環 境 え 率 極 端 高 い う 特 徴
あ LS 正解率 高確率環境 UCB1 劣 単
高確率 確率環境 UCB1 高い
LS UCB1 探索方法 差異 あ 差異 焦点
あ 同一 Mini-Max値 持 木 用い 両者 視覚的
比較 木 深さ3 子ノ 数2 あ 訪問回数毎 ノ
内 色 白 赤へ 濃淡 設定 プ 1000
回 差異 例 3 示 2同様 3 UCB1
振 舞 い 変 あ 見 い 2 結 果 踏 え
3 LS 満足 基準 従い探索 空間 広さ 調整
い 視覚的 LS 基準 良い局面 高確率
単 高 確 率 瞬 時 勝 利 着 手 執 着 同 様
LS 基 準 い局 面 活 路 基 準 良 い局 面
探 続 い
3.3 結果2
2 3 LS UCB1 振 舞い 方 大 遊
い あ 単 高 確 率 環 境 様 満 足 基 準 適 あ
UCB1 遥 高い 績 LS 示
1 同 設定 高確率 確率環境 い LS
満足 基準 min �
!,�! +|�!−�!|×0.5 設定 結果
4 示 �
! 子ノ X 以降 葉ノ
得 勝 負 情報 計算 勝率 あ
4 結果 LS 正解率 え率 2 単高確率
環 境 同 様 い UCB1 高 績 あ
LS 行 満足 木探索
善手 見 いう 適 一 考え
4.
議論
図 2:LS U（B1 正解 率 左 切 え率 右
図 3： 環 境毎 LS U（B1 木探 索方 法 違い
The 28th Annual Conference of the Japanese Society for Artificial Intelligence, 2014
- 4 -
本研究 碁 AI 等 多用さ い ン 木探
索 人間 知 触 さ LS 実装 LST 提案
UCT 提案論文[Kocsis 06] 同様 ョン
通 LST UCT 比較 結果 LST UCT 速
適解 収束 2, 4 参照 LS
木 探 索 い 人 間 知 見 満 足 基 準 従 い
特徴的 振 舞い 3 参照 本論文
残 ン 木探索 用い 方法 勝率 向
方法 振 舞い 方 紹 内容
本研究 提案手法 う 場合 有効 あ 議論
ン 木探索 場以前 AI 効率的 探
索 強さ 向 さ 優秀 評価関数 必要
あ 作 込 膨 大 時 間 費 や
い 強い AI 作 ン 木探
索 い 優 秀 評 価 関 数 作 込 同 様 方 向 プ
強 進 い [e.g., Gelly 06] 言うプ
本 来 意 味 あ ン 着 手 終 局 行 う
いう意味 あ 現在 多 碁 AI 等 ン
部 依 存 知 識 利 用 良 質 プ 用 い
一 回 プ 長 い 処 理 時 間 費 や プ
回 数 自 体 減 方 向 進 い
UCB1 膨 大 ン プ ン 数 前 提 高 性 能 示 い う
考 え 逆 方 向 あ LS う 速
正確 方法 必要 考え
ン 木探索 用い AI 勝率 大 目
標 振 舞 う う 振 舞 い 従 来 虱 潰 的
初 ン 木 探 索 実 装 Crazy
Stone [Coulom 06] 場時 振 舞い 方 注目 集
[美添 2012] 本研究 結果 UCB1 局面 優劣毎
各 指 標 変 現 い い ン 木 探 索 自
体 ン 特 徴 的 振 舞 生 要 因 あ 考 え
一方 LS 満足 基準 従い自 的 振 舞い 変
さ い LS 満足 基準 現在 局面 良い 断
場合 勝 利 着 手 楽観的 素早 選択 執 着
行動 中 満足 基準 高い 勝利 着手 一
場合 適 行動 2 単高確率環境 4
参照 逆 LS 現在 局面状況 勝利 見込 薄い
断 場 合 一 定 基 準 満 足 基 準 超 え 着 手
探 続 良 探 索 空 間 広 広 大 探 索
う LS 振 舞い 現在 AI い 稀少
あ 考 え 単 一 満 足 基 準 R 直 感 的 調 整
良い 強い 弱い AI 作 容易 あ
本研究 提案 LST 体的 う 場合 有
効 あ 議 論 善 手 善 手 評 価 値 著
種類 あ 例え 等 う 状況 い
4 示 う 満足 基準 高い選択肢 瞬時 見
LS 性質 有効 働 考え 記 逆 善手
善 手 評 価 値 差 あ い 種 類 あ 例 え
碁 等 ン 木 探 索 敗 状 況
中 数 少 い 活 路 あ 場 合 収 束 遅 点 あ
LS 選択肢 評価値 差 著 さいバン ッ 問
題 UCB 速 適解 収束 示さ
準 適解 抜 出 適解 得 示さ い
[Oyo 13, 14] LS 性質 本研究 示 探索
能力 碁等や収束遅延 問題 有効 働 考え
LS 選択肢 数 多 UCB 高 績
示 [大 用 14] 選 択 肢 多 い 状 況 特 碁 様
種類 高い 果 期待
5.
結語
人間 知 触 さ LS 用い LST 提案 方
法 UCT 速 適解 収束 人間 見 う 満
足 基準 特徴的 振 舞い示 LST 知
識 利用 作 込 碁AI 有効 働 満足 基
準 変 さ 多 例 有効 働 能性 議論
本研究 結果 実際 AI LST 実装 有
益 あ 考え 強い AI ン
ン 用 AI LST 体例 実装
参考文献
[Auer 02] Auer, P., Cesa-Bianchi, N., and Fischer, P.: Finite-time Analysis of the Multiarmed Bandit Problem, Machine learning, 47, 23–256 (2002).
[人工知能学会08] 人工知能学会： 人工知能学 ，
共立出版(2008).
[Bruegmann 93] Bruegmann, B.: Monte carlo go (1993). [Coulom 06] Coulom, R.: Efficient selectivity and backup
operators in monte carlo tree search. In P. Ciancarini and H. J. van den Herik, editors, Proceedings of the 5th International Conference on Computers and Games, Turin, Italy (2006). [Gelly 06] Gelly, S., Wang, Y., Munos, R., and Teytaud, O.:
Modification of UCT with Patterns in Monte-Carlo Go, Technical Report 6062, INRIA (2006).
[Oyo 13] Oyo, K. and Takahashi, T.: A Cognitively Inspired Heuristic for Two-Armed Bandit Problems: The Loosely Symmetric (LS) Model, Procedia Computer Science, 24, 194–204 (2013).
[Oyo 14] Oyo, K. and Takahashi, T.: A Human Causal Value Function and Its Optimality under Greedy Method for Two-Armed Bandit Problems, (AROB 19th 2014), 113−118
(2014).
[大用 14] 大用庫智, 高橋遉 ：緩い対称性 持 因果的価値 関 数 妥 当 性 バ ン ッ 問 題 対 有 効 性. (準 備中)
[Simon 56] Simon, H. A.: Rational choice and the structure of the environment, Psychological Review, 63(2), 129–138 (1956).
[Schaeffer 07] Schaeffer, J., Burch, N., Björnsson, Y., Kishimoto, A., Müller, M., Lake, R., Lu, P. and Sutphen, S.: Checkers Is Solved, Science, 317(5844), 1518–1522 (2007).
[Sutton 98] Sutton, R. S., and Barto, A. G.: Reinforcement Learning: An Introduction, Cambridge, MIT Press (1998).
[篠原 07] 篠原修 ， 口亮，桂 浩一，新 恒雄：因果性
基 信念形 N 本腕バン ッ 問題へ 適用，
人工知能学会論文 ，22(1)，58–68 (2007).
[Smith 94] Smith, S.J.J., and Nau, D.S.: An analysis of forward pruning, AAAI, 1386–1391, 1994.
[Kahneman 79] Kahneman, D. and Tversky, A.: Prospect theory: An analysis of decision under risk, Econometrica, 47, 263– 291 (1979).
[Kocsis 06] Kocsis, L. and Szepesv, C.: Bandit based Monte-Carlo Planning, Machine Learning: ECML 2006 In Proceedings of the 17th European conference on Machine Learning, 4212, 282–293 (2006).
[Takahashi 10] Takahashi, T., Nakano, M., and Shinohara, S.: Cognitive symmetry: Illogical but rational biases, Symmetry, Culture and Science, 21(1-3), 275–294 (2010).
[Takahashi 11a] Takahashi, T., Shinohara, S., Oyo, K., and Nishikawa, A.: Cognitive symmetries as bases for anticipation: A model of Vygotskyan development applied to word learning, International Journal of Computing Anticipatory Systems, 24, 95–106 (2011).
[Takahashi 11b] Takahashi, T., Oyo, K., and Shinohara, S.: A loosely symmetric model of cognition, Lecture Notes in Computer Science, 5778, 234–241 (2011).
[Tversky 81] Tversky, A. and Kahneman, D.: The framing of decisions and the psychology of choice, Science, 211, 453– 458 (1981).
