割り箸 (手遊びゲーム)

**割り箸（わりばし）**は２人(以上)で行う手遊びゲームであり、プレイヤーはそれぞれの手のいくつかの指を伸ばし、交互に手をタップすることによってそれらの本数を変化させる形で遊ぶ。割り箸は組合せゲームの一種であり、どのような局面であってもそこからの最適な戦略が知られているという意味では解決している。

## ルール
この公式的なルールは「ロールオーバー」と呼ばれ、以下で説明するように、手の指の合計が５本を超える場合、そこから５を引いた本数の指を広げる。
# 各プレイヤーは自身の手の各々で指を１本広げた状態からゲームをスタートする。最初のプレイヤーからターンは時計回りに進む。
# 自身のターンで、プレイヤーは「攻撃」か「分割」のいずれか一方を行う。
# 「攻撃」では、プレイヤーは自身の「生きている手」、すなわち指が１本以上広げられている手のうちの１つを使い、敵の生きている手を打つ。打たれた相手の手の指の本数は、打つのに使用された手の指の本数分だけ増加する。
# 各プレイヤーのいずれかの手で指がちょうど５本広げられる場合、その手は「死ぬ」。これは０本の指を広げる、すなわち拳を閉じることや、死んだ手をプレイヤー自身の背後に隠すことなどによって表される。
# いずれかの手が指５本を超える場合、そこから５を引いた本数の指を広げる。例えば、広げられた指が４本の手が、広げられた指が２本の手を攻撃した場合、合計で指は６本となるが、そのとき５本の指が自動的に差し引かれ、攻撃された手では１本の指を広げることになる。（プレイヤーのいずれかの手の指が５本以上となった時点でその手を「死んだ手」と見なすようなバリエーションも存在する。）
# 「分割」では、プレイヤーは自身の２つの手を互いに打ち、広げられた指を片方の手から他方の手へ好きな本数移動できる。ただし、単に２つの生きている手の指の本数を交換するような移動はできない。例えば、プレイヤーが広げられた指が各々２本と３本の生きている手２つを持つ場合、広げられた指が各々１本と４本の生きている手２つを持つという状態に移動することはできるが、広げられた指が各々２本と３本の生きている手２つを持つ状態(移動前とは手の左右が異なる)に移動することはできない。また、このように生きている手同士の指の本数を「分割」によって移動する場合、この移動を特に「転送」という。
# プレイヤーは「分割」のルールに従う限りにおいては、「分割」を用いて死んだ手を生き返らせることもできる。この移動を特に「分裂」という。例えば、プレイヤーが死んだ手を１つと、指が３本広げられた生きている手を１つもつ場合、広げられた指が各々１本と２本の生きている手２つを持つという状態に移動することができる。ただし、敵の手を「攻撃」を用いて生き返らせることはできない。それゆえ、２つの手がともに死んだプレイヤーはこれ以上ゲームを続けられず、プレイから除外される。
# プレイヤーは自身の手を死なせることはできない。例えばプレイヤーが、広げられた指が各々１本と２本の生きている手２つを持つ場合に、（「分割」を用いて）広げられた指が３本の生きている手１つと死んだ手１つを持つという状態に移動することはできない。
# プレイヤーは、すべての対戦相手が(同時に２つの「死んだ手」を持つことによって)プレイから除外された場合に勝利となる。

## 略記
割り箸の状態は４桁のコード[ABCD]で簡略的に表すことができる。AとBはターンプレイヤーの手(広げられた指の数の昇順)を表し、CとDはターンプレイヤーでないプレイヤーの手(広げられた指の数の昇順)を表す。単一で他と異なる状態が、誤って２つのコードで表されることがないように、各プレイヤーの手を指の昇順で表記することが重要である。例えば、[1032]というコードは許されず、[0123]と表記する必要がある。
それゆえ、公式ルール「ロールオーバー」においては、スタートの状態は[1111]であり、その次の状態は[1211]となる。また、[1211]の次の状態は[1212]か[1312]となる。各状態を４桁の数として扱う場合、最小の状態は[0000]であり、最大の状態は[4444]である。

