ネタが転がっていた (3)

テーマ:

詰将棋メモの「コンピュータ向け超難解詰将棋作品集」 といつの間にかタイアップしております(汗)


小宮日記(06/05/01) > 解けなかった37手詰めが解けた!(^-^)/

> #激指2に高速モードで解かせたら、あっというまに解いた orz


このあたりにコメントし出すとキリがなくなるのだが少々。謎電の詰・必至解図・終盤解析は、可能な限り読み落としなし、また攻方最短(受方最長)で妥当な手順解を出すことをコンセプトにしている。私のやり方が実戦的でないことは百も承知の上だし、指将棋の棋力向上に貢献しないどころか邪魔になると思う。謎電の解図処理でPN系アルゴリズムを採用してないのは、そういう目的と拘りを持ってやっているからなのだ。誤解されても困るので一応書いておくことにする。


例えば柿木将棋の解図能力は、速度ではなく出力解の妥当性の高さに大きな意味があると思う。実際、谷川に解図目的で奨めることができる市販プログラムは柿木将棋くらいしかないと思っている。柿木将棋には柿木師匠の拘りがよく見える。それが、柿木さんを師匠と呼んでいる所以でもあるわけだ。詰将棋作家に柿木将棋が人気がある理由もよく判るし、謎電の出力解の妥当性チェックにも使わせて頂いている。


全く余談で、もう何年も前の話だが。ある日、新宿2丁目のVELOCE(東京電力の対面)に入ったら、白髪のじい様 がノートパソコンを持ち込んで将棋プログラムを使って何やら詰物を分析していた。よく見ると柿木将棋(しかも市販前のβ版だったんじゃないかと思う)を使っている。ほお、趣味が良いなあ、と思って顔を覗き込んでみたら、そのじい様は、


圍棋文化研究會の岡崎正博さん(40)


だった。岡崎さん、そんなところで何やってんですか。

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[秒]
AD

ネタが転がってた (1)

テーマ:

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


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


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


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


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


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

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

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

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

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

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

AD

詰将棋解答選手権 (3)

テーマ:

日本チェス・プロブレム協会 の詰将棋解答選手権が06/03/21に行われた。第3回 の問題セットが公開されたので、毎度のことながら謎電でチャレンジしてみることにした。今回の問題セットは、チャンピオン戦(10局)、一般戦(6局)、初級戦(10局)と階級が3つになったようだ。一般戦と初級戦は計算機将棋的に簡単過ぎるので、チャンピオン戦の10局 のみ解図してみた。非pnシングル探索、Toledo/4800+、置換表:1.5GB(主表1GB/副表512MB)での計測結果は次の通り。


【チャンピオン戦】
詰手数 解図時間 初手解 探索量
1番: 9手詰 0.020秒 5六金 40,111
2番:11手詰 0.045秒 4六銀 77,671
3番:13手詰 0.141秒 3一竜 315,922
4番:17手詰 0.182秒 7四金 298,249
5番:19手詰 0.092秒 2三歩 168,443
6番:19手詰 0.152秒 3四銀 294,431
7番:21手詰 0.018秒 1七歩 36,160
8番:27手詰 0.538秒 1三飛成 1,080,892
9番:37手詰 69.100秒 5七金 127,707,259
10番:39手詰 29.708秒 2六馬 55,900,591
合計時間: 99.996秒 合計探索量: 185,919,729 (平均探索速度: 1,859,271/秒)


解かせた感じとしては、前回より今回の方が(計算機的には)簡単な気はする。全問作意通りに解けたし、解手順の組み立てに失敗するようなこともなかった。双玉問題がいくつかあり、その作意を鑑賞するだけでも楽しめる完成度の高い作品揃いだったのではないかと感じる。


