初心者のための 組み合わせゲームに関する アルゴリズム入門

初⼼者のための 組み合わせゲームに関する アルゴリズム⼊⾨

このスライドの想定読者 • 組み合わせゲームについて⼊⾨したい⼈ • min-max法について知らない⼈ • Nim(不偏ゲーム)の必勝法を知りたい⼈ • それぞれの⽅法について実際の問題を解く実装をしたい⼈ • dpの基本がわかる⼈（必須ではありませんが具体例の解法で使います）

今⽇のテーマ 組み合わせゲームに関するアルゴリズム • min-max 法 • Nim

組み合わせゲームとは 以下の2つの性質を持つ２⼈で⾏うゲーム • 完全情報…全ての情報が両⽅のプレイヤーに公開されている ×ポーカーは相⼿の⼿札が隠されている ×じゃんけんは相⼿が何を出すのかわからない

組み合わせゲームとは 以下の2つの性質を持つ２⼈で⾏うゲーム • 完全情報…全ての情報が両⽅のプレイヤーに公開されている ×ポーカーは相⼿の⼿札が隠されている ×じゃんけんは相⼿が何を出すのかわからない • 確定…サイコロのような偶然の要素がない ×すごろく、ポーカー ○じゃんけんは⾃由に⼿を出せる

組み合わせゲームとは 以下の2つの性質を持つ２⼈で⾏うゲーム • 完全情報…全ての情報が両⽅のプレイヤーに公開されている ×ポーカーは相⼿の⼿札が隠されている ×じゃんけんは相⼿が何を出すのかわからない • 確定…サイコロのような偶然の要素がない ×すごろく、ポーカー ○じゃんけんは⾃由に⼿を出せる →将棋やオセロ、三⽬並べ、Nim, etc

組み合わせゲームの基本定理 「双⽅の対局者が最善の⼿を打ち続けた場合、 どちらが勝つかはあらかじめ決まっている」

組み合わせゲームの基本定理 「双⽅の対局者が最善の⼿を打ち続けた場合、 どちらが勝つかはあらかじめ決まっている」 • 五⽬並べは先⼿必勝 • どうぶつしょうぎは後⼿必勝 • 将棋も原理的にはどちらかが必勝であるはず

組み合わせゲームの基本定理 「双⽅の対局者が最善の⼿を打ち続けた場合、 どちらが勝つかはあらかじめ決まっている」 • 五⽬並べは先⼿必勝 • どうぶつしょうぎは後⼿必勝 • 将棋も原理的にはどちらかが必勝であるはず →どちらが必勝なのか、どのような⼿を選択すれば よいのかを知るアルゴリズムはあるのか？

⼆⼈零和有限確定完全情報ゲーム 今回扱うのは組み合わせゲームの中でも ⼆⼈零和有限確定完全情報ゲームとよばれるもの

⼆⼈零和有限確定完全情報ゲーム 今回扱うのは組み合わせゲームの中でも ⼆⼈零和有限確定完全情報ゲームとよばれるもの • 零和…⽚⽅が有利になった分もう⼀⽅は不利になる • 有限…有限回の⼿番でゲームが終わる

⼆⼈零和有限確定完全情報ゲーム 今回扱うのは組み合わせゲームの中でも ⼆⼈零和有限確定完全情報ゲームとよばれるもの • 零和…⽚⽅が有利になった分もう⼀⽅は不利になる • 有限…有限回の⼿番でゲームが終わる 囲碁、将棋、チェスなど⼈⼯知能の分野でよく研究されている

まずは単純なゲームから https://atcoder.jp/contests/dp/tasks/dp_l

• https://atcoder.jp/contests/dp/tasks/dp_l

まずは単純なゲームから https://atcoder.jp/contests/dp/tasks/dp_l

• https://atcoder.jp/contests/dp/tasks/dp_l

数列（1, 2, 9, 3 ）が与えられたとき • 先⼿の第⼀⼿は 1 か 3 どちらを選ぶのが最善⼿か？

数列（1, 2, 9, 3 ）が与えられたとき • 先⼿の第⼀⼿は 1 か 3 どちらを選ぶのが最善⼿か？ • よりスコアの⾼い3を選ぶべき？

