置換表 (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

置換表 (6)

テーマ:

今日現在の謎電では、詰探索関数を複数のスレッドから排他的にしか実行出来ないように詰探索関数の冒頭でロックを掛け誤魔化しながら動いている。このようなやり方は序盤では殆ど問題にならないが、終盤ではどちらか一方のCPUしか殆ど働いていない状況に陥り、並列化の意味がなくなる。とはいえ、通常探索での置換表レコードロックは巧く働いていることは確認できたので、前回の続きとCraftyの「ロックしない手法」について私見を書く。


謎電の置換表レコード上にはセマフォとは別に、探索中は「探索中フラグ」を立てるのと同じ意味で「スレッド番号」を記録している。このフィールドが0であればその局面を探索しているスレッドはなし、0以外であればその識別番号を持つスレッドが探索中、という意味を示す。そのような区別を行っているのは、ノード再入(千日手)検出の誤った判断を防ぐ為でもあるし、重複探索を避けて効率を上げる為だ。特に後者の場合、単に別スレッドの探索が終了するのを待つのではなく、一旦(そのノードから見て)親のノードに戻り、別の手以下を先に探索[*1]するようにしている。


また、謎電の置換表は2つのテーブル(主表/副表)で構成される為、並列探索時は微妙に排他制御が複雑になっている。主表上のレコードついてのみ参照・更新を行う場合は、単にそのレコードをロックするだけだが、副表へレコードを移す時や追加する時は、副表をまるごとロックするような仕掛け[*2]になっている。また主表側のロックされているレコードを副表側へ移さなければならない状況が生じた場合は、当然ながらそのレコードのロックが解除されるまで待ち、自スレッドがそのレコードをロック出来たことを確認してから副表側へ移すようにしている。


以下Craftyの「ロックしない手法」に対する私見を述べる。


置換表(5)でも書いたが、レコードの情報を更新する際は勿論、read onlyで参照するだけであってもロックを行ってからでなければ整合性を保てない可能性がある。複数のスレッドが、そのレコードを単に読んでいるだけなら問題は生じない。しかしながら、一方が読んでいる時に他方が書き換えに行けば、そのタイミングによっては破壊されたデータを読み出すことになりかねないからだ。Craftyの「ロックしない手法」は、そのような事態の対処を考慮されていないように思う[*3]


例えばある矢倉の序盤で、2つのスレッドが▲37銀以下と▲79玉以下を探索する並列処理が行われたとする。具体的には▲37銀▽64角▲79玉、と手順前後で▲79玉▽64角▲37銀で同一の局面を探索することになるが、この時一方のスレッドでヒットし、排他的論理和演算で情報を可逆スクランブルしようとする直前に他方のスレッドが既にヒットしていて、データを読み出すタイミングがスクランブルされた直後ならば、そのデータは破壊されていることになる[*4]。そのようなメカニズムで進歩5のp.5の「最善手が壊れる」現象が起きるわけだ。特にスレッド(CPU)数が増え、1つのレコードに対して同じような時期にアクセスする頻度が高くなるほど、このような問題が起き易くなると考えられる。


[*1] これを謎電の作者は「問題先送り探索」と呼んでいる。実装法についてはいろいろ考えられるので、現在はまだ試行錯誤段階である。

[*2] これは現仕様で、将来もっと巧い方法が発見できれば変更の予定。

[*3] データが破壊されていないかどうかのチェックは行えるのかも知れないが、復元が確実に出来るわけではない。なぜなら、いつ他スレッドからそれがまた書き換えられるか判らないからだ。結局、ロックしない手法には無理がある。なお、xchg al, byte ptr [semaphore] のレイテンシはAMD64系プロセッサでは16[clocks]となっている。

[*4] これは、フリテンなしで九蓮宝燈9面待ちをツモ上がりするより遥かに高い確率で起き得る。なぜそう言えるのか、その根拠は全くない。

AD

置換表 (5)

テーマ:

1つの置換表を用いて並列探索を行う場合、置換表に対して排他的にアクセスが行えるようにする必要がある。そのアルゴリズムはいろいろ考えられるが、一般的にはレコード上にセマフォを設けて一方のスレッドがアクセス(データ参照・更新)している時、レコード単位でロックし他のスレッドはそのセマフォを除いてレコードをアクセス出来ないようにして情報の整合性を保つ、ということである。


進歩5のp.6にはYSSのコードが紹介されている。また作者である山下さんのCraftyの解析メモ の中でも示されている[*1]。Craftyの解析メモではセマフォがdwordで、この点無駄だと思っていたのだが、進歩5ではbyteに変更、ブラシアップされたのだと思われる。このレコードロック手法は謎電でも同様だが、進歩5で示されているコードに関して少し思うところを書くことにする。


まず直ぐに目につくのは、パーシャルレジスタアクセスが行われている点である。最近のプロセッサなら問題はない[*2]のかも知れないが、前世代のIntel系プロセッサだと、1つのレジスタに対してデータ幅の異なるアクセスを交互に行おうとするとストール(ペナルテイ)が発生するので気になるところである。ここはbyteアクセスで統一し、test al,al と書いた方が無難、付け加えて冒頭の xor eax,eax が不要になる[*3]


ここからは余談。test命令は、and命令とフラグの変化は同じで演算結果は捨てられる、というインストラクションである。使うニモニックとしてはandでも、仮にorを使ったとしてもzフラグを見るだけだから正しく動く。しかしながら省電力の観点から見ると、ALU-レジスタ間データ転送が(場合によってはレジスタリネーミングも)行われないので、test命令を用いるのがこの際ベストと言える。


また、何かしらのレジスタに0を代入したい時、xor reg,regとかsub reg,regと書くよりも、現在のx86系プロセッサではmov reg,0と素直に書いた方が低消費電力(ALUを駆動しないので)と考えられるしスルプットも変わらない[*4]。以前は、高速化プログラミングこそ絶対正義だったが、現代のトレンドは省電力だ。


省電力プログラミングこそ、絶対正義 [*5]


エネルギ問題が深刻化している昨今、[Ws(ワット秒)]あたり何局面を探索するかが問われる時代になるかも知れない[*6]


[*1] Craftyの手法は面白そうだが、そのやり方でCraftyが動いている方が不思議だと私は思っている。実際にYSSでは採用を止めたようで賢明な判断ではないかと感じる。

[*2] ない筈だが、エラッタとして存在することを否定できない。昔の話だが、Intelの前科Errata59や初代Pentiumのfp除算には私は泣かされた。

[*3] と、掲示板に書こうと思いつつ、気の小さい謎電の作者はちょービビって書けなかった。

[*4] 但し、mov reg,0 のregがbyteレジスタの時コードサイズは2バイトでも、dwordレジスタならコードサイズは5バイトになる。従って、0クリアに限りbyte型を除いて省コードを目的とするならxor命令を使うことは有効である(例えば、xor eax,eax の総コード長は2バイト、当然32bitモードでの話)。

[*5] (c)2006 謎電の作者。結果として同じなら消費電力の少ない命令を使う方が望ましい。これはコア自体の熱の発生を抑え、熱暴走の危険を減らすことにも繋がる。省電力プログラミングの基本は、プロセッサ内部の実行器および周辺の回路資源を意味なく使わない、ということである。

[*6] んなこと本気で言ってるのは私だけかもしれない(笑)

AD

置換表 (4)

テーマ:

置換表で、持駒違い同一盤面の管理についてリスト(リンク)管理されている方がいらっしゃった[*1]。世の中には同じことを考える人はいるものだなと思ったのだが、その時に出た話題の一つに、「オーバフロ時の古いデータへの上書き」があった。その時、うっかり誤ったことを言ってしまったので、ここで訂正する。

現在の謎電では、純粋に「最も古いデータ」に対して上書きを行っているわけではなかった。正確には、次のようなアルゴリズムになっている。


1) 主表側[*2]で最大8回まで再ハッシュを行い、それでも書き込む領域がない場合、

