アルゴリズム

[C言語] 三山くずしゲームの実装方法と戦略

2025-01-17更新日: 2025-01-17

三山くずしゲームは、3つの山に積まれた石を交互に取り合い、最後の石を取った方が負けるゲームです。

C言語での実装には、まず石の数を格納する配列を用意し、プレイヤーの入力を受け取るループを作成します。

各ターンで、プレイヤーはどの山から何個の石を取るかを選択し、選択が有効かどうかをチェックします。

戦略としては、相手に不利な状況を作るために、ニム和(各山の石の数のXOR)をゼロにするように石を取ることが重要です。

これにより、相手が必ず負ける状況を作り出すことができます。

目次から探す

三山くずしゲームとは

三山くずしゲームは、シンプルながらも奥深い戦略が求められる古典的なゲームです。

このゲームは、複数の山から石を取り除くことで進行し、最後の石を取ったプレイヤーが勝者となります。

以下では、ゲームの基本ルール、勝敗の決定方法、そしてゲームの歴史と背景について詳しく説明します。

ゲームの基本ルール

三山くずしゲームの基本ルールは以下の通りです。

初期設定: ゲームは通常、3つの山に異なる数の石が置かれた状態で始まります。
プレイヤー: 2人のプレイヤーが交互に石を取ります。
石の取り方: 各プレイヤーは自分のターンで、1つの山から1個以上の石を取ることができます。

ただし、複数の山から同時に石を取ることはできません。

ゲームの終了: すべての石が取り除かれた時点でゲームは終了します。

勝敗の決定方法

勝敗は以下の方法で決定されます。

勝者: 最後の石を取ったプレイヤーが勝者となります。
敗者: 最後の石を取れなかったプレイヤーが敗者となります。

このシンプルなルールの中に、相手の動きを予測し、最適な手を選ぶ戦略が求められます。

ゲームの歴史と背景

三山くずしゲームは、古代から存在するニムゲームの一種です。

ニムゲームは、数学的な戦略ゲームとして知られ、特にコンピュータサイエンスや数学の分野で研究されています。

三山くずしは、その中でも特にシンプルで理解しやすい形式であり、教育や娯楽の場で広く親しまれています。

このゲームは、単純なルールながらも、プレイヤーの戦略的思考を鍛えるのに適しており、プログラミングの学習においてもよく題材として取り上げられます。

C言語での三山くずしゲームの実装

C言語を用いて三山くずしゲームを実装することで、プログラミングの基礎を学ぶことができます。

以下では、必要な準備から実際のプログラムの完成までを順を追って説明します。

必要な準備と環境設定

C言語でプログラムを作成するためには、以下の準備が必要です。

開発環境: C言語のコンパイラがインストールされた環境(例：GCC、Clang)
テキストエディタ: ソースコードを編集するためのエディタ(例：Visual Studio Code、Sublime Text)

これらの環境が整っていれば、プログラムの作成を始めることができます。

石の数を管理するデータ構造

三山くずしゲームでは、各山の石の数を管理する必要があります。

ここでは、配列を用いて石の数を管理します。

#include <stdio.h>
int stones[3] = {3, 4, 5}; // 各山の初期の石の数

この配列stonesは、3つの山の石の数を表しています。

プレイヤーの入力処理

プレイヤーがどの山から何個の石を取るかを入力する処理を実装します。

void getPlayerMove(int *pile, int *num) {
    printf("山の番号を選んでください (0-2): ");
    scanf("%d", pile);
    printf("取る石の数を選んでください: ");
    scanf("%d", num);
}

この関数getPlayerMoveは、プレイヤーからの入力を受け取り、選択された山と石の数を取得します。

石を取るロジックの実装

プレイヤーの入力に基づいて、石を取るロジックを実装します。

void removeStones(int pile, int num) {
    if (pile >= 0 && pile < 3 && num > 0 && num <= stones[pile]) {
        stones[pile] -= num;
    } else {
        printf("無効な操作です。もう一度試してください。\n");
    }
}