数列（1, 2, 9, 3 ）が与えられたとき • 先⼿の第⼀⼿は 1 か 3 どちらを選ぶのが最善⼿か？ • よりスコアの⾼い3を選ぶべき？ • ⾃分の得点を X、相⼿の得点をYとすると ⾃分はZ=X-Yを最⼤にしたい 相⼿はZを最⼩にしたい

起きうる全局⾯を書き出してみる (1,2,9,3) Z=0 ○を⾃分の⼿番、□を相⼿の⼿番として ⾃分が先⼿の時を考える

起きうる全局⾯を書き出してみる ○を⾃分の⼿番、□を相⼿の⼿番として ⾃分が先⼿の時を考える (1,2,9,3) 1を選んだ時 3を選んだ時 Z=0 (2,9,3) (1,2,9) Z=1 Z=3

起きうる全局⾯を書き出してみる ○を⾃分の⼿番、□を相⼿の⼿番として ⾃分が先⼿の時を考える (1,2,9,3) 1を選んだ時 3を選んだ時 Z=0 (2,9,3) (1,2,9) Z=1 Z=3 相⼿が9を選んだ時 (9,3) １ (2,9) １ (2,9) １ (1,2) １

起きうる全局⾯を書き出してみる ○を⾃分の⼿番、□を相⼿の⼿番として ⾃分が先⼿の時を考える (1,2,9,3) 1を選んだ時 3を選んだ時 Z=0 (2,9,3) (1,2,9) Z=1 Z=3 相⼿が9を選んだ時 (9,3) １ (2,9) １ (2,9) １ (1,2) １ Z=3-9 =-6

起きうる全局⾯を書き出してみる ○を⾃分の⼿番、□を相⼿の⼿番として ⾃分が先⼿の時を考える (1,2,9,3) 1を選んだ時 3を選んだ時 Z=0 (2,9,3) (1,2,9) Z=1 Z=3 相⼿が9を選んだ時 (9,3) １ (2,9) １ (2,9) １ Z=3-1= 2 (1,2) １ Z=3-9 =-6

起きうる全局⾯を書き出してみる ○を⾃分の⼿番、□を相⼿の⼿番として ⾃分が先⼿の時を考える (1,2,9,3) 1を選んだ時 3を選んだ時 Z=0 (2,9,3) (1,2,9) Z=1 Z=3 相⼿が9を選んだ時 (9,3) １ (2,9) １ (2,9) １ (1,2) １ Z=-1 Z=-2 Z=2 Z=-6

起きうる全局⾯を書き出してみる ○を⾃分の⼿番、□を相⼿の⼿番として ⾃分が先⼿の時を考える (1,2,9,3) 1を選んだ時 3を選んだ時 Z=0 (2,9,3) (1,2,9) Z=1 Z=3 相⼿が9を選んだ時 (9,3) １ (2,9) １ (2,9) １ (1,2) １ Z=-1 Z=-2 Z=2 Z=-6 2を選んだ時

起きうる全局⾯を書き出してみる ○を⾃分の⼿番、□を相⼿の⼿番として ⾃分が先⼿の時を考える (1,2,9,3) 1を選んだ時 3を選んだ時 Z=0 (2,9,3) (1,2,9) Z=1 Z=3 相⼿が9を選んだ時 (9,3) １ (2,9) １ (2,9) １ (1,2) １ Z=-1 Z=-2 Z=2 Z=-6 2を選んだ時 Z=-6+2-1 =-5

起きうる全局⾯を書き出してみる ○を⾃分の⼿番、□を相⼿の⼿番として ⾃分が先⼿の時を考える (1,2,9,3) 1を選んだ時 3を選んだ時 Z=0 (2,9,3) (1,2,9) Z=1 Z=3 相⼿が9を選んだ時 (9,3) １ (2,9) １ (2,9) １ (1,2) １ Z=-1 Z=-2 Z=2 Z=-6 2を選んだ時 Z=-6+1-2 =-7 Z=-6+2-1 =-5

起きうる全局⾯を書き出してみる ○を⾃分の⼿番、□を相⼿の⼿番として ⾃分が先⼿の時を考える (1,2,9,3) 3を選んだ時 1を選んだ時 Z=0 (2,9,3) (1,2,9) Z=1 Z=3 相⼿が9を選んだ時 (9,3) １ (2,9) １ (2,9) １ (1,2) １ Z=-1 Z=-2 Z=2 Z=-6 2を選んだ時 5 -7 -9 5 -5 9 -7 -5