2) その8回アクセスした8つのレコードの中で最も情報コストの低いレコードと比べて、

(但し、副表へリンクしてないレコードであることが前提)

3) 新たに登録したいレコードの方が情報コストが高い場合に、そこへ上書きする。


ここでいう「情報コスト」とは、その結論値を得るコスト(探索量)を意味する。従って「古いか新しいか」ということに対して判断は行っていない。

その昔、置換表にレコードを書き込む毎に、書き込んだ回数(単に32ビットのカウント値)を記録して、その値を元に「どのレコードが一番古いか」を判断していた[*3]のだが、それより「コスト」を重視した方がよいという結論に達し、今のアルゴリズムになっている。


[*1] 選手権の会場で個人的に知ったことなので、一旦匿名とする。無問題であるならば、コメントで表明されることを希望。

[*2] 副表へ登録する場合で、且つ副表がオーバフロしている場合は、 上記のような上書き処理は行わずに捨てている(現仕様、但し将来は変える予定)。

[*3] この方法だと、当然232回の書き込みまでしか新旧の正しい判断は保証されない。

置換表 (3)

テーマ:
置換表は、単に局面の探索値や詰結論を保持するだけでなく、いろいろな活用が出来る。例えば再入フラグを用意すれば、探索中に千日手の検出も可能だし、αβ枝刈が起きた時の最善手データを保持しておけば、次回反復深化の同一ノードでの探索の時に指手生成を省いて、その手だけをまず読んでみる[*1]ということも出来る。

