はじめに
みなさんは，立体四目という遊びをご存知でしょうか。
ググってみるとなんとなくお分かりいただけると思いますが，4×4×4の空間内で四目並べをするものです。
これを安易な気持ちで4次元に拡張してしまったので，そのことについて書いてみたいと思います。
できたもの
こんな感じのものができました。
iOS上でPythonを動かすPythonista 3を使用して，iPadで作成しました。
できること
- 4次元四目で遊ぶ
- 盤面の保持 (閉じてもリセットされない)
- 棋譜の保存・読み込み
- CPU対戦
実装の話
一応GitHubにも上げておきますが，環境が限定的なので具体的なUIの実装については端折ります。
集計
真面目に集計しようとすると組み合わせが膨大なので，以下のような手順ですべての並びを網羅することにしました。
- 走査する方向を表すベクトルを決める
- その方向について，走査開始点として適当な座標をすべて列挙する
- 開始点から指定の方向に向かって走査する
1. 方向ベクトルの列挙
例えば
- x軸 → $(1, 0, 0, 0)$
- y-z平面の対角線 → $(0, \pm1, 1, 0)$
- x-z-w立方体の対角線 → $(\pm1, 0, \pm1, 1)$
- 超立方体の対角線 → $(\pm1, \pm1, \pm1, 1)$
といった感じです(すべて複号任意)。
1次元での走査では$(1, 0, 0, 0)$の軸をずらしていけばいいので，
for i in range(4):
_aggregate([[1, 0, 0, 0][i:]+[1, 0, 0, 0][:i]])
とすればOKです。
(_aggregateは2以降で出てくる関数です)
2次元以上での走査は，統一的な実装にすると可読性が悲しくなるので，あきらめて全パターンを書きました。
複号任意とするために，直積を返してくれるitertools.productを利用しました。
例えば，x-z-w立方体については，product([-1, 1], [0], [-1, 1], [1])とすることで4つの対角線を表すことができます。
2. 開始点の列挙
ある軸について，走査方向が+1となっている場合には，0→1→2→3と進むために開始点の座標は0でなければなりません。
逆に，-1となっている場合には3→2→1→0と進むために3から開始する必要があります。
0の場合には，0, 1, 2, 3のすべてがあり得ます。
これを素直に書いてあげます。
def start(val):
if val == 1:
return [0]
elif val == -1:
return [3]
else:
return range(4)
3. 走査する
可能なすべての開始点から，指定の方向に向かって走査していきます。
開始点は，4つの軸それぞれについて複数ある中からすべての組み合わせを列挙するので，再びitertools.productの出番です。
具体的にはこんな感じになります
def _aggregate(vec):
for X, Y, Z, W in vec:
if (X, Y, Z, W) == (0, 0, 0, 0):
continue
for x, y, z, w in product(start(X), start(Y), start(Z), start(W)):
s = sum(
self.get_cell(x+X*i, y+Y*i, z+Z*i, w+W*i).player for i in range(4)
)
if s == 4:
self.black += 1
elif s == -4:
self.white += 1
各マスの状態は，●が+1，○が-1，何も置かれていなければ0としてあるので，全部足してみて絶対値が4なら揃っていることがわかります。
CPU対戦
CPUは，現時点では以下のような非常にシンプルなものです。
- 自分が3目揃っていれば，4目揃える
- 相手が3目揃っていれば，阻止する
- 相手が2目揃っている筋について，多くの筋で共通している箇所を阻止する
- 自分が2目揃っている筋について，多くの筋で共通している箇所に置く
- 上の4つで決まらなかった場合は開いているところに適当に置く
このゲームでは3を同時に2つ作れば勝ちなので，3と4のような処理が入っています。
(同じ優先順位の箇所が複数ある場合にはランダムで選ぶ)
単純なアルゴリズムの割には強いです。
さいごに
Pythonistaをお持ちの方はぜひ遊んでみてください。
それ以外の環境に移植したという方がいらっしゃったらおしえていただけると嬉しいです!