この略記方法はより多くのプレイヤーがいるゲームに対しても容易に拡張できる。３人のプレイヤーがいるゲームでは、６桁の数によって表され（例. [111211]）、左端から２桁ずつの数字の各ペアは、プレイヤー１人ずつを表し、各ペアはプレイヤーがいつ自分のターンを行うかに基づいて並べられている。左端のペアはまさに今ターンを行おうとしているプレイヤーの手を表し、中央のペアはその次にターンを行うプレイヤーの手を表す、などである。右端のペアは自分のターンが来るまでに最も待たなければならないプレイヤーの手を表す（通常、そのプレイヤーはターンを行ったばかりであるため）。

## 移動
基本ルール(「ロールオーバー」)のもとで最大で14の可能な状態移動が存在する。（「分裂」と「転送」を合わせて「分割」と呼んでいる。）
* ４つの「攻撃」（A-C, A-D, B-C, B-D）
* ４つの「分裂」（02-11, 03-12, 04-13, 04-22）
* ６つの「転送」（13-22, 22-13, 14-23, 23-14, 24-33, 33-24）

しかし、１ターン中に行える状態移動はその内の５つ以下しかない。

例えば、状態[1312]は [2213], [1313], [2413], [0113], [1222] のいずれかの状態に移動する。

## ゲームの長さ
ゲームの最小手数は５手である。そのようなゲームプレイ(状態遷移)の例は１つ存在する。
# 1111 1211 1312 0113 1401 0014
各ターンで、それまでに到達した状態には戻らないように移動する場合の、最長のゲームは９手詰みである。そのようなゲームプレイ(状態遷移)の例は２つ存在する。
# 1111 1211 1212 2212 2322 0223 0202 0402 0104 0001
# 1111 1211 1212 2312 2323 0323 0303 0103 0401 0004
再訪ありの場合(すでに到達した状態に再び移動してもよい場合)のゲームの最長手数は分かっていない。

## 状態数
ロールオーバーにおいて、手が死ぬときの指の本数を「ロールオーバー量」と呼ぶ。基本ルールでは、ロールオーバー量が５であるから、箸は基数５のゲームである。プレイヤーが２人の場合の各状態は４桁の数で表され、0000から4444まで（基数５で）数えると625個の状態がある。しかし、これらの状態のほとんどが間違った表記である（例. 0132 ,1023, 1032）。それらは一見異なるように見えるが、ゲームプレイにおいては機能的に同じである（ここで「ゲームプレイにおいて機能的に同じ」というのは、プレイヤーA,Bという区別に注目するのではなく、各ターンにおけるターンプレイヤーとターンプレイヤーでないプレイヤーという区別に注目した上で、手の対称性から同じ状態を表すということを意味している。例えば、0123はターンプレイヤーの手が01、ターンプレイヤーでないプレイヤーの手が23であることを意味するが、先攻のプレイヤーAと後攻のプレイヤーBが各々01,23の手をもつ場合と、各々23,01の手を持つ場合の２つの場合を含んでいることに注意）。

機能的に異なる状態の数を知るためには、機能的に異なるペアの数を単に２乗すればよい。機能的に異なるペアは15個（00, 01, 02, 03, 04, 11, 12, 13, 14, 22, 23, 24, 33, 34, 44）存在し、いずれのプレイヤー（ターンプレイヤーとターンプレイヤーでないプレイヤー）もこれらのペアのいずれかの状態をとるから、単に15×15で、225個の機能的に異なる状態が得られる。
* 余分なもの(機能的に重複するもの)を含めると625個の状態がある。
* 機能的に異なる状態は225個ある。
* 到達可能な状態は204個ある。
21個の到達不可能な状態（0000, 0100, 0200, 0300, 0400, 1100, 1101, 1200, 1300, 1400, 2200, 2202, 2300, 2400, 3300, 3303, 3400, 3444, 4400, 4404, 4444）が存在する。
# このうち15個はターンプレイヤーの手が異なる１５個のペア（00, 01, 02, 03, 04, 11, 12, 13, 14, 22, 23, 24, 33, 34, 44）のいずれかとなり、もう一方のプレイヤーが負けている(つまり00の手をもつ)という状態である。問題は、負けたプレイヤーがちょうど自分のターンを行ったプレイヤーとなっている（すなわち“00”が右側にある）ことである。プレイヤーは自身のターンに負けることはできないため、これらの状態は明らかに到達不可である。
# 到達不可能な２１個の状態のうちの４個（1101,2202,3303,4404）はターンプレイヤーが[kk]という手をもち、もう一方のプレイヤーが[0k] という手を持つ状態である(ただし、０r の値に応じて以下のようになる。

