第8回　倉庫番を解くアルゴリズム

図1●倉庫番の問題。人を動かして荷物をゴール（G）まで押していく

　友人たちと車でスキーに行くとき，いつも困るのは「トランクへ荷物を詰め込む順番」です。大きなスキー靴やかさばるスキーウエアを詰め込んでいるうえ，人によってはゲーム機や本を持ってきたりするので，各自の荷物の量がまったく違うのです。狭い車のトランクには，これら荷物をうまい順番で入れていかないとなかなか全部収まりません。寒い冬の夜中にごそごそと詰め替えていると，手伝っている友人の一人がぽつりと言いました。「まるで倉庫番のようだ…」。

　倉庫番のような問題は世の中にあふれていると思います。いろいろな組み合わせの中から正解を求めたり，そのための手順を得る方法を見つける，というのは皆さんもよく直面する問題でしょう。今回は，こうした問題をどのようにしてプログラムで解くのかを考えてみることにします。

問題をプログラムで扱いやすいようにデータ化する

　プログラムで問題を解くにはまず，問題をコンピュータで扱える「データ」として表さなくてはなりません。図1の盤面を眺めてみると，荷物，人，壁，ゴール，といった様々なものがありますね。これらは，「荷物は1とする」「人は2とする」…というように，それぞれに数字を割り当てることで，プログラムの中で数値として扱えます。「3歩先に進めば荷物を動かせる」といった「物と物の関連」を表すには，問題の盤面をそのまま2次元配列として表現すればよいでしょう。つまり，盤面のあるマス目に「荷物」「人」…がある場合は，対応する配列の要素にそれぞれ「1」「2」…を入れておくわけです。

　これらをC言語で書くとリスト1のようになります。今回は，問題をソース・ファイルに書き写すのが楽なように，盤面の初期状態をmapstrという文字列として定義しています。リストのmapinit関数では，この文字列を基に2次元配列mapを初期化しています。盤面上にある各要素を表す値には， mapstrで使っている文字の文字コードをそのまま使うようにしました。

/* マップの内容 */
#define ITEM_WALL ('*')
#define ITEM_PATH ('.')
#define ITEM_GOAL ('%')
#define ITEM_BOX ('o')
#define ITEM_PLAYER ('@')
#define ITEM_GOAL_BOX ('G')

/* 盤面データ */
unsigned char map[MAP_WIDTH][MAP_HEIGHT];

/* 盤面の初期状態 */
unsigned char *mapstr = {
  "*********"
  "*.......*"
  "*.**o**.*"
  "*[email protected].*"
  "**o%%%*.*"
  "**....*.*"
  "****..***"
  "*********"
};

/* マップを初期化する */
void mapinit(void)
{
 int x, y, i;

 i = 0;
 for (y = 0; y < MAP_HEIGHT; y++) {
  for (x = 0; x < MAP_WIDTH; x++) {
   map[x][y] = mapstr[i];
   i++;
  }
 }
}

順序を思い浮かべながら解く方法を考える

　このデータを使ってプログラムで解く方法を考えてみましょう。このゲームは図1の状態から始まります。そしてすべての荷物がゴールに入れば終わりとなります。この始まりと終わりの間には何があるでしょうか？ 　私たちがこのゲームをプレイするときのことを考えてみると，このゲームを解く過程は「人を一歩動かす」という操作の繰り返しになっていることがわかります。荷物がゴールに向かって移動していくのも，人を動かした結果です。言い換えれば，現在の盤面の状態と，人を一歩動かす方向さえ決まれば，次の状態は自動的に決まってしまうのです。

　それなら，この「一歩動かす」という操作を一つのサイクルとして，このサイクルをループで繰り返すようにすれば，プログラムで記述できそうです。ループが終わる条件は，「すべての箱がゴールに着く」こととします。一歩動かす方向は毎回異なりますが，向きを表す変数（dirとします）を用意すれば共通に扱えます。dirに移動方向を入れながら「1歩dirへ動く」「1歩dirへ動く」…と，これをすべての箱がゴールに着くまで繰り返します。

　こう考えると，次の問題は「各サイクルでどの方向へ移動させればいいか」でしょう。人は縦横4方向に動けるので，1回目の動かし方は4通り，2回目は4 ×4通り，3回目は4×4×4通り…と，組み合わせがどんどん増えていきます。この組み合わせの中から，最終的にすべての荷物がゴールにたどり着くものを選ばなくてはなりません。

　移動方向の組み合わせを選ぶときは，最初にどこかの移動方向を選んで進めてだめなら元に戻して別の方向を調べる「深さ優先探索」，1歩で到達できる範囲，2歩で到達できる範囲…と少しずつ探索範囲を広げていく「幅優先探索」など，いくつかのアルゴリズムを利用できます。ここでは移動方向の組み合わせを選ぶために，連載第4回で紹介した最良優先探索（A＊アルゴリズム）を使うことにします。

最良優先探索を使って正しい手順を探す

　最良優先探索では，盤面の状態がどれくらい最終形（すべての荷物がゴールにある状態）に近いかを表す評価値（コスト）を計算し，それに基づいて進む方向を選択していきます。もう少し正確に言えば，それまでに調べた盤面の状態の中でコストが最小となるものを選び，そこからさらに一歩進むことで新たな状態を生成する，ということを繰り返すのです。生成した状態は，何らかのキューに格納しておき，次のサイクルではキューの中でコストが最小となるものを選ぶようにします。具体的には以下のような手順になります。

