割り箸 (手遊びゲーム)
割り箸(わりばし)は2人(以上)で行う手遊びゲームであり、プレイヤーはそれぞれの手のいくつかの指を伸ばし、交互に手をタップすることによってそれらの本数を変化させる形で遊ぶ。割り箸は組合せゲームの一種であり、どのような局面であってもそこからの最適な戦略が知られているという意味では解決している。
この公式的なルールは「ロールオーバー」と呼ばれ、以下で説明するように、手の指の合計が5本を超える場合、そこから5を引いた本数の指を広げる。
各プレイヤーは自身の手の各々で指を1本広げた状態からゲームをスタートする。最初のプレイヤーからターンは時計回りに進む。
自身のターンで、プレイヤーは「攻撃」か「分割」のいずれか一方を行う。
「攻撃」では、プレイヤーは自身の「生きている手」、すなわち指が1本以上広げられている手のうちの1つを使い、敵の生きている手を打つ。打たれた相手の手の指の本数は、打つのに使用された手の指の本数分だけ増加する。
各プレイヤーのいずれかの手で指がちょうど5本広げられる場合、その手は「死ぬ」。これは0本の指を広げる、すなわち拳を閉じることや、死んだ手をプレイヤー自身の背後に隠すことなどによって表される。
いずれかの手が指5本を超える場合、そこから5を引いた本数の指を広げる。例えば、広げられた指が4本の手が、広げられた指が2本の手を攻撃した場合、合計で指は6本となるが、そのとき5本の指が自動的に差し引かれ、攻撃された手では1本の指を広げることになる。(プレイヤーのいずれかの手の指が5本以上となった時点でその手を「死んだ手」と見なすようなバリエーションも存在する。)
「分割」では、プレイヤーは自身の2つの手を互いに打ち、広げられた指を片方の手から他方の手へ好きな本数移動できる。ただし、単に2つの生きている手の指の本数を交換するような移動はできない。例えば、プレイヤーが広げられた指が各々2本と3本の生きている手2つを持つ場合、広げられた指が各々1本と4本の生きている手2つを持つという状態に移動することはできるが、広げられた指が各々2本と3本の生きている手2つを持つ状態(移動前とは手の左右が異なる)に移動することはできない。また、このように生きている手同士の指の本数を「分割」によって移動する場合、この移動を特に「転送」という。
プレイヤーは「分割」のルールに従う限りにおいては、「分割」を用いて死んだ手を生き返らせることもできる。この移動を特に「分裂」という。例えば、プレイヤーが死んだ手を1つと、指が3本広げられた生きている手を1つもつ場合、広げられた指が各々1本と2本の生きている手2つを持つという状態に移動することができる。ただし、敵の手を「攻撃」を用いて生き返らせることはできない。それゆえ、2つの手がともに死んだプレイヤーはこれ以上ゲームを続けられず、プレイから除外される。
プレイヤーは自身の手を死なせることはできない。例えばプレイヤーが、広げられた指が各々1本と2本の生きている手2つを持つ場合に、(「分割」を用いて)広げられた指が3本の生きている手1つと死んだ手1つを持つという状態に移動することはできない。
プレイヤーは、すべての対戦相手が(同時に2つの「死んだ手」を持つことによって)プレイから除外された場合に勝利となる。
割り箸の状態は4桁のコード[ABCD]で簡略的に表すことができる。AとBはターンプレイヤーの手(広げられた指の数の昇順)を表し、CとDはターンプレイヤーでないプレイヤーの手(広げられた指の数の昇順)を表す。単一で他と異なる状態が、誤って2つのコードで表されることがないように、各プレイヤーの手を指の昇順で表記することが重要である。例えば、[1032]というコードは許されず、[0123]と表記する必要がある。
それゆえ、公式ルール「ロールオーバー」においては、スタートの状態は[1111]であり、その次の状態は[1211]となる。また、[1211]の次の状態は[1212]か[1312]となる。各状態を4桁の数として扱う場合、最小の状態は[0000]であり、最大の状態は[4444]である。
この略記方法はより多くのプレイヤーがいるゲームに対しても容易に拡張できる。3人のプレイヤーがいるゲームでは、6桁の数によって表され(例. [111211])、左端から2桁ずつの数字の各ペアは、プレイヤー1人ずつを表し、各ペアはプレイヤーがいつ自分のターンを行うかに基づいて並べられている。左端のペアはまさに今ターンを行おうとしているプレイヤーの手を表し、中央のペアはその次にターンを行うプレイヤーの手を表す、などである。右端のペアは自分のターンが来るまでに最も待たなければならないプレイヤーの手を表す(通常、そのプレイヤーはターンを行ったばかりであるため)。
基本ルール(「ロールオーバー」)のもとで最大で14の可能な状態移動が存在する。(「分裂」と「転送」を合わせて「分割」と呼んでいる。)
4つの「攻撃」(A-C, A-D, B-C, B-D)
4つの「分裂」(02-11, 03-12, 04-13, 04-22)
6つの「転送」(13-22, 22-13, 14-23, 23-14, 24-33, 33-24)
しかし、1ターン中に行える状態移動はその内の5つ以下しかない。
例えば、状態[1312]は [2213], [1313], [2413], [0113], [1222] のいずれかの状態に移動する。
ゲームの最小手数は5手である。そのようなゲームプレイ(状態遷移)の例は1つ存在する。
1111 1211 1312 0113 1401 0014
各ターンで、それまでに到達した状態には戻らないように移動する場合の、最長のゲームは9手詰みである。そのようなゲームプレイ(状態遷移)の例は2つ存在する。
1111 1211 1212 2212 2322 0223 0202 0402 0104 0001
1111 1211 1212 2312 2323 0323 0303 0103 0401 0004
再訪ありの場合(すでに到達した状態に再び移動してもよい場合)のゲームの最長手数は分かっていない。
ロールオーバーにおいて、手が死ぬときの指の本数を「ロールオーバー量」と呼ぶ。基本ルールでは、ロールオーバー量が5であるから、箸は基数5のゲームである。プレイヤーが2人の場合の各状態は4桁の数で表され、0000から4444まで(基数5で)数えると625個の状態がある。しかし、これらの状態のほとんどが間違った表記である(例. 0132 ,1023, 1032)。それらは一見異なるように見えるが、ゲームプレイにおいては機能的に同じである(ここで「ゲームプレイにおいて機能的に同じ」というのは、プレイヤーA,Bという区別に注目するのではなく、各ターンにおけるターンプレイヤーとターンプレイヤーでないプレイヤーという区別に注目した上で、手の対称性から同じ状態を表すということを意味している。例えば、0123はターンプレイヤーの手が01、ターンプレイヤーでないプレイヤーの手が23であることを意味するが、先攻のプレイヤーAと後攻のプレイヤーBが各々01,23の手をもつ場合と、各々23,01の手を持つ場合の2つの場合を含んでいることに注意)。
機能的に異なる状態の数を知るためには、機能的に異なるペアの数を単に2乗すればよい。機能的に異なるペアは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個はターンプレイヤーの手が異なる15個のペア(00, 01, 02, 03, 04, 11, 12, 13, 14, 22, 23, 24, 33, 34, 44)のいずれかとなり、もう一方のプレイヤーが負けている(つまり00の手をもつ)という状態である。問題は、負けたプレイヤーがちょうど自分のターンを行ったプレイヤーとなっている(すなわち“00"が右側にある)ことである。プレイヤーは自身のターンに負けることはできないため、これらの状態は明らかに到達不可である。
到達不可能な21個の状態のうちの4個(1101,2202,3303,4404)はターンプレイヤーが[kk]という手をもち、もう一方のプレイヤーが[0k] という手を持つ状態である(ただし、0<k<5)。ターンを行った[0k]のプレイヤーは、直前のターンで分割は行えず、それゆえそのプレイヤーは自身の[0k]を用いて相手を攻撃したことになるが、相手を[0k]を用いて攻撃し結果相手の手が[kk]となるためには、死んだ手に攻撃しなければならないため、これは不可能である。したがって、この状態には到達不可能である。
到達不可能な残りの2つの状態は3444と4444である。4444に関して、プレイヤーは分割によって[44]に到達することはできないため、ターンプレイヤー(つまり左端の44)は直前のターンで相手(右端の[44])の攻撃によって[44]となっている必要がある。[44]に攻撃された結果として[44]となり得るようなペアは[04]のみであるが、これは死んだ手が攻撃されることを要求するため、これは不可能である。したがって、4444は到達不可能である。また、3444は、4444からのみ到達可能である。4444は初期状態である1111から到達不可能なため、同様に3444も到達不可能である。
上記ポイント2に挙げた4つの状態のうち、[1101]を除いてすべては、後述の「自殺」ルールを採用すると到達可能である。[1101]は「自殺」ルールとともに、後述の「メタ」ルールを採用したゲームにおいては到達可能である。ポイント3にある2つの状態は、後述の「サンズ」ルールを採用すると[4444]が初期状態となるため到達できるが、最初の2ターン以降で、それら2つの状態([4444]と[3444])に到達することはできない。以上のことから、「自殺」「メタ」「サンズ」をすべて採用してプレイすると、合計で15個の到達不可能な状態と210個の到達可能な状態が存在する。
ゲームの勝敗が決するときの最終状態としてあり得る状態は14個ある。すなわち、0001, 0002, 0003, 0004, 0011, 0012, 0013, 0014, 0022, 0023, 0024, 0033, 0034, 0044である。これらは、勝利したプレイヤーが、生きている手を表す異なる14個のペア(01,02,03,04,11,12,13,14,22,23,24,33,34,44)のうちのいずれかの状態をとるということを意味している。これら14個の最終状態の各々に最小手数で到達してゲームが終了するような場合を考えると、そのうち8個で先攻のプレイヤーが勝利することが知られている。
カットオフ:手の広げられた指が5本を超える場合、(公式ルールで説明されている「ロールオーバー」とは対照的に)その手は死ぬ。
自殺:プレイヤーは分割で自分の手の1つを殺すことができる。ただし、広げられた指の本数の合計を減らすような移動はできない。例えば、状態[1201]では、プレイヤーは 12-03 を実行し、ゲームを [0103] に持ち込むことができ、このとき対戦相手は攻撃B-Dを行うことを強いられ、結果[0401]となるため、この時点でターンプレイヤーの勝利が確定する。しかし、状態[3301]から、プレイヤーが 33-01 (33-15) を実行し、ゲームを [0101] に持ち込むことなどはできない。
メタ:プレイヤーは、自身の手の広げられた指の本数が合計5を超える場合、その合計から5を差し引いた本数の指を(分割によって)広げることができる。例えば、[44]では広げられた指の合計は8であるため、そこから5を差し引いた結果である3を[12]に分割できる。したがって、1回の移動で[44]から[12]へ移動することが可能である。「メタ」の採用により、2つの新たな移動(34-11, 44-12)が可能となる。「メタ」と「自殺」の両方を採用してプレイする場合、追加で4つの移動(24-01, 33-01, 34-02, 44-03)が可能となり、合計で最大20の状態が新たに到達可能となる。
サンズ:両プレイヤーは自身のそれぞれの手で指を4本広げた状態([4444])からスタートする。これは通常のゲームプレイ(つまり、初期状態[1111]から)では到達できない状態である。
逆形:最初に自分の全ての手が死んだプレイヤーが勝利となる。
転送のみ:分割を行う場合、分裂は行えず、転送のみ可能である。
分裂のみ:分割を行う場合、転送は行えず、分裂のみ可能である。
スワップ/シェリー:プレイヤーの2つの手がともに生きており、それらの広げられた指の本数が等しくない場合、プレイヤーはそれらの本数を交換することができる。この場合、実質的に自身のターンをスキップすることと同じになる。このルールを採用すると、明らかに繰り返しや無限ループによる引き分けが発生しうるため、これを避けるため、プレイヤーが攻撃されることなく実行できる連続スワップの数に制限を設けることができ、制限に達するとプレイヤーは攻撃することを強制される。
ローガン条項:プレイヤーは「自殺」と「スワップ」の移動が許されているが、それは両方を同時に行う(つまり、死んでいる手を生きている手と交換する)場合に限られる。
切り株:プレイヤーの手の状態が[01]である場合、[0.5 0.5]に分割することが許される。
より多くの手:各プレイヤーは2つより多くの「手」をもつ。人は手を2つしかもたないため、これは通常、複数人のチームでプレイされる。
様々な数字:正の数rに対し、手は広げられた指の数がrとなったときに死ぬ(つまりr=5とは限らない)。r=5の場合は、標準的な割り箸ゲームのルールと同じである。手で5より大きい本数の指を表す場合は、中国版の指数字や六進指数え法、あるいは二進指数といった様々な数え上げシステムを用いることができる。
半分:分割を行うことが許されるのは、広げられた指の本数が偶数である生きている手1つを指の本数が等しい2つの手に分裂させるとき、または、広げられた指の本数が奇数である生きている手1つを指の数が可能な限り等しい(すなわち差が1である)整数となるように2つの手に分裂させるときに限られる。例えば、04-22 や 03-12 は可能であるが、04-13 や 13-22 などの移動は許されない。このルールを適用すると、後攻のプレイヤーが必勝戦略をもつ。
突然死:プレイヤーは、自身の手で広げられた指の合計が1本だけになったとき、すなわち[01]となったとき敗北する。あるいは、各プレイヤーはライフ3つから始め、自身の手が[01]となる度にライフを失い、ライフが0になると敗北する。
ゾンビ:3人以上のプレイヤーがいる場合、ゲームに負けたプレイヤーは、片方の手で指を1本広げた状態(すなわち[01])でゲームが終わるまでプレイに残り続ける。それらのプレイヤーは、自身のターンで攻撃することはできるが、分割はできない。また、他のプレイヤーはそれらの手を攻撃することはできない(Chris Bandyによって発明された)。
ウェットジャクソン:ウェットジャクソンは3人以上のプレイヤーがいるときにのみプレイできる。プレイヤーは、ゲーム中に「直立復活」とコールして起立することで、追加で1本の指を自身の生きている手に加えるか、指を1本追加し手を死んだ状態から復活させることが出来る。
整数:手の表裏を区別し、手が表(手の甲が上向き)である場合は指の本数は正の値、裏(手の甲が下向き)である場合は負の値を表す。例えば、手が裏向きで2本の指が広げられている場合、その手の値は-2であることを意味する。このとき、広げられた指の本数が0であるような生きている手も可能となるが(値3の手が値-3の手に攻撃された場合など)、手は値5または値-5になったときに死ぬ。また、プレイヤーは自身のターンで手を表裏ひっくり返し、手の表す値の+/-符号(正負)を変えることが許されている。正負を変化させるこの移動は、ロールオーバーにおいて1つの手の表す値を、5からその値を引いたものに置き換える移動と等価である。
公式ルールである「ロールオーバー」を用いると、2人の完璧なプレイヤー(可能な移動のうちで自分にとって最もよい結果を導く移動を行うプレイヤー)が行う割り箸ゲームはループに入ってしまい終了しない(勝敗がつかない)。実際、非常に経験の浅いプレイヤーでさえ、1つ先の動きを見るだけで負けることを回避することができる。
「カットオフ」ルールを採用すると、先攻のプレイヤーが必勝戦略をもつ。必勝戦略の1つは、各移動のあとに次の状態の1つに常に到達するようにすることであり、複数の選択肢がある場合はリストの最初にあるものを優先的に選択する。
[1211](ここから開始)
[ab12](abは任意の指の状態を表す)(可能ならすぐに勝利)
逆に、「自殺」ルールを採用すると後攻のプレイヤーに必勝戦略が存在する。
「カットオフ」と「自殺」をともに採用したときの(完璧なプレイヤー同士のゲームの)勝敗帰結はロールオーバー量 r の値に応じて以下のようになる。
割り箸は(p, h, r)型ゲームに一般化できる。ここで、p はプレイヤーの人数、h はそれぞれのプレイヤーの手の数、r はロールオーバー量である。
ロールオーバー量が1のゲームでは、値が1の手は値が0の手(すなわち死んだ手)になり、全ての手が開始時点で死ぬことになるため、これはとるに足らないゲームである。プレイヤーが1人以下でのゲームはゲームではなく、パズルやセルオートマトンである。
ロールオーバー量が2のゲームは、分割を行えず、ロールオーバーとカットオフルールが同じゲームとなるため、縮退している。また、手への攻撃はそのまま相手の手を殺すことになるため、プレイヤーが相手を攻撃したとき、相手のもつ生きている手の数は1つ減少する。ゲームにおける到達可能な状態は
p = 2  のとき 2h 個
p \geq 3  のとき \sum_{k=2}^p h^k{p \choose k} 個
存在する。また、 p = 2  のとき、ゲームの長さは ph -1  である。プレイヤー2人のゲーム(すなわち  p = 2 )では、任意の h に対して先攻が勝利する、と強解決されている。この縮退したケースを「切り株」ルールを採用してプレイすると、「半分」ルールを採用した上で、ロールオーバー量が4、かつ各プレイヤーが全ての手で2本の指を広げた状態からスタートするようなゲームと等価なゲームとなる。
各プレイヤーが手を1つだけもつとき(h = 1)、分割は起こり得ず、各プレイヤーの行える移動は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 である。
各プレイヤーが1より多くの手を持ち(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)。それらは一見異なるように見えるがゲームプレイにおいては機能的に同じものである。機能的に異なる状態の数を知るためには、機能的に異なるペアの数を2乗すればよい。ロールオーバー量 r、手の数 h に対して、{r + h - 1 \choose h}個の異なるペアが存在し、各プレイヤーはこれらのペアのいずれもとることができるから、結果の値を2乗するだけで、{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 < r-1 なる値 k の手を  h  個もち、もう一方のプレイヤーは値 k の生きている手を1つだけ持つ状態である。ターンを行った値 k の生きている手を1つだけもつプレイヤーは、直前のターンで分割は行えず、それゆえそのプレイヤーは自身のただ1つの生きている手[00...0k]を用いて攻撃したことになるが、相手を [00...0k]を用いて攻撃した結果相手が値 k の手を h 個もつためには、死んだ手に攻撃しなければならないため、これは不可能である。したがって、この状態には到達不可能である。
到達不可能な状態のうちの h - 1 個は、ターンプレイヤーが値 r - 1 の手を h 個もち、もう一方のプレイヤーが値 r - 1 の生きている手を k 個(それ以外の手はすべて死んだ手)もつ状態である(ただし 0 < k < h-1 )。これらの状態が到達可能であると仮定すると、プレイヤーは分割によって値 r - 1 の手を h 個もつ状態[(r-1)(r-1)...(r-1)]に到達することはできないため、ターンプレイヤーの手は自身のターンの直前に相手の攻撃によって[(r-1)(r-1)...(r-1)]となっている必要がある。しかし、相手の生きている手は全て値 r - 1 の手であり、そのうちの1つを用いて攻撃した結果として現在のターンプレイヤーが値 r - 1 の手を h 個もつためには、死んでいる手が攻撃される必要があるので、これは不可能である。したがって、これらの状態は到達不可能である。
両プレイヤーが値 r - 1 の手を h 個もつという状態も上記ポイント3と同様の理由で到達不可能である。
ターンプレイヤーが値 r - 2 の手を1個と 値 r - 1 の手を h - 1 個もち、もう一方のプレイヤーが値 r - 1 の手を h 個もつという状態は、ポイント4で挙げた状態からのみ到達可能であるが、ポイント4の状態は初期状態から到達不可能であるため、この状態も同様に到達不可能である。
ポイント2と3で挙げた状態のうち、「ターンプレイヤーが値1の手を h 個もち、もう一方のプレイヤーが値1の生きている手を1つだけもつという状態」の1つを除いて、「自殺」ルールを採用すると到達可能である。「ターンプレイヤーが値1の手を h 個もち、もう一方のプレイヤーが値1の生きている手を1つだけもつという状態」は「自殺」ルールと「メタ」ルールをともに採用してプレイしたゲームにおいては到達可能である。ポイント4と5で挙げた2つの状態は「サンズ」ルールを採用すると、ポイント4の状態が初期状態であるため、到達可能であるが、最初の2ターン以降で、それら2つの状態に到達することはできない。以上のことから、「自殺」「メタ」「サンズ」をすべて採用してプレイすると、合計で {r + h - 1 \choose h} 個の到達不可能な状態と {r + h - 1 \choose h}^2 - {r + h - 1 \choose h} 個の到達可能な状態が存在する。
ロールオーバー量が5、手の数が2である場合。
2人のプレイヤーでは、204個の到達可能状態がある。
3人のプレイヤーでは、3337個の到達可能状態がある。
4人のプレイヤーでは、25000個以上の到達可能状態がある。