Gauche:パズル探索
- Gauche を使って、とあるパズルの探索を行うプログラムを作ってみました。
https://gist.github.com/Hamayama/edfcfa99ec497044029bbb2e07f78380
実行すると、探索の様子が見られます。
- 単純な幅優先探索では、局面数が多すぎるようで、解けない面がありました。
上記ページでは、その解けなかった面のデータを設定しています。
枝刈りの条件等を追加できるとよさそうですが。。。
- 探索済みの局面については、保存して重複をチェックすることで、無限ループを回避しています。
ただ、100万局面とか たまってくるので、その重複のチェックが、ボトルネックになっています。
最初は、リストにして find で検索していたのですが、
hash-table に変更したところ 100 倍以上高速になりました。
しかし 自分の PC だと、300万局面あたりでメモリ不足になってしまうようです。
- 実装については、u8vector を hash-table の key として使えるようにするために、
(define-method object-hash ((obj <u8vector>)) (hash (u8vector->vector obj)))
と記述しています。
ただ、ユーザリファレンスによると、object-hash は 2 個の引数を取るようで、(define-method object-hash ((obj <u8vector>) rec-hash) (rec-hash (u8vector->vector obj)))
とも記述してみたのですが、これはエラーになるようでした。
- hamayama(2019/01/03 14:57:15 UTC): その後、make-hash-table の引数を、
bytevector-comparator から equal-comparator に変更したところ、
2引数の object-hash でいけるようになりました。
- hamayama(2019/06/23 03:10:36 UTC): Gauche 0.9.8 から、object-hash を定義しなくても、
u8vector をハッシュテーブル (make-hash-table 'equal?) のキーに使えるようになりました。
hamayama(2019/01/03 14:43:12 UTC)(2019/01/03 23:56:33 UTC)