トーラス上の Hex ゲームの研究
永森枝里子

1(指導教員: 金子 晃)

はじ めに結ばないとトーラス上で閉曲線にならないので, 通常の Hex に比べてはるかに難しく, かつ面白いゲームとなる．
トーラス Hex についてすぐ分かるいくつかの考察を述べる．
(1) 一方が閉曲線を完成できない間は, 他方は閉曲線を完成させる可能性が必ず残っている．実際, 例
えば黒石の位相幾何学的パターンがホモロジー的に自明ならば, これを除いた残りの本体 (無用なループに対応して単連結な他の連結成分が生じうるが, それらは無視する) は相変わらずホモロジー群が Z 2 なので, まだどちらもそれぞれの基本ループを完成させる余地が残っている．
(2) 一方が自分の基本ループを完成させると, 他方はもはや自分の基本ループを完成させることはできない．実際, 基本ループ, 例えば α を取り去った後の図形は, ホモロジー群が Z に同型となり,しかもその生成元は α と元のトーラスで凖同位(homologous) な閉曲線となるので, β はもう作れない．あるいは, ホモロジー群の２個の生成元は交点数が１となることからも分かる.

Hex ゲームは 1950 年代に作られ, 数学的研究も豊富になされてきた. 本研究ではこの Hex ゲームについて,盤をトーラスに取り替えることを試みる. ここではまず, 通常の Hex について紹介し, その後トーラス Hexの概要, 注意点, 勝敗の判定方法, 戦略について記す.

2

Hex ゲームと は

通常の Hex ゲームは, 下図のように六角形のマス目を並べた盤で２組の対辺の一方を黒, 他方を白の陣地として, 相互に１手ずつマスに石を並べてゆき, 先に自分の陣地である対辺を繋げた方が勝ちという対戦ゲー
ム (二人零和有限確定完全情報ゲーム) である.
WhiteBlackBlackWhite

図 1. 通常の Hex ゲームのボード
Hex については先行研究より次のことが知られている. 詳細については参考文献 [１] を参考にされたい.
(1) マス目の形が四角形でなく六角形のため, 通常の囲碁のように両者切れ切れという状態が生じず,従って必ず勝敗が着く．
(2) 先手必勝である．実際, (1) により必ず勝敗が着くのだから, 双方が最善を尽くせば, どちらかに必勝の手順があるはずであるが, もし後手に必勝の手順があるとすれば, 先手は初手を適当なところに置き, 以後は後手の必勝手順に従えば, 先手が勝つことになり矛盾する．この際, もし途中で既に自分が打った位置に必勝手順が重なったならば, また任意の空き地に打つ．囲碁などと異なり,自分の石は必ず自分に有利に働くことに注意．

34

ト ーラ ス Hex の注意点

黒が α + β という閉曲線を作った場合を考えてみてほしい. この場合, ボードゲーム上黒は成功したように見えるが, 白も α + β を作ることができ, これは白としても成功したように見える.
従って, このゲームをゲームとして成立させるためには, 次のいずれかをゲームの定義として採用する必要がある.
(a) 黒は α 以外の閉曲線, 例えば α + β を作ってしまった場合, その時点で反則負けとする. 白についても同様．
(b) 黒は α あるいはそれを含むホモロジー類, 例えばα + β を実現する閉曲線を作ればよしとする．白についても, β あるいはそれを含むホモロジー類を実現する閉曲線を作ればよしとする．従って,勝敗は先にこのようなループを作った方を勝ちと定める．
(c) 黒は mα + nβ, m > 0, n ≥ 0 というホモロジー類に対応する閉曲線を, 白は kβ − lα, k > 0, l ≥ 0に対応する閉曲線を作ることを目標とする．

ト ーラ ス Hex の概要

トーラスは, Z 2 と同型な１次ホモロジー群を有する(参考文献 [2] など参照) ので, それらの生成元 (以下,α, β と記す) を順に黒と白に割り当て, 先にサイクルを完成させた方を勝ちとするのである．ただし, トーラス Hex 盤の表現は下図のように, 通常の Hex 盤にのりしろ糊代を付け, 対辺を同一視することで実現した．

αWhiteBlackBlackWhiteβ

図 2a. ト ーラ スと その基本サイ ク ルWhiteBlackBlackWhite図 3. 黒と 白双方が α + β を 構成し た例
試行してみた結果, ゲームとしては, (a) だけではゲームの変化が狭すぎるように見える．α を作るのはなかなか難しいが、α ± β はわりと簡単に作れるからである．

図 2b. ト ーラ ス Hex
ゲームのボード の表現

通常の Hex では, 対辺のどのマス目に辿り着いても勝ちだが, トーラス Hex 盤では, 同じ位置のマス目と57

6(b) は至って簡明だが, ともに同じホモロジー類が実現できるので, 既につながることが確定した方が後から繋げた方に手数で負けるという囲碁のダメ詰めのようなつまらない状況が形式的には起こり得る．黒がα にこだわる理由も希薄になって, 単に先に閉曲線を作った方が勝ちというのとあまり差はなく, 全く別のゲームになってしまう恐れがある．
(c) はやや数学的で, とっつきにくいが, 黒が間違って敵のサイクル mα − nβ を作っても, 白はまだ自分のサイクル kβ − lα で mn = kl を満たすものを作る可能性がある (ただしこの等式を満たさないものはもう作れない) ということで, 通常の Hex の勝敗に近い状況を提供している．

