計算機将棋関係者のみならず、少なからず世間で話題となった人間対計算機の平手の対局が9月18日に行われた。最先端計数将棋学で採り上げないわけにはいかないのだが、いかんせん計算機同士の将棋と異なり、人間側のインタビューを取りようがないので、解説が難しいところである。そこで棋譜中の各手の詳細については、私は専門家ではないので語らないことにし、個人的に思うところと謎電の解図内容のみ書く事にする。


結果として橋本五段の勝ちで、「そりゃそうだろうなあ」というのが正直な感想なのだが、棋譜を見て「序盤といえども計算機は侮れない」という印象を専門棋士の方々に持たせることが出来たのではないかと思うところである。そういう意味では、橋本博士、TACOSが負けたにせよ good job ですよ。次回から「専門棋士同士では使わないような手」は出てこないのではないかと。定跡形にせよ力戦手将棋にせよ、何か棋理に反しているような序盤から計算機が勝っても負けても、妙に納得がいかないような気もする。


さて、左図からの謎電の必至解図の結果は、▽38飛▲48金引▽同飛成▲同金▽88飛までの5手必至。余必至として手順前後が成立し、▽38飛▲48金引▽88飛▲同角▽48飛成もある。本譜は、▽18飛▲48金引▽同飛成▲同金▽66香だが、これでも必至で、仮に▲78飛(58飛、98飛でも同じ)と受けても▽68金以下27詰がある。もしこの27手の詰手順を橋本五段が読んだ上での▽66香ならば、専門棋士というのは恐ろしいものだと思う。実際どうなのかは不明だが、感覚的に「詰がありそうだ」と感じただけだとしても、その方が怖いかもしれない。TACOSは王手ラッシュぽい手を見せているので、それを読み切っていたと思われる。


なお、謎電が▽88飛の手を解としているのは、単に少ない探索量(解図パラメタが小さい、という意味)で解けているからである。


(追補) よくよく図を見れば、橋本五段が指された▽66香は自陣への敵角の利きを遮断しており、実戦的な必至の掛け方の手本と言える。▽66香が必至上がりだと確信した上での手なら、終盤といえども人間は侮れない?

AD

謎電は、読み落としなく読むことを目指していた。飽くまで目指しているだけで、全幅探索というわけではない。元々終盤局面解析が目的であったので、読み落としがあるとその意味をなさなくなるからである。しかしながら、指将棋で強さ(勝敗)を競うとなると、そういうわけにもいかなくなる。


現在の謎電の指将棋探索は、根局面とその直下の子局面のみ全幅ではあるが、その先は静止探索に入る手前まで全合法手の約半分程度の幅、静止探索では敵駒を取る手と自駒が成る手は基本的に(条件付きで)それらの手が無くなるまで読んでいるし、王手が掛かっている時は絶対的な1手延長を行っている。


しかしながら、どうもそういった「妥協なしの読み」が探索効率を悪化させているようである。オーダリング次第ではまだまだ改善できるとは思うのだが、恐らくトップクラスのプログラムと比べて探索幅で2倍近く違う筈で、以前書いたように、激指やYSSと比べて高速化に対する棋力向上の度合が相対的に低いのは、このあたりが主原因だと考えている。


「では何が強いプログラムとそうでないプログラムを分けているのだろうか?
・・・(中略)・・・ つまり将棋プログラムでは、
『探索範囲の制御』と『評価関数の設計』が強さの大きな鍵となる」[*1]


これはもう、全くその通りだ、とつくづく思う。「強いソフトは枝刈が巧い」と名文句を言ってたのは備後将棋の恩本さんだが、読む必要のない手を如何に刈るかの技術の差の棋力への影響は相当なものだと思う。マシンの性能が2倍違うとか4倍違うなんてのは微々たるもので、オーダリングも同じで読み落としが起きないことを前提とするなら、読む幅が違えば深く読む程、そのコスト差は複利計算的に姿を表すことになる筈だからだ。


