（その2）に引き続きDomineeringゲーム局面の値Gを求めます。
3 すべての手の後のサブエリアの内、最も有利なもの（$L_{max}、R_{min}$）を求める
4 $L_{max}、R_{min}$から局面の値Gを求める
すべての手の中の最も有利なものを求める
このようなエリアを考えます
L(青)の可能な手と最善な手
| 削除するエッジ | 削除後のエリア | 削除後のG |
|---|---|---|
| 青 (1) |  |
$-\Large \frac1{2}$ |
| 青 (2) |
 |
$1+(-1)=0$ |
\begin{align}
&L_{max}=max(0,-\frac1{2})=0 \\
&従って最善の手は青(2)
\end{align}
R(赤)の可能な手と最善な手
R(赤)の可能な手は(3),(4),(5)のなので削除後のエリアは以下になります
| 削除するエッジ | 削除後のエリア | 削除後のG |
|---|---|---|
| 赤 (3) |  |
${ \lbrace 1\ | \ 0 }\rbrace$ |
| 赤 (4) |
 |
$1$ |
| 赤 (5) |
 |
$-1$ |
\begin{align}
&この場合は\{ 1\ | \ 0 \}を[0,1]の範囲
と考えます\\
&R_{min}=min(0,\{ 1\ | \ 0 \}, -1)=-1 \\
&従って最善の手は青(2)
\end{align}
最善な手を求める関数
${ \lbrace 1\ | \ 0 }\rbrace$のような超現実数表現を含む値の中から最善な手を求める関数 bestMoveを作ります。2つの値を比較する isBetterではtupleかnumberで４つのケースに分けてハンドルしています。
from math import ceil, inf
from functools import reduce
def bestMove(l, lr=1): # return the max, 0 < (1,2), (1,2) < 3, assume no (4,6),5 pattern
def choose(a,b, lr):
def isBetter(x, y, lr): # is x more advantage than y? lr: l=1, r=0
return [True, False, False, True][(lr)*2 + int(float(x)>float(y))]
if (type(a) is not tuple) and (type(b) is not tuple):
return a if isBetter(a, b, lr) else b # a, b: number
if (type(a) is tuple) and (type(b) is tuple): # a, b: tuple
ret = a if isBetter(a[1-lr], b[1-lr], lr) else b # compare the better one
if a[1-lr] == b[1-lr]: # if it is the same
ret = a if isBetter(a[lr], b[lr], lr) else b # compare the other number
return ret
#----- a or b is tuple -----------
if (type(b) is tuple): a, b, tp = b, a, 2 # swap a and b
if isBetter(b, a[1-lr], lr): return b # type 2 : a=tuple, b=number
if isBetter(a[lr], b, lr): return a
print("??? not comparable")
return a # if not comparable choose number
return reduce(lambda x,y: choose(x,y, lr), l)
for l in [[0,-0.5], [0, (1,0), -1]]:
print(f"# best move among {l} is: {bestMove( l, 0)}")
# best move among [0, -0.5] is: -0.5
# best move among [0, (1, 0), -1] is: -1
超現実数表現を簡単化する関数
青・赤ハッケンブッシュ（その１）超現実数（Surreal number）で作った関数 simpleを拡張して、LとRのどちらかが$\lbrace 0\ | \ 0 \rbrace$の場合を特別ケースとして扱います。
| 超現実数表現 | Star表現 | 値 |
|---|---|---|
| ${ \lbrace { \lbrace 0\ | \ 0 }\rbrace | { \lbrace 0\ | \ 0 }\rbrace }\rbrace$ | ${ \lbrace *\ | \ * }\rbrace$ | $0$ |
| ${ \lbrace { \lbrace 0\ | \ 0 }\rbrace | r }\rbrace : \ r \le 1$ | ${ \lbrace *\ | \ r }\rbrace : \ r \le 1$ | $0$ |
| ${ \lbrace { \lbrace 0\ | \ 0 }\rbrace | r }\rbrace : \ r \gt 1$ | ${ \lbrace *\ | \ r }\rbrace : \ r \gt 1$ | $r$ |
from sympy import Rational as r
from math import ceil, inf
def simple(sur): # Simplest forms of surreal number
L, R = bestMove(sur[0], 1), bestMove(sur[1], 0) # best choice for L and R
if type(L) is tuple or type(R) is tuple: # either one is switch case
#----- (0,0) special handling -----------
if L == (0,0) and R == (0,0): return 0 # {*|*} = 0
if L == (0,0) and R > 0: return 0 if R <= 1 else R # {*|1/2}
if R == (0,0) and L < 0: return 0 if L >= -1 else L # {-1|*}
return (L, R)
if L >= R: return (L, R) # ex. {1|0}
#---- previous code ------
if L == -inf and R == inf: return 0 # {|}
dn = 1 # denominator
ret = int(L)+1 if abs(L) <= abs(R) else ceil(R)-1 # inner integer of smaller one
while ret <= L or ret >= R:
if ret <= L: ret += r(1,dn)
if ret >= R: ret -= r(1,dn)
dn *= 2
return ret
これで必要な関数は出来たので（その４）ではDomineeringゲームの６タイルのエリアの局面の値Gを求めて行きます。
（開発環境：Google Colab）