カテゴリー別アーカイブ: パズルプログラミング

クロススクエアドナンバーパズル(Cross Squared Number Puzzle)

下図のような盤面の □ 部分に0~9の数字を入れ、2桁以上の数値は平方数(n==r*r)となるようにするパズルを「クロススクエアドナンバーパズル(Cross Squared Number Puzzle)」と言う。
※ Cマガジン2000/01 電脳クラブより
本稿では、このパズルを解くためのC/C++プログラムについて解説する。

□□□□■□
□□■□□□
□□□□□■
■□□□□□
□□□■□□
□■□□□□

ちなみに、下図は上記パズルの回答例だ。

1225#6
49#324
49729#
#25921
196#49
6#9216

盤面が大きくなければ単純な探索でも(今時のCPUであれば)すぐに全部の解を求めることができる。
番人付きの1次元配列を用意しておき、最初のマスから最後のマスまで、0~9 の数字を順に入れていき、パズルの条件が成立していれば、それを解として表示すればよい。
全部の場合を生成し、それを逐一チェックするのはパズルプログラミングの基本だ。今時のCPUは驚くほど高速なので、この基本アルゴリズムを使うことで実用的な時間内で解ける問題は数多くある。

void solve(char *board, int ix) {  // ix: 数字を入れる位置
  if( 盤面全部に数字を入れた ) {
    解発見;
    return;
  }
  for(int n = 0; n <= 9; ++9) {
    if( n == 0 && ix が複数桁の先頭 ) continue;
    board[ix] = n;
    if( 複数桁 && 右または下が番人 ) {
      if( 平方数になっていない )
        continue;
    }
    solve(board, ix+1);
  }
}

で、このパズルの場合、考えなくてはいけないのは、入れた数字が平方数かどうかをどうやってチェックするかだ。
単純な方法としては以下のものがすぐに思いつく。

・ int r = (int)sqrt(n) を計算し、n == r*r で判定
・ (6x6までという制限をつければ、)6桁分のテーブルを用意し、数値が平方数かどうかを予め計算しておく

前者は桁数制限がゆるいが、sqrt() の計算時間が大きくなりそうだ。整数演算で平方根を求めるコードを書けば、より高速化できるかもしれない。
後者は処理速度は速いが、桁数が大きくなるとテーブルサイズが肥大化する。平方数である確率は極めて低いので、なんらかの方法でテーブルを圧縮することを考える必要がありそうだ。

んで、実際にコードを書いて処理時間を計測してみたところ、sqrt() を使う版は約1秒、6桁分の平方数かどうかを判定するテーブルを用いたものは約0.66秒であった。
概ね予想どおりだが、sqrt() の処理速度は想像していたよりは遥かに高速だった。
整数演算により平方根を求める関数も書いてみたが、処理時間は約3秒で返って遅くなってしまった。
最近の x86 は sqrt() を処理する命令を持っているので、ソフトで処理するより遥かに高速、ということみたいだ。

どうぶつしょうぎ>ひよこだけの場合

temp

通常の「どうぶつしょうぎ」では田中らによって後手必勝であることが求められているが、上図のように、ライオンとひよこだけの局面から双方が最善を尽くした場合は、先手必勝 or 後手必勝 or 引き分け のどれなのであろうか?

プログラムのチェックもかねて探索してみたところ、上図は先手必勝だった。

必勝手順の初手はライオンを斜め上に上がる手だった。ひよこをとっても良さそうだが、同ライオンとなった局面は後で出てくるが、先手必敗になる。どうやらライオンは相手陣地に近い方が有利なようだ。

H:0 Z:0 K:0
 . *L  .
 . *H  .
 .  H  L
 .  .  .
H:0 Z:0 K:0

ライオンが斜めにあがると、次はひよこをただで取られてしまうので、後手はひよこを取るよりない。
後手もライオンが斜めに上がると、先手ライオンに進まれてしまい、トライを阻止できなくなる。
なので、後手はひよこをとり、先手はライオンで取り返す。
この状態が最初に言及した局面と同じで、ライオンがひとつ進んだ方が勝ちの局面だ。

H:1 Z:0 K:0
 . *L  .
 .  .  .
 .  L  .
 .  .  .
H:1 Z:0 K:0

ここで先手からライオンの頭にひよこを打たれると、後手ライオンが逃げ、先手ライオンがトライできるので、後手はライオンの頭にひよこを打つ一手。先手は横に逃げる。

H:0 Z:0 K:0
 . *L  .
 . *H  .
 .  .  L
 .  .  .
H:1 Z:0 K:0

後手のひよこが移動すると取られるし、後手ライオンが左に移動すると先手にトライされるので、後手ライオンが右による一手。

H:0 Z:0 K:0
.  . *L
. *H  .
.  .  L
.  .  .
H:1 Z:0 K:0

ここで先手が相手ライオン頭にひよこを打つと、ライオンに逃げられてしまい、あとが続かない。
正解は、下図のようにひよこを垂らす手。

H:0 Z:0 K:0
 .  . *L
 H *H  .
 .  .  L
 .  .  .
H:0 Z:0 K:0

放置しておくとニワトリを作られるので、後手は左に寄る一手。

H:0 Z:0 K:0
 . *L  .
 H *H  .
 .  .  L
 .  .  .
H:0 Z:0 K:0

先手ひよこはただ取られるだけに見えるが、成って相手ライオンを左に寄せるのが好手だ。

H:0 Z:0 K:0
 N *L  .
 . *H  .
 .  .  L
 .  .  .
H:0 Z:0 K:0

後手は取るしかない。