## 一般化
割り箸は(p, h, r)型ゲームに一般化できる。ここで、p はプレイヤーの人数、h はそれぞれのプレイヤーの手の数、r はロールオーバー量である。

### 縮退したケース
ロールオーバー量が１のゲームでは、値が１の手は値が０の手（すなわち死んだ手）になり、全ての手が開始時点で死ぬことになるため、これはとるに足らないゲームである。プレイヤーが１人以下でのゲームはゲームではなく、パズルやセルオートマトンである。

ロールオーバー量が２のゲームは、分割を行えず、ロールオーバーとカットオフルールが同じゲームとなるため、縮退している。また、手への攻撃はそのまま相手の手を殺すことになるため、プレイヤーが相手を攻撃したとき、相手のもつ生きている手の数は１つ減少する。ゲームにおける到達可能な状態は
*  p = 2  のとき 2h 個
*  p \geq 3  のとき \sum_{k=2}^p h^k{p \choose k} 個
存在する。また、 p = 2  のとき、ゲームの長さは ph -1  である。プレイヤー２人のゲーム(すなわち  p = 2 )では、任意の h に対して先攻が勝利する、と強解決されている。この縮退したケースを「切り株」ルールを採用してプレイすると、「半分」ルールを採用した上で、ロールオーバー量が４、かつ各プレイヤーが全ての手で２本の指を広げた状態からスタートするようなゲームと等価なゲームとなる。

### ２人のプレイヤー
各プレイヤーが手を１つだけもつとき（h = 1）、分割は起こり得ず、各プレイヤーの行える移動は１つしかないため、ゲームは縮退している。ロールオーバー量が r のとき、ゲームにおける k 回の移動の後（すなわちゲーム開始から k ターン後）の各状態はタプルにより表される \left(F_{k + 2} \bmod r, F_{k + 1} \bmod r \right)。ここで、F_k は F_0 = 0, F_1 = 1 のときの k 番目のフィボナッチ数である。ゲームが終了するまでの到達可能状態数は、F_{k + 2} が r で割りきれるような最小の非負整数 k に対し、k + 1 で与えられる。このゲームは r の値とフィボナッチ数の分割可能性に依って、いずれかの側が勝利するとして強解決されている。また、ゲームの長さは k である。

各プレイヤーが１より多くの手を持ち（h > 1）、それぞれの手のロールオーバー量が r \left(> 2 \right) であるとき、
* 余分なもの(機能的に重複するもの)を含めると r^{2h} 個の状態がある。
* {r + h - 1 \choose h}^2個の機能的に異なる状態がある。
* {r + h - 1 \choose h}^2 - \left({r + h - 1 \choose h} + (r - 2) + (h - 1) + 2\right) 個の到達可能な状態がある。
ロールオーバー量が r であるため、箸は基数 r のゲームである。それぞれの状態は 2h 桁の数で表される。基数 r で 2h 桁の全ての数を列挙すると r^{2h} 個の状態が得られる。しかし、これらのほとんどは誤った表記である（例.h = 3 における 001210, 010120, 100021）。それらは一見異なるように見えるがゲームプレイにおいては機能的に同じものである。機能的に異なる状態の数を知るためには、機能的に異なるペアの数を２乗すればよい。ロールオーバー量 r、手の数 h に対して、{r + h - 1 \choose h}個の異なるペアが存在し、各プレイヤーはこれらのペアのいずれもとることができるから、結果の値を２乗するだけで、{r + h - 1 \choose h}^2個の機能的に異なる状態が得られる。