min-max法 • 想定される最⼤の不利益が最⼩になるように選択を⾏う⽅法 • 相⼿が⾃分にとって最も不利になるような⼿を打ってくると仮 定して、最善の⼿を探す

min-max法 ・⾃分の局⾯では⾃分が 有利になるように選択する A B C １ D 5 -7 -9 １ G １ F １ E 5 -5 9 -7 -5

min-max法 ・⾃分の局⾯では⾃分が 有利になるように選択する A B C １ D 5 -9 １ G １ F １ E -7 ・局⾯Gは⾃分の⼿番 ・選択肢は2つで、最終スコアZは -7か-5のどちらか 5 -5 9 -7 -5

min-max法 ・⾃分の局⾯では⾃分が 有利になるように選択する A B C １ D 5 -9 5 -5 ・右側を選んで-5になる １ G １ F １ E -7 ・局⾯Gは⾃分の⼿番 ・選択肢は2つで、最終スコアZは -7か-5のどちらか 9 -7 -5

min-max法 ・⾃分の局⾯では⾃分が 有利になるように選択する A B C １ D 5 -9 5 -5 ・右側を選んで-5になる →局⾯Gにくると-5で確定 １ G:-5 １ F １ E -7 ・局⾯Gは⾃分の⼿番 ・選択肢は2つで、最終スコアZは -7か-5のどちらか 9 -7 -5

min-max法 ・⾃分の局⾯では⾃分が 有利になるように選択する A B C １ D:5 5 -9 5 -5 ・右側を選んで-5になる →局⾯Gにくると-5で確定 １ G:-5 １ F:9 １ E:5 -7 ・局⾯Gは⾃分の⼿番 ・選択肢は2つで、最終スコアZは -7か-5のどちらか 9 -7 -5 同様に、⾃分の局⾯D,E,Fでは 次に選べる局⾯のうち⼤きいスコアを選ぶ

min-max法 ・相⼿の局⾯では相⼿が 有利になるように選択する A B C １ D:5 5 -7 -9 １ G:-5 １ F:9 １ E:5 5 -5 9 -7 -5

min-max法 ・相⼿の局⾯では相⼿が 有利になるように選択する A B C １ D:5 5 -9 １ G:-5 １ F:9 １ E:5 -7 ・局⾯Cは相⼿の⼿番 ・選択肢は2つで、最終スコアZは 9か-5のどちらか 5 -5 9 -7 -5

min-max法 ・相⼿の局⾯では相⼿が 有利になるように選択する A B C １ D:5 5 -9 １ G:-5 １ F:9 １ E:5 -7 ・局⾯Cは相⼿の⼿番 ・選択肢は2つで、最終スコアZは 9か-5のどちらか 5 -5 9 -7 ・相⼿がGを選んで-5になる -5

min-max法 ・相⼿の局⾯では相⼿が 有利になるように選択する A B C:-5 １ D:5 5 -9 １ G:-5 １ F:9 １ E:5 -7 ・局⾯Cは相⼿の⼿番 ・選択肢は2つで、最終スコアZは 9か-5のどちらか 5 -5 9 -7 ・相⼿がGを選んで-5になる →局⾯Cにくると-5で確定 -5

min-max法 ・相⼿の局⾯では相⼿が 有利になるように選択する A B:5 １ D:5 5 C:-5 -9 １ G:-5 １ F:9 １ E:5 -7 ・局⾯Cは相⼿の⼿番 ・選択肢は2つで、最終スコアZは 9か-5のどちらか 5 -5 9 -7 ・相⼿がGを選んで-5になる →局⾯Cにくると-5で確定 -5 局⾯はどちらを選んでも同じで 最終スコアは5で確定する

min-max法 A B:5 １ D:5 5 C:-5 -9 １ G:-5 １ F:9 １ E:5 -7 ・局⾯Aは⾃分の⼿番 ・選択肢は2つで、最終スコアZは 5か-5のどちらか 5 -5 9 -7 -5

min-max法 A:5 B:5 １ D:5 5 C:-5 -9 5 -5 ・局⾯Bを選んで5になる →局⾯Aの時点で5で確定 １ G:-5 １ F:9 １ E:5 -7 ・局⾯Aは⾃分の⼿番 ・選択肢は2つで、最終スコアZは 5か-5のどちらか 9 -7 -5

