やねうら王開発実況用スレッド


■ 2014/10/15 9:00 Stockfishの最新版は罠なのか


5日ほど前にStockfishの最新版(GitHub上のもの)を参考に探索部分を調整した。Stockfishの前回からの差分調べたり、デバッグしたりするのに丸2日ぐらいかかって、そのあと2日ほどかけて200戦ほど対戦させると古いバージョンに対して1割ほど負け越していた。なんなんだろう。最新版は罠なのか?もっと対戦させるべきなんだろうけど、やっている戦型が偏っているせいもあってか正確な比較になっていない気もするし、とりあえず負け越しは気分が悪いので涙目でrollback。


■ 2014/10/15 19:30 やねうら未来探索について


コメント欄より。
> 「将棋ソフトの流れを汲まない」ってところについてもう少し詳しく書いてくれると嬉しいです。


(自分以外の)日本人が考え出した将棋ソフトのアイデア・実装を一切使わないという意味です。具体的にはBonanzaの1手詰め、3手詰め、GPS将棋のdf-pn、Bonanza方式の手駒だけ損している局面の検出、Bonanzaメソッド、Bonanza型の3駒関係etc…。(時間の都合で1手詰めと3駒関係はもしかしたら使うかも知れませんが…)


別に私は日本人に恨みがあるわけではありません。彼らが生み出したものがどれくらいのものなのか。コンピューター将棋の歴史(成果)がどれほどのものなのか。それらを正しく評価するためには彼らの成果をいったん全否定して、そしてそれなしに独力でやってみて、そのあと、出来がよくなかったら、「やっぱり1手詰め入れたほうがいいよね。1手詰め偉大だよね。」というように必要性や偉大性が初めて実感できると考えています。ニーチェの言葉で言えば、これが「およそ到達しうる最高の肯定の形式」でしょう。


■ 2014/10/15 21:15 やねうら王はツンデレちゃん


> PVではキオビヤドクガエルみたいなロボットですが、あれは作者からするとやねうら王のイメージとは違うのですか?


誰がキオビヤドクガエルだよ、ウワァァァンヽ(`Д´)ノ
やねうら王のイメージガールは、やねうら王公式*1ツンデレちゃんです。


■ 2014/10/15 21:20 第2回 将棋電王トーナメントPVの件


私の「カップラーメンのお湯を原爆で沸かす人はいない」というくだりは、人間の知性を超越した汎用的な思考エンジンにもなりうるようなコンピューター将棋/チェスの探索エンジンを、たかが将棋ソフトのためだけに使うのは暴挙であり、コンピューター将棋にしか使わないとしたらそれはエンジニアとしての傲慢であり怠惰であり社会的損失である、という意味です。


また「コンピューター将棋の歴史がナンボのもんじゃい」というのは、上で書いた「彼らの成果をいったん全否定して、そしてそれなしに独力でやってみて、(そうして初めて)その必要性や偉大性が初めて実感できる」という流れでしゃべりました。


私の発言の前後は大会を盛り上げる趣旨にそぐわないと判断されたのか例によってカットされており、意味不明な映像になっておりますが…。(´ω`)


まあ、私のサゲサゲな発言をうまく切り貼りしてアゲアゲな感じにする佐藤映像さんの手腕はさすがと言わざるを得ません。(皮肉ではなく、サゲサゲな感じでPVに使われるよりは、アゲアゲな感じで使われたほうが良いという意味です。)


■ 2014/10/16 9:00 やねうら未来学習メソッドについて その1


コンピューター将棋では、ボナンザメソッドを初めとして棋譜から評価関数のパラメーターを機械学習させるのが主流であるが、初代Bonanzaでで3万棋譜、後発の強豪ソフトはその何倍もの棋譜を用いている。果たして本当にそんなに要るのだろうか。人間が将棋を覚えてプロ棋士になるまでに10万棋譜も(他人の棋譜を)並べるだろうか?下手すると1万棋譜にすら及ばないのではなかろうか。それなのに人間はちゃんと学習できるわけである。そこに人間の偉大さがあるわけだが、裏をかえせばとりわけコンピューター将棋の評価関数パラメーターの調整方法には改良の余地が大いにあるわけだ。


