人生reject

思いついたことをなんとなく書く

一般化リバーシを作りたいと思った話

4×4,6×6のリバーシは完全解析ができており、両プレイヤーが最善手を指した場合、白番が勝利することが分かっている。
どうせそのうち8×8リバーシも解析されることだろう。
じゃあもっと難しく一般化したいなと思うのが人間の性。
実際4次元の4×4リバーシを実装している人も居る。
4次元オセロ

そこで一辺を2l(lは正の整数)でn次元のリバーシ(通常のリバーシは2次元)を作ろうと思ったがめんどくさいのでちょっと必要な下準備だけここにメモしておく。
例のごとくpythonです。numpy使います。

初期盤面

初期状態のn+1次元リバーシを考えた時、石を通るどの超平面で切ったとしてもn次元リバーシが出てくることが理想だと思います(対称性がいい)。
例えば三次元リバーシを考えた時。

一段目
白黒
黒白

二段目
黒白
白黒

一段目
白黒
黒白

二段目
白黒
黒白

という初期配置がありますが、
後者は縦に切り取ることによって

白黒
白黒

という2次元オセロとは異なる配置が出てきます。
よって3次元の場合は前者採用するということです。
ただこの場合、偶奇性から初手で黒が斜めに置けてしまう(立方体の対角が異なる色になる)
したがって偶数次のみを考えることが理想的な気がする。
と思っていたらそれを詳しく解説してくれている人がいた。
blog.livedoor.jp


以下のように色を決めると上で述べたような都合の良い並べ方となります。

  • 石を置く位置は座標点の数字がl,l+1となる点のみ
  • (x_1,\cdots,x_n)の色は\sum x_iが偶数の時は白、奇数の時は黒とする。

とりあえず空白を0,白を1,黒を2としておきます。

import itertools
import numpy

def make_board(n,l):
    board = numpy.zeros([2*l for i in range(n)])
    # 初期配置
    init_place = itertools.product((l-1,l),repeat=n)
    for init in init_place:
        board[init] = 1 if sum(init)%2==0 else 2
    return board

n = 2
l = 4
board = make_board(n,l)
print(board)

実行結果

[[ 0.  0.  0.  0.  0.  0.  0.  0.]
 [ 0.  0.  0.  0.  0.  0.  0.  0.]
 [ 0.  0.  0.  0.  0.  0.  0.  0.]
 [ 0.  0.  0.  1.  2.  0.  0.  0.]
 [ 0.  0.  0.  2.  1.  0.  0.  0.]
 [ 0.  0.  0.  0.  0.  0.  0.  0.]
 [ 0.  0.  0.  0.  0.  0.  0.  0.]
 [ 0.  0.  0.  0.  0.  0.  0.  0.]]

これで生成できてますね。
n=3の時も

 [[ 0.  0.  0.  0.  0.  0.  0.  0.]
  [ 0.  0.  0.  0.  0.  0.  0.  0.]
  [ 0.  0.  0.  0.  0.  0.  0.  0.]
  [ 0.  0.  0.  2.  1.  0.  0.  0.]
  [ 0.  0.  0.  1.  2.  0.  0.  0.]
  [ 0.  0.  0.  0.  0.  0.  0.  0.]
  [ 0.  0.  0.  0.  0.  0.  0.  0.]
  [ 0.  0.  0.  0.  0.  0.  0.  0.]]

 [[ 0.  0.  0.  0.  0.  0.  0.  0.]
  [ 0.  0.  0.  0.  0.  0.  0.  0.]
  [ 0.  0.  0.  0.  0.  0.  0.  0.]
  [ 0.  0.  0.  1.  2.  0.  0.  0.]
  [ 0.  0.  0.  2.  1.  0.  0.  0.]
  [ 0.  0.  0.  0.  0.  0.  0.  0.]
  [ 0.  0.  0.  0.  0.  0.  0.  0.]
  [ 0.  0.  0.  0.  0.  0.  0.  0.]]

(石のある場所だけ抜き出し)
きちんと互い違いになってますね。

探索方向の設定

石をひっくり返せるか捜索するのに、ある石から見て一方向に進めて捜索する(たてよこななめ全部見るって話)。
8×8の場合を考える。
例えば、(4,4)地点に石が置けるかどうかの捜索は、(3,3),(3,4),(3,5),(4,3),(4,5),(5,3),(5,4),(5,5),8方向を調べればよい。
これらの方向を移動するためには(-1,-1),(-1,0)(-1,1),(0,-1),(0,1),(1,-1),(1,0),(1,1)の値を起点(今回の場合は(4,4))に足して移動する方法が単純で嬉しい(実際(-1,-1),...,(1,1)を(4,4)に足すことによって(3,3),...,(5,5)が得られていることが分かる)。
この方向の値は{-1,0,1}の直積で得ることができる。
pythonで直積を取るにはitertoolsを使えばよい。

import itertools

n=2
directions = list(itertools.product((-1,0,1),repeat=n))
directions.remove(tuple([0 for i in range(n)]))
print(directions)

結果は

[(-1, -1), (-1, 0), (-1, 1), (0, -1), (0, 1), (1, -1), (1, 0), (1, 1)]

生成できてます。