ハード的な理由[*2]や何かしらの制限で置換表を大きく持てない場合は、2レベル置換表[*3]と呼ばれるデータ構造で管理するのも手だが、一般的なパソコンで動かすアプリケーションの場合は、メモリサイズを充分に大きく確保できるので、同一盤面で持駒違いのレコードは別途管理する方法も考えられる。

具体的には、主表と副表の2つの表を用意し、ユニークな盤面キーを持つレコードについては主表で管理する。ある時、持駒違いの同一盤面のレコードを登録しなければならなくなった場合、副表に書き込んでおいて、そのレコードのアドレスを主表側のレコードに記録しておく、というものである。勿論、更に持駒の異なる同一盤面レコードを登録しなければならなくなった時は、副表の方でポインタをリンクし連結させていく、というやり方だ。

詰探索の場合、持駒違いの同一盤面データが、5~25%程度の頻度で発生する。平均すると15%程度になる。これを1つの表で管理しようとすると、局所的にキーのぶつかり合いが多くなり、登録・表引効率が落ちることがある。これを避けようというわけだ。謎電では、そういう方式で置換表を使っている。

因みに、置換表(1)で示した詰物を解いた時の置換表の利用状況は次の通り。
--
主使用数: 64,213[rec] (主表の使用レコード数)
・拡張数:  4,956[rec] (副表へリンクした主表側のレコード数)
拡張率  :     77[‰]  (副表へリンクが起きた確率)
副確保数: 10,880[rec] (持駒違いの同一局面の総レコード数)
※「拡張率」は%ではなく‰(パーミル/千分率)表示なので注意
--
詰情報数: 70,137[rec] (主表+副表で真に使用した総レコード数)
                      =主使用数-拡張数+副確保数
・詰    :  4,507[rec] (詰結論が得られたレコード数)
・不詰  : 45,251[rec] (不詰結論が得られたレコード数)
・不明  : 20,379[rec] (結論が得られなかったレコード数)
最多使用:      8[rec] (副表内の同一盤面最多リンクレコード数)
--
このようにレコード管理を行うと、同一キー(同一盤面)のレコードのぶつかり合いやオーバフロが起き難くなるので、置換表の利用効率について私的に満足している。

[*1] そうすることによって再度枝刈が起きれば、探索効率が上がるだけでなく、指手生成自体を部分的に省略出来るので、少なからずコストを減らすことが可能になり探索が高速化する。
[*2] 例えばPS2のような家庭用ゲーム機では、元々載っているメモリが少ない。
[*3] 同一の局面キー値のデータが複数存在する場合、「1)最新の情報 2)探索量の最も大きい方」の2つを保持する方法。つまりは古い結論データや少ない探索量で結果を得られる局面の結論データに上書きされ、実質消されるのと等価となる。

置換表 (2)

テーマ:
置換表は、言葉通りテーブルである。つまりはレコードの表を意味する。一つのレコードは、キー(インデクス)部とデータ部から成る。レコードのサイズは開発者の設計に因るが、概ね16~32バイトの大きさになる。2nバイトの大きさにした方が、計算機のアーキテクチャ上、登録・表引処理を高速に出来るが、16を越えたら32としてしまうとメモリの使用効率が悪くなるので、4nバイトの大きさにすることもある[*1]。

計算機将棋で用いる置換表のキーは局面をコード化したものだが、現在の主流は、局面=盤面+持駒と分けて「盤面をハッシュキー化[*2]し、持駒はデータ部へ置く」のが一般的だ。単純な完全同一局面だけでなく、持駒違いの「同一盤面」の結果を引用できることもあるからだ。例えば詰探索で、ある盤面で持駒が金1枚で詰むことが判っていれば、その情報を利用して、盤面が同一で持駒の中に金1枚以上があれば、他の駒のあるなしに関わらず詰むと判断出来る。

置換表は詰探索の為だけに用いられているわけではなく、指将棋の探索でも、探索値を記録しておき、探索の条件次第で手順違いの同一局面の結果を引用できる。「条件次第」というのは、例えばある局面で「そこから5手先まで読んだ時の探索値が+250」という記録があれば、少なくとも5手以内の探索値を得たい場合は、そのまま+250を引用可能という意味だ。

さて、αβカット法で探索を行う場合、探索値は真値ではなく境界値になることがある。最善手順ノード上などの「生成した手全てを読んだ時の探索値」は真値だが、枝刈が起きたノードでの探索値は「以上」あるいは「以下」の意味になるので、その扱いに注意が必要になる。

そのような境界値を置換表で管理する場合、探索値とは別に「真値・以上・以下」の識別が出来るように特別なビットフィールドを用意する方法もあるが、最初から「以上値」と「以下値」を独立した2つのフィールドで探索値を管理する方法[*3]も考えられる。探索値が真値なら「以上値」も「以下値」も同じ値にするということだ。