置換表を1.5GB確保したが30秒を経過したあたりから探索速度が落ち込んでいたようで、平均で毎秒約186万局面の速度しか出ないというのは、恐らく図の複雑さも影響しているのだと思う。個人的な目標を言えば、速度だけでなく効率も上げ、9・10番を各問3秒以内で解きたいところである。

仮想合2手延長探索

テーマ:

詰将棋のルール にちょっと興味深い図(2005/10/27)があったので、謎電といくつかの市販将棋プログラムで試験的に解いてみた。ソースは2ちゃんねるからのようである。


結論から書くと、謎電では▲39角の1手詰となる。但し、警告を出すようにしている。なお、とある市販プログラムで解くと、ヘンな動作を起こさせたりするので、計数将棋学的には結構面白い図かも知れない。


謎電では柿木のアルゴリズムの変形で仮想合2手延長探索を行っている。例えばこの図の場合、▲39角に▽28合とし、その合駒を直に取って王手を掛ける手についてのみ2手延長して探索する、というものである。反復深化4回目、つまりは7手先まで読んだ時点で、仮想合で詰むことが判り、どのような駒種であっても(その駒を使わずに)詰と判断し、特にこの場合2手目は合駒しか手がないので解の組立を中断して「▲39角までの1手」が返るようになっている。


注意しなければならないのは、仮想合処理を実装する際は「連続王手の千日手」の誤った判定を行わないようにするのがポイントになる。「取った駒を直に相手に返す」という処理とほぼ同じ動作になるので、これを言葉通りに処理すると、不詰扱いになりかねないからだ。


具体的には、▲39角▽28合▲同角▽27玉▲39角▽28合▲同飛▽17玉に▲29飛の局面が、置換表を参照した時に完全同一局面で不詰(連続王手の千日手と等価扱い)に判定してしまうとちょっと拙い。詰方基準で駒得同一盤面として詰扱いにする方がまだマシだ、という意味である。


しかしこの図は1手詰というわけではなく、不完全作として扱われるようだ。恐らく、無駄合か否かの判定基準は「1回の合で2手延命しているだけかどうか」であって、「その駒を使わずに詰ますことが出来るかどうか」ではない、ということだと思われる。この図に限って言えば、確かに▽28合は4手以上の延命になっている。


(追補) 余談だが、謎電では玉方に持駒がない時、あるいは持駒の駒種が1つしかない時は、仮想合生成・探索を行わないようにしている。
(私信) TETSU様 なるほど、そのあたりが意見の分かれるところなんですね。コメントありがとうございました。こういう局面を計算機で解かせた時に、人間に対してどのようなワーニングを出すかがポイントだと思ってるのですが、今の謎電は「解不定」と表示しているだけです。

あなたは何秒で解けますか

テーマ:

計算機将棋プログラムが、その詰解図能力を世間に誇示しだしたのは、10年くらい前からではないかと思う。左図は、週刊将棋上での森田将棋の宣伝で、ちょっとウロ覚えなのだが「あなたは何秒で解けますか?森田将棋なら2秒です」という旨のキャッチコピーが使われていた詰物だ。

この「2秒」で解ける時のマシンスペックがどれくらいのものなのか不明だが、当時、森田将棋の詰解図性能はピカイチで、DOSベース(仮想86)で動いていた謎電で初代Pentium/90MHzを使って解いた時、探索効率が悪く10秒を切ることが出来なかった記録が残っている[*1]

今にしてみれば、この体験から、謎電の詰探索性能改善計画がスタートした気がする。「あなたは何秒で解けますか」が、「あなたのプログラムは何秒で解けますか」に読めたからだ。但し、その初速は遅く、加速も鈍かった。
左図は、'99/08にNHK・ETV特集で出て来た詰物、柿木将棋が約30秒で解いたと紹介されていた。当時、これも手元にあったMMXPentium/200MHzを使って、やっとWin32への移植が終ったばかりの謎電で試してみたら「およそ450万局面の探索で約40秒掛かった。柿木将棋といい勝負になってきたかなー」と書かれたメモが今も残っている[*2]

