アルゴリズム

[Python] 三山くずし(石取りゲーム)で絶対に勝つプログラムを実装する方法

2025-01-18更新日: 2025-01-18

三山くずしは、複数の山から石を取り合うゲームで、最後の石を取ったプレイヤーが勝つルールです。

絶対に勝つためには、ニム和(XOR和)を利用した戦略が有効です。

各山の石の数をXOR演算し、その結果が0でない場合、次の手でXOR和を0にするように石を取ることで勝利が可能です。

XOR和が0の場合は、相手がミスするのを待つしかありません。

目次から探す

三山くずしとは
ニムゲームとXORの関係
三山くずしにおける必勝戦略
Pythonで三山くずしを実装する
コンピュータが絶対に勝つ戦略を実装する
応用例
まとめ

三山くずしとは

三山くずしは、石取りゲームの一種で、プレイヤーが交互に山から石を取り合うシンプルなルールが特徴です。

ゲームは通常、3つの山から構成され、各山には異なる数の石が置かれています。

プレイヤーは自分のターンに、任意の山から1つ以上の石を取り、相手に石を取らせることを目的とします。

最終的に、相手が石を取れなくなった時点で勝利となります。

このゲームは、戦略的思考を必要とし、特にニム和を利用した必勝法が存在するため、数学的な要素も含まれています。

三山くずしは、シンプルながらも奥深い戦略性を持つゲームとして、多くの人に親しまれています。

ニムゲームとXORの関係

ニムゲームの基本ルール

ニムゲームは、複数の山から石を取り合うゲームで、以下の基本ルールがあります。

ルール	内容
プレイヤー数	通常は2人
山の数	複数の山(任意の数)
石の取り方	自分のターンに任意の山から1つ以上の石を取る
勝利条件	相手が石を取れなくなった時点で勝利

XOR演算とは

XOR(排他的論理和)演算は、2つのビットが異なる場合に1を返し、同じ場合には0を返す論理演算です。

具体的には、以下のように定義されます。

$A$ XOR $B$ = 1(AとBが異なる場合)
$A$ XOR $B$ = 0(AとBが同じ場合)

この演算は、ビット演算としても広く利用され、特にゲーム理論において重要な役割を果たします。

ニム和の概念

ニム和は、各山の石の数を2進数で表現し、XOR演算を用いて計算される値です。

具体的には、次のように計算します。

$Nim-Sum = a_{1} \oplus a_{2} \oplus a_{3}$

ここで、 $a_{1}, a_{2}, a_{3}$ はそれぞれの山の石の数です。

ニム和が0である場合、次のプレイヤーが必ず勝つことが保証されます。

ニム和を使った必勝法

ニム和を利用した必勝法は、相手のターンにニム和を0にすることを目指す戦略です。

具体的な手順は以下の通りです。

現在のニム和を計算する。
ニム和が0でない場合、相手が次に取る手を考慮し、自分の手を決定する。
自分の手を打った後、相手のニム和が0になるように石を取る。

この戦略を用いることで、相手に勝利のチャンスを与えず、ゲームを有利に進めることができます。

三山くずしにおける必勝戦略

ニム和を0にする手の見つけ方

三山くずしにおいて、ニム和を0にする手を見つけるためには、以下の手順を踏むことが重要です。

現在のニム和を計算する: 各山の石の数をXOR演算で計算し、ニム和を求めます。
各山の石の数を確認する: 各山の石の数を確認し、どの山から石を取るかを考えます。
ニム和を0にする手を特定する: ニム和が0でない場合、次のように計算します。

各山の石の数を $a_{i}$ とし、次の条件を満たす山を見つけます。
$a_{i} \oplus Nim-Sum < a_{i}$ となる山を選び、その山から石を取ります。

この手法により、相手のターンにニム和を0にすることができます。

相手がミスした場合の対応

相手が最適な手を打たずにミスをした場合、以下の戦略を取ることが重要です。

ミスを利用する: 相手がニム和を0にしなかった場合、次のターンで自分がニム和を0にする手を選びます。
相手の選択肢を制限する: 相手が次に取る手を考慮し、相手が有利な手を選べないように石を取ります。
勝利を確実にする: 相手がミスをした場合、できるだけ早く勝利条件を満たすように行動します。

相手が再びミスをすることを期待せず、確実に勝利を目指します。

ニム和が0のときの戦略

ニム和が0の状態では、相手が次のターンで必ず勝つことができます。

