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