この詰物は、詰め上がりが○の形になるのがミソで、場合によってはそれを判断できなければ(あるいは玉方応手の探索順が悪ければ)、作意解を得られない。謎電では、そのような認識処理を行ってないので、詰ますことは出来ても正解を得ることは出来ない。

また左図は、青野照市九段作。永世名人Ⅲプレステ版で19'05"、ドリキャス版なら1'47"で解けるという話である。家庭用ゲーム機と一般のPCの性能とでは全然比べようもないが、同様に当時の謎電でMMXPentium/266MHzを用いた時、3秒程度で解けた[*3](但し、その時の謎電は最後の8手を作意ではない手順で詰ませていたので参考にならない)。「ヨッシャ、永世名人に勝ったー、はっはっはっ」と思っていたが、選手権の直接対決で永世名人に謎電が勝った試しはない(笑)

なお、この頃までの謎電は、置換表というものを実装してなかった。詰・不詰の結論を、完全にツリー管理で行うという、非常に涙ぐましく原始的なことはやってた。当然、置換表を用いた時の効率と比べれば全く比較にならない。


さて最後の左図。これは既にPN系詰探索が猛威を振いつつある時代に、近代将棋'00/02(p.38)で紹介されていた実戦図。「▲谷川は14分で詰ましたが、400MHzのCPU+RAM128MBで3時間以上掛かった」らしい。プログラム名も判らないしアバウトな表現になっているが、実際記事内では詳細を伏せてある。

現謎電(Barton/3000+,置換表1GB)で解くと39手詰、置換表がオーバフロをバリバリ起こし出して300秒位掛かるので、相当難しい実戦詰であることは確かだ。しかしながら、これくらいは古典的な探索手法のままでもサクっと詰ませたいと思うところである。でなければ、図巧8番の作意解を純粋に探索で得ようなんてのは夢のまた夢になってしまうからだ。

攻方最短・受方最長手順解(理想的には作意解)を求めるアルゴリズムを極めてみるのも面白いと思うのだが、詰解図はPN系がほぼ主流になってしまった。と言いつつ、現在最強のPN系詰探索ならどれくらいのコストで解けるのか興味あるところではある。


[*1] 現謎電では、63[ms]で解く(Barton/3000+)。

[*2] 現謎電では、2498[ms]で解ける(Barton/3000+)が、指将棋では今でも柿木将棋と勝負にならない、為念。

[*3] 現謎電では、86[ms]で解く(Barton/3000+)。

双玉詰試験図

テーマ:

第6回選手権での出来事だったと思う。1手詰で勝ちという局面で、確かに詰んではいるのだが、その手が「自玉で敵玉に直接王手を掛けた反則手で負け」という将棋を観戦した時、笑うに笑えないものがあり、選手権終了後、自宅に着くなり速攻で自分のプログラムのテストを念入りにやった記憶がある。稀に玉頭戦になった場合に起き得る話ではあるが、双玉共に自爆判定を行っておけば回避できる問題ではあるものの、そのような大逆転反則負けは悲し過ぎるのでやはりキッチリ試験しておきたいところである。

そういうわけで、正しく解けるようにしておきたい双玉問題についていくつか例を挙げておく。なお、一般的な双玉の詰物を大量に試験されたいならば、(また神吉ネタだが)次の作品集をお奨めする。そして、本の表紙に向かって「ここでも全身ピンクかよ!」と突っ込みを入れてみるのも一興だ[*1]


カンキの双玉詰将棋傑作選〈上巻〉

カンキの双玉詰将棋傑作選〈下巻〉


さて通常は、次の詰物が実用時間で正しく解ければ、ほぼ問題なしと言えそうである。

左図は、将棋世界付録「神吉宏充双玉詰将棋集」の39番、また右図は、そのVol.4の47番から引用。どちらも「選手権の実戦で現れたならサクっと詰ましたい難易度」だ。


