図1 15パズル
スライディングブロックパズルというパズルゲームの中に15パズルというものがある。図1のように4×4のマスに1から15までの数字が入っていて1つの空白があり、空白を利用して数字を入れ替える。本研究では15パズルの最短手数と最短経路を求める高速なプログラムを作成することを目的に研究を行った。
15パズルとは4×4個のマスに1から15までの数字が入っていて1つの空白があり、空白を利用して上下左右のマスから数字を入れ替えて、図2のように整列した状態にすることを目的としたゲームである。
8パズルとは15パズルの場合4×4マスだったのが、図3のように3×3マスになっているもので、1から8までの数字が入っている。
図4のように15パズルと8パズルではマスの数が異なり、15パズルの方が7個多い。そのため、15パズルの方が8パズルより盤面の状態数が多く解くことが難しい。
8パズルの場合の状態数は最大で9!=362880 通り存在する。また、15パズルの場合の状態数は16!=20922789888000 通り存在する。
15パズルや8パズルには解くことのできない問題が存在する。図5のような15と14だけを入れ替えた問題は解くことができない。したがって、15パズルの解くことのできる状態数は16!/2となる。
本研究ではゲーム木を作成し、それを探索することで最短手数を求める。しかし、15パズルの状態数は16!個あるため、これを全てメモリに置いて探索することはできない。そのため、工夫をする必要がある。
ゲームのある盤面から一手で行ける別の盤面を考えると、図6のような木のように枝分かれする。こういった関係のデータ構造をゲーム木という。
15パズルの状態数は多いため、探索方法を工夫しないと最短手数が増えるにつれゲーム木が大きくなり答えが返ってくるまでに時間がかかってしまう。そこで、本研究ではA*アルゴリズムを利用して効率的に探索することにした。
A*アルゴリズムとはゲーム木に対してダイクストラ法を実施することである。
ダイクストラ法とはネットワークでの最短経路を効率的に求めることができる。既に最短経路を求めた部分に、処理していない頂点の中で一番近いものを一つずつ加えていくことを繰り返して最短経路を求める。
A*アルゴリズムを利用するためには最短経路を求めた部分に、処理していない盤面の中で目的に一番近いものを加える必要がある。そのため、処理していない盤面の中で目的の盤面に一番近いものがどの盤面かわからなければならない。
目的の盤面に近いかどうかを評価するためにコストを考える。コストをf*(n)とするとf*(n)=g*(n)+h*(n)と置くことができる。15パズルの場合、g*(n)は初期盤面からの移動回数になる。h*(n)は目的の盤面までの最小コストになる。本研究ではh*(n)はマンハッタン距離を利用することにした。
コストの計算ができればどれだけ目的の盤面に近いかどうかわかったことになるので、コストの比較をすることで目的の盤面に一番近い盤面を探すことが可能になる。そして、A*アルゴリズムでは目的の盤面に一番近い盤面のみを取り出せればよいのでヒープを使うことにした。
ヒープとは最小値または最大値を求めるのに適しているデータ構造である。本研究ではコストが最小値のものを求めるために利用する。子は親より大きいか等しいという制約がある。各頂点においてその頂点より小さいという関係が成り立っている。この木は完全二分木にすることができる。
根の頂点は木全体で最小となる。この③を取り出した後、完全二分木であることを保つため⑫の頂点を一旦根に移動し、親子の大小関係を親が小さくなるように頂点を交換していくと、木の深さ程度の手間で再び正しいヒープ木となり、図8のように、根が最小の頂点になる。
本章では作成したプログラムについて説明する。プログラムの作成に使用した言語はC言語である。
盤面やコストなどを持つ構造体を以下のようにした。banは盤面をそのまま持つ
typedef struct heap {
int ban[SIZE];
int cost;
int moves;
struct heap *parent;
} HEAP;
movesは移動した回数を表す。costはmovesとマンハッタン距離を足したものである。movesの値を持つ理由はヒープでcostの値が同じの盤面が現れた時、movesが小さい方が親になるようにするためである。parentのポインタは自分の親がどの盤面かわかるようにすることで最短経路を求めることができる。
A*アルゴリズムを利用して最短手数を求めるために、まずヒープを用意する。二分ヒープは配列使って表現できる。
HEAP *heap = NULL;
if (heap == NULL){
if ((heap = malloc(ARRAY*sizeof(HEAP))) == NULL) {
fprintf(stderr, "メモリーエラー\n");
exit(1);
}
}
#defineで定義したARRAYの数値を変えることでヒープの大きさを変えることができる。また、探索済みの盤面を入れておくclose配列も用意する。
次にA*アルゴリズムを利用して最短手数と最短経路を求めていく。
while (checkGoal(temp->ban) != 1){//ゴールかチェック
temp->parent = add_node(temp,close,closelast);//closeへ移動し親のアドレス受け取る
closelast++;
//隣接ノード生成、コスト計算、ヒープへ追加
last = move(temp->ban, last, temp->moves, heap, temp->parent,close,closelast);
//最小値を取り出す
last--;
temp = minimum(heap, last);
//ヒープ組直し
down_sort(heap,last);
}
ヒープから取り出した盤面が目的の盤面であるかを確認するためにcheckGoal関数を使う。もし、目的の盤面であった場合はループを終わる。
目的の盤面でない場合はadd_node関数を利用してヒープから取り出した盤面を探索済みとしてclose配列へ移す。そしてmove関数を使い直前にclose配列へ入れた盤面を親とする隣接ノードを生成し、distance関数を使いコストの計算をしてadd_heap関数でヒープへ追加する。ヒープへ追加したので、up_sort関数を使いヒープを組直す。
次にminimum関数を使いヒープからコストが最小の盤面を取り出す。
そして、down_sort関数を使いヒープを組直す。
これらの動作を目的の盤面が現れるまで繰り返す。最初に目的の盤面が現れたものが最短手数である。
最短手数の目的の盤面を見つけることが出来たら、最短経路を求める。ヒープにある盤面もclose配列にある探索済みの盤面もHEAP構造体なので自分の親のポインタを持っている。
したがって、最短手数の目的の盤面から順番に親を辿って行けば最短経路が分かる。それをprint関数として作成した。
作成したプログラムに対して計算時間を測定した。ランダムに生成した盤面に対して最短手数ごとの計算時間は図9のようになった。
一方、求めた解が最短でなかった割合を図10に示す。
最短手数が26手以下の問題に対して7秒以内で解くことができた。また、最短手数が増えるにつれ計算時間が指数関数的に多くなっていることが分かる。したがって、最短手数が40手を超える問題についてはメモリ上に存在する盤面が多くなりすぎて答えを求めることができなくなっていく。最長最短手数である80手の問題の答えを見つけることは困難である。
以上より15パズルを高速に解くプログラムが作成できたと言えるが、正しく最短手数を求めることができない問題が存在するためプログラムを改良する必要がある。
また、本研究ではコストの計算でh*(n)をマンハッタン距離としていたが、別の評価関数を使うなどすることで効率的に最短手数を求めることができると考える。
近年のパソコンではプロセッサの中のコアが複数あるため並列処理をすることができれば、コア数によってより早く最短手数を求めることが可能であると考える。
本研究では盤面の情報を入れるのにint型の配列を使用しているが、これをchar型の配列へ変更するなどメモリの使用量を減らすことも求められる。
C言語を用いて15パズルの最短手数と最短経路を求めることを目標に研究を行った。15パズルなどの身近なパズルでも効率のよい解法が見つかっていないものもある。
ヒープやA*アルゴリズムなどは15パズルの最短経路を求めるためにできたものではない。しかし、プログラムを工夫したり組み合わせて利用することで色々な問題を解決できる可能性がある。
本研究で作成したプログラムのソースコード main.c