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

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/708PRMLで指摘されているかと思いますが、最尤推定は正確な推定のために膨大なデータを必要とします。藤井四段はプロになってから確認されている対局結果(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下がった。

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

まとめ

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

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

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

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

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


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

  • (1) ▲7六歩 △8四歩 ▲5六歩 △6二銀 ▲5八飛 △8五歩 ▲7七角 △4二玉 ▲4八玉

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

  • (2)△3四歩 ▲5五歩

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

  • (3) △5二金右 ▲6八銀 △3二銀 ▲5七銀 △3三銀


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

  • (4;A) ▲4六銀 △7四歩 ▲4五銀 △3二玉 ▲3八玉 △7三銀

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

  • (5;A)▲5四歩 △6四銀 ▲5三歩成 △同 金 ▲3四銀 △同 銀 ▲2二角成 △同 玉 ▲5三飛成 △同 銀 ▲5五角 △4四銀 ▲8二角成 △8八飛打


  • (6;A) ▲6八金打 △8九飛成 ▲8一馬 △9九龍 ▲6三馬 △3二金 ▲4一馬 △3一歩 ▲2八玉 △3三銀 ▲5九歩 △5七桂 ▲同 金 △6九龍 ▲4六桂 △4五銀


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

次に玉を囲ってみる

  • (4;B) ▲3八銀 △7四歩 ▲3九玉 △3二玉 ▲2八玉 △7三銀 ▲6六銀 △6四銀 ▲4六歩

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

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

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

  • (5;B-B)△8六歩 ▲同 角 △4四銀 ▲5四歩 △同 歩 ▲同 飛 △5五歩 ▲7七桂 △5三金 ▲6五銀 △7五歩

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

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

  • (4;C) ▲3八玉 △7四歩 ▲4八銀上 △7三銀 ▲6六銀



まとめ

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


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

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

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

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

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

(8八角成から)
▲8八銀 △3三桂 ▲3八金 △9四歩 ▲4八銀 △4四角
▲3六飛 △2三銀 ▲1六歩 △1四歩 ▲7七銀 △3四銀
▲7五歩 △4五銀 ▲7六飛 △5四銀 ▲2四歩 △3一歩

結論

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

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

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

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


次のテーマ

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


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

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

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

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

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

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

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



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


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

1-a) 9四歩 1六歩 1四歩 の場合
例えば
3八銀 2三銀 3六歩 8八角成 8八銀 3三桂 7七銀 2五歩打 2八飛 2四飛 6八玉 6二玉 7九玉 3四銀 3七桂 4四角打 2九飛 2六歩 8二角打(下図) 9三香 9一角成 3五歩打 2五歩打 2一飛 2六飛
: 魔女, やねうら200点くらい出る
sfen : ln1g4l/1Bsk2g2/2ppppn2/p4bsrp/9/P1P3PpP/1PSPPPN2/2G3S2/LNK2G1RL w 2Pp 48


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





2)2三銀
例えば
3八銀 6二玉 7七角 7七角成 同桂 3三桂 2八歩打 8二歩打 9五歩

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



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


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

3-c) 7四歩 4八銀 7三桂
例えば
3八金 9四歩 1六歩 8八角成 同銀 4四角打 4六飛 3三銀 7五歩 6四歩 7六飛 6三銀 7四歩 同銀 7五歩打 6五銀 3六飛 

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

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


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

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

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

(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
これを読みました。まふ定跡は全く知らなかったので参考になりました。
やっぱり定跡作るのにも色々アプローチがあるのかなぁということを思ったりしました。

最後に

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

オイラー線の証明

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


△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

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

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

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

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

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

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

将棋AIで定跡を作れるか試してみた2

追記(5/6) : 有力でかつ少しだけ激しい局面に入った時にその手が抹消される恐るべきバグを見つけてしまったので信頼性が揺らいできました


前回の記事から数か月がたっていた。
tokoharurakugaki.hatenablog.com


まずは、いろいろいじって数か月でわかったことを書いていき、
最近やってみたことの結果などを書いていきます。

  • そもそも前回やった8手は少なすぎて意味がない。
  • もっというと15手でもあんまり意味が無さそう
  • 深さ22手くらい読ませないとあんまり意味がないのでは?
    • 根拠 : Aperyの局面評価が収束するのが大体そのくらいだから。
    • Fail High, Fail Low が起きるのは仕方ないのでそれを除くと22手くらい
  • やねうら王Classic-tceでは深さ22を読ませたいが、これは局面によって単位時間で読める深さが異なる。
  • この意味では矢倉が読んでくれやすそうなのでやはりこれを採用する
    • つまり開始局面は新矢倉24手組
      • ln3kbnl/1r1sg1g2/p2p2spp/1pp1ppp2/9/2PPP1P2/PPSG1P1PP/2G2S1R1/LNBK3NL b - 25

アルゴリズム(ふんいき)
1. 読ませたノードのうち、一番読ませた方がよさそうなところをいい感じに決める
2. 読ませて少し展開 : ただしここはかなり適当。1~3手程度が展開される。
3. 1へもどる

生成局面数 : 数千

  • 数千、とぼかしているのは、途中で生成順序のミスが見つかったり、細かい調整をしているので無駄な局面を多く生成していると考えられるため、正確な数を書いても意味がないから。

結果

千日手っぽい局面が大量に生成される。

大量に生成されている様子はおまけとして下に書く。

理由を考えると

  • この探索方法では、例えば激しめの展開の末端局面では評価値が大きく変化してしまう可能性がある
  • 一回大きく変化してしまうと局面探索の優先度が大きく下がってしまう
  • 特に矢倉で消極的な手を選び続けると互いに相手へ攻めていけない状況へは容易に到達してしまう

といった理由が重なってうまくいかなかったと思われる

どうすればいい?

回避策としてまず考えられるのは千日手のスコアを-100にするとかだが、この場合は千日手にできる手が多すぎる可能性が高くうまく機能しない可能性が高い。
適当に飛車を動かすだけで局面数は結構増え得るのに金銀玉なども動かして千日手的状況を保てる可能性が高いからだ。(もちろん千日手を避けた時の評価によるけど、どうせ穏やかな変化ばかり続くと考えるとあんまり期待は持て無さそう?と思ったり。)

したがって、ちょっとやそっと実装を変えたところで結果は大枠変わら無さそうに見えるので、ほとんど手詰まりに見える。

次はどうするか?

念のため千日手の評価を下げた版でもうちょっと眺めてみる。

あとは、どう穏やかに進行しても千日手を避けてくれそうで、深さ22くらいでもぱっぱと読んでくれそうな局面を開始局面にして調べる、ことですかねぇ。何があるんだろう。

おまけ

もちろん内部的には千日手は回避するようにしてますが、それでも厳しいですという意味合いの表です。
最適局面からの離れ具合が小さい局面ベスト300をベタッと貼ります。200局面が評価0になります。
読み方は、不正確な表現ですが、
左から最適局面からの評価の離れ具合、その局面の重要度、その局面のsfenとなっています。千日手かつそれが最適解なら離れ具合は0といった気分です。

続きを読む