多分、激指が10手先を読んでいる時に、謎電は7手先を読んでいる最中、という程度だと思う。謎電が10手先を読み始める頃には、恐らく激指は14手先は読んでいるだろう。となれば、持時間の長い将棋ほどその棋力差は広がる一方だ。更には、局面評価関数を含めて静止探索から得る探索値の精度も棋力に影響するわけだから、R換算で1000点以上の差になっても全く不思議でもなんでもないことになる。


R差1000点以上というのは途方に暮れてしまいそうな、というより絶望的といっても良いほどの棋力差で、二枚落の手合でも良い勝負になるかどうか疑問な差だが、柿木師匠に「激指を目標にしなさい」と言われたことでもあるし[*2]、そういうわけでR2500を目標にして、『探索範囲の制御』と『評価関数の設計』を再度一から作り直す覚悟でやりますので、鶴岡さん以下計算機将棋開発者の皆さん、よろしくお願いします...って、どこまで本気か疑わしい締め文句になってしまった今回のコラムである。

-- 完 --


[*1] IPSJ Magazine Vol.46 No.7 July 2005 p.818 (CSA資料集2005 p.32)より引用。

[*2] この時、柿木さんは酔ってたからなあ。社交辞令だよなあ。酔ってても死角なし。恐るべし柿木師匠!!

#社交辞令:世間付き合いを円滑にする為に用いる文句。

AD

謎電の思考エンジンは、基本的にショートストローク高回転志向である。動力のメカ的な摩擦損失に相当するオーバヘッドを極力減らし、明らかに無駄な処理を完全に省き、部品レベルの研磨においては十二分に施し、Barton/3000+でも毎秒Over100万局面を達成出来ている。しかし、それでもSPEARに勝てない。何故か?


「以前は部分的にアセンブリ言語で書かれたプログラムも存在したが、

現在ではさすがにそこまでしているプログラムはほとんどない」[*1]


すみません、謎電はインラインアセンブラ、バリバリ使ってます(汗) ただでさえ少ない開発持時間を、そういうところのデバグで費やしてしまっていること自体が、開発者最大の悪手で、はっきり敗着ですか。


「もう1つの理由は、量が質にダイレクトに結びつくという性質である」[*2]


これをエンジンに例えるなら、質がトルク、量が(単位時間あたりの)回転数に相当する。出力[W]=2π×トルク[N・m]×回転数[rpm]÷60[*3]だが、謎電の場合、トルクが非常に細く回転数を上げても殆ど棋力を搾り出せていないことが判っている。


「激指ではそのような問題を避けるために、序盤・中盤・終盤であるかの判定は

1つの連続的な数値で行うようにしている」[*4]


トルクが出ない直接的な原因は、低負荷高回転~高負荷低回転のほぼ中間あたりのバルブの開閉タイミングが合ってない上に、無段階バルブタイミングではないことが挙げられる。次回選手権までには、各回転数と負荷に合わせて最適なバルブタイミングを自己調整できるように改造を施そうと思っている。

と、こう書くと何の話なのか訳が判らないので要約すると、結局「進行度に合わせた局面評価が行われていない拙さ」が問題であるということだ。特に序盤でも終盤でもない、中盤の評価がおもいきし変になっていることが最近判った。中盤でありながら序盤とみたり、逆に終盤と見たりすることが、相当高い確率で起きている。勿論序盤そのものに関しても相変わらず課題は多いのだが、前回よりは多少時間を掛けて改善しようと思う。

-- 続く --


[*1] IPSJ Magazine Vol.46 No.7 July 2005 p.821 (CSA資料集2005 p.35)から引用。

[*2] IPSJ Magazine Vol.46 No.7 July 2005 p.822 (CSA資料集2005 p.36)から引用。

[*3] 因みに、8,000rpmの時に10kgf・m(98N・m)のトルクを出している時が最高出力となるエンジンは、2π*98*8000/60≒82,100[W]で、1[ps](仏馬力)は735.5[W]であるから、約111.6[ps]となる。

[*4] IPSJ Magazine Vol.46 No.7 July 2005 p.820 (CSA資料集2005 p.34)から引用。

AD

