読者です 読者をやめる 読者になる 読者になる

tokoharuの落書き帳

らくがきですよ

やねうら王で遊んだ話(横歩取り編)

(UPD :この記事の続編です。こちらもどうぞ やねうら王で遊んでみた(横歩取り編2) - tokoharuの落書き帳 )

この記事はコンピュータ将棋 Advent Calendar 2016 - Adventar12/16分の記事です。

コンピュータ将棋界隈の人ではないのですが、枠が余っていたので登録してみました。

お話の内容は「将棋AIを使って序盤の研究っぽいことできないかなぁ」というものです。といっても私自身は将棋AIを強くするという目的でやっていたわけではないので、通常開発者がやるべきこと(勝率を測るなど)は行っていないことに注意してください。鑑賞用の定跡か研究だと思うのがよいかと思います。

個人的にはこれらの結果に対して棋力の高い人からのフィードバックがあれば大変嬉しいですが、それ以外のツッコミも募集中です

結果を早く知りたい人は「結果」の項目へジャンプしてください。

生成用プログラムについて

コンセプトと長所短所

最近は随所で将棋AIを使って研究するという話が見られるのですが、おそらく評価値を見るだけではAIが良いと言っている方向に数手進めてみると評価値に簡単に裏切られる(そして疲弊する)ので自分なら自動化したいなぁということで、自分が序盤を研究する人という体で、そのあたりの自動化・可視化の意味で作ってみました。

また、後述するように探索部には手を加えておらず、サブルーチンとしてやねうら王を使い、その時点で知っている評価値だけを見て次に考える局面を決めます。これが意味するのは
・通常の探索で深いものとは異なった結果を出す。
・特に中盤の難しい局面において深さを深くすれば現れるような指し手は、浅い探索では悪い評価である可能性があるため、そういう手を見過ごす可能性は十分にあるので中盤の手は信用し過ぎないほうがよい
・似た理由だが、難しく評価値が探索中に大きく上下する局面はその後再び採用されずらいので、有力な手順を見逃している可能性がある。
・展開がおそい。序盤の合流がおきやすい局面では特に無駄に重複した局面を読んでいる可能性がある。
といったことになるかと思います。

最後のポイントは局面によっては致命的であり、実際角換わりで同じことをしようとすると手の順序に関して自由度が高すぎるために似た評価値を持つ局面が大量に生成されるため現状うまくいかないのですが、今回の横歩取りではこのタイプの自由度は大きくないためそれっぽく動いているのだと思われます。
この点を根本的に避けようと思うと探索パート内部を変更する必要があって大変そうに思います。

しかし悪いところばかりではなく、
・自動でたくさんの局面を調べるので、自分で局面を入力しなくても勝手に評価してくれることがある
・単純にどんな局面を探してるのかを鑑賞できるので面白い
くらいの長所があると思います。


アルゴリズム(大雑把)

あまり深くは立ち入りませんが
・やねうら王Lateをサブルーチンとして使って
・ノードを少しずつ展開していく。
・展開の仕方はProgressive Wideningの亜種。
・亜種というのは本来勝率を使うところを評価値に変えた点が異なる
という方針です。

1局面あたり5000万ノード以上読ませて、数万局面あるかと思います。

また、開始局面を手動で変えて様子を見ることがあるため全体としては半自動です

結果

次のフォルダです。なお、プロがいうところの定跡はできていないと思いますが、指している手について感想があれば教えていただきたいです。
https://www.dropbox.com/sh/oinx05vwu9fme5i/AADOIRV53deEopb3x8hiu0u5a?dl=0
見た目は大体こんなのです(ただしバージョンが異なるため中身の内容は異なります)
f:id:tokoharu-sakura:20161217185036p:plain


ファイルの開き方や使い方のヒントは後述します。

