網羅的探索…スライド・パズルとルート・パズル
牧野 浩二
当記事はInterface増刊 AI自習ドリル 第20回「網羅的探索…スライド・パズルとルート・パズル」【PDF版】の一部を抜粋したものです．
ご購入はコチラ https://cc.cqpub.co.jp/lib/system/doclib_item/1631/
今回はゲームAI を扱います．ひと言で「ゲーム」といっても種類がたくさんありますが，今回対象とするのは「パズル・ゲーム」です．2 種類のパズル・ゲームを取り上げて，これをプログラムで解いてみます．パズル・ゲームを解くために，幅優先探索や深さ優先探索といった探索アルゴリズムを用いるので，各アルゴリズムの概要やプログラムについても説明します．
また，パズル・ゲームを解くためのプログラム作成には，ナップザック問題を解くためのプログラムを応用しましたので，ナップザック問題についても触れています．
1．できること
● 網羅的に探索するのはAI の基礎テクニックの1 つ
AI は人の役に立つような仕事ができるようになってきました．例えば，レントゲン写真から病気を見分けたり，自動翻訳をしたり，天気を予測したりなど，人間以上の結果を出せることもあります．仕事に使うだけでなく，ゲームにAI を搭載しようという「ゲームAI」もあります．
ゲームAI というと，パックマンやスーパーマリオのようなテレビゲームを解いたり，囲碁や将棋で人間と対戦したりといったものを思い浮かべるかもしれません．他には，6面立体パズルを解くための「DeepCubeA」と呼ばれるものもあり，これらには強化学習や深層強化学習が使われています．
今回はゲームAI として，パターンを網羅的に試すことでパズルを解くための手法を紹介します．「これがAI ？」と疑問に思う方も居ると思います．
将棋やチェスなどが人間と対戦するためのAI プログラムの初期は，網羅的に探索する方法が採用されていました．しかし，その手数が膨大になりすぎるため，探索する範囲を狭めるための工夫（例えば，最初に香車を動かさないなど）が付け加えられていきました．そのため，網羅的に探索するのはAI の基礎となる方法です．
● 2 つのパズル
今回はパズル・ゲームとして以下の2 つを取り上げます．
• ロジカル・ルート・パズル
• スライド・パズル
▲ロジカル・ルート・パズル
ロジカル・ルート・パズルは，写真1−1 に示すようなパズルで，上から5 色の玉を転がして，決まった位置まで到達するルートを作るものです．
このパズルは2 種類のブロックがあり（実際には3 種類だが，本誌では2 種類だけ使う），図1−1 に示すように，問題ごとにそれぞれ使える数が決められています．このパズルでは最終的な結果だけが重要で配置する順序は必要ありません．
このパズルは全てのピースを置かなければ，答えが出ません．また，置き方の正解は1 種類ではなく，数種類ある場合があります．図1−1（a）（b）の答えは1種類ですが，図1−1（c）は6 種類の答えがあります．
このパズルでは，1 つでも答えが見つかればよいので，図1−2 の横の太い矢印で示すように，交差するピース全ての置き方を試してから2 つ目の交差するピースの置き方を試すよりも，縦の太い矢印で示すように，どんどん置いていった方が答えに早く到達できます．この探索方法は深さ優先探索と呼ばれています．
▲スライド・パズル
図1−3 に示すスライド・パズルも，動かし方を網羅的に探索することで答えに到達します．この場合はロジカル・ルート・パズルとは異なり，手順が重要となります．
このパズルでは短い手順で解くことが良い探索方法となっています．そのため，図1−4 の縦の矢印に示すような連続的にどんどん動かすことを試す方法よりも，横の矢印のように，動かせる全ての方法を試してから次の動かし方を試す方法が良いとされています．この探索方法は幅優先探索と呼ばれています．
● 紹介する技術の応用範囲
今回は探索法として，
• 深さ優先探索
• 幅優先探索
の2 つを解説することで探索の基礎を学びます．この探索方法は以下のことに応用できます．ただし，今回の方法は基礎的なものですので，これにいろいろな方法（注1）を付け足すことが必要です．
•最適選択問題
価値と重さのように2 種類以上の属性が設定されている幾つかの選択肢をある制約の中で選ぶ問題：ナップザック問題，トラックの輸送，商品選択など
• 配送計画問題
幾つかの場所を効率良く巡る経路を求める：巡回セールスマン問題，宅配便，ごみ収集経路の設計など
• 最適経路問題
ある地点からある地点へ移動するときの最短経路を求める：カーナビ，乗り換え案内など
• 最小木問題
幾つかの場所を最短の経路でつなぐ組み合わせを求める：送電網，石油やガスのパイプラインの設計など図1−4 スライド・パズルも縦方向の探索と横方向の探索がある
• スケジューリング問題
長さと順番が決まっている複数の選択肢から間を空けずに詰め込む問題：工場の操業計画，勤務表，対戦表など
• 配置問題
さまざまな大きさの物体を隙間なく埋める問題：荷物の積み込み，店舗の配置など
注1：これらの探索法に付け足して，より効率よく探索する手法として，ヒューリスティック探索があります．代表的なものではダイクストラ法やA＊（エースター）といったものがあります．
具体的には，迷路を探索する場合，ゴールに近づく方に探索すると「良い探索である」ことをあらかじめ与えておきます．スライド・パズルでは，本来の位置に近付く方向に動かした場合に「良い探索である」ことをあらかじめ与えておきます．
これらは対象とする問題に合わせて設定する必要があったり，その値が本当に良いものなのか分からないといった問題があるため，使う際には問題をよく理解しておく必要があります．
2．イメージでつかむ
今回は，ロジカル・ルート・パズルとスライド・パズルの2 つのパズルを対象とします．また，今回のキー・ポイントとなる探索アルゴリズムの原理を示すために，ナップザック問題についても説明します．
● ロジカル・ルート・パズル…溝をそろえてルートを作成する
ロジカル・ルート・パズルは，全ての組み合わせを試すことで必ず答えが求まります．そして，途中のピースの入れ方には全く影響せず，最後の答えだけが重要となる問題です．そのため，今回の探索問題を扱うのにはちょうど良い問題です．
▲遊び方の例
今回は一例として，以下のルールを定めます．
• 図2 − 1 のように空きマスが3 つで2 つのマスは決められている
• 決められている部分は直進ピースを使う
• 各問題には使えるピースが決まっている
例えば，図2−1 を図2−2 に示すピースを使って解く場合は，図2−3 の2 つの組み合わせを試せば全ての組み合わせになります．この場合は図2−3（b）が正解となり，ゴールまで正しくボールを転がせます．
▲直進/ 交差ピースの数を増やせば難易度が増す
もう少し難しくした例を図2−4 に示します．ここで使えるのは直進ピースが1 個，交差ピースが2 個です．
また，さらに少し難しくした例を図2−5 に示します．ここで使えるのは直進ピースが5 個，交差ピースが4個です．これを頭の中で全て行うことはかなり難しいと思います．ルートの作り方としては全部で75 のパターンがあり，その中の6 個のパターンが答えとなりました．
● スライド・パズル…盤面の数字を昇順にそろえる
スライド・パズルは写真2−1 のように1 ～ 15 の数字が書かれたマスと，1 つの空きマスがあるパズルです．このパズルでは，数字が書かれたマスを空きマスの方向に移動することを繰り返して，ばらばらになった盤面から数字を並べ替えます．
例えば，図2−6 のような盤面からでも動かせる組み合わせを全て行えば必ずそろえることができます．このパズルの場合は，最終的な順番に並べることができるかどうかだけでなく，その途中経過も知りたいところです．そのため，ロジカル・ルート・パズルよりも少しだけプログラムが複雑になります．また，スライド・パズルには数字だけでなく絵が描かれているものもあります．
● ナップザック問題…あらゆる組み合わせから問題に沿う最適な組み合わせを探す
ナップザック問題は，重さ，価値がバラバラの，複数の商品を，ナップザックに詰め込むことを想定しています．その際に重さの制限ギリギリまで，合計の価値が最大になるように商品を詰め込むには，どのような組み合わせが最適であるかを追求します．
ナップザック問題はゲームAI ではありませんが，今回紹介するパズルを解く方法と同じ方法で解くことができ，また問題が単純なのでプログラムが簡単に書けます．
そこで，この後ではナップザック問題を例にしてパズルを解くプログラムを説明します．また，ナップザック問題は探索問題の基礎的な問題ですので，知っておいて損のない問題となります．
▲問題例
ナップザック問題の中には，例えば重さと価値が異なる数種類の商品があり，決められた重さ以下の組み合わせの中で最大の価値となる組み合わせを探し出すものがあります．具体的に言えば，重さと価値が表2−1 に示す12 種類の商品があり，合計の重さが20kg 以下で価値を最大にする組み合わせを求める問題となります．この場合は商品A，B，D，E，F の5 つを選ぶと合計の重さが18kg，価値が最大の740万円となります．
3．やってみよう
■ ロジカル・ルート・パズルをプログラムで解く
● 使うプログラムとその実行結果
プログラムはLogicPuzzle.ipynbです．
次のURL からダウンロードできます．
https://www.cqpub.co.jp/interface/download/contents_ai.htm
これをGoogle Colaboratory（以下，Colab）で実行するとリスト3−1 が表示されます．
ここにgoalと書かれた後ろに「y r g p b」という文字が書かれています．上の「y r g p b」はボールの配置を，下の「r y g b p」はボールがゴールすべき位置の色をそれぞれ表しています．そして，0 と1 はそのまま下に移動することを表していて，2は右にずれ，3は左にずれることを表しています．
実際に試してみると，図3−1 のように確かに上のボールの色と同じゴールに到達することが分かります．
● プログラムの実行結果をパズルに当てはめる
リスト3−1 は上の方に1 がたくさん並んでいます．ロジカル・ルート・パズルではスタート位置を変えることが可能ですが，プログラムを簡単にするためにスタートの位置までを直線ピースで埋めるものとしています．そのため，出力された結果を実際のロジカル・ルート・パズルで表すと図3−2 と同じになります．
2 と3 は必ずセットで配置されるようにプログラムされています．そのため，この部分は交差ピースを表すこととなります．そして，0 が埋めるべき部分です．交差ピースを全て正しく配置した後，この部分は直進ピースが入ります．ここでは処理を簡単にするために直進ピースを表すこととしています．
● プログラムを改造して他の問題を作る
プログラムの変更点は以下の3 つです．
• init_pzl：問題設定
• start_ball：スタートのボールの置き方
• cross_block：交差ブロックの数
レベルによってはスタート位置が下の方になりますが，これをプログラムで設定するのではなく，上部を1 で埋めて図3−2 のように直進ピースで埋められた盤面として設定します．そして，ピースを置く部分は0としておきます．
次に，スタートのボールの置き方を設定します．ここで，y，r，g，p，b はそれぞれ，黄，赤，緑，紫，青を表しています．最後に，交差ピースの数を設定します．
今回作成するプログラムでは，交差ピースを全て配置して，余った部分に直進ピースを配置することとしました．交差ピースの数を設定しておけば，自動的に直進ピースの数が設定した通りになります．
▲問題例と設定方法
ここではロジカル・ルート・パズルの例題を作ってみます．例題はロジカル・ルート・パズルの公式ホームページ，
https://www.kumonshuppan.com/kumontoy/kumontoy−syousai/code=54685
からダウンロードできます．レベル分けした例題と解答例は以下のようになります．
• 例題 レベル1−1（リスト3−2）
• 例題 レベル3−1（リスト3−3）
• 例題 レベル4−3（リスト3−4）
■ スライド・パズルをプログラムで解く
● 使うプログラムとその実行結果
プログラムはSlidePuzzle.ipynbです．これを実行すると，リスト3−5 のように表示されます．ここで0 は空きマスを示していて，これを図で表すと図
3−3 となります．
これは一番下が初期配置で，下から順に動かしていき，一番上がゴールとなります．この場合は4 → 5 → 8の順に動かすと順番に並べることができます．
● 盤面を変化させる方法
▲方法1…乱数のSEED を変える
例えば，リスト3−6 に示すようにrandom.seedの引数を変えると，初期配置が変化します．
▲方法2…手順を増やす
手順の数を変えることもできますが，手順を増やせば増やすほど問題が複雑になります．例えば，リスト3−7 のように変更することで手順を3 としていたものを10 に変えられます．この場合は8 手で正解に到達していますが，ランダムで動かすため解くために必要な手順は動かした手順よりも少なくなる場合があります．
▲方法3…自分で盤面を設定する
これはプログラムにリスト3−8を追加します．なお，適当に配置した場合は解けない問題もあります．
● 盤面の大きさを変える
size変数を変えることで，盤面の大きさを変えることもできます．これはリスト3−9 のように4 にすると4× 4 の大きさの15 パズルになります．
<プログラムの入手先>
https://www.cqpub.co.jp/interface/download/contents_ai.htm
本稿は著作物であり，著作権法により保護されています．本書の一部，または全部を著作権者に断りなく，複製または改変し他人に譲渡すること，インターネットなどに公開することは法律により固く禁止されています．違反した場合は，民事上の制裁および刑事罰の対象となることがあります．