最近瀬川アマのプロ入り試験がいろいろなところで話題になっている。実のところ、私はこのことにあまり興味がなかった。何故なら、これは瀬川さん本人の実力が決める問題で、彼がプロ棋士になれてもなれなくても廻りが騒ぐようなことではないと思っていたからだ。ところがBIGLOBEストリームで米長会長曰く「祭りということで、大いに盛り上げて頂きたい」ということらしく、このプロ入り6番試験の意図は何なのか判ったような気がした。試験対局の相手が当初の発表と変わって、何故か2番目に神吉六段が出てくることなっている。しかも神吉曰く「立ち直れないくらいに叩きつぶします[*1]」と、これはまた過激な発言が飛び出ているし、俄然興味を持ってしまった。


既に1局目佐藤(天)三段戦が7月18日に行われ、当日のNHK総合のニュース7で報道された。夕食時全国レベルのニュース扱いになっていたのにはかなり驚いた。結果として、やはり現役奨励会員三段は強かったわけだが、ここで(アマに)負けるようでは(奨励会員の方が)プロになることを諦めなければならなくなってしまう。瀬川アマにとっては、奨励会員にプロ入りを認めさせる為に何があっても絶対勝たなければならない将棋だった筈で、そのプレッシャは想像を絶するものだったかもしれない。


余談だが、このニュース中「プロ棋士になるまでの順序」が簡単だが的確に解説された。知ってる者にとっては余計なレクチャだが、これが予め判ってないと何故に「プロ入り試験」が話題になってるのか、将棋界に興味のないものにはチンプンカンプンなので、あの短い時間の中で実に巧い解説を入れたものだなと感心した。


既にタイミングを逸してしまったネタのような気がするのだが、とりあえず謎電での解図結果をメモしておく。


左図は、飛車を取られた所。本譜は▲53桂▽42玉と進行するのだが、ここでは▲32歩成▽同玉(▽同銀は、▲34桂以下必至)▲23銀▽同玉▲35桂▽22玉(▽14玉は、▲26桂以下頓死)▲23金▽31玉▲43桂成までの9手必至がある。

しかしながら▲53桂からの「超安全な勝ち方」は、見習った方が良いのかもしれない。勝ち将棋鬼のごとし、とはこのことか。


左図は、▲33歩に▽43銀とかわしたところだ。ここから本譜は▲32金だが、▲22銀の方が速く、これで必至上がり。これだと▽53香すら指せず(▲41金の1手詰)投げるしかない。


謎電的に、この局面は「頓死・頓必至なし」として、瞬時に▲22銀と指すし、殆どの将棋プログラムがそう指すのではないだろうか。私の目には、この将棋は、あまりに大差が付いてしまっているように感じる。



[*1] ZAKZAK(05/07/07)からの引用。本当にそう言ったのか疑問に感じてはいるのだが、これも奥の深い宣言である。
AD

参考資料

テーマ:

思うところあってちょっと調べてみた。瀬川晶司アマは昭和45年3月23日生である。その±1年間に生まれたプロ棋士(故人含む)は次の通り。なお、括弧内は棋士番号。これは「プロになった順」も意味する。


s44. 4. 2 飯塚祐紀  (203)
s44. 6. 3 畠山鎮    (192)
s44. 6. 3 畠山成幸  (193)
s44. 6.15 村山聖    (180)
s44.10. 1 佐藤康光  (182)
s45. 2. 3 中座真    (219)
s45. 6.22 先崎学    (185)
s45. 9. 5 丸山忠久  (194)
s45. 9.27 羽生善治  (175)
s45. 9.29 藤井猛    (198)
s45.10.10 森内俊之  (183)
s46. 2. 7 増田裕司  (225)
s46. 3.17 郷田真隆  (195)

よく見ると、これは相当な激戦区である。また、個人的に何かしら縁のあるプロ棋士も次にメモしておく。


s32. 4.29 田中寅彦  (127)
s34. 3. 1 神吉宏充  (160)
s37. 1.17 飯田弘之  (159)
s37. 4. 6 谷川浩司  (131)
s44. 3.21 勝又清和  (215)

余談だが、50音順で並べると田中(寅)の直後に谷川がくる。また、神吉と飯田先生が殆ど同期というのには驚いた。奨励会卒業順位で言えば、飯田先生の方が上だ。因みに私は谷川とカスパロフを足して2で割ったあたりの生年月日なのだが、選手権での実力は、神吉並である(笑)

AD

Move Generator 分析 (5)

テーマ:

