原問題はこちら

有名な 15パズル問題 を解くプログラムを公開する.ただし,断っておきたいが,本解答プログラムはあくまでも 上記のUVa問題を解くためのものであり,時間的・メモリ的制約から,このままでは一般的な15パズル問題を解けるものではないかも.

15パズルは子供の時から遊んできた知的ゲームのひとつ.空いているスペースの周りをスライドしていき,1から15までの順にきれいに揃えるとゲーム終了.

勿論,数字の代わりに絵柄を貼り付けることも可能だが,本質は変わらない.

われわれ人間が遊ぶ時に最短移動回数(最小手数)のことについてあまり意識しないのに対して,プログラミング問題では最小手数を問われることが多い.ただ,本問題では,出題側が明確に最小手数を求めてはいないようだが,50手を越えた解答を提出してもいけない.実際のテストデータを見たわけではないが,最小手数が45手のテストデータを複数用意されると,最大5手までの誤差しか許容されなくなる.そういう意味で,本問題の解答プログラムでも,最小手数を十分に意識したつくりでないといけないだろう.

15パズルを解くアルゴリズムはいくつもあると思うが,ここではA*アルゴリズムを使ってみた.

<盤面の記述>
 盤面(レイアウト)の記述には4X4の2次元配列でもいいが,ここでは計算の効率性から1次元配列を使う.順番の数え方は左上から右下まで1行ずつとする.

例えば,記事トップ(上の写真)の盤面では
   char layout[16] = { 11, 2, 8, 5, 13, 14, 10, 12, 4, 3, 1, 7, 9, 15, 0, 6 };
になるし,ゴール状態は
   char goal[16] = { 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 0 };
になる.ただし,スペースは 0 で表す.

なお,2次元と1次元との位置対応は以下になろう.r は行番号(0~3),c は列番号(0~3),p は1次元での対応位置(0~15)とすると,

  p = 4*r + c
  r = p / 4, c = p % 4

効率向上のため,実際のプログラムではビットシフトやビット演算を使う.

#define RC2P(r,c)  (((r)<<2)+c)
#define P2R(p) ((p) >> 2) #define P2C(p) ((p) & 3)

<高速に解くことの困難性>
 15パズルは高々4X4なのだが,特定の盤面から完成のゴール状態までの最短移動回数(最小手数)は最長80手まであると証明されたそうだ.コンテスト制限時間 45秒内で解くことは大変困難であろう.そのためか,本問題のテストデータには 45手までのものしか使われていないようだ.

それでも、A*アルゴリズムや、IDA*アルゴリズム等高速探索法を使わないとタイムアウトになってしまうだろう.

<A*アルゴリズムと発見的関数>
 A*アルゴリズムは人工知能の研究によく使われる探索技法のひとつ.初期盤面からゴールまでの最短経路の探索に,ヒューリステック(発見的)関数を用いている.

つまり,各々の盤面について,以下のような発見的関数値を計算する.それらの値の中から,最も関数値の小さいもの(盤面)より,次の探索を始める.勿論,最小手数でなくても良ければ,s(t) を使うことはない,つまり,f(t) = e(t) とすることもできるが,本問題では最小手数に近い解答を出さないといけないことから,s(t) を全く使わなくて良い訳でもなさそう.

   f(t) = s(t) + e(t)
     f(t): 盤面 t での発見的関数の値
     s(t): 初期盤面から盤面 t までの手数(移動回数)
     e(t): 盤面 t からゴールまでの手数の推定値

ここでは、推定値 e(t) に,盤面 t での各数字の位置と,ゴール状態での各数字の位置とのズレ(マンハッタン距離)の合計を使う。

具体的に、例えば、記事トップの盤面では、数字の1がゴール状態では左上のところにあるはずなので、その位置ズレは横方向 2、縦方向 2、計 4 と計算する。その他の数字については以下の計算になる。

   (記事トップの盤面)
 数字1: 横ズレ2、縦ズレ2、計 4
    2: 横ズレ0、縦ズレ0、計 0
    3: 横ズレ1、縦ズレ2、計 3
    4: 横3、縦2、計 5
    5: 横3、縦1、計 4
    6: 横2、縦2、計 4
    7: 横1、縦1、計 2
    8: 横1、縦1、計 2
    9: 横0、縦1、計 1
    10: 横1、縦1、計 2
    11: 横2、縦2、計 4
    12: 横0、縦1、計 1
    13: 横0、縦2、計 2
    14: 横0、縦2、計 2
    15: 横1、縦0、計 1
