15パズルの解法について 北海道情報大学 情報メディア学部 情報メディア学科 新井山ゼミ 0321604 大石 貴弘
前回までの成果 15パズルの解法について 反復深化法 下限値 計算方法 MD （Manhattan Distance） 計算方法 MD （Manhattan Distance） I D （Invert Distance） WD （Walking Distance）
将棋のアルゴリズムについて 『コンピュータ将棋のアルゴリズム』 の読了 出版 『工学社』 著者 『池 泰弘』 出版年 2005.2 『コンピュータ将棋のアルゴリズム』 の読了 出版 『工学社』 著者 『池 泰弘』 出版年 2005.2 将棋は対戦形式→探索のアルゴリズムも特化 他のアルゴリズムを参考にするより、 15パズルの特性について知る方が建設的
将棋のアルゴリズムについて 今回の参考資料は『入門編』→結論には早計 『コンピュータ将棋の進歩』 / 松原仁編著 出版者 共立出版 出版年 1996.3 の借用
幅優先探索 反復深化（縦型探索） 幅優先探索（横型探索） メモリの消費が少 同じ面を何度も探索→堂々巡り 同一局面チェック メモリの消費が膨大
幅優先探索 問題点 必要なメモリの量が膨大 15パズルは『16の階乗』個のパターン 実際には偶奇性によりその半分 解決策 必要なメモリの量を抑える 枝狩りなどで保存する盤面自体を減らす など 現在のところ、未解決
下限値 WDの弱点 最短手数 = 64手 WD = 32 移動数(縦)/移動数(横) = 0 / 32 コマの交差によるロスを無視 最短手数 = 64手 WD = 32 移動数(縦)/移動数(横) = 0 / 32 弱点を考慮した具体的な計算方法は現在 皆無、思案中
下限値 OD（Oblique Distance） コマを斜めに分類 WDと同様 WDと同様の方法で移動 さらにピースの分け方を逆 １段目=｛1｝ 2段目=｛2,5｝ ３段目=｛3,6,9｝…… WDと同様の方法で移動 さらにピースの分け方を逆
今後の課題 より正確で効率的な下限値の算出方法 正確であるほど盤面の計算回数が減少 解法の計算においてもっとも重要
次回までの成果誓約 下限値についての考案 目標としてはWD以上 弱点を克服
補足 横型探索（幅優先探索） 手の浅い方（横方向） から順に探索
補足 縦型探索(深さ優先探索) 右図のように子節点を 優先 一つの経路を先(図で いえば下を優先的に) へと探索
15パズルの偶奇性 初期状態からコマを一組づつ交換 最終状態での交換の回数 偶数ならば解が存在 奇数ならば並べることが不可