セルフプレイテストってのはあまりアテにならんことは、昔からよく知られていたことで、謎電同士の対局でも配分時間を4倍変えて(例えば、1手5秒と20秒)対局させると、全くお話にならないくらい勝率に差が出るわけです、この場合1:9位。なので、探索速度(レート)を単に上げる改造を施すだけで、なんだか明らかに強くなった気がするわけですが、実際にはそれほど強くなってるわけじゃないんですね。


「3倍の高速化によってレーティングで約100点上昇というのが筆者の個人的な見積りである」[*1]


ここでは山下さんの実験結果の引用もありますが、謎電的には約4倍で+100点(非セルフプレイ)という結果で、これは謎電の探索効率が激指やYSSより悪いことを示している気もします。探索効率が良いプログラム程、高速化による棋力向上は大きい筈。具体的には探索する手の刈り方(探索幅)や、そのオーダリングあたりの善し悪しがモロに出るのではないかと。

さて、計算機将棋開発者として長年(笑)やってきて、ここまでチビシーことを言われたのは初めてである。


「弱いものをいくら速くしても弱いままだ」[*2]


ええ、そうですよ、そうですとも。でもね、でもね~、人の心の傷口にワサビを塗りつけるようなこと言って楽しいですかっ?ええ?? と、思わず開き直る謎電の作者。

いやー、かなり痛いところを突かれましたね。正論で返す言葉がないですね。実際謎電は24のRで1400位なんですけどね、16倍速く出来て+200強くなったとしてもR1600、256倍でもR1800という計算になりますからね。もっと根本的本質的な改善が必要なことは判ってるんです、もー余計なお世話ですよ(泣)

ほ~んと、そのあたりどうにかしないとハード探索やったところで高々知れているわけで。具体的には謎電がソフト探索のままで、最低でもR2200位に達し、且つ10倍の高速化で+200点上昇するくらいまでにならないと、FPGA使う気にもならないわけですね。それでも100倍速く出来てR2600ですが。

-- 続く --


[*1] IPSJ Magazine Vol.46 No.7 July 2005 p.822 (CSA資料集2005 p.36)から引用。

[*2] IPSJ Magazine Vol.46 No.7 July 2005 p.815 (CSA資料集2005 p.29)から引用。

CSA資料集 2005

テーマ:

今日(正確には昨日の夕方)CSAから資料集が届いた。ので目を通していたら、こういう時間になってしまった。そこにある学会誌・新聞記事の殆ど全部を読んでなかったので、こういう資料集は結構重宝な気がするし、コレだけでCSA会費のモトを取ったような気がするから不思議だ。何と言っても(激指の開発メンバのひとりである)鶴岡さんの書かれた記事は、的確・明瞭・簡潔な上に平易で説得力もある文章には毎度のことながら感心してしまう。いろいろ面白いネタが転がっているので、これから一時期は、そのあたり私なりに感じるところを散文詩的に書こうと思う。

KFEnd

テーマ:

全世界三千万人の計算機将棋ファンの皆様こんにちは。計算機将棋研究一筋八十余年の謎電の作者です[*1]。今回は、あの「1位・2位を撃破した将棋プログラム」をdefeatしたKFEndをご紹介致しましょう。


はっきり言って謎電最大の好敵手である。いや、強豪であり難敵と言った方が正しいかもしれない。SPEARは勿論、KFEndに勝つまで私は計算機将棋開発者であることを辞めないつもりでいるのだが、今のところその実力差は、実績を見れば歴然で比較しようもないところである。しかし、少しづつながら近づきつつあるので、後ろから追いかける側というのはダウンヒルバトルと同様、楽しみが多いところであると思っている。


と言いながら、作者の有岡さんとは(ほとんど無理矢理)親しくさせて頂いているし、またお世話にもなっている。ので、個人的なことについてはここでは詳しく書かない。多くの開発者が、ABC探索を語らせればMcAllesterの右に出るのが有岡さんだと言っても過言ではないほど只者ではないことを認めるところではないだろうか。それは "Inside KFEnd" を読まれたことのある殆どの方がご存知だと思うところである。但し極く一部、具体的には少年A(特に名を秘す)を除く[*2]