この関数removeStonesは、指定された山から指定された数の石を取り除きます。

勝敗判定の実装

ゲームの終了条件を判定するためのロジックを実装します。

int isGameOver() {
    return (stones[0] == 0 && stones[1] == 0 && stones[2] == 0);
}

この関数isGameOverは、すべての山の石がなくなったかどうかを判定し、ゲームの終了を確認します。

完成したプログラム

以上の要素を組み合わせて、三山くずしゲームの完成したプログラムを示します。

#include <stdio.h>
int stones[3] = {3, 4, 5};
void getPlayerMove(int *pile, int *num) {
    printf("山の番号を選んでください (0-2): ");
    scanf("%d", pile);
    printf("取る石の数を選んでください: ");
    scanf("%d", num);
}
void removeStones(int pile, int num) {
    if (pile >= 0 && pile < 3 && num > 0 && num <= stones[pile]) {
        stones[pile] -= num;
    } else {
        printf("無効な操作です。もう一度試してください。\n");
    }
}
int isGameOver() {
    return (stones[0] == 0 && stones[1] == 0 && stones[2] == 0);
}
int main() {
    int pile, num;
    while (!isGameOver()) {
        printf("現在の石の状態: [%d, %d, %d]\n", stones[0], stones[1], stones[2]);
        getPlayerMove(&pile, &num);
        removeStones(pile, num);
    }
    printf("ゲーム終了！\n");
    return 0;
}

このプログラムは、プレイヤーが交互に石を取り合い、すべての石がなくなるとゲームが終了するシンプルな三山くずしゲームを実現しています。

戦略とアルゴリズム

三山くずしゲームは、単なる運のゲームではなく、数学的な戦略を駆使することで勝利を目指すことができます。

ここでは、ニム和の概念を中心に、必勝法や戦略の実装方法について解説します。

ニム和の概念

ニム和とは、ニムゲームにおける戦略的な概念で、各山の石の数を2進数で表し、それらをビットごとにXOR演算した結果を指します。

ニム和が0でない状態では、次のプレイヤーが有利な状況にあります。

XOR演算: 各ビットを比較し、異なる場合に1、同じ場合に0を返す演算です。

ニム和を利用した必勝法

ニム和を利用することで、必勝法を導き出すことができます。

基本的な考え方は以下の通りです。

ニム和が0でない場合: 次のプレイヤーが有利です。

適切な手を選ぶことで、相手に不利な状況を強いることができます。

ニム和が0の場合: 現在のプレイヤーは不利です。

相手がミスをしない限り、負ける可能性が高いです。

相手を追い詰める戦略

相手を追い詰めるためには、ニム和を0にする手を選ぶことが重要です。

これにより、相手に不利な状況を強いることができます。

戦略的な手: ニム和を0にするために、どの山から何個の石を取るべきかを計算します。

戦略の実装方法

ニム和を利用した戦略をC言語で実装する方法を示します。

#include <stdio.h>
int stones[3] = {3, 4, 5};
int calculateNimSum() {
    return stones[0] ^ stones[1] ^ stones[2];
}
void makeStrategicMove() {
    int nimSum = calculateNimSum();
    for (int i = 0; i < 3; i++) {
        int target = stones[i] ^ nimSum;
        if (target < stones[i]) {
            printf("山 %d から %d 個の石を取ります。\n", i, stones[i] - target);
            stones[i] = target;
            return;
        }
    }
    // ニム和が0の場合、適当に1個取る
    for (int i = 0; i < 3; i++) {
        if (stones[i] > 0) {
            printf("山 %d から 1 個の石を取ります。\n", i);
            stones[i]--;
            return;
        }
    }
}

この関数makeStrategicMoveは、ニム和を計算し、最適な手を選んで石を取ります。

完成したプログラム

ニム和を利用した戦略を組み込んだ三山くずしゲームの完成したプログラムを示します。

