[DL輪読会]Assessing Game Balance with AlphaZero: Exploring Alternative Rule Sets in Chess

DEEP LEARNING JP [DL Papers] Assessing Game Balance with AlphaZero: Exploring Alternative Rule Sets in Chess Shota Imai（Matsuo Lab） えるエル@ImAI_Eruel DL輪読会2020/09/25 http://deeplearning.jp/ 1

• http://deeplearning.jp/

書誌情報 ◼出典： https://arxiv.org/abs/2009.04374 ◼著者： Nenad Tomašev, Ulrich Paquet, Demis Hassabis（DeepMind）, Vladimir Kramnik（チェスの元ワールドチャンピオン）

• https://arxiv.org/abs/2009.04374

論文概要 3 ◼現代のチェスは，戦略の大半はゲームが始まる前に分析によって練られた もので占められており，引き分けも極めて多い ◼チェスは長い年月をかけてルールが少しずつ変わってきたが，妥当なルー ルの変更には人間のプレイによるゲーム性の評価が不可欠で，現行ルール のチェスを突然変えるのは不可能 ◼本論文では一部ルールを変更したチェスの改変版で学習したAlphaZero モデルの自己対戦によって，そのルールにおけるゲームバランスを評価 Shota Imai | The University of Tokyo

今日の発表について 4 ◼一応AlphaZero使っているので強化学習とか木探索の話が出てきますが， ほとんど機械学習の専門知識なしでも聞ける内容 ◼一応チェスの基本的な知識を必要とするので，序盤で解説します ◼本発表で使用する図は，論文中，または日本チェス協会や後身のNCSのも のを引用しています ◼（強化学習の基礎自体に不安があるなら拙作で恐縮ですが深層強化学習サ マースクールで使った以下の資料を勧めておきます） 強化学習の基礎と深層強化学習 https://www.slideshare.net/ShotaImai3/rlssdeepreinforcementlearning 発表の内容のほとん どがチェスの話です Shota Imai | The University of Tokyo

• https://www.slideshare.net/ShotaImai3/rlssdeepreinforcementlearning

目次 5 ◼チェスの基礎知識 ◼AlphaZeroと関連手法 ◼論文の内容 Shota Imai | The University of Tokyo

チェスの基礎知識 Shota Imai | The University of Tokyo 6

チェス入門 / 基本的なルール ◼白黒二つの陣営に分かれ，各プレイヤーが交互に自分の駒をルールに則っ て動かし，相手のキングを先にチェックメイト（どのように動いても次の 手でキングを取られる状態）した方が勝利 ◼ゲームのルール上，その後の展開でどのように動いても両者ともチェック メイトができない展開になった場合は引き分け ◼基本的な部分は将棋と似ているが後述のようにいくつか重要な違いがある Shota Imai | The University of Tokyo 7

チェス入門 / チェスの盤面と駒 ポーン ルーク ナイト ビショップ クイーン キング Shota Imai | The University of Tokyo 8

チェス入門 / チェック，チェックメイト，ステイルメイト ◼チェック - 次の一手で何らかの駒の動きで相手のキングを取れるようになっている状況（将棋 での王手） - キングにチェックをかけられた側は必ずチェックを回避するような手を打つ必要が ある ◼チェックメイト - チェックをかけられ，チェックを回避する手段がなく，どのような手を打っても次 の一手でキングが取られる状況 - 単にメイトとも ◼ステイルメイト - 自分の手番であり，チェックはされておらず，合法手が存在しないという条件を満 たした場合「ステイルメイト」となり，ゲームは引き分けになる Shota Imai | The University of Tokyo 9

チェス入門 / キング，クイーン ◼ キング - ◼ クイーン 全八方向全てに１マス動ける 将棋の王将と同じ どのような手を打ってもこのキング が取られるチェックメイトになると 負け - 左右，斜め方向の空きマスに無制限 の移動ができる ルーク+ビショップ（将棋だと飛車+ 角）の性能を持つ最強の駒 Shota Imai | The University of Tokyo 10

チェス入門 / ビショップ，ルーク ◼ ビショップ - ◼ ルーク 斜め方向の空きマスに無制限の移動 が可能 将棋の角と同じ - 上下左右方向の空きマスに無制限の 移動が可能 将棋の飛車と同じ Shota Imai | The University of Tokyo 11

