tokoharuの落書き帳

らくがきですよ

藤井四段レーティング予測にベイズ推定を使ってみた

早速ですが、某まとめサイト記事で次のような記述を見つけました（画像をクリックすると読みやすくなります）

f:id:tokoharu-sakura:20170503130444p:plain
f:id:tokoharu-sakura:20170503130448p:plain

以上のように、藤井四段のレーティングは一部の人にとって興味深く、また他のプロ棋士と比較して突出して高い数値を予測する人もいます。せっかくなので私も調べてみました。ベイズ推定を使ったのは初めてですが、個人的には楽しい経験になりました。

前提と予想

まず、将棋界に公式なレーティング指標は存在しません。その代わりに複数の方が非公式レーティングを公開してくれています。今回はhttp://kishi.a.la9.jp/ranking2.html におけるレーティングを予測することにします。現状トップ層は1850後半程度、平均は1550程度です。藤井四段は対局数が十分ではないこともあり、15連勝しても1600程度にとどまります。

例えばhttp://norimune.net/708やPRMLで指摘されているかと思いますが、最尤推定は正確な推定のために膨大なデータを必要とします。藤井四段はプロになってから確認されている対局結果(5/3現在)が公式15, 非公式9であり、これは相当少ないです。また、最尤推定を公式戦のデータのみに適用すると負けデータがないため推定レーティングが無限大に発散してしまいます。したがって、最尤推定で推定するのは危険だと思われます。

ベイズ推定とは

私はしっかり勉強していないので、細かい説明はほかの人に任せることにして、ざっくりとした導入をします。正確性については勘弁してください。

そこで上記の棋士レーティングで考えてみましょう。このとき、「藤井四段のレーティングは、1800・2500が同程度もっともらしい」と言われたとしましょう。どちらを信じますか？

大体の方は1800ですよね。2500はさすがに。。。と考える方が多いと思います。ではこの判断はどこからきたのか？というと事前の情報（=上記の棋士レーティング分布）を既に知っているからです。このような事前情報（事前分布といいます）を考慮に加えたのがベイズ推定というわけです。

やってみた。

Pythonの練習もしたいのでPythonで実装しました。

細かい準備

ここは読まなくても問題ないです。

事前分布の設定です。これは棋士のレーティング分布を正規分布に当てはめればいいだろう、ということにしました。これは例のレーティングページのソースを見て、これをLinux系のファイル操作で適当に処理してデータを整形します。次のような感じです。

$ cut -d '>' -f 9 rating.txt | cut -d '<' -f 1 | grep '[0-9]' | sed -e "s/\$/,/" > rating_arranged.txt

grepは奨励会員などの行で起きる空行を詰めるために行い、sedは単にカンマをつけるだけです。これはpythonの配列にそのまま書き込みたいためです。

正規分布へのフィッティングは scipy.statsのnormを用いました。
norm.fit(kishi_rating)の結果は
(1550.9578313253012, 149.3638862341212)でした。

細かい設定

最尤推定はベイズ推定の事前分布を一様分布にすることと等価なので、ベイズ推定をするプログラムを作れば十分です。

また、対戦相手のレーティングは対戦直後のレートを使いました。ただし2015年度以前のデータは失われてしまったようなので、場合によって2016年度の初期値を使用しました。藤井四段の非公式戦の対戦相手は現在(2017/5/2)のレーティングを使用しました。

近藤誠也五段のデータで最尤推定とベイズ推定を比較

最尤推定よりベイズ推定の方がいいでしょう、と言い続けていますが、本当によい推定法かは過去のデータでチェックする必要があります。
そこで藤井四段の一年前にプロ入りし、特に王将戦で勝ち続けて王将リーグ入りした近藤五段のプロ入り直後15戦のデータをもとにそれぞれ推定させました。

結果：

分位 0.1 0.25 0.5 0.75 0.9
最尤推定 1650 1716 1795 1880 1964
ベイズ推定 1593 1645 1702 1762 1817
ベイズ(25戦) 1629 1672 1720 1769 1814

