ナッシュ均衡 ( 最適反応 ) 支配戦略のみで説明できない場合 ( その) 戦略 A 戦略 B 戦略 A (,) (0,0) 戦略 B (0,0) (,) 支配戦略均衡 : 無しナッシュ均衡 :(,) と (,) 支配戦略均衡よりも適応範囲が広いナッシュ均衡の良い性質各プレイヤーは戦略変更の積

Size: px

Start display at page:

Download "ナッシュ均衡 ( 最適反応 ) 支配戦略のみで説明できない場合 ( その) 戦略 A 戦略 B 戦略 A (,) (0,0) 戦略 B (0,0) (,) 支配戦略均衡 : 無しナッシュ均衡 :(,) と (,) 支配戦略均衡よりも適応範囲が広いナッシュ均衡の良い性質各プレイヤーは戦略変更の積"

ふじよしありはら
5 years ago
Views:

1 コンピュータ将棋の技術と展望自己紹介名前保木邦仁 ( 生まれ北海道東区 ) 年齢 36 職業電気通信大学特任助教専門 00 年頃まで化学, 以降ゲーム情報学コンピュータ将棋プログラム Bonanza を作っています囲碁将棋から学ぶゲーム情報学公開講座保木邦仁 0 年月 8 日内容将棋と関係するゲーム理論概略将棋と関係するゲーム理論概略チェス将棋の思考アルゴリズムコンピュータ将棋対人間の歴史ゲームの完全解明 ( 神の一手?) は究極的な目標の一つ囲碁将棋のようなゲームでゲーム値 ( 勝ち負け引き分け ) 最適な戦略フォンノイマン ( ミニマックス定理 ) とはどのようなものなのだろうかジョンナッシュ ( ナッシュ均衡 ) 戦略形ゲームー支配戦略と支配戦略均衡他店と競争しなければならない過去のデータから値段設定に対する売上は大体想像可能低価格で沢山売れる客は安い方の店から商品を買う他店できるだけ売上を増やしたい店長ゲーム自店 (900,900) (800,0) (800,0) 9 (0,800) (800,800) (600,0) (0,800) (0,600) (700,700) 相手プレイヤーの行動基準がどうであろうとも支配戦略 (7) をとるのが良い他店パレート最適性 ( 囚人のジレンマ ) 支配戦略のみで説明できない場合 ( その ) 自店通常営業一斉値下げ通常営業 (+ 千万,+ 千万 ) ( 倒産, 千万 ) 一斉値下げ ( 千万, 倒産 ) (- 千万,- 千万 ) 支配戦略均衡 :( 一斉値下げ, 一斉値下げ )? パレート最適 :( 通常営業, 通常営業 ) ゲームの性質によっては何が最善なのかはっきりしない場合がある

2 ナッシュ均衡 ( 最適反応 ) 支配戦略のみで説明できない場合 ( その) 戦略 A 戦略 B 戦略 A (,) (0,0) 戦略 B (0,0) (,) 支配戦略均衡 : 無しナッシュ均衡 :(,) と (,) 支配戦略均衡よりも適応範囲が広いナッシュ均衡の良い性質各プレイヤーは戦略変更の積極的な理由がない支配戦略均衡はナッシュ均衡先ほどの支配戦略均衡の例自店 7 9 他店 7 (900,900) (800,0) (800,0) 9 (0,800) (800,800) (600,0) (0,800) (0,600) (700,700) ナッシュ均衡戦略を支配する戦略はないナッシュ均衡の良くない性質非合理的なプレイヤーに対する不安戦略 A 戦略 B 戦略 A (,) (0,) 戦略 B (0,) (,0) 戦略の組 (A, A ) が唯一のナッシュ均衡プレイヤーが戦略 B を選らんでしまった場合にプレイヤーも戦略 B を選べばよかったと後悔ジムナッシュ均衡の良くない性質チキンレースジョンハンドル切るハンドル切らないハンドル切る ( チキン, チキン ) ( チキン, 勝ち ) ハンドル切らない ( 勝ち, チキン ) ( 死亡, 死亡 ) 戦略の組 ( 切る, 切らない ) と ( 切らない, 切る ) はナッシュ均衡相手がどっちの均衡を目指すのか不明な場合ナッシュ均衡は戦略決定の指針とならない人ゼロ和ゲーム利得の和がゼロ戦略 A 戦略 B 戦略 A (,-) (0,0) 戦略 B (0,0) (-,) 戦略 A 戦略 B 戦略 A 0 戦略 B 0 - 以下のように簡略化して利得行列を書くゼロ和の場合のナッシュ均衡の更に良い性質戦略 A 戦略 B 戦略 A 0 5 戦略 B -5 0 他のプレイヤーが非合理的な戦略を選んでも自分の利得が減少することはない