リンクを開くと dbとtreeの二種類のファイルがあります。treeはdbから可視化のために生成されたものなのでdbが元データになります。
smallとあるものは端折ったものでファイルサイズも小さいのでまずはそちらを開くのが良いかと思います。
dbはほとんどやねうら王フォーマットで自分用に修正したものですが、修正分は使わなくてもよさそうなのでそのうちやねうら王フォーマットに戻すかもしれません。(しかし指し手と評価値以外は信用できない値なのでそこも直さなきゃなぁ...)

treeの読み方

・一行の情報の意味
3三角[2二],100,0,lnsgk1snl/6g2/p1ppppb1p/6R2/9/1rP6/P2PPPP1P/1BG6/LNS1KGSNL b 3P2p 17 であれば
「前の局面からの指し手、新しい局面での評価値、ズレの総和、sfen(その局面を表現した文字列)」を表します。
指し手の表現はおよそ将棋所であるような形式だと思います。
また、「ズレの総和」というのは、例えば次善手を選んだ時に最善手からの評価値の差を知りたくなるので、そういう量の総和を表すことにしています。


・複数行の意味
ある局面の直下に一手進んだ先の局面があるとき、先の局面に進むのが最適な手順であることを表すため、これを繰り返せば想定手順ということになります。評価値はその局面からやねうら王を使って読ませたものではなく、先ほどの手順で辿った終端の局面で読ませたものになります。

・重複(同一手数)
重複している局面(sfen)は(duplicated)と表記されています。どれかひとつにそれ以後の局面の情報があります。

・重複(非同一手数)
非同一手数で重複している局面は実は扱いが雑で手が浅い局面に合わせただけです。tree上では行き止まりになっています。このあたりはいずれ修正します。

鑑賞のためのヒント(非開発者向け)

1. ファイルがバカでかいので困る。
メモ帳から開こうものなら大変なことになるので他のエディタを使うことを推奨します。Visual Studioからでも見れますが、それ以外なら自分は次のTeraPadで動作することを確認しましたので紹介します。TeraPad - 窓の杜ライブラリ

2. sfenから局面の再現,さらにsfenへの再変換をしたい
局面識別のためにsfenを使用していますが、sfenを将棋版で表現される形に直そうと思ったときは将棋盤局面図を作成が便利です。
「任意のsfenを入力」をクリックしてコピペすれば局面を表示してくれます。sfenへの再変換もできるのでこれを用いてtree, dbでの検索が可能になります。(sfenの最後の数は手数を表現しているが、sfenへの変換の際には手数が1になるはずなのでこれを除外して検索するのがよい)

3. ある局面に対する指し手リストを見たい
ある局面に対して指し手のリストが気になることがあると思いますが、treeから辿って確認しようとすると労力がかかることが想定されます。これはdbファイルを開いてそのsfenで検索すればわかるのでこれを使うと便利です。

指し手表現は "2b3c"のような形で、前2文字が移動前の位置、後2文字が移動後の位置を表す。成りは+, 打ちは*であらわされ、このとき英大文字は駒の種類を表す (Pは歩, など)


生成される様子を眺めていた感想

・全体的に9六歩(+5八玉 or 6八玉)と突く系統の局面にはおよそ+100のスコアがついている場合が多く、SILENT MAJORITYではそこまで差が開いていないように思えたので、やねうら王さんのクセなのでしょうか?長時間ぶんまわしても結局否定できなかったので、実は本当に先手がよいということが分かったりすればアツいと思うんですがどうでしょう(夢見すぎかなぁ)

例 :

・飛車ぶつけは採用したがらない?
・6二玉と早上がりする手も推奨したときあって驚きましたが、結果では先手側に少し振れました。

から例えば

に行きつくらしい。

・当初、コンピュータ将棋が発達したからプロが言うような定跡も割といい感じに作れたりしないかという淡い期待を持っていましたが、相当難しそうだなぁという感じました。

細かいQ and A

Q. なぜやねうら王2017 Earlyではないのか