チェス入門 / ナイト，ポーン ◼ ナイト - ◼ ポーン 上下左右それぞれ２マス進んだ場所 から１マス分だけ横の場所に動ける 中間にある駒は飛び越えられる 将棋の桂馬を八方向に動かせるよう にしたもの - 平時は正面１マスのみ移動できる駒 ゲーム開始地点からは2マス移動可 正面に他の駒があるときは移動でき ないが，斜め前に相手の駒があると きには取って移動できる 相手側の最上（下）段マスに到達す ればポーン以外の任意の駒に昇格 （プロモーション）する Shota Imai | The University of Tokyo 12

特殊なルール 13 ◼ キャスリング - - ◼ アンパッサン ゲーム開始から動いていないキング とルークがあり，間に他の駒がなく， チェックメイトもされていない場合 に可能な動き キングがルークの方向に2マス移動 し，ルークはキングを飛び越えて反 対側のマスに移動する この一連の動きを一手で可能 - ルークが正面に２マス動いた場合に 可能な手 相手のルークは2マス動いたルーク が本来1マス動いた時にいる位置に 向かって斜め方向に動いて，その ルークをとることができる Shota Imai | The University of Tokyo

勝敗に関連する事項 ◼50手ルール：50手連続でお互いにポーンが動かず，駒が取られることが ない場合，プレイヤーの申請により引き分けになる ◼スリーフォールド・レピティション：同じ形の曲面がゲーム中に出現する ことになる場合，プレイヤーの指摘で引き分けとなる Shota Imai | The University of Tokyo 14

その他チェスの重要用語 ◼マテリアル：駒の価値からどれくらい自軍が有利かを示す指標 ◼オープニング：ゲームの序盤．大量の定跡が存在 ◼ミドルゲーム：ゲームの中盤 ◼エンドゲーム：ゲームの後半 ◼ファイル，ランク - ファイル：チェスボードの縦列 - ランク：チェスボードの横列 Shota Imai | The University of Tokyo 15

チェスAIに関連した話題 ◼チェスにおけるAIと人間の戦いは1997年にはほぼ決着がついており， 当時の世界チャンピオンのガルリ・カスパロフがIBMのDeep Blueに敗れ ている ◼AlphaZeroは2017年当時最強のチェスAIだったStockfishと対戦して，白 番（先手）で25勝25引き分け0敗，黒番で3勝47引き分け0敗 ◼上記のように，純粋な勝敗を求めるチェスAIの研究はほとんど尽くされて いるといっていい状況（そして，理想的な対局ではチェスが引き分けとい う消極的な結果に終わりやすいことを示している） ◼今回の研究は人間との共同作業でチェスそのものの性質のあり方を考察す る新たな取り組み Shota Imai | The University of Tokyo 16

AlphaZeroと関連手法 Shota Imai | The University of Tokyo 17

囲碁の世界最強棋士に勝つ歴史的快挙を成し遂げた囲碁AI AlphaGo ◼ 2016年，DeepMindにより開発され，世界最強棋士とされるイ・セドル九段を破った ◼ 従来のモンテカルロ木探索，強化学習のアルゴリズムを使った囲碁AIのアルゴリズムに， 深層学習を巧みに組み合わせ，飛躍的に棋力が上昇 ◼ 従来のモンテカルロ木探索をベースに，盤面から勝率を出力するCNN（バリューネット ワーク），人間の棋譜で学習したCNN（SLポリシーネットワーク），そのネットワーク を元に強化学習したRLポリシーネットワークを組み合わせて探索の質を上げている Shota Imai | The University of Tokyo 18

モンテカルロ法 ◼囲碁や将棋などで，現在の局面からどの手を打つのが良いかを，ランダム シミュレーションを使って計算する手法 ◼コンピュータの計算力に任せ，合法手を選択して終局まで適当に打つシ ミュレーション（プレイアウト）を複数回繰り返す - ある手は勝率が低い（100回適当にシミュレーションしてみて20回しか勝てなかっ た） →その打ち手による遷移先があまりよくない - 別の手は勝率が高い（100回適当にシミュレーションしてみて90回勝った） →その打ち手による遷移先がよい ◼つまり，なんとなくいろんな手を複数回シミュレーションしてみて，勝率 が高い手が一番良い打ち手として採用する手法 →モンテカルロ法，原始モンテカルロ木探索 Shota Imai | The University of Tokyo 19

