情報・システム工学概論 2015-05-25 コンピュータゲームプレイヤ鶴岡慶雅工学部電子情報工学科工学系研究科電気系工学専攻概要 • コンピュータ将棋と機械学習 – ゲームと人工知能 – ミニマックス探索、αβ枝刈り – 評価関数 • 囲碁、ポーカー、麻雀、他のゲーム – モンテカルロ木探索 – 不完全情報ゲーム – ナッシュ均衡ゲームと人工知能 • 人工知能研究 – 計算機で知的な情報処理ができるようにしたい • ゲーム AI – 限定された「世界」 – ルールが明確に定義 – 手法の性能評価が比較的容易 – 強い人間プレイヤの存在将棋 • Japanese chess • 持ち駒のルール（取った駒が再利用できる） • 将棋人口（１年に１回以上指した15歳以上の人の数）：７００万人将棋電王戦FINAL • 2015年３月～４月 – 持ち時間５時間 – プログラム事前提出 • 結果 – 第１局 – 第２局 – 第３局 – 第４局 – 第５局 ○ 斎藤慎太郎五段 vs Apery ● ○ 永瀬拓矢六段 vs Selene ● ● 稲葉陽七段 vs やねうら王 ○ ● 村山慈明七段 vs ponanza ○ ○ 阿久津主税八段 vs AWAKE ● コンピュータ将棋選手権2015 • 決勝リーグの結果（5月5日） Program Hardware (# cores) 勝敗分 ponanza 64 7 0 0 NineDayFever 18 5 1 1 AWAKE 8 4 2 1 Apery 8 4 3 0 52 3 4 0 544 3 4 0 12 1 7 0 8 0 8 0 GPS将棋 YSS 激指 Selene コンピュータ vs 人間 http://www.junichi-takada.jp/computer_shogi/comvshuman.html ２００５年１０月プロ棋士と将棋ソフトの対局禁止令棋力 • 段、級による評価 – 10級～1級、初段～六段 – 免状、将棋道場などによる • プロ棋士は独自の段、級 – 奨励会（三段まで） – 四段以上がプロ棋士 • 基準があいまいで棋力の評価には使えない将棋倶楽部２４ • インターネット将棋道場（会員数 30 万人） • レーティングシステムによる棋力評価 http://www.shogidojo.com/ レーティング • 棋力を数値化する手法 – Elo rating system EA = 1 1 + 10 ( RB − R A ) / 400 E A ：プレイヤAが勝つ確率 RA ：プレイヤAのレーティング RB ：プレイヤBのレーティング – 対局相手と勝ち負けの履歴から最尤推定将棋倶楽部２４のレーティングの分布 600 1600 2800 http://ameblo.jp/professionalhearts/entry-10003293849.html プロ棋士のレーティングの分布 45 40 40 40 人数 35 31 30 27 25 20 15 15 10 8 3 5 1 0 1200 1300 1400 1500 1600 1700 1800 1900 レーティング http://homepage3.nifty.com/kishi/ranking2.html コンピュータ将棋の棋力 • １局３０分以内で終わるような早指しの場合レーティングで 3500点以上 • 長い持ち時間の将棋では？ – 持ち時間が長くなると相対的に人間にとって有利コンピュータチェス・将棋・囲碁 FPGAで将棋プログラムを作ってみるブログ http://blog.livedoor.jp/yss_fpga/archives/53897129.html 稲庭将棋戦法 • 棋譜 – WCSC21_F2_GEK_PON.csa • 相手の時間切れ負けを狙う • 歩を全く突かず自陣のなかで駒を動かすだけ • どこかに駒のききを集中させれば簡単に崩壊するはずだが – そのような戦略的な思考はコンピュータは苦手 – 学習データにそのような棋譜がない – そもそも相手は自分が大優勢だと錯覚しているコンピュータの思考法の原理 2 現在の局面 2 １手先の局面２手先の局面 2 3 -4 1 0 -2 -4 -2 5 • 評価関数によって末端局面の有利・不利の度合いを数値化 • お互いが自分にとって最も都合の良い手を選ぶと仮定して逆算（ミニマックス探索）深さ優先探索 2 現在の局面 2 １手先の局面２手先の局面 2 3 -4 1 0 -2 -4 -2 • 関数の再帰呼び出しで簡単に実装できる • 省メモリ 5 枝刈り 2 現在の局面 2 １手先の局面 1 枝刈り！２手先の局面 2 3 1 -2 枝刈り！ -2 • 探索ノード数を大幅に減らせる • 現在局面で選択する手と評価値は変わらない反復深化最大深さ１で探索最大深さ２で探索最大深さ３で探索最大深さ４で探索 • 探索の最大深さを徐々に深くしていく • 時間がなるまで繰り返す評価関数 • 局面の有利／不利を数値化 – 互角ならゼロ – 先手が有利ならプラス – 後手が有利ならマイナス • 重要な要素 – – – – 駒の損得駒の働き玉の危険度序盤の駒組み＋320点駒の損得 • 駒の価値駒種価値駒種価値王 ∞ 竜 1280 飛 920 馬 1150 角 750 成銀 590 金 610 成桂 610 銀 570 成香 630 桂 310 と 660 香 270 歩 100 評価関数 • 線形モデル – 重みベクトルと特徴ベクトルの内積でスコアを計算重みベクトル v(t ) = w φ (t ) T 局面 t のスコア局面 t の特徴ベクトル特徴ベクトル • 駒の損得を表現する特徴ベクトル 1    − 1      3   （先手の飛車の数）－（後手の飛車の数）（先手の角の数）－（後手の角の数）（先手の歩の数）－（後手の歩の数）重みベクトル • それぞれの特徴の重要さを表す  920     750        100    飛車を1枚得していることの「重み」角を1枚得していることの「重み」歩を1枚得していることの「重み」スコアの計算 • 重みベクトルと特徴ベクトルの内積をとる  920     750  (1 − 1  3)   = −250     100     後手が少し（歩2.5枚ぶん）有利駒の働き • 序盤は駒の損得だけ考えていればよい • 終盤は「駒の損得より速度」 – 隅のほうの駒を取りにいっている間に自分の玉が追い詰められる ⇒ 昔の将棋ソフトの典型的な負けパターン • 駒の働きを考慮することが非常に重要駒の働きを表現する特徴ベクトル • 例）盤上の２つの駒の位置関係どんな駒がどこにいる (14×81) 2 = 1285956 129万次元の特徴ベクトル 重みベクトルを手作業で決めるのは無理！比較学習（comparison training） • コンピュータチェスの評価関数の自動学習 – Tesauro (2001), DeepThought – 教師付き学習 • エキスパートの棋譜 – 多少効果あり • 将棋では大成功 – 別名 Bonanza メソッド（先読みなしの）比較学習プログラムが選んだ手 v1 プロ棋士が指した手 v2 v3 • プロ棋士が指した手と同じ手を指すように調整 • v3 > v1 となるように重みベクトルを調整先読み＋学習プログラムが選んだ手 v1 プロ棋士が指した手 v2 v3 プログラムによる探索 y1 y3 • y3 > y1 となるように重みベクトルを調整 • プロ棋士の読みをプログラムの読みで代用最適化 • Bonanza 方式 (保木, 2006) – 損失関数を定義 ∑ T [wφ (t ) − wφ (t )] j∈N j T(x) 1.0 0.5 1 0.0 -2 -1 0 1 x / 歩の交換値 (保木, 2006) 図１：T(x) の関数形．（実線）階段型関数（破線）計算で実際に用いられたもの – 損失が極小になるように重みベクトルを最適化 2 激指の評価関数の学習法 • パーセプトロン学習 1. 学習データ中の局面をランダムにひとつ選ぶ 2. 最善手の選択を間違えるなら重みベクトルを更新 3. 以上、繰り返し • 更新式（正解手のスコアを超える手が１つの場合） ( ) w ← w + φ t * − φ (tˆ ) 正解手からの探索での末端局面間違えて選ぶ手からの探索での末端局面なぜ学習できるのか？ • 更新後のスコアの差を計算してみると・・・正解手の更新後のスコア φ (t )(w + φ (t ) − φ (tˆ )) = wφ (t ) + φ (t * * * ) * 2 ( ) − φ t * φ (tˆ ) 間違えて選んだ手の更新後のスコア 2 * * ˆ ˆ ˆ ˆ ˆ φ (t ) w + φ t − φ (t ) = wφ (t ) + φ t φ (t ) − φ (t ) ( 両者の差 ( ) ) ( ) ( ) (( ) ) wφ t − wφ (tˆ ) + φ t − φ (tˆ ) * もともとの差 * 必ず正 2 激指の評価関数の特徴量 • • • • • • • • • • • • • 盤上にある同種の駒の数持駒にある同種の駒の数自玉・相手玉との相対位置位置と自玉・相手玉の絶対位置との組み合わせ（序盤のみ）位置と大駒の絶対位置との組み合わせ（序盤のみ）隣にいる駒行（Y座標）、列（X座標）自分のきき、相手のききがついているかどうかピンされているかどうか歩でたたかれる可能性があるかどうか２つ上にある駒隣接する升にいる駒：学習 • 学習データ – プロ棋士の棋譜約５万局 – プロ棋士の指し手が正例、それ以外の合法手は負例 • 学習にかかる時間 – １６時間（探索深さ６） • 棋譜の指し手との一致率 – 序盤48.3% 中盤43.0% 終盤45.3% 激指の実装について • 言語 • 開発： C++ （約５万行）： linux + gcc • 探索法：実現確率打ち切り • 評価関数 : 自動学習（Bonanza 方式） • 探索速度： 200万局面／秒 on Xeon W5590 探索アルゴリズム • 実現確率打ち切り – 局面の実現確率を探索打ち切り条件とする（実現確率）＝（親局面の実現確率）ｘ（遷移確率） 1.0 0.5 0.3 0.5 0.7 0.35 0.3 0.2 0.1 遷移確率 0.5 0.15 実現確率遷移確率指し手のカテゴリだけ見てみるとカテゴリ駒得で取り返す駒得で駒を取る駒得で王手をかける飛車が成る角が成る：遷移確率 58～89％ 16～42％ 43％ 21％ 20％：様々な特徴量を用いて推定 • ロジスティック回帰モデル p( y | x ) = 1  F  1 + exp − ∑ λi f i ( x )  i =1  素性の重み素性関数 • ２値分類：「指される」 or 「指されない」 • 訓練データの尤度を最大化するようにパラメータ（素性の重み）を決定遷移確率推定に利用する特徴量 • • • • • • • • • 指し手そのもの（移動元と移動先の座標、駒の種類）駒の種類駒の移動元の局所的な盤面情報（3x3）駒の移動先の局所的な盤面情報（3x3）駒の移動先に敵のききがあるかどうか駒得をする手かどうか直前に動いた駒を取り返す手かどうか相手の飛車の位置と局所的な盤面情報の組み合わせ：学習 • プロ棋士の実戦譜約５万局 – 実際に指された手を正例、それ以外の手を負例とした学習データの条件付尤度を最大化 ( ) Lλ = ∑ log pλ y ( j ) | x ( j ) − C ∑ λi j – L1ノルムによる正則化 • 数値計算によって最適化 – OWL-QN法（quasi-Newton法） i 指し手予測の例激指の予測 ▲７一角（0.28） ▲３四歩（0.09） ▲５三角（0.09） ▲５三銀（0.02） ▲５七飛（0.02） ▲４一銀（0.02）： △４四金まで予測精度 • 学習データとは別の100局で評価 1位 10位まで 20位まで序盤 59.2% 97.0% 99.7% 中盤 40.2% 87.5% 95.9% 終盤 37.4% 83.2% 91.8% 合計 45.5% 89.3% 95.9% 読みの深さ • 中盤の局面（探索時間：約30秒） 8000000 7000000 6000000 5000000 4000000 3000000 2000000 1000000 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 詰め将棋王手の連続で相手玉を詰ます詰む手順が見つかれば勝ちそれぞれのノードの先頭で呼ぶ残りの実現確率に応じて詰めルーチンの探索ノード数の上限を設定 • アルゴリズム： dfpn • • • • – 証明数と反証明数を用いた深さ優先探索探索量と強さの関係探索の基本深さ勝敗勝率 9 vs 8 478勝 98敗24分 0.83 10 vs 9 458勝119敗23分 0.79 11 vs 10 441勝134敗25分 0.77 12 vs 11 447勝128敗25分 0.78 13 vs 12 433勝140敗27分 0.76 並列化による高速化 • αβ法 – 前の探索結果を利用して探索範囲を狭めることができる – 逐次的に実行するのが最も効率的 – 効率的に並列化することは難しい • 速度向上 – ８コアのマシンで約４倍の速度向上マルチスレッドによる並列化の効果コンピュータ将棋の棋力の伸び • 半分はハードウェアの進歩：速度２倍で70点 • 残りはソフトウェアの進歩棋力の伸びの予想 • 速度向上とレーイティング – 思考速度が2.5倍でレーティングが100点上昇 • コンピュータの速度向上 – 5年で10倍 • ソフトの改良がなくても10年でレーティングが 500点上昇？将棋ソフトの新しい役割 • 将棋プログラムは強くなりすぎた – もうアマチュアで勝てる人はいない • 人間の上達を助けるツール – 「悪手」「好手」の指摘 – 検討のツール – 指導対局 • 観戦のサポート