電王戦 --- 将棋電王トーナメント --- やねうら王特設ページ
■ 2013/10/13 6:00 特設ページはじめました
とりあえず、第三回電王戦の将棋電王トーナメントに出場する「やねうら王」の開発状況などをここに書いていきます。(定期的に追記していきます)
将棋電王トーナメント 出場ソフト http://ex.nicovideo.jp/denou/tournament/soft.html
昨日、仕事が一段落したので久々にAppStoreのランキング見たら、テイルズオブハーツＲが発売になってて、しかも15日まで半額セールなので速攻購入して13時間もやってしまった…。もうしませんもうしません。＞＜
明日から頑張ります…。
■ 2013/10/13 7:30 やねうら王の特徴
ドワンゴの電王戦の担当者から「出場ソフトの特徴」などについて質問メールが来ていたので「ソフトの特徴」として以下のように書いておいた。(公式サイトでの公開および当日の紹介で通知されるらしい) ちなみにまだ以下に書いてあるようなことは何もできてないのだが…。明日から頑張ろう…。
・世界最速の指し手生成ルーチン搭載
コンピューター将棋の指し手生成ルーチンとして世界最速を誇り、
発表以来、いまだに抜かされたことはない(気がする)、世界最速の指し手生成ルーチン搭載。
・必勝！やね裏定跡
本大会のために考案された対コンピューター将棋戦略。
コンピューター将棋のハマりパターンを詰みの局面までインプット。
勝ちパターンにハマればどんな強豪ソフトだろうとまさに一発KO。
・究極進化！やね裏学習メソッド
従来将棋ソフトのように評価関数を棋譜から学習するタイプの学習ではなく、
一局一局から定跡を自動学習するやね裏学習メソッドを採用。
一局ごとに進化する世界初のコンピューター将棋ソフト。
・超軽量！やね裏評価関数
強豪コンピューター将棋ソフトが評価関数を重量化するトレンドに逆らい、
あえて究極の軽量化を追求したやね裏評価関数。軽さこそ正義！速さこそ我が魂！
■ 2013/10/14 5:30 やね裏学習メソッドについて
定跡の自動学習の仕組みを追加しなければ、プロ棋士にソフトを貸し出して事前研究をされたのでは公式対局において勝てる可能性はグッと減る。そこで、今回出場するすべての将棋ソフトは「やね裏学習メソッド」を採用すべきである。そのためのアルゴリズムをここに書いていく。すこぶる簡単に実装できるので今回出場するソフトの作者は実装すべきである。
まず、将棋において、強い人の指す指し手と弱い人の指す指し手との違いは何かということを考えてみよう。
私がR1500(アマ初段)程度だったころ、Bonanzaと対局すると中盤で5手ぐらい進めると明らかに劣勢の局面になった。また5手戻して、別の手を指すのだが、それでも5手ほど進めると同じく劣勢の局面になった。それをしばらく繰り返すが、一向に形勢互角の局面にならず、将棋というのは、なんと難しいゲームなのかと思った。
指し手はどの手もこの手も悪手ばかりなのだ。それは自分の将棋観を根底から打ち砕かれるような衝撃であった。事ここに至り、自分は将棋というゲームを誤って認識していたのだと悟った。
ハイレベルな対局において素人が思っているほどの指し手に自由度はなく、広大な砂漠のなかから一粒の種を探すかの如く、悪手ではない手を探さなければならない。
これを図にすると次のようになる。
大雑把ではあるが、言いたいことは伝わるはずだ。ある局面において、R500の人が選ぶ指し手の統計をとったときに90%まで網羅しようと思うと20手ぐらいあるとしよう。
R1000の人だと、10手ぐらいしかない。R2000の人だと5手ぐらいしかない。R3000の人だと3手ぐらいしかなく、神様レベルだと1手か2手になると。それが上図の意味するところである。
もっとも、R500の人は先まで見越すことはできないので、実戦的にはR500の人が思いつくような指し手の候補のなかに、R3000の人が「必然手」だと思うような手が含まれていないことは多々あるのだが、話を簡略化するためにそれについてはいまは考えないことにする。
上図を見ればわかるように、最終的に同じ指し手を選んでいたとしても、R500の人が選んだのと、R3000の人が選んだのとでは意味合いが異なる。R3000の人が「この局面ではこの一手」だと思うような手を、R500クラスの人の集団のなかで、その指し手を選ぶ人の割合は10%程度かも知れない。R500クラスの人が同じR3000の人と同じ指し手を選んでいたとしても、前者はたまたまくじ引きで10%の確率で当たったにすぎず、後者は100%の確率で当たるくじ引きであったと言える。
将棋というのは、このように1手ごとに最善手を引くためのくじ引きをしているようなものであり、少しでも当たる確率の高いくじ引きをしないと不利になりやすいというゲームだと言える。
さて、これをコンピューター将棋の探索と結びつけて考える。ほとんどのコンピューター将棋は反復深化法と言って一手ずつ探索深度を深くする探索手法をとっている。これは、探索深さNの最善手は、それより一手浅く(N-1の探索深さで)探索したときの最善手と一致することが多く、それゆえ、一手ずつ深くしながら、各局面での最善手を置換表(実体はハッシュテーブル)と呼ばれる表に格納しておくと、一手浅いときの最善手からまず先に探索することで探索時間を短縮化できるからである。
まともな評価関数においては、この探索深さが1手深くなるごとにR200ずつ程度上がると言われている。なぜ探索深さを深くすると強くなるのか、その原理的な説明は誰にも出来ない。(それらしい数理モデルで説明することは出来るかも知れないが…)
この件について、篠田 正人氏(奈良女子大学理学部数学科教授にして将棋のアマ強豪。コンピューター将棋にも造詣が深い)に以前、私は直接尋ねてみたことがあるが、私の期待するような回答は得られなかった。(「原理的なことはわからない」という回答であった)
また、まともでない評価関数であると、探索深さを深くしても強くならないのだが、しかし、駒得のみの評価関数であっても探索深さを深くすることにより強くなることは実戦により証明されており(floodgate上での駒得だけの評価関数による実験として「ひよこ将棋」がある)、この場でまともでない評価関数を持ちだしてきて反例を挙げることには何の意味もない。駒得のみの評価関数より粗悪な評価関数など現実的に採用するはずがないのだから。
さて、そう考えたときに、反復深化の深度(イテレーション回数。以下、単にイテレーションと書く)を少しでも上げるにはどうすれば良いのかという話になる。
どの将棋ソフトでもイテレーション3だとR500、4だとR700、5だとR900、…のようにイテレーションを上げるごとに強さがほぼ線形に上がっていく。つまり、同じ思考ルーチンが導き出した答えであっても、R500の指し手、R700の指し手のように、イテレーション回数が多い(思考時間を増やした)指し手のほうが強い指し手である。
よって、同じ思考ルーチンであるなら、イテレーション回数が少ない指し手よりイテレーション回数が1回でも多い指し手のほうが圧倒的に価値が高いと仮定して構わない。
この事実を用いてどのように序盤定跡を学習させるかだが、上の仮定があり、また、本大会のように、マシンスペックが固定化されているのであれば、単に次のようにすれば良い。
tは、今回の指し手のための思考時間とする。もし、データベース上でこの局面が登録されており、過去、そのときこの局面において思考した時間がtより大きいならデータベース上に登録されている指し手を選択し、今回の指し手のための思考を終了。
思考時間が大きいほうがイテレーションはたくさん回るはずだから、そのときの指し手のほうが圧倒的に優れている(上記仮定より)ので、こうしてしまって何の問題もない。
これにより、一度遭遇した局面の思考時間が短縮化され(定跡扱いで即指しになる)、前回と同じ変化(同一の棋譜)であっても終盤のために持ち時間をたくさん残すようになる。その結果、終盤でたくさんイテレーションが回り、前回より良い手を指せるようになるという仕組みである。つまり、プロ棋士が事前研究をしてきても、研究と同一手順では勝てない(可能性が高い)。
また、本大会のようにPCのスペックが固定化されていない場合でも、nps(探索速度)やPCのコア数から、現在のマシンの1秒が、基準マシンの何秒に相当するかは計算できるので、基準マシンの何秒に相当するかという単位で上記の処理を適用してやれば、PCのスペックが固定化されていなくともこのアルゴリズムが適用できる。
これが「やね裏学習メソッド」の全貌である。簡単に実装できるので是非、他のコンピューター将棋の作者も実装して欲しい。
なお、コンピューター将棋では従来、定跡は独自形式のファイルとして持たせることが多かったが(そのほうが速いし、それほど複雑な入出力は必要なかったので)、私は今回SQLite3で行なう。
DBのアクセス時間はもったいないが、しかし今回の持ち時間であれば相対的に無視できる程度だろうし、また一局終了ごとに定跡として指し手をDBに登録していかないといけないので、独自のファイル形式だとそのへんの処理を書く手間やメンテナンスのコストなどを考えると、割に合わないからである。
■ 2013/10/14 16:00 やね裏学習メソッドII(局後の自動検討)について
コメント欄のほうで、やね裏学習メソッドでは、「(ボンクラーズが定跡DB通りに進行して)富岡流の必敗局面に足を踏み入れた」ものや、「阿部四段が習甦に対して行った先手番一手損角換わり」のようなものは回避不能ではないかという指摘がありますが、これに関しては次のようにするだけで回避できます。
終局のときに、定跡DB上に自分の指した指し手とそのときの考慮時間を記録するわけですが、コンピューター側が負けたとしたら、それぞれの自分がその一局で指した局面をひとつずつ調べ、それらの局面において、思考時間をDB上に記録されている指し手の思考に使った時間の2倍の時間を用いて思考し、その指し手を定跡DB上に記録しておくだけで良いです。(この局後の自動検討を「やね裏学習メソッドII」と呼ぶことにします。)
これで同じ変化で負けるごとにそれぞれの局面での思考時間は2倍・4倍と増えていくので、原理的には、何度か同じ手順で負け続けていれば、いずれ新しい手を指すでしょう。
まあ、この局後の自動検討で1手の思考時間が数時間ぐらいになってしまいますと、さすがにどうかと思いますが、そのへんはSQLite3を使っているので、1手の思考時間として数時間使っている局面のみリストアップして人間が見て手心を加えてやるぐらいのことは出来るでしょうし、あるいは局後検討で時間を消費しすぎている局面が出現した時点でalertを出し、ソフトの作者にメールを送信して知らせる、みたいなことも出来ます。
将棋倶楽部24や将棋ウォーズのようなオンライン対局サイトでコンピューターに自動対局をさせる上で(一日に何千局も自動対局させることを想定)、こういう自動学習〜alertの仕組みは必要不可欠だと私は考えています。
また、このような「やね裏学習メソッド(定跡自動学習)」および「やね裏学習メソッドII(局後自動検討)」を搭載して、floodgateのような他ソフトとの自動対局サイトに放り込んでおけば、他のソフトのハマり定跡を自動発見してくれるというメリットがあります。
この発想こそが、「必勝！やね裏定跡(対コンピューター将棋戦略。詰みの局面まで入力された定跡)」につながっていくのですが、それについてはまた次回にでも。
■ 2013/10/15 9:00 やねうら王 Q&A
コメント欄がごちゃごちゃしてきたので、整理するため、返信が長くなるような質問のコメントは削除して、以下にQ&Aとしてまとめてみました。コメント削除の件は悪しからずご了承ください。
また大会直前までコメント欄にて質問等は随時受け付けています。(私も参考になるものもあるので) 皆様、よろしくお願い致します。(いただいた質問は整理してここに追記していきます。)
Q) ５位に入賞できるかわからないのにプロ棋士との対局のための対策を練っても仕方ないのでは？
A) 客観的に見て、やねうら王は５位に入賞できる可能性はなくもないので、プロ棋士への礼儀としてそれなりの対策を練っておく(それができないなら出場しない)べきかと私は考えています。
Q) プロ棋士がやねうら王に対して再現将棋(事前研究で勝った棋譜を持ってきて対局させる)場合、やねうら王はそれを回避できますか？
A) 中盤ぐらいまではDBに登録されている手の進行となり、その部分の思考時間はゼロ(ルール上は1手につき1秒消費)になります。100手で終局する将棋の50手目から、DBに登録されている手から離れ、実際に思考するとしたら、2倍の持ち時間が与えられているのと同じで、2倍の時間をかけて思考すればR100〜150程度強くなるのは実証されてますから、この分だけ強くなります。
Q) 序盤でのコンピューター将棋側の悪手は思考時間を2倍にした程度では、軌道修正不可能では？
A) 同一変化の棋譜を2度、3度試していれば、それらの局面についての事後検討時間は4倍,8倍のように上がっていきます。そうすればR200〜300、R300〜450のようにそれらの局面でのやねうら王の棋力は瞬間的には(局後検討をした局面では)上がることになります。
少しぐらい不利な局面からスタートしたとしても、未知の局面になってかつ練習将棋のときにくらべて、数手の間だけでもそれだけ強い相手にバトンタッチされれば、勝負の行方はわからないのではないでしょうか。
Q) 残念ながら、指し終わったら電源を切られて意味ないような気がします・・・・。連続対局なら、CPUを学習に割り当てられません。
A) 連続対局であろうと電源が切られようとUSIプロトコルの次のisreadyに対して局後の自動学習が終わるまでreadyokを返さなければいいだけです。それがプロ棋士に貸し出すソフトに対する規約で禁じられているなら話は別ですが、そのへんは私にはよくわかりません。このへんは、設定で変更できるように作っておき、運営の人と話し合って、許される範囲で局後検討機能を有効にしたいと思います。思考設定の変更は思考ルーチンの改変ではありませんから、都度設定を変更するのは許されるかと思います。
Q) readyok返そうが返さまいが電源切られたら(強制終了されたら)学習できないですよね？
A) そこは、DBに保存してあって、次回起動時に局後検討が未消化の局面があるかqueryかけて調べればいいだけです。(局後検討オプションが設定でオンのときのみ)
Q) 局面再現をさせないためなら得した時間をすぐ使ったほうがいいように思うのですが
A) 定跡DBに載っていたので即指しできて30秒得したら、次の手番ですぐにその30秒も加えて思考して、早い段階で研究局面から離れたほうが価値が高いという意味でしょうか。そういう考え方も成り立つと思いますが、統計的に、序盤は思考時間変えてもあまり指し手に変化が出ないのですよね。思考時間が利いてくるのは主に中盤以降ですね…。(よくわかりません。)
Q) やね裏学習メソッドIIなのですが、現実的に正しい敗北対策に収束するのでしょうか…
A) やってみないとわかりませんが、2倍の時間を費やせばR150程度上がるというのは絶対的な真実なので、R150上がった結果、ハマり局面に突入して負けるなら、まあそれは不運としか言いようがないと私は思っています。
コンピューターの苦手な入玉将棋など、思考時間をいくら増やしても全く強くならない展開もありえますが、まあ、それは別の課題でして、やね裏学習メソッドの問題ではないかなと思います。
Q) 電王戦時に貸し出し時と思考設定すら変えられない可能性もあるのでは？
A) 局後の自動検討ですが、その棋譜の全局面を調べなくとも、評価値が傾いた周辺の数手だけでも局後検討する時間があれば全然違ってくると思います。USIのisready(対局準備が出来ているかどうかの問い合わせ)に対して局後検討を続ける設定とは別に、(USIプロトコルの)gameover後、isreadyが送られて来るまでならば局後検討などをしていても許されると思いますし。(これも設定でする/しないを変えられるようにしておこうと思いますが。)
■ 2013/10/16 9:00 やねうら王開発再開！
本日から開発を再開する。まずは3年前のソースコードを掘り起こしてきてVisual Studio 2012でコンパイルが通るようにするところからなのだが…。
実装予定の項目はこうだ。
1) ３年前に仕込んだバグ取り(1日)
2) やね裏学習メソッド、やね裏学習メソッドIIの実装(2日)
3) やね裏定跡の入力(2日)
4) やね裏評価関数のパラメータ学習(2日)
5) 探索部をStockfishのアイデアを元に改良(5日)
1)〜4)が無事終わったら、一応、出場はする。そこまですら実装が終わらなければ残念ながら出場はキャンセルである。
■ 2013/10/16 21:30 開発環境整えるのも大変だという話
Windows Server 2012のHyper-Vのゲストとして同OSをインストールして、そこでやねうら王の開発をしようと思い、丸一日かけて開発環境を構築していたのだが、以下のバグに遭遇した。
1) Windows Server 2012はコマンドプロンプトでの外字の処理にバグがあって化ける。
2) Visual Studio 2012(SP3)のプロジェクト、read-onlyになっているソースファイルに対してコンパイル時にwarningが出る。
以前の開発時には思考ルーチンのデバッグのために外字を使って、コマンドプロンプト上で直接盤面を表示させていたのだが、これが1)のせいで出来ない。Windows Server 2012にもなって誰も外字なんか使っていないのかも知れないが、それにしてもひどいバグだ。このせいで、コマンドプロンプトを使ったデバッグがかなりやりにくい。
2)は自作のプリプロセッサ経由でソースコードを生成していて、その生成されたソースコードを間違えて編集してしまわないように、生成後のソースコードはread-onlyにしているのだが、Visual Studio 2012のバグにより、これに対してwarningが出る。このバグ、Visual Studio 2010のときは、SP2あたりで修正されたはずなのだが、新しいVisual Studioになって、またバグを仕込みなおしたのか。ホント、勘弁して欲しい。
その2点を除けば、とりあえずビルドは出来るようになった。
それから、やねうら王のソースコードはいま確認したら2MB程度あった。泣きそう。このソースコードの詳細、思い出すだけでも大変だ。あと、前回開発時に大改造しようとして、改造しかけた形跡が至るところにあって、思考ルーチンがまともに動かない。revert(以前のバージョンに戻すこと)したほうがいいのだが、きちんと動くバージョンのソースコードがどれだかもわからない。仕方ないので明日は、手作業でrevertするところからである。
評価関数に変更を加えた場合、学習に2週間程度かかるので、評価関数の変更をするならもう2,3日しか期日がないのだが、ご覧の有様である。
■ 2013/10/17 23:00 定跡あり×定跡なしの勝率
定跡DBがないと序盤で思考時間を取られるので、ずいぶん損をする。本家Bonanzaでも、定跡あり vs 定跡なしだと定跡なしのほうはずいぶん負け越すのではないかと思う。
→ 2013/10/18 24:00 試してみました。5分切れ負け100戦。60-2-38。(定跡ありから見て60勝、38敗、2引き分けの意味) 定跡がないとR50〜R70程度低下すると言って良さそうです。
→ 2013/10/19 16:30 さらに100戦。53-2-45。
問題は定跡DBなし×なしの戦いで、これだと同じような戦いばかりになる。並列探索をしているので、まったく同じ指し手にはならないが、似たような進行になる。定跡DBがないと(古いバージョンと)自己対戦によって、改良が正しく行えているかを評価するということすらできない。
やねうら王はいまこの状態で、バグ取りすらままならない。そこで、可及的速やかに定跡DBを搭載しなければならない。明日頑張ろう…。
■ 2013/10/18 21:00 SQLite3導入完了
間々に仕事が入ってくるので、コンピューター将棋の開発に専念できない。今日は2時間ほどしか時間がなかったのでとりあえずSQLite3を導入して、C++から呼び出せるようにした。
SQLite3だがx64用のdllすら用意されて無くて自分でコンパイルするところからやったのだが、x86環境でも動くようにしたい。これを真面目に考えだすと結構面倒である。
sqlite3はpublic domainらしいので、sqlite3.cのソースコードをプロジェクトに入れることにした。結局のところ、これが一番楽だ。実行ファイルは600KBほど増加した。(Visual Studioのソリューションに追加し、sqlite3.cはプリコンパイル済ヘッダーを使わない設定にすればコンパイルが通る。)
速度的には、トランザクション開始〜300バイトほどのテーブル行のINSERT 10万回〜トランザクション終了が10秒かからない。速すぎて驚愕。これなら将棋の対局中にデータを都度INSERTしていき、試合終了時にトランザクションを終了するようにしたとして、終了処理として1秒かからない。
それはそうと、SQLite3用のWindows用の管理者ツール(phpMyAdminみたいなもの)が無くて困った。PHPで書かれているSQLite3用のツールは出来が良いのだが、開発機にPHPの実行環境をインストールしたくないので、単体ソフトウェアとして動作するものを探したのだが、これが、「このソフトはBLOG型の表示ができない」「このソフトは、テーブルのデザインがGUI上で出来ない」「このソフトは、テーブルのダンプができない」など、それぞれのソフトがどこか少しずつ機能が足りていない。複数のソフトを組み合わせてやっとなんとか使える状況である。
まあ、今回はそんなに複雑なテーブル設計ではないのでデバッグ作業は問題とならないのでこれで良しとする。
■ 2013/10/19 22:00 npsが知りたいなら実際に探索しちゃいなよ
局後検討のためにそのマシンのnps(秒間の探索ノード数 ≒ そのマシンの探索能力)が必要だ。
これをCPUのクロック数とスレッド数から概算で計算しようと思っていたが、RDTSC命令とか使うと、いまどきのPCはspeed stepとか言ってCPU利用率が低いときに周波数を落とすのでこのへん一筋縄でいかない。CPUのベンダーIDを調べようと思うとCPUID命令が必要なのだが、x64になってVisual C++はインラインアセンブラをサポートしていないのでこの命令を呼び出すだけで一苦労である。
結局、システム情報を取得するにはWMI(Windows Management Instrumentation)というテクノロジーを使うのが一番簡単なのだが、このWMI、PowerShellのようなスクリプトから呼び出すのは容易なのだが、C++から呼び出すには一苦労である。
仮にそこでCPU名とクロック数が得られたとして、そこからnpsを概算で求めるにはCPU名ごとのnpsが書かれている表みたいなものが必要になる。おい、そんなものどこから用意するんだ。YSSベンチ*1か？
これらのことを考えると、初期局面で実際に探索してnpsを計測するほうがよほど確実で手っ取り早いことがわかる。というか、わかった。今日、数時間も費やしてたったそれだけのことがわかった。泣きそう。
■ 2013/10/20 12:00 いまどきこんなバグがOSに残っているだなんて
Windows Server 2012のコマンドプロンプトで外字の表示が崩れると書いたが、外字どころか、2バイト系の記号が全般的に崩れる。(コードページ 932(SJIS),MSゴシックにて確認) printf("□□"); すらまともに表示できない。これのせいでデバッグがままならない。
いまどき、OSの開発時のテストも大部分が自動化されているのだろうけど、こういう「表示が崩れる」というようなテストは自動テストが書きにくく(そもそも特定のコードページ、特定のフォントで生じる問題であるなら事前にテストが書けない意味もあるし)、テストがザルになっていたりするのだろう。なかなか興味深い事例ではあるが、いまこの状況においてはいい迷惑である。
■ 2013/10/20 12:30 将棋所のquit問題
コンピューター将棋のGUIとして将棋所という代表的なソフトがあり、機能性・操作性に優れているので、ほとんどのコンピューター将棋の開発者はこのソフトを用いている。このソフトはUSIプロトコルというプロトコルで思考エンジンとやりとりをする。いまUSIプロトコルはあまり問題ではないので、詳細は省く。
問題は、このやりとりが、標準入出力経由だということだ。つまり、思考エンジンは、printfで標準出力に出力し、将棋所からのメッセージはfgetsで取得するようなプログラムにさえしておけばあとは将棋所がなんとかしてくれるという仕組みである。
つまり将棋所は、子プロセス(?)で起動させたソフトの標準入出力をリダイレクトしているわけであるが、Windowsではこれは匿名パイプ(anonymous pipe)で行なう。ところがWindowsの匿名パイプはいろいろ仕様が嫌らしい部分があって、子プロセス側でアクセス違反があると親プロセスを巻き込んで落ちたり、その匿名パイプが切断されたときにprocessがkillされたりする(気がする)。詳しく調べていないのでよくわからないが、思考エンジンにバグがあると将棋所を巻き込んで落ちることがあり、大変デバッグがしにくい。
それはそれとして、将棋所では対局後、quitメッセージが送られてくるのだが、そのあとこの匿名パイプが切断されるので、思考エンジンが思考を続けることが原理上出来ない。局後の自動検討は将棋所を使う限りは不可能だ。quitが来る前に自分で別のプロセスを勝手に起動しておけば良いのだが、それはそれで、なかなかお行儀の悪いソフトである。
SQLite3は複数のプロセスから同時にDBのファイルをopenすることは想定されていないので、局後検討用のプロセスがこのデータベースファイルにアクセスしていると、次の対局の時に思考エンジンがDBにアクセスできない。自前でmutexみたいなもので排他処理をしないといけない。
まあ、それくらいやってもいいのだが、局後の自動検討用のソフトは自前で盤面を表示しないといけない。(しなくてもいいが、するべきだろう) これが大変である。コマンドプロンプトは前述のように表示がバグっているし、また、ユーザー環境に外字をインストールしてもらうわけにもいかない。そうなってくると、HTMLで盤面を出力してそれをブラウザコンポーネントでレンダリングするのがお手軽であるが、そういうUIの部分を書きたくないからUSIプロトコルでやりとりをしているのに、本末転倒である。
さらに、将棋所には、思考エンジン設定のダイアログにテキストボックスやチェックボックス、ボタンなどを表示するための手段がある。(setoptionコマンド) しかし、ボタンを表示してもボタンが押されたときにoptionコマンドが送られてくるのだが、このときに思考エンジン側からinfo stringで途中経過を将棋所に表示してもらおうと送信しても、それが表示されない。
おそらく、将棋所の作者はボタンが押されたら思考エンジン側は独自のダイアログを出すなりする用途を想定しているのだろうけど、そもそもそういう独自のダイアログとかログ表示ウィンドゥとかを出す手間が惜しいから標準入出力を使っているのであって、ここで思考エンジン側が自らWindowのメッセージループを自分で回して、自分でダイアログを表示して、自分でそこに途中経過の表示をしなさいというのはどうも首を傾げざるを得ない。
info stringではなく、デバッグ用のウィンドゥを将棋所側で出してくれて、そこに表示するためのコマンド(info debugなど)が用意されていないと開発者的には非常に辛い。将棋所はこのGUIを用いて思考エンジンと対局するユーザーには優しい作りだが、開発者には比較的厳しいものがある。
次に、将棋所で対局中に途中中断をするとquitメッセージが送られてくるはずなのだが、中断時にquitを送ると同時にprocessがkillされているっぽく、終了処理をさせてもらえない。前述の匿名パイプが絡んでいるのかも知れないが原因はよくわからない。なかなか開発者的には厳しい作りになっている。
とりあえず、以上のような理由から、将棋所で局後検討を実現するのは現実的ではないという結論に達した。局前検討(isreadyのあと応答を返さずに検討)は出来る。これは通常対局では無意味だが、自動連続対局時には意味があるだろう。また、floodgateに参戦させるときは、対局終了後、すかさず次の対局のためのisreadyが送られてくるので、次の対局までの空き時間を利用して自動局後検討をすることは可能である。
■ 2013/10/20 13:45 棋譜からの学習について
とりあえず、やね裏メソッドI,IIの実装と、やね裏定跡の入力は明日ぐらいに終わらせるつもりではあるが、明日で終わるかどうかよくわからない。あと、3年ぐらい前に探索部をいじくりまわしたときの弊害で何やら指し手がおかしい。根が深そうで、このデバッグにどれだけ時間がかかるか想像がつかない。
評価関数はBonanzaの3駒関係から少し変更した。Bonanzaのソースをいじって、先週、Bonanzaで棋譜からの学習をスタートさせた。これがまた遅く、DEPTH=3で、4コアのマシン(4年前に購入)だと3万局で１回のイテレーションが48時間ぐらいかかる。(2013/10/21 訂正。実際は1イテレーション20時間強ぐらいの模様。) うわぁぁ…。こりゃ、大会当日までに値が収束するかどうかも怪しいな…。
それからさっき、急ぎの仕事が入ってきたので10月22日から4,5日ほど時間が取られる可能性が濃厚だ。こりゃ、下手するとデバッグが終わらんな…。
とりあえずそんな状況のなか、綱渡りのようにしてやねうら王の開発をしている。
■ 2013/10/20 21:20 floodgateの2013年度の棋譜
今日も途中で仕事が入ってきて、1,2時間ぐらいしかやねうら王の開発ができなかった。やねうら王で使う定跡の入力のため、floodgateから棋譜をダウンロードしてこようと思ったら、2013年度分の一括したファイルがなくて、仕方ないからクローラー自分で書くところからだ。
1時間もあれば書けると思うが、本当、思考ルーチンの改良という美味しい部分(?)以外に必要なお膳立てが多すぎて非本質的な作業ばかりが続く。コンピューター将棋に限ったことではないが、こういう地道な作業に耐えられる人だけが優秀な成果を残すことが出来るのだろう。(私には無理だ…)
■ 2013/10/20 21:30 コンピューター将棋の進歩は止まらない？
コンピューター将棋関係者には常識だが、Bonanzaメソッド以降、コンピューター将棋において大きな改良というのはほとんどなされていない。また、探索は従来のコンピューター将棋の探索技術より、Stockfishというコンピューターチェスのソフトのほうが優れていることが明らかになったので、上位ソフトは軒並みStockfishの探索部を真似しているような状況である。
つまり、いままでのコンピューター将棋における探索技術の歴史の全否定である。(唯一の例外は詰将棋におけるdf-pnぐらいか)
それでもコンピューター将棋の年々の強さの伸びが鈍化したという話は聞かない。
PCのスペックも近年はそれほど向上していないにも関わらずである。
これが何故かと言うと、私が思うに、いまのPCで探索深さが十分に深いので、わずかな枝刈り性能の差が決定的な差を産み出すのだ。1手ごとの平均分岐数が2.0なのと2.1なのとではわずかな差に思えるが、しかし20手先を読むときに2の20乗(=1,048,576)と2.1の20乗(=2,782,184)とで3倍近く違う。平均分岐数のわずかな差(枝刈り性能のわずかな差)が、読むべき局面の数として天と地ほどの差を産み出す。
だから、探索深さが十分深くなってきたコンピューター将棋の勝負において、わずかなソフトの改良によって大きく強さが変動するということが往々にしてあり得るのである。
このような傾向は、PCが速くなれば速くなるほど顕著になるので、今後は長い時間をかけて統計をとり、改良の効果を毎回丁寧に考察しながら少しずつ改良を積み重ねるというような不断の努力がより一層必要となる。(私には到底無理だ)
■ 2013/10/21 18:00 floodgateクローラー
floodgateクローラー完成。1時間ぐらいかかるかと思ったらC#で書いたところfloodgateでは棋譜が日付別に整理されているようで、ソースコード自体は5分ほどで書けた。うまく動いているようだ。
var start_url = "http://wdoor.c.u-tokyo.ac.jp/shogi/x/2013/"; var dt = new DateTime(2013, 1, 1); var web_client = new WebClient(); var regex = new Regex("href=\"(.+\\.csa)\""); // 今日の日付まで達したら終了。 for (;dt < DateTime.Now;dt = dt.AddDays(1)) { var url = start_url + '/' + dt.Month.ToString("00") + '/' + dt.Day.ToString("00/"); var data = web_client.DownloadString(url); var mc = regex.Matches(data); foreach (Match m in mc) { var filename = m.Groups[1].Value; var url2 = url + filename; web_client.DownloadFile(url2, "2013/"+filename); } }
※ 上記のソースコードは自由にお使いください。(実際に動かすときにはサーバー負荷に配慮する処理を追加してください。)
■ 2013/10/22 17:50 1年分の棋譜
floodgate 2013年分の棋譜は昨日の分までで12万5千局程度。1.5GB程度。ここ数年分だと60万局、6GBほどある。
Windowsのファイルシステムだとこの棋譜が入っているフォルダを開くだけでも数分かかる。ファイル列挙をするだけでOSがフリーズ同然になる。扱いにくくてかなわない。プログラムを書くより、待ち時間のほうが長い。ゴミ箱を空にするだけで何時間もかかるのだが…。(Hyper-Vのゲストで作業していることや、Shadow Copyによるシステムの復元が出来る設定にしているせいもあるのだろうけど…)
結論的にはこのように大量のファイルを扱うならHyper-Vやめとけとか、ストレージはSSDにしろだとか、そもそもファイルを細切れにせずに1本のファイルにしとけだとか。
プログラムの修正で思い出したが、プログラムの修正の効果を確認するためには5分×200局ほど対戦させないといけないため、丸一日程度要する。それを考えるとこのあとバグ等を修正できるとして2,3個ぐらいだろうか…。
■ 2013/10/23 0:50 CSA拡張プロトコルとはなんぞや
ドワンゴの窓口の人から、メールが来ていて、テスト用のサーバーの準備が出来たから使ってみてね(要約)とのことらしい。CSAプロトコルに独自拡張がされているのだが、ほとんどのコンピューター将棋の思考エンジン開発者はUSIプロトコルに対応させて、ネットワーク接続部分とかは将棋所にお任せなはずで、ここを拡張されても自力では対応できないのではなかろうか…。(しかもあと1週間ほどしかないのに…) 私としては、将棋所で接続できるならそれでいいや。
ところで他の思考エンジンの開発者はブログとかTwitterとか進捗がさっぱりわからないけど、もともと思考エンジン開発者は情報とかあまり発信しない文化なのか、それとも、参加申込みをするからにはとっくに完成していていまさら開発進捗も何もあったもんじゃないのか。たぶん後者なんだろう。
■ 2013/10/23 5:00 ドワンゴで用意されている対局サーバーに接続
ドワンゴで用意されたサーバーに将棋所で接続して普通に対戦できることを確認。ポート設定は不要の模様。(ドワンゴの窓口の人のメールにあった4081ポートを指定すると接続できない模様。将棋所がポート設定に対応していないのだろうか？floodgateと同じ4081ポートなので変更する必要はなさそうなだが…)
■ 2013/10/23 5:10 将棋所が勝手に設定を保存する件
将棋所のバージョンが2.8(2013/09/15リリース)以降、思考エンジンの設定が勝手に将棋所に保存されるようになった。これによって便利になるソフトもあるかも知れないが、ほとんどのコンピューター将棋ソフトの開発者にとっては迷惑極まりない。
なぜなら、ほとんどの開発者は、思考エンジンのデバッグ用のウインドウなどを出すようには作っていない。USIプロトコルに対応させるためには標準入出力の処理だけで済むため、それ以上のことをしようとは思わない。つまり、思考エンジンのデバッグはコマンドラインから行なっている。このときに毎回setoptionなどをコマンドラインから手打ちするのは嫌だから設定は自前で保存し、思考エンジン起動時に自前で読み込むようにしている。ほとんどの開発者はたぶんそうしている。
将棋所が単に思考エンジンからのoption設定を二回目以降無視するだけなら良いが、将棋所の思考エンジン設定で設定を変更してもその変更をsetoptionで通知せずにquitコマンドが送られてくるので、思考エンジン側では将棋所の思考エンジン設定で変更された設定を保存する機会が与えられない。(通常対局の最初に送られているので一度でも対局すればisreadyが来たタイミングで保存することは出来るのだが、上で書いたように中断ボタンを押したときにquitが送られてくる前にkill processされるようで、終了タイミングでは保存できない。isreadyタイミングで保存しなければならない。なんてことだ…)
また、開発時には設定項目を増やしたり減らしたり、設定のデフォルト値を変更したりするので、都度、将棋所が書き出している設定ファイル(Engine.xml)を削除しなければならない。そもそもこのファイル、勝手に消していいのか？副作用はないのか？など、不安の種は尽きない。
これらの理由から、設定が将棋所で保存されるメリットは開発者的には皆無で、デメリットしかないという状況である。
■ 2013/10/23 5:20 将棋所にデバッグウインドウが欲しいのは私だけではないはずだが
将棋所に言いたいことはいくらでもある。例えばデバッグ表示である。USIプロトコル対応の思考エンジンである以上、局面をUSIプロトコルに書かれた局面形式で出力する処理はどの思考エンジンであってもすでに書いてあるはずである。
よって、デバッグ時にこの形式で局面を出力して、それが将棋所側で用意されたデバッグウインドウに局面が表示できれば開発がすこぶる捗ることは間違いない。
将棋所側でデバッグ用の局面表示に対応するのは難しくないと思うのだが、将棋所の作者は思考エンジンを作っている人ではないらしく、(思考エンジンの開発者ではなく)将棋ファンのための利便性のほうに力点があるようで、そういった意見はなかなか受け入れられない。
とは言え、USIプロトコル対応のGUIで連続対局・CSA対局サーバーへのネットワーク接続などの機能がひと通り備わっているUSIクライアントは将棋所しかなく、実質的に将棋所一択のような状況である。また長年の動作実績があるので通信対局など重要な部分においてバグはほとんどないと思われる。これと同じクオリティでUSIクライアントを作ろうと思うと数ヶ月単位の大仕事である。(主要部分だけなら1ヶ月もかからないかも知れないが) このため、なかなか自分で作る気にはなれない。
■ 2013/10/23 7:15 floodgateの棋譜が使い物にならない件
やね裏定跡の分析のためにfloodgateの棋譜をふるいにかけるプログラムを書いたのだが、floodgateの棋譜(CSA形式のファイル)には評価値がついていない。そんな馬鹿なと思って、サイトのほうで対局画面を見ると、評価値グラフというのが表示されている。この評価値グラフはどこから取得されているのかと思ったら、別途、どこかからSVGで流し込まれているようだ。(GnuPlotを使ってあるからか？)
よくは調べていないが、このSVGのデータソース元は公開されていないようで、SVGファイルから元の評価値を復元するのは実質的には不可能だろう。何故、ソフトの評価値という指し手とともにサーバーに送っている一番大切な情報をCSAファイルに書き出さないのか、この実装には頭を傾げざるを得ない。この実装だと棋譜の二次利用をする上で非常に困るし、ひいてはコンピューター将棋の進歩を妨げる。
対して、floodgateではソフトの読み筋として送っている情報は、CSAファイルに「'**」として書きだされているのだが、この読み筋を送るかどうかはソフトに委ねられているので送ってこないソフトは送ってこないし、しかも投了の瞬間には評価値も読み筋も送らないので評価値的にマイナスになったから投了したのか、それとも途中中断等の操作により投了したのかCSAファイルから判断がつかない。
CSAプロトコル上は投了の直前にも評価値を送れると思うのだが、将棋所が送っていないからか、投了時の評価値はCSAファイル上には記録されていない。2手前のそのソフトが送信した評価値(CSAファイルに記録されている)を見ればどちらが優勢だったかはわかるはずだと言う人もいるかも知れないが、将棋には、優勢だと思っていたのに着手された瞬間見落としていた即詰みに気づき投了することがある。
「コンピューター将棋でいまどきそんなことってあるの？」と思う人もおられるだろうけど、実際に上位のソフトでもこれは稀にある。例えば、次の習甦 vs Blunderの対局である。
投了直前までBlunderは自分が優勢だと思っており、習甦が８一角を打った瞬間に負けに気づき投了している。評価値グラフ上は一度たりとも劣勢である値は出力されておらず、CSAファイルはもちろん、グラフを見てもBlunderが勝ったのか負けたのか、そして局面が優勢だったのか劣勢だったのか、判断できない。
floodgateの棋譜はコンピューター将棋開発上も、また将棋の文化的にも、重要な遺産であるから、こうした問題をきちんと解決してもらいたいと切に願う次第である。
※ ちなみに上の局面からの詰み手順は、８一同玉に７ニ銀！である。(９ニ玉と逃げると９三香、同金、同角成、同玉、８三金からの詰みがあるので、７二銀には同玉だが、６ニと、８一玉、７ニと、９一玉に９ニ金、同玉、９三香、同金、８ニ角成以下詰んでしまうのである) この７ニ銀〜６ニとの手順はいかにも効率が悪そうなのでBlunderは通常探索で見落としていたのだろう。
■ 2013/10/23 9:30 互角のソフト同士が100局対局してどこかで10連敗する確率は？
ソフトの改良の結果、強くなっているかどうかを試すのは将棋所などを用いて200連戦ほどして、統計学的に有意かどうかで判定する。ところが、同等になるはずが、初っ端から何連敗もすることがある。「でも長期的には勝率五割に落ち着くんでしょ？それって確率的には…」みたいな話をいまからしたいわけじゃない。
将棋所で1つ目に登録する思考エンジンのほうが、最初、少し分がいい気がする。最初の10回ぐらいに関しては1つ目の思考エンジンのほうが有利ではないかと思う。
もちろん、片側の思考エンジンが思考しているときにもう片側の思考エンジンの待機のさせかたが悪く、CPU資源を幾ばくか食っているだとかそういう初歩的な問題ではない。また、人間の感覚的に最初に起きた事象ほど印象深く残っているだとか、そういう感覚の話がしたいわけでもない。
では何かというとOSのスレッドスケジューリングの問題である。OSのプロセス/スレッドスケジューリングがどうなっているのかについては、一言で言うと謎である。Windows7と8とで何かアルゴリズムに変更が加えられていてもそれを知るのは並大抵のことではない。(OS開発者が自分で記事にするだとか、ソースコードが流出するだとかしない限り)
それで、思考エンジン1の(OSの処理単位としての)プロセスおよびスレッドのほうが思考エンジン2のプロセスおよびスレッドより先に作られる。それも、コア数だけ並列化するので、4コアなら最低でも4スレッド。場合によってはHyperThreadingを考慮し8スレッドを生成する。
ところが、そんなに作って、それらのスレッドをスレッド負荷率100%でぶん回したときにOSはこのスレッドをどう捉えるのだろうか。大仕事が来たから、他のプロセスにはちょっと待ってもらおうというようなスケジューリングがなされないだろうか。
ファイルシステムなんかでもそうだが、一つ目のファイルの転送が終わらないうちに２つ目のファイルの転送を始めるとすこぶる転送速度が落ちる。このようなことを考え、関係のありそうなプロセスに関しては、なるべく先に起動されたプロセスを優先するようなスケジューリングをしてもおかしくはない。
その結果、思考エンジン1のほうが思考エンジン2よりCPU資源等において優遇されてもおかしくはないのである。
…ということをちょっと思ったが、たぶんそんなことはないんだろうな…。
(私は気になるので連戦するとき、半分の対局数を消化したところで思考エンジン1,2を入れ替えているが…)
■ 2013/10/23 20:55 コンピューター将棋の改良点 2013年度版
コンピューター将棋の探索はコンピューターチェスのStockfishのパクリ手法を真似て行なうというのが決定打であることはすでに書いた。
また、高速化に関してはどうせメモリ帯域がボトルネックになるのでそれほど劇的な高速化は不可能で、プログラミング経験30年以上の大ベテラン(?)が書こうと、プログラミング経験15年程度のひよっこ(?)が書こうと数割程度の速度差しかないのが現実である。
そもそも上位に君臨しているコンピューター将棋の思考エンジンを開発している人たちのほとんどは東大関係者で、かつプログラミングスキルに非常に長けている人が多いので(C++ templateを自在に扱え、x64やAVXなどのアセンブラに精通し、CPUアーキテクチャを詳細に理解しているので)、そういう前提で話をするなら「(そのクラスの人間ならば)誰が書いても速度は同じ(せいぜい1,2割程度の違い)」と言っても過言ではない。
そうなってくるとコンピューター将棋で劇的な改善があり得るのは評価関数と定跡部分だけなのである。
定跡部分の劇的な改良として、対局中/対局後の自己学習(やね裏メソッドI,II)および、詰みまで入力された定跡(やね裏定跡)については、私が考案した。(コンセプトプルーフのためにも、多少バグってようが、弱かろうが、今回はなんとしても出場したい。)
そして評価関数なのだが、Bonanzaの三駒関係でもまだ学習方法(ボナンザメソッド)の改善は十分に考えられる。まだいまの機械学習では三駒関係すらきちんと学習できていない部分が多々あり、それらを改善することによりまだ強くできるのである。
そうは言ってもボナンザメソッドでもそこそこいい値に収束しているので従来、これで十分だと考えられていた。
ところが、PCのスペックが向上し、また探索技術としてStockfishのものをパクリ取り入れ、探索が効率的に行えるようになってきたので、わずかな評価値の差が勝率の差として大きく反映するようになってきたのである。
つまり、わずかにボナンザメソッドを改良するだけで勝率が数割あがる(例えばNDF)というのは普通に起こりうるわけである。
(つづく)
■ 2013/10/23 21:00 評価関数の棋譜からの学習の改善方法
評価関数の学習メソッドの改善方法はいくつかある。機械学習の手法そのものをボナンザメソッドから変更する。例えば、収束の速い方法(オンライン学習等)にするだとか。
しかし、そうしても収束が速いか遅いかだけの違いで、強さとはあまり関係がない。むしろ、オンラインは収束は速いが値の精度がよろしくないので三駒関係をオンライン学習でやったときにボナンザメソッドよりいい値に収束するかは私には疑問である。(というか、私はよく知らない。)
そこで、目的関数(良い手だと定義し、その良い手が大きな値になるように設計された関数)をどう設計するかという話になる。
棋譜が教示信号なわけであるが、なるべく良質な棋譜を大量に集める必要がある。(棋譜の数が少ないと実戦例に乏しい形をきちんと学習できない)
いまであればプロ棋士とコンピューター将棋との実力が拮抗していることが示されたので、floodgateの棋譜を使うのも悪くないと思う。
また、棋譜の良さに応じて重みづけを変えてやるという手法は古くからある。
試合に勝ったほうの指し手のみを学習するだとか、強い棋士の重みは大きくするだとかである。
私が採用したアイデアは、トップ棋士である羽生さんの指し手は重みを2として、底辺棋士の重みは1とし、棋士レーティングに比例した重み付けをするというものである。(以下、その正規化されたテーブル) また、これを用いて三駒関係を学習させたときに勝率が有意に改善されることは確認した。
// 棋士の名前と、正規化されたレーティング char* kishi_name[] = { "羽生善治三冠", "渡辺明竜王", "郷田真隆九段", (中略) "佐藤義則八段", "安西勝一六段", "上記以外の棋士", }; double kishi_weight[] = { 2, 1.934023286, 1.857697283, (中略) 1.07373868, 1.067270375, 1, };
他の手法として、例えば、対局中の評価値の推移のように2手進めてみると前の評価値が過小/過大評価であったと気づく場合がある。(下図) 要するに深い深度での探索結果と浅い深度での探索結果とが一致するようにパラメーターを修正という考え方がある。これはBlunderなどで採用されている。(NDFもこの考えかたなのかどうかについてはNDFのアルゴリズムの詳細が発表されていないのでわからないが)
ともかく、「コンピューター将棋には興味があるけど、自分で探索部も詰将棋ルーチンも指し手生成も書きたくないよ！(書けないよ！)」という人は、どうせ評価関数こそが最大の肝であるので、この部分の改善をしてコンピューター将棋界にデビューするのもアリなのである。
そして、上で書いた通り、評価関数以外の部分ではほとんど改善がしにくいのが実状なので、評価関数の改善だけに取り組みつづける人が成功する可能性が案外高いのである。
■ 2013/10/24 17:30 やね裏定跡、11,875局分入力完了！
やね裏定跡(詰みの局面まで入力された定跡)の11875局分の入力が完了した。
(入力って言っても私が手打ちしたわけじゃなくて、プログラム書いたあと放置してただけなんだけど…)
SQLite3は結構速く、各局面での最善手およびその指し手の出現頻度を保存していく場合、秒間数局(300query/sec)程度はさばけるようだ。(Hyper-Vのguest OSでそれくらいの速度なのでSSDを載せてある最先端のPCならその何倍も出ると思う) ただ、局面数が増えてくると(DBのファイルが大きくなってくると)だんだん遅くなって…スケーラビリティは今ひとつかも知れない。
まあ、それでも秒間50queryぐらいできるから、1手ごとに定跡DBに問い合わせたり、試合中に思考結果をDBに書き戻したりするのはどうってことなさそう。ただ、欲を言えば本番ではHDDよりはSSD搭載のPCのほうが嬉しいのだが…定跡DBをSQLite3のような汎用DBを使って実装している将棋ソフトは他にはあまりないだろうから、そういう要望はあまりないんだろうなぁ…。
また、SQLite3を使った定跡DBの構築作業は、非常に楽だった。Bonanzaの定跡処理部分のソースコードとか二つの定跡ファイルをマージするための処理とかが書いてあって、結構複雑だった記憶があるが、SQLite3ならそういうことは一切考えなくて済むし、あとでテーブル設計を修正するようなことも容易である。本当、SQLite3を選択して良かった。Bonanzaみたく自前のDB構造でやってたら私は今月いっぱいかけても定跡DBが完成するかどうかすら怪しいところだった。
なんにせよ、やね裏定跡の用意が間に合って良かった。ちょっと動作が怪しい部分もないではないが…。
もう少し改良してみることにする。
→ やね裏定跡を厳選しなおした結果3734局に減ってしまった。
■ 2013/10/24 18:45 やね裏定跡とは何なのか？
やね裏定跡とは何なのか？
Bonanzaなどに入力されている定跡は精度が悪く、定跡を抜けた時点で劣勢の局面であるということが多々あった。いまやコンピューター将棋はそこそこ強いので、そのあとfloodgateのように15分の持ち時間で終局まで続けると一度も劣勢の評価値にならないままゲームが終局する可能性が高い。
つまり、このとき次のような評価値曲線を描く。
これを「ワンサイドゲーム」と定義する。このワンサイドゲームでは、定跡を抜けたところでプラスの評価値であることが保証されており、また、双方のソフトがそれを同じように評価していること、そして、そのあと実際に勝っていることからも、定跡を抜けた局面ですでに優劣がついている可能性が高いと考えられる。
そこで、上記のようなワンサイドゲームを信頼できるソフト(R2800以上のソフト)に限って抽出し、その勝ったほうの指し手のみを定跡として入力した。それがやね裏定跡の正体である。
こうしておくことで定跡を抜けた局面で自分が有利になっているようなゲーム木(定跡木)が得られる。
従来、定跡木の終端局面それぞれでBonanzaを何秒か思考させて、定跡木のなかでmin-max探索のようなことをして有利になりやすい定跡を選択するような研究があったと思うが、やね裏定跡は、それと同じような効果が得られるわけである。
■ 2013/10/25 18:45 お手軽な思考時間制御法について
コンピューターチェスやコンピューター将棋の思考時間制御は非常に難しい問題で、真面目なアプローチとしては、局面がどれくらい不安定か(正しい判断を下すために思考時間の必要な局面であるか)をたとえばSVM(サポートベクターマシン)で数値化して、それに応じた時間を費やすのが望ましい。
ところが、そういうアプローチは大変面倒くさく、手間がかかるので、普通の開発者はそこまでやっていない。やっていないながらもお手軽にそれらしくする方法をここに書いてみたい。
まず、将棋の序盤はどうせ考えても致命的なほどの差はつかないゲームなので、中盤の思考時間の半分だけ使うとする。そして終盤もそこそこコンピューター将棋は正確に読むので終盤も徐々に思考時間を減らすとする。この関数をaとする。
そうすると、関数aをグラフに書くと下図のような台形になる。
いまN手目で、ここでの残りの手持ち時間は思考ルーチンにUSIプロトコルで与えられる。切れ負け設定であれば、これが緑の部分の面積Sに相当する。このN手目で使っていい時間は、NからN+1までの小さな縦長の台形の面積である。
よって、斜線の面積をSoとすると、今回の思考時間 = So / S × 残り持ち時間 みたいな式になる。(SoととSは、関数aを積分して出すものとする)
個人的な見解だが、重要な局面でだけ他の局面の何倍も深く読んでもなかなか効果が出にくい。その前後の局面もそれ相応に読むべきである。例えば詰将棋で最初に時間を費やし13手詰めを読み切り、初手で飛車を捨てる手を指したが、次の手番で9手しか読まなかったらどうだろう。詰みまで読みきれずに日和ることになり、前の飛車を捨てた手が致命的な悪手となってしまう。
よって、読みを特定の手だけ増やしてもさほど効果はないのではないかというのが私の考えである。(その手の前後もある程度増やして、上図の台形のように、なだらかに持ち時間が1手ごとに変化するようなものが理想だと思う)
■ 2013/10/26 02:30 Bonanza系の探索ルーチンでは本大会では上位に食い込めない？
Bonanza系の探索ルーチンを搭載しているソフトは多コア(6コア以上)になったときに、(他の将棋ソフトに比べて)探索性能が出ないようである。
本大会のように8コアのPCでかつ、統一ハードだとBonanza系の探索ルーチンは圧倒的に不利なのだ。
やねうら王もご多分に漏れずBonanzaのソースコードを大いに参考にしているのでモロに煽りを食っている。だからStockfish風に探索部を丸ごと書き換えたいのだが…。
まあ、やねうら王の場合、それ以前の問題として、まだ評価関数の学習が終わってなくて、あと、やね裏学習メソッドI,IIの実装が終わってなくて、おまけにいくつかバグがあって、ときどき変な指し手が混じってるんだけど…。それでも、まだ直したいところがあるのでこのあとソースコード大量に書き換えるつもりでいるのだが、テストすらろくに出来ない可能性が…これで出れるのか…。いや、出るけど…。
ちなみに対Bonanza6.0、現在の勝率は40%ぐらい。(変な指し手で自爆して勝てない局が混じってる) おい、頼むよ。せめて5割は勝ってくれよ…。というか、nps(探索速度)とか、改良内容からして7割ぐらい勝たないとおかしいだろ、これ。
嗚呼、テイルズオブハーツRさえ出ていなければ…。こんな大事な時期になんて大作ゲームを出してくれやがるんだ！テイルズの大ファンとしてはやらざるを得ないじゃないか。くそ〜！
■ 2013/10/26 13:00 持ち時間制御その2
持ち時間について、いまルールを読んで知ったのだが、
1) 電王戦トーナメントの予選は、持ち時間15分+そのあと1手10秒
2) 電王戦トーナメントの本戦は、持ち時間2時間切れ負け
3) 電王戦(プロ棋士との対局)は、持ち時間5時間+そのあと1手1分
となっているようである。正直、切れ負けの調整しかしてなかった。
切れ負けも15分切れ負けのつもりで調整していた。いまから1)〜3)を書かないといけない。
コンピューター将棋は持ち時間の使い方によって勝率は大きく変動する。やねうら王の場合、やね裏定跡にハマると序盤で有利になるので中盤でBonanzaの2倍ぐらい湯水の如く時間を使い、そのまま終盤を押し切るという作戦で考えていたが、上記2)のように2時間も持ち時間があると、floodgateの棋譜通りにいかないから、序盤で互角以下で進行し、中盤で時間を使ったわりに互角のまま進行し、終盤、時間がなくて大きく弱体化して負けるという最悪の流れとなってしまう。
やねうら王としては本戦、こんなに時間要らないのに…(ﾉ∀`)ｱﾁｬｰという感じである。
やはり、上記2)のために持ち時間の使い方を調整しなおさなければならない。
次に、1)と3)だが、この1)と3)でアプローチの仕方が全く異なる。
1)は、持ち時間とそのあとの1手の時間との比率が90 : 1であるが、3)は、300 : 1である。前者であれば、100手目(自分の手番は50手)までに持ち時間を使い切り、そのあと1手ごとに9.8秒ぐらいまで使うのがベストであろう。(そんなギリギリにして通信のレスポンス的に大丈夫なのかどうかは知らんが…)
3)は、持ち時間とそのあと1手とのバランスが極めて悪いため、使い切る戦略にすると終盤の思考時間が相対的に少なすぎて、終盤で相当の弱体化をしてしまう。おそらく使い切る戦略は損だと思う。これくらいのバランスならば140手目ぐらいまでで持ち時間を消費するぐらいのペースで進めて、そのあと持ち時間がなくなれば仕方ない、というぐらいの配分がベストではないかと思う。
と、このように、
・切れ負け(持ち時間がなくなると負け)かどうか
・持ち時間と1手ごとの時間との比率がどうであるか
という二つの観点から最適値というのは変わってくるのである。つまり、上記の1),2),3)ではそれぞれ全く異なった持ち時間配分のための戦略が要求されるのである。
いまからこのプログラムを書いて調整しなければならない。
やね裏学習メソッドの実装もまだだというのに…。それ以前にバグ取らないと…。
■ 2013/10/26 21:30 思考時間制御がすべての鍵
探索部をどう改良してもStockfishから劇的に改善されることはないのが実状。
また評価関数もどう改良してもBonanzaの3駒関係から劇的に改善されることはないのが現実。
それに対して、思考時間制御(思考時間の配分の調整)というのは、劇的な改善をもたらす。重要な局面を判断して、そこでのみたくさんの時間が使えるなら劇的に強くなる。
そのことに私が気づいたのはだいぶ後であって、Blunderのaki.さんから、「大学の卒論のためにコンピューター将棋の思考時間制御について研究しようと思っている」という話を聞いたころ(5年ぐらい前の話)まで遡る。
当時はもとより、いまでも思考時間制御なんてほとんど誰も注目していない分野であり、また、そこを改善したところで…みたいな考えもあって、当時の私は「aki.さんなら、評価関数とか探索とか研究したほうが実りがあるんじゃないですか」とどっちかというと否定的な見方をしていた。
しかし思考時間制御にボナンザメソッドを導入して、なおかつ成果を挙げたaki.さん。その画期的な論文に、私の名前が載っている*2のは身に余る光栄である。
■ 2013/10/26 21:35 最終局の直前までが俺の開発期間だ！
今日は私の誕生日だったので祝賀会でこんな時間になってしまった。開発する時間がどんどん減っていくな。こりゃ、電王戦トーナメント中にも開発せざるを得ない。
大会規定では、(5位以内の入ったとして)電王戦トーナメントに出場したソフトを無改造でプロ棋士と戦うことであるから、電王戦の最終局まではプログラムをいじっても構わないことになる。(最後の1局でその最終調整をしたソフトを用いるなら)
昔、YSSの山下さんが世界コンピュータ将棋選手権で本戦の前日とかにホテルでプログラムをいじっていたという話を聞いて、「そんなときにいじってエンバグ(修正した結果、新たにバグを生み出してしまうこと)でもしたらどうするんだ」と思ったものだが、大会中、それも最終局の直前までVisual Studioを起動してビルドしていたという前例はないはずだ。私がその記念すべき第一号となろう。
者ども、俺様の生き様(死に様？)を見ておれ！
■ 2013/10/27 18:45 やね裏学習メソッドIの実装完了
テストはろくにしてませんが、とりあえずやね裏学習メソッドIの実装が完了しました。
実装自体は簡単なものの、将棋所の思考エンジン設定のところから様々な学習オプションを変更できるようにしたり、その設定されたオプション通りに動くようにしたり、説明用のドキュメントを更新したりと、何かと時間がかかります。
一度指したことのある局面をさくさく指してくれると人間側としては対局していて非常に気持ちがいいですね。まあ、今回の大会ではあまり関係ないかも知れませんが。
とりあえず1局ごとに定跡を学習するのは世界初だと思ってたのですが、よく考えたら1985年ごろに棋太平という将棋ソフトがあって、あれも序盤の自分(コンピューター)の指し手をDB(?)に記憶してたような気が少しします。持ってなかったので良くは知りませんが。棋太平はソフトをコピーすると、プロテクトに引っかかっていると起動画面の馬に跨っている武士が馬から落馬している画像に差し替わるのが有名ですね。
まあ、なんにせよ、コンピューター将棋で1局ごとの局後の自動検討〜自動学習はやねうら王が世界初ですかね。
■ 2013/10/28 1:35 やねうら学習メソッドII実装完了
やね裏学習メソッドIIの実装も完了しました。もう眠たいのでテストは明日やります。
やねうら学習メソッドI、やねうら学習メソッドIIのために書いたソースコードはそれぞれ300行程度。あと、本体のソースコードの修正が必要だった箇所が200行程度。そんなわけで今日は1100行ほど書きました。
SQLite3を使っているのでDBアクセスまわりはすこぶる楽ちんです…が、局後検討のため思考エンジンをDBから読み込んだ指定局面から呼び出す必要があるのですが、その部分のソースコードは、あまり綺麗に書いていなかったので意外と大改造になりました。
実際はソースコードを書く何倍もの時間を検証作業とかドキュメント作業とかに費やさないといけないので明日以降、時間がいくらあっても足りません。よくこんな状態でエントリーしたなぁと自分でも思うのですが。
■ 2013/10/28 1:45 スレッドまわりが複雑
やねうら王のスレッドまわりですが、以下の4グループにわけられます。
1) USIコマンドの受付スレッド
2) 思考時間を監視して、時間になったときに強制停止させるためのスレッド
3) 思考ルーチンの開始〜終了のために待機しているスレッド(思考開始時は、このスレッドが思考ルーチンのメインスレッドとなる)
4) 思考ルーチンのスレッド(コアの数だけ)
という構成になっているのですが、DBにどのスレッドからアクセスすべきかだとか、思考スレッドとの調停をどのスレッドが行なうべきかだとか、そういう問題が出てきて、極めて複雑な状態管理が必要になります。
図を描いて状態遷移などについて説明すべきなのですが、いまはその気力がありません。すみません。
上記2)みたいなものを作らなければ設計は楽になるのですが、正確に秒読み時間のギリギリ(0.97秒ぐらいまで)使いたいので、そのためにはどうしても残り時間を監視するための専用スレッドが必要になります。
■ 2013/10/28 1:50 当日までにやるべきこと
現時点でのToDo。
・やねうら学習メソッドI,IIの動作検証(バグがないか)
・Visual Studio 2012を当日持っていくノートパソコンにもインストール
・持ち時間制御のための手法を考えなおして、実装
・探索がおかしいバグ修正(たぶんかなり根が深い)
・条件を変えながらBonanzaと対戦実験＆チューニング
・やね裏定跡がBonanza相手にハマるパターンを調査
・当日までにボナンザメソッドで棋譜から学習させている評価関数パラメータがいい感じの値に収束してくれることをお祈り
間に合うのかなぁ…。特に探索がおかしいバグは…どうだか…。
■ 2013/10/28 1:55 Bonanzaのnarrow book問題
この記事自体が長文すぎて誰もこんなところ見てないとは思いますが、Bonanzaのnarrow book問題について、ちょっと走り書きだけしておきます。
narrow bookというのは定跡DBを使うとき、出現頻度の高い定跡のみを使うというオプションです。
やねうら王もこのアイデアに倣い、思考エンジン設定でnarrow bookのオプションが用意してあり、出現頻度の高い定跡のみを採用することが出来ます。
それでBonanzaと対戦させていてわかったのですが、Bonanzaのnarrow bookでないとき(たぶんデフォルトではそうなっている)は、不利になる定跡が混じっています。プロがたまーに趣向として指すような、アマチュア臭い感じのアレですね。
早い話、narrow bookにしないとBonanzaは弱いんですね。今日、Bonanzaと対戦させてて、200戦して5割以上勝つなーと思って眺めていたのですが、なんのことはない。narrow bookをオンにするとボコボコ(死語)にやられました。3,4割ぐらいしか勝てません。あまりに凹んだので、50局目ぐらいで対局を中断しました。
やねうら王の探索がバグっているのか、もともと探索部がおかしいのかはよくわかりません。
また、持ち時間設定によって勝率ががらっと変わるので、何を基準にしていいのかさっぱりわかりません。持ち時間によってはBonanzaに7割ぐらい勝てたり、3割ぐらいしか勝てなかったり。対戦結果にムラがありすぎですね。
やねうら王の持ち時間の使い方が悪いのもあるんでしょうけど。
とりあえず、この問題をあと残された期間中に解決しなくてはならないのです。
まあ、そんなわけでBonanzaは当日はnarrow bookで来るんじゃないかなーと思うのですが、それならそれでnarrow bookに対してやね裏学習メソッドIIで事前学習させたいわけですが、まあ…いまからでは到底無理ですね。大会に出てくるBonanzaがBonanza 6の定跡ファイルのままとは限りませんし、局後検討に要する時間は半端ないですし。
そういう意味ではやね裏学習メソッドは今回、完全に空振りなのですが、まあ面白ければそれでいいじゃんと言いますか、とりあえず、こういうアプローチが可能なのだということを他のコンピューター将棋の開発者の方に知ってもらえればと思います。
■ 2013/10/28 2:20 長文になってきたので次ページに
次ページ。
電王戦 --- 将棋電王トーナメント --- やねうら王特設ページその２
http://d.hatena.ne.jp/yaneurao/20131028#p1
