ハーフギャモンプログラムのダウンロードはこちらからどぞ～
ミニギャモン（3分の２サイズのバックギャモン）プログラムのダウンロードはこちらからどぞ～

ハーフギャモン

ボード：石が置けるポイントは１～12、その他にスタート（バー）とゴールがある。
黒石は12→1の方向に、白石は1→12の方向に進むものとする。
※ 本稿では数値を直接記述するが、ソースコードではシンボルを割り当てるべきである
ハーフギャモンの白黒双方の石数は８とする（バックギャモンは15個で、その1/2を四捨五入）
初期状態のピップス数：54
サイコロの出目は、1-1, 1-2, 1-3, 2-2, 2-3, 3-3 の6通り。
ピッピス数の期待値は ((4 + 8 + 12) + (3 + 4 + 5) * 2)/9 = 5.333…
ランダムゲームによる、1ゲームの平均ターン数：41.862、ノーコンタクト状態のターン数：4.35
平均可能着手数：4.78919

ランダムゲームによるゲーム木のサイズは 4.78919^41.861 = 3.0 * 10^28
1回のロールアウトの所要時間は 5.5ミリ秒だった＠Core i5 3.46Ghz 2012/08/19

データ構造

データ構造への要求：

各ポイント（含むS/G）の石の状態を高速に参照・修正可能でないといけない
ゲーム終了状態、ベアオフ可能状態、ノーコンタクト状態か、白黒最後尾ポイント、などの判定を高速に行えないといけない
白黒反転、または白黒反転したボードオブジェクトが高速に生成・破棄可能でないといけない
（ネガアルファ or ネガマックスを使用するため）

単純かつ自然な方法

ボードの状態を char point[14]; で表す。
値が０ならば空、プラスならば黒石個数、マイナスならば白石個数
point[0] は黒のスタート位置とする。point[13] は白のスタート位置
上がった個数を別途保持する char nBlackGoal, nWhiteGoal。これはゲーム終了を高速判定するため
評価：

必要なメモリサイズは、14 + 2 = 16バイト
ポイントの状態を参照するには、point[ix] で参照し、符号をチェックしなくてはいけない
ゲーム終了判定は nBlackGoal == 8 または nWhiteGoal == 8 で行う
白黒入れ替えは、char swap を９回行う（代入と参照がそれぞれ27回）
ベアオフ可能かどうかは、最大９箇所の状態を判定しなくてはいけない
最後尾ポイントを求めるには、最大12箇所の状態を判定しなくてはいけない。
バイナリサーチ不可
石移動処理において、ゴールの場合を別途処理しなくてはいけない

白黒の配列を分離

黒石の状態を char black[14];、白石の状態を char white[14]; で表す
双方とも、インデックス 0→13 の方向に進むものとする。（逆にするのもあり）
黒スタートと白スタートが分離したので、nBlackGoal, nWhiteGoal は不要になった
評価：

必要なメモリサイズは、14 * 2 = 28バイト
ポイントの状態を参照するには black[ix], white[13-ix] を参照しなくてはいけない
ゲーム終了判定は black[13] == 8 または white[13] == 8 で行う
白黒入れ替えは、char swap を14回行う（代入と参照がそれぞれ42回）
ベアオフ可能かどうかは、最大９箇所の状態を判定しなくてはいけない
最後尾ポイントを求めるには、最大12箇所の状態を判定しなくてはいけない。
バイナリサーチ不可
石移動処理において、ゴールの場合を別途処理する必要は無い

配列ではなくビットボードを使用
結論：

ゲーム木探索

オセロやチェスなどの2人零和有限確定完全情報ゲームは、ゲーム木をミニマックス評価することにより局面の評価を行うことができる。
バックギャモンはサイコロを振り、その出目により着手を行うので、2人零和有限「確率的」完全情報ゲームである。
ミニマック評価を行うツリーには子ノード評価値の最小値を返すミニノードと、最大値を返すマックスノードがる。
バックギャモンではそれらに加えて、サイコロを振ることに対応するノードがある。
本稿ではこれを加重平均ノードと呼ぶ。
多くの論文では「Chance Node」と呼ばれているが、子ノードの評価値の加重平均値を返すので、処理をそのまま名前にした方がわかりやすいと考えた。
ハーフギャモンでは、1-1, 1-2, 1-3, 2-2, 2-3, 3-3 の6種類のサイコロの出目がある。
ゾロ目の確率は 3/9、それ以外の確率は 6/9 である。

最終盤

白黒双方がベアオフ可能状態を最終盤と呼ぶことにする。
黒石の最終盤の状態数は 4^8 / 8! = 65536 / 24 = 1.6。。。あれっ、ではなく 165 通り。

NC(p, n) = 1 if n == 0 || p = 1, p if n == 1, ΣNC(p-1, n-i) for(i=0; i<=n; ++i)
ちなみに、バックギャモンの場合は NC(7, 15) = 54,262

165通り全てについて上がり手数の期待値を計算可能。結果はこちら