例えば、NDFは3駒関係を3駒絶対+3駒相対+2駒絶対+2駒相対のように分解して学習させた。*2 データの次元を下げたわけだ。NDFはNDF独自の学習メソッドを開発したが、その効果のほどは私にはよくわからない。というのも、このように3駒関係を分解してボナンザメソッドで学習させるだけで相当に棋力が向上すると言われている。たぶんAWAKEはこの方法。*3 だから、ボナンザメソッドはボナンザメソッドで改良の余地があるだろうけど、データの次元を下げることでボナンザメソッドのままでももう少し精度の良い学習が出来る。


また別の言い方をすれば、ボナンザメソッドほど優秀な学習方法でなくとも次元をひたすら下げていけばちゃんと学習できる(かも知れない)ということでもある。そうすれば大量の棋譜は要らなくなる。学習時間が短縮化できる。羽生さんの棋譜だけで学習するだとか、長い持ち時間で自己対戦させたコンピューター将棋同士の対局棋譜のみを使う、というようなことも出来るようになる。(かも知れない)


■ 2014/10/16 18:00 やねうら王(笑)


今回、電王トーナメントにエントリーするときに名前をどうしようかと思ったのだが、「やねうら王 2014」だと、今年5月ごろに将棋倶楽部24に放流していたものと紛らわしい。かと言って、「やねうら王 2015」だと来年はどうするのかという問題が出てくる。


「やねうら王 2014 後編」「やねうら王 2014 Alternative」などいろんな名前を考えた結果、「やねうら王(笑)」とかにしたらどうかというアイデアが浮かんだ。ちょうど『STEINS;GATE』に夢中になっていたときで、作品中に出てくる「電話レンジ(仮)」からの着想である。


しかし「やねうら王(笑)」にしてしまったら、ニュースサイトや新聞で取り上げられたときに「Aperyとやねうら王(笑)は、激闘を繰り広げた。」とか書かれても、全然激闘に見えないって言うね。個人的にはそれはそれでやねうら王らしいかなと思うんだけど、なんか記者の人が迷惑しそうなのでストレートに「やねうら王」のままで行くことにした。


■ 2014/10/17 9:00 やねうら未来学習メソッドについて その2


次元の下げ方は他にもある。例えば、王の右隣の金と二つ右隣の金とではどちらが価値が高いだろうか?右隣のほうがいくらか価値が高いだろう。このように2駒相対でも、隣接する升につく値自体は比較的滑らかであると考えられる。これを利用する。Aperyチームはたぶんここを多項式近似でやっている。*4 2変数関数の多項式近似、テイラー展開してほげほげ…うーんそんなの20年ぐらい前にやったなぁ…(遠い目)


時間もないことだし、一発でバグなしで書く自信がないので多項式近似は私は採用見送り。もう少しシンプルな方法でやる。まあ、多項式近似が適しているのかどうかはよくわからない。そのへんは(3駒関係を採用するとして)3駒関係にどういう点数がつくのが適切かという問題でもある。


また例えば、先手の王と角と銀のような3駒関係を考えるとき、角の利きがあるところとないところとでは事情が違ってくる。角が行ける場所(チェッカープレート的な意味で)の銀かどうかでも話が変わってくる。また敵陣にいる生角と、非敵陣にいる生角とでも価値は大きく違ってくる。


何らかの関数で近似するにしてもこれらについては分けて考える必要があると思う。(不連続な関数になるだろうから) このへん比較実験等をやるべきなのであるが、実装→機械学習→ランニング(自己対戦)というサイクル、残り2サイクル回せるか回せないかの時間しかない。バグなしで一発で書けて2サイクル回せる程度。たぶんそれは無理。1サイクルしか回せない。つまりワンチャンスしかない。泣きそう。


ともかく今日中にやねうら未来学習メソッド(うざいな、この名前!)の学習部を完成させてランニングするぞー。


■ 2014/10/18 11:00 OS X Yosemiteはヨウスミテ


OS X Yosemiteの無料配布が始まったので速攻インスコした。VMWare Fusion4が使えなくなった。Fusionの最新版は7らしく、7ならYosemiteに対応しているらしいのだが、OSが無料なのにOSのアップグレードごとにFusionにお金を払うのは馬鹿らしい。もしかすると仮想環境はもうオワコンなのかな…と思いつつ、Fusion4→7はアップグレード扱いにならず新規購入のみだったので、Paralles Desktop 10を購入。


