割り箸 (手遊びゲーム)

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

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

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

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

 移動 
基本ルール(「ロールオーバー」)のもとで最大で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）

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

例えば、状態は , , , , のいずれかの状態に移動する。

 ゲームの長さ 
ゲームの最小手数は５手である。そのようなゲームプレイ(状態遷移)の例は１つ存在する。
 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] という手を持つ状態である(ただし、０<ｋ<５)。ターンを行った[0k]のプレイヤーは、直前のターンで分割は行えず、それゆえそのプレイヤーは自身の[0k]を用いて相手を攻撃したことになるが、相手を[0k]を用いて攻撃し結果相手の手が[kk]となるためには、死んだ手に攻撃しなければならないため、これは不可能である。したがって、この状態には到達不可能である。
 到達不可能な残りの２つの状態は3444と4444である。4444に関して、プレイヤーは分割によってに到達することはできないため、ターンプレイヤー(つまり左端の44)は直前のターンで相手(右端の)の攻撃によってとなっている必要がある。に攻撃された結果としてとなり得るようなペアはのみであるが、これは死んだ手が攻撃されることを要求するため、これは不可能である。したがって、4444は到達不可能である。また、3444は、4444からのみ到達可能である。4444は初期状態である1111から到達不可能なため、同様に3444も到達不可能である。
上記ポイント２に挙げた４つの状態のうち、を除いてすべては、後述の「自殺」ルールを採用すると到達可能である。は「自殺」ルールとともに、後述の「メタ」ルールを採用したゲームにおいては到達可能である。ポイント３にある２つの状態は、後述の「サンズ」ルールを採用するとが初期状態となるため到達できるが、最初の２ターン以降で、それら２つの状態(と)に到達することはできない。以上のことから、「自殺」「メタ」「サンズ」をすべて採用してプレイすると、合計で15個の到達不可能な状態と210個の到達可能な状態が存在する。
ゲームの勝敗が決するときの最終状態としてあり得る状態は１４個ある。すなわち、0001, 0002, 0003, 0004, 0011, 0012, 0013, 0014, 0022, 0023, 0024, 0033, 0034, 0044である。これらは、勝利したプレイヤーが、生きている手を表す異なる１４個のペア(01,02,03,04,11,12,13,14,22,23,24,33,34,44)のうちのいずれかの状態をとるということを意味している。これら１４個の最終状態の各々に最小手数で到達してゲームが終了するような場合を考えると、そのうち８個で先攻のプレイヤーが勝利することが知られている。

 バリエーション 
 カットオフ：手の広げられた指が５本を超える場合、（公式ルールで説明されている「ロールオーバー」とは対照的に）その手は死ぬ。
 自殺：プレイヤーは分割で自分の手の１つを殺すことができる。ただし、広げられた指の本数の合計を減らすような移動はできない。例えば、状態では、プレイヤーは 12-03 を実行し、ゲームを に持ち込むことができ、このとき対戦相手は攻撃B-Dを行うことを強いられ、結果となるため、この時点でターンプレイヤーの勝利が確定する。しかし、状態から、プレイヤーが 33-01 (33-15) を実行し、ゲームを に持ち込むことなどはできない。
 メタ：プレイヤーは、自身の手の広げられた指の本数が合計５を超える場合、その合計から５を差し引いた本数の指を（分割によって）広げることができる。例えば、では広げられた指の合計は８であるため、そこから５を差し引いた結果である３をに分割できる。したがって、１回の移動でからへ移動することが可能である。「メタ」の採用により、２つの新たな移動（34-11, 44-12）が可能となる。「メタ」と「自殺」の両方を採用してプレイする場合、追加で４つの移動（24-01, 33-01, 34-02, 44-03）が可能となり、合計で最大２０の状態が新たに到達可能となる。
 サンズ：両プレイヤーは自身のそれぞれの手で指を４本広げた状態()からスタートする。これは通常のゲームプレイ（つまり、初期状態から）では到達できない状態である。
 逆形：最初に自分の全ての手が死んだプレイヤーが勝利となる。
 転送のみ：分割を行う場合、分裂は行えず、転送のみ可能である。
 分裂のみ：分割を行う場合、転送は行えず、分裂のみ可能である。
 スワップ/シェリー：プレイヤーの２つの手がともに生きており、それらの広げられた指の本数が等しくない場合、プレイヤーはそれらの本数を交換することができる。この場合、実質的に自身のターンをスキップすることと同じになる。このルールを採用すると、明らかに繰り返しや無限ループによる引き分けが発生しうるため、これを避けるため、プレイヤーが攻撃されることなく実行できる連続スワップの数に制限を設けることができ、制限に達するとプレイヤーは攻撃することを強制される。
 ローガン条項：プレイヤーは「自殺」と「スワップ」の移動が許されているが、それは両方を同時に行う（つまり、死んでいる手を生きている手と交換する）場合に限られる。
 切り株：プレイヤーの手の状態がである場合、[0.5 0.5]に分割することが許される。
 より多くの手：各プレイヤーは２つより多くの「手」をもつ。人は手を２つしかもたないため、これは通常、複数人のチームでプレイされる。
 様々な数字：正の数ｒに対し、手は広げられた指の数がｒとなったときに死ぬ（つまりｒ＝５とは限らない）。ｒ＝５の場合は、標準的な割り箸ゲームのルールと同じである。手で５より大きい本数の指を表す場合は、中国版の指数字や六進指数え法、あるいは二進指数といった様々な数え上げシステムを用いることができる。
 半分：分割を行うことが許されるのは、広げられた指の本数が偶数である生きている手１つを指の本数が等しい２つの手に分裂させるとき、または、広げられた指の本数が奇数である生きている手１つを指の数が可能な限り等しい(すなわち差が１である)整数となるように２つの手に分裂させるときに限られる。例えば、04-22 や 03-12 は可能であるが、04-13 や 13-22 などの移動は許されない。このルールを適用すると、後攻のプレイヤーが必勝戦略をもつ。
 突然死：プレイヤーは、自身の手で広げられた指の合計が１本だけになったとき、すなわちとなったとき敗北する。あるいは、各プレイヤーはライフ３つから始め、自身の手がとなる度にライフを失い、ライフが０になると敗北する。
 ゾンビ：３人以上のプレイヤーがいる場合、ゲームに負けたプレイヤーは、片方の手で指を１本広げた状態（すなわち）でゲームが終わるまでプレイに残り続ける。それらのプレイヤーは、自身のターンで攻撃することはできるが、分割はできない。また、他のプレイヤーはそれらの手を攻撃することはできない（Chris Bandyによって発明された）。
 ウェットジャクソン：ウェットジャクソンは３人以上のプレイヤーがいるときにのみプレイできる。プレイヤーは、ゲーム中に「直立復活」とコールして起立することで、追加で１本の指を自身の生きている手に加えるか、指を１本追加し手を死んだ状態から復活させることが出来る。
 整数：手の表裏を区別し、手が表(手の甲が上向き)である場合は指の本数は正の値、裏(手の甲が下向き)である場合は負の値を表す。例えば、手が裏向きで２本の指が広げられている場合、その手の値は-2であることを意味する。このとき、広げられた指の本数が０であるような生きている手も可能となるが（値３の手が値-３の手に攻撃された場合など）、手は値５または値-５になったときに死ぬ。また、プレイヤーは自身のターンで手を表裏ひっくり返し、手の表す値の＋/－符号(正負)を変えることが許されている。正負を変化させるこの移動は、ロールオーバーにおいて１つの手の表す値を、５からその値を引いたものに置き換える移動と等価である。

 最適戦略 