計算時間は短い（0.1秒程度）ので、ゲーム起動時に計算しておき、参照するのもあり
最大手数は G 0 0 8 の 5.35676
同じピップス数ならば、空のポイントが無い方が手数が短いか等しい？

理由：上がることが出来ず、インナー内で移動しなくてはいけい場合があるから
例：G 1 2 1 2.1358、G 0 4 0 2.2716
例：G 1 2 1 2.1358、G 0 4 0 2.2716
例：G 2 2 2 2.94376、G 0 0 4 2.82167 ← 反例
例：G 6 1 1 3.36214、G 5 0 2 3.36214

同じピップス数ならば、石数が少ない方が手数が短いか等しい？

理由：大きな目で小さいポイントの石を上げるという無駄がなくなるから
例：G 0 0 4 2.82167、G 2 2 2 2.94376
例：G 0 0 2 1.77778、G 6 0 0 2.44444

ピップス数が小さい方が手数が少ない？

【仮説】手数の期待値が最小になる手が最善手である？

最善でなくても、悪くはない。相手が必ず2手で上がれる場合は、2手で上がれる確率を最大にする手の方がいい場合があるかも

双方ベアオフ可能状態は 165*165 = 27,225

最終盤を完全読み

加重平均＋MinMax評価により、各状態の期待値を算出可能

ただし、石数・上がりまでの手数により状態数は指数関数的に増加するので、現実的に計算可能な局面は限られる
処理を高速化するための、特に有効な手法としては、ハッシュ法、アルファベータがある。前者は問題ないのだが、確率的ゲームであるギャモンには加重平均ノードが入るので、アルファベータの効果はそれほどでもない（と予想される）

局面	期待値	完全読み	ハッシュ（サイズ）	ハッシュ＋αβ
G <4・・・・・・・・・・>4 G	0.555556	0.81ミリ秒	0.20ミリ秒（3）	0.82ミリ秒
G ・<4・・・・・・・・>4・ G	0.406226	47ミリ秒	8.9ミリ秒（42）	63ミリ秒
G ・・<4・・・・・・>4・・ G	0.373876	18.210秒	444ミリ秒（496）	2.934秒
G ・・・<4・・・・>4・・・ G	0.340931	計測不能	3.622秒（1615）	計測不能

※ G <4・・・・・・・・・・>4 G の場合、勝率は 3/9 + 6/9*6/9 = (27 + 36)/81 = 0.777…、
期待値 = 勝率*2 - 1 = 0.555…

終盤をモンテカルロ法で評価

終盤期待値参照

評価関数

本稿では白番で、白からみた評価関数を論じる。値がプラスなほど白に有利とする。
基本は上がりまでの手数だと考える

白の手数を w、黒の手数を b とすれば、評価関数は f(w, b) であらわされる。
手数が少ない方が勝つ確率は高い。b - w > 0 であれば、白が有利
それぞれの手数が少ない場合は逆転する確率は小さく、手数が多いほど逆転する確率が高くなる

上がりまでの手数を計算するのはコストが高いので、ピップス数を用いる方がよい

1回のロールの平均ピップス数は 5.333 なので、ピップス数/5.333 で大雑把な手数を計算できる
バーに石がある場合、ブロックがある場合等は別途補正しなくてはいけない
手番の補正は 5.333/2 を足すだけなので、容易である。
※ 実際にはブロックされたりするので、もう少し小さい数を引く
ピップス数差の最大値は 14*8 = 112

バーに石がある場合の補正

インナーが全てブロックされていれば、移動出来ないので、ピップス数に 5.333 を加える
インナーに空きがある場合、出れない確率（p）を算出し、5.333 * p を加える

ブロック補正

相手ブロックにより、移動出来ない確率 (p) を算出し、5.333 * p を加える
実際に移動出来ない確率を算出するのはコストが高い
1～3の目で移動出来る石が何個あるかを計算し、０であればペナルティとするのがよさげ
場合の数は 9^3 = 729 なので、ハーフギャモンならばテーブル化しておくことも可能

ヒット補正

ヒット可能な場合、実際にヒットする確率（1/2～1/4？）を乗じて相手のピップ数に加える

パフォーマンス計測

2012/08/26 0.009.Dev にて、初期状態から、サイコロの目 2-3 で3手先読みを行った場合：

処理時間：0.470秒、末端ノード数：5429、5429/0.47 = 11,551 NPS
1手先ノード数：４，2手先ノード数：146
平均着手可能数：4.8、サイコロの目の種類：6 なので、4.8^3 * 36 = 3981。
初期状態あたりでは、着手可能数が平均より多いようだ。終盤は石数が少ないから。
将棋と比べると数10倍遅いのは何故？

最も処理時間を要しているのは、可能着手リスト生成だと思われる。ので、処理時間を計測してみた

以下は、可能着手リスト生成を２回行うことで、その処理時間割合を計測してみた結果
１手読み：(0.82-0.45)/0.45 = 0.822222
２手読み：(26-16)/16. = 0.625
３手読み：(904-475)/475. = 0.903158
予想通り、処理時間の大部分は可能着手リスト生成に費やされていた