ヘキサポーンの後退解析

後退解析の理解のために、メモリがシビアじゃない問題で解いてみようと思った。で、とりあえずヘキサポーン。ヘキサポーンはチェスのポーンを3個ずつ持って3x3の盤で遊ぶゲームで、一番奥まで侵入したら勝ち。3 ** 9で2万状態あれば十分収まってしまう。対称性とか、駒は最大3個とかを考えるともっと小さいはずだけどそれは「メモリを節約するチューニング」だと割り切って捨てた。

ソースはテストケース込みで300行弱。 http://svn.coderepos.org/share/lang/python/retrograde/retrograde.py

4回後退するだけで結果が出た。初期状態は「両者最善手を打てば引き分け」だそうな。実行結果:

-----
.vv
v..
^^^
DRAW
-----
  v.v
  ^v.
  .^^
  DRAW
-----
  v.v
  v..
  .^^
  DRAW
-----
  vv.
  ^.v
  .^^
  WIN
-----
v.v
.v.
^^^
DRAW
-----
  .vv
  v^.
  ^.^
  WIN
-----
  .vv
  .v.
  ^.^
  DRAW
-----
  vv.
  .^v
  ^.^
  WIN
-----
  vv.
  .v.
  ^.^
  DRAW
-----
vv.
..v
^^^
DRAW
-----
  .vv
  v.^
  ^^.
  WIN
-----
  v.v
  .v^
  ^^.
  DRAW
-----
  v.v
  ..v
  ^^.
  DRAW

自分が端歩をついたときに反対側の端歩をつくとか、真ん中をついたときにそれを取らない、というミスを後手がしたら勝てる、ということか。正しく動いているように見える。

  vv.
  ^.v
  .^^
  WIN
-----
  vv.
  .^v
  ^.^
  WIN

さて、問題が小さくてチューニングするまでもなくメモリに乗る今回のようなケースは簡単だったけども実際には可能な限りメモリを節約したいわけだな。例えば今回の場合3 ** 9 = という無駄にでかい空間を確保したけども、駒は最大3個であることを使えば6540で十分なことがわかるし、頑張ればもっと縮む。他のゲームでもそのゲームの特徴を利用して小さい空間に畳んでしまう必要があるわけだなー。

まあ、それは後退解析の大筋にはあんまり関係ない気がする。上のコードのencodeとdecodeの部分が複雑化して、あとget_childrenとget_parentが正規化されたものを返すようになる必要があるんだな。とりあえずPythonで書いてみてC++用のテストにつかおう。