日別アーカイブ: 2015年6月14日

どうぶつしょうぎ>ハフマン的符号化

出現頻度の高い情報を短いビットで表す符号化をハフマン符号化と言う。

どうぶつしょうぎの場合、空欄である確率が高いので、以下のように符号化することが出来る。

0 空欄
100x ゾウ
101x キリン
110x ライオン
1110x ひよこ
1111x にわとり

※ x は先手コマなら0、後手コマなら1

持ち駒も0である確率が高いので、以下のように符号化する。

0 0
10 1
11 2

初期局面は、4*6 + 5*2 + 4 + 6 = 44bit で表現できる。
盤面のコマが持ち駒になると、盤面では 3 または 4bit 減り、持ち駒は 0 または 1 ビット増えるので、
差し引き 3~4bit 減ることになる。
したがって 44bit あれば、持ち駒も合わせた局面の状態を表現できることになる。

どうぶつしょうぎメモ

どうぶつしょうぎの盤面は 3 * 4 = 12 マス。
コマの種類は5種類なので、1マスの状態数は 5 * 2 + 1 = 11種類だ。
(2倍するのは先手・後手があるから。+1 してるのは空欄)
なので、これを符号化するには 4bit あれば足りる。
盤面全体では 4 * 12 = 48bit になる。
持ち駒の種類は3種類で、最高2個なので、3 * 2 * 2 = 12bit
したがって、48 + 12 = 60bit で符号化できることになる。