従って,e(t) の値は最終的に,上記数字1から15までの位置ズレの合計値,すなわち 37 になる.

すぐに気づくことだが,e(t) はそこからの探索手数の下限を示すものでもある.例えば,記事トップの盤面では 36手以下で完成することはありえない.

以下はプログラムに使っている f(t) の計算 に関する部分.

int evaluate(char *t, int step)
{
int r, c, rr, cc;
int x, e;
e = 0; for (r = 0; r < 4; r++) for (c = 0; c < 4; c++) { if ((x = t[RC2P(r,c)] - 1) >= 0) { rr = P2R(x), cc = P2C(x); e += ABS(r-rr) + ABS(c-cc); } } return step + 2*e; }

(プログラムの説明) 変数 r, c は行番号、列番号を表す.RC2P(r,c) により,1次元配列での対応位置)を算出。x はゴール状態での数字の正しい位置(0~15)。それをまたゴール状態での行番号 rr および列番号 cc に戻し,マンハッタン距離を求める.なお,関数の引数,t は盤面配列,step は初期盤面からの手数(ステップ数)を表す.

何回ものテスト結果から,プログラムに実際に使われている f(t) は以下のようなものに変えた.

   f(t) = s(t) + 2*e(t)

e(t) の前の係数を 1 にすると計算時間および記憶領域が大幅に増えてしまい,2 を越える値にすると正しく推定できず,探索エラーになってしまう.

係数を実数(2.5 や 2.1 とか)にしたりして,多少のテストもしたが,整数との違いはいまいち判らない.

<優先度付きキューの出番>
 初期盤面からたどりつけられるすべての盤面から,発見的関数 f(t) で計算した最小値の盤面より次の探索を始める訳なので,すべての盤面を優先度付きキューに登録すると,最小値となる盤面を取り出すことは効率的にできる。

プログラムに,下の記事に説明した通りの優先度付きキュー(小さい順優先)を使用している.

<2重登録の条件付き禁止とハッシュテーブル>
 同一盤面を優先度付きキューに重複して登録すると大変効率が悪くなる.しかも,ゲームの性質上,重複盤面は沢山出てくるはず.時計周りあるいは反時計周りの移動を考えてもそのことにすぐ気づく.知的ゲームといわれたのも,われわれ人間が無限ループを如何に避け,ゴールまでの移動パターンを見つけ出すかを問うからであろう.

ということで,ここではハッシュテーブルを活用して2重登録を防ぐ.ただし,同一盤面にたどりつけたということは,初期盤面から違うルート(違う移動方法)で同一盤面にやってきたこともありうるので,初期盤面からの手数は小さければ、ハッシュテーブルに登録し直さないといけない.

以下はハッシュ関数に関する部分.引数 id は登録しようとする盤面の識別ID,lookup( ) 関数のリターン値は 登録拒否であれば 1,登録OKであれば 0 である.

#define HSIZE   39989
typedef struct { int id; short cno; } TBL; TBL tbl[HSIZE+1];
int lookup(int id) { int i; char *t; TBL *tp; unsigned long long d;
t = move[id].t; for (d = 0, i = 0; i < 16; i++) d = ((d << 4) + t[i]; i = d % HSIZE;
while ((tp = tbl+i)->cno == cno) { if (!memcmp(move[tp->id].t, t, 16)) { if (move[tp->id].step > move[id].step) { tp->id = id; return 0; } return 1; } if (++i == HSIZE) i = 0; } tp->cno = cno, tp->id = id; return 0; }

(プログラムの説明) 定数 HSIZE はハッシュテーブルのサイズ、素数にするといいだろう.ハッシュテーブルの構造体メンバー id は盤面の識別ID,cno はテストデータのシリアルナンバーを表す.

盤面の実体は move テーブル(詳細については次の記事を参照)にあるが,ハッシュテーブルにはその盤面に対応する識別ID が格納されている.

ハッシュ関数では,識別 id に対応する盤面 t を move テーブルから取り出し,盤面 t の1次元配列について,盤面の各数字を4ビット左シフトし,累計を取る.さらにそれをインデックスとしてハッシュテーブルに重複盤面ID の有無を照合する.盤面が重複していて,しかも,初期盤面からのステップ数(手数)が大きければ,2重登録だと認識し,登録を拒否する.

2重登録になるけれど,初期盤面からのステップ数が小さければ,そのまま登録を許可する.

——–

Comments are closed.

Post Navigation