最後に、MarcのMoveGeneratorの指手の優先制御について分析する。基本的にアービトレイション中にMVV/LVAに基いた move ordering が行われているわけだが、全生成手の優先順を見ると王手とポーンが成る手が例外扱いされており、全体的な優先付けは次の様になっている。
--
1) 王手
2) 成る手(あれば)
3) 駒を取る手(MVV/LVA順)
4) 駒を取らない手
--
この優先順をそのまま将棋で用いるのは不適切と思える。将棋では、王手が最善手になるのは寄せか詰がある、あるいは勝負が決するほどの駒得になる場合くらいだし、チェスのようにポーンが成ると勝負が決まってしまうような状況は少ない。従って、1) 2) は省くとして 3) 4) をこのままとするのもいささか問題がある。MarcのMoveGeneratorでは、「最も価値の高い敵駒」を「最も価値の低い自駒」で取る手の順になってはいるが、純粋な交換値(差分値)ではなく「敵駒の価値」が優先される[*1]。ソフト探索では、駒を取る手で優先度を決める場合、通常以下のことも付加し複雑になる。
--
a) 取れる敵駒が只か否か
- また取った時に成れるか否か

- その敵駒が、次に自駒を取れるか否か
b) 取りに行く自駒が取られそうな状態か否か
- 取られそうなら紐が付いているか否か
- 更に紐が付いているなら、敵のどの種類の駒に取られそうか
--
これらを加味してやや精密な交換値を求め、優先順を制御した方が効率は上がる(αβ枝刈が効いて探索量が減る)。しかしながらハード探索の場合、ここに挙げた判断や演算全部をそのまま実装しようとすると複雑になり過ぎて回路規模が大きくなる上にクリティカルパス、つまりは探索速度にまで影響が及びかねないのでバランスが問題となる。このあたりは実際に試して実験値を得ないと何とも言えないが、将棋に適した指手優先制御を考える必要があることを、今後の課題としてここに挙げておく。


更に、静止探索に入る前の「4) 駒を取らない手」についても、何の工夫もなく漠然と「盤上の駒が動く手」「持駒を盤上に打つ手」を生成し探索しても当然ながら効率は上がらない。チェスでは駒を打つ手がルール上存在しないので、ここでも将棋固有の優先付けの工夫が重要になってくる。付け加えて、全幅探索で良いのならまだ簡単だが、選択的探索を実現したいならば優先付けだけでなく生成条件付けも必要になり、回路規模の増加が避けられなくなる問題も出てくると予想できる。


将棋でのハード探索が有効であるか否かを決めるのは、このあたりの研究が非常に大きな鍵になると思われる。探索速度は上がっても、探索順の拙さによって探索効率が落ちれば、ハード探索の意味が薄れてしまうからだ。私個人の目標としては、2年以内を目処に一次試作を完了させる予定で、それまでにある程度解決しておきたい最優先事項である。実証で3年、実用まで5年といったところ[*2]


[*1] このあたりの詳細は、以前に挙げたMarcの論文中に記述されている。要は「移動先のループ」と「移動元のループ」があり、それまで生成してない手の中で最有力手を取り出すという手法で、外側の「移動先」が内側の「移動元」より優先され、純粋な交換値ではなく「取る駒の価値」が優先キーになる。これがアービタによってソートされることになるだけだが、生成速度を重視するならば、この手法は極めて有力と考えられる。

[*2] このような計画では、A岡さん(特に名を秘す)やY下さん(特に名を秘す)に先を越されるかも知れない。いや、もしかしてK木さん(特に名を秘す)が数年前から作ってたりして、しかも既に動いてたりして? 私はゆっくりですが追いかけますので、みなさんお先にどうぞ。

AD

Move Generator 分析 (4)

テーマ:

ここでは、MarcのMoveGeneratorの中でのデータ表現について分析してみる。盤上の桝位置を示す値、駒コードについては、Marcのソース chess_square_defs.vhd の中で定義されている。桝位置はカラム/ローが3ビットづつ("000"~"111")の計6ビット、駒コードは3ビットで具体的には次の様な表現になっている[*1]
--
"000":Empty (空桝)
"001":Pawn
"010":King
"100":Knight
"101":Bishop
"110":Rook
"111":Queen
--
更に色(手番)は "1" をWhite、"0" をBlackとし、色+駒コードの合計4ビットで駒種を表現している。これとは別に、更に2つの内部表現がある。1つは「駒の利き表現(6ビット)」で、もう一つはアービトレーション用「優先度(3ビット)」だ[*2]。どちらも駒種コードからデコード生成され、内部的に処理し易いように変換しているだけのことなので複雑に考える必要はない。


