ミラクル終盤術分析

テーマ:

左図は、ミラクル終盤術[*1]のp.37から引用。解説では、▲33香▽同桂▲44桂▽同歩▲21角▽42玉▲43香▽同金▲同角成▽同玉▲41竜▽42香▲32金▽51銀▲同竜▽32玉▲21銀▽22玉▲12金▽同香▲42竜▽21玉▲22香▽11玉▲31竜と詰め上がりまで示されている。

謎電で必至解図を行った時、必要最低パラメタ{7,11}なら約96秒(攻方頓死チェックを外すと約57秒)で17手必至として解くことができる。

しかしながら指将棋モードではタイムアウトを起こし、前解図効果も出ず正着を指すことが出来ない。この図は相当難しい局面で、ここで必至を掛けなければ先手勝てない。例えば▲22香といった緩手なら▽48と以下先手玉頓必至、▲47金直も意味がなく▽39銀以下やはり頓必至となる。つまり先手玉には「殆ど受けのない2手スキ」が掛かっているわけだ。

さて、羽生さんの解説手順と必至解図結果が微妙に異なるので、参考までに分析内容を以下に示す。

--
初手から4手:▲33香に替えて▲44桂からの手順前後でも同様に必至がかかる。
5~11手目:▲21角~▲41竜まで激しく同意で無問題。
12手目:▽42香は▲52金までの早必至で、▽42桂[*2]が最強の受け。
    ▽42香に▲52金なら、▽31銀は▲53金!以下詰。
                       また▽51銀は▲同竜までなので無意味。
13手目:▲32金は▲52金に劣る。▲32金だと▽31銀と受けられて手数が延びる。
14手目:▽51銀は取られて必至上がりなので無意味。
       ▽31銀とし、▲同竜▽52玉▲72銀まで必至
          (あるいは▲42金▽同銀▲32金もある)。
15手目:▲51同竜で受けなし(16手目は参考までに▽32玉となっている)。
17手目:▲21銀(本来は受方最長で11手詰)より、▲31金からの7手詰の方が早い。
    参考の詰手順は「駒余りなし」が狙いと思われる。
--
以上が正しければ、専門棋士に対しても(詰の有無に限らず)計算機がお役に立てる可能性があることを示せたと思うのだが如何だろうか。
[*1] 第1刷は平成3年1月25日。私は平成6年にこの本を買ったのだが、この図を見て刺激を受け、必至探索処理のコーディングに着手したことを覚えている。

[*2] 12手目に▽42桂と受けた場合、▲32金▽31銀▲同竜▽52玉▼72銀まで合計17手必至となり、謎電はこの手順を解とする。

AD

K8系最適化手引書

テーマ:

K8系プログラマ必携[*1]のドキュメント。AMDのHPに行けばあるのだが、判り難い場所なのかもしれない。あまり知られていないような気がしたので、ここで(も)紹介する。

 

Software Optimization Guide for AMD Athlon™ 64 and AMD Opteron™ Processors

 

文書#25112。現時点で、Rev.3.05(Nov.2004)。英文。要AdobeReader。


[*1] と書きつつ今年の選手権もK7系(Barton/3000+)で参戦。当然Singleである(号泣)

AD

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

テーマ:


本blogをご覧頂きありがとうございます。先週の結果は上表の通りとなりました。集客力のあるサイト様からご紹介を享けると異常にカウンタが跳ねます。

さて、今週からは私も選手権の準備の方に時間を割きたいと思いますので、選手権が終るまでお休みか時々の更新になります。

 

謎電の今年の目標は、1) シード権を獲る、2) SPEARに今度こそ勝つ、3) KFEndに勝つ(野望というより無謀ですが)という、全く身の程知らずなものであります。終盤は良くなりましたが序中盤が相変わらず拙いところがあるので、実のところはシード権を獲ることすら危ないというのが現状でしょう。


人気blogRanking(自然科学)
元祖ブログランキング(自然科学)

AD

注意すべきWarning

テーマ:

VisualC/C++が吐き出すコンパイル時の warningメッセージで、特に注意すべきメッセージについて挙げる。

