割り箸 (手遊びゲーム)

割り箸（わりばし）は２人(以上)で行う手遊びゲームであり、プレイヤーはそれぞれの手のいくつかの指を伸ばし、交互に手をタップすることによってそれらの本数を変化させる形で遊ぶ。割り箸は組合せゲームの一種であり、どのような局面であってもそこからの最適な戦略が知られているという意味では解決している。
ルール.
この公式的なルールは「ロールオーバー」と呼ばれ、以下で説明するように、手の指の合計が５本を超える場合、そこから５を引いた本数の指を広げる。
略記.
割り箸の状態は４桁のコード[ABCD]で簡略的に表すことができる。AとBはターンプレイヤーの手(広げられた指の数の昇順)を表し、CとDはターンプレイヤーでないプレイヤーの手(広げられた指の数の昇順)を表す。単一で他と異なる状態が、誤って２つのコードで表されることがないように、各プレイヤーの手を指の昇順で表記することが重要である。例えば、[1032]というコードは許されず、[0123]と表記する必要がある。
それゆえ、公式ルール「ロールオーバー」においては、スタートの状態は[1111]であり、その次の状態は[1211]となる。また、[1211]の次の状態は[1212]か[1312]となる。各状態を４桁の数として扱う場合、最小の状態は[0000]であり、最大の状態は[4444]である。
この略記方法はより多くのプレイヤーがいるゲームに対しても容易に拡張できる。３人のプレイヤーがいるゲームでは、６桁の数によって表され（例. [111211]）、左端から２桁ずつの数字の各ペアは、プレイヤー１人ずつを表し、各ペアはプレイヤーがいつ自分のターンを行うかに基づいて並べられている。左端のペアはまさに今ターンを行おうとしているプレイヤーの手を表し、中央のペアはその次にターンを行うプレイヤーの手を表す、などである。右端のペアは自分のターンが来るまでに最も待たなければならないプレイヤーの手を表す（通常、そのプレイヤーはターンを行ったばかりであるため）。
移動.
基本ルール(「ロールオーバー」)のもとで最大で14の可能な状態移動が存在する。（「分裂」と「転送」を合わせて「分割」と呼んでいる。）
しかし、１ターン中に行える状態移動はその内の５つ以下しかない。
例えば、状態[1312]は [2213], [1313], [2413], [0113], [1222] のいずれかの状態に移動する。
ゲームの長さ.
ゲームの最小手数は５手である。そのようなゲームプレイ(状態遷移)の例は１つ存在する。
各ターンで、それまでに到達した状態には戻らないように移動する場合の、最長のゲームは９手詰みである。そのようなゲームプレイ(状態遷移)の例は２つ存在する。
再訪ありの場合(すでに到達した状態に再び移動してもよい場合)のゲームの最長手数は分かっていない。
状態数.
ロールオーバーにおいて、手が死ぬときの指の本数を「ロールオーバー量」と呼ぶ。基本ルールでは、ロールオーバー量が５であるから、箸は基数５のゲームである。プレイヤーが２人の場合の各状態は４桁の数で表され、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個の機能的に異なる状態が得られる。
21個の到達不可能な状態（0000, 0100, 0200, 0300, 0400, 1100, 1101, 1200, 1300, 1400, 2200, 2202, 2300, 2400, 3300, 3303, 3400, 3444, 4400, 4404, 4444）が存在する。
上記ポイント２に挙げた４つの状態のうち、[1101]を除いてすべては、後述の「自殺」ルールを採用すると到達可能である。[1101]は「自殺」ルールとともに、後述の「メタ」ルールを採用したゲームにおいては到達可能である。ポイント３にある２つの状態は、後述の「サンズ」ルールを採用すると[4444]が初期状態となるため到達できるが、最初の２ターン以降で、それら２つの状態([4444]と[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)のうちのいずれかの状態をとるということを意味している。これら１４個の最終状態の各々に最小手数で到達してゲームが終了するような場合を考えると、そのうち８個で先攻のプレイヤーが勝利することが知られている。
最適戦略.
公式ルールである「ロールオーバー」を用いると、２人の完璧なプレイヤー(可能な移動のうちで自分にとって最もよい結果を導く移動を行うプレイヤー)が行う割り箸ゲームはループに入ってしまい終了しない(勝敗がつかない)。実際、非常に経験の浅いプレイヤーでさえ、１つ先の動きを見るだけで負けることを回避することができる。
「カットオフ」ルールを採用すると、先攻のプレイヤーが必勝戦略をもつ。必勝戦略の１つは、各移動のあとに次の状態の１つに常に到達するようにすることであり、複数の選択肢がある場合はリストの最初にあるものを優先的に選択する。
逆に、「自殺」ルールを採用すると後攻のプレイヤーに必勝戦略が存在する。
「カットオフ」と「自殺」をともに採用したときの(完璧なプレイヤー同士のゲームの)勝敗帰結はロールオーバー量 formula_1 の値に応じて以下のようになる。
一般化.
割り箸は(p, h, r)型ゲームに一般化できる。ここで、formula_2 はプレイヤーの人数、formula_3 はそれぞれのプレイヤーの手の数、formula_1 はロールオーバー量である。
縮退したケース.
ロールオーバー量が１のゲームでは、値が１の手は値が０の手（すなわち死んだ手）になり、全ての手が開始時点で死ぬことになるため、これはとるに足らないゲームである。プレイヤーが１人以下でのゲームはゲームではなく、パズルやセルオートマトンである。
ロールオーバー量が２のゲームは、分割を行えず、ロールオーバーとカットオフルールが同じゲームとなるため、縮退している。また、手への攻撃はそのまま相手の手を殺すことになるため、プレイヤーが相手を攻撃したとき、相手のもつ生きている手の数は１つ減少する。ゲームにおける到達可能な状態は
存在する。また、formula_5 のとき、ゲームの長さは formula_10 である。プレイヤー２人のゲーム(すなわち formula_5)では、任意の formula_3 に対して先攻が勝利する、と強解決されている。この縮退したケースを「切り株」ルールを採用してプレイすると、「半分」ルールを採用した上で、ロールオーバー量が４、かつ各プレイヤーが全ての手で２本の指を広げた状態からスタートするようなゲームと等価なゲームとなる。
２人のプレイヤー.
各プレイヤーが手を１つだけもつとき（formula_13）、分割は起こり得ず、各プレイヤーの行える移動は１つしかないため、ゲームは縮退している。ロールオーバー量が formula_1 のとき、ゲームにおける formula_15 回の移動の後（すなわちゲーム開始から formula_15 ターン後）の各状態はタプルにより表される formula_17。ここで、formula_18 は formula_19, formula_20 のときの formula_15 番目のフィボナッチ数である。ゲームが終了するまでの到達可能状態数は、formula_22 が formula_1 で割りきれるような最小の非負整数 formula_15 に対し、formula_25 で与えられる。このゲームは formula_1 の値とフィボナッチ数の分割可能性に依って、いずれかの側が勝利するとして強解決されている。また、ゲームの長さは formula_15 である。
各プレイヤーが１より多くの手を持ち（formula_28）、それぞれの手のロールオーバー量が formula_29 であるとき、
ロールオーバー量が formula_1 であるため、箸は基数 formula_1 のゲームである。それぞれの状態は formula_6 桁の数で表される。基数 formula_1 で formula_6 桁の全ての数を列挙すると formula_30 個の状態が得られる。しかし、これらのほとんどは誤った表記である（例.formula_39 における 001210, 010120, 100021）。それらは一見異なるように見えるがゲームプレイにおいては機能的に同じものである。機能的に異なる状態の数を知るためには、機能的に異なるペアの数を２乗すればよい。ロールオーバー量 formula_1、手の数 formula_3 に対して、formula_42個の異なるペアが存在し、各プレイヤーはこれらのペアのいずれもとることができるから、結果の値を２乗するだけで、formula_31個の機能的に異なる状態が得られる。
formula_44 個の到達不可能な状態がある。
ポイント２と３で挙げた状態のうち、「ターンプレイヤーが値１の手を formula_3 個もち、もう一方のプレイヤーが値１の生きている手を１つだけもつという状態」の１つを除いて、「自殺」ルールを採用すると到達可能である。「ターンプレイヤーが値１の手を formula_3 個もち、もう一方のプレイヤーが値１の生きている手を１つだけもつという状態」は「自殺」ルールと「メタ」ルールをともに採用してプレイしたゲームにおいては到達可能である。ポイント４と５で挙げた２つの状態は「サンズ」ルールを採用すると、ポイント４の状態が初期状態であるため、到達可能であるが、最初の２ターン以降で、それら２つの状態に到達することはできない。以上のことから、「自殺」「メタ」「サンズ」をすべて採用してプレイすると、合計で formula_42 個の到達不可能な状態と formula_76 個の到達可能な状態が存在する。
2人より多くのプレイヤー.
ロールオーバー量が5、手の数が2である場合。