min-max法 min-max法にのっとって ⾃分も相⼿も最善⼿を選び続ける と仮定すれば、最初の時点で 最終スコアとそれに⾄る局⾯ が決まっていることになる A:5 B:5 １ D:5 C:-5 -7 -9 １ G:-5 １ F:9 １ E:5 -5 9 -7 -5

※なお、実際には最終スコアZが分からなくても どちらがどのくらい有利かさえ判断つければ良い (1,2,9,3) Z=0 (2,9,3) (1,2,9) Z=1 Z=3 (9,3) １ (2,9) １ (2,9) １ (1,2) １ Z=-1 Z=-2 Z=2 Z=-6 2を選んだ時 5 -7 -9 5 -5 9 -7 -5

※なお、実際には最終スコアZが分からなくても どちらがどのくらい有利かさえ判断つければ良い すなわち、局⾯Gのとき… (1,2,9,3) Z=0 (2,9,3) (1,2,9) Z=1 Z=3 (9,3) １ (2,9) １ (2,9) １ (1,2) １ Z=-1 Z=-2 Z=2 Z=-6 2を選んだ時 5 -7 -9 5 -5 9 -7 -5

※なお、実際には最終スコアZが分からなくても どちらがどのくらい有利かさえ判断つければ良い すなわち、局⾯Gのとき… (1,2,9,3) ・⾃分が2を選ぶと相⼿が１を選び、 Z=(Gまでのスコア)+2-1 Z=0 (2,9,3) (1,2,9) Z=1 Z=3 (9,3) １ (2,9) １ (2,9) １ (1,2) １ Z=-1 Z=-2 Z=2 Z=-6 2を選んだ時 5 -7 -9 5 -5 9 -7 -5

※なお、実際には最終スコアZが分からなくても どちらがどのくらい有利かさえ判断つければ良い すなわち、局⾯Gのとき… (1,2,9,3) ・⾃分が2を選ぶと相⼿が１を選 び、 Z=(Gまでのスコア)+2-1 Z=0 (2,9,3) (1,2,9) Z=1 Z=3 (9,3) １ (2,9) １ (2,9) １ (1,2) １ Z=-1 Z=-2 Z=2 Z=-6 ・⼀⽅で⾃分が1を選ぶと Z=(Gまでのスコア)+1-2 2を選んだ時 5 -7 -9 5 -5 9 -7 -5

※なお、実際には最終スコアZが分からなくても どちらがどのくらい有利かさえ判断つければ良い すなわち、局⾯Gのとき… (1,2,9,3) ・⾃分が2を選ぶと相⼿が１を選 び、 Z=(Gまでのスコア)+2-1 Z=0 (2,9,3) (1,2,9) Z=1 Z=3 (9,3) １ (2,9) １ (2,9) １ (1,2) １ Z=-1 Z=-2 Z=2 Z=-6 ・⼀⽅で⾃分が1を選ぶと Z=(Gまでのスコア)+1-2 2を選んだ時 5 -7 -9 5 -5 9 -7 -5 2を選んだ⽅が ⾃分にとって有利

実装例 # ⼊⼒の受け取り N=int(input()) a=list(map(int, input().split())) # a[i]からa[j]までの数列が残ってるような局⾯において、 # それ以降に加算されるスコアZの最⼤値をscore [i][j] に格納 score=[[0]*(N) for _ in range(N)]

実装例 # scoreの初期化 # a[i]だけが残ってる最終局⾯においてそれ以降にZに加算さ # れるスコアは＋a[i]または−a[i] # 与えられた数列の⻑さが偶数のとき最後に数字を取るのは相⼿ hugou=1 if (N%2==0): hugou=-1 for i in range(N): score[i][i]=hugou*a[i]

実装例 for len in range(1,N): #len+1が, 残っている数字の個数 for i in range(N-len): j=i+len if((N-(len+1))%2==0): #⾃分の⼿番のとき score[i][j]を計算 else: #相⼿の⼿番のとき score[i][j]を計算 print(score[0][N-1])

