将棋の局面を256bitに圧縮するには？

投稿日時: 投稿者:

Ponanzaに倣い、大量に自己対戦棋譜を生成してそれをもとに強化学習をやりたいわけですが、この生成を誰かに手伝ってもらおうと思ったときに棋譜のファイルサイズが大きいので、そのやりとりが意外と大変です。

ところで、1局面は何bitで表現できるのでしょうか？

将棋の完全ハッシュは何bitで表現できますか？

上の記事に出てきた話では、なのはminiがハフマン符号化を用いて256bitに収めているということでした。

そこでやねうら王も256bitにpack/unpackするルーチンを提供しようと思い、書いてみることにしました。USE_SFEN_PACKERをdefineするとPosition::sfen_pack(),sfen_unpack()などが使えるようになります。やねうら王を用いて大量の棋譜を生成している人は、是非活用してみてください。

さて、局面を256bitに収めるコードを、書いて気づいたのですが、改めて考えてみるとこの256bitに収まるというのは奇蹟的なことなので、そのことについて今回は詳しく書いてみたいと思います。

まず、手番1bit、玉の位置7bit×先後 = 14bitは良いでしょう。

そのあと盤上の駒にハフマン符号を割り当てていきます。どの駒をどういう風にコード化するか(bit列を割り当てるか)は事前に決めておきます。この意味で、今回の手法は、(動的ハフマン符号ではなく)静的ハフマン符号に分類されます。

普通、ハフマンと言うと動的ハフマン符号を意味するのですが、今回のように盤上の、それぞれの駒の出現率がわかっているときは、静的ハフマンで済みます。

すべての駒が盤上にあるとしたら、81升のうち、一番出現頻度が高いのが空(カラ)の升で、次に歩、その次に、香・桂・銀・金、そのあと、角・飛車です。

そこで、空に1bit、歩に2bit、香・桂・銀・金に5bit、角・飛車に6bitを割り当てます。

これは、ハフマンツリーの作り方として情報工学の教科書とかに載っている内容なので、ググれカスです。(これより全体のbit数が短くなるような符号の割り当て方が存在しないことは、ハフマンツリーの性質として保証されています。)

具体的には、なのはminiでは以下のように符号化されているようです。やねうら王もこれに倣っておきます。

右端に「+2」と書いてあるのは、成り駒のフラグと手番(先手・後手)のフラグで2bitさらに必要という意味です。金は成り駒はありませんので、「+1」というわけです。

さて、ここで、手駒はないものとして、これだけで何bitになるか計算してみましょう。

  • 手番(1bit)
  • 玉の位置(2枚×7bit = 14bit)
  • 空(81-40升=41升、41升×1bit=41bit)
  • 歩(18枚×4bit=72bit)
  • 香、桂、銀、金(4枚×6bit × 4種 = 96bit)
  • 角、飛(2枚×8bit×2種 = 32bit)合計 256bit

恐ろしいことに静的ハフマンを使って、手駒を入れずにすでに256bitです。
そして、同時に、ぴったり256bitです。奇蹟としか言いようがありません。

「手駒はどうするのか？」という声が聞こえてきそうですが、ここで一つの魔法が使えます。

いま、盤上のある駒が1枚、手駒に移動したとします。盤上のその升は空になりますから、その升の盤上の表現のために1bitが必要となります。しかし、手駒には空は存在しないので、さきほどの静的ハフマン符号の右側の1bitを省略することが出来るわけです。

こうですね。実際には、成り駒をそのまま手駒にすることはありえないので金以外は、「+2」ではなく「+1」で良いのですが、説明がややこしくなるのでここはあえて「+2」のままにしておきましょう。(実装上も「+2」のままにしておいたほうが簡単でしょう。)

さて、そうすると、盤上でN bitで表現されていた駒が1つ手駒に移動したとき、盤上は1bit、手駒は(N – 1) bitで表現されることになりますから、全体のbit数は変わりません。すなわち、手駒が何枚になろうと、やはり全体としては256 bitぴったりで表現できるのです。

これを奇蹟と呼ばずして何と呼べば良いのでしょう。

いや、ほんと凄いですね。これを発見して実装した、なのはの作者のかずさんには盛大な拍手を送りたいと思います。