実際 : http://kishi.a.la9.jp/2016R/1303.html ここにある通り、2016年度後半は1600代後半から1700ちょうどで推移した。

わかること：
最尤推定の予想は1716～1880ということでかなり高い数値を示しており、実際より高い予測を出す傾向にあった。この点でベイズ推定の方が正確な予想をしていそうだとわかる（少し高めぐらいか？）。

留意点：もしベイズ推定の方が優れているとしっかり示すなら、ほかのプロ棋士でも同様のことをチェックするべきだが、大変なので近藤五段に限ることにする。

藤井聡太四段のレーティング予測

本題に入ります。近藤五段の結果でおそらく正確な値を出しやすそうと判断した、上述のベイズ推定を使いました。

分位 0.1 0.25 0.5 0.75 0.9
公式戦のみ(15戦) 1710 1767 1833 1902 1967
非公式戦追加(15+9戦) 1789 1836 1890 1946 1998


現状のレーティング(30位 : 1706, 20位 : 1746, 10位 : 1799)を勘定に入れれば、公式戦の結果だけでも少なく見積もって30位、炎の七番勝負を勘案するとトップ10入りは十分にありえるという結果になりました。そして中央値が驚きで、この予測が正しいなら驚きです。
この結果は高すぎるのかどうか、数か月後が気になるところです。


おまけ（最尤推定）

分位 0.1 0.25 0.5 0.75 0.9
非公式戦追加(15+9戦) 1934 2005 2093 2191 2290

やはり最尤推定は高く出すぎな感じがします。最初の某まとめ記事の結果とも近い部分があります。
個人的には2000～2200というのは拒否感の方が大きいです。

コード : GitHub - tokoharu/predict_rating


議論

  • 事前分布は妥当か？

やはり近藤五段のベイズ推定の結果も気持ち高めに出ているような気がする。
原因を求めるとするならば、今回は事前分布として「プロ棋士全員のレーティング分布を正規分布にフィッティングしたもの」を選んだが、この分布の裾が軽すぎたのかもしれない、とも考えられる。そこで少し裾を重くするために (分散) = 15000程度に抑えてみる。

これをチェックするために高野四段と佐々木大地四段の最初15戦のデータも加えてみた。

分位 0.1 0.25 0.5 0.75 0.9 現在
佐々木四段 1520 1566 1617 1668 1715 1586
高野四段 1416 1462 1514 1566 1612 1521
近藤五段 1580 1627 1681 1735 1785 1699
近藤五段(25戦) 1617 1657 1702 1748 1790 1699
藤井四段(公式のみ) 1675 1726 1784 1843 1899 (将来)
藤井四段(非公式込) 1756 1799 1848 1898 1945 (将来)

なんとなくであるが、前者3名は0.5分位点に近いレーティング値をとっているように思える。そのため、こちらの予測の方が信頼できるかもしれない。また、裾が重くなったため、藤井四段の予測レーティングは本編で紹介したものよりもおよそ40下がった。

これがより妥当かどうかはもう少しまじめに調べないとわからないだろうと思う。
そもそも正規分布も妥当でないかもしれない。

追記

現状一番妥当な(分散)=15000のバージョンで現状の結果を上げる

分位 0.1 0.25 0.5 0.75 0.9
藤井四段(非公式込, 6/4現在) 1777 1818 1863 1910 1953

上との違いは公式戦連勝と豊島戦の敗戦である。
豊島戦での敗戦はチャラになっているらしい。


まとめ

  • 藤井四段のレーティング予測をベイズでやってみた。
  • 近藤五段の結果からベイズ推定の方が比較的まともそうな予測を出すことが分かった。
  • 予測は予測でしかないので、今後の藤井四段にも注目ですね！

◎もし間違いなどありましたらお教えください。

やねうら王での半自動検討（先手中飛車編）