謎電に、そのアイデアを実装してみた。結果として速くなることはなかったが、探索値の登録と引用に関するするコード部分は、判り難い判定文がなくなった分だけ簡略化出来た。アイデアとしては悪くないと思ったが、実装やデバグの手間を考えると、割に合う改造だったかどうか判断がつきにくい。

[*1] 因みに謎電の場合、32バイト/レコードとして、32バイト全部をフィールドとして使用している。平均毎秒30万レコードの登録が行われるので、先述のように毎秒10MBくらい置換表を消費することになる。
[*2] 桝位置と駒の種類(先/後、および生/成の区別あり)全てにハッシュ値を予め決めておき、盤上の駒の配置に基づいてキーの計算を行う。現在では64ビットの長さにすることが一般的。なお、手番情報についてもキーの中に含ませるやり方もあるが、謎電では手番をキーに含ませず、表自体を(論理的に)独立させている。
[*3] 探索値をshort(符号付16ビット)型2つの合計4バイトで管理させている。探索値を16ビットで管理するのは、386ネイティブ(プロテクト)モード以前の古典的にして伝統的な手法だ。このあたりは近い将来ネタにしようと思う。

置換表 (1)

テーマ:
左図は、詰将棋探検隊の90番(三木宗太作/詰パラ昭和50.10)から引用。
作意は97手詰[*1]。謎電にとって非PN探索で実用時間内で解ける最長手数詰物である。
PNを使わずこの詰物を実用的な時間で解けるのは置換表[*2]のお陰だ。置換表の役目は、一言で言えば「重複した探索を抑えること」である。つまり、一度探索した局面の結論を保持しておき、手順違いによって同一局面に達した時、過去に探索した結論を用いることによって探索コストを省こうというわけだ[*3]。この詰物を謎電で解いた時の時間は0.368秒(Barton/3000+)だが、もし置換表を用いずに解図を行うと「秒」の世界では探索が終らない。実際にこの問題を置換表を使わず解図してみると、10分経っても詰結論を得られなかった。
去年の選手権で謎電は、1.25GBのメモリを確保して置換表に割り当てていた。これだけ確保すれば、指将棋探索ならば約120秒間はオーバフロを起こしにくい[*4]。これは毎秒10MB程度のテーブルを消費していることを意味する。1.25GBというサイズは、1手に配分する最長時間から逆算して割り当てた大きさだが、マシンの性能が上がるにつれて探索レートが上がる=置換表の消費レートも上がるので適切に増やす必要が出てくる。
最近では、PC3200(DDR400)の512MB品が\4,000-台、1GB品が\13,000-台で買えるようになった。ヘタにCPUのアップグレイドを行うより、メモリをテンコ盛りにした方がコスト対性能比は良くなるかもしれない。

[*1] 謎電で解いた時の手順は、▲13角▽21玉▲22歩▽12玉▲24角不成▽22玉▲13角不成▽21玉▲22歩▽12玉▲35角不成▽22玉▲13角不成▽21玉▲22歩▽12玉▲46角不成▽22玉▲13角不成▽21玉▲22歩▽12玉▲57角不成▽22玉▲13角不成▽21玉▲22歩▽12玉▲68角不成▽22玉▲13角不成▽21玉▲22歩▽12玉▲79角成▽22玉▲13馬▽21玉▲31馬▽同玉▲33香▽41玉▲32香成▽51玉▲42成香寄▽61玉▲52成香上▽72玉▲64桂▽81玉▲82歩▽92玉▲84角不成▽82玉▲93角不成▽81玉▲82歩▽92玉▲75角不成▽82玉▲93角不成▽81玉▲82歩▽92玉▲66角不成▽82玉▲93角不成▽81玉▲82歩▽92玉▲48角不成▽82玉▲93角不成▽81玉▲82歩▽92玉▲39角成▽82玉▲93馬▽81玉▲71馬▽同玉▲62成香▽同玉▲52成香▽71玉▲72歩▽81玉▲82歩▽同玉▲74桂▽81玉▲71歩成▽同玉▲62桂成▽81玉▲72桂成まで97手詰。
[*2] 置換表とは、"Transposition table"の和訳。「局面表」、あるいはハッシュキーを用いるテーブルであることから「ハッシュ表」と呼ばれることもある。
[*3] 通常、置換表を用いずに非PNで反復深化AND-OR探索を行った時(探索の対象となる詰物にもよるが)、置換表なしでは2手深く読む毎に4~5倍程度、置換表ありなら2手深く読む毎に3倍程度探索量が増加する。つまりは、置換表を用いると深く読むほど(反復深化回数が増えるに従って)相対的な探索効率が変化(向上)する。
[*4] 逆に言えば、これより小さいと2分前に得た局面の探索結果を覚えていられないということになるが、オーバフロが発生しだすともっと悲惨で、「数μ秒前の結果すら覚えてない」という言わば痴呆症現象が起きるようになる。