うらお今回は、置換表の仕組みとその実装について説明します。perftの高速化のための置換表を実装するまず前回の宿題。perftの高速化のための置換表を実装するところから。keyを変更しておく。keyを変更しておく。keyの下位bitをindexとして、置換表にアクセスする。する)と、indexの値が求まる。この意味がわからない人は、PCの電卓を起動して、プログラマー電卓モードで2進数で10000000と入力して1引いてみること。これは、01111111という答えになる。entryCount]としてもだいたい同じ意味ではあるが、剰余の計算やや遅いというのと、(厳密には)一様分布でないのが、少し気になる。一様分布の意味がわからない人はggrks。してしまうと一様分布にならない。このへん、bit演算に慣れていない人には説明わかりにくいみたいなので、追記。ここまでの話がわかりにくい人は、10進数で考えてみるといいかも。100で割った余りは下2桁を見ればよい。同様に2進数でもこれと同じ理屈が成り立つ。100b(末尾のbは2進数表記であるの意味)で割った余りも2進数表記の下2桁を見ればよい。取ると元の100000bで割った余りとなるのである。line(通例64bytes)の倍数か約数にして、かつ、tableのメモリアライメントを64bytes境界になるように調整したほうが速いことは言うまでもないことではあるが、この実装について興味のある人は、Stockfishのtt.h/tt.cppを見て欲しい。それから、上のプログラム中にDepthHash(depth)というのが出てくるが、これはただの乱数テーブルで、depthに応じた何かしらの乱数値が返ってくる。本当は、局面のhash値をキーとしてdepthとPerftSolverResultを格納すればいいのであるが、それだと同じ局面のdepth違いの情報が同じTTEntryに格納することになってしまう。普通、将棋の思考エンジンで用いる置換表では、このようにTTEntryが衝突した場合に、何かしらの方法で格納する。いう仕組みを用意するのは面倒なので、ここでは、hash値とdepthをキーとしてPerftSolverResultを格納したかったのだ。そこでhash値をdepthも考慮した値にする必要があった。}という組み合わせに対応するhash値が得られるという考えである。上のプログラムが置換表の説明および実装として、最小限のプログラムで、これを改良すればどんな置換表でも自由自在に(?)作れるようになるわけだ。うら王miniは将棋思考エンジンフレームワークを標榜するわけであるが、置換表に何を格納するかというのは、どんなプログラムにしたいかで異なってくる。上のperftの例で言えば、局面とdepthをキーとして、perftの統計情報(PerftSolverResult構造体)をそのまま格納しておきたかった。このように、将棋エンジンごとに置換表というのは異なるのが自然であるので、無理にやねうら王miniの置換表を使うことはないと思う。置換表はこのように簡単に実装できるのだから。Keyを128bit/256bit化できる無駄機能があるとお答えしておこう。本当、無駄機能なので、こういう無駄機能を省いて、ソースコードを短くしたやねうら王nanoを別途公開しようかと考えているところである。なんじゃ?と思った人もおられるだろう。Keyを128bitとか256bitにしたときに、下位64bitを得るための呪文である。keyのサイズ自体はshogi.hの冒頭で変更できるようになっている。研究時に局面が厳密に合致しているかどうかを判定したいときなどに用いる。うら王nanoではこの機能は削除する予定。研究時に局面が厳密に合致しているかどうかを判定したいときなどに用いる。うら王nanoではこの機能は削除する予定。Keyを選択しているときは以下のKey128が用いられる。SSEの命令が使ってある。256bit版はAVXの命令が使ってある。Keyが大きくなるとそれをそのまま置換表に格納する場合、メモリ転送量が増えてメモリ帯域を圧迫するので当然ながら遅くなる。Keyは実用になる気がしなくもないのだが...。keyの実装で面白い点を挙げておく。keyにしたときに、その定跡DBが使えないことになってしまう。keyのときのhash値と完全に一致するように実装してある。keyの自然な拡張というわけだ。関数の引数に直接書くと(rand関数呼び出しの)評価順序が既定されていないので困る。C++11では左からのはずなのだがVC++2015ではそうなっていない。関数の引数に直接書くと(rand関数呼び出しの)評価順序が既定されていないので困る。C++11では左からのはずなのだがVC++2015ではそうなっていない。}#endifこういうSET_HASHというマクロを用意して、以下のように初期化する。keyを生成するときも64bitの乱数を4つ生成して、そのうちの3つを捨てているわけだ。面白い実装だと思うが、いかがであろうか。手番としてbit0を用いる。それ以外はbit0を使わない。これをxorではなく加算して行ってもbit0は汚されない。keyの下位64bitは合致するようにしておく。これは定跡DBなどで使うときにこの性質が欲しいからである。keyを求めたいときに用いる。手番としてbit0を用いる。それ以外はbit0を使わない。これをxorではなく加算して行ってもbit0は汚されない。keyの下位64bitは合致するようにしておく。これは定跡DBなどで使うときにこの性質が欲しいからである。keyを求めたいときに用いる。Hashを将棋ではxorではなくaddで行なうというところまで話をしたが、注意しなければならないことの説明がまだ終わってなかった。置換表に登録した指し手を取り出してくるわけだが、いくつか困ったことになる。hashが衝突したりして別の局面の情報が登録されていることがある。SMPによる影響、すなわち、置換表のエントリーから値を取り出しているときに、別のスレッドによって置換表のエントリーの書き換えが起きることもある。Multiprocessingの略のようで、「他のスレッドが壊すねん!」という文脈でよくStockfishのソースコードに書いてあるので覚えておくといいと思う。置換表に登録している情報のうち最も重要な情報は指し手である。その局面でベストだと思われる指し手を登録しておくのに使う。これが他の局面の指し手を間違って取り出してしまった場合、どうだろうか。その局面では非合法手となってしまう。その結果、3枚目の角を打ってしまうかも知れない。(笑)そこで置換表から取り出してきた指し手に関しては、合法手かどうかを判定しないといけない。ところが、先手は1段目に歩を打てない。51歩打みたいな手は先手の手としては非合法手である。後手の51歩打は非合法ではない。正確に言うと、51の升に駒があると打てないから非合法手だし、二歩であるとか打ち歩詰めであるとか、etc...のケースにおいて非合法手であるが、51歩打だから非合法手とは言えない。後手の51歩打は非合法手とは限らない。よって、置換表から取り出してきた指し手の合法性についてチェックするときに、これが後手の局面用の指し手だとわかっていれば51歩打という指し手があっても、打てないはずの升への打ち歩でないことは確かなので、この合法性のチェックの処理が一部省略できるのである。置換表は、先手の局面と後手の局面とは登録する場所が分かれていて欲しい。置換表はそのような性質を持っているのが望ましい。keyの下位から何bitかを使う。さきほどの置換表の実装を思い出して欲しい。1)];と書いてあった。HashEntryが先手と後手とで異なる場所であることを担保するには、先手と後手とで、hashのどこかのbitが異なる値になっていれば良いが、上のようにエントリーのアドレスを求めるとしたら、そのために使えるbitはbit0しかない。ここ以外のbitはアドレスの計算に必ず使うとは言いがたいからである。そこで先手ならbit0を0、後手ならbit0を1とするような実装にする。するとさきほどのpsq,handの乱数テーブルなどもbit0は手番情報として使うので0にしておかなければならない。bit0が0である数字をいくら足そうが引こうがbit0は0のままであるので、bit0に影響を及ぼさない。keyのbit0を用いる。さきほどの乱数テーブルの初期化するソースコードで言うところのZobrist::sideがこのための定数である。次は先手番なのでZobrist::sideを減算となるわけであるが、do_move()では相手番になれば良いのでこんな判定処理は不要で、単に次のようにすれば相手番となる。Hashにおいても、手番の更新だけはxorで済ませるというテクニックが誕生した。Hashing(xorを用いるオリジナルのほう)では、sideも単なる乱数値で上のように1という定数ではない。Hashingはコンピューターチェスの開発過程で発祥したものであり、チェスには将棋の先手51歩打のような先手だけが非合法手となるような性質の指し手は存在しないので、仮にhashが衝突して置換表から先手用の局面の指し手として後手の指し手が得られたとしても、上に書いたような合法性のチェック上の問題は発生しないので、問題とならなかったのだろう。0はside(手番)を表すbitとして確保しておくような実装が好ましいのである。これは将棋特有の問題であるということになる。keyの実装の完全な理解が得られ、そして、置換表の自前実装が出来るようになった。(と思いたい)次回に続く。:うーむ、やはりなかなか手強いですね。恒例のまちがい探し、一つ。>上のperftの例で言えば、局面とdepthをキーととして・・・あまりの思考の速さにタイピングの速さが追いついていない様です。昔の人は言ったものです。急いては事を仕損じる、、、とかや。:YaneuraOuで遊ばせて頂いているプログラミング初心者です。仕様っぽかったのですが、一件念のためご報告です。例によって、もし見当はずれな内容でしたら、申し訳ございませんが無視ください。NORMAL_PERFTをコメントアウトして、高速なperftを行おうとしたところ、置換表確保時に私のPCの8GBのメモリを食いつぶしてPCがフリーズしました。置換表のサイズを4GB以下程度に変更したところ、正常に動作しました。完全に私のPCが貧弱なせいなのですが、公開時に同様の事象が起こる人もいそうだと思いましたので、念のためご報告させていただきます。いつも楽しく拝見させていただいております。