また、以前、解けない詰将棋 でも採り上げたような、実戦では殆ど現れそうもない局面ではあるものの、出来れば作意通りに解きたい、ちょっと落とし穴のある図を2問ほど挙げておく。

左図は、出典不明だが、攻め方玉に王手が掛かっている状態から連続逆王手で詰ます問題。また右図は、おもちゃ箱「加藤徹 全作品」3手詰 No.11aから引用した詰物で、計算機将棋プログラマ泣かせの作品だ。作意通りに解けるならば、相当の工数を掛けてプログラムを作っていると窺い知ることが出来る。因みに現謎電では、右図を詰ますことは出来ても作意通りには解けない。


以上の4局は、何かしら解図アルゴリズムに改造を掛けた時、必ず試験する問題集に含ませて頂いている。


[*1] 無論、私はここぞとばかり間髪を入れずそうした。

超難解詰将棋作品集

テーマ:

コンピュータ向け超難解詰将棋作品集というタイトルのページが、詰将棋メモの中に最近新設されたので、ここで紹介する。詰探索アルゴリズムに自信のあるプログラマの方、必読。


これは決して挑発でも嫌味でもない純粋に学究的興味の現れで、このような提起をしてくださる詰将棋作家の方がいらっしゃるというのは、非常にありがたいことだと私は思っている。実際、これは私も知りたいと思っていた。特に、それ程手数が長くない割に解図コストが極めて高い詰物に興味があり、次の2問について現在分析中。



裸玉(5一玉・角金4銀2歩9、詰パラ2004年4月号)『驚愕の曠野』改良図

裸玉(3八玉・金4銀4桂香歩3、詰パラ2003年11月号)


なお、頭から解こうとすると、謎電ではどちらも実用時間内で解けない。

詰将棋解答選手権 (2)

テーマ:
日本チェス・プロブレム協会 の詰将棋解答選手権が先日行われたが、第2回 の問題セットが公開されたので、早速謎電を使って計測してみた。なお、問題セットは、一般戦(6局)チャンピオン戦(10局) で分かれている。

非PN探索、Barton/3000+、置換表:1GBでの計測結果は次の通り。

【一般戦】
      詰手数   解図時間 初手解                 探索量
  1番  5手詰    0.000秒 4四金                    104
  2番  7手詰    0.001秒 2一飛                  1,681
  3番  9手詰    0.005秒 1三金                  8,390
  4番  9手詰    0.007秒 6五銀                 10,458
  5番 11手詰    0.002秒 4九角                  3,172
  6番 13手詰    0.569秒 3二飛                809,001
合計時間:       0.584秒    合計探索量:        832,806
                           平均探索速度:    1,426,037/秒
【チャンピオン戦】
      詰手数   解図時間 初手解                 探索量
  1番  7手詰    0.003秒 5八角                  3,829
  2番 11手詰    0.021秒 3九香                 27,546
  3番 13手詰    0.057秒 3五桂                 67,528
  4番 13手詰    0.019秒 4二桂成               26,038
  5番 17手詰    0.018秒 3七歩                 26,536
  6番 19手詰    0.079秒 7五馬                102,227
  7番 23手詰    0.497秒 2五金                666,835 [*1]
  8番*25手詰  477.111秒 3二銀            711,263,949 [*2]
  9番 33手詰    1.306秒 2四銀              1,988,951
 10番*31手詰  158.833秒 6三飛            196,926,510 [*3]
合計時間:     637.944秒    合計探索量:    911,099,949
                           平均探索速度:    1,428,181/秒
【修正図】
      詰手数   解図時間 初手解                 探索量
     *37手詰  832.732秒 5六香          1,027,142,914 [*4]
                           平均探索速度:    1,233,461/秒

前回と比べ、今回は一筋縄ではいかなかった。特に、チャンピオン戦の8番は見た目や詰手数より遥かに難しい。チャンピオン戦7番を解図して妙な不具合が発現した。現在調査中。

