三山崩しゲーム

名前だけ聞いても分からないかもですが、やったことのある方もたくさんいると思います。 私も授業中とかによくやりました。 最後の１つを取ったら勝ち的なゲームです。 このゲームには必勝法があるので、今回はそれを紹介します。

ルール

1. いくつかの石を３つの山に分けます。
2. ２人のプレイヤーは交互に１つの山から１つ以上の好きな数の石をとる。
3. 最後の１つを取った方の勝ちヽ(´∀`｡)ﾉﾟｲｪｲ

必勝法

説明がちょっと難しいのですが、 それぞれの山の石の数を２進法展開して同じ基底の係数の和が全て偶数になるように石をとります。 文章で書かれてもよく分からないと思うので、PHPのコードにしてみました。

function saikyou($input) {
    $order = ceil(log(max($input), 2)) + 1;
    arsort($input);
    foreach ($input as $k => $v) {
        $binary[$k] = str_split(str_pad(decbin($v), $order, "0", STR_PAD_LEFT));
    }

    $key = null;
    for ($i = 0; $i < $order; $i++) {
        $sum = 0;
        foreach ($binary as $v) {
            $sum += (int)$v[$i];
        }
        if ($sum % 2 == 1) {
            if ($key === null) {
                foreach ($binary as $k => $v) {
                    if ($v[$i] === "1") {
                        $key = $k;
                        $binary[$key][$i] = "0";
                        break;
                    }
                }
            } else {
                $binary[$key][$i] = (string)(1 - (int)$binary[$key][$i]);
            }
        }
    }

    ksort($binary);
    foreach ($binary as $k => $v) {
        $output[$k] = bindec(implode("", $v));
    }

    return $output;
}

$inputには配列でそれぞれの山の石の数を入れます。 ↓こんな感じになります。

$input  = array(9, 2, 5);
$output = saikyou($input);  // array(7, 2, 5)

$outputは最強の石の取り方でできたそれぞれの山の石の数です。 上の例では（７，２，５）なので、９の山から石を２つ取るのが最強です。 ちゃんと２進法展開の同じ基底の係数の和が全て偶数になっているのが分かります。 山の数は３つでなくても同じですし、石の数もいくつあっても考え方は一緒です。

便利な関数がたくさんあって短いコードでスッキリ書けました。 説明の難しいこともコードにするとスッキリですね。

◯参考 三山崩しゲーム