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)