実装例 #score[i][j]を計算 #⾃分の⼿番のとき score[i][j] =max(左端の数値+それ以降に加算されるスコア、 右端の数値+それ以降に加算されるスコア) =max(a[i]+score[i+1][j], a[j]+score[i][j-1])

実装例 #score[i][j]を計算 #相⼿の⼿番のとき score[i][j] =min(-左端の数値+それ以降に加算されるスコア、 -右端の数値+それ以降に加算されるスコア) =min(-a[i]+score[i+1][j], -a[j]+score[i][j-1])

計算量 • score[i][j]を全通り計算している →数列の⻑さがNのとき NC2 =O(N2) ⼀般的なゲームでは選択肢は2つとは 限らないため、計算量はさらに増⼤する 選択肢がm個ありn回の操作でゲームが終わる場合、O(mn)

• • α-β法 ○が⾃分の⼿番、□が相⼿の⼿番 スコアの⾼い⽅が⾃分に有利 A: ? B:? １ C:5 D:5 I:? E:-7 G:9 １ M:? １ J:? １ F:? H:? K:? L:? N:? O:?

• • • α-β法 ○が⾃分の⼿番、□が相⼿の⼿番 スコアの⾼い⽅が⾃分に有利 図のように局⾯C,D,E,G におけるスコア が分かっている時 A: ? B:? １ C:5 D:5 I:? E:-7 G:9 １ M:? １ J:? １ F:? H:? K:? L:? N:? O:?

• • • α-β法 ○が⾃分の⼿番、□が相⼿の⼿番 スコアの⾼い⽅が⾃分に有利 図のように局⾯C,D,E,G におけるスコア が分かっている時 A: ? Hを調べる必要はない! B:? １ C:5 D:5 I:? E:-7 G:9 １ M:? １ J:? １ F:? H:? K:? L:? N:? O:?

• • • α-β法 ○が⾃分の⼿番、□が相⼿の⼿番 スコアの⾼い⽅が⾃分に有利 図のように局⾯C,D,E,G におけるスコア が分かっている時 A: ? Hを調べる必要はない! B:? １ C:5 D:5 I:? １ F>9 E:-7 なぜなら… • Gが9の時点でFは9以上が確定 G:9 H:? １ M:? １ J:? K:? L:? N:? O:?

• • • α-β法 ○が⾃分の⼿番、□が相⼿の⼿番 スコアの⾼い⽅が⾃分に有利 図のように局⾯C,D,E,G におけるスコア が分かっている時 A: ? Hを調べる必要はない! B:? １ C:5 D:5 I:? １ F>9 E:-7 なぜなら… • Gが9の時点でFは9以上が確定 • Cは５なので,相⼿⼿番の局⾯Bにおいて 局⾯Fは選ばれない G:9 H:? １ M:? １ J:? K:? L:? N:? O:?

• • • α-β法 ○が⾃分の⼿番、□が相⼿の⼿番 スコアの⾼い⽅が⾃分に有利 図のように局⾯C,D,E,G におけるスコア が分かっている時 A: ? Hを調べる必要はない! B:5 １ C:5 D:5 I:? １ F>9 E:-7 なぜなら… • Gが9の時点でFは9以上が確定 • Cは５なので,相⼿⼿番の局⾯Bにおいて 局⾯Fは選ばれない G:9 H:? １ M:? １ J:? K:? L:? N:? →局⾯Bにおいて 5であることが確定! O:?

• • • α-β法 ○が⾃分の⼿番、□が相⼿の⼿番 スコアの⾼い⽅が⾃分に有利 さらに局⾯J,K,Lを調べて図のようになった場合 A: ? B:5 １ C:5 D:5 I:? １ F>9 E:-7 G:9 H:? １ M:? １ J:3 K:3 L:1 N:? O:?

• • • α-β法 ○が⾃分の⼿番、□が相⼿の⼿番 スコアの⾼い⽅が⾃分に有利 さらに局⾯J,K,Lを調べて図のようになった場合 A: ? M,N,Oを調べる必要はない! B:5 １ C:5 D:5 I:? １ F>9 E:-7 G:9 H:? １ M:? １ J:3 K:3 L:1 N:? O:?