モンテカルロ木探索 （Monte Carlo Tree Search; MCTS） ◼原始モンテカルロ木探索では，乱数シミュレーションを行うため，現実的 には相手がミスをしなければ勝ちに繋がらないような手も選択してしまう 可能性 ◼そこで，有力な手に探索を集中させ，良さそうな手についてはゲーム木を 展開して何手も先読みするという手を使うことが考えられる →モンテカルロ木探索の成立 ◼一般的には2006年にレミ・クーロンが開発した囲碁AI「Crazy Stone」が 起源とされる AlphaGo等，後続のゲームAIはこのMCTSを ベースにしているものが多い（強化学習はあ くまでも補助） Shota Imai | The University of Tokyo 20

AlphaGoの構成要素 ◼ロールアウトポリシー - モンテカルロ木探索で高速にプレイアウトを行うために高速推論できるモデル使用 ◼SLポリシーネットワーク（Supervised Learning of Policy Network） - 人間の棋譜データによって教師あり学習，盤面を入力したときの出力手がトップ棋士と 似るようにしたCNN（畳み込みニューラルネットワーク） - 最終的にトップ棋士の打ち手とネットワークの出力手の一致率は57%に(従来は多くて約 40%) ◼バリューネットワーク - 盤面を入力とし，勝率を出力するように学習したCNN - 従来の囲碁AIにおける評価関数を深層学習の力で作り上げたと言える ◼RLポリシーネットワーク - SLポリシーネットワークを初期値として，自己対戦によって強化学習を行う - 方策学習のアルゴリズムとしてはREINFORCEを使う ◼非同期方策価値モンテカルロ木探索（APV-MCTS) - 従来のモンテカルロ木探索に加え，バリューネットワークやRLポリシーネットワークも 利用することで効率的に木探索を行う 21

人間の囲碁のデータを一切使わずAlphaGo超え AlphaGo Zero ◼ AlphaGoを改良し，人間の棋譜データをまったく使わず，囲碁でAlphaGo同等以上の 強さとなった囲碁AI ◼ 人間の知識を一切使用しないため最初の打ち方はデタラメだが，自己対戦で強化学習を 行うと，人間では想像できない手も打てるように ◼ AlphaGoの改良系との主な違いは以下 - バリューネットとポリシーネットを統合し（デュアルネットワーク），ResNet 使用 - 木探索でプレイアウトを行わず，デュアルネットの評価値のみを探索の参考にする - 自己対戦は現時点の最強モデルを相手に行ってパラメータを更新 Shota Imai | The University of Tokyo 22

囲碁，将棋，チェスの全てで頂点を極めた汎用ゲームAI AlphaZero ◼ AlphaGo Zeroをさらに改良し，チェスや将棋などのゲームにも適用可能にした ◼ 先代AlphaGo Zero，当時世界最強のチェスAIだった“Stockfish”，2017年世界コンピュー タ将棋選手権で優勝した将棋AI “elmo”に対し全て勝ち越し ◼ アルゴリズムは非常に簡潔で，AlphaGo Zeroとの違いとして， - 将棋やチェスは単なる勝敗以外の結果があるため，勝率予測ではなく期待収益予測 を行う - AlphaGo Zeroでは過去のモデルのプールから最も強いものを選択して自己対戦に 使っていたが，AlphaZeroでは単純に最新モデルのみで自己対戦を行う Shota Imai | The University of Tokyo 23

論文の内容 Shota Imai | The University of Tokyo 24

今回評価するルール ◼本論文では，右図のように ルールを変更した9つの改変 版について検討する ◼基本的にはチェスのオリジナ ルルールに忠実だが，有効な 戦略は大きく違う 例：ポーンが横にも動ける，自分の駒 を取れる，ステイルメイトが勝ちにな る等 ◼なお，これらのルール変更は この論文オリジナルのものと いうわけではない Shota Imai | The University of Tokyo 25

検討する改変版チェスの例 Shota Imai | The University of Tokyo 26

