15パズルの解法について 北海道情報大学　情報メディア学部 情報メディア学科　新井山ゼミ 0321604　大石　貴弘.

Presentation on theme: "15パズルの解法について 北海道情報大学　情報メディア学部 情報メディア学科　新井山ゼミ 0321604　大石　貴弘."— Presentation transcript:

1 15パズルの解法について 北海道情報大学　情報メディア学部 情報メディア学科　新井山ゼミ 　大石　貴弘

2 前回までの成果 15パズルの解法について 反復深化法 下限値 計算方法 MD （Manhattan Distance）
計算方法　 MD　（Manhattan　Distance） I　D　（Invert　Distance） WD　（Walking　Distance）

3 将棋のアルゴリズムについて 『コンピュータ将棋のアルゴリズム』 の読了 出版 『工学社』 著者 『池 泰弘』 出版年 2005.2
『コンピュータ将棋のアルゴリズム』　の読了 出版　『工学社』　著者　『池　泰弘』 出版年　2005.2 将棋は対戦形式→探索のアルゴリズムも特化 他のアルゴリズムを参考にするより、 　 15パズルの特性について知る方が建設的

4 将棋のアルゴリズムについて 今回の参考資料は『入門編』→結論には早計 『コンピュータ将棋の進歩』 / 松原仁編著 出版者 共立出版
出版年 の借用

5 幅優先探索 反復深化（縦型探索） 幅優先探索（横型探索） メモリの消費が少 同じ面を何度も探索→堂々巡り 同一局面チェック
メモリの消費が膨大

6 幅優先探索 問題点 必要なメモリの量が膨大 15パズルは『16の階乗』個のパターン 実際には偶奇性によりその半分 解決策
必要なメモリの量を抑える 枝狩りなどで保存する盤面自体を減らす 　　　　　　　　　　　　　　　　　　　　　　　　　　など 現在のところ、未解決

7 下限値 WDの弱点 最短手数 = 64手 WD = 32 移動数(縦)/移動数(横) = 0 / 32
コマの交差によるロスを無視 最短手数　=　64手 WD　=　32　 移動数(縦)/移動数(横) 　=　0　/　32　 弱点を考慮した具体的な計算方法は現在 皆無、思案中

8 下限値 OD（Oblique Distance） コマを斜めに分類 WDと同様 WDと同様の方法で移動 さらにピースの分け方を逆
１段目=｛1｝ 2段目=｛2,5｝ ３段目=｛3,6,9｝…… WDと同様の方法で移動 さらにピースの分け方を逆

9 今後の課題 より正確で効率的な下限値の算出方法 正確であるほど盤面の計算回数が減少 解法の計算においてもっとも重要

10 次回までの成果誓約 下限値についての考案 目標としてはWD以上 弱点を克服

11 補足 横型探索（幅優先探索） 手の浅い方（横方向） から順に探索

12 補足 縦型探索(深さ優先探索) 右図のように子節点を 優先 一つの経路を先(図で いえば下を優先的に) へと探索

13 15パズルの偶奇性 初期状態からコマを一組づつ交換 最終状態での交換の回数 偶数ならば解が存在 奇数ならば並べることが不可