State of the Digital Shogics [最先端計数将棋学] -3ページ目

CycloneIII

ここのところ本業モードに入っていて殆ど更新してないのにも関わらずアクセスが爆発していたので原因を調べてたら、"CycloneIII"でググられてのリンクだったようだ。このブログが無意味にトップに来てたのにはビビった（汗）因みに"Cyclone III"でググると下位。僅か１文字スペースがあるか否かでここまで検索結果が違うというのも、微妙に問題がある気はする。それはともかく。

アルテラの本家ＨＰでは既にアナウンスされているが、やはり最先端計数将棋学的に書いておかねばなるまい。モノ自体は07/03/20に発表されていたようである。完全に本業に入ってたので全然気が付かなかった。

本家：http://www.altera.co.jp/products/devices/cyclone3/cy3-index.jsp

ASCII24：http://ascii24.com/news/i/hard/article/2007/03/20/667856-000.html

MYCOM journal：http://journal.mycom.co.jp/news/2007/03/20/540.html

Tech-On!：http://techon.nikkeibp.co.jp/article/NEWS/20070317/129062/

CycloneIII アプリ開発に対応したQuartusII Ver7.0が既にリリースされているので試してみようと思っている。ダウンロードセンタはこちら→http://www.altera.co.jp/support/software/download/sof-download_center.html

因みにCycloneIIIのスタータキットが\19k-。評価レベルでしか使えないが、ちょっとFPGAなるものを勉強してみようか、という方にはお奨めする→http://www.altera.co.jp/products/devkits/altera/kit-cyc3-starter.html

（但し、毎度のことながら発注してもすぐには手に入らないと思われる）

残念だったなライエル

ほーんと、残念だったなライエル。でもな、決して気を落とすんじゃないぞ、生きていれば良いことあるよ。はい、第17回選手権申し込み者リストを見て謎電の作者はコウフンしました。というわけで、

俺は二次で待ってるぜ　(笑)

うむ、何度言っても実に気持ちの良いイヤミな台詞だ。兎に角計算機将棋の神様に愛されていたのはサーマルメータ有岡選手までだったということだ。てか、KFEndが一次で戦うなんていうのは他の方々に迷惑な話であるから当然と言える。で、付け加えて、近年の計算機将棋のレベルは上がって来てるので、

SPEARが一次予選を突破出来ない確率は３割ある [*1]

と言ってライエルにキョーレツにプレッシャ～を掛けておくことにする。

さて雄伏２年、同期のアロンウルフ棚瀬選手、棚瀬将棋（仮）ってエントリになってますけど、仮称とは言えこのオーソドックスなプログラム名に「将棋とは独りで指すもの、独りで全ての責任を背負ってＹＳＳと闘って倒して優勝してこそ意味がある」という意気込みを感じます。マイムーブと共に期待しましょう。

資料集2006

CSAから資料集が昨日届いた。今年もまた正論をぶつけてくる輩がいる。06/04/19の週刊将棋（資料集のp.39）から引用する。

> その場合は強いプログラムを元にチップを作らないと意味はないのですが。

…だからさ、判ってるんだよ、んなことは!!

繰り返すか、普通!?

イジメ？新手のイジメ??

この審判員の人柄が全く信じられない[*1]謎電の作者だった。いや、もう謎電の作者的にはSPEARを倒せりゃそれで良いんですよ。FPGAはbitboardの100倍速いとか言ってやりますよ（涙）

[*1] 選手権参戦者の中で、最も人柄を信用されてないのは、実は「謎電の作者」なのだが、自分のことは棚に上げておくことにする。

ありがとう、マイムーブ西村!!

参戦２年目、余興とはいえＧＰＷ杯でSPEARを倒した注目のプログラムを、ここで紹介しようと思う。

マイムーブ

しかも、トータル順位がSPEARより１コ上というのがとってもクール。狙ってその順位ならファンタスティク。

ＧＲＥＡＴ　ＪＯＢだ！マイムーブ西村!!