これを将棋へ適用する場合、余程酷いコード設計でない限りは神経質になる必要はないと考える。必要があれば、処理の内容に応じて内部でコード変換を掛けて用いれば良いだけの話だ。とはいえ無駄なデコードが頻繁に入るようではリソース的にも速度的にも厳しくなるので、なるべく(ソフト処理でもハード処理でも)合理的な将棋用のコードをここで考えてみることにする。
--
(bit0~3の4ビット)
"0000":歩 "1000":と
"0001":香 "1001":成香
"0010":桂 "1010":成桂
"0011":銀 "1011":成銀
"0100":金 "1100":<未使用>
"0101":角 "1101":馬
"0110":飛 "1110":竜
"0111":玉 "1111":<仮想合駒>
--
上記は現謎電で使用している駒コードで、4ビットで構成される。これがベストだとは言えないかもしれないが、ソフト/ハード共用で使うコードとしては、それほど悪くはないと考えている。また、これとは別に手番等を示す為に2ビットが頭に付加される。
--
(bit4~5の2ビット)
"00":空桝
"01":先手(下手)駒
"10":後手(上手)駒
"11":<移動不可:OB領域>
--
この中の "11" については内部的なコードで盤外検出用に使っているものである。ソフト探索の場合に意味があるだけで、ハード探索では決して使用されない[*3]。なお、指手の生成順の制御は、アービタに送り込む「駒の優先度」、即ち駒の価値で決められることになるわけだが、その場合は4ビット駒コードから4つのLUTを使い1つのロジックレベルで変換が可能であるし、利き表現については元々将棋は駒種が多く、左右対称ではあっても「前後の対称性」が低いので、チェスの様には単純化出来ないものと考えている。


余談だが、ソフトでのデータ表現の場合、「ビット位置」が極めて重要な意味を持つ場合があるが、ハードでは基本的にON/OFFの表現であって、それを纏めて「2進数値」として捉えるだけでなく、「ベクトル」や「1ビットデータの配列」として扱う。結局配線次第でビット位置を自在に入れ替えたり削ったり割り込んだり出来るので、ソフトより更に「柔軟にデータ処理ができる」ことを知っておく必要があり、それがハードを巧く使うコツにもなる。

-- 続く --


[*1] なにやら妙なコード体系に見えるが、これはこれで相当合理的な割り当て方である。

[*2] 詳しくは、Marcのソース chess_square.vhd と論文 MBThesis.pdf "An FPGA Move Generator for the Game of Chess"の4-3(前者)と4-4(後者)を参照のこと。
[*3] そもそもハード探索の場合、盤外に相当する「桝」が存在しない。

Move Generator 分析 (3)

テーマ:

今回は、MarcのMoveGeneratorの手法を将棋へ適用してみることを考える。これは、あくまで指手生成を行う回路のみが対象だが、探索コアの要と言える、このメカニズムとアーキテクチャが理解できれば、局面更新(1手進めるか戻す)処理は赤子の手を捻るようなものであるし、静的局面評価は好きなように演算させれば良いだけだし、探索制御は有限状態マシン(FSM)を組むだけの話になる。


Chrillyの探索コアは、それらを全て含んで10,000slices程度のリソースを消費し、MarcのMoveGeneratorは約10,000LUTs、つまりは5,000slices程度を消費している。ChrillyもMarcも、DeepBlueのMoveGeneratorを参考にしており[*1]、局面評価と探索FSM、その他の足廻の回路を組めば探索コアが出来上がる。探索コアは、前述の数字から指手生成回路のおよそ倍程度に規模が膨れ上がると(大雑把ではあるが)予想できる。


チェスと将棋では盤のサイズ(桝の数)が違うし、そもそもルールが異なる。まず最初に、チェスの指手生成回路を将棋へ適用を考える場合に考慮すべきゲームのルール差を箇条書きする。

--
・チェスより将棋の方が複雑になると考えられる部分
 + 将棋は持っている駒を盤上に打てる。従って、取った駒を管理する必要がある
  + ニ歩の禁手を避けるために、先後共に盤上の筋毎に生歩の存在を検出する必要がある
  + チェスには打歩詰(禁手)の概念がない
  + 打歩詰に関しては、探索によって判定する必要がある(静的な判定が困難なのでFSM側で対処)
  + 静止探索では通常駒を盤上に打つ手を生成しないが、将棋では王手が掛かっている場合ありえる
  + 勿論、静止探索に入る以前では「駒を盤上に打つ手」は普通にある
   + 従って、手番側の持駒にどのような駒種があるかを各桝へ知らせるバスが必要になる
 + 将棋では、歩香桂銀角飛が敵陣に入る(あるいは敵陣から出る)時に、不成か成かを選択できる