2016/7/2 10:20 追記

かずさんより。

なるほど。空き升と歩の存在確率が、それぞれ約1/2,約1/4というのが圧縮する上で利いているようですね。

「将棋の局面を256bitに圧縮するには？」への12件のフィードバック

  1. 双玉でない詰将棋のような盤上の玉が欠けた状態は、玉の位置を特別な6bitの値(例:000000)で示し、通常の位置はそれを避けた7bitの値で示す(例:0100000,1100000,0010000,…,1111111)ようにすると良いんでしょうかね。互換性は無くなっちゃいますが。

    返信 ↓

    • 王の位置を82番目の升にすれば良いだけでは？私はそうしてますよ。今回のフォーマットでも王の位置は7bit確保されていますから、128番目の升まで大丈夫です。(๑´ڡ`๑)

      ちなみに駒落ちは、最後にbitが余るので、成りの手駒を末尾(256bit目付近)までpaddingしておけば良いかと思ってます。(もっといい方法があるのかな？)

      返信 ↓

      • あれ、単純に82番めのマスにすると空マスが1bit余計に必要だったりしませんか？

        返信 ↓

        • あら…。そうか。それは参った。玉の位置二つなら、log 2 (82升×82升) ≒ 12.71 ≦ 13なので13bitで表せるから、ここから1bit捻出しますか…。しかし、両方の玉がいない状態を表現できないですなー。まあいいか…。

          返信 ↓

          • なので、格好悪いですが先後玉の位置を示すフィールドも可変長にするとかで。

            xxxxx00: 玉無し(2bit)
            ?????10: 玉の位置(0-31,7bit)
            ?????01: 玉の位置(32-63,7bit)
            ?????11: 玉の位置(64-95,7bit)

            のように2-7bitでの符号化も出来そうではありますが。

  2. はじめましてshibataと申します。いつも楽しく拝見させて頂いてます。
    ハフマン符号化について次のような符号化ではどうでしょうか。
    表がバラバラになっていたらごめんなさい。
    オリジナル
    駒 符号 使用 もち 成 必要
    bit数 手 bit数
    番手 1
    王の位置 2 7 14
    空白 41 xxxxx0 1 41
    歩 　　18 xxxx01 2 1 1 72
    香車 　　 4 xx0011 4 1 1 24
    桂馬 　　 4 xx1011 4 1 1 24
    銀 　　 4 xx0111 4 1 1 24
    金 　　 4 x01111 5 1 0 24
    飛車 　　 2 111111 6 1 1 16
    角 　　 2 011111 6 1 1 16
    合計 255
    提案版
    駒 符号 使用 もち 成 必要
    bit数 手 bit数
    番手 1
    王の位置　　 2 　6.5 0 0 13
    角の位置 　　 2 　6.5 1 1 17
    飛車の位置　 2 　6.5 1 1 17
    空白　　　　41 xxx0 1 0 0 41
    歩　　　　　18 xx01 2 1 1 72
    香車 　　　　 4 0011 4 1 1 24
    桂馬 　　　　 4 1011 4 1 1 24
    銀　　　　 4 0111 4 1 1 24
    金 　　　　 4 1111 4 1 0 20
    合計 253

    返信 ↓

    • 王・飛車・角をすべて升(6.5bit)で表現すると、それ以外の駒が最長でも4bitで表現できるので全体のbit数が縮まるということですね。面白いですね。

      返信 ↓

  3. 256ビットに押し込み!!すごい!!
    詰将棋のような盤上の玉が欠けた状態の表現方法　私見
    最初の王将の位置の値を次のように解釈してはどうですか
    1-81 先手玉の位置–通常の双玉
    82：１玉､先手玉のみ且つ先手番､手番ビット->空白に繰入れ
    83：１玉､先手玉のみ且つ後手番､手番ビット->空白に繰入れ
    84：１玉､後手玉のみ且つ先手番､手番ビット->空白に繰入れ
    85：１玉､後手玉のみ且つ後手番､手番ビット->空白に繰入れ
    86：0玉､先手番､
    87：0玉､後手番､
    0､88～127､予備

    返信 ↓

コメントを残す

メールアドレスが公開されることはありません。 ※ が付いている欄は必須項目です