超現実数応用編: Domineeringの局面の値（その１）

青・赤ハッケンブッシュ（その１）超現実数（Surreal number）では非不偏（Impartial）ゲームの局面の値を超現実数（Surreal number）を用いて求める方法を紹介しました。

"Winning Ways for Your Mathematical Plays, Volume 1" J.H.Conway,etcではさらに超現実数を拡張してより複雑なゲームの局面の値を求めています。

今回はこの本に出てくるゲーム Domineeringを使って局面の値を求めるコードを作って行きます。

Domineeringゲーム

Domineering (Wikipedia 英語) に説明がありますが。タイル状のボードにドミノを先手は横に、後手は縦に置いていき置けなくなった方が負けというシンプルなゲームです。下の図では13手目で後手の横が置けなくなった状態を示しています。

基本的な局面の値G

青・赤ハッケンブッシュ（その１）超現実数（Surreal number）でやったように基本的なボードの空エリアの基本的な局面の値Gを求めます

	ボードの空エリア	G	値
(a)		${ \lbrace \ \ | \ \ }\rbrace$	0
(b)		${ \lbrace \ \ |0 }\rbrace$	$-1$
(c)		${ \lbrace \ \ |0 }\rbrace$	$-1$
(d)		${ \lbrace \ \ |-1,0 }\rbrace$	$-2$
(e)		${ \lbrace -1 \ \ |0,1 }\rbrace$	$-\frac1{2}$

ここまでは

\begin{align}
&G = \{L_{max}\ | R_{min}\}のとき　\\
&L_{max}\ \lt R_{min} なので
\end{align}

前回と同様な方法でGの数値を求まりましたが、そうでない例が出てきます。

局面の値Gが数値にならない場合

すなわち以下のような$L_{max}\ \ge R_{min}$のケースです

	ボードの空エリア	G	値
(f)		${ \lbrace 0\ | \ 0 }\rbrace$	-
(g)		${ \lbrace 1\ | \ -1 }\rbrace$	-
(h)		${ \lbrace 0\ | \ -1 }\rbrace$	-

この場合はこの表記(switch)を残したまま、次のステップを評価する必要があり。アルゴリズムが複雑になります。ただ中には評価できる組み合わせもあるので、それは今後の具体例の中で考えていきたいと思います。

とりあえず今回はDomineeringゲームの６タイルのエリアのすべてのGの値を求めることを目標にして以下のステップで考えていきます。

1. 6タイルのエリアのすべての形を求める
2. そこに縦、横のドミノを置いたときの残りのサブエリアを求める
3. すべての手の後のサブエリアの内、最も有利なもの（$L_{max}、R_{min}$）を求める
4. $L_{max}、R_{min}$から局面の値Gを求める

次回の（その２）ではこの１，２を考えます。