C++で解く「石を1個ずつ取り除くニムゲーム」の勝者予測プログラム

この問題はニムゲーム（Nim Game）と呼ばれるもので、山積みの石の数を表す正整数 N が与えられ、2人のプレイヤー playerA と playerB が交互に石を取っていくゲームです。私たちの課題は、このゲームの勝者を予測するプログラムを作成することです。

ニムゲームとは

ここでは、1つの山に積まれた石と、playerA・playerB の2人のプレイヤーがいます。各プレイヤーの番には、山から石をちょうど1個だけ取り除くことができます。playerA が先手として最初の石を取ることから始まり、最後に石を取ったプレイヤーが勝者となります。

具体的な例を見てみましょう。

入力：N = 6
出力：playerB
説明：
石の総数 = 6、石が取られる順序は
playerA → playerB → playerA → playerB → playerA → playerB

この場合、6個目の石は playerB が取るため、勝者は playerB になります。

解法アプローチ

この問題を解く一つの方法は、N の値と勝者の関係から一般的な規則性（公式）を見つけ出すことです。いくつかの N の値に対する勝者を確認してみましょう。

• N = 1 のとき、勝者は playerA
• N = 2 のとき、勝者は playerB
• N = 3 のとき、勝者は playerA

これらの結果から、次のような規則が導き出せます。

• N が奇数の場合： 勝者は playerA（先手）
• N が偶数の場合： 勝者は playerB（後手）

これは直感的にも理解できます。各ターンで必ず1個の石が減っていくため、N が奇数なら最後の1個は先手の playerA が取り、偶数なら後手の playerB が取ることになるからです。したがって、N を2で割った余りを判定するだけで勝者を求められます。

C++での実装例

上記の解法を実装したプログラムが以下です。

#include<iostream>
using namespace std;

bool findGameofNimWinner(int N){
    if(N % 2 == 0)
        return 0;   // 偶数なら playerB の勝ち
    else
        return 1;   // 奇数なら playerA の勝ち
}
int main(){
    int N = 26;
    cout << "The winner of the Game of Nim is ";
    findGameofNimWinner(N) ? (cout << "Player A") : (cout << "Player B");
    return 0;
}

実行結果

The winner of the Game of Nim is Player B

N = 26 は偶数であるため、出力は Player B となり、規則通りに正しく判定できていることがわかります。

まとめ

この問題は、各ターンで石を1個しか取れないという制約があるため、N の偶奇を判定するだけで O(1) の計算量で勝者を特定できる非常にシンプルなゲーム理論の問題です。より一般的なニムゲーム（複数の山や複数個の石を取れるバリエーション）では XOR を使った戦略が必要になりますが、本問題のように単純なルールの場合は偶奇の判定だけで十分です。