これとは別に、だいぶむかしに、容量優先最適化したら将棋盤表現はどうなるかなぁ *1 と考えたことがある。まだ情報量的にコンパクトではないけど ~~40-byte~~ (しまった、こんだけでは成れない。もっと増える) かなぁと思ったんだけど、いかにも動かしにくそうだった。で、棋譜 DB 向けならまだしも、ゲーム木探索向けではないだろうなぁくらいに思ってそのままにしてあった。

が、がが！！

これは、もっともナイーブに、メモリ無駄遣い的に実装した bitboard を、ひょっと圧縮したような形になっているのではないかな。（常に 1-bit だけ on になるような 81-bit bitmap の情報量は 81-bit もない！）

ひょっと圧縮したので、ひょっと元に戻るぞ。

わりかしコンパクトなので、局面同士の比較コストも小さめである。あー、ハッシュは Zobrist hashing だとばかり思い込んでいたけど、ちょっと違うものになるなぁ。

盤表現は ~~40-byte~~ (←計算しなおさないと。このままでは 34-bit 不足してる筈。エンコードは考え直し。), ワークは bitboard と attack table の併用でとりあえず決めておこう。

しかし、Hyatt の文章は発見的に書かれていて、エッセー調で、とても面白い。まだ読みはじめたばっかりだけど、全部訳しながら読もう。

訳すのはコストが掛かるのだけど、何度も読み返すときのコストが激減するのと、条件が整ったら（著者にお伺い？）訳したものを web に置けるかなぁ。

関係ないけど、transposition table を訳すなら「移行判定表」がいいと思った（ちょっと前までは「別手順表」だと思っていた）。まあ、「転置表」/「置換表」が誤訳であることは間違いない。 *2

*1 メモリアクセスコストの高い今日ですから、試しに容量優先最適化を考えてみる価値は常にあると思います。

*2 さらに関係ないけど、Control transfer は「×制御転送」ではなく「○制御転移」だと信じている。

本日のツッコミ(全4件) [ツッコミを入れる]

# うんの (2007-02-23 (Fri) 18:44)

おろ。bitboard でない attack table なんて要らない気がするぞ。 垂直データの可算器（←ちょっと意味不明）を構成すればいいのね。 並列処理効率をあげるためには u32 bb[3]; と struct { u64 a; u32 b; } の union がいいかも。 あ、独り言です。

# うんの (2007-02-23 (Fri) 18:46)

ま、試作は Ruby で Array の attack table だけど。

# うんの (2007-02-23 (Fri) 18:58)

さらにメモ： 「ハッカーのたのしみ」 5-1 にはワード中の 1 ビットの数え上げというのがある。

# うんの (2007-02-23 (Fri) 19:14)

ビットの足しあげは、 ・たくさん 1 があるケース ・1 が少ないケース ・1 がある方がめずらしいケース で最適なコードが異なるので、試作版で統計と取っておくのが大切。 垂直データ Array だと、垂直方向のビット位置によって傾向が全然ちがうはず。