静止探索は、主に駒の損得を重視した探索になる。駒の損得は、書くまでもなく駒の取り合いで発生する。つまりは盤上の自駒が動いて敵駒を取るか、その逆に盤上の敵駒が自駒を取る、といった着手に因って起きる。場合によっては、駒を取らずに単に「成る手」も読みに入れることもあるが、盤上の駒が動く手のみに注目して手を生成し探索を行うことになる。

単純な静止探索は、争点(駒の取り合い点)をある1つの桝に絞って探索を行う[*1]。これは探索コストが少なくて済むが、得られる探索値の信憑性が低くなる。少し工夫した静止探索では、互いの手番で取れる駒全てに着目する。更に工夫された静止探索では、相手に手番が渡った時の損を加味したり、駒が詰まされているかどうかまでチェックするものもある[*2]。

一般に静止探索中は(特に取られそうな)駒が逃げるとか、持駒を打って(取られそうな駒に)紐を付ける、といった手は読まない。そこまで広く読んでしまうといつまで経っても探索が終端しないので、ある意味妥協した探索となっているわけだ。

チェスの場合は駒を打つ手はないが、将棋の場合「持駒を盤上に打てる」というルールが非常に曲者で、静止探索の中で読み落としが膨大に起きることになる。駒を打って両取りを受ける、といった手を読まないために損しない局面であっても、損すると判断してしまうこともあるわけだ。また逆も起こり得る。

駒を取る手がないか取っても得にならない時、そこで探索を終端して静的局面評価関数を呼ぶことになる。場合によっては駒がぶつかり合っている局面でも強制的に評価しなければならないこともある。そのような場合、例えば質駒をどれくらい持っているかが重要な評価対象となる。これは将来に現れると思われる潜在的な得(あるいは損)を評価するという意味だが、このあたりは各開発者が企業秘密ではないにしても、公開しにくい。

そのような「潜在的価値」は線形的な予測が出来ないため、未だ試行錯誤で調整しているというのが現状だろう。実際、僅かなパラメタ値の設定の違いで、棋力が大きく変化する。静止探索および静的局面評価には、そういった問題が多々あるが、であるが故に計算機将棋の中の極めて面白いテーマの一つだ。

[*1] 俗にSOMA(ソマ)と呼ばれる。語源不明。
[*2] Inside KFEnd静止探索は、極めて凝った手法になっている。
AD
静止探索[*1]とは、一言でいえば「先読みの末端で行う探索」のことだ。例えばある深さまで先読みを進め、駒がぶつかり合っている状態で評価しても(駒の取り合いが多い局面ほど)大きな誤差を持つ評価値しか得られない。そこで、その誤差をなるべく小さくする為に、駒の取り合いがなくなる局面まで延長して先読みするのが静止探索の役目である[*2]。

静止探索の手法は奥が深い。アルゴリズム的には似ていたとしても、恐らく選手権参加者で誰一人として同じ探索結果にならないだろう。これは勿論、静止探索の末端で呼ばれる「静的局面評価関数」の評価方式が異なるからだ。同じ深さでまで先読みしたとしても、末端の評価の善し悪しで棋力が大きく変わる。

静的局面評価では、概ね次の評価を行う(代表例)。
・駒の価値
・盤上の配置的価値(特に自玉・敵玉との相対位置)
・持駒の潜在的価値
・質駒を持っている価値(特に手番側)

これらの総合的な評価計算によって、間接的に玉の安全度(逆に言えば危険度)や、駒が働いているか遊んでいるかも考慮されるわけだ。手番を持っていることの価値が直接加味されることはあまりないと思うが、質駒の評価を行うことを考えれば、これも間接的に評価されるので全く評価されないというわけでもない。

持駒の潜在的価値の評価は、ちょっと特殊である。例えば、既に歩を4枚持って、駒得になるからと言って5枚目の歩を取るというのは、殆どの場合意味がない。歩が手持ちに5枚あったところで、将来それが役立つ可能性が非常に低いからだ。そういう場合、例え只でも+の評価ではなく0あるいは-の評価となるような工夫が必要になってくる。

そういった細かな計算を行うと、評価関数自体が相当重くなってくる。以前1手深く読むとレイティングで200向上する旨のことを書いたが、静的局面評価の僅かな違いで、200どころではない大きな棋力差が出てくる。極論を言ってしまえば、例え反復深化1回分遅くなるくらい評価関数が精密で重い処理になっても、それを充分補って余るくらい効果が高くなることがある。
-- この項、続く --

[*1] "Quiescence search" の和訳。"Q-search"とか「静けさ探索」と呼ぶこともある。
[*2] 単に駒の損得で将棋の勝敗が決するわけではないが、駒得できるかどうかは勝敗を決める要素の一つなので精密に調べる必要がある。特に一局の将棋の前半(序盤から中盤)は駒の損得が勝敗を決めるウエイトは大きい。
AD

ランキングチェック (第3週)

テーマ:

本blogをご覧頂きありがとうございます。先週の結果は上表の通りとなりました。不気味な(?)テーマの割に、平均約10名様が訪問されていらっしゃるようで、誠にありがたいことです。
最近、with2.netの人気blogランキングに登録してみました。今のところ、ここだけに更新pingを送ってます。
今週も1日1記事くらいで進めていきたいと思います。
AD