ゼロ和の場合のナッシュ均衡の更に良い性質戦略 A 戦略 B 戦略 C 戦略 A 0 戦略 B - - - 戦略 C 0 0 0 複数の戦略の組 (A, A) と (C, A) はナッシュ均衡を形成均衡戦略を交換した組もまた均衡を形成し利得が等しいミニマックスとマックスミニ戦略保証水準を最大にする戦略戦略 A 戦略 B 戦略 C 戦略 A 0-6 戦略 B - 0 3 戦略 C 6-3 0

3 ゼロ和の場合のナッシュ均衡の更に良い性質戦略 A 戦略 B 戦略 C 戦略 A 0 戦略 B 戦略 C 複数の戦略の組 (A, A) と (C, A) はナッシュ均衡を形成均衡戦略を交換した組もまた均衡を形成し利得が等しいミニマックスとマックスミニ戦略保証水準を最大にする戦略戦略 A 戦略 B 戦略 C 戦略 A 0-6 戦略 B 戦略 C 一般にマックスミニ値ミニマックス値プレイヤーはミニマックス値を狙うと戦略 B プレイヤーがマックスミニ値を狙うと予想すると戦略 A -6 ゼロ和の場合のナッシュ均衡の更に良い性質 3 展開型ゲームの良い性質戦略 A 戦略 B 戦略 C 戦略 A 0-6 戦略 B 3 戦略 C マックスミニ値とミニマックス値が一致マックスミニ戦略とミニマックス戦略は均衡点を形成展開型ゲームは標準型ゲームに置き換えることが可能ナッシュ均衡戦略を再帰的に求めることが可能ミニマックス値 () がこのようなゲームの解と考えられる最適反応戦略不合理なプレイヤーに対しても損をしないマックスミニ値と等しいどの均衡戦略が複数あっても値は同じ他の戦略に支配されないチェス将棋の思考アルゴリズム ( テーマ) 将棋は分岐数が多いチェスのように探索できるのか? 最善応手系列静的評価関数 ( テーマ) 静的評価関数の効果的な設計法は? 力づく探索の効率改善将棋の合法手数は持ち駒ルールのため平均 80 手末端局面数は 80 d (d は探索深さ ) 枝刈によって計算量を削減 αβ 枝刈前向き枝刈 8 3

4 6 以下 5 以下確定以上以上 3 以下以上 α 枝刈以上 α 枝刈 3 以下 3 以下計算のオーダーを最大で n d から n d/ に削減

5 探索局面数将棋ゲーム木の前向き枝刈り ab 探索 ab 探索 Bonanza 基準探索深さ探索局面減少 Futility 枝刈 Null Move 枝刈 LMR 法 ( 簡易実現確率 ) 8 チェスで上手くいくことが知られている前向き枝刈りを将棋に応用図 : 探索局面数の基準深さ依存性終盤局面秒程度の時間で深さ 0 個により平均 8の全幅探索相当の計算が可能これはコンピュータの長所で人間にはとても無理将棋の局面評価法局面の良し悪しを適当に見積もる関数ゲーム中の局面の特徴を, 重みを付けて足し合わせるチェス : 駒割り機動性中央制圧度オセロ : 合法手の数辺, 隅の形将棋 : 局面の評価が大変困難といわれていた 005 年ごろから評価関数の大規模な自動学習が成功 009 年コンピュータ将棋選手権順位 GPS 将棋プログラム名大槻将棋 3 文殊 KCC 将棋 5 Bonanza 位から 5 位までこの自動学習法を採用コンピュータが一層強くなった概要評価関数の教師付き機械学習プロ棋士の選択 a 上方修正コンピュータの選択 7 ルート局面 b 子局面 5 7 末端評価値 c 下方修正性質の良い目的関数を設計してミニマックス探索ごと自動調整一致率 (%) 大規模機械学習の将棋での試み歩歩大規模な機械学習が安定して行われる + + 銀玉 5 千万パラメータ百 5 十万パラメータ 6 万パラメータ既存手法 (6 万パラメータ ) 0 反復回数銀銀玉銀玉銀歩銀玉現在の機械学習の問題点人間熟達者の棋譜から学習人間を超えることができるのか? 棋譜に表れにくい状況入玉型不思議で怪しい駒組みコンピュータ将棋対人間 007 Bonanza 対渡辺明竜王コンピュータ側 : Intel Xeon.66GHz 8 core 人間側 : 現在も竜王タイトルを保持コンピュータ敗北 00 あから対清水市代女流王将コンピュータ側 : 約 00 台の計算機使用人間側 : 通算タイトル獲得数歴代位コンピュータ勝利 0 ボンクラーズ対米長邦雄永世棋聖コンピュータ側 : 伊藤英紀氏 ( 富士通 ) 開発人間側 : 現役時代トッププレイヤーコンピュータ勝利コンピュータはトッププレイヤーに未だ勝利していない 5

