青・赤ハッケンブッシュと超現実数（Surreal number）

青・赤ハッケンブッシュ（Stalk）

青・赤ハッケンブッシュ(Red-Blue Hackenbush)には以下のようなものがあります。今回は最も簡単なStalkに注目してその局面がどちらに有利かを判定する値を求めていきます。

グリーン・ハッケンブッシュとGrundy数ではグリーン・ハッケンブッシュのような不偏ゲーム（先手と後手の打てる手が同じ）の局面の判定をGrundy数を用いて行いました。しかし赤・青ハッケンブッシュは、ルールが対象的ではない非不偏ゲームなので、違ったアプローチが必要です。

赤・青ハッケンブッシュに馴染みのない方はこのYoutube（英語）がお勧めです。

HACKENBUSH: a window to a new world of math

ルールは、グリーン・ハッケンブッシュと同じですが、青は青のみ、赤は赤のみを取ることができ、取るものがなくなったら負けです。

青・赤ハッケンブッシュの簡単な例

基本的な局面の値は

• (a) どちらも打つ手がないとき（先手の負け）$\rightarrow 0$
• (b) 青が１手で勝つとき$\rightarrow 1$
• (c) 赤が１手で勝つとき$\rightarrow -1$

	青・赤ハッケンブッシュ	局面の値	超現実数表現
(a)		0	${ \lbrace \ \ | \ \ }\rbrace$
(b)		$1$	${ \lbrace 0|\ \ }\rbrace$
(c)		$-1$	${ \lbrace \ \ |0 }\rbrace$

超現実数（Surreal number）表現

超現実数表現では、以下のように

V = \{B_1, B_2,...,B_n \ | \ R_1, R_2,...,R_m \}

• 左側に青が手を打ったあとの局面の値を列挙する
• 右側に赤が手を打ったあとの局面の値を列挙する

したがって(b)では青が青エッジを取ると(a)になるので左に0を、赤は打つ手がないので右に空白を書きます。

超現実数表現から局面の値を求める

超現実数表現$V$の値$x$は$B_1, B_2,...,B_n \ \lt x \lt \ R_1, R_2,...,R_m$を満たす$x$で

1. 絶対値が最小の整数
2. 整数がなければ分母が最も小さい$2$のべき乗の分数（$1/2, 5/8$など）
3. 空白は、左は$-\infty$、右は$\infty$とみなす

以下にいくつか例を挙げます、たくさん数が並んでいるとややこしいですが、要は左は最大値、右は最小値を抜き出せは簡略化できます。

超現実数表現	簡略化	局面の値
${ \lbrace \ \ |\ \ }\rbrace$	"	$0$
${ \lbrace 0 \ | \ 1 }\rbrace$	"	$1/2$
${ \lbrace 0,1 \ | \ }\rbrace$	${ \lbrace 1 \ | \ \ }\rbrace$	$2$
${ \lbrace \ \ | \ 0,-1.-2}\rbrace$	${ \lbrace \ \ |-2}\rbrace$	$-3$
${ \lbrace -1 \ | \ 0,-1/2}\rbrace$	${ \lbrace -1 |-1/2}\rbrace$	$-3/4$
${ \lbrace 0,1/2 \ | \ 1,3/4}\rbrace$	${ \lbrace 1/2 \ | \ 3/4}\rbrace$	$5/8$

この簡略化した超現実数表現から局面の値を求める関数$simple$を作ります。空白は$\pm inf$で表します

from sympy import Rational as r
from math import ceil, inf
def simple(L, R):  # Simplest forms of surreal number
  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

for s in [[-inf, inf],[0,1],[1,inf], [-inf,-2], [-1,-r(1,2)],  [r(1,2),r(3,4)]]:
  print("# ", s, simple(s[0], s[1]))
  
#  [-inf, inf] 0
#  [0, 1] 1/2
#  [1, inf] 2
#  [-inf, -2] -3
#  [-1, -1/2] -3/4
#  [1/2, 3/4] 5/8 

青・赤ハッケンブッシュから超現実数表現

• (d) は青が取ると(a)になり、赤が取ると(b)になるので超現実数表現は${ \lbrace (a) | \ (b) }\rbrace$ = ${ \lbrace 0 \ | \ 1 }\rbrace$で、局面の値は$\Large \frac1{2}$です
• (e) は青が取ると(a)、赤が下のエッジ取ると(b)、上のエッジを取ると(d)となるので超現実数表現は${ \lbrace (a) | \ (b),(d) }\rbrace$ = ${ \lbrace 0 \ | \ 1,\Large \frac1{2} }\rbrace$で、局面の値は$\Large \frac1{4}$です

	青・赤ハッケンブッシュ	超現実数表現	局面の値
(d)		${ \lbrace (a) | \ (b) }\rbrace$ = ${ \lbrace 0 \ | \ 1 }\rbrace$	$\Large \frac1{2}$
(e)		${ \lbrace (a) | \ (b),(d) }\rbrace$ = ${ \lbrace 0 \ | \ 1, \Large \frac1{2} }\rbrace$	$\Large \frac1{4}$

超現実数表現を求めるコード

文章で書くとかなり複雑ですが、再帰関数でコードを書くととってもシンプルになります。青・赤ハッケンブッシュは青が0、赤が1で地面からのリストで表現しました。例えば(e)は$[0,1,1]$です。

def gameValue(hacken):
  s = [-inf, inf]    #  +-infinity
  for i, br in enumerate(hacken):  # br: 0-blue, 1-red
    s[br] = [max, min][br](s[br], gameValue(hacken[:i])) 
  return simple(s[0], s[1])

for t, hk in [ ("a",[]), ("b",[0]), ("c", [1]),("d", [0,1]), ("e", [0,1,1])]:
  print(f"# ({t}) :", hk, gameValue(hk))
# (a) : [] 0
# (b) : [0] 1
# (c) : [1] -1
# (d) : [0, 1] 1/2
# (e) : [0, 1, 1] 1/4

（開発環境：Google Colab）