公式ルールである「ロールオーバー」を用いると、２人の完璧なプレイヤー(可能な移動のうちで自分にとって最もよい結果を導く移動を行うプレイヤー)が行う割り箸ゲームはループに入ってしまい終了しない(勝敗がつかない)。実際、非常に経験の浅いプレイヤーでさえ、１つ先の動きを見るだけで負けることを回避することができる。
「カットオフ」ルールを採用すると、先攻のプレイヤーが必勝戦略をもつ。必勝戦略の１つは、各移動のあとに次の状態の１つに常に到達するようにすることであり、複数の選択肢がある場合はリストの最初にあるものを優先的に選択する。
 (ここから開始)
 [ab12](abは任意の指の状態を表す)(可能ならすぐに勝利)

逆に、「自殺」ルールを採用すると後攻のプレイヤーに必勝戦略が存在する。

「カットオフ」と「自殺」をともに採用したときの(完璧なプレイヤー同士のゲームの)勝敗帰結はロールオーバー量 の値に応じて以下のようになる。
 ロールオーバー量 勝敗帰結 2 先攻必勝 3 引き分け(勝敗がつかない) 4 先攻必勝 5 後攻必勝

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

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

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

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

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

 個の到達不可能な状態がある。

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

 ロールオーバー量 状態数 機能的に異なる状態数 到達可能状態数 3 81 36 26 4 256 100 85 5 625 225 204 6 1296 441 413 7 2401 784 748 8 4096 1296 1251 9 6561 2025 1970 10 10000 3025 2959 11 14641 4356 4278 12 20736 6084 5993

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