置換表1GB確保では詰探索の場合、約1分を越えるとオーバフロを起こしだし、探索効率が徐々に落ち込んでいくようである。


[*1] 無駄(中)合判定にバグあり。表示が23手詰になっているが、正しくは21手詰。
[*2] 置換表がオーバフロを起こして解組立失敗。

[*3] 表示は31手詰になっているが、これは16回目の反復深化で探索が終端したことを示している。余詰があるらしく解手順の9手目は64馬となったが、それ以降組み立てられない。

[*4] 上記10番の修正図。これも置換表がオーバフロを起こし、手順を組み立てられない。作意を4手進めてから(残33手詰)解くと、約226秒で解くが、最終2手が情報落ちになる。

図巧8番の自虐的探索

テーマ:

左図は、図巧の8番。詰手数でいえば41手だが、計算機的にはミクロコスモスより難しい詰物だ。1997年4月に最長手数のミクロコスモスがPN探索で解けたが、図巧の8番を計算機を用いて詰ませたのは、その後のことだからである。


手数だけを見れば中編に入る詰物なので、古典的な「深さに基く反復深化」で解けてもおかしくなさそうだが、実際に図巧の8番を頭から解こうとすると、謎電の場合1分の探索で23手先まで、10分かけても25手先までしか反復深化が進まない。PNを使っても将棋図巧全100局の中では最も解図コストの高い詰物なのだから一筋縄で行かないのも当然だ。

この図巧8番について、暇な時に色々調べているのだが、ちょっと面白いことに気が付いたのでここに記録しておく。

まず、詰上がりから順に逆算して1,3,5,…と手数を増やし、いったいどこまでなら実用的な時間で解けるのかを調べてみた。その結果は次の通り(Barton/3000+、置換表:1GB)。


詰手数   解図時間 初手解           探索量
 1手詰    0.000秒 2二金                1
 3手詰    0.000秒 1三角成             12
 5手詰    0.000秒 2三桂成             27
 7手詰    0.000秒 3三香              173
 9手詰    0.000秒 1二金              611
11手詰    0.001秒 2二角            1,921
13手詰    0.010秒 2三金           11,178
15手詰    0.022秒 3二竜           27,598
17手詰    0.020秒 3二と           30,363
19手詰    0.025秒 9二飛成         34,682
21手詰    0.182秒 7七角          204,721
23手詰    0.924秒 3四桂        1,074,113
25手詰    1.439秒 4三と        1,861,774
27手詰    4.742秒 4三金        6,006,925
29手詰 4542.982秒 8七角    5,792,948,795


逆算31手詰以上の手数がかかる局面については計測を断念した。


さて、29手詰と27手詰の間の解図時間(探索量)がいきなり約3桁変化する現象が起きた。この異常な探索量爆発は、単に手が広いという理由だけではなく、玉方の応じ方に起因しているようだ。

逆算29手詰局面は▲87角以外にも有効な王手はいろいろある。例えば詰まない王手の▲33と▽同玉▲44角なら、玉方は{▽42玉、▽43玉、▽32玉、▽34玉、▽24玉}の5つの応じ方があり、人間なら「▽24玉で手が続かない」とすぐに判断するが、計算機的には探索の中で▽42玉や▽43玉といった極めて悪劣な応じ方をしてしまうことがある。次に「▲88角と竜を抜かれながら王手を掛けられ、後にその飛車で王手を掛けられる」あるいは「44の角が動く手は全て王手」というように自虐的に探索量を増やしてしまうことが、気が付かないうちに内部で起きているのだ。

一般に攻方の手の探索順位付けをいくら工夫しても探索効率は2~3倍程度しか改善しないが、玉方の手はその探索順によって(つまりは優先付けの工夫次第で)、桁違いに改善出来る可能性があることが判る一例ではないかと思う。