将棋プログラム「激指」 　鶴岡 慶雅

概要 ゲーム研究と将棋プログラム 実際の将棋プログラムの中身 探索アルゴリズム 指し手生成 評価関数 展望

コンピュータ将棋選手権

コンピュータ将棋選手権

コンピュータ将棋選手権

コンピュータ将棋選手権

ゲームプログラムの現状 チェス オセロ 将棋 囲碁 1997年 Deep Blue (IBM) vs カスパロフ 1997年 Logistello vs 村上健 Logistello の６勝０敗 将棋 アマ５段 囲碁 アマ初段（？）

コンピュータ将棋 チェス 将棋 取った駒は使えない 終盤になるほど盤上の駒が減るので branching factor が減少 全幅探索でもかなり強いプログラムが作れる 収束　⇒　終盤データベース 将棋 取った駒を持ち駒としていつでも使える 中終盤になると盤上の駒は減るが持ち駒が増えるのでbranching factor が増大 全幅探索では全然だめ 収束しない

激指 Overview 言語 ： C++ （約25000行） 開発OS ： Linux 探索法 ： 実現確率打ち切り 探索法 ： 実現確率打ち切り 探索速度 ： 10～15万 node / sec 5～10万 leaves / sec (AthlonXP 2000)

データ構造 将棋盤 駒 きき 直接きいている駒 間接的にきいている駒 近距離・遠距離 ピン 角 金 歩 桂 玉 香

探索アルゴリズム 実現確率打ち切り 局面の実現確率を探索打ち切り条件とする （実現確率）＝（直前の局面の実現確率）ｘ（遷移確率） 1.0 0.5 0.3 遷移確率 0.5 0.3 0.7 0.2 0.5 0.35 0.1 0.15 実現確率

遷移確率 指し手のカテゴリに基づいて決定 カテゴリ 遷移確率 駒得で取り返す 58～89％ 駒得で駒を取る 16～42％ 駒得で王手をかける 43％ 飛車が成る 21％ 角が成る 20％ ：

探索の振る舞い 取り返しなどの手順が続く局面は深く読む 駒をただで取られるような手順は深く読まれない ありそうな展開を中心に読むため、トリッキーな手の見落としの危険はあるが、資源配分の効率化の効果の方が大きい

指し手生成 カテゴリごとに生成 可能な指し手を差分更新する方法もあるが、そうすると指し手のカテゴリを判別する処理が重くなる 「ある升目へ移動する手」等の primitive を組み合わせて生成 可能な指し手を差分更新する方法もあるが、そうすると指し手のカテゴリを判別する処理が重くなる

探索の深さ 中盤の局面で約１分探索

評価関数 駒の損得 駒の働き 玉の危険度 序盤の駒組み 相手玉および自玉に近いほどプラス 相手玉の周辺に自分のききがあるほどプラス 悪形はマイナス、など、

駒の損得 駒の価値 だいたいききの数の比例？ 参考） TD法による学習（飯田2002） 駒種 価値 王 ∞ 飛 950 角 800 金 600 銀 550 桂 400 香 歩 100 駒種 価値 竜 1300 馬 1150 成銀 600 成桂 成香 と 駒種 価値 王 ∞ 飛 943 角 675 金 570 銀 492 桂 223 香 196 歩 100 駒種 価値 竜 1535 馬 1196 成銀 481 成桂 443 成香 284 と 586 だいたいききの数の比例？

駒の働き 序盤は駒の損得だけ考えていればよい 終盤は「駒の損得より速度」 駒の働きを考える必要 どうでもいい駒を取りにいっている間に自分の玉が追い詰められる ⇒　コンピュータの典型的な負けパターン 駒の働きを考える必要

駒の働きの計算 盤面の進行度を0～100％の数値で評価 進行度に応じて位置の評価を重く 進行度はルートノードだけで判断するべきか？ 探索結果の評価値の一貫性がなくなる 局面が急激に変化するときにまずい

局面の進行度 序盤～終盤を、0～128の数値で表現 重要な駒が敵陣に近づいて いるほど終盤に近い （進行度） ＝Σ（駒の重み）ｘ（段の重み） 駒種 重み 王 15 飛 10 角 7 金 8 銀 桂 5 香 歩 2 段 重み 1 4 2 3 5 6 7 8 9 重要な駒が敵陣に近づいて いるほど終盤に近い （進行度） 　＝Σ（駒の重み）ｘ（段の重み）

駒の働き 敵玉に対する働き 自玉に対する働き

駒の働き（例） 敵玉に対する働き 位置の評価 140% 進行度 85% 玉 金 駒の価値が 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

棋力の伸びの予想 自己対戦の結果から コンピュータの速度向上 10年でレーティング1000点上昇？ 思考時間が2.5倍でレーティング200点上昇 コンピュータの速度向上 5年で10倍 10年でレーティング1000点上昇？ ちょっと楽観的すぎる

なぜ楽観的すぎるのか Diminishing return 自己対戦では勝率が過大になる コンピュータチェスでは、探索が深くなるほど、一手深く探索する効果が減少していく 自己対戦では勝率が過大になる 理由 同じ探索アルゴリズム、評価関数を用いているため、浅い方の探索が深い方に包含される 評価関数の欠点が顕在化しない

