ハーフギャモン
- バックギャモンの状態数は 約10^20 と言われている（参照）が、 その計算方法は不明である。
- ハーフギャモンの状態数は、ポイント数・コマ数が半分なので、バックギャモンの状態数の 1/2乗、すなわち 約10^10 と推測している。
- 計算方法が不明なので、まずはランニング状態に限り、全ての状態を列挙し、それらの期待値を全て計算することを目指すことにすことにする。
状態数
黒石のみの状態数
- 白黒双方の状態数を数えるのは大変なので、まずは黒石のみの状態数を数える。
- スタート・ゴールを含めると、石を置くことの出来る箇所は14箇所なので、 それぞれの石を区別する場合の状態数は 14^8 となる。
- 実際にはそれぞれの石は区別されないので、14^8 よりかなり小さい数となる。
- 8個の石の入れ替えは 8! なので、14^8 を 8! で割ればいいと思うかもしれないが、
石が同一箇所にある場合は、もともと１つの状態としか数えられていないので、
8! で割っても正しい答えは算出できない。
（※ そもそも 14^8 は 8! で割り切れない。場合の数は必ず自然数である） - そこで、n 個の石を p 箇所に置く時の場合の数を返す NC(p, n) という関数を定義する。
- p が 1 の場合、全ての石をそこに置くことしか出来ないので、NC(1, n) = 1 となる。
- 最初の場所における石数は 0個～n個 なので、それぞれの個数を置き、 残りの p-1 箇所に n-i 個（i は最初の場所に置いた個数）を置く場合の数を合計する。
- 従って、NC(p, n) は以下のように再帰的に定義できる。
int NC(int p, int n)
{
if( p == 1 )
return 1;
else {
int sum = 0;
for(int i = 0; i <= n; ++i)
sum += NC(p - 1, n - i);
return sum;
}
}
（※ 従って、白黒それぞれ8個を14箇所に置く（ただし、同じ位置に白黒の石を置くことは不可）場合の数は、 203490*203490 = 4*10^10 より小さいということになる。ハーフギャモンの状態数が 10^10 程度という予測と矛盾しない。）
(1, 1, 1, 1, 1, 1, 1, 1, 1)
(1, 2, 3, 4, 5, 6, 7, 8, 9)
(1, 3, 6, 10, 15, 21, 28, 36, 45)
(1, 4, 10, 20, 35, 56, 84, 120, 165)
(1, 5, 15, 35, 70, 126, 210, 330, 495)
(1, 6, 21, 56, 126, 252, 462, 792, 1287)
(1, 7, 28, 84, 210, 462, 924, 1716, 3003)
(1, 8, 36, 120, 330, 792, 1716, 3432, 6435)
(1, 9, 45, 165, 495, 1287, 3003, 6435, 12870)
(1, 10, 55, 220, 715, 2002, 5005, 11440, 24310)
(1, 11, 66, 286, 1001, 3003, 8008, 19448, 43758)
(1, 12, 78, 364, 1365, 4368, 12376, 31824, 75582)
(1, 13, 91, 455, 1820, 6188, 18564, 50388, 125970)
(1, 14, 105, 560, 2380, 8568, 27132, 77520, 203490)
ランニング状態の状態数
- ランニング状態とは、互いに相手をヒットできる可能性が無い状態のことである
- ランニング状態かどうかを判定するには、白黒それぞれの最後尾の石の位置を調べるとよい。
- 黒石の最後尾位置を bt、白石の最後尾位置を wt とするとき、wt > bt ならばランニング状態である。
- 実際の計算では、白黒ともに別々の座標系を持ち、０ポイントをゴールとし、ポイントの大きい方から小さい方に進むとした方がいろいろと都合がよい。 この場合は bt + wt <= 12 ならばランニング状態と判定できる。
- ランニング状態の状態数を数えるには、白黒双方の最後尾位置で場合分けするのがよい
- bt = 1～11, wt = 1～12-bt について、それぞれの場合の数を数え合計する。
※ bt = 0～12 でないのは、終局状態を数えないようにするためである。 そもそもの目的は全ての状態の期待値を計算することなので、終局状態を含む必要はない - ランニング状態の状態数を数えるプログラムは以下のようになる
// ix ～ 0 に n 個の石を置く場合の数を数える
// ただし ix 位置には１個以上石を置くものとする
int nPermutation1Color(int ix, int n)
{
if( !ix )
return 1;
else {
int sum = 0;
for(int i = 1; i <= n; ++i)
sum += NC(ix, n - i);
return sum;
}
}
// ランニング状態の状態数を返す
template<int NP, int NS>
int nPermutationRunning()
{
int sum = 0;
for(int bt = 1; bt < NP; ++bt) {
int n = nPermutation1Color(bt, NS); // 最後尾が bt の時の状態数
for(int wt = 1; wt <= NP - bt; ++wt) {
sum += n * nPermutation1Color(wt, NS);
}
}
return sum;
}
※ バックギャモンの期待値は [-3, +3] なので、1バイトで表すと、分解能は約