ParallesではFusionのディスクイメージをそのまま使えるのだが、ディスクイメージの変換をしないといけなくて、MacBook Airにその空き容量がないから外付けHDDにいったん移動させて…みたいなことをやってたら丸一日潰れた。こんなんで電王トーナメントに出れるのか見ていて不安になっている読者もおられるだろうが、もちろん私も大いに不安である。


■ 2014/10/19 17:00 妖怪将棋はじめました


土日は息子(5歳)と遊ぶ曜日と決まっているので、息子と遊び倒した。プログラム1行も書いてない…ヤバイ。息子は本将棋になかなか興味を持ってくれないので、毎回将棋の駒を使った新しいゲームを私が考えて、それをやることにしている。今日やった(私がルールを考えた)のは「妖怪将棋」


【妖怪将棋のルール】 59と51に先手、後手の王を置く。先手と後手が交互に「歩」をサイコロ代わりに振る。表が出ると移動であり、盤上の好きな駒を本将棋のルールに従い移動できる。(手駒があればそれを打つことも出来る) 裏が出ると「召喚」か「移動」かを選択できる。召喚したいときは、「召喚〜!」(妖怪ウオッチの妖怪を召喚するときの声で)と言いながら駒箱から好きな駒を1枚召喚できる。召喚した駒は好きな場所に置ける or 自分の手駒化することができる。王を取られると負け。


なかなか面白いと思うのでみんなやってみて。駒を並べる手間が掛からないし、将棋の終盤の醍醐味が楽しめる。


この妖怪将棋のルール140文字にまとめて、ツイートしてきた。流行るといいな.. → https://twitter.com/yaneuraoh/status/523752757883174912


※ 追記 : 難度調整の例)
変更ルール1) 玉の位置が59と51からだといきなり頭上に金を召喚されてしまって短手数で終了してしまうので子供がそれを学習したら、玉の位置を58と52、57と53のように場所を変えてやるとゲーム性が増します。
変更ルール2) あるいは、初期陣形として玉の両側に金を配置してやるだとか。
変更ルール3) 歩を47,57,67(後手は43,53,63)に配置するだとか。
変更ルール4) 折りたためる将棋盤なら盤面を片側(4×9)だけにするだとか。
変更ルール5) 召喚は歩を振って可能にするのではなく、1局に10回まで自分のターンで「召喚」と宣言すると召喚できるようにすると実力勝負に。
変更ルール6) 歩を振る枚数を2枚にして、1枚裏 = 召喚 or 移動。2枚とも裏 = 変身 or 喚 or 移動。として、変身は自分の盤上の駒を駒箱の別の駒と交換できるだとか。
変更ルール7) 歩を振って低い確率において、「変身」以外に「チェンジ」と宣言して盤上の任意の2駒(相手の駒でも良い)を交換できるだとか。
変更ルール8) 歩を振って低い確率において、「変身」以外に「反転」と宣言して盤面を180度回転させられるだとか。


のようにやるごとに新しいルールを追加したり減らしたりして、そのルールにおける最善を息子に考えさせたり、そのルールのルールとしての良し悪しを考えさせたりしている。自分の思考訓練にもなってとても楽しい。


■ 2014/10/19 20:00 やねうら未来学習メソッド3


普通、棋譜に出現回数が少ない因子はゼロに収束する。(というか、0に収束するような力を学習時に加えてやる)


そうすると、学習時に出現していない局面の因子はゼロに収束してしまう。そこで、棋譜の数を桁違いに増やしていろんな特徴因子が必ずたくさん出現するようにする。しかしそんなに大量の棋譜は世の中にはないので(プロの棋譜が3〜5万と、floodgateの棋譜が50〜100万棋譜程度)、NDFがやったように何らかの方法で局面を水増ししないといけない。大量の局面があるので学習にも大量の時間を要する。(局面数に比例した時間を要する)


棋譜や局面数を増やすというのは力技ではあるが、確実に成功する方法である。何故なら、それによって正しい(いい感じの?)値に収束しやすくなるからである。これには電気代と学習に要する時間が必要である。(さらに言えば数億〜数百億局面を与えて正しくパラメーターが収束するような学習メソッドでなければならないが…。)