KFEndの魅力は終盤力である。それは一言でいえば、谷川にも似た踏み込みの良さにある。「コンピュータ将棋や囲碁の掲示板」に勝又先生からよせられたコメント(2000/03/16)から判るように、専門棋士ウケするほどの棋風だ。以前、「川端将棋-KFEnd戦に見る名手 」でも書いたが、例の▽53飛を私はリアルタイムで見ていた。その時、丁度勝又先生がこの将棋を解説されており、▽53飛にいたく感心されていらっしゃったのを良く覚えている。恐らく掲示板でのコメントは、この将棋の事を特に指されているのではないかと思うところである。


また、2003年の第13回選手権二次▲KFEnd▽TACOS戦でのKFEndの終盤力を、「佐藤(康)ばりの寄せ」と称されたのは飯田先生である。この将棋の103手目▲14歩から7手必至[*3]を掛ける時、KFEndはほぼ消費時間0で読み切っている(記録上は1秒だが、それはルールなので)。


さて、「あっ」と一言叫んで心臓が1.5秒くらい止まる程個人的に感動したKFEndの将棋を改めて紹介する。左図は、第11回選手権二次▲竜の卵▽KFEnd戦。53手目に竜の卵が78にいた金を79に引いたところ。恐らくこの手は疑問手だが、ここでKFEndが指した次の一手には心底タマゲた。これ以上に絶対的に速い手はないと思えたからである。


▽66角!!


この手が指し過ぎか否か、私ごときでは判断不可能である。しかしながら私にとっては、その手順は魂を揺さぶる魅力的な寄せに見えた。勝負は過程ではなく結果であるとするなら、▽66角こそが「最短の勝着」と言える手であり、谷川の「光速の寄せ」を凌ぐ「タキオン[*4]の寄せ」と称したいところだ。KFEndと比べれば謎電の終盤力は、まだまだターディオン級である。


54手目▽66角以下、▲同金▽77銀▲同桂▽同飛成▲89玉▽97桂打▲同香▽同桂不成▲98玉▽79竜と僅かに10手進めて左図だが、もうこうなるとどうにも凌ぎようがないように思う。最後は、▲97玉に▽95歩以下3手必至。本譜は詰め上がりまで含めて74手で終っている将棋である。図の左右を見比べれば、如何にKFEndが一方的に攻めたかが判る。


ところでKFEndには「3年に一度決勝へ行く」というジンクスがある。第8回デビュー以来、第10回、第13回、と3年周期で決勝へ進出している。次回は第16回で、その3年周期に当たる年だ。そういった意味からも、かなり気合が入った改良が加えられた上で参戦されるであろうと予測できる(などと書いて開発者にプレッシャ~を掛けてみる)。

選手権では敵だとしても、今後の活躍が楽しみな将棋プログラム[*5]である。また、敵ながら天晴れ、という手を観せて頂きたいと思っている。


将棋を指している時、投了図が見えるらしい。その時確信したよ。コイツは誰よりも寄せが速くなる(笑)


[*1] 西暦2060年頃に、入れ歯ガタガタいわせながら、そう言ってみたい気がする。
[*2] "Inside KFEnd" を読んで眠くなった、と当人の前でのたまった、恐らく唯一の計算機将棋開発者。
[*3] 後手最後の▽11香を無駄受けとするなら5手必至。余談だが、この将棋は互いに1手25秒か1秒消費で殆ど指しているところが面白い。
[*4] タキオン(tachyon、ταχύς=ギリシャ語で速いの意から)とは、超光速で動くと仮定する素粒子。名付け親はアメリカの物理学者ジェラルドファインバーグ(Gerald Feinberg)。どんなに減速しても光速度以下にならず、そのような素粒子は現時点でも発見されていない。因みに、質量0で真空中を光速運動する粒子をルクシオン(luxon)、正の実数の静止質量を持ち真空中を光速未満で運動する粒子をターディオン(tardyon)と言う。全く蛇足だが、チェレンコフ効果は、真空中ではなく触媒(物質)中で荷電粒子の速度が光速度(光は、真空中では約30万km/sだが、例えば水中なら約22.6万km/s程度)より速い場合に起きる発光現象のことである。