+ 行き所のない駒を作る手は禁手なので、その判定が出来るようにする必要がある
 + また、チェスには金銀香歩および竜や馬に相当する駒はなく、成駒を含めると駒種が多い
+ 従って、駒種に基いて利きを生成するデコーダが、将棋では複雑になる

・チェスより将棋の方が単純になると考えられる部分
 - チェスのポーンの動きと利きは、将棋の歩と似て非(チェスの方が複雑)
  - ポーンが初期位置から2つ前進するような手は、将棋の歩にはない
  - また、前方に駒がある時、ポーンは進めない(敵駒であっても取れない)
  - ポーンは前方斜めの敵駒を取れるが、歩にはそのような手はない
 - 同様にアンパサンやキャスリングのような手は、将棋にはない
 - チェスのナイトと将棋の桂馬は利きが異なり、ナイトの方が利き伝搬が複雑になる
 + チェスでは、成れる駒はポーンのみで、敵陣最上段で強制的に成るのみ(このこと自体は単純)
  - 但し、キング以外の好きな駒種に出来るという将棋にはないルールがあり、この点チェスの方が複雑
 - チェスの静止探索では、駒を取る手だけでなく王手も読みに含めている[*2]
--

盤の大きさが異なる点については、チェスでは8x8の64、将棋は9x9の81桝なので、単純計算で将棋はチェスの約(81/64)1.3倍の規模になると考えられ、更に将棋では持駒を管理し、それを各桝に伝えたり、二歩禁検出の必要がある分、付加的な回路と配線が増える。また駒種については、各桝で駒値を管理するFF(レジスタ)が1ビット増えるだけではあるが、駒の利きを生成するためのデコーダはおよそ2倍の規模になると考えられ、付け加えてMVV/LVA[*3]の演算も複雑になる。これらを総合的に考慮すれば、将棋の指手生成回路の規模は、チェスの場合の1.5倍程度には膨れ上がると推測できるし、更に指手の生成条件や生成順序を精密に制御したい、あるいは高速化したい場合(後述)は、2倍近くかそれ以上を覚悟する必要がある。


ここで、動作速度への影響を考えてみる。MarcのMoveGeneratorに限らずDeepBlueにしろHydraにしろクリティカルパス(重大な遅延路)は、生成する手の移動先・移動元の桝を決定するためのアービタ[*4]の性能に大きく影響される。チェスでは、64個の桝の一つを選択するために2分木6レベル、63個のアービタを使用する。これを将棋の指手生成でそのまま用いると2分木7レベルとなり、1レベル分チェスより時間コストが増えることになる。3分木アービタを独自に作れば(34=81なので)4レベルとなるが、3分木アービタは2分木のそれの3倍の回路規模となり、やや遅延が増えると思われるので効果があるかどうかは判らないが、3分木アービタを試してみる価値はありそうだ[*5]

-- 続く --


[*1] どうやら、DeepBlueの論文(の一部だが)「F.-H. Hsu, "A two-million moves/s CMOS single-chip chess move generator," IEEE Journal of Solid -State Circuits, vol. sc-22, no. 5, 1987, pp. 841-846.」を読んでいるようである。ChrillyやMarcの論文を読むと、常にこの参照が出て来る。

[*2] これはDeepBlueは勿論、MarcのMoveGeneratorでもそうなっている。Chrillyの探索コアについては不明。チェスでは、駒を取る手だけでなく、王手も「非常に重要な手になる」と考えられる(チェスプログラムでは、王手が掛かっている局面では必ず延長して探索しているのが殆ど)。例えば、王手クイーン取りといった両取り一発で勝敗が決定的になることが多いからではないだろうか。

[*3] Most Valuable Victim / Least Valuable Aggressor の略。一言でいえば、交換値のこと。

[*4] Marcのソースでいえば、arbitor.vhd。2分木アービタ1つ分の「部品」がVHDLで記述されている。

[*5] 例えば、1回の2分木の遅延が1.0nsなら7レベルで合計7.0nsだが、3分木の遅延が1.5nsで済めば4レベルで6.0nsとなり、ロジック資源を大きく喰うものの、多少なりともfmax(最高動作周波数の意)を上げることが出来る(あるいは犠牲にせずに済む)。

