15パズルのプログラムによる 解法 北海道情報大学 情報メディア学部 情報メディア学科 新井山ゼミ 0321604 大石 貴弘 前回までの成果 • １５パズルを解くプログラムの制作 – 反復深化 • 深さ制限(何手目まで探索するか)を設定し、縦形 探索 • 縦形探索 – 子節点を優先して探索する手順 – 下限値 • パズルを解くのに最小限必要な移動数を求める『 概算』 • 下限値を使った枝刈り（盤面の計算を省略する判 定）が可能 – それ以外での高速化 下限値の具体的な計算 • MD（Manhattan Distance） 元の盤面 計算する盤面 • 元の盤面と計算する盤面において、各パネルについて 何マス離れているか(距離)計測。その合計がMDの値 • 1は2マス、3は2マス、５は１マス、7は2マス、８は1マス 離れているので、2+2+1+2+1=8 MD=８ 下限値の具体的な計算 • ID（Invert Distance） 元の盤面 計算する盤面 • 転倒数から計算 • パネルの上下移動により転倒数は+3、-3、+1、-1変化 • 『転倒数 ／ ３ ＋ 転倒数 ％ ３』の計算。右上図で行うと 『上下移動の最低限必要な移動数』が算出可能 • 盤面を90度回転して同様に計算 = 『左右移動の最低限 必要な移動数』を算出 • 左右の移動数 + 上下の移動数 = ID 下限値の具体的な計算 • 転倒数 完成形 • コマの順番が逆である場所の数 • 今回の完成形(転倒数0)の並び方 1.2.3.4.5.6.7.8.9.10.11.12.13.14.15 例の盤面 • 算出方法 – すべてのコマに順に着目 – そのコマより前のコマの中で、その コマより数値が大きい(=順序が逆) コマの数を値として保存 – すべての値を合算 = 転倒数 – 例の盤面の転倒数は 3 下限値の具体的な計算 • WD（Walking Distance） • WDの概念 – MDの上位版 – 上下移動(あるいは左右移動)だけに着目し、最 低限必要な移動数を計算 盤面の例 MD = 3 ID = 7 解くには19手必要 下限値の具体的な計算 • WD（Walking Distance） 下限値の具体的な計算 • WD（Walking Distance） • １段目に属するコマ = 1.2.3.4 • ２段目に属するコマ = 5.6.7.8 • 3段目に属するコマ = 9.10.11.12 • 4段目に属するコマ = 13.14.15 • 空白の上下の段のコマのひとつを空白と入換え=一手 下限値の具体的な計算 • WD（Walking Distance） • 上図から下図の状態 にするためには11回 の移動が必要 ＝最低限必要な 上下移動の動の回数 • 盤面を90度回転させ て同様に計算した左 右移動の数と、上下 移動の合算がWD • 例の盤面でのWDは 0 + 11 ＝ 11 下限値の具体的な計算 • WD（Walking Distance） – 実際のパズルの探索 • あらかじめすべてのWDの値を計算し、保存 • テーブルを作成 • 局面ごとにそのテーブルを参照 ID、WDについての参考：『コンピュータ&パズル』 実験 • 最短手数 – 解くまでにかかる手数 • ID+MD – IDとMDのうちよりよい 値を採用して探索 評価 • 実験 – 下限値の計算方法には盤面による相性あり – ランダムに並べたパズルであれば十分な速度で 解を算出 • 前回の成果誓約 – 将棋のアルゴリズムの応用についての考察 • 未達成 考察 • 将棋のプログラムについての知識不足 – 1からの知識習得 – 参考資料 • 『コンピュータ将棋のアルゴリズム』 • 出版 『工学社』 • 著者 『池 泰弘』 • 出版年 2005.2 の借用、読書中 今後の課題 • WDよりも優秀な下限値の計算方法の模索 • 『コンピュータ将棋のアルゴリズム』の読了 次回までの成果誓約 • 『コンピュータ将棋のアルゴリズム』の読了の うえ、考察 • 下限値の計算方法の模索 • 反復深化以外でのパズルの解法 補足 • 縦型探索(深さ優先探索) • 右図のように子節点を 優先 • 一つの経路を先(図で いえば下を優先的に) へと探索 補足 • 反復深化 • 深さ制限(上限値)を 用いる • 深さ制限内でのすべ ての経路を探索 • 徐々に深さを増やし て探索
© Copyright 2024 ExpyDoc