#include <stdio.h>
int stones[3] = {3, 4, 5};
int calculateNimSum() {
    return stones[0] ^ stones[1] ^ stones[2];
}
void makeStrategicMove() {
    int nimSum = calculateNimSum();
    for (int i = 0; i < 3; i++) {
        int target = stones[i] ^ nimSum;
        if (target < stones[i]) {
            printf("山 %d から %d 個の石を取ります。\n", i, stones[i] - target);
            stones[i] = target;
            return;
        }
    }
    for (int i = 0; i < 3; i++) {
        if (stones[i] > 0) {
            printf("山 %d から 1 個の石を取ります。\n", i);
            stones[i]--;
            return;
        }
    }
}
int isGameOver() {
    return (stones[0] == 0 && stones[1] == 0 && stones[2] == 0);
}
int main() {
    while (!isGameOver()) {
        printf("現在の石の状態: [%d, %d, %d]\n", stones[0], stones[1], stones[2]);
        makeStrategicMove();
    }
    printf("ゲーム終了！\n");
    return 0;
}

このプログラムは、ニム和を利用して最適な手を選び、プレイヤーが常に有利な状況を作り出すことを目指しています。

応用例

三山くずしゲームは、そのシンプルなルールからさまざまな応用が可能です。

ここでは、複数山への拡張、GUIを用いたビジュアル化、AIによる自動プレイについて解説します。

複数山への拡張

三山くずしゲームを複数の山に拡張することで、より複雑で戦略的なゲームを楽しむことができます。

以下のポイントを考慮して実装を行います。

山の数を動的に設定: 配列のサイズを動的に変更することで、任意の数の山を扱えるようにします。
初期化: 各山にランダムまたは指定された数の石を配置します。

#include <stdio.h>
#include <stdlib.h>
#define MAX_PILES 10
int stones[MAX_PILES];
void initializePiles(int numPiles) {
    for (int i = 0; i < numPiles; i++) {
        stones[i] = rand() % 10 + 1; // 1から10個の石をランダムに配置
    }
}

このコードは、最大10個の山にランダムな数の石を配置する初期化関数を示しています。

GUIを用いたビジュアル化

C言語でGUIを用いたビジュアル化を行うには、外部ライブラリを使用することが一般的です。

ここでは、簡単なビジュアル化のアイデアを紹介します。

ライブラリの選択: SDLやGTKなどのライブラリを使用して、ゲームの状態を視覚的に表示します。
インタラクション: マウスやキーボードを用いて、プレイヤーが石を選択し、取ることができるようにします。

具体的な実装はライブラリに依存しますが、以下のような流れで進めます。

ウィンドウを作成し、各山の石を描画する。
プレイヤーの入力を受け取り、石を取るアクションを実行する。
ゲームの状態を更新し、再描画する。

AIによる自動プレイ

AIを用いて自動的にプレイすることで、ゲームの戦略を学ぶことができます。

AIはニム和を利用して最適な手を選びます。

アルゴリズムの選択: ミニマックス法やモンテカルロ法などを用いて、AIの戦略を強化します。
実装例: 先に示したニム和を利用した戦略をAIに組み込み、プレイヤーの代わりに自動で石を取るようにします。

void aiMove() {
    int nimSum = calculateNimSum();
    for (int i = 0; i < MAX_PILES; i++) {
        int target = stones[i] ^ nimSum;
        if (target < stones[i]) {
            printf("AIは山 %d から %d 個の石を取ります。\n", i, stones[i] - target);
            stones[i] = target;
            return;
        }
    }
    for (int i = 0; i < MAX_PILES; i++) {
        if (stones[i] > 0) {
            printf("AIは山 %d から 1 個の石を取ります。\n", i);
            stones[i]--;
            return;
        }
    }
}

この関数aiMoveは、AIが最適な手を選んで石を取る動作を実装しています。

AIによる自動プレイは、ゲームの戦略を深く理解するのに役立ちます。