State of the FPGAs

テーマ:

現在最強のFPGAについて、諸元も含めてここにメモしておく。


・Altera : StratixII EP2S180

71,760ALMs, 143,520ALUTs(179,400LEs), 9,383,040bits(BlockRAM total)=9,163Kbits
・Xilinx : Virtex4 XC4VLX200

89,088Slices, 200,448LogicCells, 6,048Kbits(BlockRAM)+1,392Kbits(DistributedRAM)=7,440Kbits


これらは、どちらもChrillyの探索コアなら8個は入る規模、最高のスピードグレイド品なら約2倍の速度で走らせる[*1]ことが出来るFPGAだ。極論を書けば、2個あれば現Hydraと同等程度の性能が出せる(8cores×2倍速×2個で、32coresと同等になるという意味で)。但し、1個の部品単価はロット(1000個単位)で買ってもOpteron並に高価なものである。

余談だが、互いに白書(WhitePaper)で殴り合いをやっていて面白いので、それも以下に残しておく。ハード屋にとっては意味がよく判り、なにやらニヤリとしてしまう内容だ。


Altera : StratixII vs. Virtex-4 Density Comparison
Xilinx : Power vs. Performance: The 90nm Inflection Point


要約すると、Altera曰く「ウチのFPGAは、XilinxよりLUTのアーキテクチャが優れているので、大規模且つ高速な回路が作れる」とし、Xilinx曰く「ウチのFPGAは、Alteraよりノイズが少なく低消費電力で熱が出にくく高クロック動作でも安定して動く」と主張しているわけである。

このように、名指しで他社製品と比較して公表する真似は、日本ではあまり品が良いものとは言えず余程のことがない限りやらないが、アチラでは日常茶飯事である。だとしてもこれらの白書はかなり過激で、それだけFPGAビジネスが大きく成長しつつあるという事を示している。


[*1] 因みに、現Hydraで使われているVirtexIIPro VC2VP70-5は、スピードグレイド最低ランク品である。なお、このグレイドが1つ上がると約10%高速化する。AlteraもXilinxも1つの品種で3ランク程度用意している。

Hydra考 (5)

テーマ:

DeepBlueにしろHydraにしろ、探索速度(レート)を稼いでいる要はハード探索に因るものであってソフトは単にその支援を行っているに過ぎない。しかしながら、だからと言って根ノードからハード探索を行って効率を上げられるのかと言えばそうはならない。恐らく根ノードから行えば、どこかの深さでソフトとハードの「実効=速度と効率の積」が逆転する。まずハード探索では厳密な置換表処理が(出来なくはないだろうが)難しいし、特定の手を延長して探索するといったことも簡単ではなく、探索する手のオーダ制御も同様だ[*1]。それが出来るのか出来ないのかどっちなんだと言われれば「FPGAのリソースが許す限り可能」なのだが、それだと今度は速度が犠牲になってしまいかねない。それらの平衡を保ちながら、最終的に「最も高い棋力を得る」ことが目標になってくる。


さて、DeepBlueの稼動率の悪さは、CPU間通信オーバヘッドとソフト探索側でのハード探索コアの利用の拙さが主原因と思われる。特にDeepBlueの場合、1個のCPUが16個のコアを使用できる仕様になっているが、単に「固定的な深さのノードでしか並列化してない[*2]」のなら、Chrillyの言にもあった通り、高い稼動率を望めない。並列αβ探索で効率を上げるコツは、「(NegaMax表現で)α値が決まっていて、且つβ値が決まっていないノード」部分を並列探索することにある。α値が決まってない(1番目の手を未だ探索してない)ノードでは、他の枝の枝刈が起きにくく無用な探索を行う可能性が高くなるし、β値が決まっているノードでは枝刈によって他の枝の探索が全く無駄になる可能性があるからだ。


またHydraの場合、ChrillyはPCIバスのボトルネックを強調している。これはPCIカードの仕様による制限か、ドライバの仕様に引っ張られて性能を上げられない、あるいは通信プロトコルが拙いのかも知れないが、何れにせよ稼動率を上げる余地は充分あるのではないかと感じている。そもそも論をぶってもしょうがないのだが、グラフ状ゲーム木を並列でαβ探索する場合、先の理由とは別にクラスタ構成では効率を上げにくい[*3]。各CPUが他のCPUと密接に連携して並列実行しないと無駄が生じやすい[*4]