[*5] なお、「KFEnd」というのは、当初の棋譜編集プログラムに詰、必至などの終盤用のルーチンを加えた時点で付けた名前で、KFEnd = KiFu editor and END game analyzer の略称だ(プログラマーズノート より引用)。

YSS

テーマ:

謎電が第7回選手権に初出場した年に優勝したプログラムがYSSである。であるが故にその時の事を良く覚えている。但し、残念ながら今日までYSSと対局したことは一度もない。2度に1度は決勝シード組であるYSSは、あまりに強過ぎて組み合わせに当たるチャンスが殆ど無いからである。しかし逆に言えばYSSに当たったことがないというのは、それだけ謎電は運が良かったのかもしれない。


余談だが、YSSの作者である山下さんは囲碁プログラム彩の作者でもあり、私の廻りではこちらの方が有名だ。理由は私が宮崎に住んでいるからで、宮崎では将棋より囲碁の方が圧倒的に盛んであり[*1]、彩がフリーウエアだからというせいもあるだろう。これは話し出すと結構長くなるし計算機将棋とは全く関係ないので機会があれば改めて書きたいと思う。


さて、その山下さんの計算機将棋開発者に対する影響は計り知れないものがあるのではないかと思っている。特に「コンピュータ将棋の進歩2」においてのYSSの詳細なアルゴリズム説明と具体的なパラメタデータの公開は、前にも後にも山下さんが群を抜いているのはないかと思う。また「YSSと彩のページ」及び「コンピュータ将棋や囲碁の掲示板」を通しての継続的な活動は誰にも真似の出来ないところで、最先端計数将棋学的にも貴重なネタの宝庫である。HPや掲示板で、時々山下さんが公開される統計データ等について、こちらでも追試したり自分の持っているデータと照らし合わせてみたりするのだが、極めて信憑性の高い情報であることが確認でき、やはり一流の開発者というのは一味違うことをやってるものだなと感心することが多い。


残念なのは、YSSは謎電の好敵手と呼ぶには実力差があり過ぎて語りようがなく、そもそも公式対局がないことである。恐らく、24のR換算で言えば1000点前後の違いがある筈で、これはそうそう簡単には埋まらないと思っている。研究の差、努力の差、掛けている時間の差が、それぞれそれなりに大きいとは思うのだが、結局は「計算機将棋に対する情熱の差」がプログラムの棋力に直結しているのではないかと、山下さんを見てて感じるところである。謎電の場合は、「計算機将棋に対する」というより「将棋の終盤分析に対する」という局所的目標に特化させている。これを大きく広げないと、「YSSの敵に非ず」のまま謎電は引退を余儀なくされてしまいそうだ。


山下さんに対しては失礼な書き方になるが、YSSは第15回選手権で決勝シードを失う4位であった。次回選手権は、余程の事がない限り二次予選からなので、対局が出来るチャンスが少なからずあることになる。たとえ大差で負けることになるとしても、私にとってYSSとは一度は公式戦で対局してみたいプログラムの一つである。


最後に、印象に残っている第7回選手権決勝▲金澤将棋▽YSS戦から、謎電での解析結果を以下に書く。


左図は、117手まで進んだ局面。▲19桂は馬取りになってはいるが後手玉に詰めろが掛かっているわけではなく、ここで先手玉に必至を掛ければ勝ちというところだ。結論を書けば、▽79銀▲77玉▽84桂までの3手必至。▽84桂は▲同金と取れない(▽75香以下の簡単な詰がある)し、▲85金と歩を払っても同じく頓死なので、最強に受けて▲86歩と玉の逃げ道を作っても、▽59角▲68銀▽76歩以下17手詰がある。

本譜の後手は▽18馬と一旦逃げ、ここから十数手の間先手の相手をすることになるのだが、これは残り時間が既に少ない状態であった(当時は30分切れ負けで、この時YSSは約25分を使っていた)し、そもそもマシンの性能を考慮すれば、これを読み切るのは厳しかったと思われる。