• • • α-β法 ○が⾃分の⼿番、□が相⼿の⼿番 スコアの⾼い⽅が⾃分に有利 さらに局⾯J,K,Lを調べて図のようになった場合 A: ? M,N,Oを調べる必要はない! B:5 １ C:5 D:5 I:? １ F>9 E:-7 なぜなら… • Jが3の時点でIは3以下が確定 G:9 H:? １ M:? １ J:3 K:3 L:1 N:? O:?

• • • α-β法 ○が⾃分の⼿番、□が相⼿の⼿番 スコアの⾼い⽅が⾃分に有利 さらに局⾯J,K,Lを調べて図のようになった場合 A: ? M,N,Oを調べる必要はない! B:5 １ C:5 D:5 I:? １ F>9 E:-7 なぜなら… • Jが3の時点でIは3以下が確定 • Bは５なので,⾃分⼿番の局⾯Aにおいて 局⾯Iは選ばれない G:9 H:? １ M:? １ J:3 K:3 L:1 N:? O:?

• • • α-β法 ○が⾃分の⼿番、□が相⼿の⼿番 スコアの⾼い⽅が⾃分に有利 さらに局⾯J,K,Lを調べて図のようになった場合 A: ? M,N,Oを調べる必要はない! B:5 １ C:5 D:5 I:? １ F>9 E:-7 なぜなら… • Jが3の時点でIは3以下が確定 • Bは５なので,⾃分⼿番の局⾯Aにおいて 局⾯Iは選ばれない G:9 H:? １ M:? １ J:3 K:3 L:1 N:? →局⾯Aにおいて 5であることが確定! O:?

α-β法 • 途中で探索を打ち切ることができるので、 min-max法より効率的に探索ができる

補⾜ 1. さらなる効率化の⼯夫として、反復深化法やscout法がある 2. 将棋のようなゲームだと、Zのようなスコアが無い →盤⾯の有利不利度合いを⽰す評価値をつかう ※評価値は駒の数や配置などから計算する

不偏ゲーム

不偏ゲーム ⼆⼈零和有限確定完全情報ゲームのうち、 すべての局⾯において、 「どちらの⼿番でも打てる⼿の候補が変わらない」ようなゲーム

不偏ゲーム ⼆⼈零和有限確定完全情報ゲームのうち、 すべての局⾯において、 「どちらの⼿番でも打てる⼿の候補が変わらない」ようなゲーム • 将棋やオセロは⾃分と相⼿の打てる場所が違うため当てはまらない

不偏ゲーム ⼆⼈零和有限確定完全情報ゲームのうち、 すべての局⾯において、 「どちらの⼿番でも打てる⼿の候補が変わらない」ようなゲーム • 将棋やオセロは⾃分と相⼿の打てる場所が違うため当てはまらない ♦勝敗の決め⽅ 先に打てる⼿がなくなったほうの負け（もしくは勝ち）

Nim 代表的な不偏ゲーム 、Nim

Nim 代表的な不偏ゲーム 、Nim ルール ①コインの⼭が複数ある

Nim 代表的な不偏ゲーム 、Nim ルール ①コインの⼭が複数ある ②⼭を⼀つ選び、その中から1枚以上コインを⾃由に取る

Nim 代表的な不偏ゲーム 、Nim ルール ①コインの⼭が複数ある ②⼭を⼀つ選び、その中から1枚以上コインを⾃由に取る ③コインを交互に取っていき、 先にコインが取れなくなったほうの負け （即ち最後の⼀枚を取ったほうの勝ち）

「このゲームには、必勝法がある」 • コインの初期状態（⼭の数とコインの枚数）が分かれば、 先⼿と後⼿のどちらが必勝か、どうコインを取っていけば良い のかが分かる

「このゲームには、必勝法がある」 • コインの初期状態（⼭の数とコインの枚数）が分かれば、 先⼿と後⼿のどちらが必勝か、どうコインを取っていけば良い のかが分かる 例えば次のような初期条件ではどちらが必勝だろうか？ • ⼭が⼀つだけのとき • コインが1枚ずつ2⼭のとき

「このゲームには、必勝法がある」 • コインの初期状態（⼭の数とコインの枚数）が分かれば、 先⼿と後⼿のどちらが必勝か、どうコインを取っていけば良い のかが分かる 例えば次のような初期条件ではどちらが必勝だろうか？ • ⼭が⼀つだけのとき→先⼿必勝 ⼀気に全部取り切ってしまえば良い • コインが1枚ずつ2⼭のとき