貴殿のことを謎電の作者は決して忘れないだろう。で、彼の開発日誌を読むと謎電の作者的に興味深い話が実に多い。特に面白かった内容を引用しコメントしよう。

> ライエル先生曰く、SPEAR は「時間配分入れてるから、時間切れでは負けない」とのことでしたが切れそうに。

…中略…

> SPEAR 玉が詰まされたときは残り２秒でした。ライエル先生曰く「言ったとおり、切れ負けじゃあない」

まんずいがったなやライエル。山形大学工学部情報科学科助教授としての威信と尊厳が保たれてよぉ。切れ負けさこいたら例えプロフェッサ飯田の推薦があっても、教授への道は絶たれていたところである。てか、もしかして「残１秒になったら投了する」ってオチがあったのかもしれないが。でもな、ライエル。何で負けても負けは負けなのだよ。

> ライエル先生のＧＰＷでの発表だと BitBoard は非 BitBoard の２倍の速さとのことでした。

これは謎電の作者に対するライエルからの挑戦状だな (笑)

将棋は、時々ボクシングに例えられることがある。その理由は恐らく競技内容の激しさにあるのだと思う。計算機将棋は、特に選手権のような大会では一見計算機同士の闘いに見えるが、その実は人間同士の闘いである。またハングリィスポーツという意味でもボクシングに勝るとも劣らない。しかしながら、そういう見方になかなかならないので、最先端計数将棋学では参戦者をリングネームで呼んでいる。無論、その参戦者に断って名付けているわけではないが、その当人以外にはそれなりにウケているようである。例えばガルリ吉村（現審判員）の場合は、

・世界を獲った

・引退した

~~・老けて見える~~

というのが由来だが、コレはサーマルメータ有岡選手[*1]には好評だったようである。最近ではマエストロ柿木選手、ここのところ集中登場しているカメラマン山下選手[*2]など、リングネームとして市民権を得るまで謎電の作者は努力を怠らないつもりである。

さて、ここで最も重要な好敵手のリングネームを考える必要が出てきた。書くまでもなくReijer Grimbergen [*3]選手をどうするかである。当初、Reijer "嫌味" Grimbergenといったようにミドルネームを付けようと思っていたのだが、これは長ったらしく不適切だ。そこで、GrimbergenをGrim-berg-enと分解し、その意味を英語的に解釈してみたところ、リングネームは次のようになった。

ライエル恐氷山（おそれひょうざん）選手

謎電の作者は、これだ！と思ったね。今後、彼にプレッシャ～を掛ける時には、そのように呼ぼうと思っている。

[*1] 一般に判りやすいように？「エービーシー有岡選手」と呼ぶべきかも知れないのだが、謎電の作者としては、日本製品の信頼性を影で支えて来た彼の本業に敬意を表して、そう呼ぶことにした。

[*2] 今後、「ハイエンド山下選手」と呼ぼうかどうか迷っている。が、「カメラマン山下選手」が定着しつつあるので悩むところである。

[*3] この顔写真を見て思ったのだが、コレ、なんかサワヤカ過ぎない？

機械学習

ボナンザ保木選手の「局面評価の学習を目指した探索結果の最適制御」を読んでみた。なにやらえらく難しく書かれているような気がするが本質は単純だと思う。これで巧くいくとするなら、なぜ今までチェス系ゲームで画期的とも言える機械学習の成果がなかったのか不思議なくらいだ。保木選手とは面識がないので、これ以上のコメントは誤解を招きかねず、それは本意ではないので一旦遠慮する。