あから 00 について合議法の利用約 00 台の計算機を使用分散並列探索法 + 合議法異種プログラム (Gekisashi, GPS

: 多数決による性能の向上勝率は一手 3 秒,000 局より計算 Player 勝率 (%) 多数決合議 73 Gekisashi 50 GPS

公式戦で初めて人間が対コンピュータ戦略をとるボンクラーズは 0 年コンピュータ将棋選手権で優勝 Bonanza のソースコードを参考にして作成された

異種格闘戦, 東京, 976 レスリング ( アントニオ猪木 ) キックが得意ボクシング ( モハメドアリ ) パンチが得意図 :

6 あから 00 について合議法の利用約 00 台の計算機を使用分散並列探索法 + 合議法異種プログラム (Gekisashi, GPS Shogi, Bonanza, YSS) で多数決合議法についてフェイルセーフな分散並列環境の構築複数プログラムの寄せ集めで強い人工知能作成表 : 多数決による性能の向上勝率は一手 3 秒,000 局より計算 Player 勝率 (%) 多数決合議 73 Gekisashi 50 GPS Shogi 36 あから 00 は清水女流王将に勝利した Bonanza 6 YSS 37 IPSJ Official Character T. Obata, T. Sugiyama, K. Hoki, T. Ito, CG00 電通大伊藤毅志助教との共同研究 Minimax 探索を行うプログラムの合議ボンクラズ対米長邦雄永世棋聖 (0) 公式戦で初めて人間が対コンピュータ戦略をとるボンクラーズは 0 年コンピュータ将棋選手権で優勝 Bonanza のソースコードを参考にして作成された ( といわれる ) 合議法によってミニマックス探索の結果が安定化されるのではないか? 人間プレイヤー側の第一手 6 二玉の意味は? 異種格闘戦, 東京, 976 レスリング ( アントニオ猪木 ) キックが得意ボクシング ( モハメドアリ ) パンチが得意図 : アントニオ猪木はラウンドほとんど寝転がった 5 ラウンド ( 最終ラウンド ) まで決着つかず引き分け怪しげな駒の運びでインファイトを回避防衛ラインを築くコンピュータは飛車を往復させて手待ちの繰り返し人間側は引き分けにする権利を得ていたかのように見えたがその後接近戦になったコンピュータの勝利 6

7 コンピュータ将棋の主な技術 00 年実現確率探索 ( 激指 ) DFPN ( 詰将棋 ) 006 年評価関数の機械学習 (Bonanza) 力づく探索 (Bonanza) 009 年合議法 ( 文殊 ) 00 年分散並列探索の実用化 (GPS 将棋 ) 006 年以降数の暴力に頼った方法が将棋でも成功をおさめているまとめ大量のデータを許容できる時間内にできるだけ沢山処理する技術局面の深く広い探索大規模機械学習分散並列化今年のコンピュータ将棋選手権では予選敗退! 渡辺竜王を苦しめたと言われている Bonanza より強いプログラムが 8 個もあったトッププロにもう少しで追いつきそう表 : 今年のコンピュータ将棋選手権結果順位 GPS 将棋 Puella α 3 ツツカナ Ponanza 5 習甦 6 激指 7 YSS 8 Blunder 7

Microsoft PowerPoint - vc2013.s.takeuchi.pptx

Microsoft PowerPoint - vc2013.s.takeuchi.pptx コンピュータ将棋の技術と GPS 将棋について JST ERATO 湊離散構造処理系プロジェクト竹内聖悟概要 GPS 将棋の紹介コンピュータ将棋で使われる技術形勢判断と先読み GPS 将棋の技術今後の将棋 AI と研究コンピュータ将棋と可視化近年のコンピュータ将棋 2007 年 : 渡辺明竜王 -Bonanza 渡辺竜王の勝利 2010 年 : あから 2010- 清水市代女流王将あからの勝利