情報処理学会 第87回全国大会

5K-07
ヒントの少ない一筆書きパズルのモンテカルロ木探索による生成について
○内川 伶,山本修身(名城大)
本研究はスリザーリンクに類似したn×nの格子状のマス目をなぞる,ある一筆書きパズルを対象とする.このようなパズルのうち,少ないヒントで構成されるパズルを生成することが本研究の目的である.このパズルでは,パズルの解が唯一になるまでランダムにヒントを逐次添加することをプレイアウトとして,モンテカルロ木探索により少ないヒントのパズルを見つけることができる.しかし,パズルのサイズnが大きくなるとプレイアウトの計算量が爆発してしまい,n>6についてはうまくパズルを生成することができない.本研究では,プレイアウトにマルコフ連鎖モンテカルロ法を利用することで,プレイアウトの計算量を削減することを試みる.