HackerRank Game Theory の勧め - はまやんはまやんはまやん

HackerRank Game Theory

https://www.hackerrank.com/5-days-of-game-theory
Typical DP Contestというのがありますが、それのゲーム理論版

ゲームの勝敗判定をする問題を解く選択肢

必勝法・貪欲法（必勝の条件・法則がある）
バックトラッキング（遷移先に負け状態が1つでもあれば勝ち状態）
Nim/Grundy数

hamayanhamayan.hatenablog.jp

問題

Game of Stones

https://www.hackerrank.com/contests/5-days-of-game-theory/challenges/a-game-of-stones
T個のクエリがある。N個の山があり、そこから2,3,5個のいずれかを取る。
取れなくなったら負け。初手が勝ちならFirst, 後手が勝ちならSecond

Tower Breakers

https://www.hackerrank.com/contests/5-days-of-game-theory/challenges/tower-breakers
T個のクエリがある。N個、数Mがある。各数をその数の約数のどれかに変換する操作をする。
全ての数が1の状態で番が回ってきたら負け。初手が勝ちなら1, 後手が勝ちなら2

A Chessboard Game

https://www.hackerrank.com/contests/5-days-of-game-theory/challenges/day-1-a-chessboard-game
T個のクエリがある。15*15のマスに1つ駒がある。
この駒は、(x - 2, y + 1), (x - 2, y - 1), (x + 1, y - 2), (x - 1, y - 2)に移動できる。
移動できなくなった方が負け。初手が勝ちならFirst, 後手が勝ちならSecond

Nim Game

https://www.hackerrank.com/contests/5-days-of-game-theory/challenges/day-2-nim-game
T個のクエリがある。各クエリは、N個の石の個数がS[i]の石の山がある。
順番に石が残っている山から1つ以上の石を取り除く操作をする。
取り除く石がなくなったら負け。先手が勝ちならFirst, 後手が勝ちならSecond

Misera Nim

https://www.hackerrank.com/contests/5-days-of-game-theory/challenges/misere-nim
T個のクエリがある。各クエリは、N個の石の個数がS[i]の石の山がある。
順番に石が残っている山から1つ以上の石を取り除く操作をする。
最後に石を取り除いた方が負け。先手が勝ちならFirst, 後手が勝ちならSecond

Nimble Game

https://www.hackerrank.com/contests/5-days-of-game-theory/challenges/nimble
T個のクエリがある。0～N-1個の番号がついた箱にC[i]個の石が入っている。
順番に1以上の番号の箱から石を1つ取り出し、それよりも小さい番号の箱に入れる。
操作が行えなくなった方が負け。先手が勝ちならFirst, 後手が勝ちならSecond

Poker Nim

https://www.hackerrank.com/contests/5-days-of-game-theory/challenges/day-2-poker-nim
T個のクエリがある。N個の石の個数がS[i]の石の山がある。
順番に「石を増やす」か「石を減らす」かする。
ただし「石を増やす」はK回しか行えない。
操作ができなくなった方が負け。先手が勝ちならFirst, 後手が勝ちならSecond

Tower Breakers, Revisited!

https://www.hackerrank.com/contests/5-days-of-game-theory/challenges/tower-breakers-2
T個のクエリがある。N個の数列があり、各要素はM[i]。
各数をその数の約数のどれかに変換する操作をする。
全ての数が1の状態で番が回ってきたら負け。初手が勝ちなら1, 後手が勝ちなら2

Tower Breakers, Again!!

https://www.hackerrank.com/contests/5-days-of-game-theory/challenges/tower-breakers-3
T個のクエリがある。N個の数列があり、各要素はM[i]。
ある数Xを選び、それをY個の数Zに分ける(Y*Z = X, Y > 1)。
全ての数が1の状態で番が回ってきたら負け。初手が勝ちなら1, 後手が勝ちなら2

A Chessboard Game, Again!

https://www.hackerrank.com/contests/5-days-of-game-theory/challenges/a-chessboard-game
T個のクエリがある。15*15のマスにk個の駒がある。
この駒は(x - 2, y + 1), (x - 2, y - 1), (x + 1, y - 2), (x - 1, y - 2)に移動できる。
移動できる駒がなくなった方が負け。初手が勝ちならFirst, 後手が勝ちならSecond

Digits Square Board

https://www.hackerrank.com/contests/5-days-of-game-theory/challenges/digits-square-board
T個のクエリがある。N*Nの板にA[y][x]の数が書いてある。
合成数が1つでも書いてある板を選び、縦横どちらかに割る。
割れなくなった方が負け。初手が勝ちならFirst, 後手が勝ちならSecond