もう一つ別の方法は、少し手間がかかる方法ではあるが、出現しなかった特徴因子がゼロに収束してもそれほど問題とならないように学習時の評価関数の設計を行なうことである。そうすると棋譜が少なくて済む。学習に要する時間も劇的に短縮される。


どうやって設計するか例示しよう。


例えば、玉の周辺8近傍の空き升の状態(空いている/いないを1bitで表現するとしたら8近傍=8bit=256通り)と玉の位置(81升)との組み合わせとなる。大雑把には256×81通りの組み合わせとなる。これに対する広さのボーナスを評価因子として用意するときのことを考えてみよう。


玉が中段にいて8近傍がすべて駒に囲まれているような局面は現実的には出現しない。かと言って、そのときこの評価因子が0になってはまずい。


そこで、例えば、
玉の左上・真上・右上に駒があるときの広さボーナス = 玉の左上・真上に駒があるときの広さボーナス + 玉の左上・右上に駒があるときの広さボーナス + 玉の真上・右上に駒があるときの広さボーナス + 玉の左上・真上・右上に駒があるときの広さボーナス
というように分解してやる。そうすると、最後の項が出現回数ゼロで、ゼロに収束したとしてもそこそこ正しい値がつく。


このような因子の分解を玉の位置に関しても行なう。


88の玉の真上に駒があるときのボーナス = 8段目に玉がいて、その真上に駒があるときのボーナス + 8筋目に玉がいてその真上に駒がいるときのボーナス + 88の玉の真上に駒があるときのボーナス


ここでは段と筋に対して分解したが、分解の仕方はいろいろな方法が考えられる。なるべく合理性のある分解の仕方が好ましい。穴熊かそうでないかで分けるだけとか、入玉かそうでないかで分けるだとかも考えられる。


88の玉の真上に駒があるときのボーナス = 8段目に玉がいて、その真上に駒があるときのボーナス + 8筋目に玉がいてその真上に駒がいるときのボーナス + 穴熊ではなくて、玉の真上に駒があるときのボーナス + 入玉ではなくて玉の真上に駒があるときのボーナス + その88の玉の真上に駒があるときのボーナス


以下略。


とりあえず今回出場するやねうら王はこの方法で学習させてみる。
因子の分解の方法をまだ考え中なんだが、もう二週間切ってるのにそんなことを言っていて大丈夫か…。


■ 2014/10/20 22:45 MagicBitboardはオワコン


コンピューター将棋では飛・角・香のような遠方駒がどこまで利いているのかを得るため、コンピューターチェスの技法であるMagicBitboard*5を使っている人がいます。PonanzaやAperyなどがそうです。*6


しかし、将棋ではMagicBitboardはテーブルサイズが大きくなるのでCPU cacheの汚染がひどく、速度的なメリットは得られていないというのが私の考えで、やねうら王ではMagicBitboardは使っていません。MagicBitboardを使わない場合でも、簡単な比較実験において速度的にはほぼ同等だとわかっています。


それでも、MagicBitboardを使わないと、StockfishのようなMagicBitboardを使うタイプの探索部を参考にしようと思ったときに、そのソースコードと等価にするために苦労するというのはあります。そこで、MagicBitboard自体は使いたくはないが、MagicBitboardのようなことをしたい、例えば玉の8近傍に駒があるかないかを調べるために、occupied bitboardから、王の8近傍に駒があるかどうか直列化して集めてきたいということはあります。


このような将棋ソフト開発者の声がインテルに届いたのか(?)、HaswellではBMIというビット操作を行なう命令が追加されており、これを使うとMagicBitboardと等価なことが簡単に出来ます。
http://d.hatena.ne.jp/LS3600/20141011


簡単にとは言っても、速度的に数%速くなるかどうかだけの話なので、こんな直前に大改造してバグっていたら大変なので私は今回は採用しませんが、BMIはなかなか夢のある命令セットではあります。


■ 2014/10/20 22:50 やね裏評価関数とは何か?


電王トーナメントのアピール文書、「やる予定」「やる予定だけど効果かどうかはわからん」みたいな書き方をしているものもたくさんありますが、ソフトがアピール文通りになっていないからと言って罰則があるわけではないのでそれを見越してやねうら王は適当ぶっこいてるんだろうと邪推している人もおられるかも知れません。