A. 横歩取りに関してはearlyが公開される前からぶん回していたから

Q. なんで普通のProgressive Widening、つまりプレイアウトの勝率を使わないのか

A. 将棋は弱いプレイヤーがプレイした結果の積み重ねよりも強いプレイヤーの考えのほうが有用だと思うから強いプレイヤーの評価値を使うほうがましかなぁと考えたため。そもそもこの考え方が正しいのかは怪しい気がする。


Q. 評価値使うっても評価値って割とブレない?困らない?

A. ブレて困ります。数十くらい評価値がブレ得るのに、100くらいの範囲の評価値に収まる局面は数千単位でありそう。こんな候補から最善を探し出せる気がしない。実際、少し走らせればtreeもダイナミックに変化します。


Q. 人間の定跡を超えてるか?

A. 棋力がないのでわかりません。
ただ次のようなことは起きました:
「ぐぐって出てくる定跡を調べていないようなのでその局面を入力してしばらく考えさせると評価値を当初のものから100くらい変えて有力な変化だと考えを改めた。」
とはいえ、こうなることを期待して調べさせたことは何度もあったが、こういう事例はほとんどなかった。


Q. そのほか工夫した点は?

A.
1. 主にtceで遊んでいたとき、生成される局面がせいぜい20手先-30手先くらいのもので、これでは先まで読んでいるとは言いがたいので、進んだ局面ほど重みを増やした。Progressive Wideningの思想であれば調べてない局面に重きをおくべきだが、いつまで経ってもはじめのほうの局面しか展開してくれなかったのでこうした。もちろん短所はあって、頑張ってたくさん調べた局面以下がよさげな一手で無意味になるという可能性がある。どうするのがいいんでしょうね。

2. 評価値のみを使って探索するということは、一度使われた評価値はずっと使われる可能性があり、そうすると展開したい局面が似たようなものばかりになることが多くつまらなくなりがちだった。なので、実際の評価値から正規分布のノイズを加えることで多様な局面を調べることができるようにした。ただノイズは大きすぎても調べたい局面が膨大になるだけなので加減が難しい。手動でノイズの幅は調整している。


裏話

魔女の評価値と見比べつつ決着が付きそうなところまで掘り進めるのがゲームっぽくて楽しかったです。くじらちゃんじゃないですけど、ゲーム要素を付け加えて勝手に探索してもらってどんどん序盤ファイルを作れたら面白かったりしないかな、と妄想していました。それから、dbを検索すると妙に深い局面があると思いますがそれはそういうことです。

実は某所将棋部の方に前のバージョンを見せたことがあるのですが、そのときの反応は「互角のままで終わってもどうもいえない」というもので、こちらが「やっぱり最低40手先まで読まないと厳しいですか」と尋ねるとそれに肯定的でしたのでこれが目標になりました。いくつか修正を加えましたがそれでもなかなか厳しかったです。

一方調査用に一冊序盤の本を買いました。読んでみて少しハッとなったのですが、人間の定跡では「難解」という評価があるのですね。プログラムでそれをうまく表現するにはどうするのがいいのだろうなぁ。

今後

一番問題になりそうなのは評価値が大きくブレる局面をどうするかなので、これをどうにか扱いたいです。
なので、ブレていればさらに深く調べるルーチンを加えるのがいいんでしょうか。しかしこれも調整をしないとどこまでも深く調べようとするかもしれませんし難しいですね。探索の技術をもう少し学んだほうがいいのかもしれません。

何かコメントがあればぜひお願いします。

(おまけ)qhapaqさんの記事の感想

qhapaq.hatenablog.com
これを読みました。まふ定跡は全く知らなかったので参考になりました。
やっぱり定跡作るのにも色々アプローチがあるのかなぁということを思ったりしました。

最後に

やねうら王を開発・公開して下さっているやねうらおさんに感謝いたします。やねうら王でなければここまで遊べていなかったかもしれません。