ちょっと気になる話題が聞こえてきたので記事にまとめておきます。
完全ハッシュの定義についてはggrks。
局面(盤面+手駒+手番)を何bitにpack出来るかという話。
これは、定跡データを作るときなどになるべく小さくpackしたいのでわりと切実な問題。
なのはminiは、ハフマン符号を使っているらしい。
ハフマン符号化は、出現頻度が高いものに短いbit列を割り当てる。
将棋の盤面だと、空白の升が一番出現頻度が高く、次に歩である。そこで、空白の升を0b(1bit)、先手の歩を100b(3bit)とか何かそんな感じで割り当てていくと、そこそこ短くなるという理屈である。詳しくはggrks。
たぶんハフマン符号化等をしていいなら200bitぐらいに収まる気がする。
しかしAVX時代に突入して、256bitなら一命令で計算できるので、差分計算がしやすく、かつ256bitに収まって欲しいという要求もある。
そこでZobrist Hashの更新と同じ程度の計算コストで出来る方法を編み出す必要がある。
ざっくり計算してみる。
手番は1bit。
角・飛のように成れる駒は、升(81升=7bit) + 先後(1bit) + 成り(1bit) = 9bit。
金のように成れない駒は、ここから1bit少なくて8bit。
王はhash keyのbit位置で先後決めておけば先後を表現する1bitは省略できて7bit。
歩は、愚直にやると角・飛と同じく9bitなのだが、各筋に先手の歩は1つしか存在できないので、hash keyのbit位置で先後どちらのどの筋を表現する歩であるかを決めておけば18枚に対して、それぞれ升(9升=4bit)+成り(1bit)で5bitずつで済む。
手駒は、升を意味する数字が82,83であればそれは先手,後手の手駒であるということにする。(歩も同様に手駒の時は、10,11升目にあるという扱いにする)
歩 5 * 18 = 90
香 9 * 4 = 36
桂 9 * 4 = 36
銀 9 * 4 = 36
金 8 * 4 = 32
角 9 * 2 = 18
飛 9 * 2 = 18
王 7 * 2 = 14
手番 1 * 1 = 1
281 bit
だめだ。256bitから少し(かなり?)オーバーした。
これ以上縮めるとZobrist Hashの更新と同等の速度でなくなってくる。(気がする)
歩が4bitで表現できたとしても263bit。ぐぬぬ。
256bitちょっと厳しいんじゃないの？何とかなるの？どうなの？
追記(2015/12/29 4:00)
局面数>4.65*10^62 であることがわかっている https://t.co/jXtkrRG5Gr ので、62*log2(10) で200は超えるはず。 https://t.co/bOtfIYR9Sg
— 山田 剛 (@yamadacsa) December 28, 2015
なるほど…。
あとコメント欄で指摘があったのですが、歩の成りは、1つの筋に1つとは限らないので上で書いたの間違ってました…。うおおお。だとしたら、256bitに収めるの、大変すぎ！
歩は成った場合、一つの筋に複数枚存在できるので、そう単純に5bitに出来ないのでは？
えーっと、効きの話ではないようですよ。
sfenを小さなビット列に押し込みたいという話でしょうか。
ちなみに、成りのビットがあるので2歩判定も可能でしょう。
自分も興味ありますね。自分はsfenそのものをハッシュにする気でしたので、小さくできるんだったらそれもいいかもなーと思います。
まぁ、この甘えがアマたるゆえんですね。
妙案がありますように。
あ、勘違いしてるかも。
ちょっと今、頭腐ってるので取り下げます。
スミマセン。
> 歩は成った場合、一つの筋に複数枚存在できるので、そう単純に5bitに出来ないのでは？
酔っぱらいながら書いたので適当でした..申し訳ない。
ハッシュの替わりに完全ハッシュをキーに使って検索する場合、検索結果を合法手かどうか検査せずにそのまま使えるので、Zobrist Hashより少しくらい遅くなっても良い思いますが、ハフマン符号化とか極端なパック(先手後手の王2つ分の座標を合わせれば合計13bitで済むとか)をすると「少しくらい遅く」で済まないですよね。
そうなんです…。
駒に背番号振っちゃうと、置換表に向かなくなりますしね。難しいです。
背番号自体は、評価値の差分計算のときに必要でして、これはStockfishでもAperyでも持ってるのでこれ自体は問題ないかと。
＞局面数>4.65*10^62 で
上記引用論文で上からの評価が9.14*10^69となり、2^233以下で局面数自体は収まります。
ただし、「既に駒がある升は排除」して配置可能箇所を数えるなど、とんでもなく面倒な事になりますから、
間違いなく「233bit以上」なのだろうなぁ
うおおおおお。
Avx512があれば、眠れない夜も安心。
と行きたいところですが、まだ２，３年先の話ですしどうにかならないでしょうかねぇ。
将棋空間ってそんなにデカかったんだなぁ。
メモリに乗らないじゃないか。Orz
AVX512が使えても、512bitも置換表に格納しようとなるとメモリ帯域がボトルネックになって遅くなるでしょうね。いまですら、64bit hash keyを128bitにするのが良いかどうかすら微妙なところでして…。
そもそもchar64字あればsfen格納する方が短いっていう。
普段からボケてますけど、これはマジボケだった。
うまいスイートスポットがないですねぇ。
しかし、そんな微妙なところで差異が出るくらいで戦ってるんですね。全然世界が違う！Orz
恥の上塗りでお尋ねしたいのですけど、sfenって最長どれくらいですか。
50文字パックする方法考えたんですけど、初期盤面すら入りませんでした。
あれ？sfenて意外とデカい？
成り駒(p+のように二文字)が盤上にべたべたあると(成ってない駒と合わせて)それだけで64文字は軽く超えるような…。
charで64文字 = 512bitなので、32文字 = 256bitに出来るかどうかの話をここではしてますね。256bitはハフマン符号化すれば余裕。差分計算が簡単に出来るようにするのは困難。512bitも使っていいなら余裕。というのが現状。
なるほど。
色々取り違えていたようです。
失礼しました。
結局、256bit以内に収めるには、実践的には「なのはmini」の方法位で手を打つくらいしかないかと思います。ハフマン符号化しているのでZobristHashとは比較にならない位重たいとは思いますが。
なるほろ…。ハフマン符号化、差分計算しますか…。(ZobristHashに比べれば重いものの、全体からすると1%以下の速度ダウンで済むかなと)
ちなみに選手権に参加しているソフトで、置換表に完全ハッシュを使っているソフトがあって、確か都万さんの「隠岐」だったと思いますが、局面により違うが233～239bitって言ってたような記憶があります。
なお、ハフマン符号化はしていたと思います。
ほほー。なるほろ！
（＾ｑ＾）全局面に 予め連番振っておいて、 なんかすごいちからで
四角いバーコードリーダーみたいに
この盤面の数字は Ｎｏ．１０２０３０４０５！ ピコッ☆！
と出てくればいいんだが
よくわかってないぜ☆ （＾＿＾）
そんなに小さな値じゃないぜ？
10進数なら、80桁以上になると思う。
ｱﾁｬｰ／（＾▽＾）＼
（＾～＾）たまに衝突するぐらいのところで我慢するかなんだぜ☆ｗｗｗｗｗｗ
自分の頭では、282bit が限界でした。
盤：81bit
盤上の駒の区別（駒種・成不成・先後）：5bit
持ち駒（駒種）＆持ち駒の区切り：3bit
（区切りの前が先手駒、後が後手駒）
後手が１枚だけ持ち駒を持っている時が最長で、81+5*39+3+3= 282bit
持ち駒を 駒種＆先後 で 4bit にすると、区切り記号が不要になり、最長は、すべての駒が盤上にある場合で、
81+5*40=281 bit になりました。
S,G を先手後手の持ち駒の個数として、
81+5*(40-S-G)+4*(S+G)=281-(S+G) で、S=G=0の時 281bit になります。
最初の81bit の１の個数を求め、その数だけ5bit 単位で、残りは 4bit 単位で切り出せば、盤面を復元できます。
> 最初の81bit の１の個数を求め、その数だけ5bit 単位で、残りは 4bit 単位で切り出せば、盤面を復元できます。
なかなか面白いアイデアですね。256bitレジスタに対するbit shiftがなくて(SSEでは64bitまでしか)、あとpop countも64bitが2回になりますけど。
いずれにせよ、256bitの壁は厚そうですね…。
＞ちなみに今日はいまから、過去に無許可路上ライブして逮捕されてるアイドル事務所の社長らと。（忘年会）
お勤め、御苦労さまです。
https://twitter.com/yaneuraou/status/681776127170359300?ref_src=twsrc%5Etfw
普通にやると 353 bit って言う事でいいんですかね？
(1+1+7) * 34 + 金(1+7) * 4 + 王(7) * 2 + 手1 =
306 + 32 + 14 + 1 = 353 bit
はい、353bitあれば、ZobristHashで使ってるmagic numberをそれに合わせて変更するだけでいまのコードがそのまま使えますね。つまりはZobristHashと速度的には等価です。
あとは、全体から見て1%程度の速度ダウンと引き換えに256bitに収まるかというのは一つの焦点かなと。まあ、hash keyが256bitになったら置換表へのアクセスで10%ぐらい速度ダウンするでしょうが、それはそれとして…。
> 升(81升=7bit)
2^(6.4)=84なので、やねうらおさんの
> 281 bit
ここから (0.6 * 40) =24bitほど節約できる（数学的には）
情報学的なエントロピー的にはそうですね…。log(2)81 = 6.339.. なので0.66bit*40 = 26.4bitほど節約できます…が、これを拾うのは大変そう..。
あ、その281bitというのは、と金は1つの筋に複数存在できるのを忘れてた(勘違いしていた)ときに計算したものなので正しくは↑のコメントの353bitになる気が…。
現実的にはハフマン符号化で差分計算頑張るほうが楽ですね、たぶん。
普通に何も考えずに256bitのZobristHash使ったとして、1億台のPCで探索し続けても我々が生きているうちに1度でもhash衝突する確率はほぼほぼ0のような気もしますが…。
90*90=8100。ところで2^13=8192。だから2^13を90で割算すると、90までの数字が2個作れる。これで81升+持駒=83か所は表現可能。
0.1bitまで拾うとなると確かに非現実的ですが、0.5bitをかき集めるのはこんな感じで
> 353bitになる気が
はぅ・・・・256bitの壁は厚いです
> 90*90=8100。ところで2^13=8192。
なるほろ..
> はぅ・・・・256bitの壁は厚いです
〜 最強伝説ハフマン 〜
完
具体的な手法を与えず情報量の見積もりだけでいいのであれば…
255 < log2(83[升] ^ 40[駒]) < 256
升情報だけでこれですわ。
駒の先後・成り・手番が入るはずもないという。
結論：ハフマンつよい
> 255 < log2(83[升] ^ 40[駒]) < 256 1枚目は83ですけど、2枚目は(手駒でなければ)82、...以下略。でも、先後・成りを含めて256bitに詰めるのは厳しそうですね..
休主さんへ
> 255 < log2(83[升] ^ 40[駒]) 6000000000000000パターンで表現してしまうんですね。
これが嫌ならmasa氏の方式で行くんでしょうが、あれでも272bitが限界みたいですからね
あら？コピペ失敗した？？１行の文字列数が長すぎた？？
訂正
全ての歩が私の「と金」として盤上に存在する局面は、と金１、
と金２の位置交換の重複を考えると、同一局面であっても
８１！ ＞ 6000000000000000パターンで表現してしまうんですね。
あー気になってたところつつかれました。
やねさんへ
はい。83 ^ 40 を permutation(81, 40) + 手駒 にできれば幾分か縮みます。16bitくらい？
投稿直前まで悩んだのですが、「差分計算が速いこと」という要件があるので、実装が単純そうな83進数方式で計算しました。
りちゃさんへ
同一局面を示す異なる値が多いというツッコミですね。
下敷きにしたのが記事本文での計算方式で、駒ごとにビット位置を固定するものですので、そこから遊びビットを回収しようよ、というのが主旨です。この考え方だと本質的に背番号の並び替えのぶんだけ重複＝回収できない遊びが生じてしまいますね。
その点、masaさん方式だと必ず combination になる点で優れていますね。
ハフマン符号使いつつ将来的にそこそこ差分更新しやすくできそうな局面256bit化(手番含む、駒箱可能)を実装してみました(差分更新はまだ実装してません)。
CPU=i5 1.6Ghz, CXX=clangで、最多合法手局面(593通, R8/2K1S1SSk/4B4/9/9/9/9/9/1L1L1L3 b RBGSNLP3g3n17p 1)の256bit化1回あたり500nsecくらいでした。なお、同じCPU,CXX,同局面でなのはmini0.2.2のEncodeHuffman関数による256bit化1回あたりは1200nsecくらい。ただし、なのはminiは配布されたままだとコンパイルがうまく通らなくてMakefileをけっこういじったので、速度的に最善設定なのか自信なし。
差分更新までできたら、githubあたりに上げます。
また凄い人が現れた！差分更新が速いと嬉しいですね。私が考えたのは盤上の筋(or 段)ごとにハフマン符号化したものを256bit*9で持っておいて、更新のあった筋だけ再計算して、最後にそれ連結する方法です。差分計算、10ns程度で終われば、1Mnps(1nodeにつき1000ns)出てるときの1%がhashの更新にかかる時間だということになって、これぐらいであれば無視できる範囲なのですが…。(256bitものhashを探索時に置換表に格納したりするとメモリ帯域的に10%ぐらい速度低下があるでしょうけども、それはまた別の話で…)
古い話題になっちゃいましたが、以下、途中経過。
なお、短い実行時間の話になってきたので、実行時間測定にrdtscを使うようにしました。なので、クロック数表記です。???nsなどへの換算は各自でお願いいたします。
実行環境=CPU:i5 1.6Ghz, CXX:clang
局面: 最多合法手局面(593通)
256bit化1回あたり: 550〜600clk(非差分更新、前回より少し高速化してます)
256bit化後の単純な差分更新1手分: 15〜20clk(王以外の駒の同筋移動で、駒取りなし、成なし)
テーブル化でもう少し早くできそうな箇所があったり、逆に差分更新での指手の種類判定(駒取りの有無など)を呼び出し側に押し付けてるので本来はこれも差分更新の実行時間に含めるべきじゃないか？…など、実行時間がまだ多少前後しそうな状況ですが、差分更新で駒取や成が絡むともっと時間がかかるでしょうから(数倍〜10倍くらい？)、ご希望の10nsは無理かも。
まあ、せっかくなので、一通りの差分更新できるようになったら、どこかに上げます。
あ、コメントの仕方をミスった。
すいません、「通りすがり 2016年1月8日 07:40」は「通りすがり 2016年1月4日 12:24」の続きの話題です。
新しいアイデアが詰まってそうなので、完成したら是非ソースコードを公開してくだされ…。
出現確率？0.5に近いものに優先してビットを割り当てます。
盤上の有無81
先手持ち駒数6 後手持ち駒数は不要
駒の向き40
駒の成34
駒の種類 歩と以外か40
桂香金銀飛角王種別3×22=66
手番2こめの王の向きで表現0
合計267ビット
先手持ち駒5ビットでも実用上よさそうですが、
それでも266ビット。
それは更新に関してハフマン符号化するのと同じぐらいの計算量が発生するのにハフマン符号化よりサイズが縮まっていないので、劣化ハフマンなのでは…。
どうもです。
ハフマンで256以下になる保証か証明はないのでは？
まあ実用上オーバーすることはないんでしょうが。
更新時の差分が早くないと使えんというのはすみません。
ただパズル的に考えてるだけなので。
掛け算でビット圧縮は避けてますが。
さて成香の下記追記で4ビット減って263になりましたが、
3×22の中で飛角を同一扱いして代わりに成桂と桂馬を別扱いすれば
成りフラグを4ビット回収できます。
飛車角の順番は4C2で6通りなので3ビットで置換表で復号し、差し引き1ビット回収です。262。
まだ持ち駒に無駄な向きフラグと成りフラグがあり、1ビットを先手持ち駒7以下と8以上の区別に使えば、持ち駒8個以上のときに向きフラグを8ビット回収できます。金とか桂香とか成りフラグを失った駒ばかりでも向きフラグは回収できます。8以上なら持ち駒数は追加5ビットで表せるので純減8ビット=254。
問題は持ち駒7以下の場合に絞られます。
先手持ち駒数に3ビット必要なので持ち駒数を4ビットで表すことになり、元の6ビットに比べて2減の260ビット。
あと4ビットですがこっから先は思い付きませんでした。3×22の所に無駄が残ってると思いますが(各駒最大4こまでという情報をつかえてない)
同じ扱い&複合では変わらないです。銀と成銀別扱いで王と金同じ扱いだと、成りフラグ4ビット回収に復号6C2=15は4ビットで利得無し。
王を位置情報で別扱いにして銀と成り銀別扱いだと、王2個の歩フラグ種別フラグ向きフラグ回収で10ビット回収。成り銀フラグで4ビット回収。王の位置情報復旧に14ビットまたは81×81掛け算方式13ビットに失った手番フラグ復活で、15ビットまたは14ビットで利得無し。
ビット盤面の駒のないとこにしか王は来ないので、持ち駒少ないから空白は64以下、いやちがう、駒のあるとこにしかこないとすれば、王の位置は最大40駒の順番で各6ビットで表現でき、掛け算方式なら11ビット、40C39の置換表なら780で10ビットに収まる。手番フラグを含めても11ビットで復号。
あと1ビット!
40C39じゃなくて40C2か。でもそもそも王と玉の区別必要だから40P2で、11ビット必要ですね。
あと2ビットが限界でした。
> ハフマンで256以下になる保証か証明はないのでは？
出現頻度の高い駒(歩など)に短いbit列を割り当てるので全体のサイズは必ず固定長さになり、それが256bit以下になることは、「なのは」のソースコードにおいて証明されています。
それゆえ、ハフマンより差分更新が少なくてかつ256bitに収まる手法が求められていますが、ハフマンの差分更新自体をそこそこ高速化できるという議論が上のほうのコメントにあります。
そんなわけでして、
・256bit以下に収まる
・ハフマンより差分更新が楽
という両方の条件を満たしていただきたいのです。
なるほど。。。ハフマンで256ビット以下が保証されてるなら，基本はそれで行くしかなさそうな気がしますね。
というのは，私のパズル・手動パックでも相当情報量の濃ゆいビットを割り当てたつもりでしたが，1ビットに平均0.9ビット以上の情報を詰めるのは厄介です。
ハフマン符号化であらかじめ濃くしたビットを振っていくのが確実でシンプルだと思います。
そうそう，片方の持ち駒の情報は全く不要なのに気付いたので，持ち駒数が少ないときに持駒数表現に割り当てるビットを最小限にすることで合計256ビット以下になることがわかりました。
もはやどうでもいいんですが。
さっきのですが，香と成香を別種として3×22に含めれば，成フラグ4ビット回収できますね。これで263ビッ
…数え落としがあったらすみません。