各改変版チェスの評価の流れ 1. 各ルールに対してAlphaZeroのモデルを自己対戦によって学習 2. 学習を終えたモデル同士で，各ルールで対戦させる 3. 対局中の局面の評価値，勝敗の分布，出現した戦略をもとに，各ルール の性質の評価を行う Shota Imai | The University of Tokyo 27

AlphaZeroモデルの学習 ◼各ルールで，AlphaZeroのモデルを自己対戦によって学習 ◼各モデルのハイパーパラメータは同じものを使い，バッチサイズは4096， 学習のステップ数は100万，1手に選択に伴うMCTSのシミュレーションは 800回 ◼学習時には探索の多様性を出すため，以下の工夫を行う - モデルが出力する打ち手の確率にノイズを与える - 各対局の最初の30手はMCTSの訪問回数に基づいたソフトマックス出力によって確率 的に選択し，残りは訪問回数トップの手を決定論的に選ぶ Shota Imai | The University of Tokyo 28

各ルールの評価 ◼学習済みモデルを用いて，それぞれのルールについて学習を行う ◼本論文では特に以下の要素に注目する - 対局のドロー率 初手（白番）のアドバンテージ 各ルールが様々なオープニングの勝敗に与える影響 追加されたルールで可能になった打ち手の有用性 ゲームの多様性 変更されたルールによる駒の推定価値の変動 各ルールのチェスの定性評価（by 世界チャンピオン） ◼評価する自己対戦のセットとして，1手の推論時間が1秒のものを10000 セット，1分のものを1000セット用意 ◼チェスの場合，探索が一定以上深くなると，大体固定された手を打つよう になってしまうので，評価時にも最初の20手は出力のソフトマックスを とって確率的に選択 Shota Imai | The University of Tokyo 29

自己対戦による評価の結果 ◼左は1手1秒，右は1手１分の自己対戦の結果 ◼ほとんど引き分けになるが，ルール変更によってある程度分布に変化が生 じている Shota Imai | The University of Tokyo 30

改変版チェスの分析 / ドロー率の計算 ◼オリジナルのチェスは理想的な展開になった場合，引き分けになるであろ うとの仮説があり，実際，現代のチェスは引き分けがかなり多い ◼各ルールについて，対局結果から，相対的にどの程度引き分けになりやす いか計算 ◼下図は行のルールに対して列のルールの方がどれくらいドローしやすいか =決着のつきにくさを示している ◼Torpedoが一番決着しやすい Shota Imai | The University of Tokyo 左：対局数1000 右：対局数10000 31

改変版チェスの分析 / 白番（先行）の有利さ ◼各ルール，白番（先行）の場合にどれだけ有利か（勝ち，または少なくと も引き分けに持ち込めるか）を対局結果から計算して相対的に比較 ◼下図は列のルールに対して行のルールの方がどれだけ白にとって有利かを 示している ◼Torpedoが一番白にアドバンテージがある =決着がつきやすいゲームルールは先行有利になりやすい Shota Imai | The University of Tokyo 左：対局数1000 右：対局数10000 32

改変版チェスの分析 各ルールの様々なオープニングが勝敗に与える影響 ◼各ルールで，一般的なオープニングの展開になった場合，勝敗にどれだけ 影響があるか（先手がどれだけ勝ちやすくなるか）を分析 ◼ここでは，ダッチ・ディフェンス，チゴリン・ディフェンス，アレヒン・ ディフェンス，キングズ・ギャンビットについて分析 ◼大体のルール変更では，ある程度の影響はあるものの極端に勝敗に影響す ることはないが，一部（Pawn sidewaysにおけるチゴリン・ディフェン ス）などは極端に先行有利となる Shota Imai | The University of Tokyo 33

改変版チェスの分析 / ルール変更で追加された手の使用について 各ルールで追加された新たなチェスの駒の動きを，AlphaZeroがどれだけ好 んで使用するか=どれだけ有効な打ち手になりうるかを分析 ◼Torpedo moves - Semi-torpedoでは88%の対局がtorpedoを使用 - torpedoルールでは94%の対局がtorpedoを使用 - プロモーションが早くなるので，当然といえば当然の結果 ◼ポーンの後方移動と横移動 - Pawn-back chessでは96.3%の対局が後方移動を使用 - Pawn-sideways chessでは99.6%の対局が横移動を使用 - 特に横移動は，ゲーム内の全ての打ち手の11.6%を占めた ◼自軍の駒を取る - 52.5%の対局で自軍の駒を取る打ち手が発生した - 86.9%は自軍のポーンを取る動き（大きな移動ができる駒の進路を空けている） Shota Imai | The University of Tokyo 34