更に、DeepBlueもHydraも、恐らくCPUから探索コアに対して探索依頼を行った後、その結果がコアから返って来るまでCPUはアイドル状態になっているだけだと思われる。その時間資源を使って「2つ目以降のコア」を効率的に使うために、別系統のノードの探索を行わせて並列数を上げさせることも可能な筈だが、このあたりはChrillyにとっても今現在課題になっているのではないかと思う[*5]
理想的には、クラスタによる並列実行ではなく、少数のCPUであってもSMPによる協調処理の方が有力な筈で、各CPUが全ての探索コアに対して自在に制御できる構成の方が性能を落としにくいだろう。具体的な例を考えれば次の様になる。


左図は、各CPUが「待機している探索コア」を自在に要求して使用できるという仕様にしたものだ。間にマネージャが入るが、CPU側から見れば処理を依頼する相手はマネージャだけであって、Ready状態のコアをいちいち探す必要はない。マネージャから見れば、処理を要求しているCPU(あるいはスレッド)が誰であるかは、どのアドレスへアクセスされたかで判ることが出来るようにし、結果もそのアドレスから返すようにすれば混乱が起きることはない。マネージャが空いているコアを常時管理して処理を依頼し、コア側でその探索が終了すれば結果をマネージャへ引き渡し、マネージャが代行して依頼主のCPU側へ返すというわけである。更にフライングで探索依頼、または投機的に探索が出来るようにキューを持たせ、必要に応じていつでも探索をキャンセル出来る機能もマネージャ側に欲しい。以上のように出来れば、コアの稼働率を限界まで上げられることを期待できる。


この図は、4CPUs/8cores構成になっているが、FPGA側は8coresである必要はない。仮に32coresに出来るならば、現Hydraと大して変わらないかそれ以上の性能を実現できる可能性がある。CPU-FPGA間通信プロトコルを工夫した上で Memory mapped I/O にすれば、レイテンシはそれほど落ちるものではないし、少なくとも光ネットワークよりは遥かに速い。目指しているのは「車検が通るスポーツカー」ではなく、「サーキットのレコードを叩き出すフォーミュラマシン」なのである。私がもしFPGAを用いて探索を行うのであれば、試してみたいアーキテクチャの最有力候補としてここに記録しておく。


[*1] 例えば「前回の反復深化時の最善手から読む」といった細かな制御に対処しにくい。
[*2] Hydraのコアでは「残3手+静止探索」、DeepBlueのコアでは「残4手+静止探索」のようである。但し、DeepBlue場合、静止探索に入る前に延長処理が入ることもあり、固定的に4手全幅+静止探索というわけではないようだ。
[*3] 正確に言えば、元々の意味での「収穫逓減」が起き易い。
[*4] なお、NUMAの場合は各CPUのバスの利用(主にメモリアクセス)で互いが邪魔をし合わないようにするためのアーキテクチャだが、極端に大きなスレッドローカルストレージ領域が必要でないなら、NUMAであることが有利とはならない。

[*5] もしかすると、ある程度解決している問題なのかもしれないが、そのような論文が見当たらない。

Hydra考 (4)

テーマ:

ここでソフトとハードの良いとこ取りを目指したハイブリッド探索と、並列化の効率について考えてみる。なお、ここで示す数字は、あくまで時間あたりの表面的な探索量であって、それが棋力と直結しているか否かについては議論しないことにする。システムとして意味のあるハイブリッド探索および探索の並列化が行われているかを先に問うのが目的だからだ。

まず、DeepBlueIIでは、30個のCPUと480個の探索コアを用い、各CPUが16個のコアを制御していた。現時点でのHydraでは32個のCPUと32個の探索コアを用い、各CPUが単に1個のコアを用いるだけである。DeepBlueのコアは毎秒200~250万局面を探索するが、システム全体では毎秒1~2億局面[*1]で、実質的な効率は10~20%と公表されている。現Hydraのコアは毎秒約600万局面を探索する計算になり[*2]、単に32倍すれば毎秒約2億局面だが、システム全体で見た時の実稼動率を50%とすれば、毎秒1億局面程度の性能となる。