戦略

通常の Hex では，序盤のうちは石を中央に置く方が働きがよいことはよく知られているが，トーラス Hex
では，当然そのような区別は無く，辺に置いた石も中央の石と全く同等である．連結戦略については，局所的には通常の Hex と同じで，図 4 のような配置が効率的に連結性を確保する単位となるが，対局的には，辺をワープする連結性が慣れていないとなかなか難し
い．作戦的にも，最後に繋ぐ対象が辺ではなく一個の石 (ただし特定の石である必要はなく，ゲームの進展につれて臨機に変化はし得るが) であるところが，読みを難しくする.

注 上の主張はサイクルの交点数を計算すれば分かる：(mα − nβ, kβ − lα)= mk(α, β) − nk(β, β) − ml(α, α) + nl(β, α)= mk − nl
ここで交点数が反対称な双一次形式であることを用いた．特に, (β, α) = −(α, β). これは交点数 (α, β) が,α, β の交点において, α の正の接線方向と β の正の接線方向をこの順番に並べたものがトーラス面の正の向きの座標となるとき +1, 負のとき −1 と定義し, 全ての交点についてこれらを加えたものとして定義され, 更にそれを Z 係数に線型に拡張したものだからである．
以上より, 本研究では (c) を定義として採用する.

5

勝利判定のア ルゴ リ ズム

黒の場合の勝利判定の手順を示す. 黒は mα +nβ(m > 0, n ≥ 0) を作ることを目標とする. 置いた石の座標を (i0 , j0 ) とし, m, n の初期値を m = n = 0 とする. 整数 si , sj (初期値は si = sj = 0) を用いる.
(1) 置いた石の位置を記憶, これを基点として自分に隣接する石に沿って探索開始. 探索中の石の座標を (it , jt ) とする.
(2) it−1 − it = 10 の場合 si = si + 11, it−1 − it = 10の場合 si = si − 11 とする. β 方向でも同様に jt−1 − jt = 10 の場合 sj = sj + 11,jt−1 − j1 = 10 の場合 sj = sj − 11 とする. 更に
α 方向, β 方向それぞれについて基点からの差分
di = it − i0 + si , dj = jt − j0 + sj を計算する.
(3) di = 11 ならば m = m + 1, di = −11 ならば
m = m − 1 とする. 同様に dj = 11 ならばn = n + 1, dj = −11 ならば n = n − 1 とする.
m の値が変化したなら, si = 0, n の値が変化したなら, sj = 0 とする.
(4) 基点の石 (i0 , j0 ) と隣接するかを調べる. 隣接すれば基点の石を (it , jt ), 探索中の石を (it−1 , jt−1 )として, (2)(3) より m, n の値を求め (9) へ, 隣接しなければ (5) へ.
(5) 隣合う黒石のうち, 未探索の石の数を求める.
(6) (5) で求めた石の数が 0 個なら (8) へ, 1 個ならその石に進み (2) へ, 2 個以上なら (7) へ.
(7) 探索中の石の座標を記憶, 連結している石を一つ選択し (2) へ.
(8) (it , jt ) = (i0 , j0 )(探索中の石が基点の石) ならば終了, そうでなければ一つ前に記憶した点へ戻って (2) へ.
(9) m > 0, n ≥ 0 ならば黒の勝ち, そうでなければ(5) へ.

図 4. 基本的な連結パ
タ ーン . こ れら の黒石は２ 者択一で繋がる

図 5. マスの評価例

コンピュータに良い手を打たせるには，自分自身が連結成分を増やすこと, また相手の連結成分が増えないようにすることを考えなければならない. 本研究では, これらを加味して盤上のマス目一つ一つに評価値を定め, 最も評価値の高いマスに石を置くものとする.
図 5 の石がそれぞれ白, 黒だった場合に下記のような戦略をとる.
・白 (コンピュータ) が勝つための戦略 (図 5:白石)(1) 基本的な連結パターンの増加.
図 4 で示した連結パターンにあたる図 5(4)(7)(8)(11) の評価を高くする.
(2) 連結パターンからの連結.
図 5(5) の評価を高くする. 図 5(2) に黒石がある
場合 (3) の評価を高くする. 逆も同様.
(3) 連結成分の増加.
白石に隣接するマスの評価を高くする. 図 5(1)(6)(9)(10)(12)-(16).
(4) 勝利の一手.
そこに置けば白石が勝利することが明らかなマスがある場合, 評価値に関係なくそのマスに置く.
図 5 が黒石の場合に上記 (1)-(3) と同様にマスを評価することで, 黒 (人) を勝たせないための戦略となる.

7

ま と めと 今後の課題

今回はトーラス Hex がゲームとして成立するための定義を述べ, トーラス Hex をゲームとして確立させた. また勝敗の自動判定, 簡単な戦略を持って人の相手ができるコンピュータゲームの実装を行った. 今後は更に強いプログラムを作ることを目標とする.

参考文献[1] Cameron Browne, “Hex Strategy : Making theRightConnections”, Cyberite Pty Ltd, (2000).
[2] 加藤十吉, “位相幾何学”, 裳華房, (2010).
58