将棋プログラム「激指」 鶴岡 慶雅 概要 ゲーム研究と将棋プログラム 実際の将棋プログラムの中身 探索アルゴリズム 指し手生成 評価関数 展望 コンピュータ将棋選手権 コンピュータ将棋選手権 コンピュータ将棋選手権 コンピュータ将棋選手権 ゲームプログラムの現状 チェス 1997年 Deep Blue (IBM) Deep Blue の２勝１敗３分 オセロ 1997年 Logistello vs Logistello の６勝０敗 将棋 アマ５段 vs カスパロフ 囲碁 アマ初段（？） 村上健 コンピュータ将棋 チェス 取った駒は使えない 終盤になるほど盤上の駒が減るので branching factor が減少 全幅探索でもかなり強いプログラムが作れる 収束 ⇒ 終盤データベース 将棋 取った駒を持ち駒としていつでも使える 中終盤になると盤上の駒は減るが持ち駒が増えるのでbranching factor が増大 全幅探索では全然だめ 収束しない 激指 Overview 言語 開発OS 探索法 探索速度 ： C++ （約25000行） ： Linux ： 実現確率打ち切り ： 10～15万 node / sec 5～10万 leaves / sec (AthlonXP 2000) データ構造 将棋盤 駒 きき 角 直接きいている駒 間接的にきいている駒 近距離・遠距離 ピン 金 歩 桂 玉 香 探索アルゴリズム 実現確率打ち切り 局面の実現確率を探索打ち切り条件とする （実現確率）＝（直前の局面の実現確率）ｘ（遷移確率） 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％ ： 探索の振る舞い 取り返しなどの手順が続く局面は深く読む 駒をただで取られるような手順は深く読まれ ない ありそうな展開を中心に読むため、トリッキー な手の見落としの危険はあるが、資源配分の 効率化の効果の方が大きい 指し手生成 カテゴリごとに生成 「ある升目へ移動する手」等の primitive を組み 合わせて生成 可能な指し手を差分更新する方法もあるが、 そうすると指し手のカテゴリを判別する処理 が重くなる 探索の深さ 中盤の局面で約１分探索 3500000 3000000 2500000 ノード数 2000000 1500000 1000000 500000 0 1 2 3 4 5 6 7 8 9 10 11 12 深さ 13 14 15 16 17 18 19 20 21 22 評価関数 駒の損得 駒の働き 相手玉および自玉に近いほどプラス 玉の危険度 相手玉の周辺に自分のききがあるほどプラス 序盤の駒組み 悪形はマイナス、など、 駒の損得 駒の価値 参考） TD法による学習（飯田2002） 駒種 価値 駒種 価値 駒種 価値 駒種 価値 王 ∞ 竜 1300 王 ∞ 竜 1535 飛 950 馬 1150 飛 943 馬 1196 角 800 成銀 600 角 675 成銀 481 金 600 成桂 600 金 570 成桂 443 銀 550 成香 600 銀 492 成香 284 桂 400 と 600 桂 223 と 586 香 400 香 196 歩 100 歩 100 だいたいききの数の比例？ 駒の働き 序盤は駒の損得だけ考えていればよい 終盤は「駒の損得より速度」 どうでもいい駒を取りにいっている間に自分の玉 が追い詰められる ⇒ コンピュータの典型的な負けパターン 駒の働きを考える必要 駒の働きの計算 盤面の進行度を0～100％の数値で評価 進行度に応じて位置の評価を重く 進行度はルートノードだけで判断するべき か？ 探索結果の評価値の一貫性がなくなる 局面が急激に変化するときにまずい 局面の進行度 序盤～終盤を、0～128の数値で表現 駒種 重み 段 重み 王 15 1 4 飛 10 2 4 角 7 3 4 金 8 4 3 銀 7 5 2 桂 5 6 1 香 5 7 0 歩 2 8 0 9 0 重要な駒が敵陣に近づいて いるほど終盤に近い （進行度） ＝Σ（駒の重み）ｘ（段の重み） 駒の働き • 敵玉に対する働き 39 46 54 66 88 120 150 150 110 97 70 50 31 15 7 3 0 37 44 50 62 84 110 140 140 110 89 62 39 19 7 0 0 0 35 39 48 57 80 100 115 120 107 78 46 31 15 7 0 0 0 34 36 45 50 62 74 78 74 65 48 35 15 7 0 0 0 0 28 35 42 46 50 52 54 50 46 31 23 7 3 0 0 0 0 15 19 27 31 32 34 35 32 31 23 19 11 5 0 0 0 0 9 11 15 19 23 31 29 27 23 19 11 7 3 0 0 0 0 3 5 9 14 19 25 25 25 15 7 3 0 0 0 0 0 0 • 自玉に対する働き 3 4 6 11 15 19 23 19 7 0 0 0 0 0 0 0 0 23 21 27 25 31 28 39 36 54 53 80 80 95 98 113 112 120 110 100 105 90 85 64 60 39 35 27 19 19 11 11 7 7 0 21 25 26 34 50 70 84 92 92 88 76 46 31 15 7 0 0 20 23 26 31 42 55 65 65 65 62 46 35 21 11 5 0 0 17 17 19 27 31 39 42 42 42 39 27 19 7 0 0 0 0 7 10 12 15 17 19 23 23 23 19 15 7 0 0 0 0 0 3 4 5 6 6 7 9 9 9 8 6 1 0 0 0 0 0 0 0 0 1 1 1 2 2 2 2 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 駒の働き（例） 敵玉に対する働き 玉 位置の評価 140% 進行度 85% 金 (1.4 1.0) 0.85 0.34 駒の価値が 34%UP！ 序盤の駒組 よくある方法 矢倉囲い、美濃囲いなどの形を覚えておく それらの形に近いほど評価値を高くする 激指では 囲いの形は（ほとんど）知らない 部分的な悪形を減点 探索と評価関数の関係 探索アルゴリズムによって最適な評価関数は 異なる 探索の深さによっても異なる 原則的には、探索が深いほど単純でよい 完全に探索できるのなら０か１ １手しか探索できないなら非常に複雑な局面評価 詰めルーチン 王手の連続で相手玉を詰ます 詰む手順が見つかれば勝ち それぞれのノードの先頭で呼ぶ 残りの実現確率に応じて詰めルーチンの探 索ノード数の上限を設定 アルゴリズム： PDS （長井1998） 証明数と反証明数を用いた深さ優先探索 コンピュータ将棋の棋力 レーティング 強さを数値化 参考） 段級位とレーティング（飯田2002） レーティング 段級位 ソフトの達成年 強い相手に勝つと 1400 アマ2級 1995年 大きく増える 弱い相手に負ける と大きく減る 1600 アマ初段 1996年 1800 アマ二段 1997年 2000 アマ三段 1999年 2200 アマ四段 2001年 2400 アマ六段 2600 プロ 2800 タイトル保持者 探索量と強さの関係 勝敗 勝率 レベル12 vs レベル11 167勝25敗8分 0.870 レベル11 vs レベル10 155勝38敗7分 0.803 レベル10 vs レベル9 165勝28敗7分 0.855 レベル9 vs レベル8 173勝21敗6分 0.892 レベル8 vs レベル7 182勝16敗2分 0.919 棋力の伸びの予想 自己対戦の結果から 思考時間が2.5倍でレーティング200点上昇 コンピュータの速度向上 5年で10倍 10年でレーティング1000点上昇？ ちょっと楽観的すぎる なぜ楽観的すぎるのか Diminishing return コンピュータチェスでは、探索が深くなるほど、一 手深く探索する効果が減少していく 自己対戦では勝率が過大になる 理由 同じ探索アルゴリズム、評価関数を用いているため、 浅い方の探索が深い方に包含される 評価関数の欠点が顕在化しない 高速化するための努力 盤面情報の更新の差分化 駒を移動したときのききの更新など 評価関数を差分化 駒の損得と働きに関しては完全に差分化 他の細かいところは差分化が大変 並列化 プロファイラで重い所を探す どの処理に時間がかかっている か？ 処理 割合 局面評価 ２８％ 駒の移動 ２２％ 指し手生成 １６％ 詰みチェック １５％ 仮評価 １０％ ： ： 並列化 αβ法 探索結果を利用して window を狭めていく sequential に実行するのが最も効率的 もともと並列化には適さない それでも無理やり並列化すると Opteron Dual で約1.5倍の速度向上 プログラムの改良・修正 やみくもにプログラムを変更するのは危険 バグが入るかも？ 強くしたつもりが弱くなってるかも？ 序盤の500局面をプロの実戦譜から抽出 変更のたびに1000局（先後入れ替え）対戦 変更前 ｖｓ 変更後 520勝480敗なら強くなったと言えるのか？ 統計的検定 帰無仮説 「２つのプログラムは同じ強さである」 帰無仮説が正しいとして、観測データの尤度 （起きる確率）を求める 尤度が小さければ帰無仮説を棄却 「２つのプログラムは同じ強さであるとはいえな い」 統計的検定 尤度 ベルヌーイ試行なので二項分布 正規分布で近似 対局数が1000回で、σ＝１５ ５３０勝４７０敗なら、強くなったと言ってもいい かも 展望 評価関数の自動学習 大規模PCクラスタによる並列化 上達のパートナーとしてのプログラム 名人を超えるのはいつか？ 評価関数の自動学習 TD法 局面が進んだときの評価値の変化が少なくなる ようにパラメータを調整していく （評価値のグラフ） 名人を超えるのはいつか？ NHK人間講座「大局を観る」 米長邦雄 永世棋聖 「…さて、では将棋のトッププロとコンピュータではどうでしょ うか。現在は人間のほうがずっと強いし、コンピュータ科 学が思いもかけない飛躍でもしなかぎり、少なくともあと１ ００年は人間の力のほうが上でありつづけるだろうと、私 は思っています。 （中略） この、手を渡したり、金を寄せたりといった微妙な駆け引 きがコンピュータは苦手です。というより、わからない。そ れらは過去のデータや計算からは導き出せない微妙な、 ある意味では摩訶不思議な手なので、どう対応していい かわからなくなってしまうのです。…」 強くなるだけではだめ？ 将棋プログラムは強くなりすぎた 1000人に一人しか勝てない 強さ以外に楽しめる要素 「悪手」「好手」の指摘 検討のツール 指導対局 棋風のシミュレーションによる仮想棋士 最大エントロピー法を 利用した棋譜集から の指し手学習 鶴岡慶雅 大山名人はこの局面でどう指す？ 後手番 正解 ２五歩 激指の予測 ２五歩（9.2%） ８四歩（7.3%） ４五歩（5.9%） ５三銀（5.4%） ： 指し手を確率的に予測 用途 棋士の棋風を再現 実現確率打ち切り探索の遷移確率 探索の枝狩り/延長 ： 方法 大量の棋譜から確率モデルを利用して機械学習 最大エントロピー法による 機械学習 Log-linear model 素性の重み 素性関数 1 F qx exp i f i x Z i 1 ２値分類： 「指される」 or 「指されない」 訓練データの尤度を最大化するようにパラメータ （素性の重み）を決定 学習に利用する素性（特徴量） 指し手そのもの（移動元と移動先の座標、駒の種類） 駒の種類 駒の移動元の局所的な盤面情報（3x3） 駒の移動先の局所的な盤面情報（3x3） 駒の移動先に敵のききがあるかどうか 駒得をする手かどうか 直前に動いた駒を取り返す手かどうか 相手の飛車の位置と局所的な盤面情報の組み合わせ ： 学習 大山十五世名人の棋譜６５０局を分割 訓練データ： ５１２局 テストデータ：１００局 中盤までの全ての局面（進行度４０以内）にお いて、可能な指し手を全て生成し、学習デー タとする 指し手予測の正解率 順位 訓練データに 存在する局面 訓練データに 存在しない局面 計 1 77.7 35.3 46.9 2 91.0 49.4 60.8 3 95.5 58.0 68.2 4 98.5 63.8 73.2 5 99.1 69.1 77.3 6 99.4 73.3 80.4 7 99.8 76.8 83.1 8 99.8 79.4 84.9 9 99.9 82.2 87.0 10 99.9 84.6 88.8 ※局面ごとに上位ｎ個の 指し手を出力し、そ の中に正解手が含ま れているかどうかの パーセンテージ ※訓練データ：５１２局 訓練データに存在し ない局面でも３割以 上の確率で正解手を 当てている。 正解率と訓練データ量の関係 known unknown total 100 90 80 正解率（％） 70 60 50 40 30 20 10 0 10 100 訓練データ数（局数） 1000 訓練データは多けれ ば多いほどよい ５００局でもまだ不足 指し手予測の例 先手番 正解 １六歩 激指の予測 ６六歩（25％） ６八銀（11％） ４七銀（10％） ３七銀（9％） ： 指し手予測の例 先手番 正解 ４五歩 激指の予測 ４五歩（70.1%） ５五歩（23.2%） ４五桂（6.4%） ２五歩（3.8%） ： 課題 予測精度 学習に利用する特徴量をさらに工夫する 訓練データを増やす 探索への利用 実現確率打ち切りに適用 棋風の再現 探索による結果とどう折り合いをつけるか
© Copyright 2024 ExpyDoc