H:1 Z:0 K:0
*L  .  .
 . *H  .
 .  .  L
 .  .  .
H:0 Z:0 K:0

で、先手ライオンがひとつ前に進むと、後手は先手のトライを防ぐ手が無い。

H:1 Z:0 K:0
*L  .  .
 . *H  L
 .  .  .
 .  .  .
H:0 Z:0 K:0

というわけで、ひよこをたらして成り捨てるのが絶妙手で、13手で先手の必勝というわけだ。

どうぶつしょうぎ>後退解析

全局面の生成ができたので、次は「後退解析」で、全局面の解析を行なう。

「後退解析」とは、評価が確定した局面から順に順に局面の評価を確定していく処理だ。
評価とは 勝ち・負け・引き分けのいずれかだ。
最初は全ての局面の評価を不明(UNKNOWN)にしておき、ある局面について、その子局面を生成し、
・子局面のどれかひとつが勝ちであれば、勝ち
・子局面の全てが負けであれば、負け
という処理を行い、局面の評価が変化しなくなるまで繰り返せばよい。
このとき、問題になるのはどの局面を調べるか?ということだ。
全局面数がそう多くなければ、全局面について処理を行なっても速度的に問題はないが、局面数が膨大な場合はちょっと遠慮したくなる。
どうぶつしょうぎの場合は末端局面を覗いても約100M局面もあるので、かなり膨大だ。
どうしよう?

どうぶつしょうぎ>全局面生成

「どうぶつしょうぎ」の完全解析 を参考にして、まずは(末端局面を除く)全局面の生成を行ってみた。
アルゴリズムは単純で、以下のようなものだ。

初期局面をハッシュに入れる
初期局面をオープンリストに入れる
while( オープンリストが空でない間 ) {
  オープンリストから局面をひとつ取り出す
  全ての可能着手をリストアップ
  for(全ての着手について) {
    着手を実行
    if( 末端局面でなければ ) {
      初期局面をハッシュに入れる
      初期局面をオープンリストに入れる
    }
  }
}

前掲論文によれば、末端局面を除く全局面数は 99,485,568 で、末端局面を含めると 246,803,167 ということなので、全局面を保持するハッシュテーブルはかなり巨大になってしまう。
最初は std::unordered_map を使用していたのだが、130メガ局面を生成したあたりでおいらのマシンの物理メモリ容量の 12GB を消費してしまい、そのせいか win7 x64 OS がハングアップしてしまった。orz
std::unordered_map はおそらくオープンハッシュでリンクのためにメモリを消費するので、メモリ効率があまりよくない。
1局面は64bit = 8バイトで表現できるので、ハッシュのキー部分だけを考えれば、256M * 8 = 約2GBあれば足りるはずだ。
全局面数があらかじめわかっていれば、クローズドハッシュを自分で作った方がよいので、自作することにした。
衝突確率を下げるために倍の容量を確保したとしても 4GB で事足りる。末端局面を含めないとすれば、その半分の 2GB で充分なはずだ。
のだが、なんと VC++ は x64 モードでも固定配列では 31bit を超えることができない。
なので、new を使ってメモリを動的に確保するようにしたのだが、それも何故かうまくいかず露頭に迷ってしまった。
が、これはおいらの設定ミスで、ソリューションに新しいプロジェクトを追加し、そこでテストプログラムを書いていたのだが、追加したプロジェクトが x64 モードではなく x86 モードでビルドされていたというオチであった。

で、なんとか末端局面を含まない全局面をリストアップできたのだが、局面数が 96,814,709 で、前掲論文の結果とだいたいあっているのだが、ピッタリ一致していない。
まだ、何かバグがあるのかもしれない。

どうぶつしょうぎ>ハフマン的符号化

出現頻度の高い情報を短いビットで表す符号化をハフマン符号化と言う。

どうぶつしょうぎの場合、空欄である確率が高いので、以下のように符号化することが出来る。

0 空欄
100x ゾウ
101x キリン
110x ライオン
1110x ひよこ
1111x にわとり

※ x は先手コマなら0、後手コマなら1

持ち駒も0である確率が高いので、以下のように符号化する。

0 0
10 1
11 2

初期局面は、4*6 + 5*2 + 4 + 6 = 44bit で表現できる。
盤面のコマが持ち駒になると、盤面では 3 または 4bit 減り、持ち駒は 0 または 1 ビット増えるので、
差し引き 3~4bit 減ることになる。
したがって 44bit あれば、持ち駒も合わせた局面の状態を表現できることになる。

どうぶつしょうぎメモ

どうぶつしょうぎの盤面は 3 * 4 = 12 マス。
コマの種類は5種類なので、1マスの状態数は 5 * 2 + 1 = 11種類だ。
(2倍するのは先手・後手があるから。+1 してるのは空欄)
なので、これを符号化するには 4bit あれば足りる。
盤面全体では 4 * 12 = 48bit になる。
持ち駒の種類は3種類で、最高2個なので、3 * 2 * 2 = 12bit
したがって、48 + 12 = 60bit で符号化できることになる。

Quwel メモ

Quwel  プログラムに関するメモ

  • 1マスを char で表し、8×8 配列を用意するとよい
  • 1次元配列にし、周囲に番人を置くとよい。9×10 = 90バイトの1次元配列となる
  • 単純な反復深化でも、ツリーの幅が狭い問題であれば解くことができる。
    • リラックス Level 100 は、幅が狭く、最短手数は10手だが、探索ノード数約6000で解を発見できる
    • リラックス Level 99 は、幅が広く、最短手数は10手だが、7百万以上でも解を発見できない