不偏ゲーム:操作できなくなったプレイヤーが勝ちの Nim

ないしは、それに相当する、いくつかの不偏ゲームを複数個同時並列でプレイするような不偏ゲームの必勝法について。

今回は競技プログラムに関する記事です。

katoufujibanana.hatenadiary.jp

こちらの記事の続編です。Grundy 数などの説明は前回の記事に書いてあるので、まだ見ていない方は前回の記事からどうぞ。

さて、前回の記事の最後の方に但し書きを入れた、いくつかの不偏ゲームを複数個同時並列でプレイするような問題で、終了盤面を迎えたプレイヤーが勝ちというルールの場合の必勝法は、やや天下り的ではありますが、以下のようになります。

  • 同時並行しているすべての不偏ゲームの初期盤面の Grundy 数が 1 以下の場合、 Grundy 数が 1 の盤面が偶数個である場合先手必勝、奇数個である場合後手必勝
  • そうでない場合、「各ゲームの初期盤面の Grundy 数の xor をとったもの」が 0 である場合後手必勝、0 でない場合先手必勝

となります。

ただし、同時並行しているそれぞれの不偏ゲームの Grundy 数は、そのゲームの終了盤面の Grundy 数を 0 として算出してください。

一体、どうしてこんなことになるのでしょう?

まずは、同時並行しているすべての不偏ゲームの初期盤面の Grundy 数が 1 以下である場合から考えてみます。

このとき、一度でも相手に Grundy 数が1の盤面が奇数個ある盤面を押し付けると、以降相手には Grundy 数が1の盤面が奇数個ある盤面を押し付け続けることができます。

偶奇のパリティと、Grundy 数 0 から 0 以外の盤面への遷移は、もう一度 0 にしなおして返す操作を考えると証明できるかと思います。

そしていずれはゲームが終了するので、どこかの時点で、相手に Grundy 数が1の盤面が1個しかない盤面が押し付けられます。相手がその1の盤面を0にしてあなたに返して来たらあなたの勝ちです。

いずれかの不偏ゲームの Grundy 数 0 から 0 以外の盤面への遷移をして返して来たら、その盤面をもう一度 0 にしなおして、もう一度 Grundy 数が1の盤面が1個しかない盤面を押し付けなおしましょう。

これで、同時並行しているすべての不偏ゲームの初期盤面の Grundy 数が 1 以下である場合の必勝法がわかりました。

では、同時並行している不偏ゲームの初期盤面の Grundy 数に 1 以下でないものが含まれるときは、どうするのでしょうか?

このとき目指すのは、同時並行している不偏ゲームの初期盤面の Grundy 数について、ひとつだけが2以上であり、他はすべて1以下であるという盤面をつくることを目指します。

この盤面における、各ゲームの盤面の Grundy 数の xor をとったものは明らかに非ゼロです。また、同時並行している不偏ゲームのうち、盤面が Grundy 数が2以上のものの個数は、1個ずつ変化していくため、いずれはその盤面が出現します。

そのため、相手に xor が 0 の盤面を押し続けていると、いずれ自分の手番でこの盤面が回ってきます。

この手番が回ってきたときに

  • Grundy 数が1の盤面が奇数個ある場合、Grundy 数が2以上の盤面の Grundy 数が 0 になるように遷移させる
  • Grundy 数が1の盤面が偶数個ある場合、Grundy 数が2以上の盤面の Grundy 数が 1 になるように遷移させる

ことで、相手に Grundy 数が1の盤面が奇数個ある盤面を押し付けることができます。

あとは、同時並行しているすべての不偏ゲームの初期盤面の Grundy 数が 1 以下の場合で述べたように、相手に Grundy 数が1の盤面が奇数個ある盤面を押し付け続けることで勝ちになります。

これで、いくつかの不偏ゲームを複数個同時並列でプレイするような問題で、終了盤面を迎えたプレイヤーが勝ちとなる場合の必勝法もわかりました。

ぜひ競プロや実生活でもお役立てください。