| 箱入り娘
|
|
|
|
|
|
|
| ■ 箱入り娘
|
|
|
| 箱入り娘とは、下図のように横4マス、縦5マスの盤に縦横幅が 2x2, 2x1, 1x2, 1x1 の4種類のピースが合計10個あって（下図の×の部分にはピースが無い）、ピースを盤上でスライドさせて下方の出口から①のピースを出す最短手順を求めるパズルである。
|
| 下図はもっとも一般的な「箱入り娘」の初期状態であるが、初期位置が異なったり、各ピースの個数が異なったり、出口に位置が異なったり、盤のサイズが異なる亜種が多数存在する（http://www.pro.or.jp/~fuji/java/puzzle/slide/index.html 参照）。本稿では下図の一般的な「箱入り娘」について、その解放手順を求めるプログラムについて述べる。
|
図1. 標準的な「箱入り娘」の初期状態
┏━┯━━━┯━┓
┃ │ │ ┃
┃③│ ① │③┃
┃ │ │ ┃
┠─┼───┼─┨
┃ │ ② │ ┃
┃③├─┬─┤③┃
┃ │④│④│ ┃
┠─┼─┴─┼─┨
┃④│× ×│④┃
┗━┷━━━┷━┛
========
出口
|
|
|
| ■ 探索
|
|
|
| 最短手順解を求めるには、初期状態から到達可能な盤面をを次々に生成していき、解の状態に到達したかどうかをチェックするとよい。局面生成順序としては横優先と深さ優先の2通りがある。前者は横型探索、後者は縦型探索とも呼ばれる。横型探索はｎ手目で生成可能な局面すべてをメモリに保持する必要があるので、多量のメモリを必要とする傾向にある。縦型探索は末端状態に至るまでの情報を保持しておけばいいので、横型探索よりもメモリを必要としない傾向にある。
|
| 横型探索プログラムは以下のように記述できる。
|
初期状態を生成;
for(n=0; ;++n) {
n 手目の状態から n+1 手目の状態を全て生成;
if( 解状態に到達したか )
解を発見
}
|
| n 手目の状態から n+1 手目の状態全てを生成するためには n 手目の状態全てを保持しておく必要がある。また、箱入り娘では異なる手順で同じ局面になる場合があるので、そのチェックも行う必要がある。そのためには生成した局面を覚えておき、n+1 手目の局面を生成した時点で、その局面が生成済みかどうかをチェックし、生成済みであれば保存しないようにするとよい。
|
| 縦型探索プログラムは以下のように記述できる。
|
main()
{
初期状態を生成;
doSearch(10); // 10手先までの局面を生成
}
void doSearch(int lvl)
{
int n = genMove(); // 可能な着手を生成
for(i = 0; i < n; ++i) {
i 番目の着手を実行;
if( 解状態に到達したか )
解を発見;
if( lvl > 1 )
doSearch(lvl-1);
i 番目の着手を元に戻す;
}
}
|
| 上記プログラムは最大深さ10で局面を生成しているが、実際のプログラムでは最大深さをいくつに指定したらよいか解らない。また、同一局面の探索を防ぐために局面の重複チェックを行うが、そのためには少ない手数から局面を生成する方が理にかなっている。したがって、単純な縦型探索ではなく、探索深さを 1, 2, 3 ... を１ずつ増やしながら縦型探索を行う、反復深化の方が箱入り娘には適している。プログラムは以下のようになる。
|
main()
{
初期状態を生成;
for(n=1; ; ++n)
doSearch(n); // n手先までの局面を生成
}
void doSearch(int lvl)
{
int n = genMove(); // 可能な着手を生成
for(i = 0; i < n; ++i) {
i 番目の着手を実行;
if( 解状態に到達したか )
解を発見;
if( 現在の局面へ最短手順で到達 && lvl > 1 )
doSearch(lvl-1);
i 番目の着手を元に戻す;
}
}
|
| 反復深化は単純な縦型探索よりは箱入り娘の探索に適しているが、箱入り娘は同じ局面に到達する手数が同じ異なる手順が多数存在するので、無駄な探索を行うことになる。生成した局面の重複チェックを行うには生成した局面を覚えておく必要があるので、それをもとに次の手数の局面が生成できるのであれば、横型探索を行う方が無駄がなく合理的である（厳密には重複チェックを行うための局面情報と、次の手数の局面を生成するための局面情報は同一である必要はない。前者はいかに少ないメモリで表現できるかと、いかに高速に重複チェックできるかが重要であり、後者はいかに速く次の手数の局面を生成できるかが重要である）。
|
|
|
| ■ 初期状態からn手で生成される状態数
|
|
|
| 「箱入り娘」の場合は、ある局面から生成できる局面数がもともと少なく、異なる着手により同一状態になる頻度が高いので、手数により局面数が爆発することが無い。表1. は1手～40手までの各手数で生成される局面数を示したものである。1手前の局面に比べ数10パーセントしか増加していない。これが将棋であれば数十倍以上になるから、「箱入り娘」の局面ツリーは極めて横幅が狭く、深いツリーであると言える。
|
表1. 初期状態からn手で生成される局面数（対称形は考慮しない）
手数 局面数 手数 局面数
---- ---------- ---- ----------
1 8 11 44
2 10 12 50
3 15 13 46
4 18 14 52
5 18 15 43
6 23 16 59
7 28 17 62
8 42 18 70
9 42 19 64
10 50 20 74
手数 局面数 手数 局面数
---- ---------- ---- ----------
21 48 31 373
22 64 32 456
23 81 33 487
24 91 34 551
25 113 35 650
26 156 36 717
27 197 37 774
28 187 38 906
29 240 39 946
30 295 40 1038
|
|
|
| ■ 次手数局面生成のための状態表現
|
|
|
| 特定の局面から1手で到達できる局面を生成するための状態表現としては、盤面の各位置に存在する（空白も含めた）ピース番号を指定する方法がよい。（空白も含めた）ピース番号は 0～11 で表現可能なので、uchar bd[5][4]; で盤面状態を表現できる。
|
| 可能な着手を生成するためには空欄位置から盤面をスキャンするが、盤の外かどうかのチェックが必要になる。そのためには座標のチェックを行うのが自然な方法だが、番人というテクニックを使えばそのチェックが不要になる。すなわち、uchar bd[(5+2)*(4+1)]; で盤面を宣言し、下図の様に 4*5 の周りに壁を配置するとよい。
|
ＷＷＷＷＷ
・・・・Ｗ
・・・・Ｗ
・・・・Ｗ
・・・・Ｗ
・・・・Ｗ
ＷＷＷＷＷ
|
|
|
|
|
| ■ 重複チェックのための状態表現
|
|
|
| 生成局面の重複チェックを行うには、手数が確定した局面を覚えておく必要がある。したがって、なるべく少ないメモリ数で局面の状態を表現でき、かつ高速にアクセスできる方法を考えねばならない。単純に状態を表現するには、(1) 盤の各マスに存在するピースの種類を指定する、(2) 各ピースが盤上のどこに存在するかを指定する、の2種類の方法がある。前者の方法では、各マスの状態数は ピースの種類＋空白＝５ なので、5^20 ≒ 9.5x10^13 となる。後者の方法では、盤上のマスは20個所あり、ピースは10個あるので、20~10 ≒ 10^13 となる。どちらも数が大きすぎて全状態をメモリに置くことが困難である。そこで状態数が少なく効率のよい状態表現を考えねばならない。
|
| 前者の方法で、図1.を表現すると下図のようになる。
|
図2. マスの状態指定による盤面状態指定
┏━┯━━━┯━┓
┃３│１ １│３┃
┃ │ │ ┃
┃３│１ １│３┃
┠─┼───┼─┨
┃３│２ ２│３┃
┃ ├─┬─┤ ┃
┃３│４│４│３┃
┠─┼─┴─┼─┨
┃４│０ ０│４┃
┗━┷━━━┷━┛
|
| この図をみるとわかるように、最も左上のマスに 1x2 のピースがあれば、その下にも 1x2 のピースがあるのは必然であり、その部分に存在するピースの情報を保持するのは無駄である。2x2, 2x1 でも同様なので、マスに存在する（空白も含めて）ピースの種類を指定するのは 12 個所で充分である。
|
図3. ピース形状を考慮した盤面状態指定
┏━┯━━━┯━┓
┃３│１ │３┃
┃ │ │ ┃
┃ │ │ ┃
┠─┼───┼─┨
┃３│２ │３┃
┃ ├─┬─┤ ┃
┃ │４│４│ ┃
┠─┼─┴─┼─┨
┃４│０ ０│４┃
┗━┷━━━┷━┛
|
| 各ピースの左上位置はピースの配置により変わってくるので、ピース種別を指定する場所を一定にすることは出来ない。そこで、盤面をを左上から右に、次にその下に移り左から右にという順にスキャンしていき、ピースの左上個所のピース種別を指定することにする。こうすれば 12 個所のピース種別を指定すれば充分である。さらに、最後の一個は自動的に決まるので、5^11 ≒ 4.9x10^7 で状態が指定できることになる。10^13 からはかなり減ったが、4.9x10^7 は49メガということであり、全状態をメモリに置くにはまだまだ難がある。
|
| 状態指定を０～４の数字の並び（ただし、それぞれの個数は 2, 1, 1, 4, 4）とすれば、その場合の数は 12!/(2! * 1 * 1 * 4! * 4!) = 415,800 と大幅に減る。これらの数字の並びは許されない状態も含むが、これくらいの数ならば、100メガバイト以上のメモリを積む今日マシンであれば全状態をメモリ上に持っても何の問題もない。０～４の数字の並びによる状態指定から状態の通し番号を計算するには以下のようにするとよい。
|
| 数字の並び（図3では 313323444004）をスキャンし2x2ピースの位置を求め、これを P22（0<=P22<12） とする。2x2 を除いた数字の並び（図3では 33323444004）から2x2ピースの位置を求め、これを p21（0<=P21<11）とする。2x1 も除いた数字の並び（図3では 3333444004）で、1x2 の部分を1、その他を0とする数値（図3では 1111000000）の通し番号を求め、これを P12（0<=P12<210） とする。同様に 1x1 についても通し番号を求め、P11（0<=P11<15）とする。p22 + 12 * (p21 + 11 * (p12 + 210 * p11)) が数字の並びの通し番号となる。
|
|
|
| ■ プログラム
|
|
|
| 上記の方法により作成したプログラムを hako.cpp に置く。
|
| PenIII@800, Mem:384, Win2K, VC++6.0 の環境で、（対称形を考慮せず）全ての局面を生成するのに 0.10 秒を要した。
|
| プロファイル結果を見ると、局面の重複チェックのための通し番号の生成に、もっとも多量の 38% の時間を費やしていた。
|
|
|
|
|