2025 年 4 月 19 日 Build with AI Kwansai

将棋AIの進化と最前線 〜アルゴリズム、評価関数、 そして未来〜 ザイオソフト コンピュータ将棋サークル 野田 久順 岡山県立大学情報工学部 助教 NPO法人AI電竜戦プロジェクト 副理事長 芝 世弐

目次 • 将棋 AI の概要 • 将棋 AI の種類 • CPU エンジン • GPU エンジン • 最新動向 • 定跡 • 知識蒸留 • 将来展望

自己紹介 • 野田 久順 (ひさより) • ザイオソフト コンピュータ 将棋ソフトサークル所属 • 主な実績 • 2017年 第5回将棋電王 トーナメント 優勝 • 2021年 CSA貢献賞 受賞 • 2024年 第34回世界 コンピュータ将棋 選手権 優勝 https://nlab.itmedia.co.jp/nl/articles/1711/13/news130.html

• https://nlab.itmedia.co.jp/nl/articles/1711/13/news130.html

自己紹介 • 芝 世弐 • 俗称白ビール：Kristallweizen(2019) • プロ団体が配信に利用 • 朝日新聞社・毎日新聞社のYouTube中継にも 利用されている • アマチュア棋士が AI の裏付けを加えて棋書を 書く時代に • プロアマ問わず多くの利用者

電竜戦 • 2020 年より NPO 法人 AI 電竜戦プロジェクトが 主催するオンライン将棋大会 • AI・人間ともに参加可能 • 寄付を受付中 • 低コスト参加を実現 • 2022年より ハードウェア統一戦を導入 （※それ以前は電王 トーナメントにて実施）

将棋 AI の概要

将棋 AI とは • 将棋を指すソフトウェア • 局面を入力すると 推奨手や評価値を提示 • 推奨手：次に指すべき指し手 • 評価値：先手・後手の有利さを 示す数値 ShogiHome https://sunfish-shogi.github.io/electron-shogi/

• https://sunfish-shogi.github.io/electron-shogi/

ゲーム木 • 合法手を基にゲームの状態を 展開する状態遷移の図 • ゲームのすべての状態遷移を 表現可能 • ゲーム木を調べつくすと、 両者が最善を尽くした 場合の結果を特定可能 … … • この過程を「ゲームを解く」と 呼ぶ … …

探索量から見たゲームの複雑さ • ゲームを解くための 探索局面数≒ゲームの複雑さ • 探索局面数= 𝑁 × 𝑁 × ⋯ 𝑁 = 𝑁𝑀 𝑁: 平均合法手数 𝑀: 平均終了手数 • 複雑なゲームでは、現実的な 時間内に全ての状態遷移を 読み切ることは不可能 ゲーム チェッカー オセロ チェス 中国象棋 将棋 囲碁 探索局面数 10 の 30 乗 10 の 60 乗 10 の 120 乗 10 の 150 乗 10 の 220 乗 10 の 360 乗

探索と評価 3 • 一定の手数まで 「探索」を行い、 その局面を「評価」する 3 • 探索：人間の「読み」に相当 • 評価：人間の「大局観」に相当 7 3 1 5 2 左側の状態に遷移する手が最善 この時の評価値は 3 4 1

将棋 AI のアーキテクチャ

CPU エンジンと GPU エンジン CPUエンジン GPUエンジン 探索アルゴリズム アルファ・ベータ法 PUCT 評価関数 NNUE評価関数 ディープラーニング評価関数 特徴 探索速度が速い 探索速度が遅い 末端局面の評価精度が低い 末端局面の評価精度が高い 終盤に強いとされる 序盤に強いとされる やねうら王、水匠、tanuki- dlshogi 主な将棋 AI

CPU エンジンの 探索アルゴリズム

ミニマックス法 …先手 …後手 • 先手は評価値の最大化を 目指す手を選択 …終端接点(評価を行った局面) • 先手：マックスプレイヤー • 後手は評価値の最小化を 目指す手を選択 3 • 後手：ミニマムプレイヤー 3 7 3 1 5 2 4 1

アルファ・ベータ法 …先手 …後手 • ミニマックス法と同じ計算結果 • 不要な探索の枝刈り …終端接点(評価を行った局面) 3 • 枝刈りの例 • 現在の先手の評価値は 3 • 先手の評価値の更新には 4 以上の 評価値が必要 • 後手は低い評価値を選択 • 調査した終端接点の評価値は 2 • 後手の評価値は 2 以下 • 先手の評価値は更新されない • この枝の探索打ち切りが可能 3 7 3 5 2