もし今のYSSなら、この3手必至を読み切れるとなれば、謎電がいくら終盤に自信を持っていても、もうどうにもならない差がある気はする。分析は出来ても実戦(配分1分)では指せない手順だからだ。


[*1] ご存知の方も多いと思うが、宮崎は盤も石も「世界的に有名な」産地である。特に蛤(ハマグリ/clam)碁石はメキシコ産を除けば日本では宮崎県日向市だけでしか作られていない。

TACOS

テーマ:

今のTACOSは、もー手が付けられないくらい異常に強いらしい。『激TACOS』とプログラム名を変更するんじゃないかという勢いがある。第15回選手権では決勝まで進んで6位だが、今は24のR換算で2500には達しているのではないかと思える程の怖い存在だ。


謎電にとって好敵手とは既に言えない雲の上の存在になりつつあるTACOSだが、7年前の第9回デビュー当時は一次予選すら突破できない程度でしかなく、私の印象では、計算機将棋に興味がある学生が趣味で作ってる、というものだった。しかしながら第13回選手権頃に大ブレイクしたのにはちょっと驚く。トータルの順位を見れば、第9~12回の4年間は謎電にアドバンテージがあったが、第13回で一気に追い抜かれてしまったのである。


さて、ここで謎電の過去の栄光を自慢することにする(笑)


TACOSと謎電の初対局は、非常に印象深く良く覚えている。TACOSが初めて一次予選を突破し、二次に現れた第11回選手権の時の事だ。その二次の最終戦(9戦目)、その時点でTACOSが1勝6敗1分、謎電が2勝6敗と最下位を争っている状況。その差が0.5ポイントしかなかった。因みに当時、私は飯田先生を良く知らず、そもそもお顔を存じておらず、背広を着ていらっしゃったので、正直「どこのオッさんか?」と思っていた[*1]


対TACOS戦が始まる時、そのオッさんに「一局教えて頂けますか?」と挨拶されてしまった時には、「いえー、教えるって程のものではないですよ、私のプログラムは」と返したのだが、「いやいや、謎的電棋さんは先輩ですから、是非教えてください」と繰り返されるので、一次突破組にそれほど負ける気がしてなかった私は、「判りました、0.5勝差がどれだけ大差であるかをお教え致しましょう」とトンでもない返事を本気で言ってしまったのであった(実話)。


恐らく、飯田先生もこの返答にはビックリされたのではないかと思う。でも、何故か負ける気がしなかったんですよ、なんとなく。 といったことがありながらも、対局中はオッさん同士でその将棋の話が弾むわけで、左図は、76手目に謎電が▽38銀と指したところ。そう、この時であった。そのオッさんの口から、次の一言が飛び出る。


「この手は専門的に観て損だな~」


なんと、職業棋士独特の云い回しが。無論、この時のオッさんがプロ棋士だと知らない私は、この言葉の意味をちょっと考え込んだ。非専門的に見ても駒の働きが悪く疑問手に見えるし、口癖なのかな~、とか呑気に思っていた。結局真相は懇親会の時まで知ることなく、局面は進んでいったのだった。


結果この将棋は、その年の選手権二次最下位を謎電がTACOSに譲った一局となった。人間として、いや計算機として、譲り合う心の大切さを知った、貴重な対局ではなかったかと思う。


TACOSとの対局はこの一局だけである。実力が大きく異なるとなかなか当たらないのだが、出きれば来年あたり、もう一度対局したいと思っている。その為には私の方が相当努力しなければならない状況になっていることは言うまでもない。


[*1] なお、飯田先生と私は同じ年の生まれである。従ってどっちもオッさんなのだが、どっちかというと私の方が若く見えるよね、ね、ね。