このため、自分がニム和を0にする手を選ぶことはできませんが、以下の戦略を考慮することが重要です。

相手のミスを待つ: 相手が最適な手を打たないことを期待し、ミスを待ちます。
相手の選択肢を狭める: 自分の手を打つ際に、相手が次に取る手を制限するように石を取ります。

これにより、相手がミスをする可能性を高めます。

心理戦を利用する: 相手にプレッシャーをかけるために、時間をかけて考えるフリをするなど、心理的な戦略を用いることも有効です。

このように、ニム和が0の状態でも、相手のミスを誘発する戦略を取ることで、勝利のチャンスを高めることができます。

Pythonで三山くずしを実装する

ゲームの初期設定

まず、ゲームの初期設定を行います。

三山くずしでは、3つの山にそれぞれ異なる数の石を配置します。

以下のコードでは、初期の石の数を設定します。

# 山の初期設定
mountains = [3, 5, 7]  # それぞれの山に3、5、7個の石を配置

プレイヤーの入力処理

次に、プレイヤーからの入力を処理します。

どの山から何個の石を取るかを入力してもらいます。

以下のコードでは、入力を受け付ける関数を定義します。

def get_player_input(mountains):
    while True:
        try:
            mountain_index = int(input("山の番号を選んでください (0, 1, 2): "))
            stones_to_take = int(input("取る石の数を入力してください: "))
            if mountains[mountain_index] >= stones_to_take > 0:
                return mountain_index, stones_to_take
            else:
                print("無効な入力です。再度入力してください。")
        except (ValueError, IndexError):
            print("無効な入力です。再度入力してください。")

ニム和の計算方法

ニム和を計算するための関数を定義します。

各山の石の数をXOR演算で計算し、ニム和を求めます。

def calculate_nim_sum(mountains):
    nim_sum = 0
    for stones in mountains:
        nim_sum ^= stones
    return nim_sum

勝敗判定の実装

勝敗を判定するための関数を定義します。

山に石が残っていない場合、ゲームが終了します。

def check_game_over(mountains):
    return all(stones == 0 for stones in mountains)

ゲームのループ処理

ゲームのメインループを実装します。

プレイヤーが交互に石を取り、勝敗を判定します。

def play_game():
    mountains = [3, 5, 7]  # 初期設定
    while True:
        print("現在の山の状態:", mountains)
        nim_sum = calculate_nim_sum(mountains)
        print("ニム和:", nim_sum)
        mountain_index, stones_to_take = get_player_input(mountains)
        mountains[mountain_index] -= stones_to_take
        if check_game_over(mountains):
            print("ゲーム終了！あなたの勝ちです！")
            break
        # コンピュータのターン
        # ニム和が0でない場合、最適な手を選ぶ
        if nim_sum != 0:
            for i in range(len(mountains)):
                if mountains[i] ^ nim_sum < mountains[i]:
                    stones_to_take = mountains[i] - (mountains[i] ^ nim_sum)
                    mountains[i] -= stones_to_take
                    print(f"コンピュータは山{i}から{stones_to_take}個の石を取りました。")
                    break
        else:
            # ニム和が0の場合、ランダムに石を取る
            for i in range(len(mountains)):
                if mountains[i] > 0:
                    mountains[i] -= 1
                    print(f"コンピュータは山{i}から1個の石を取りました。")
                    break
        if check_game_over(mountains):
            print("ゲーム終了！コンピュータの勝ちです！")
            break

完全なサンプルコード

以下に、三山くずしの完全なサンプルコードを示します。

これを実行することで、ゲームを楽しむことができます。

# 三山くずしの実装
def get_player_input(mountains):
    while True:
        try:
            mountain_index = int(input("山の番号を選んでください (0, 1, 2): "))
            stones_to_take = int(input("取る石の数を入力してください: "))
            if mountains[mountain_index] >= stones_to_take > 0:
                return mountain_index, stones_to_take
            else:
                print("無効な入力です。再度入力してください。")
        except (ValueError, IndexError):
            print("無効な入力です。再度入力してください。")
def calculate_nim_sum(mountains):
    nim_sum = 0
    for stones in mountains:
        nim_sum ^= stones
    return nim_sum
def check_game_over(mountains):
    return all(stones == 0 for stones in mountains)
