読者です 読者をやめる 読者になる 読者になる

ai65536's blog

将棋とかプログラムとか

盤面情報をハフマン符号化 実験メモ

局面のハッシュキーにはZobristハッシュが一般的に使われているが、

ハッシュキーの衝突問題がある。

局面をハフマン符号化してハッシュキーとして使用できれば、

衝突問題の回避や盤面情報の復号も簡単に行える。

定跡DBを作成するにあたり、

局面のハッシュキーに盤面情報をハフマン符号化のテストする。

 

結論

エンコードに時間がかかりすぎる

正確に計測してないが、遅すぎて途中で寝てた

 

・想定よりサイズが大きい

ハッシュキーのサイズは256ビットだったが、実験によるワーストケースだと270ビットとなっている。(これに持ち駒情報42bitと手番情報1ビットを加えた値が実際のサイズ)

また、実際の最長サイズがわからない。(=ハッシュキーとしては扱いづらい)

最低でも最大サイズが234ビット以下にならないと使い難い。

 

既に作成されたデータベースにアクセスするだけなら問題ないが、

 データ作成時にはある程度まとまった時間が必要である。

 また符号化後のサイズが最大サイズが不明なのも問題である。

 

これらの課題を解決するより、Zobristハッシュ+盤面情報を別途持ったほうがよいと思われる。

  

実験条件

・手持ちの棋譜の各局面をハフマン符号化する

・盤面情報は1マス5ビット x 81マスの内部で使ってる情報をそのまま使用

・持ち駒は今回のテストでは含まない

・使用した棋譜は手持ちの9,434棋譜、1,083,837局面

実験結果

駒の出現回数と符号

出現回数 符号
49579213 1
先手王 1083837 0111111
先手飛 903421 0111110
後手桂 1923870 011110
先手銀 1918885 011101
先手桂 1918681 011100
後手銀 1906048 011011
後手飛 899026 0110101
先手馬 136192 0110100111
後手馬 132729 0110100110
後手と 116075 0110100101
後手竜 115326 0110100100
先手と 114138 0110100011
先手竜 108732 0110100010
後手成銀 27668 011010000111
先手成銀 24338 011010000110
先手成香 20283 011010000101
後手成香 19875 011010000100
先手成桂 33496 01101000001
後手成桂 31144 01101000000
後手角 729714 0110011
先手角 728641 0110010
後手王 1083837 011000
後手香 2052704 01011
先手香 2051788 01010
後手金 2004913 01001
先手金 1994334 01000
先手歩 8077368 001
後手歩 8054521 000

 

符号化後のサイズ

最小 140 ビット

最大 275 ビット

平均 212ビット

処理時間

未計測だか数分で終わるような処理ではない