一回くらいこういう解説記事っぽい何か、書いてみたかったんです。
まず動機は次の記事です。
www.fgfan7.com
この記事での５五歩不突きが先手にとって都合がよいことを追認できるか、ということに興味があります。

今回の記事では、有力かもしれない後手からの変化を主に紹介します（以下ですます調は省きます）


ちなみに、参照記事では先手が有利となる変化だったが、これについては７五歩が悪手で７三桂であれば千日手コースに持っていけそうだという見解になった。したがって、先手ももう少しよい手順があればそのほうがよい状況である。

  • (1) ▲７六歩 △８四歩 ▲５六歩 △６二銀 ▲５八飛　△８五歩　▲７七角 △４二玉 ▲４八玉

ここまでは参照記事における手順とおおよそ同じであるが、ここで変化する

  • (2)△３四歩 ▲５五歩

この変化で評価値的には-50から0程度(ほぼ互角後手持ち)になりやすいようである。
しかしだからといって安泰というわけではなく、問題はここからである。

  • (3) △５二金右 ▲６八銀 △３二銀 ▲５七銀 △３三銀


一つ目の変化として、ここで銀をどんどん前に出してみる

  • (4;A) ▲４六銀 △７四歩 ▲４五銀 △３二玉 ▲３八玉 △７三銀

調べてる段階ではこのあたりで評価値-50程度であったが、ここから先手が激しい手順へ持っていける。これを具体的に調べると次のようになった

  • (5;A)▲５四歩 △６四銀 ▲５三歩成 △同　金 ▲３四銀 △同　銀 ▲２二角成 △同　玉 ▲５三飛成 △同　銀 ▲５五角 △４四銀 ▲８二角成 △８八飛打


  • (6;A) ▲６八金打 △８九飛成 ▲８一馬 △９九龍 ▲６三馬 △３二金 ▲４一馬 △３一歩 ▲２八玉 △３三銀 ▲５九歩 △５七桂 ▲同　金 △６九龍 ▲４六桂 △４五銀


このもう少し先まで調べさせたが、結局スコアは-200程度で後手若干有利のスコアだったように思う。

次に玉を囲ってみる

  • (4;B) ▲３八銀 △７四歩 ▲３九玉 △３二玉 ▲２八玉 △７三銀 ▲６六銀 △６四銀 ▲４六歩

次のように進めるとスコア0のような局面がちょくちょく提案されており、怪しい可能性がある

  • (5;B-A) △１四歩

次の変化は今回見つけた変化の中で一番見た目が大変な局面へ進む。

  • (5;B-B)△８六歩 ▲同　角 △４四銀 ▲５四歩 △同　歩 ▲同　飛 △５五歩 ▲７七桂 △５三金 ▲６五銀 △７五歩

この局面の先を検討した結果、現状先手有利のスコアを示している。
しかしブレが大きいこともあり、現状は難解という判断になると思う。

ここまでの結果を総合して若干後手持ちという結果だということを書こうとしたら次の変化が見つかった。
次のような手順の出現で評価値は0から30くらいに切り替わった。しかしこの先も先手有利かというとよくわからない。

  • (4;C)　▲３八玉 △７四歩 ▲４八銀上 △７三銀 ▲６六銀



まとめ

  • 先手中飛車に対して５五歩不突き型を検討させてみた
  • (4;C)以後で後手がよくできれば後手にとってもうれしいが、よくわからない
  • 結局、現状では先手有利とも後手有利ともいえず難しいことが分かった


注)著者自身に棋力は無いので、これも有力、などといった詳しい解説はできません。また、局面図につまらないミスを載せている可能性もあります。ミスについてはコメントをくださると幸いです。

やねうら王で遊んでみた(横歩取り編3)

前回、結局８八角成からがよくわからないとのことだった。
幸か不幸か最近忙しかったのでぶん回した。
一時期互角以上に先手がよくなったようにも見えていたが、
やっぱりよくわからないようだった。

以下の31歩打で後手がよくなるということも無いが、
先手にとっても難しいようだった。