def play_game():
    mountains = [3, 5, 7]  # 初期設定
    while True:
        print("現在の山の状態:", mountains)
        nim_sum = calculate_nim_sum(mountains)
        print("ニム和:", nim_sum)
        mountain_index, stones_to_take = get_player_input(mountains)
        mountains[mountain_index] -= stones_to_take
        if check_game_over(mountains):
            print("ゲーム終了！あなたの勝ちです！")
            break
        # コンピュータのターン
        if nim_sum != 0:
            for i in range(len(mountains)):
                if mountains[i] ^ nim_sum < mountains[i]:
                    stones_to_take = mountains[i] - (mountains[i] ^ nim_sum)
                    mountains[i] -= stones_to_take
                    print(f"コンピュータは山{i}から{stones_to_take}個の石を取りました。")
                    break
        else:
            for i in range(len(mountains)):
                if mountains[i] > 0:
                    mountains[i] -= 1
                    print(f"コンピュータは山{i}から1個の石を取りました。")
                    break
        if check_game_over(mountains):
            print("ゲーム終了！コンピュータの勝ちです！")
            break
# ゲームを開始
play_game()

このコードを実行すると、プレイヤーとコンピュータが交互に石を取り合う三山くずしのゲームが楽しめます。

コンピュータが絶対に勝つ戦略を実装する

コンピュータの手を決定するアルゴリズム

コンピュータが絶対に勝つための戦略は、ニム和を利用したアルゴリズムに基づいています。

具体的には、以下の手順で手を決定します。

ニム和の計算: 現在の山の状態からニム和を計算します。
ニム和が0でない場合: ニム和が0でない場合、最適な手を選びます。
ニム和が0の場合: ニム和が0の場合は、ランダムに石を取るか、相手の手を制限するように行動します。

このアルゴリズムにより、コンピュータは常に最適な手を選ぶことができます。

ニム和を0にする手の選択

ニム和を0にする手を選ぶためには、次のようにします。

ニム和を計算: 現在の山の状態からニム和を計算します。
各山の石の数を確認: 各山の石の数を確認し、次の条件を満たす山を見つけます。

$a_{i} \oplus Nim-Sum < a_{i}$ となる山を選び、その山から石を取ります。

石を取る: 選んだ山から、ニム和を0にするために必要な数の石を取ります。

以下は、ニム和を0にする手を選ぶためのサンプルコードです。

def choose_optimal_move(mountains):
    nim_sum = calculate_nim_sum(mountains)
    for i in range(len(mountains)):
        if mountains[i] ^ nim_sum < mountains[i]:
            stones_to_take = mountains[i] - (mountains[i] ^ nim_sum)
            return i, stones_to_take
    return None  # 最適な手が見つからない場合

プレイヤーの手に対するリアクション

プレイヤーが手を打った後、コンピュータは次のようにリアクションします。

プレイヤーの手を受け入れる: プレイヤーが選んだ山と取った石の数を受け入れ、山の状態を更新します。
勝敗判定: プレイヤーの手によってゲームが終了したかどうかを判定します。
コンピュータのターン: プレイヤーの手が有効であれば、コンピュータのターンに移ります。

コンピュータは、前述のアルゴリズムに従って手を決定します。

以下は、プレイヤーの手に対するリアクションのサンプルコードです。

def player_turn(mountains):
    mountain_index, stones_to_take = get_player_input(mountains)
    mountains[mountain_index] -= stones_to_take
    if check_game_over(mountains):
        print("ゲーム終了！あなたの勝ちです！")
        return True  # ゲームが終了した
    return False  # ゲームは続行

コンピュータが負ける場合の処理

コンピュータが負ける場合は、以下のように処理します。

ニム和が0の場合: コンピュータがニム和が0の状態で手を打つ場合、最適な手を選ぶことができません。

この場合、ランダムに石を取るか、相手の手を制限するように行動します。

相手のミスを待つ: コンピュータは、相手がミスをすることを期待し、次のターンで勝利を目指します。
ゲームの進行: コンピュータは、相手の手に対してリアクションを行い、ゲームを続行します。

以下は、コンピュータが負ける場合の処理のサンプルコードです。

def computer_turn(mountains):
    nim_sum = calculate_nim_sum(mountains)
    if nim_sum == 0:
        # ニム和が0の場合、ランダムに石を取る
        for i in range(len(mountains)):
            if mountains[i] > 0:
                mountains[i] -= 1
                print(f"コンピュータは山{i}から1個の石を取りました。")
                break
    else:
        mountain_index, stones_to_take = choose_optimal_move(mountains)
        mountains[mountain_index] -= stones_to_take
        print(f"コンピュータは山{mountain_index}から{stones_to_take}個の石を取りました。")