高速化するための努力 盤面情報の更新の差分化 評価関数を差分化 並列化 プロファイラで重い所を探す 駒を移動したときのききの更新など 駒の損得と働きに関しては完全に差分化 他の細かいところは差分化が大変 並列化 プロファイラで重い所を探す

どの処理に時間がかかっているか？ 処理 割合 局面評価 ２８％ 駒の移動 ２２％ 指し手生成 １６％ 詰みチェック １５％ 仮評価 １０％ ：

並列化 αβ法 それでも無理やり並列化すると 探索結果を利用して window を狭めていく sequential に実行するのが最も効率的 もともと並列化には適さない それでも無理やり並列化すると Opteron Dual で約1.5倍の速度向上

プログラムの改良・修正 やみくもにプログラムを変更するのは危険 序盤の500局面をプロの実戦譜から抽出 バグが入るかも？ 強くしたつもりが弱くなってるかも？ 序盤の500局面をプロの実戦譜から抽出 変更のたびに1000局（先後入れ替え）対戦 変更前 ｖｓ　変更後 520勝480敗なら強くなったと言えるのか？

統計的検定 帰無仮説 帰無仮説が正しいとして、観測データの尤度（起きる確率）を求める 尤度が小さければ帰無仮説を棄却 「２つのプログラムは同じ強さである」 帰無仮説が正しいとして、観測データの尤度（起きる確率）を求める 尤度が小さければ帰無仮説を棄却 「２つのプログラムは同じ強さであるとはいえない」

統計的検定 尤度 対局数が1000回で、σ＝１５ ５３０勝４７０敗なら、強くなったと言ってもいいかも ベルヌーイ試行なので二項分布 正規分布で近似 対局数が1000回で、σ＝１５ ５３０勝４７０敗なら、強くなったと言ってもいいかも

展望 評価関数の自動学習 大規模PCクラスタによる並列化 上達のパートナーとしてのプログラム 名人を超えるのはいつか？

評価関数の自動学習 TD法 局面が進んだときの評価値の変化が少なくなるようにパラメータを調整していく （評価値のグラフ）

名人を超えるのはいつか？ NHK人間講座「大局を観る」 米長邦雄 永世棋聖 「…さて、では将棋のトッププロとコンピュータではどうでしょうか。現在は人間のほうがずっと強いし、コンピュータ科学が思いもかけない飛躍でもしなかぎり、少なくともあと１００年は人間の力のほうが上でありつづけるだろうと、私は思っています。 （中略） 　　この、手を渡したり、金を寄せたりといった微妙な駆け引きがコンピュータは苦手です。というより、わからない。それらは過去のデータや計算からは導き出せない微妙な、ある意味では摩訶不思議な手なので、どう対応していいかわからなくなってしまうのです。…」

強くなるだけではだめ？ 将棋プログラムは強くなりすぎた 強さ以外に楽しめる要素 1000人に一人しか勝てない 「悪手」「好手」の指摘 検討のツール 指導対局 棋風のシミュレーションによる仮想棋士

最大エントロピー法を利用した棋譜集からの指し手学習 鶴岡慶雅

大山名人はこの局面でどう指す？ 後手番 正解 ２五歩 激指の予測 ２五歩（9.2%） ８四歩（7.3%） ４五歩（5.9%） 正解　２五歩 激指の予測 　２五歩（9.2%） 　８四歩（7.3%） 　４五歩（5.9%） 　５三銀（5.4%） 　　：

指し手を確率的に予測 用途 方法 棋士の棋風を再現 実現確率打ち切り探索の遷移確率 探索の枝狩り/延長 ： 　　： 方法 大量の棋譜から確率モデルを利用して機械学習

最大エントロピー法による 機械学習 Log-linear model ２値分類： 「指される」 or 「指されない」 訓練データの尤度を最大化するようにパラメータ（素性の重み）を決定 素性関数 素性の重み

学習に利用する素性（特徴量） 指し手そのもの（移動元と移動先の座標、駒の種類） 駒の種類 駒の移動元の局所的な盤面情報（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 79.4 84.9 9 99.9 82.2 87.0 10 84.6 88.8 ※局面ごとに上位ｎ個の指し手を出力し、その中に正解手が含まれているかどうかのパーセンテージ ※訓練データ：５１２局 訓練データに存在しない局面でも３割以上の確率で正解手を当てている。

正解率と訓練データ量の関係 訓練データは多ければ多いほどよい ５００局でもまだ不足

指し手予測の例 先手番 正解　１六歩 激指の予測 　６六歩（25％） 　６八銀（11％） 　４七銀（10％） 　３七銀（9％） 　　：

指し手予測の例 先手番 正解　４五歩 激指の予測 　４五歩（70.1%） 　５五歩（23.2%） 　４五桂（6.4%） 　２五歩（3.8%） 　　：

課題 予測精度 探索への利用 棋風の再現 学習に利用する特徴量をさらに工夫する 訓練データを増やす 実現確率打ち切りに適用 探索による結果とどう折り合いをつけるか