CPU エンジンの評価関数

NNUE 評価関数 • 2018年 那須悠 氏により発表 • 主な特徴 • ディープラーニングによる評価関数 • CPU による高速な推論 • 全結合ニューラルネットワーク • 活性関数は clipped ReLU • 差分計算による効率化 • 手番の考慮 • HalfKP 特徴量 • 整数 SIMD 演算による高速化

全結合ニューラルネットワーク • 隠れ層 3 層程度の浅い ディープラーニング … … … … … … … 入力層 (特徴量) 隠れ層 出力層 (評価値)

HalfKP 特徴量 • 将棋盤面を表す数値ベクトル • 玉の位置と玉以外の 1 駒の 位置と種類の組み合わせを One-hot encoding し、加算 • 81 × 1548 = 125,388 次元のベクトル 玉と玉以外の 1 駒の組み合わせの例 盤面上に存在するすべての組み合わせについて One-hot encoding したものを 足し合わせる

GPU エンジンの 探索アルゴリズム

PUCT • モンテカルロ木探索に基づく探索 • 以下の式が最大となる手を選択 0.3 0.8 0.2 0.1 0.4 0.2 0.4 0.7 0.5 0.3 0.2 0.1 0.2 0.5 0.4 𝑄 𝑠𝑡 , 𝑎 + 𝑈 𝑠𝑡 , 𝑎 勝率 𝑈 𝑠, 𝑎 = 𝑐𝑝𝑢𝑐𝑡 𝑃 𝑠, 𝑎 着手の確率 σ𝑏 𝑁 𝑠, 𝑏 1 + 𝑁 𝑠, 𝑎 𝑠𝑡 … 局面 𝑎 … 着手 𝑄 𝑠𝑡 , 𝑎 … 局面 𝑠𝑡 の勝率 探索回数の少なさ 𝑐𝑝𝑢𝑐𝑡 … 定数 𝑃 𝑠, 𝑎 … 着手の確率 𝑁 𝑠, 𝑎 … 𝑠 における 𝑎 の訪問回数 • 𝑄 𝑠𝑡 , 𝑎 と𝑃 𝑠, 𝑎 は評価関数が出力する。 …

GPU エンジンの評価関数

GPU エンジンの評価関数 • 畳み込みニューラルネットワーク（CNN）を使用 • 画像認識などで用いられる一般的手法の応用 • 局面を複数の画像に変換して入力 • 中間層は ResNet • 出力層は着手確率と勝率を出力

GPU エンジンのネットワーク例 着手の確率 (方策) ResNet ResNet ResNet … 勝率 (価値) ・ ・ ・ 入力層 ResNet blocks 中間層 出力層

入力層 • 局面を画像に変換して入力 • 駒の種類ごとに 2 値画像を 作成 • 駒があるマス：白（1） • 駒がないマス：黒（0） 先手の 歩のみ 白くする

入力層 (続) • 持ち駒の種類ごとに 最大枚数分の画像を用意 • 持ち駒あり：白（1） • 持ち駒なし：黒（0） • 合計 104 枚の画像として入力 金は 4 枚あるため 画像を 4 枚用意する

中間層 Convolution • ResNet (Residual Network) • ネットワークの深層化に強い 構造 • 層をスキップする ショートカット接続の導入 • ショートカットした層の 入力と出力の残差を学習 Batch Normalization ReLU Convolution Batch Normalization ReLU 残差ブロック

方策ネットワーク • 着手確率を出力 • 指し手の表現は移動先 × 移動方向の組み合わせ • 出力層は フィルターサイズ 1×1、 フィルター数 27 の 畳み込み層 ラベル数 移動する手 10 成る手 10 持ち駒から打つ手 7 合計 27 下 左下 右 駒 左 右上 上 左上 右上 (桂) 左上 (桂) 27枚 ⋯ ResNet 移動の種別 右下 ⋰

価値ネットワーク Batch Normalization ⋯ ResNet • 勝率を出力 • 出力層は 1×1 フィルター・ 27チャネルの畳み込み層 → ユニット数256の全結合層 → ユニット数1の全結合層 27枚 ⋰ 全結合 シグモイド 1 ユニット ReLU 256ユニット 全結合 勝率

最新動向

最新動向 • 定跡 • 知識蒸留

定跡

定跡 • 局面とその局面における指し手のリスト ☗２六歩 96% ☗７六歩 2% …

定跡 • 定跡の役割 • 序盤の思考時間を節約 • 評価関数の精度の悪さを補助 • 有利な局面への誘導

