超現実数応用編: Domineeringの局面の値（その１）ではDomineeringゲーム の紹介とその基本的な局面の値Gを求めました。
今回は以下のPythonコードを作って行きます
- Domineeringゲームの６タイルのエリアすべての形を求める
- そこに縦、横のドミノを置いたときの残りの空きエリアを求める
６タイルのエリアすべての形を求める
これはまさにポリオミノ (Wikipedia)の$n=6$のヘキソミノ35個の形を求めることなので、ポリオミノのピースの数を求めるで求めた以下の形のデータをそのまま使います。
縦、横のドミノを置いたときの残りの空きエリアを求める
ここに縦、横のドミノを置いたときの残りのサブエリアは、複数の連続したエリアに別れてしまう場合があるので意外に面倒です。
ここはちょっと視点を変えて、連続したエリアを グラフで表すようにします。例えばヘキソミノの１番であれば以下のように縦のエッジを青で、縦のエッジを赤で表します。
こうすれば例えば真ん中の縦の部分にドミノを置いた場合は、グラフからそこの青のエッジを取り除いたのと同じことになります。
| サブエリア | グラフ表現 | エッジを削除 |
|---|---|---|
 |
 |
 |
この様にエリアをグラフに変換すると、pythonのライブラリの networkx の以下の機能を使って
- remove_nodes_fromを使ってエッジと両端のノードを削除する
- connected_componentsで残った連結ノードを取りだす
残りのサブエリアを求めることができます。
エリアをグラフに変換
順番にコードを書いていきます。まずエリアをグラフに変換する関数 bd2gです。縦のエッジは青、横のエッジは赤の属性をセットします。
from itertools import combinations
import networkx as nx
def diff(p1,p2): # difference of two tile
return (abs(p1[0]-p2[0]),abs(p1[1]-p2[1]))
def bd2g(bd): # board to graph conversion
G = nx.Graph()
for p1,p2 in combinations(bd,2):
d = diff(p1,p2)
if d == (0,1) or d == (1,0):
G.add_edge(p1,p2,color=("blue" if d==(0,1) else "red"))
return G
def printEdges(G):
print(f"# --- Edges ---")
for eg in G.edges:
col = G.edges[eg]["color"]
print("#", eg, col)
G = bd2g(((0, 0), (1, 0), (2, -1), (2, 0), (3, -1), (4, -1)))
printEdges(G)
# --- Edges ---
# ((0, 0), (1, 0)) red
# ((1, 0), (2, 0)) red
# ((2, 0), (2, -1)) blue
# ((2, -1), (3, -1)) red
# ((3, -1), (4, -1)) red
エッジを削除
ここから青のエッジを削除します
G.remove_nodes_from([(2,-1), (2,0)])
printEdges(G)
# --- Edges ---
# ((0, 0), (1, 0)) red
# ((3, -1), (4, -1)) red
残った連結ノードを取りだす
G1 = list(nx.connected_components(G))
print(G1)
# [{(1, 0), (0, 0)}, {(4, -1), (3, -1)}]
これでドミノを置いた後のサブエリアを求められたので、それぞれの局面の値Gを再帰的に求めて足し合わせれば良いことになります。
次回の（その３）では、いよいよサブエリアの局面の値Gから現在のGを求める方法を考えます。