棒消しゲームの必勝法
棒消しゲームとは
2人のプレイヤーがルールに沿って交互に棒を消していき、最後の棒を消したプレイヤーが勝ちというゲーム。
初期配置として、図のようにいくつかの棒が数段に分かれて並んでいる。
棒を消すルール
- 1本以上消さないといけない
- 消せる棒は同じ行のもののみ
- すでに消されている棒を超えて消すことはできない
例えば、下図のような盤面だと、2段目は左右の棒を同時に消すことはできない。
必勝法
この棒消しゲームには必勝法がある。今回はその必勝法を書いていく。
用語の定義
この記事で使う用語を定義していく。
グループ
一度に消すことができる棒の集まり。
図Aだと、 3, 1, 1, 7 本からなる4つのグループがあることになる。
図Bだと、 1, 1, 1, 2, 2, 1 本からなる6つのグループがあることになる。
評価値
盤面に対して、各グループの本数のビット列で排他的論理和をとったものを評価値という。
図Aだと
グループが1つもないときの評価値は
必勝法について
初期盤面の評価値が
戦術としては、評価値が
その戦術で必勝法になることを示すには、以下の3つを示さないといけない。
- A: 評価値が
0 0 - B: 評価値が
0 0 - C: 棒が存在しない盤面の評価値は
0
証明
A の証明
あるグループ
グループ
が成り立ち、式変形をして、
となる。ここで、手番プレイ後の盤面の評価値
となるが、ルール上最低でも1本は消さないといけないため
と
B の証明
評価値が
評価値の計算方法から、
アイデアとしては、
そうすることで、グループ
C の証明
棒がないということは、グループが1つもないということなので、その盤面の評価値は 0 となる。
対戦ゲーム
以上の証明で、棒消しゲームは必勝法があるゲームということが分かった。
対戦相手のコンピュータがその必勝法を使ってくる、対戦プログラムを書いてみた。
対戦プログラム
from dataclasses import dataclass
import random
import sys
# 入力エラーの例外
class InputError(Exception):
pass
# グループの本数を管理するクラス
@dataclass(frozen=True)
class Group:
count: int
def __init__(self, count: int) -> None:
if count <= 0:
raise ValueError("Non positive number.")
object.__setattr__(self, "count", count)
def __str__(self) -> str:
return str(self.count)
# ゲーム状態を管理するクラス
class Game:
groups: list[Group]
def __init__(self, groupCount: int, minCount: int, maxCount: int) -> None:
"""
Args:
groupCount int: グループの数
minCount int: 各グループの最小本数
maxCount int: 各グループの最大本数
"""
if groupCount <= 0 or minCount <= 0 or maxCount <= 0:
raise ValueError("Game init args are wrong.")
# ランダムに盤面を作成する
groups = []
for _ in range(groupCount):
groups.append(Group(random.randint(minCount, maxCount)))
self.groups = groups
# プレイを実行する
def play(self, before: int, afterA: int, afterB: int) -> None:
"""
Args:
before int: 削除対象のグループの本数
afterA int: 新規にできるグループの本数
afterB int: 新規にできるグループの本数
"""
# 入力値が不正の時
if before < 1 or afterA < 0 or afterB < 0 or before <= afterA + afterB:
raise InputError(f"Value is wrong.")
# 削除対象グループの探索
for index, group in enumerate(self.groups):
if group.count == before:
# 削除対象グループの削除
del self.groups[index]
break
else:
# 削除対象グループが鳴ければ例外を出す
raise InputError(f"No exist {before}.")
# 新規にできたグループの追加
if afterA > 0:
self.groups.append(Group(afterA))
if afterB > 0:
self.groups.append(Group(afterB))
# 評価値の計算
def evaluete(self) -> int:
e = 0
for group in self.groups:
e ^= group.count
return e
# 勝敗判定
def isWin(self) -> bool:
return len(self.groups) == 0
def __str__(self) -> str:
return str(list(map(lambda x: str(x), self.groups)))
# 必勝法通りプレイする関数
def getBestStrategy(game: Game) -> (int, int, int):
x = game.evaluete()
n = x.bit_length() - 1
# 必勝盤面でないときはランダムで棒を消す
if x == 0:
target = game.groups[random.randint(0, len(game.groups) - 1)].count
afterA = random.randint(0, target - 1)
afterB = random.randint(0, target - afterA - 1)
return target, afterA, afterB
# 必勝法通り棒を消す
target = 0
for group in game.groups:
if group.count & 2 ** n != 0:
target = group.count
break
else:
raise ValueError(f"No exist.")
return target, target - 2 ** n, x - 2 ** n
def main(game: Game):
print(game)
# 手番の決定
print("Are you first move? [y/n]: ")
move = input()
if move == "y":
turn = 0
elif move == "n":
turn = 1
else:
exit()
# ゲームの実行
while True:
# 挑戦者のターン
if turn == 0:
if game.evaluete() == 0:
# 負けが決まっているときのメッセージ
print("----- player turn (YOU LOSE!!!) -----")
else:
print("----- player turn -----")
print(game)
try:
before, afterA, afterB = map(int, input().split())
except KeyboardInterrupt:
break
except:
print("input error!")
continue
try:
game.play(before, afterA, afterB)
except InputError:
print("input error!")
continue
turn = 1
if game.isWin():
print("you win")
break
# 必勝法を使ってくるコンピュータのターン
elif turn == 1:
print("----- computer turn -----")
print(game)
before, afterA, afterB = getBestStrategy(game)
print(str(before) + " " + str(afterA) + " " + str(afterB))
game.play(before, afterA, afterB)
turn = 0
if game.isWin():
print("computer win")
break
else:
raise ValueError(f"Something wrong.")
# ゲーム盤面の作成
args = sys.argv
game = Game(
int(args[1]), # グループの数
int(args[2]), # 各グループの最小本数
int(args[3]), # 各グループの最大本数
)
# ゲーム開始
main(game)
使い方
実行は引数に3つを指定する。
- 第1引数: グループの数
- 第2引数: 各グループの最小本数
- 第3引数: 各グループの最大本数
例では、初期盤面として4から6本からなるグループが3つ作られる。
$ python3 main.py 3 4 6
初期盤面が表示され、最初に先攻か後攻かを決められる。先攻なら y 、後攻なら n を指定する。
['4', '4', '5']
Are you first move? [y/n]:
y
手番時にプレイ内容を以下のように指定する。
- 1つ目の数字: 削除対象にするグループの本数
- 2つ目の数字: 削除後にできる1つ目のグループの本数
- 3つ目の数字: 削除後にできる2つ目のグループの本数
例では、5本からなるグループを 0 本と 0 本のグループに分ける(全消し)するプレイになる。
----- player turn -----
['4', '4', '5']
5 0 0
コンピュータがプレイする。必勝法が使える盤面なら必勝法を、そうでないときはランダムでプレイする。
----- computer turn -----
['4', '4']
4 1 0
----- player turn -----
['4', '1']
4 1 0
最終的に、全部のグループがなくなったら勝敗が決まる。
----- player turn -----
['4', '1']
4 1 0
----- computer turn -----
['1', '1']
1 0 0
----- player turn -----
['1']
1 0 0
you win
必勝法への挑戦
もしコンピュータの方に必勝盤面が渡ると、下記の表示に変わって勝てないことを示される。
その表示が出ないように、最初の手番選択と、各手番のプレイを間違えないように進めること(必勝法で進めていくこと)に挑戦してほしい。
----- player turn (YOU LOSE!!!) -----
亜種ルール
最後の棒を消したプレイヤーが勝ちというルールにしたが、最後の棒を消したプレイヤーが負けというルールも存在する。実はその場合でも、前述した方法をほぼ同じ方法で必勝法があることが示せる。
1つのグループを除いて全てのグループの本数が1本になるまでは、前述した必勝法でプレイすればいい。その状況になれば、2本以上あるグループを
1つのグループを除いて全てのグループの本数が1本になる、という状況は盤面の評価値が
おわりに
このゲームの存在自体は中学生の頃に知り、どこかのサイトでこの記事と同じ必勝法が解説されていた。そのサイトでは方針だけで、数学的な証明がなかったので、ちゃんと証明したいなと思っていたら、めちゃくちゃ時が経ってしまっていた。
証明だけではなく対戦プログラムも書いたので、是非皆さん必勝法を使って対戦してみてもらいたい。
余談
A の証明がパッと思いつかなかったので Claude Sonnet 4 に聞いてみたら、証明の概要を書いてくれた。プロンプトとしては、この記事の「棒消しゲームとは」と「必勝法」という章をそのまま渡してやっただけ。最初出されたものが8割り程度の出来栄えだったが、部分的に再度聞き返すことで詳細の説明もしてくれた。どうせ無理だろうと高を括っていたが、想像以上にできていたので動揺した。
Discussion