途中で先手がいい感じになる手を探せたらいいけど、やっぱり難しいのかな

(８八角成から)
▲８八銀 △３三桂 ▲３八金 △９四歩 ▲４八銀 △４四角
▲３六飛 △２三銀 ▲１六歩 △１四歩 ▲７七銀 △３四銀
▲７五歩 △４五銀 ▲７六飛 △５四銀 ▲２四歩 △３一歩

結論

やねうら王が96歩のことを好きだったからといって、
進めてみてよい結果が出るかというと必ずしもそうでなかった。

特に８八角成以降の局面は難しさが顕著だったように思う。
しかし、調べさせた局面を眺めると、やねうら王・魔女ともに+50～+150程度のスコアを出すようにはできるようなので、まだ有望な方なのかもしれない

横歩取りの変化を見ていて分かった課題

単一のAIのみでは勘違いする局面というのが出てくるということがわかった。これはあまり好ましい状況とは言えない。
単純な打開策は他のAIでの評価も加えて正確さを高めることが挙げられる。
しかしそれをすると計算時間も少し増えるし、何より自分の技術力のほうが怪しい。
ということで後回しかなぁ。


次のテーマ

角換わりが最近注目されてるようなのでやってみたが、
見たところ相当難しそう。
これは合流などが多く序盤何を指しても得点にあまり影響しないため、
自分の手法に適さないように見える。
有力な指定局面があればまたそこから考えさせるかもしれない


ということで気分を変えて先手中飛車を調べてみる。
www.fgfan7.com
開始局面が序盤過ぎるので、角換わりの時のようにわけがわからなくなる懸念はあるが、とりあえずやらせてみる。

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

前回の記事ではあまり手順を載せていなかったので、今回はそれを補完してみようと思います。
特に今回は前回の記事で示唆された９六歩型が本当にいいのかをを調べるという体でいきます。

実際それぞれの応手に対して必ずしもちゃんと調べているとも言えない状況だったこともあり、
魔女の評価も手元で考慮しつつ応手を調べさせました。このときできるだけ魔女で200点程度獲得できる手順生成を目指しました。
こういう生成はあるソフトだけがよいと判断していても他ソフトではさっぱりということもあるので、そういう意味では有力な証拠にもなると思います。

とはいえ長時間回して確認したわけでもないのでやはり実は誤りだったということも十分考えられますし、そもそも下記手順は最善でない可能性は十分にあります。疑問を示すコメントなどがあれば対応するかもしれないし、面倒だから対応しないかもしれません（そこはすみません）。

符号についても間違いがあるかもしれません（そこもすみません）

現在のバージョンはこれです。
https://www.dropbox.com/sh/sm2idv4a7i16ey0/AADfAFg60EMw8ZgteMNd91yJa?dl=0



基本図は次。25手目9六歩まで


この応手に対して現状考えている手順を示します。ただし後手は魔女に持たせたときの変化になります。現状の最善手としての表示ではないが、ある程度有力な手順だとは思います。

1-a) ９四歩　１六歩　１四歩　の場合
例えば
３八銀　２三銀　３六歩　８八角成　８八銀　３三桂　７七銀　２五歩打　２八飛　２四飛　６八玉　６二玉 ７九玉　３四銀　３七桂　４四角打　２九飛　２六歩　８二角打（下図）　９三香　９一角成　３五歩打　２五歩打　２一飛　２六飛
: 魔女, やねうら200点くらい出る
sfen : ln1g4l/1Bsk2g2/2ppppn2/p4bsrp/9/P1P3PpP/1PSPPPN2/2G3S2/LNK2G1RL w 2Pp 48


1-b) ９四歩　１六歩　２三銀の場合
例えば
４八銀　２四飛　同飛　同銀　３九金　１四歩　２八歩打　１五歩　　　(魔女+150点くらい)
ln1g3nl/2s1k1g2/2ppppb2/p6s1/8p/P1P5P/1P1PPPP2/1BG1KS1P1/LNS3GNL b RPr2p 37





