置換表 (7)

テーマ:

CSA例会議事録がMLで流れてた。何か微妙に不思議なことが書かれてあったので、これを今回のネタにしようと思う。


さて、「ハッシュのクリア」とある。置換表の初期化のことだと思うが、謎電では起動時のみしかフィジカルなイニシャライズ(0クリア)は行っていない。だからと言って過去の探索記録を再利用しているわけでもなく、指将棋では探索の直前にロジカルなイニシャライズを毎回行っている。これは「一瞬」で済む。議事録では「ばかにならない」とか「クリアしなくてもよくないか」とあるので、


YSSでは毎回置換表全体を(物理的に)クリアしている


という解釈になるのだが、そうなの!? もう何年も前の話になるが、この件はKFEndの有岡さんとも議論したことがある。実際GBytes単位のメモリを置換表の為に確保し、それを毎回フィジカルにイニシャライズするのは時間コストが馬鹿にならないので、当然何かしらの工夫が必要だ。で、謎電では具体的には次の様な方法でこれを解決している。


・置換表の全てのレコード上に2bytes(unsigned short)のフィールドを用意する。仮にこれをrec.uとする。

・また、置換表利用回数を管理する2bytes変数を用意する。仮にこれをnとし、初期値は0とする。

・プログラム起動時のみ、置換表用メモリ確保と共に全体をフィジカルにイニシャライズする。

 (all 0x00 を書き込む/仮想記憶域から出す為に0x00以外の値をその前に一旦書いておくという裏技もある)

・置換表をロジカルにイニシャライズしたい時は、単にn++とする。

 (例えば指将棋の探索開始直前に、これを1回実行する)

・置換表内の任意のレコードrecが未使用かどうかは rec.uとnの比較で判定する。

 (rec.u==nで使用済、rec.u!=nで未使用を意味することになる)

・置換表内の任意のレコードrecを使用済にしたい場合は、そのレコードのフィールドrec.uにnを代入する。


これだけである。置換表内の各レコードが未使用か否かを「フラグ」で管理するのではなく「値」で管理しているというわけだ。この手法は微妙な問題を孕む(この例の場合、65536回前に初期化した筈の結果を「使用済」と判断してしまうことがありえる)のだが、実用上は問題ないものとして放っている。わざわざ説明するまでもない一般的な手法だと思われるのでこれまで書かなかったものの、プレッシャ~になるかなーという気がしたので一応書いてみることにした(笑)


【余談】 これはそれほど効果があるわけではないのだが、置換表のような巨大なメモリ領域を初期化したい場合に最も高速なのはmovdqa命令を巧く使うことである。但し、16バイトアドレス境界合わせをしないとaccess violationを起こすし、memset()と比べて数%しか速くならない(DRAMが相手の場合)。 更に余談だが、AMDのプロセッサではprefetchwを使えば多少は速くなると思ったのだが、2代目Athlonからハードウエアプリフェッチが効いているようで、現プロセッサでは効果が薄い(殆どない)ようである。
【補足】 付け加えて、詰将棋での千日手判定は(王手を掛ける手番時の)駒損同一盤面判定と併用(一発同時判定)が可能なので、千日手判定だけを外しても解図効率が上がる筈がないのだが、恐らく実装が謎電と異なるのだろうと思う。
【更に追記】 出席者の中に橋本博士(以後、ドクタ橋本と呼ぼうかと。あと飯田教授は、プロフェッサ飯田ですね、そのまんまですが)を発見。十二分にプレッシャ~を掛けていただけたのではないかと謎電の作者は分析している。
AD

本業モード、一旦終了

テーマ:

実家に帰ってきた。そろそろ本ブログの方も本腰入れて更新しようかとは思っているものの、別件の道楽にハマってしまい、本ブログの存在すら忘れかけていた。んで本題だが。


カメラマン山下選手の件、どうプレッシャ~を掛けるのが効果的か、先ずは「最善手0.5手延長」ネタで考察文を書こうかと思っていたのだが、某秘密基地の最新情報に拠れば、


突如PIC使って機械工学(メカ屋)やってる


らしい。うむ、これはとても良いことだと思う、芸域広がるし。このあたりも将来、プレッシャ~ネタにしよう、ふふふ。


ところで次のCSA例会、ML読むと「最近の改良」という内容で発表されるようである。惜しい、ちょっと行けそうもない、まったく残念。プレッシャ~を掛けるには滅多にないチャンスなのだが。というわけで、謎電の作者の代わりにプレッシャ~を掛けて頂けるオーディエンス募集中。CSAメンバでなくても9月9日は例会へゴー(笑)


【追記】
更に敵はPICでラーメンタイマも作っているらしい。となれば、謎電の作者的にFPGAで作らねばなるまい。というわけで、FPGAにスピーカ付けてみた。単なる矩形波ビープでは満足できないので、SACD の原理でもあるΔΣ変調 を使ってみる。簡単に言えばビットストリームD/A変換だ。指定時間経過するとチャルメラ の音色で、

ソラシ~ラソ、ソラシラソラ~~


てな感じで完了を知らせてくれる。これが日本が世界に誇るラーメンタイマの真のExtremeEditionである(笑) で、ΔΣ変調というと何やら難しく聴こえる が、これまた実にインチキ臭いほど簡単である。参考までにスケマを示す。

AD