CodeMeaning
C4172 ローカル変数またはテンポラリのアドレスを返します
auto変数ではなくstatic変数にしないと問題があるコーディング。これは概ね危険。油断しているとたまにやってしまうので注意。
C4706 条件式の比較値は、代入の結果になっています
ケアレスミスで "==" と書くべきところを単に "=" と書いてしまっている場合がある。定数と変数の比較は、定数を左項に書くようにすることで(単なるワーニングではなく)フェイタルエラー となるのですぐに気付く。しかしながら、変数同士の場合はワーニングでしかないので注意が必要。
C4127 条件式が定数です
if( 0 ) といった文を書くと起きる。稀に意図してそう書く場合があるが、このメッセージが出たら、一応はソースを確認しておいた方が無難。
C4715 '関数名' : 値を返さないコントロールパスがあります
関数の定義では戻値があるのに、単に return していると起きる。これも概ね危険。
C4700値が割り当てられていないローカルな変数 'xxx' に対して参照が行われました
auto変数を初期化せずに(あるいは代入せずに)使用した場合に、このメッセージが出る。アルゴリズムによってはそれでも問題は起きないが、やはりソースを確認しておいた方が無難。また、Debugモードでは正常に動作するが、Releaseモードだとうまく動かないような時、このワーニングが起きていることがよくある。
C4701 値が割り当てられていないローカルな変数 'xxx' に対する参照が行われる可能性があります
これは、C4700と同等。違いは、関数内部で参照が行われている時はC4700で、関数外部で参照される可能性がある時はC4701となる。例えば、初期化していないauto変数を戻り値にすると、このメッセージ(C4701)が出力される。
C4211非標準の拡張機能が使用されています : extern が static に再定義されました
グローバル宣言した変数をautoではないローカルなスタティク変数にしてしまった時に、このメッセージが出る。グローバル変数として使った変数名を失念してしまうとこのようなことになる。
C4554演算子の優先順位に問題があります。カッコを使用して優先順位を明確にしてください
C言語の仕様上の演算子の優先順順位を100%覚えていて常に間違いなく式を記述できる、などということは不可能だと考えた方がよい。一目見て優先順位が判らない場合、論理演算子と等号・不等号、三項演算子を含む式の場合は、括弧記号を用いて記述した方が後々問題が起きにくくなる。あるいは、複数行の式にした方がよく、見かけは冗長になるが最適化が効けば遅くなることはない。
C4033

(C4035)

'関数名' : 関数には戻り値が必要です
例えば、int func(...); と宣言している関数であるにも関わらず、int 型の戻値を返さないような関数だと、このようなワーニングが出る。「ついウッカリ忘れる」ということもあるが、関数の仕様を戻値なしから戻値ありに変更した場合、全ての return 部分についてチェックする必要がある。このワーニングを残したまま実行すると戻値は不定なので注意。
'関数名' : 戻り値がありません
C4035も同様のワーニング。return文そのものがない時にはC4035が出る。

これらの warningは、見逃すことができず、無視すると酷い目に遭うものばかりである。むしろ、fatal扱いである方が望ましい程の問題を引き起こすことが多い。例えば C4700は、「Debug構成でビルドすると巧く動くが、Release構成では不具合が起きる」といった現象がよくある。
なお、ワーニングが煩い時は、コンパイルエラーレベルを落とすか、#pragma warning(disable : 9999 ...) とプログラムの冒頭で指示することで強制的に消すことができるが、なるべくそのようなエラーメッセージ抑制は行わない方が無難かもしれない。

激指の興味深い探索法 (2)

テーマ:

将棋という分野に、統計的機械学習の一手法を適用して「指し手学習」を行うという研究を、激指の鶴岡さんが試みられている[*1]。これは、多数の実戦譜の、局面と実際に指された指し手の局所的な配置関係などを基に、局面と手の相関を予め求めておき(つまりは学習させておき)、未知の局面に対して、どういう手がどのくらいの確率で指されるかを求める(指し手を予測する)、というものだ。

 

鶴岡さんの言によれば、実現確率打ち切りの探索アルゴリズムに適用できるということだが、有力な候補(指されると予測される確率が高い)手の順に探索できるという意味では、枝刈効率は相当改善しているのではないかと期待できる。

 

よくある学習の手法は、例えばTD法のように「駒の価値の最適値を求める」といったものだが、この試みは、そこから更に一歩前進した手法であるように思われる。今年の選手権で、実際にこの手法を用いてチャレンジされてくるとなれば、激指がどのような結果を残せるか非常に興味深いところである。

 

その結果が良しとなれば、将棋においての Artificial Intelligence の礎を築くことになる筈だ。今の所は指し手予測に用いる特徴量の対象を人間が決めているだけだが、その対象特徴そのものについても試行錯誤的であっても機械が自身で決めるとなれば更に面白い。

 