置換表 (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分前に得た局面の探索結果を覚えていられないということになるが、オーバフロが発生しだすともっと悲惨で、「数μ秒前の結果すら覚えてない」という言わば痴呆症現象が起きるようになる。
左図は、本間博詰将棋集(将棋世界/平成10年4月号付録)の6番から引用。
作意は、▲23銀▽13玉▲14銀成▽22玉▲23成銀▽同玉▲21飛成▽22桂▲32角▽13玉▲14角成▽同桂▲24銀▽同角▲25桂まで15手詰だが、15手先まで探索しなくても解ける例をここに挙げる。
初手▲23銀に▽同玉と応じると、▲21飛成▽22桂▲32角▽13玉▲14角成▽同桂▲24銀▽同角▲25桂の9手詰(初手からだと11手詰)がある。2手目に▽23同玉と応じた場合は残9手で詰む、ということが、この11手詰まで読んだ時点で置換表に登録される。
2手目▽23同玉以外は▽13玉しかなく、▲14銀成▽22玉の一手に▲23成銀。ここで▽23同玉(6手目)となり、置換表に登録してある先の局面に完全同一となり、その詰結論を引用できることになる。従って、6+9=15手詰であることを、15手先まで読まなくても判定できることになるわけだ[*1]。ここで問題となるのは解手順の組み立て。
謎電の場合、詰探索部と詰手順組立部のロジックは独立している。探索部では純粋に探索だけを行うのだが、解手順を組み立てる為の「攻方最短王手+玉方最長応手」の情報を置換表に補助的に記録し、探索終了後にその情報に基づいて初手から置換表を追いかけて詰手順を組み立てている。
逆に言えば、置換表がオーバフロを起こしてしまうと手順を組み立てられなくなってしまう。詰結論を得た局面についてはなるべく置換表に残す(重要度の低いレコードに上書きする)ことで、可能な限り組み立てられるようにしてはいるが、本質的な問題の解決には至っていない。

[*1] この問題を解いた時の探索量の変化は次の通り。6回目の反復深化(11手先まで)の時点で探索が終端している。
--
 1:              6 (              6+   0.000*)
 3:             78 (             72+  13.000*)
 5:            646 (            568+   8.282*)
 7:          3,678 (          3,032+   5.693*)
 9:         12,454 (          8,776+   3.386*)
11:         18,854 (          6,400+   1.513*)
--

詰将棋解答選手権 (1)

テーマ:

日本チェス・プロブレム協会 が詰将棋解答選手権という大会を行っている。これはあくまで人間同士の競技だが、計算機でどの程度の速さで解けるのか興味があったので謎電を使って計測してみた。
最近行われた第2回大会の問題セットは未だ発表されてないようなので、第1回の問題セット を使ってみる。なお、CPUはBarton/3000+、置換表は1GB、PN[*1]を用いない原始的なアルゴリズムを使ってみた。


詰手数 解図時間 初手解 探索量 1番 7手詰 0.002秒 1二角成 3,410 2番 9手詰 0.003秒 4四飛 4,326 3番 13手詰 0.001秒 2二馬 2,202 4番 15手詰 0.018秒 5六馬 25,655 5番 17手詰 0.218秒 1五銀 284,872 6番 19手詰 1.057秒 4三歩成 1,450,022 7番 23手詰 0.252秒 2三銀 358,211 8番 29手詰 6.889秒 2五竜 9,204,858 9番 35手詰 2.903秒 4九角 3,979,222 10番 37手詰 21.621秒 3二金 29,512,505

総解図時間は32.964秒、総探索量は44,825,283局面となり、平均探索速度は1,359,825局面/秒となった。第2回の問題セットが判れば、また調べてみたいと思う。

[*1] PNとはProof Numberの略で「証明数」のこと。謎電は、なるべく作意解・攻方最短(玉方最長)手順解を得ることに力を入れている。

電子計算機と将棋

テーマ:
以前、東公平さんが面白いコラム将棋雑話『電子計算機と将棋』を書かれていたので、これを現時点で考察してみる。
当時はHITAC 5020Fを用い、左図の詰物を36秒で解いたということである。
謎電では、これをBarton/3000+[*1]を用いて、8,962局面[*2]、平均1,203[clocks/局面]、約0.005秒で解く。アルゴリズムは原始的な「深さに基づく反復深化・王手全幅応手全幅・AND-OR探索」。単純計算で約7,000倍速くなったということになる(私的基準で)。短手数の詰物ならばマシンの性能差のみが現れるものとして考えると、(36年間に7,000倍高速化したとすれば、7,0001/36なので[*3])年間平均1.28倍程度は高速化していることになる。
因みに越智利夫さんは、この成果を数学セミナー(1968.6)で発表されている。恐らく、詰将棋をマシンで解こうというアイデアは旦代晃一さんがコンピュータチェスから得たのだろうと思われるが、詰将棋に適用してみるというのは相当の困難があっただろう。何故ならば、当時と今では、その開発環境に雲泥の差がある筈だからだ。

[*1] AthlonXP 2.16GHz FSB333MHz Memory:PC2700使用。Barton/3000+はいささか古いマシンなので、現在x86系MPUでは最速と思われるOpteronあるいはAthlon64FXあたりを用いれば1.5倍は高速化すると思われる。もし、StratixIIやVirtex4などのFPGAを用いてハードウエア探索で解くならば、更に1桁の高速化が可能だろうし、金に糸目をつけずフルカスタムASIC化するならば2桁は難くない。
[*2] この時の、反復深化毎の探索量の変化を次に示す。
--
 1:              4 (              4+   0.000*)
 3:             40 (             36+  10.000*)
 5:            216 (            176+   5.400*)
 7:            945 (            729+   4.375*)
 9:          3,928 (          2,983+   4.156*)
11:          8,962 (          5,034+   2.281*)
--
[*3] 因みに、Google検索で、"7000^(1/36)" と入力すると、自動的に電卓機能が働き、1.27881664の結果を得ることが出来る(但し、埋め込みの間接検索ではなく本家で直接検索の時のみ)。