JavaScriptで三山崩しを作ってみる

bubudoufu

3年前

このページでは三山崩しと二山崩しをコンピュータと対戦できます。必勝法なども少しだけ解説しています。
作成した三山崩しのコードはgithubにあります。
その他、作成したアプリやゲームの一覧はこちらにあります。

概要
山が２つの場合の必勝法
山が３つの場合の必勝法（良形・必勝形を覚えて勝つ）
山が３つの場合の必勝法（XORで計算して勝つ）
JavaScriptでコンピュータの指し手をプログラムする

概要

三つに分かれた石の山から二人が交互に取り合い最後の一つを取ったほうが勝ちのゲームです。手番を選択するとコンピュータとの対戦が始まります。

ルール

一つの山から好きなだけの石を取って良い。
一度に２つ以上の山から石をとることはできない。
自分が手番の時は石を一つ以上取らなくてはいけない。
交互に石を取っていき最後に石を取ったほうが勝ち。

山が２つの場合の必勝法

石取りゲームは開始時点の石の数と取り方のルールによって勝敗は決まっていて、山が二つの場合は山の数を同数にして相手側に渡すと勝つことが出来ます。
例）(1,1),(2,2),(3,3),etc.

ゲーム開始時石の数が違う場合は先手番を取り、同数にして相手に渡すのを繰り返す。
例）(7,5)→(5,5)→(2,5)→(2,2)

ゲーム開始時石の数が同じ場合は後手番を選択し相手に石を先にとってもらい同数が崩れたのを同数にする。
例）(6,6)→(6,4)→(4,4)

山が３つの場合の必勝法（良形・必勝形を覚えて勝つ）

相手が石をどう取っても自分が勝てる形を良形と言います。

(1,2,3)は良形となります。この形で手番を渡された場合どうゆう取り方をしても相手に最後の石を取られるのを確認できると思います。
例）(1,2,3)→(0,2,3)→(0,2,2), (1,2,3)→(1,1,3)→(1,1,0), (1,2,3)→(1,2,0)→(1,1,0), etc.

今回作成した三山崩し（石の数が1～9）では以下の形が良形となります。

山が２つの場合の必勝法と同じ形　例）(0,4,4), (0,5,5), (0,6,6), etc.
(1,2,3)
(1,4,5)
(1,6,7)
(1,8,9)
(2,4,6)
(2,5,7)
(3,4,7)
(3,5,6)

注）()内の石の数は順不同でも構いません。(a,b,c)は (b,c,a), (c,b,a),(a,c,b) などでもok

上記の形を常に相手番に渡せば勝つことが出来ます。初期配置時に上記の形にできない場合は後手番を選択して相手に先に石を取ってもらいます。相手に石を取ってもらうと上記の形のいずれかに出来るので勝つことが出来ます。

山が３つの場合の必勝法（XORで計算して勝つ）

良形は計算でも求めることが出来ます。山にある石の数を二進法で表し、各桁をXORで計算し０となった場合は良形となります。

例）(2,4,6)の場合
二進法で表す。
2→ 10
4→100
6→110
各桁をXORで計算する。000となる10進法で表すと0なので良形。
例）(2,4,9)の場合
二進法で表す。
2→ 10
4→ 100
9→1001
各桁をXORで計算する。1111となる10進法で表すと15なので良形ではない。

(2,4,9)をXORで計算すると15となりました。この形を良形にするには2,4,9それぞれに先ほど計算した答えの15とXORの計算をしその答えが石の数より小さい場所を答えの数に置き換えると良形になります。
2 XOR 15 →13
4 XOR 15 →11
9 XOR 15 →6
9を6に置き換える2 XOR 4 XOR 6 = 0なので良形になります。

初期配置時が良形の場合は後手番を選択し、そうでない場合は先手番を選択して常に良形を相手に渡していけば勝てます。

JavaScriptでコンピュータの指し手をプログラムする

JavaScriptではビット排他的論理和演算子を使うと先ほどの計算が出来ます。

// 石の数が(3,7,5)の例
console.log(3 ^ 7 ^ 5); // 1

1 2	// 石の数が(3,7,5)の例 console.log(3 ^ 7 ^ 5); // 1

以下のプログラムは配列stonesに石の数を入力するとどこから石をいくつ取れば良形になるかコンソールログに表示されます。

const stones = [3, 7, 5];
let xor;

stones.forEach((value) => {
  xor ^= value;
});

if (xor === 0) {
  console.log("良形です");
} else {
  for (let i = 0; i < stones.length; i++) {
    if (stones[i] > (stones[i] ^ xor)) {
      console.log(
        `${stones[i]}つ石がある山から${
          stones[i] - (stones[i] ^ xor)
        }つ取ってください`
      );
      break;
    }
  }
}

// 3つ石がある山から1つ取ってください

const stones = [3, 7, 5];

let xor;

stones.forEach((value) => {

xor ^= value;

});

if (xor === 0) {

console.log("良形です");

} else {

for (let i = 0; i < stones.length; i++) {

if (stones[i] > (stones[i] ^ xor)) {

console.log(

`${stones[i]}つ石がある山から${

stones[i] - (stones[i] ^ xor)

}つ取ってください`

);

break;

}

// 3つ石がある山から1つ取ってください

最後までお読みいただきありがとうございました。
作成した三山崩しのコードはgithubにあります。
その他、作成したアプリやゲームの一覧はこちらにあります。