ところで某カメラマン山下選手は、選手権初日～決勝最終戦まで全身からオ～ラを発していた。その姿は、喩えるなら「星飛雄馬に向かって予告ホームラン出してる花形満」って感じだった。その自信と根拠が今をもって謎電の作者は理解できない。懇親会では「Bonanzaに負けたおまえら、今まで何やってたんだ!?(translated by 謎電の作者）」だったが、私はむしろ、

「Bonanzaに勝ったおまえさん、一体何やったんだ!?」

と尋ねたいところだ。ざっくり対Bonanzaチューニングとしか思えない。とすれば「少ないパラメタ＋手動チューニング」の職人芸の方が優るということになるのだが、それがいつまで続くか今後の選手権が見物である。←プレッシャ～（笑）

StratixIII

重複してしまうが、最先端計数将棋学的に書いておかねばなるまい（笑）

http://www.altera.co.jp/corporate/news_room/releases/products/nr-s3release.html
http://www.altera.co.jp/products/devices/stratix3/st3-index.jsp
http://www.altera.com/literature/br/br-stratixIII.pdf

ＥＳ品が来年第３四半期出荷と少々未来の話になっている。但し、設計だけならQuartusII Ver6.1を使って今からでも可能だ。明日の選択肢のひとつとして最先端野郎に謎電の作者はこのデバイスを推奨する。
少し話は逸れるが↓のアナウンスの意味の判る方は、完全に業界通だ。

http://www.altera.co.jp/corporate/news_room/releases/products/nr-gigabeat.html

師匠～

ＧＰＷ杯2006の結果を見た。

師匠～、俺は信じてましたよ（涙）

アレにはいつか計算機将棋の神様の天罰が下ると思ってました。ドクタ橋本アーンド北陸先端大も信じてました。ちなみに師匠は、私が師匠と呼ぶのを嫌がられているようです。そこで今後は、「マエストロ（巨匠）柿木」とお呼びすればよろしいでしょうか？

勝負手生成

結局、GPWには行けなかった[*1]。演目を見ると、

> コンピュータ将棋におけるモンテカルロ法の可能性

ってのがあることに今気が付いた。やるなドクタ橋本アーンド北陸先端大。どういう内容だったのかさっぱり判らないが、カメラマン山下選手に対して完膚なきまでにプレッシャ～[*2]を掛けて頂けたのではないかと謎電の作者は信じている。

さて、将棋へのモンテカルロ法の適用について少し思うところを書こうと思う。

秘密基地でも書いたが、モンテカルロ法は適用範囲が非常に広いものの、基本的に「正攻法では解けない問題に対して用いる」ことが効果的である。例えばπの値をモンテカルロ法で求めるより、既に判っている計算式で求めた方が遥かに低コストだ。正攻法があるなら、それを使うに越したことはない。（モンテカルロ法の使い方にも因ると思われるが）精度とコストの兼ね合いを考えた時、モンテカルロ法を将棋に用いるのは不利な筈だが、例外的な使い方が考えられる。

囲碁プログラムCrazyStoneでは、「勝率をベースにした評価値を使う」という面白い応用を行っている。単に地を評価した値ではなく、勝率を基準にした値を使うやり方で成功例を残したが、この考え方はケース次第で将棋にも活用できる可能性がある。そのケースとは「どう指しても勝ちがない局面で、どう指すのが最善手か」を決める基準で用いる。

どう指しても勝ちがない局面。言うまでもなく、相手が最善手を必ず指してくることを前提とすれば、自分は負ける以外の道がない局面だが、そのような局面であっても「最善手は存在する」というのが専門棋士的な考え方であるらしい[*3]。そのような場合、正攻法での（常識的な）探索では、全ての手が「負けの結論値」しか戻って来ないので手が決められないし、安直に「最も負けを引き伸ばす手」を最善としてしまうと、大抵はジリ貧でミジメな負け方を選ぶことになり、つまりは汚れた棋譜を残すことになる。

しかしながら、自分が負けであることを悟った（あるいは極端に形勢が悪い）時に、勝率をベースにしたモンテカルロ探索ならば、「相手は最善手が指せない（指せるとは限らない）」ことを前提にした探索・評価値となり得るので、勝負手を放つ基準に用いる解決案のひとつになる。無論、自分より相手の方が（特に終盤が）強い時は勝ちを拾うことは難しいが、逆に終盤力の低い相手に対して相当有力な手法になると考えられる。具体的なアルゴリズム・実装法はこれから開拓するしかないものの、基本的なアイデアは使えそうである。

[*1] だが今、横浜に居る。デジカメを持ってくるのを忘れてしまい困っている。

[*2] 恐らくは、G.W.BushがKim Jong-ilに対してプレッシャ～を掛けているのと同じ位、モーレツ且つキョーレツだったと思われる。ところで最先端計数将棋学では一ヵ月以上に渡って「無言の圧力」という新技を掛けてみたのだが、効果の程はどうだったか。

[*3] この件について、十数年前に田中(寅)と議論になり、「よし、ラチが明かないからカラオケで勝負だ!!」ということになった記憶がある。かなり記憶が曖昧だし、話作ってる気もする(笑)

置換表 (7)

ＣＳＡ例会議事録がＭＬで流れてた。何か微妙に不思議なことが書かれてあったので、これを今回のネタにしようと思う。

さて、「ハッシュのクリア」とある。置換表の初期化のことだと思うが、謎電では起動時のみしかフィジカルなイニシャライズ（０クリア）は行っていない。だからと言って過去の探索記録を再利用しているわけでもなく、指将棋では探索の直前にロジカルなイニシャライズを毎回行っている。これは「一瞬」で済む。議事録では「ばかにならない」とか「クリアしなくてもよくないか」とあるので、

ＹＳＳでは毎回置換表全体を（物理的に）クリアしている

という解釈になるのだが、そうなの!? もう何年も前の話になるが、この件はＫＦＥｎｄの有岡さんとも議論したことがある。実際ＧBytes単位のメモリを置換表の為に確保し、それを毎回フィジカルにイニシャライズするのは時間コストが馬鹿にならないので、当然何かしらの工夫が必要だ。で、謎電では具体的には次の様な方法でこれを解決している。

・置換表の全てのレコード上に2bytes(unsigned short)のフィールドを用意する。仮にこれをrec.uとする。

・また、置換表利用回数を管理する2bytes変数を用意する。仮にこれをnとし、初期値は０とする。

・プログラム起動時のみ、置換表用メモリ確保と共に全体をフィジカルにイニシャライズする。

　（all 0x00 を書き込む／仮想記憶域から出す為に0x00以外の値をその前に一旦書いておくという裏技もある）

・置換表をロジカルにイニシャライズしたい時は、単にn++とする。

　（例えば指将棋の探索開始直前に、これを１回実行する）

・置換表内の任意のレコードrecが未使用かどうかは rec.uとnの比較で判定する。

　（rec.u==nで使用済、rec.u!=nで未使用を意味することになる）

・置換表内の任意のレコードrecを使用済にしたい場合は、そのレコードのフィールドrec.uにnを代入する。

これだけである。置換表内の各レコードが未使用か否かを「フラグ」で管理するのではなく「値」で管理しているというわけだ。この手法は微妙な問題を孕む（この例の場合、65536回前に初期化した筈の結果を「使用済」と判断してしまうことがありえる）のだが、実用上は問題ないものとして放っている。わざわざ説明するまでもない一般的な手法だと思われるのでこれまで書かなかったものの、プレッシャ～になるかなーという気がしたので一応書いてみることにした(笑)

【余談】これはそれほど効果があるわけではないのだが、置換表のような巨大なメモリ領域を初期化したい場合に最も高速なのはmovdqa命令を巧く使うことである。但し、16バイトアドレス境界合わせをしないとaccess violationを起こすし、memset()と比べて数％しか速くならない（DRAMが相手の場合）。更に余談だが、AMDのプロセッサではprefetchwを使えば多少は速くなると思ったのだが、２代目Athlonからハードウエアプリフェッチが効いているようで、現プロセッサでは効果が薄い（殆どない）ようである。

【補足】付け加えて、詰将棋での千日手判定は（王手を掛ける手番時の）駒損同一盤面判定と併用（一発同時判定）が可能なので、千日手判定だけを外しても解図効率が上がる筈がないのだが、恐らく実装が謎電と異なるのだろうと思う。

【更に追記】出席者の中に橋本博士（以後、ドクタ橋本と呼ぼうかと。あと飯田教授は、プロフェッサ飯田ですね、そのまんまですが）を発見。十二分にプレッシャ～を掛けていただけたのではないかと謎電の作者は分析している。