今年はどうなるかはわかりませんが、しかし、去年は私は書いている通りのことはすべてやりました。そのなかでやね裏評価関数についてだけは、説明を書いてなかったのでそろそろオープンにしてもいいかと思い、解説記事を書きました。興味のある方はご覧ください。


やね裏評価関数とは何か?
http://d.hatena.ne.jp/LS3600/20141020#p1


■ 2014/10/21 9:30 棋譜からの学習部を書き起こし中


特徴因子の次元下げがやっと綺麗に定式化できた。NDFがやっている次元下げよりもっと一般的で、もっと(数式的に)綺麗な形で定式化できた。これだと10倍ぐらい収束が早い(当社比)ような気はする。


あとは、棋譜からの学習部を1から書き起こし中である。(いまごろ…) やっと1/4ぐらい書けた。あと3,4日で書いて、AWS(Amazon Web Services)借りて棋譜からの学習やる。高くつくなぁ…。


学習部はソース行数にして5000行程度になる感じ。これ一箇所でもバグってるとうまく収束しないという…背筋が寒くなるな。


■ 2014/10/21 18:30 NDFの近似的並進対称性


NDFの「相対位置を保ったまま3駒を移動してもそれほど価値が変わらない」(AperyのPR文より)というのは、AWAKEがやって、評価部でR250上がったかのように書いてある。(これだけで上がるのかそうでないのかはこのPR文からはよくわからないが…)


上位の将棋ソフトを作っている開発者は、未知の局面(棋譜からの学習のときに出現しなかった特徴因子がたくさん出てくる局面)に対する適応力を上げるためにこういう小細工をいろいろやっているわけだが、数百万局面しかないのに数億の評価関数パラメーターを求めようというのが土台無理な話であって(連立方程式を解くときに未知変数が多すぎる場合に似ている)、そもそも1兆ぐらいの棋譜があれば、ほとんどの特徴因子を網羅できるはずであり、NDFの手法で暫定的につけてある値よりは遥かに合理性のある値になるはずである。


つまり、
棋譜が足りなくて出現しない評価因子がゼロになってしまう(Bonanza 6.0状態) <<< NDFの手法(+R250) < 多項式近似など <<<(超えられない壁)<<< 超大量の棋譜からの学習
みたいな関係式は成り立つのかなと思う。


あとはNDFがやっているように手番を評価関数に追加するとR50〜100ぐらい上がるのかも知れないけど、私は実験していないのでわからない。


■ 2014/10/22 8:30 番組の途中ですが科研費の時間です


なんか知り合いの大学の先生に誘われて経済学のなんかを共同研究することになっているのだが、科研費を申請の締め切りが迫っているのだよ。


GPS将棋を初めとして、大学関係者はこの時期大変忙しいので電王トーナメントに出場するのは結構厳しいような気がする。特に
科研費 >>> (超えられない壁) >>> 電王トーナメントの優勝賞金
であるようなところにとっては…。


■ 2014/10/22 19:30 やねうら王の開発の進捗


棋譜からの学習部、1/4ほどさらに書いた。あと半分ぐらいで完成。実装上のミスがなければ、そこそこ棋力が上がる気はするんだが、気がするだけかも知れん…。AWAKEの評価部でBonanza6から+R250は信じていいのか、否か。時間もないしR150も上がれば御の字であるが。


■ 2014/10/22 20:00 今年のApery・Ponanzaの強さについて


Aperyが今年5月の選手権(世界コンピュータ将棋選手権)のときのバージョンに7割ぐらい勝ち越すらしいのだが*7、+R150ぐらいか。Aperyは5月の選手権の時点でBonanza6の評価関数よりは(評価部において)+R100ぐらい上だったと思うので、Bonanza6を基準に言うと+R250で、AWAKEの+R250とだいたい計算は合う気はする。


Aperyの選手権バージョンとやねうら王2014(5月時点でのやねうら王)はほぼ同じ強さ。やねうら王がいまから+R150になると、Aperyが選手権バージョンから+R150なら、Aperyと同等。