棋力を決める(相関性のある)特徴が何であるかを「(あたかも)自助努力によって発見できる」ようになれば、その機械が動き続ける限り(ある漸近線に向けて)無限に[*2]、しかも自動的に強くなることができる筈だ。となれば、それは画期的なことであり、真にA.I.と初めて呼べることかもしれない。それが実現できるのはまだ先のことにせよ、第15回選手権において、激指がどんな活躍を見せるか、私は楽しみにしている。 


[*1] 概要については、将棋プログラム「激指」のページにある(要PowerPoint)。

[*2] 少々語弊があるが、「アキレスと亀のパラドクス」の逆の現象になる。

計算機的攻方最短の意義

テーマ:

 


左上図は、ある詰物の途中図である。ここから「攻方最短」で解くと、▲82同竜▽同玉▲72角行成▽91玉▲92歩▽同玉▲83馬▽91玉▲92歩▽81玉▲72角成までの11手詰となる。


大山の詰将棋100 の中には詰将棋の規則が書かれてあり、その一つに「一、攻め方最短手数で詰めること」と明記してある。私はこれを信じていたのだが、10年くらい前に「そんなルールはない」と言われたことがある。更には「一、攻め方最後どの駒を使っても詰みの時は、位の高い方の駒で詰めること」、また「一、玉方最後どの駒で取っても詰みの時は、位の高い方の駒で取ること」とあり、これも信じ切っていた。しかし「そんなルールはない」ということらしい。ということは、大山康晴十五世名人は、おもいっきし話を作ってたということになってしまう。信じる者が馬鹿を見たのだろうか[*1]。


さて、この左図の余詰を無理矢理調べてみると、▲81竜▽93玉▲82竜▽同玉と2手冗長な手順から詰ますことができるし、右図からは▲72角不成▽71玉▲61角成▽81玉▲72馬引と4手冗長な手順で詰ますことが出来る。計算機的視点で見れば、攻方最短のルールがなければ作意解が得られないことになるのだが、それともこれらは「余詰」であり、傷扱いになるのだろうか。


[*1] 一時期、謎電の詰探索ロジックの中に、このルールも考慮して実装していたのだが、攻方最後・玉方最後の着手ルールについては意味がなさそうなので外した記憶がある。

左図は、第10回選手権決勝IS将棋-YSS戦。ここではIS将棋が勝ちを読み切っていたようなのでこれまで採り上げなかったのだが、これを分析してみることにした。

さて、本譜は▲31竜に▽同金の頓死なのだが、▽同玉でも簡単な必至が掛かるので、▽同金の方が、恐らく入玉可能性を見て探索値が高いために、YSSはそう指すことになったのだと思われる。

この局面の正確な「最短手順の必至」を読み切るのは相当のコストが必要なのだが、かなり微妙な図だ。 IS将棋の棚瀬さんの解説では、「▲31竜▽同玉▲23歩で必至」となっているが、更にそこから▽44飛[*1]と受けても▲33歩成までの5手必至。

また、余必至手順として、3手目から▲33歩成▽同金▲23歩までの5手必至もある。

 

因みに、この図を謎電で必至解図を行うと、次のような結果となった(Barton/3000+、置換表:1GB)。

--
{5,11}: 5.894秒:▲31竜▽同金▲33歩成▽同玉▲43飛▽34玉▲36歩まで7手必至
{5,13}: 9.550秒:同上
{5,15}:21.470秒:同上
{5,17}:42.517秒:同上
{5,19}:18.882秒:▲31竜▽同玉▲33歩成▽同金▲23歩まで5手必至
{5,21}:35.049秒:同上
{5,23}:76.580秒:同上
--

なお、▲31竜に▽同金は、▲33歩成▽同玉▲43飛▽34玉▲44金▽35玉▲33飛成▽46玉▲45金▽同玉▲56銀▽46玉▲47銀▽同玉▲25馬▽48玉▲49歩▽同玉▲58角▽48玉▲47馬▽59玉▲39竜までの23手詰があるのだが、解図パラメタが足りないと、7手目の▲36歩で必至と判断する。▽36同馬と取っても、▲45飛成▽同玉▲56金▽35玉▲34金▽25玉▲33金▽24玉▲34馬▽14玉▲15銀までの11手詰があるので、{5,11}で必至として解けてしまっているわけだ。 低いコストで勝ちを読み切れるという意味では、「長い詰みより短い必至」の格言の通りだが、逆転がない局面なので、そう言えるだけかもしれない。詰がある時は、きっちり詰まして勝ちたいところである。