左の表は"The Chess Monster Hydra"から引用した。2プロセッサ時の効率99.7%については信憑性を問いたくなる[*3]ような数字だが、それは置いておくとして、4~8プロセッサ時の数字に着目すれば、約87%まで効率が落ちている。更に16、32、64プロセッサと並列数が増えれば、ますます実効率は落ちるだろう。これは主に通信オーバヘッドに因る。元々CPU-FPGA間通信で約20%のロス[*4]があり、CPUノード間の通信オーバヘッド(特にレイテンシ)は、それが光ファイバを使っていようと大きいし、またノード間で置換表を共用して並列探索を行っているわけではないので、無意味な重複探索を避けらない。それ以外にもプロセッサが遊んでしまう状況はいろいろある。そこまで考えれば、トータルの性能損失率は50%どころではないかも知れない。


余談だが、先のChrillyからのメイルによれば、Hydraは将来的に64CPUs/64FPGAs構成を計画しているようだ。現在使われているFPGAカード1枚にコアを2個以上載せるだけの資源があるので、再度128coresにして動かしてみたい気はする。Chrillyは「僅か10%しか高速化しなかった」と言っていたが、逆に言えばそのような構成で効率を上げる為の制御アルゴリズムが存在するように思えるからだ。

因みに、"The Hydra Project"によれば、現在、VirtexIIProのXC2VP70を用いていることになっている。このFPGAはslice数で最大33,088のプログラミングが可能なものである。Chrillyの探索コアは9,879slices、それを3倍しても29,637slicesなので「気合で3個のコア」を載せられそうだ。しかし、そういうことをすると一回の合成・配置・配線(言わばコンパイル&リンク)にまる一日を要したり、その配置・配線が変化してクリティカルパスの遅延時間が延びる[*5]といった思いもよらぬ事がいろいろ起きて、ますます破綻[*6]する事がある。

さて、最終形と思われる64CPUs/64FPGAs構成のHydraのハードウエア原価は(人件費を除く、全パーツ代という意味で)どれくらいになるだろうか。1つのデュアルノードが、2CPUs+2FPGAsで\1M程度、それが32ノードで\32M、32ノードの光ネットワーク=I/Fカード+光ファイバケーブル(これが結構高かったりする)+HUBのセットで\5M以上、周辺機器、収納ラック、その他もろもろを含めたコストをざっと計算して\40M前後ではないかと予想できる。\40Mといえば、Ferrari F40の(当時の日本での)新車価格であり、HONDA NSX-R 3台分である。DeepBlueの総製作コストの1/100以下かもしれないが、それでも個人では到底用意できる金額にならない。嫁に破門にされ、娘に勘当される覚悟があっても[*7]、借金してまで買う次元の物ではなさそうである。

全く話が逸れるのだが、自分の仕事がらHydraにはちょっと気にいらないところがある。それは消費電力だ。現Hydraですら5kWは喰っているだろうし、64CPU構成なら10kWに達するだろう。完全に京都議定書 を無視したようなシステムである。相手の感覚を破壊する一手を指せるかもしれないが、と同時に地球環境も破壊するように思えるのは私だけだろうか。

-- 続く --


[*1] '97のカスパロフ戦の最終局では毎秒3億5000万局面を探索したという話もあるが、ここでは論文中の数字を引用した。

[*2] 55MHz動作で、1ノードの探索あたり9クロックを要するものとして算出した。

[*3] これこそ「ロス疑惑」である。損失率0.3%というのは、低温核融合 の論文並に疑問符が付く。

[*4] これは "The Hydra Project" にも記述があるし、Chrilly本人もMLでそのようなことを述べている。

[*5] そういうことが良くある。ある程度「遊び」ともいえる空間的余裕が必要。詰め込み過ぎると、特に配線経路が変わり、無視できないほど遅延が大きくなることが起きるし、フロアプランニングも手間が掛かるようになる。

[*6] シミュレーションでは問題なくても、実際にはTDPが増えて熱で動かなくなるという落とし穴もある。

[*7] と言っても、娘以前に嫁を私は持ってない。

内藤先生からの挑戦状 (2)

テーマ:

数年振りに内藤先生から挑戦状が来た。「電脳は詰将棋を解くことにかけては神様の領域に近づいたが、必至については苦手としているのが面白い[*1]」 その挑戦状、確かに受け取った[*2]。以下に謎電の解図結果を示す。なお解図パラメタは{5,11}とし、Barton/3000+を用いた。


     解手数___解図時間_初手解_____________詰探索回数
  1番: 1手必    0.018秒o2三飛                     71
  2番: 1手必    0.015秒o3三銀                     61
  3番: 1手必    0.008秒o2一角                     77
  4番: 1手必    0.021秒o2一桂成                   98
  5番: 1手必    0.018秒o4一角                     95
  6番: 1手必    0.018秒o2四飛                     67
  7番: 1手必    0.022秒o3三角成                  109
  8番: 1手必    0.038秒o5一飛                    281
  9番: 1手必    0.002秒o3三飛成                   64
 10番: 1手必    0.001秒o1二銀不成                 61
 11番: 1手必    0.011秒o4三飛成                  162
 12番: 1手必    0.003秒o3三桂成                   61
 13番: 1手必    0.002秒o1四銀                     67
 14番: 1手必    0.002秒o2四竜                     61
 15番: 1手必    0.012秒o4三銀                     81
 16番: 1手必    0.004秒o3二金                     69
 17番: 1手必    0.008秒o7三銀                     63
 18番: 1手必    0.004秒o1二角                     64
 19番: 1手必    0.003秒o6四桂                     63
 20番: 1手必    0.033秒o6三香                     97
 21番: 1手必    0.008秒o2二銀不成                 61
 22番: 1手必    0.012秒o3三銀                     62
 23番: 1手必    0.007秒o3二飛不成                 91
 24番: 1手必    0.030秒o6四銀                     72
 25番: 1手必    0.006秒o8四桂                     87
 26番: 1手必    0.027秒o2四飛                     79
 27番: 1手必    0.057秒o3三銀                    126
 28番* 9手必   12.406秒o2五桂                 81,479
 29番: 1手必    0.013秒o1二飛                    360
 30番: 1手必    0.047秒o2三角                     65
 31番: 1手必    0.008秒o4二飛                     62
 32番: 1手必    0.009秒o3四桂                     72
 33番: 1手必    0.004秒o2四金                     61
 34番: 1手必    0.001秒o3四角成                   61
 35番: 1手必    0.026秒o4一角                     85
 36番: 1手必    0.038秒o8四飛                    136
 37番* 3手必    0.459秒o2三銀                    652
 38番: 1手必    0.031秒o2三銀打                   61
 39番: 1手必    0.001秒o4七銀                     61
合計時間:      13.433秒    合計探索量:         85,505

正答数: 39[問] (正答率:1000[‰]) 対象数: 39[問]


初手は全問正解だが、28番と37番は1手必至にならない。その理由を以下に示す。


左図は28番。解説では▲25桂までの1手必至となっているが、{5,11}で解図を行うと、以下▽63飛▲13桂成▽同玉▲14銀▽22玉▲32金▽11玉▲31馬まで9手必至となる。また、▲25桂に▽32銀と受けても詰まず、以下▲13桂成▽同玉▲24銀▽同桂▲32馬までの7手早必至となる。

私の実力では巧い修正案を見つけられなかった。
左図は37番。解説では▲23銀までの1手必至となっているが、以下▽54飛▲33銀まで3手必至となる。因みに▲23銀に▽44飛は、▲22竜▽24玉▲12銀不成▽34玉▲23竜までで受けにならない。

修正案としては、安直だが56に攻方の歩を置くことで、作意通りの一手必至になる。例えば、▲23銀に▽94飛でも▲22竜▽24玉▲12銀不成▽34玉▲23竜▽44玉▲45銀までで詰む。



[*1] 勿論、私が直接貰ったわけではない。将棋世界8月号の付録「内藤國雄の一手必至」から引用。

[*2] 自分宛というわけではないのに(というより挑戦状だと思う方がおかしいが)、もー完全にノリノリである。問題集チューニング派の悲しい業と言える。

別冊MultiCore ('05/07号)

テーマ:

皆さんこんにちは。別冊MultiCoreの時間です。


DualCoreではありませんが、Single最強のAthlon64FX57(2.8GHz)のbox品がリリースされました。実勢価格は\120k前後といったところです。恐らくFXは、Single版のまま需要がある限りは消えることはなさそうな気配で、半年後には3.0GHzに達しそうです。年間平均0.4GHzペースの上昇ですね。


さて、注目のAthlon64X2/4800+(2.4GHz/L2:1MBx2)ですが、即売り切れで入手困難な状況は今も変わらないようです。それ以外のモデルおよびOpteronのDualCoreシリーズの実勢は次の様になっていました。

--
4600+(2.4GHz/L2:512Kx2) : \100kを切る
4400+(2.2GHz/L2:1M  x2) :  \80kを切る
4200+(2.2GHz/L2:512Kx2) :  \66k前後
Opteron275(2.2GHz)      : \160k前後
       270(2.0GHz)      : \130k前後
       265(1.8GHz)      : \100k前後
--

なお、Opteron800番台DualCore品の実勢は全く判りません(汗)