2)２三銀
例えば
３八銀　６二玉　７七角　７七角成　同桂　３三桂　２八歩打　８二歩打　９五歩

ln1g4l/1psk2g2/p1ppppnsp/1r7/P8/2P4R1/1PNPPPP1P/2G1K1SP1/L1S2G1NL w BPbp 36



3-a) ７四歩　４八銀　７三銀
例えば
３六歩　８六歩　同歩　同飛　３五歩　２五歩打　同飛　７六飛　７七角　２四歩打　２七飛
ln1g3nl/4k1gs1/p1spppb1p/2p4p1/6P2/P1r6/2BPPP1RP/2G1KS3/LNS2G1NL w 4Pp 40
ここから７七角成でもしばらく進めて魔女が+200位を出した瞬間があることは確認した。
全体的に+100くらい出てくれている。


3-b) ７四歩　４八銀 ８八角成
例えば
同銀　４四角打　３六飛　４二玉　３九金　３三銀　４六歩　８六歩打　同歩　同飛　８七歩打　７六飛　７七銀　７五飛　８二角打
ln1g3nl/1Bs2kg2/p2ppps1p/2p2b3/2r6/P4PR2/1PSPP1P1P/2G1KS3/LN4GNL w 2P3p 44
ただし評価のゆれが激しく難しそう。

3-c) ７四歩　４八銀 ７三桂
例えば
３八金　９四歩　１六歩　８八角成　同銀　４四角打　４六飛　３三銀　７五歩　６四歩　７六飛　６三銀　７四歩　同銀　７五歩打　６五銀　３六飛　

魔女は+150くらいと評価。

4) ８八角成
不明 : これが一番後手希望があるように見える. 調査中


結果だけだと淡白ですが、裏では色々な局面を試していて大変でした。
やはりソフトが異なれば見解が大きく異なる局面が出てくるなあと思いました。

また、これは主観ですが、長大な手順を考えるとなるとAIでの評価は大変なのかなと思いました。やっぱり勘違いのようなことはあるし、それを指摘しても相手は納得してくれないからすべてを指摘しないといけないのは相当骨が折れる作業だと思いました。

やねうら王で遊んだ話（横歩取り編）

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

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

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

お話の内容は「将棋ＡＩを使って序盤の研究っぽいことできないかなぁ」というものです。といっても私自身は将棋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の読み方

・一行の情報の意味
３三角[２二],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
これを読みました。まふ定跡は全く知らなかったので参考になりました。
やっぱり定跡作るのにも色々アプローチがあるのかなぁということを思ったりしました。

最後に

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

オイラー線の証明

大昔にダイアリーに書いてプライベートになったものを改めて見返したら
面白いことが書いてあったのでここに再掲しておきます


△PQRの重心、外心、垂心をそれぞれG,V,Hとする。
PQ,QR,RPの中点をそれぞれS,T,Uとする。

△PQRは△UTRをR中心に2倍に拡大したものなので、
HRの中点Aは△UTRの垂心と一致し、
TUの中点をMとすると、
△STUの垂心でもある点Vと点Aの中点はMとなる。

また、SG:GR=1:2であり、GM:MR=1:3である。

以上より、メネラウスの定理の逆、およびメネラウスの定理より
3点UGHは同一直線上にありVG:GH=1:2

特殊な場合もありそうですがまぁ大体こうなりそうです

ところで他の証明は
オイラー線の３通りの証明 | 高校数学の美しい物語
これが詳しいのですが、自分の証明のほうがより初等幾何っぽさが強くないですかね？

・・・と思ったけどよく考えると結局本質は VS:RH = 1:2なのでほとんど変わらないですね。

改めて読み返すと STUの垂心がVになることがわかりませんでしたが、外心の性質を思い出すとPV=QVだからVSとPQは直交するから言えるんですね。

さらに調べると次の動画の方がわかりやすいなぁと思いました。
www.youtube.com

こういう動画が大昔にもあれば僕がこんな記事書かなくてもよかったのに。