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

（その３） までに作った関数を使っていよいよDomineeringゲームの６タイルの35個の全てのエリアに対して局面の値Gを求めます

関数Domineering

エリア bdに対して以下のステップで局面の値Gを求めます。

1. エリアのデータをグラフGに変換(bd2g)
2. Gのすべてのエッジを一つづつ除いて、残りの複数のサブエリアに対して関数Domineeringで局面の値を求め、和を求める（局面の値が$\lbrace 0\ | \ 0 \rbrace$のように数値にならない場合はそのまま残す）
3. エッジの色に応じて超現実数のL（青）とR（赤）に分ける
4. 関数simpleで（出来れば）数値にする

def Domineering(bd):
  if len(bd) == 1: return 0
  G = bd2g(bd)  # board -> Graph
  ret = [set([-inf]),set([inf])]
  for eg in G.edges:            # for all edges in G
    G1 = deepcopy(G)
    G1.remove_nodes_from(eg)    # remove edge and 2 nodes
    nextBD = list(nx.connected_components(G1)) # get remaining parts
    nextG = 0
    for bd1 in nextBD:
      g1 = Domineering(list(bd1))
      if g1 != 0: # ignore 0
        if type(g1) is tuple:   
          if type(nextG) is tuple:  print(("???? not suported", nextG, "+", g1))
          nextG = g1    # assume only one tuple 
        else:
          nextG += g1   
    ret[0 if G.edges[eg]["color"]=="blue" else 1].add(nextG)  # add to ret {L|R} based on the edge color
  return simple(ret)   # simplyfy surreal number

６タイルの全てのエリアの対局面の値Gを求める

（その１）で求めた６タイルの全てのエリアのデータがリストpolyにはいっているとすると、以下のような結果が得られました。

for n, bd in enumerate(poly,1):
  print(f"{n}: G = {Domineering(bd)}")
# 1: G = -3/2
# 2: G = ((0, 0), -1/2)
# 3: G = -3
# 4: G = ((0, 0), -2)
# 5: G = (1, 1)
# 6: G = 0
# 7: G = ((0, 0), 0)
# 8: G = (-1, -1)
# 9: G = -1/2
# 10: G = (2, (0, 0))
# 11: G = -1/2
# 12: G = -3/2
# 13: G = 3/4
# 14: G = 0
# 15: G = (2, -1/2)
# 16: G = -3/2
# 17: G = ((0, 0), -1)
# 18: G = ((0, 0), -1/2)
# 19: G = (2, -1/2)
# 20: G = (2, 1)
# 21: G = (1, 1)
# 22: G = (1, -1)
# 23: G = ((0, 0), -1)
# 24: G = 0
# 25: G = 3/4
# 26: G = 0
# 27: G = (0, -2)
# 28: G = 0
# 29: G = (1, -1)
# 30: G = (1, 0)
# 31: G = (1, -1)
# 32: G = (-1, -2)
# 33: G = (0, -1)
# 34: G = (-1, -1)
# 35: G = (-1, -1)

"Winning Ways for..."Figure 20 と答え合わせ

これだと合っているのかよくわからないので、Figure 20と同じ順番に並び替えて表示しました。赤の表記が回答です。
以下の点を考慮すれば、答えは合っているようです。

• $\lbrace 0\ | \ 0 \rbrace$は star *に変える
• エリアの縦横が違うものはL/Rが入れ替わって符号が逆

というわけで長くなりましたが、なんとかDomineering ６タイルの全てのエリアの局面の値Gを求めることが出来ました。

今回は６タイルまでのケースに限って現れる局面の値Gを処理しましたが、それ以外は not supportedのコードです。今後時間と気力があれば７タイルも挑戦したいと思います。

（開発環境：Google Colab）