左図はライエル問題集の53番(ProblemID:895-6)である。参考手順は、▲11角▽同玉▲41竜▽31銀▲12歩▽同玉▲21銀▽11玉▲32銀成、最終手を▲32竜としてしまうと勝負がひっくり返ってしまう面白い問題だ。


さて、YSSの読み(http://www32.ocn.ne.jp/~yss/grimbergen.txt )を調べてみると、


> # ▲11角打△11王▲41龍△31銀打▲43銀打△79角成▲79金△79飛成▲79王△68角打▲88王△77金打▲77桂△77銀成▲98王△87成銀▲87王△86角成▲88王△22金▲42銀打△68成銀▲31龍△21桂打▲21桂成△21金


となっていて、ここで注目したいのは5手目の▲43銀である。


左図は、その▲43銀を指したところ。この手は次に▲21桂成以下7手詰の詰めろで、これを単純に受けようとすると▽12玉くらいしかなく(▽22角、▽12角もあるにはあるが、何れも)▲32銀成で必至上がり、頭から数えて7手必至となる。つまりは参考手順より更に速い手を見つけ出しているわけだ。しかもこっちの手順の方が手持ちに歩を残すのでより安全なようである。


謎電で頭から解図すると、パラメタ{5,11}で9手必至、{7,11}で解くと7手必至となる。YSSは、どうやら通常探索中の相当深いノードでも7手詰くらいの詰めろは(言い方を替えれば頓死を)確認しながら探索しているようだ。なかなかやるなYSS。このデータは2004/11/18時点でのものなので、現在では更に終盤力に磨きが掛かっていると思われる。謎電の作者、大ピンチ、てか孫子曰く敵を知り己を知れば百戦危うしからず、だがこの場合、知らない方が幸せだったかも知れない(汗)

AD

選手権まであと1週間

テーマ:

あいかわらずバグにハマっている。並列探索が巧く働かん。仕様を盛り込み過ぎた(笑) 目標としてはDeepJunior並の1.8倍(実効90%)を目指しているのだが、そういう数字が出る前に原因がハッキリ判らない再現性のないバグに悩まされている。おかげで本ブログを更新する暇が作れなかった。余談だが(仮に意図通りに動くようになったとしても)、効率を計算する時、探索量を基準とするか解図時間を基準とするか、結構微妙な問題だ。基本的には解図時間をベースに求めた方が正しいような気はするものの、解が同一になるとは限らないので単純に時間コストだけで効率を求めるものでもなさそうである。


並列化すると解が変化するのは、(並列化アルゴリズムのバグもあり得るが)探索アルゴリズム側の特性だと思う。この現象が起きるメカニズムを捕らえるのは結構厄介なので追いかけきれないのだが、手の延長法と置換表からの結論引用法に拠って、その現象の起き易さが変化することは判った。


手の延長法については、恐らく、帰納的条件で延長するのなら問題が起き難いが、演繹的条件で延長すると少しおかしくなる。例えば「直前に動いた(あるいは盤上に打たれた)駒を取る手」といった条件で延長すると、そのノードへの経路の違いで同一局面同一手でありながら延長したりしなかったりすることがある。そういう理由で探索する手のオーダリングによって置換表への登録値が変わり、つまりは引用時の結論値が変化する。しかしながら、探索した結果に基づいて延長するか否かを決める、といったような帰納的条件だけで探索すると解が安定するようである。これなら経路違いであっても同一局面同一手が異なる探索挙動を示すことにならないからだと思われる。


既に時間がなくなってきたので、このあたりは次期の課題として残しておくことにして、取り敢えずGPFが起きないレベルに持っていくことを今期の目標にしようかと思う。

AD

ネタが転がってた (2)

テーマ:

詰将棋おもちゃ箱の「コンピュータ向け超難解詰将棋作品集 」を私は時々ウオッチしている。少し古い話なのだが、ここにも楽しげなネタがあったので、謎電の作者的感想を書いておこうと思う。


左図について。

> 2005年8月6日、岩田俊二さんよりコメント
> 「何日もかかって作った作品が,4秒と0秒で解かれてしまいました。コンピュータがこんなに進化しているとは,知りませんでした。ところで,コンピュータは全検をしているのでか? 場合の数でいえば,全検は不可能と思えるのですが・・・。全検でなければ,ソフトの隙を狙う手がありそうな気がします。」


ここでの「全検」とは「全数検査」という意味で使われているのだと思う。東大将棋と激指については判らないが、柿木師匠のキャラクタからして柿木将棋は全幅探索の筈。但し、AND-OR探索はαβ枝刈と同様、全局面探索でなくても解が保証される。


詰物を古典的な深さに基づく反復深化で解こうとすると、2手深く読む毎に概ね3倍程の解図コストを必要とする。指標としては2倍以下なら簡単、4倍以上なら難解、5倍以上で超難解だと言える。この図の場合、37手詰でありながら399,278局面の探索で解け、2手毎に約1.5倍程度にしか増えず、人間の感覚からは信じにくい結果ではないかと思う。


結局置換表が効きやすく、実質的な探索幅が狭い詰物は計算機にとって難解な部類に入らない。計算機の隙を突くには、手数が長いというだけでなく「玉方がどう応じても王手の候補が沢山ある」ことで短時間では解けなくし、玉方作意手の外に多くの余詰手順を含ませておくことで作意解を得られ難いようにすることが方法の一つとして考えられる。その上で完全作を目指すとなれば、作り手側も相当苦労するのではないかと思われる。謎電の作者としては、是非、そのような作品を作って頂きたいと願うところである(嫌味ではなくマジで)。


最後に、謎電で上の詰物を解いた時の反復深化毎の探索量プロファイル結果を示す(Toledo/4800+)。


---
 1:              5 (              5+   -.---*)
 3:             33 (             28+   6.600*)
 5:            138 (            105+   4.181*)
 7:            429 (            291+   3.108*)
 9:            926 (            497+   2.158*)
11:          2,055 (          1,129+   2.219*)
13:          4,133 (          2,078+   2.011*)
15:          7,018 (          2,885+   1.698*)
17:         11,047 (          4,029+   1.574*)
19:         16,541 (          5,494+   1.497*)
21:         24,135 (          7,594+   1.459*)
23:         34,481 (         10,346+   1.428*)
25:         47,032 (         12,551+   1.363*)
27:         62,252 (         15,220+   1.323*)
29:         83,559 (         21,307+   1.342*)
31:        129,186 (         45,627+   1.546*)
33:        180,942 (         51,756+   1.400*)
35:        272,952 (         92,010+   1.508*)
37:        399,278 (        126,326+   1.462*)
---
解図時間:   0.229[秒]

ネタが転がってた (1)

テーマ:

ここ数日デバグ作業でハマっていて最先端計数将棋学を更新してなかった。が、楽しげなネタが転がってたので殆ど私信になってしまうが書くことにする。


小宮日記 (06/04/19) >謎電あたりの高速なソフトだと、PN-DNをやってるんでしょうねえ。


謎電の詰探索アルゴリズムは現状、古典的な「深さに基づく反復深化」でしかない。しかも王手全幅・応手全幅。当然ながらAND-OR探索なので応手については、ある手が詰まない限り別の手を読まない。無駄合か否かの確認で延長探索を行っているものの、それを除けば置換表と手のオーダリングに頼って(探索速度は落ちるが)探索効率を上げているだけである。チャンピオン戦9番に限っていえば、玉方応手のオーダリング次第で大きく解図コストが変化する。一言でいえば「次に有効な王手が掛かりにくいように受ける手を優先する」のが効率を上げるポイントである。この件は「図巧8番の自虐的探索 」でも解説している。


> 「成って詰まないなら、成らない手も詰まないので指さない」とか柿木さんのアルゴリズムもある


初耳だが、柿木師匠そんなこと言ってましたっけ!? 多分「(飛角歩および敵陣2段目の香が)成って打歩詰を検出した場合は、それが成らない手も読んでみる(それまでは読まない)」ということなのではないかと思う。この効率向上は確かに小さいが、実装しといて損はないので謎電の詰探索には入っている。因みに指将棋では、「(打歩詰ではなく)負けを検出した時に不成の手を読んでみる」というアルゴリズムになっている。実戦では殆ど効果がないが、次の一手問題を解かせる時には、作られた問題だけあって有効に働くことが結構ある。


【追記 06/04/19 22:30】 なぜか読み落としていたみたいなので追加。

> (1秒に300万手以上探索可能)

うさぴょんのだんな、みさき将棋を見習え!!(笑)

> すみません。かなり間違って書いてました。

> 「成って王手をかけ、それが取られて詰まないとき、不成りの手を読まない(取られれば同じ)」でした(サイエンス社「コンピュータ将棋」P93)

でしたか。それなら納得しました。その場合、即刻置換表にヒットするので、謎電では特に細工はしてません。

没になったコラム (1)

テーマ:

どっちも専守防衛の図。


海上警備行動(子供のニュースウイークリー)


角を動かしているだけで使えないってのが、なんつーかアレですね。この戦法を、某北挑戦相手に使うのはちょっとナニです。Harpoonは撃ち落とせても、Taepodong撃ち落とせなかったらシャレにならん。角換わり将棋も含めて、できれば自粛したいところ。


【追記】そいえば謎電は、初対局で角を切って金を取った。謎電の作者は、その時の心境を次のように述べています。


「あんときゃ生きた心地がしなかった(汗)」

SPEAR (2)

テーマ:

選手権まであと3週間となった。ライエルに対するプレッシャ~を更に強めていこうかと思う。とりあえず、前回までの成績をまとめ直してみる。

7th
('97)
8th
('98)
9th
('99)
10th
('00)
11th
('01)
12th
('02)
13th
('03)
14th
('04)
15th
('05)
SPEAR 23 25 25 22 16 20 23 20 16
謎電 24 27 15 19 22 27 22 19 17

3年連続1位差というのは、まったくふざけた話だ。しかも2年周期できれいにトータル順位が入れ替わっている。この悪循環を断ち切るには、第16回の直接対決でSPEARにビシっと勝つしか道はないと謎電の作者は考えている。


去年の選手権での話だが、▲SPEAR▽謎電戦が始まる直前に、ライエルグリムベルゲンさんは次のようにネイティブな日本語で述べています。


勝負は、やる前から決まっている。


あのなライエル。オランダではそういう諺があるのかも知れないが、日本ではそういう言い方はせんのだよ。


A) 勝負は、塵を掃くまで判らない。

B) 勝負は、胃液吐くまで判らない。

C) 勝負は、下駄を履くまで判らない。


さて、どれでしょう。てな冗談はさておき、次回SPEARと当たることがあれば、とっておきの秘策を謎電は用意しているから楽しみにしていてくれ。

StratixII GX のサンプル出荷開始

テーマ:

個人的に期待していたStratixII GXの出荷がやっとアナウンス された。と言ってもサンプル出荷でしかないし、受注を開始した開発キットも評価レベルのボードなので使えないのだが、将来的にトランシーバチャネル数が16以上のモノが出てくれば、PCI Express x16[*1]に対応したFPGAカードが出てくるだろうと思う。


具体的には、EP2SGX90Fか2SGX130G。量産開始が今年の10~11月の予定なので、実際にPCI Express x16のカードが出てくるのは来年に入ってからになるかも知れない。間に合えばそのあたりのデバイスを使って第17回で4coresハード探索をやってみたいと思っている。その前の第16回でSPEARを倒さないとな(笑)


[*1] 1レーン片方向あたり2.5Gb/sなので、x16で40Gb/s=5GB/sがピークの転送速度だが、実ピーク帯域はその20%減の(8B/10Bエンコーディングが入るので)、片方向あたり4GB/s、双方向で8GB/sとなる。とはいえ実際には転送速度より応答速度の方が重要だったりするし、ドライバだけでなくアプリレベルのプロトコルの設計次第で通信効率は相当変わる。