定跡 2010 年代前半 2010 年代後半 • 手動入力による構築 • プロ棋士の棋譜からの生成 • floodgate の棋譜からの 自動抽出 • 自己対局による定跡生成 • 勝率に基づく選別 • 評価値に基づく選別 • モンテカルロ木探索の導入 • 定跡データベース末端局面の 評価値によるミニマックス 処理

定跡 2020 年代前半 2020 年代後半 • 自己対局結果による 定跡の自動修正 • ？？？ • 不利な手順の削除・置換 • 有利な手順の強化・拡張 • 代表例：角換わり水匠定跡

知識蒸留

知識蒸留 (1) • 知識蒸留（Knowledge Distillation） • 教師モデルの知識を生徒モデルに伝達する手法 • 将棋 AI における適用： Response-based Knowledge に基づくオフライン知識蒸留

知識蒸留 (2) • (過去) 知識蒸留を用いない強化学習による評価関数の 学習フロー 1. CPUエンジン同士の自己対局による学習データの生成 • 局面・評価値・勝敗を含む学習サンプル 2. NNUE 評価関数の学習

知識蒸留 (3) • 知識蒸留による評価関数の学習フロー 1. CPUエンジン同士の自己対局による学習データの生成 • 局面・評価値・勝敗を含む学習サンプル 2. GPUエンジンの評価関数による局面の推論 • 学習局面に対する勝率の出力 3. 勝率から評価値への変換 4. 学習サンプル内の評価値の置換 • 元の評価値をGPUエンジン由来の評価値に差し替え 5. 置換後の評価値を用いた NNUE 評価関数の学習

将来展望

将棋の神様のレーティングを超える！？ • 将棋の神様のレーティングは 5000 • 「５０００てね？ コンピューターがまだ人間のプロと 同じくらいの強さだったときに、神様のレーティング だったんです。」 • (25ページ目)半年後に将棋の神様が現れるかもしれない話──最強将棋ソフト開 発者が語る“ディープラーニング勢の台頭による将棋ソフトの進化” | 文春オンラ イン https://bunshun.jp/articles/-/42974?page=25

将棋の神様のレーティングを超える！？ https://www.4gamer.net/games/999/G999905/20240824004/ 将棋AIはどのようにしてプロ棋士を凌駕したのか？ そしてこれからどこへ行くのか？［CEDEC 2024］

• https://www.4gamer.net/games/999/G999905/20240824004/