[*1] ▽41歩と受けると、▲22金▽同金▲同歩成▽同玉▲33歩成▽同玉▲43飛▽34玉▲44金▽35玉▲33飛成▽46玉▲45金▽同玉▲56銀▽46玉▲47銀▽同玉▲25馬▽48玉▲26馬▽49玉▲58角▽同玉▲38竜▽69玉▲79金までの27手詰がある。

次の一手評価 (2)

テーマ:

今度は、IS将棋の棚瀬さんのところのコンピュータ将棋用問題集(全20問)も試してみた。結果は、パラメタを調整してすら12問しか解けなかった。これは凹む。解けたのは終盤か、明らかに簡単な問題くらいしかない。IS将棋は17(16?)問解けているらしく、この差は大き過ぎる。

 

唯一の救いは左図[*1]である。これだけは自慢出来るかもしれない。パラメタ{5,21}の設定の時、1手必至として約29秒で解けるが、指将棋モードでの必至探索では解き切れずタイムアウトを起こす。しかしながら、その途中結果を置換表に残したまま指将棋探索で再利用することで、▲13飛を最善手として指すことが出来る。

 

謎電は、▲13飛▽67香不成▲同金▽87馬▲78歩に▽13金なら▲同竜以下21手詰があることを前解図段階で辛うじて読んでおり、その情報が置換表上にあることで解けるようだ[*2]。なお、下線部は必至解図内で無駄受け判定の為の強制延長が行われている部分を示している[*3]。


[*1] あまりに嬉しいのでハデな図にしてみた(羽生さんですら指せない手だったとは)。

[*2] この現象を前解図効果(pre-search effect)と勝手に呼んでいる。

[*3] 双玉問題の場合、1手必至であることを読み切るためには、この手順を1回目の反復深化の中で読まないと正答できない。付け加えて、攻方が頓死していないことも(実際には不完全になってしまうが)読まなければならない。 


(追補訂) 05/04/13 18:25 いま調べなおしたら、なぜか正答問と正答数が違う。なんか減ってるような…手元の記録では、ooooo|oooxo|xoooo|oooox:17問なのですが、何故? しかも羽生さん▲33竜!?  これは困りましたね。 あ、棚瀬さん、読んでる?  まさかね(滝汗)


 (追) 05/04/13 19:40 ……灯台下暗し。トップページから検索一発で氷解。 いや、謎電は大したことないですよ、楽しみでやってるのと勝ちに行くのとは別次元ですから。

入玉宣言勝ち試験図

テーマ:

左図は、現実にはありえないのだが、入玉宣言勝ち試験局面(の一つ)として挙げてみる。
この図のポイントは、
・王手が掛かっている状態で、宣言しないこと(▲52歩と受けること)
・後手が次に王手以外の手を指した時、合法手がないからといって投了しないこと
の2つがある。
なんとなく嫌な予感がしたので、とりあえず作って試験してみたのだが、意図通りに動いたのでホッとしている。


参考までに、入玉宣言勝ちの条件について下に示す。
--
(a) 宣言側の手番である。
(b) 宣言側の玉が敵陣三段目以内に入っている。
(c) 宣言側が(大駒5点小駒1点の計算で)
先手の場合28点以上の持点がある。
後手の場合27点以上の持点がある。
点数の対象となるのは、宣言側の持駒と敵陣三段目以内に存在する玉を除く宣言側の駒のみである。
(d) 宣言側の敵陣三段目以内の駒は、玉を除いて10枚以上存在する。
(e) 宣言側の玉に王手がかかっていない。(詰めろや必死であることは関係ない)
(f) 宣言側の持ち時間が残っている。(切れ負けの場合)
以上1つでも条件を満たしていない場合、宣言した方が負けとなる。
(注) このルールは、日本将棋連盟がアマチュアの公式戦で使用しているものである。
以上の宣言は、コンピュータが行い、画面上に明示する。通信対局の場合は、「%KACHI」のコマンドを送信する。

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

テーマ:

 


本blogをご覧頂きありがとうございます。先週の結果は上表の通りとなりました。4月4日の爆発は、超の付く大御所サイト様2ヵ所からリンクされていたのが原因のようでした(汗) リンクありがとうございました(礼) 9日の爆発は新たにブログ登録したからだと思います。

今週も1日1記事くらいで進めていきたいと思います。


人気blogRanking(自然科学)
元祖ブログランキング(自然科学)