　キューに格納する要素は，コストが低い順にソートしておきます。そうしておけば，先頭から調べる状態を取り出していくことにより，常に最終形に最も近いところから調べられます。キューから取り出した状態では上下左右のいずれにも移動できない場合は，キューの先頭からもう一つ状態を取り出せば，それが2番目に最終形に近いことになります。これで効率よく探索できます。

　盤面の状態を保存するには，リスト2のような構造体t_nodeを使います。先の2次元配列mapの形で保存するのでは，メモリーが無駄になるからです。壁やゴールの位置は人を移動しても変わらないので，t_nodeには人と荷物の位置だけを保持するようにしています。costはその状態におけるコストを保存するメンバー，backnodeは一つ前の状態へのポインタを保存するメンバーです。状態の遷移は初期状態をルートとするツリーを構成する＊2ので，その親ノードを指すのがbacknodeだと考えてもいいでしょう。すべての荷物がゴールに到達したときには，このbacknodeメンバーを順にたどっていくことで，そこに至る手順を再現できます。

/* 座標を表す構造体 */
typedef struct {
 int x, y;
} t_point;

/* 盤面の状態を表す構造体 */
typedef struct node {
 t_point boxpos[MAP_BOXLIMIT]; /* 荷物の位置 */
 t_point playerpos; /* 人の位置 */
 struct node *backnode; /* 一つ前の状態 */
 int cost; /* コスト */
} t_node;

　今回の問題で注意が必要なのは，人が動き回った結果，同じ盤面状態に戻って来るようなケースがあることです。こうした「堂々巡り」が生じると，探索が無限ループに陥ってしまいます。これを防ぐには，過去に調べた状態をすべて保持しておき，キューに登録する前にすでに調べたものかどうかを確認しなければなりません。言い換えれば，キューから取り出した後も，その状態を保持しておかなくてはいけないのです。

　ここではt_node型の配列に状態を格納し，キューにはその要素へのポインタを格納することにします。すでに調べた状態かどうかは，この配列を走査することで判別できます。今回のような簡単な問題なら，これでも時間がかかり過ぎることはありません。問題が複雑なために調べる状態の数が多くなる場合は，配列の代わりにハッシュ・テーブルを利用するといいでしょう。

壁や荷物を調べて移動できるかどうかを判定する

　この手法でポイントとなるのは，先の(1)～(4)のうち，(2)の「移動できるかどうかを調べる」，(3)の「どれだけ最終形に近づいたかコストを計算する」の二つです。まずは，(2)から考えてみましょう。

　人を移動させるためには，移動先に壁がないことが前提です。さらに，移動先に荷物がある，つまり「荷物を押す」場合には，荷物の移動先に壁や別の荷物がないことも条件になります。壁については，配列mapから読み取ればわかります。一方荷物については，先ほどのt_node型の配列から判断しなくてはいけません。

　これらの判定をする関数をリスト3に示します。playstep_movecheckはt_point型の引数で指定した位置（座標）が壁かどうかを調べる関数です。playstep_boxcheck関数は指定した位置に荷物があるかどうかを調べ，もしあればt_nodeのメンバーであるboxpos 配列のインデックスを返します。

/* 指定した位置が壁かどうか */
int playstep_movecheck(t_point *pos)
{
 return (map[pos->x][pos->y] != ITEM_WALL);
}

/* 指定した位置に箱があるならインデックスを返す */
int playstep_boxcheck(t_node *node, t_point *pos)
{
 int i;
  for (i = 0; i < MAP_BOXLIMIT; i++) {
   if ((node->boxpos[i].x == pos->x) && 
       (node->boxpos[i].y == pos->y)) {
    return i;
   }
  }
  return -1;
}

/* 箱の移動先に壁や別の箱があるかどうか */
int playstep_boxmovecheck(t_node *node, 
      t_point *newplayerpos, t_point *difpos)
{
 t_point newboxpos;
 newboxpos.x = newplayerpos->x + difpos->x;
 newboxpos.y = newplayerpos->y + difpos->y;
 if (!playstep_movecheck(&newboxpos)) return false;
 
 /* その先に箱があるかどうかを調べる */
 return (playstep_boxcheck(node, &newboxpos) < 0);
}

/* 人を移動できるかどうか */
int playstep_playermovecheck(t_node *node, t_point *difpos)

{
 t_point newpos;
 newpos.x = node->playerpos.x + difpos->x;
 newpos.y = node->playerpos.y + difpos->y;

 /* 移動先が壁でないか */
 if (!playstep_movecheck(&newpos)) return false;

 /* 移動先に箱があるとき，箱も一緒に動かせるか */
 if (playstep_boxcheck(node, &newpos) >= 0 &&
    !playstep_boxmovecheck(node, &newpos, difpos)) 
    return false;
 return true;
}

　これらを利用して人が移動できるかどうかを総合的に判定する関数がplaystep_playermovecheckです。この関数では，移動先に壁や荷物があるかどうかを確認し，荷物がある場合にはさらに下請け関数のplaystep_boxmovecheckを呼び出しています。 playstep_boxmovecheckでは再び先のplaystep_movecheckなどを使って荷物の移動先に壁や別の荷物がないことを確認しています。

　このほか，「壁際に荷物を押したらそれ以上操作できなくなる」「荷物が組み合わさって押せなくなる」といった手詰まりになる状態をあらかじめ判別して除くようにすれば，効率よく探索を進められます。これについては読者の方への宿題としておきましょう＊3。