参考文献 • [1] 山岡 忠夫， 加納邦 彦．強 い将棋 ソフト の創り かた． マイナ ビ出版 ，202 1年，296 p． • [2] Silver, D., Hubert, T., Schrittwieser, J., Antonog lou, I., Lai, M., Gue z, A., Lanctot, M., Sifre, L., Kumara n, D., Gra epel, T., Lillicrap, T., Simonyan, K., and Hassabis, D. A g eneral reinfo rcement learning algo rithm tha t masters chess, shog i, and go through self-play. Science, 3 62(6419):1140–114 4, 2018. ISSN 0 036-807 5. do i: 1 0.112 6/science.aar6404. URL http://science. science mag.org/content/3 62/6 419/1140. • [3]那須 悠．“高速 に差分 計算可 能なニ ューラ ルネッ トワー ク型将 棋評価 関数” ．コ ンピュ ータ将 棋協会 ．https://www.apply.computer-shogi.org/w csc28/appeal/the_e nd_of_genesis_T.N.K.evolution_turbo_type_D/nnue.pdf ，（ 参照202 4-08-11） • [4] 伊藤 毅志， 保木邦 仁，三 宅陽一 郎．ゲ ーム情 報学概 論 - ゲー ムを切 り拓く 人工知 能．コ ロナ社 ，201 8年，234 p． • [5] “ミニ マック ス法”． Wikipedia．https://ja .wikipe dia .org /wiki/%E3%83%9F%E3%8 3%8B%E3%83%9E%E3%83%8 3%E3%82%AF%E3%82 %B9 %E6%B3%95 ，（ 参照202 4-08-12） • [6] “Minimax”．Chessprogramming wiki．https://www.chessprogramming.org/Minimax，（ 参照202 4-08-12） • [8] “アル ファ・ ベータ 法”． Wikipedia． https://ja .wikipe dia .org /wiki/%E3%82%A2%E3%83%AB%E3%83%95%E3 %82%A1%E3 %83%BB%E3%83%9 9%E3%83%BC%E3%82 %BF%E6 %B3 %95 ，（ 参照202 4-08-12） • [9] やね うらお ．“YaneuraOu”．https://github.com/ya neurao/YaneuraOu ，（ 参照202 4-08-12） • [10] 出村 洋介 ． “将棋 ソフト 「技巧 」 アピ ール文 書”． http://www 2.computer-shogi.org/w csc27/appeal/Gikou/g ikou_a ppea l_wcsc27 .pdf ，（ 参照202 5-03-16） • [11] 金澤 裕治 ． “NineDayFever”． http://www 2.computer-shogi.org/w csc27/appeal/NineDayFe ver/NDF-201 7.txt，（ 参照202 5-03-16） • [12] 瀧澤 誠． “#28 世界 コンピ ュータ 将棋選 手権(WCSC28) elmo”．https://www.apply.computer-shogi.org/w csc28/appeal/elmo/elmo_wcsc28 _r3.pdf，（ 参照202 5-03-16） • [13] 山口 祐． “WCSC29 詳細 アピー ル文書 （PAL）”． https://www.apply.computer-shogi.org/w csc29/appeal/PAL/wcsc29_PAL.pdf，（ 参照202 5-03-16） • [14] 磯崎 元洋 ． “やね うら王 WCSC30 PR文書”．https://www.apply.computer-shogi.org/w csc30/appeal/Yane ura Ou_with_Otafuku_Lab._2020/WCSC30_YANE_PR.txt，（ 参照202 5-03-16） • [15] 松下 光則 ． “チー ム Ba rrel house のア ピール 文書＠ 第 31 回世 界コン ピュー タ将棋 選手権”．https://www.apply.computer-shogi.org/w csc31/appeal/White_Beer/appeal2021.pdf，（ 参照202 5-03-16） • [16] 磯崎 元洋 ． “やね うら王 PR 文書”．https://www.apply.computer-shogi.org/w csc32/appeal/Yane ura Ou/WCSC_PR .pdf，（ 参照202 5-03-16） • [17] 磯崎 元洋 ，杉村 達也． “やね うら王 チーム WCSC33 終了 後の PR 文書”． https://www.apply.computer-shogi.org/w csc33/appeal/yaneuraou/yaneuraou_wcsc33_after.pdf，（ 参照202 5-03-16） • [18] “半年 後に将 棋の神 様が現 れるか もしれ ない話──最強 将棋ソ フト開 発者が 語る“デ ィープ ラーニ ング勢 の台頭 による 将棋ソ フトの 進化” ”． “ニコ ニコニ ュース オリ ジナル”． https://originalnews.nico/2 23718/2．（ 参照202 5-03-23） • [19] “将棋AIはど のよう にして プロ棋 士を凌 駕した のか？ そし てこれ からど こへ行 くのか ？［CEDEC 202 4］”．4Gamer.ne t． https://www.4gamer.net/ga mes/999/G99990 5/20 240824 004/． (参照202 5-03-23)

• https://www.apply.computer-shogi.org/wcsc28/appeal/the_end_of_genesis_T.N.K.evolution_turbo_type_D/nnue.pdf，（参照2024-08-11
• https://ja.wikipedia.org/wiki/ミニマックス法
• https://www.chessprogramming.org/Minimax
• https://ja.wikipedia.org/wiki/アルファ・ベータ法，（参照2024-08-12
• https://github.com/yaneurao/YaneuraOu，（参照2024-08-12
• http://www2.computer-shogi.org/wcsc27/appeal/Gikou/gikou_appeal_wcsc27.pdf，（参照2025-03-16
• http://www2.computer-shogi.org/wcsc27/appeal/NineDayFever/NDF-2017.txt
• https://www.apply.computer-shogi.org/wcsc28/appeal/elmo/elmo_wcsc28_r3.pdf
• https://www.apply.computer-shogi.org/wcsc29/appeal/PAL/wcsc29_PAL.pdf
• https://www.apply.computer-shogi.org/wcsc30/appeal/YaneuraOu_with_Otafuku_Lab._2020/WCSC30_YANE_PR.txt
• https://www.apply.computer-shogi.org/wcsc31/appeal/White_Beer/appeal2021.pdf
• https://www.apply.computer-shogi.org/wcsc32/appeal/YaneuraOu/WCSC_PR.pdf
• https://www.apply.computer-shogi.org/wcsc33/appeal/yaneuraou/yaneuraou_wcsc33_after.pdf
• https://originalnews.nico/223718/2
• https://www.4gamer.net/games/999/G999905/20240824004/

ご清聴ありがとうございました