「このゲームには、必勝法がある」 • コインの初期状態（⼭の数とコインの枚数）が分かれば、 先⼿と後⼿のどちらが必勝か、どうコインを取っていけば良い のかが分かる 例えば次のような初期条件ではどちらが必勝だろうか？ • ⼭が⼀つだけのとき→先⼿必勝 ⼀気に全部取り切ってしまえば良い • コインが1枚ずつ2⼭のとき→後⼿必勝 「プレーヤーは必ず1つの⼭を選び 1枚以上取らなければならない」

「このゲームには、必勝法がある」 • ⼭が2つでコインの枚数が同じ • ⼭が2つでコインの枚数が異なるとき

「このゲームには、必勝法がある」 • ⼭が2つでコインの枚数が同じ→後⼿必勝 後⼿は先⼿が取ったコインの枚数と同じ数をもう⼀⽅の⼭から取って 「⼭が2つでコインの枚数が同じ」状態に戻して相⼿に返し続ければ良い • ⼭が2つでコインの枚数が異なるとき

「このゲームには、必勝法がある」 • ⼭が2つでコインの枚数が同じ→後⼿必勝 後⼿は先⼿が取ったコインの枚数と同じ数をもう⼀⽅の⼭から取って 「⼭が2つでコインの枚数が同じ」状態に戻して相⼿に返し続ければ良い • ⼭が2つでコインの枚数が異なるとき→先⼿必勝 先⼿はコインが多い⽅の⼭から取って 「⼭が2つでコインの枚数が同じ」状態にすれば、 あとは上の状況と同じ

「このゲームには、必勝法がある」 • ⼭が2つのとき、すべての局⾯は2種類に分けられる 2つの⼭のコインの数が「同じ」or「異なる」

「このゲームには、必勝法がある」 • ⼭が2つのとき、すべての局⾯は2種類に分けられる 2つの⼭のコインの数が「同じ」or「異なる」 • 「同じ」局⾯の場合、次の局⾯は必ず「異なる」 ⽚⽅の⼭からしかコインが取れないから

「このゲームには、必勝法がある」 • ⼭が2つのとき、すべての局⾯は2種類に分けられる 2つの⼭のコインの数が「同じ」or「異なる」 • 「同じ」局⾯の場合、次の局⾯は必ず「異なる」 ⽚⽅の⼭からしかコインが取れないから • ゲームが進⾏すると、 必ずどちらかの⼭のコインが尽きて⼭が⼀つになる →この局⾯において全てのコインを取りきってしまえば勝ち

「このゲームには、必勝法がある」 ⼭が2つのときの必勝法 「2つの⼭のコインの数が同じ」という局⾯を 相⼿に押し付け続ける

「このゲームには、必勝法がある」 ⼭が2つのときの必勝法 「2つの⼭のコインの数が同じ」という局⾯を 相⼿に押し付け続ける • ⾃分には「 2つの⼭のコインの数が異なる」局⾯しか回ってこない • いずれ⼭が⼀つの局⾯がくるので、全て取れば勝ち

「このゲームには、必勝法がある」 • 「2つの⼭のコインの数が異なる」局⾯にいるプレーヤーは、 ミスをしなければ必ず勝てる • 「2つの⼭のコインの数が同じ」局⾯にいるプレーヤーは、 相⼿がミスをしてくれないと、必ず負ける

⼭が3つ以上あるときは??

⼭が3つ以上あるときは?? • これまでと同じ⽅法は通⽤しない

⼭が3つ以上あるときは?? • これまでと同じ⽅法は通⽤しない • しかし考え⽅は同じ

⼭が3つ以上あるときは?? • これまでと同じ⽅法は通⽤しない • しかし考え⽅は同じ • 全ての局⾯を 「必ず勝てる局⾯」と「必ず負ける局⾯」に分けたい

結論（理屈はあと） 1. N個の⼭のコインの枚数をそれぞれ２進数に変換する

結論（理屈はあと） 1. N個の⼭のコインの枚数をそれぞれ２進数に変換する 2. N個の2進数についてビットごとのXORを計算する

結論（理屈はあと） 1. N個の⼭のコインの枚数をそれぞれ２進数に変換する 2. N個の2進数についてビットごとのXORを計算する 3. このとき、全ての局⾯は2種類に分けられる 「XORが0」or「XORが0じゃない」