{r + h - 1 \choose h} + (r - 2) + (h - 1) + 2 個の到達不可能な状態がある。

# これらの内の {r + h - 1 \choose h} 個は、ターンプレイヤーの手が {r + h - 1 \choose h} 個の異なるペアのいずれかとなり、 もう一方のプレイヤーが負けているという状態である。問題は、負けたプレイヤーがちょうどターンを行ったプレイヤーとなっていることである。プレイヤーは自身のターンで負けることはできないため、これらの状態は明らかに到達不可能である。
# 到達不可能な状態のうちの r - 2 個は、ターンプレイヤーが 0  なる値 k の手を  h  個もち、もう一方のプレイヤーは値 k の生きている手を１つだけ持つ状態である。ターンを行った値 k の生きている手を１つだけもつプレイヤーは、直前のターンで分割は行えず、それゆえそのプレイヤーは自身のただ１つの生きている手[00...0k]を用いて攻撃したことになるが、相手を [00...0k]を用いて攻撃した結果相手が値 k の手を h 個もつためには、死んだ手に攻撃しなければならないため、これは不可能である。したがって、この状態には到達不可能である。
# 到達不可能な状態のうちの h - 1 個は、ターンプレイヤーが値 r - 1 の手を h 個もち、もう一方のプレイヤーが値 r - 1 の生きている手を k 個（それ以外の手はすべて死んだ手）もつ状態である（ただし 0 ）。これらの状態が到達可能であると仮定すると、プレイヤーは分割によって値 r - 1 の手を h 個もつ状態[(r-1)(r-1)...(r-1)]に到達することはできないため、ターンプレイヤーの手は自身のターンの直前に相手の攻撃によって[(r-1)(r-1)...(r-1)]となっている必要がある。しかし、相手の生きている手は全て値 r - 1 の手であり、そのうちの１つを用いて攻撃した結果として現在のターンプレイヤーが値 r - 1 の手を h 個もつためには、死んでいる手が攻撃される必要があるので、これは不可能である。したがって、これらの状態は到達不可能である。
# 両プレイヤーが値 r - 1 の手を h 個もつという状態も上記ポイント３と同様の理由で到達不可能である。
# ターンプレイヤーが値 r - 2 の手を１個と 値 r - 1 の手を h - 1 個もち、もう一方のプレイヤーが値 r - 1 の手を h 個もつという状態は、ポイント４で挙げた状態からのみ到達可能であるが、ポイント４の状態は初期状態から到達不可能であるため、この状態も同様に到達不可能である。
ポイント２と３で挙げた状態のうち、「ターンプレイヤーが値１の手を h 個もち、もう一方のプレイヤーが値１の生きている手を１つだけもつという状態」の１つを除いて、「自殺」ルールを採用すると到達可能である。「ターンプレイヤーが値１の手を h 個もち、もう一方のプレイヤーが値１の生きている手を１つだけもつという状態」は「自殺」ルールと「メタ」ルールをともに採用してプレイしたゲームにおいては到達可能である。ポイント４と５で挙げた２つの状態は「サンズ」ルールを採用すると、ポイント４の状態が初期状態であるため、到達可能であるが、最初の２ターン以降で、それら２つの状態に到達することはできない。以上のことから、「自殺」「メタ」「サンズ」をすべて採用してプレイすると、合計で {r + h - 1 \choose h} 個の到達不可能な状態と {r + h - 1 \choose h}^2 - {r + h - 1 \choose h} 個の到達可能な状態が存在する。

### 2人より多くのプレイヤー
ロールオーバー量が5、手の数が2である場合。
* 2人のプレイヤーでは、204個の到達可能状態がある。
* 3人のプレイヤーでは、3337個の到達可能状態がある。
* 4人のプレイヤーでは、25000個以上の到達可能状態がある。

## 脚注



## 関連項目

* 手を用いた遊び

## 外部リンク

* 「割りばしゲーム」が後手必勝であることを確認する