指で数字を増やして5を目指すゲームが後手必勝であることを示す
指で数字を増やして5を目指すゲームとは
子供の頃やってたこれらの遊び、皆様の地元ではなんて呼んでましたか？ちょっと仕事で参考にしたいので、県名とかも教えてくれると嬉しいです！
— やしろあずき@1日目M-03a (@yashi09) 2017年7月5日
ちなみにやしろあずきの地元では
①「これやろうぜ！」
②「これやろうぜ！」
③「これやろうぜ！」
④「これやろうぜ！」
でした。アホか。 pic.twitter.com/pJaurIQUls
これの③です。
正式な名称はないようで、Wikipediaには「数字を増やす遊び」という名前で紹介されているようです。その記事によれば 割り箸・マッチ・グリンピース・戦争・プラフィン という地域名があるらしいです。
ゲームのルール
このゲームは地域・人によってルールの違いがあり、これが正当といったルールはありません。そのため、タイトルの「後手必勝」は自分の場合での「後手必勝」であり、あなたのルールではそうでないかもしれません。
それを踏まえて、この記事でのルールを説明しますが、面倒なのでルールはWikipediaから引用します。
- 先攻、後攻を決める。
- 参加者は向き合い、両者人差し指を出して相手に見せる（これで両者とも両手は人差し指のみなので、両手は「1」である）。
- 先攻が選択か、分身を行う(2人以上で行う場合は、先攻の時計回り又は反時計回りで順番に行う。この際の選択は自分以外であれば誰の手でもよい)。
- 後攻が同様に行う。
これを繰り返し、先に相手の両手を消滅させた者が勝ちとなる。
- 選択
- 両手のどちらかで、自分か相手の手のいずれか一つに触れるなどして選ぶ。
- 選ばれた手は、選んだ手の指の数が足される。「3」の手が「1」の手を選んだのなら、選ばれた手は「4」となる。
- 分身
- 指の本数が「2」以上であり片手が消滅していた場合に、指の本数を好きに分けることができる。
- もし、指の本数が「5」ならば、片手に「1 - 4」を分け、もう一方をその残りの数とする。
- 消滅
- 指の本数が「6」以上になった場合、その手は消滅する。
- 指の本数が「5」丁度になった場合、その手は消滅する。
また、その他のルールとして以下を追加します。
分身は両手が出ている場合も行える。つまり指の合計本数が変わらなければ右と左で数をかえてもよい。
また、「2」と「3」の手を「3」と「2」にするような自分の手の間での単純交換は禁止します。
表記法
以下ではゲームの状態をプレイヤーと手の状態のタプル (プレイヤー, 先攻手1, 先攻手2, 後攻手1, 後攻手2) として表現します。プレイヤーは A と B で表現し、Aは先手でBは後手です。初期状態は (A,1,1,1,1) です。
また、簡単のため、例えば (A,1,2,1,1) と (A,2,1,1,1) は同じものとみなします。前者の sorted な表記を「正規化された」ものと呼びます。
探索の手法
TL;DR: 状態遷移図を全列挙し、終了状態からボトムアップで解析をします。
- 必勝状態リストを用意する。
- 全ての手の (正規化された、有効な) 状態を生成する。
- それぞれに関して状態遷移先を求める。
- 以下をループする。必勝状態リストが変更されなくなれば終了。
- 全ての状態について以下を行う。
- 状態遷移先の中に必勝状態のものがあるならば、この状態を自分の必勝リストに追加。
- 状態遷移先が全て相手の必勝状態ならば、この状態を相手の必勝リストに追加。
- 全ての状態について以下を行う。
終了時に必勝リストに無いものはお互いが最善手を取り合っても終了しない「ループ」を意味します。
検証用コード
verify してないので間違ってるかもしれません。
from itertools import product NUMBER_OF_FINGER = 5 # 指の本数。人間の場合は 5。 """ 「消滅」についての処理 """ def trunc(i): # 指の数(5) 以上の場合は消滅 if i >= NUMBER_OF_FINGER: return 0 # return i % 5 else: return i """ 状態表現を正規化する。入出力は状態表現の集合(set) 例: (A,0,1,3,2) -> (A,0,1,2,3) """ def normalize(hand_set): normalized = set() for (player, a1, a2, b1, b2) in hand_set: a = (a1, a2) if a1 < a2 else (a2, a1) b = (b1, b2) if b1 < b2 else (b2, b1) normalized.add((player,) + a + b) return normalized """ AとBの手を反転。 """ def flip(hand): (player, a1, a2, b1, b2) = hand return (player, b1, b2, a1, a2) """ 現在の手から状態遷移先を求める """ def get_valids(hand): # 後手の場合は先後を反転させて扱う、後で戻す (☆) if hand[0] == 'B': hand = flip(hand) (player, a1, a2, b1, b2) = hand # 有向手のコレクション valids = set() # 相手の手 opponent = 'B' if player == 'A' else 'A' # 自分の手が非0 ∧ 自分の手が非0 → 相手を攻撃 # 自分の左右 × 相手の左右 で 4パターン if a1 != 0 and b1 != 0: valids.add((opponent, a1, a2, trunc(a1 + b1), b2)) if a2 != 0 and b1 != 0: valids.add((opponent, a1, a2, trunc(a2 + b1), b2)) if a1 != 0 and b2 != 0: valids.add((opponent, a1, a2, b1, trunc(a1 + b2))) if a2 != 0 and b2 != 0: valids.add((opponent, a1, a2, b1, trunc(a2 + b2))) # 分裂ルール # 手が (2,3) の場合 (1,4), (3,2), (4,1) という手が生成できる for i in range(max(-(NUMBER_OF_FINGER-1-a2), -a1), min(a2, NUMBER_OF_FINGER-1-a1)): # (1,1) => (1,1) と言ったのを弾く if i == 0: pass # (2,3) => (3,2) と言った単純交換は禁止 elif (a1+i,a2-i) == (a2,a1): pass else: valids.add((opponent, a1 + i, a2 - i, b1, b2)) # それぞれの遷移先を正規化しまとめる。 valids = normalize(valids) # ☆ if player == 'B': valids = map(flip, valids) # 結果はリスト return list(valids) """ 探索する """ def search(): # 必勝手順がある場合保存される winner_table = dict() # 状態遷移表 trans = dict() # 全状態について状態遷移表をつくる for hand in product('AB', range(5), range(5), range(5), range(5)): (p,a1,a2,b1,b2) = hand if a1 <= a2 and b1 <= b2: if (a1,a2) != (0,0) and (b1,b2) != (0,0): trans[hand] = get_valids(hand) elif (a1,a2) == (0,0): winner_table[hand] = 'B' # B勝ち elif (b1,b2) == (0,0): winner_table[hand] = 'A' # A勝ち # 必勝手順をボトムアップ探索 # winner_table が更新されなくなるまで繰り返し実行 changed = True while changed: changed = False for (source, target) in trans.items(): # 既に勝者が確定している場合はスキップ if source in winner_table: continue player = source[0] # 状態遷移先の勝者情報を取得 results = set(map(lambda t: winner_table.get(t, 'X'), target)) # 状態遷移先に自分が勝者である手がある場合はそれを選べばよいので、 # この手については自分が勝者であることが確定 if player in results: changed = True winner_table[source] = player # 状態遷移先が相手の必勝しかない場合(⇔ 自分(player)も未確定(X)もない場合)、 # 自分が必敗であることが確定 elif 'X' not in results: changed = True winner_table[source] = results.pop() # これは相手の文字となる return (winner_table, trans) if __name__ == '__main__': (winner_table, trans) = search() # 初期状態の勝者を出力 print(winner_table.get(('A',1,1,1,1), 'Loop'))
結果
B
はい。
状態遷移表を出力する。
これだけではつまらないので途中の状態遷移表をHTMLで出力します。 赤が先手必勝手順が存在する状態。青が後手必勝手順が存在する状態を意味します。
# main 部 patch if __name__ == '__main__': def hand_str(hand): return '({},{},{},{},{})'.format(*hand) def id_str(hand): return '{}{}{}{}{}'.format(*hand) (winner_table, trans) = search() print(""" <html><head> <style> .A { color:red; } .B { color:blue; } .X { color:gray; } </style> </head> """) print(""" <body> <p>Notation: (Turn, A's left hand, A's right hand, B's left hand, B's right hand)</p> <ul> <li><span class="A">Red: A will win</span></li> <li><span class="B">Blue: B will win</span></li> <li><span class="X">Gray: Maybe Loop</span></li> </ul> <p><a href="#A1111" style="color:green;">Start Game!</a></p> """) for source in product('AB', range(5), range(5), range(5), range(5)): (player, a1, a2, b1, b2) = source if not (a1 <= a2 and b1 <= b2) or (a1, a2, b1, b2) == (0,0,0,0): continue if source in trans: targets = trans[source] target_str = ', '.join(map(lambda s: '<a class="{}" href="#{}">{}</a>'.format(winner_table.get(s, 'X'), id_str(s), hand_str(s)), targets)) print('<a class="{}" name="{}">{}</a> -> {}<br>'.format(winner_table.get(source, 'X'), id_str(source), hand_str(source), target_str)) elif source in winner_table: print('<a class="{}" name="{}">{}</a> -> {} Wins!<br>'.format(winner_table.get(source, 'X'), id_str(source), hand_str(source), winner_table.get(source, 'X'))) print("</body></html>")
Preview
More
様々なルールが存在すると書きましたが、先ほどのコードをルールに合わせて修正すると色々検証することが出来ます。例えば、6以上の時に消滅せずに剰余をとるようにするとループになってしまいます。色々遊んでみるとおもしろいです。
余談
状態遷移図を Graphviz で出そうとしたら超巨大になってしまうのでやめたほうがいいです。