去年の電王トーナメント時のPonanza(=今年発売されたPonaX)は、やねうら王2014に7割ぐらい勝っていたので+R150。
今年のPonanzaは去年のPonanzaから7割ぐらい勝つらしい。*8


つまり、去年から+R150。ということはやねうら王2014からは+R300。やねうら王がやねうら王2014から+R150上がってもまだ今年のPonanzaにはR150も届かない。(そもそも、やねうら王がこのあとR150も上がるかどうかわからん…)


やねうら王2014は5万円の自作パソコンで将棋倶楽部にてR3300程度であったが、今年のPonanzaはここに+R300。そして最新のパソコンで(16コアXeonで)やるとたぶん+R400ぐらい上がって、R4000。将棋倶楽部24でR4000とかバケモンっすな…。もはや羽生さんを連れて来ても2,3割勝てるかどうかすら怪しい。将棋ソフト、この1年で強くなりすぎだろ!ソフトの改良により年間R50ぐらいの上昇と言われてたのは何だったんだよ!ヽ(`Д´)ノ


※ 追記 : 上記のPonanzaの件、間違っているのではないかとコメント欄で指摘もらいました → http://d.hatena.ne.jp/yaneurao/20141015#c1413986160
「勝率70%はいってくれよ・・」*9とのことなのでまだ前回出場時のものに対して勝率70%には行ってないけど、行きそうな雰囲気ではあります…。


■ 2014/10/23 25:00 やねうら未来学習メソッド -- 次元下げその後


相対KPPの次元下げは一般化するのがかなり難しく、今日、試行錯誤しているうちに、3つの定理を発見した。最初、その難しさについて私は理解できていなかったのだが、いまならハッキリ言える。相対KPPの次元下げ、これは難しい。


いまこの定理を解説している時間はないし、そもそもこのような次元の下げ方が妥当かどうかも疑わしいので詳しい話は割愛する。とりあえず私が検算した結果だけ写真で掲載しておく。この写真だけで意味のわかる人にはわかるようになっている。



■ 2014/10/24 20:30 鏡像問題


KPP絶対でもミラー(左右対称)は考慮されなければならない。これはこれで難しいのだが、いま、問題をすごく簡単化してPP絶対についてのみ書くのでプログラマーの人や数学の得意な人は挑戦してみて欲しい。


問題1)
いま、駒P1,P2があるとして、この盤上の升 P1 = (x1,y1) , P2 = (x2,y2)を考える。
盤上の升なのでx1,y1,x2,y2は筋・段を表す1から9までの整数とする。


任意のP1,P2に対して、P1とP2の組が(5筋を対称軸とする)鏡像関係にあるときは同じidを返す関数が必要である。この関数を設計しなさい。


例)
「31金と72金」の2駒が存在する盤面と、「32金と71金」の2駒が存在する盤面とは鏡像関係にあります。(x1,y1,x2,y2) = (3,1,7,2) と(3,2,7,1)が同じidを返さなければなりません。
※ 注 P1 = P2のケースをアリとするかナシとするか、どちらの方法もそれなりに合理性があるが、ここではBonanza6に倣い、P1 = P2のケースもありうるものとする。


ただし、
1) P1,P2は「金」と「金」のように同じ駒種であると仮定して良い。
2) 得られるidは0から始まり整数として連続していること。(欠番があると配列を確保するときに勿体無いため。)
3) 変換のためにid[x1][y1][x2][y2]のような表引きはしてはならない。(メモリが勿体無いため)
4) 小さな計算量で求まること。長い時間のかかるループをぶん回すの禁止。(ここの処理に時間がかかるの嫌なため)


問題2)
問題1)の関数の逆変換も作ること。問題1)の関数で得られたidから、元のP1,P2の升(2通り)が得られること。


問題3)
P1 = (kind1 , x1 , y1) , P2 = (kind2 , x2 , y2) , kindは駒種(0から19までの整数)であるとしたとき、問題1),問題2)と同じようにidを求める関数とその逆関数を設計しなさい。ただし、すべての駒種の駒は、すべての升に置けるものとする。



まあ、上のように書くと難しそうに見えるが、「鏡像関係のものを除くと、P1,P2の組み合わせは何通りあるか」という数え上げの問題に帰着する。これなら大学入試の数学レベルだ。(15分で解けとか言われると涙でそうだが…)