Fun Game

https://www.hackerrank.com/contests/5-days-of-game-theory/challenges/fun-game
T個のクエリがある。長さNの数列A[i],B[i]がある。
0<= i＜Nとあるiを1つ選ぶと、自分はA[i], 相手はB[i]得られる。
各iは1度しか選べない時、初手が勝ちならFirst, 後手が勝ちならSecond, 同点ならTie

Powers Game

https://www.hackerrank.com/contests/5-days-of-game-theory/challenges/powers-of-two-game
T個のクエリがある。*2^1*2^2*2^3*...*2^nというアスタリスクと2の累乗から成る列がある。
順番に*を+か-かに変える処理を行う。
全て変換後の計算結果が17の倍数なら後手Secondの勝ち、そうでないなら先手Firstの勝ち

Deforestation

https://www.hackerrank.com/contests/5-days-of-game-theory/challenges/deforestation
T個のクエリがある。N頂点の根が1の木がある。
互いに辺を1つ選び、その辺で繋がっている子の部分木を削除する。
部分木を消せなくなったら負け。先手が勝ちならFirst, 後手が勝ちならSecond

短い解説

以上の問題についてはwinjiiさんのブログで細かく解説されています。
http://winjii.hatenablog.com/search?q=Game+Theory
以下の問題は日本語解説が見つからなかったので詳しく書きます。

しっかりした解説

Powers Game

https://www.hackerrank.com/contests/5-days-of-game-theory/challenges/powers-of-two-game
必勝法がある。数学的に考える問題。偶奇を使って勝敗を操作する系のよくある考え方。
今回はmod17とした時の計算結果が必ず奇数となれば勝てるということを使う。
17の倍数うんぬんの話なので、計算結果mod17が0となれば後手が勝ちという条件に読み替えておきます。

2^nのnの値	2^n(mod 17)	-2^n(mod17)
1	2	-2 = 15
2	4	-4 = 13
3	8	-8 = 9
4	16	-16 = 1
5	15	-15 = 2
6	13	-13 = 4
7	9	-9 = 8
8	1	-1 = 16
9	2	-2 = 15
10	4	-4 = 13

...
大切な事実が2つあって

nの値もmod8で周期性がある
各2^nは正負で偶奇が異なる

2^nのnの値(mod 8)	2^n(mod 17)	-2^n(mod17)
0	1	16
1	2	15
2	4	13
3	8	9
4	16	1
5	15	2
6	13	4
7	9	8

またしても重要な事実

0～3と4～7には対称性がある

では場合分けしていきます。

(i) nが奇数のとき
先手は一番最初にどの数でも良いので選ぶ。この時、mod17の値が奇数となるように+,-を選ぶ。
これからは後手がどんな数でどんな+,-で選んでも、先手の番で全体の計算結果が奇数となるように選択していけば、先手が最後の番となるので勝てる。

これはすぐ分かりそうな考察です。ここからが難しい。

(ii) n == 0 (mod 8)
どっから出てきたんだと言う感じですが、「0～3と4～7には対称性がある」という事実から得られる。
nが偶数ならば必ず先手後手の順が続く訳ですが、この場合分けの状況ならば、先手の手と後手の手を合わせてmod17で0にすることができる。
具体的には先手が+2^1 (=2)としたなら後手は+2^5 (=15)を選ぶことでmod17で0にすることができる。
これをゲームの終わりまで続けていくと後手が勝てる。
これは「対称的な手を選択し続けると勝てる」という必勝法での常套手段。

(iii) それ以外
これだと対称的に手を選択して最後まで行けないので後手が勝てない。
なぜ行けないと勝てないのかはどんだけ考えても分からん。
https://www.hackerrank.com/contests/5-days-of-game-theory/challenges/powers-of-two-game/editorial
ブルートフォースで検証できるとか書いてあるけども…

なので、n%8==0ならSecond, それ以外ならFirstを吐けばAC

Deforestation

https://www.hackerrank.com/contests/5-days-of-game-theory/challenges/deforestation
「Green Hackenbush」問題らしい。

あまり良く分かってないので、多分こういうことだろうという解釈

Grundy数は部分木を一本のパスに帰着させた場合のパスの長さ
部分木を一本のパスに帰着させる時は、子のパスの長さ（=Grundy数）のxor
子のパスの長さをxorするときは、子のgrundy数+1してxorをとる（+1は自分とその子の間の辺の分）

これで根から順にGrundy数を計算する。