別冊MultiCore ('05/09号)

テーマ:

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

やっと64X2/4800+のタマ数が安定してきたようです。先週頃から予約なしで買えるようになったみたいですが、まだイマイチ高い。また3800+という廉価グレイドも出ているようで、これは激安PentiumD対抗の為でしょう。

--
                                      ('05/07時点)
4800+(2.4GHz/L2:1M  x2) : \110k前後
4600+(2.4GHz/L2:512Kx2) :  \85k前後   (\100kを切る)
4400+(2.2GHz/L2:1M  x2) :  \66k前後   ( \80kを切る)
4200+(2.2GHz/L2:512Kx2) :  \58k前後   ( \66k前後)
3800+(2.0GHz/L2:512Kx2) :  \43k前後
Opteron275(2.2GHz)      : \135k前後   (\160k前後)
       270(2.0GHz)      : \120kを切る (\130k前後)
       265(1.8GHz)      :  \90kを切る (\100k前後)
--
約2ヵ月前と比べると10~15%OFFという感じです。

局面更新の高速化

テーマ:

先月、コンピュータ将棋や囲碁の掲示板でも書いた話なのだが。局面更新処理[*1]の高速化が探索レートに大きく影響することは、恐らく計算機将棋開発者の殆ど全員が気付かれているのではないかと思う。一度でもプロファイラを使ったことがあれば必ず気付く筈だからである。私も例外でなく、10年以上前にプロファイルを取った時は、局面更新が全体の4割前後を占めて極めて重いことを知り、その対策が最大のテーマになったことが何年にも渡って続いた。


もともと謎電は、486DX2を使っていた時代に(置換表なしで)ノード当たりの詰探索コストが約4,000[clocks]程度であることは判っていた。その後、初代Pentium時代(この時も置換表なし)で2,500[clocks]位、その時に初めてプロファイラを使い、局面更新が1,000[clocks](40%)前後喰うことを知った。この部分を速く出来れば数割は高速化可能だと踏み、今日までに5回、局面更新処理のデータ表現・構造も含めてコードを書き直している。


その間に置換表の実装や探索する手のオーダの強化によって一時的に(探索効率は上がっても)探索レートが落ちたりもしたが、結果現時点では、Barton(AthlonXP)でノード当たり1,450[clocks]、内局面更新が平均220[clocks]まで軽減。こう書く局面更新だけ見て約4~5倍速くなったことになるが、CPUのアーキテクチャが異なるので実際には3倍程度ではないかと思う。


結論を書けば、やはりデータ表現の工夫がポイントで、高速化のコツは、「条件分岐命令を極力減らす」ところにあると感じている。486以降のCPU[*2]は、内部処理のパイプライン化によって高速動作させるアーキテクチャになっている。条件分岐命令の実行時に、その分岐予測が外れるとパイプラインの段数にほぼ比例したストールを起こしIPC値が悪化する。従って、分岐予測がヒットし易いようにするか、あるいは条件分岐命令そのものが極力生成されないようにコーディングすることを心掛けるだけでも相当の高速化が可能になる。つまりは条件分岐命令を減らす為のデータ表現が重要になってくるわけだ。勿論、処理量そのものを減らすアルゴリズムを見つけ出すことも大切だが、ここで言っているのはプロセッサの特性を考慮することも重要だということである。


最近の謎電では、局面更新より寧ろ指手生成の高速化にテーマが移りつつある。特に詰探索の指手生成は、指将棋のように他のノードから手を借りてくるような融通が利き難いし、手の優先付けまで考慮すればかなり重い処理になってしまう。因みに現謎電の「王手+応手生成コストの合計」は40%前後(ノード当たり約600[clocks])に達している。これはオーダリングと打歩詰を除く指手の合法性(主に自爆)判定処理を含めているせいもあるが、とりあえずこの部分で2割の削減を目標にして、今月はソースを読み返して改良を検討してみようと思っている[*3]


[*1] ここで言う局面更新処理は、駒の利きの更新を含んだ移動処理を指している。置換表実装後は、盤面のハッシュキー演算処理や、(置換表への)メモリプリフェッチ処理なども含む。

[*2] 因みに、i486と初代Pentiumは5段、MMXPentiumで6段、Prescott(Pentium4)に至っては31段パイプラインである。9段と言えば名人の段位だが、プロセッサにおいては節操がない。

[*3] 謎電の序中盤力がなかなか改善しない原因は、このように作者が詰探索に異様に手を入れ過ぎているためである。それ以上に、GUIや足廻り系に拘っているのも大問題なのだが。