改変版チェスの分析 /ゲームの多様性 35 ◼各ゲームの序盤について，AlphaZeroが出力する現在の状態からの移動確 率からエントロピーHを計算して，どの程度打ち手に多様性があるかみる ◼エントロピーが0に近ければ，最前手がほとんど1つに絞られて，固定化さ れた打ち手の選択肢しかない=多様性が低いことを示しており，エントロ ピーが高ければ，様々な打ち手の候補が存在し多様性が高い TorpedoやNo-castlingのように決着がつき やすいゲームは，多様性が低い =決着のつきやすさと多様性のトレードオフ Shota Imai | The University of Tokyo

改変版チェスの分析 /マテリアル ◼ポーンの価値を1とした場合の各 駒の価値が各ルールでどのように なるか分析 ◼各駒の相手の個数との差分をとっ た特徴ベクトルに重みをかける評 価関数を作成し，重みの大きさか ら駒の重要度を算出 - 特徴ベクトル - 評価関数 - 損失関数 （z:実際の勝敗） Shota Imai | The University of Tokyo 36

改変版チェスの分析 /定性評価 ◼チェスのグランドマスターが各ルールの棋譜から打ち手の主観的評価を行 う ◼人間のプレイヤーの経験に基づく美的感覚，プレーして面白さを感じるか どうか，人間のプレーと比べた場合に展開がどの程度違ったものになるか をみている Shota Imai | The University of Tokyo 37

定性評価 1/2 38 ◼ No Castling chess - キングを守るための複雑性が増し，守りよりも攻撃的になりがち - なかなか面白いルール ◼ No Castling（10） - あまり魅力がないルール - 結局どれだけキャスリングが制限されてもキャスリング自体が極力な手であるため，キャスリング をする固定化された戦略になりがち ◼ Pawn one square chess - ポーンの動きが遅いので，ゲーム展開も非常にゆっくりしたものになる - ゆっくりとゲームを楽しみたい人向け ◼ Stalemate=win chess - 高レベルプレイヤー同士のゲームでは，ステイルメイトが引き分けの決定打にはあまりならない - よってこのルール変更が与える影響は小さく微妙 ◼ Torpedo, Semi-torpedo chess - ダイナミックで攻撃的なチェスになる - 各局面で従来のチェスにはない選択肢が生まれやすい（が，その選択肢が最重要で多様性は小さ い） Shota Imai | The University of Tokyo

定性評価 2/2 39 ◼Pawn-back chess - ポーンを後方に移動させるのは，どちらかというと弱い場所の補強に使うと思いそ うだが，実際には後方に下がって攻撃の進路を開けたりと意外と攻撃的 - AlphaZeroがある一部のオープニングを強く好むようになった ◼Pawn-sideways chess - かなり複雑なプレイが要求されるようになり，従来のチェスに慣れている人にとっ ては難しい - 従来のチェスではあり得ない戦術が多い ◼Self-capture chess - 一番美的で面白いルール - ゲームのあらゆる局面で自分の駒を取ることことが選択肢に入り，様々な戦略を考 えることができる Shota Imai | The University of Tokyo

まとめ 40 ◼人の棋譜を使わず最強クラスのプレイヤーを超える強さになるAlphaZero を工夫して使うことで，ゲームルールを改変した場合にも機械的にルール の性質評価を行うことができた ◼特にTorpedo chess, Semi-torpedo chess, No-castling chess Stalemate=winのルールは現在のチェスよりも勝敗が決しやすい（が同時 に正確なプレーが要求され，特に序盤は展開が固定化されやすい） ◼今回はゲーム戦略の発展が行き詰まりがちだったチェスのみの評価だった が，将棋や囲碁，その他のゲームでも同様にゲームルールの変更，妥当性 の評価，バランス調整を行える可能性がある Shota Imai | The University of Tokyo