結論（理屈はあと） 1. N個の⼭のコインの枚数をそれぞれ２進数に変換する 2. N個の2進数についてビットごとのXORを計算する 3. このとき、全ての局⾯は2種類に分けられる 「XORが0」or「XORが0じゃない」 必勝法 「XORが0」という局⾯を相⼿に押し付け続ける

具体例で確認 • ⼭が３つあってコインがそれぞれ11枚, 12枚, 15枚のとき 11(10) 12(10) 15(10) → → → 1 0 1 1(2) 1 1 0 0(2) 1 1 1 1(2)

具体例で確認 • ⼭が３つあってコインがそれぞれ11枚, 12枚, 15枚のとき 11(10) 12(10) 15(10) → → → ビットごとにXORをとると 1 0 1 1(2) 1 1 0 0(2) 1 1 1 1(2) 1000 （普通に⾜して, 繰り上がりが無いと思えば良い）

具体例で確認 • ⼭が３つあってコインがそれぞれ11枚, 12枚, 15枚のとき 11(10) 12(10) 15(10) → → → ビットごとにXORをとると 1 0 1 1(2) 1 1 0 0(2) 1 1 1 1(2) 1000 （普通に⾜して, 繰り上がりが無いと思えば良い） よって、このとき先⼿は「XORが0じゃない」局⾯にいる

具体例で確認 • 「XORが0」となるようにコインを取る （XOR=1000 が 0000 になるなら 取り⽅はなんでも良い）

具体例で確認 （XOR=1000 が 0000 になるなら 取り⽅はなんでも良い） • 「XORが0」となるようにコインを取る • 例えば、1５枚の⼭から8枚のコインを取る 11(10) 12(10) 15(10) 8(10) → → → → 1 0 1 1(2) 1 1 0 0(2) 1 1 1 1(2) 0 1 1 1(2)

具体例で確認 （XOR=1000 が 0000 になるなら 取り⽅はなんでも良い） • 「XORが0」となるようにコインを取る • 例えば、1５枚の⼭から8枚のコインを取る 11(10) 12(10) 15(10) 8(10) → → → → ・ XOR が 0 0 0 0になった 1 0 1 1(2) 1 1 0 0(2) 1 1 1 1(2) 0 1 1 1(2)

具体例で確認 • 後⼿はどのようにコインを取っても XORが0ではなくなってしまう 1つの⼭からしか取れないから 11(10) 12(10) 8(10) → → → 1 0 1 1(2) 1 1 0 0(2) 0 1 1 1(2)

具体例で確認 • 後⼿はどのようにコインを取っても XORが0ではなくなってしまう 1つの⼭からしか取れないから 11(10) 12(10) 8(10) → → → 1 0 1 1(2) 1 1 0 0(2) 0 1 1 1(2) • 例えばコイン8枚の⼭から取るとき 1011 + 1100 + X ＝0000 となるようなXは、X＝0111しかない そのため必ずXORが0ではなくなる

Nimの必勝法 このように、 「 XORが０」という局⾯を相⼿に押し付け続ければ、 • ⾃分には「XORが0ではない」局⾯しか回ってこない • いずれコインは尽き、そのとき0(10) →0(2) で XORは0 であるから、相⼿が負けている。 敗者＝「先にコインが取れなくなったプレーヤー」 ＝「コインが0 枚のときのプレーヤー」 ∈ 「 XOR=0のときのプレーヤー」

Nimの必勝法 ⼭が2つの場合は、XORが0となるのはコインの枚数が同じとき 結局同じことをやっている

実装例 #⼊⼒の受け取り N=int(input()) #Nは⼭の数 coin=list(map(int, input().split())) #それぞれのコインの枚数 XOR=0 # XORの結果を格納する変数

実装例 for i in range(coin): XOR ^= i #ビット演算 if XOR!=0 : print(“先⼿必勝”) else: print(“後⼿必勝”)

計算量 • O(N) • ⾜すだけ

Grundy数 • ⼀般に不偏ゲームはNimにおけるXORのように 局⾯を分類して数値を割り当てることで解析を簡単にできる • 詳細は別の機会に譲る

まとめ 組み合わせゲームに関するアルゴリズム • min-max 法 • Nim(不偏ゲーム)