やねうら王の連続自己対戦フレームワークを用いて勝率を計測しているのですが、計測するごとにばらつきがあったりして、安定した結果とは言いがたいです。
この新しいApery評価関数、前回から強くなってない可能性が微レ存。詳しくはメールしますた。(｀･ω･´)ゞ https://t.co/H49x1zfb7n
— やねうら王 (@yaneuraou) August 4, 2016
Apery20160730 vs Apery20160803 1万対局
1手0.1秒 , 5464 – 83 – 4453(55.1% R35.54)
1手0.3秒 , 5409 – 115 – 4476(54.72% R32.89)— やねうら王 (@yaneuraou) August 4, 2016
いくつかの原因はわかったので、それについては修正済みです。自己対戦で勝率を見る上でつまずきそうなところを、私の知る限りをざっと書いておきます。(なお、自己対戦自体は、3千局〜1万局こなしているものとします。)
1) 定跡、あまり長い手数まで採用すると、優劣がかなりのレベルでついていることがある。
例えば、32手目まで定跡を採用すると、駒得だけの評価関数であってもApery(WCSC26)に対して3%ぐらい勝てるようです。激しい戦いになっていると、ひたすら駒得だけ考えてもそれなりに正解手が指せるんでしょうね。
形勢が微妙に傾いているものなども考慮すると、勝率に対して3〜5%ぐらいのノイズが載っていると考えるべきでしょう。(勝率5割に引き寄せられる。)
それだと計測自体かなりいい加減なものとなってしまうので、定跡は早い段階で打ち切りたいのですが、そうすると今度は同じような進行になってしまい、今度は勝率が一方向に偏ります。(勝率が0%か100%のほうに引き寄せられる。)
2) 1手あたりの思考時間をランダム化する弊害
1手あたりの思考時間を設定値から1〜1.5倍ぐらいにランダム化することで、指し手をばらつかせて、同じ試合運びになるのを回避していたのですが、これだと終盤で1.5倍を与えられたときに相手より先に詰みを見つけたりして、やはり勝率が5割に引き寄せられるようです。
そこで、序盤はランダム化を強くして、終盤はランダム化を小さく(終盤ではすでに異なる局面になっているだろうから)することでこの問題を緩和できます。
具体的には、やねうら王では、
t = t * min(1.5f , 1.0f + 10.0f/ply);
のようにして対局させています。
また、定跡でばらけさせるために、定跡の終端で何らかの評価値をつける方法もありますが、その評価値をつけるための探索資源がもったいないだとか、手間が馬鹿にならないだとか、そのソフトが好む展開ばかりが高い点になるだとか、これはこれで悩ましいです。
なので、上記のように1手の指し手に与える持ち時間をランダム化するほうがお手軽で、そこそこうまくいくアイデアのような気はしています。(両者の比較データは持ちあわせていないです。)
3) 短い秒数だと終盤の特徴を高く評価しているほうが勝ちやすい
短い秒数での計測だと詰みに絡む特徴(玉の上空に敵の金・銀がいるかなど)を高く評価しているほうが、詰みそうな局面に高い点数をつけるので、そちらを優先して探索するようになり、詰みを見つけやすくなるというのはあります。ところが、序盤でそんな局面を探しても結局は詰まないので、無駄に探索していることになります。
そんなわけで、短い秒数と長い秒数とでは勝率の高い評価関数の性質がやや異なるようです。
ただし、現実的には長い秒数で十分にテストすることは出来ないので、短い秒数で勝率が上がっていれば、強くなっているとせざるを得ない意味はあります。
4) 置換表のサイズが小さいとまずいかも
私の実験環境では自己対戦は、1PC 80論理コアでやっているので、1PC内で160個の思考エンジンが起動しています。メモリがもったいないので評価関数バイナリは共有メモリに配置しています。置換表はメモリがもったいないので16MBだけ確保するようにしています。これでも0.1秒ならそんなに問題はないのですが、1秒以上になってくるとおそらく探索効率が悪化するので、結局、本来より短い持ち時間で対局させているときと同じような結果になります。(十分なデータがなくてどれくらい悪化するのかはわかりませんが…)
5) 論理コアの数だけ思考エンジンを立ち上げるのは難しい
思考時間がほとんど与えられないプロセス(Windows OSのprocessの意味)が出てきたりして、それが勝率計測上、ノイズとして作用しかねないだとか。(勝率が5割に引き寄せられる)
探索を時間で打ち切るより、探索node数で打ち切るほうが、実験環境のCPU差などに左右されなくて良い可能性があります。(ただ、探索部の調整のときはそれだとうまくいかない…)
6) 自己対戦サーバー側に何かバグがある可能性が微レ存
スミマセン、スミマセン(´ω｀)人 バグを発見された方は報告ください。
7) 思考エンジン側に何かバグがある可能性が微レ存
スミマセン、スミマセン(´ω｀)人 バグを発見された方は報告ください。
8) 短い思考時間だと時間制御のアルゴリズム上の問題で、より短い時間で指してしまうだとか。
スミマセン、スミマセン(´ω｀)人 バグを発見された方は報告ください。
まとめ)
他にも「この計測方法はおかしいのでは？」というのがあればコメント欄などで教えてください。
定跡の終端に来たところでSFENスナップショットをファイルに出力して、次の開始時にSFENファイルがあったら、先手後手入れ換えて必ずもう一番指すようにするとか。
その終端の局面が互角に近い局面でないと、先後入れ替えて指しても、先手側(or後手側)が高い確率で勝ってしまうので、勝率として見たときは5割に引き寄せられてしまいます。
おっしゃる通りです。
が、そもそも平手の初期局面自体、先手有利52％くらいじゃないですかね。
初手94歩で互角とか？
1.先手有利53％局面を複数先手後手入れ換えて用いることで、51％だけ勝ち越すバージョンの有利を検出できるかどうか。
2.できるとしてその必要な試行回数は、完全互角局面を用いた場合に比べてどの程度増大するか。
3.先手有利の割合が不明な局面を用いた場合はどうか。必勝局面を用いた場合は検出不可能なことは明らかですが。
という統計学上の問題にある程度目処をつけないと、どこをどの程度改善する必要があるかわからない様に思えます。
暫定的直感的には、
1．できる
２．有利度が予め正確にわかっていれば問題ない。
ノイズが混ざるので局面自体の有利度と検出すべき差に応じて試行回数を増やす必要がある
３．先後入れ換えで偶数回指せばいい。試行回数をどの程度増やすべきか不明。
というとこでしょうか。
解決法としては、最新バージョンの自己対戦で互角度を検出し保証したやねうらテスト局面集を千～1万局面位用意するとかですかねえ。
まあ、序盤でわずかに優位を築いても、そのままその優位を拡大して勝ちきるためには、長い持ち時間でないといけないというのもあって、1手1秒ぐらいの対局ではそれが出来ないため、逆説的に、序盤のわずかな差は無視できる(互角だとみなせる)というのはありますけどね。
評価関数以外の要因で勝負が決まるのを避けたいということですよね。
すると、思考時間を乱数で上下させること自体でノイズを入れ込んでると思えます。
先手に与えた時間と同じだけ後手に与える方法もありますが、将棋の性質上、先に時間かけて良い手を見つけた方が有利でしょう。
指し手を無理にバラけさせると勝率に影響する。
勝率への影響だけキャンセルしたいならば、
バラけ後の局面で先後入れ換えで指すしかないのでは。
それでもバラけ局面自体の偏りで5割に引っ張られますが。
そこを避けるには、バラけ局面自体を同一エンジンで自己対戦してフィルタしてノイズを濾しとるしかないように思えます。
HTは2スレッド平等にCPU資源割り振るとはかぎらないとすれば、、、杞憂な気もしますが、、、
プロセス数を物理コア数に一致させてlazySMP切ってシングルスレッドモードで対戦すればノイズが減るのでは。
もしくは探索ノード数で平等にするかですかねえ。
持ち時間の勝率への影響ですが、将棋の性質上、長い時間が必要な局面で不十分な時間しか与えられず、先に悪手を打った方が不利になる、と言うべきですか。
> すると、思考時間を乱数で上下させること自体でノイズを入れ込んでると思えます。
まあ、それを言いだすと、0.1秒対局もぴったりでは止まれないので思考時間に毎回10数%の誤差があります。完璧なテストをしようと思うと、そのへんも無くすほうが良いのでしょうけども…。なかなか難しいですね…。
そうは言っても，探す砂金がどんどん細かくなってるので，既知の濁りは地道に一つ一つ取り除いていくしかないのでは？
多少揺らぎがないと局所最適にはまり込むだけかもしれませんが。嵌ってから抜け出す方法を考えればいいとも。
ミリ秒単位で正確な割り込みが入らないなら，時間固定ではなくNODE数かDEPTH固定で計測するべきと思われます。評価関数比較用に，浅いDEPTHの全幅検索モードを作るとか。
ただ…
・強くなったかどうか
・どのくらい（レート）強くなったか
・短時間で結果を知る
という３つの目標ですが…
テストケースのノイズを取り除かずにブラックボックスでも，うまい方法があるような気もするんですが。
数学パズルみたいな。
AとBを比較するのではなく，AとC,BとCを比較するとか，同じテストケースを毎回使うとか，ひっくり返すとか……
SPAM避けでコメント内にURL入らんのですね。
下欄に入れてみました。直接本件と関係ないですが。
> 探す砂金がどんどん細かくなってるので，既知の濁りは地道に一つ一つ取り除いていくしかないのでは？
まあ、そうなんですけど、そのへんはノイズがある程度あっても対局回数を大きくすると2つのソフトのどちらが強いか自体は計測できますから、それよりは現状、長い時間でないと計測できない探索パラメーターなどをどうチューニングするかが喫緊の課題ですね…。
囲碁ソフトの開発の場合、９路盤で４子、１９路盤で８子置いた互角とされる局面が公開されており、その局面から白黒両方を持って評価しています。ただ、そのような局面を３０００～１万用意するのは大変ですね。
もう少し序盤が上手になったら、やねうら大定跡を整備しなおして、ある程度深い探索をして互角に近いとわかっている局面のみから自己対戦をスタートするようにすれば、改善される可能性がなくはないですね。そのソフトの好みそうな戦型(振り飛車は避けるだとか、角換同型腰掛銀は避けるだとか)が出現しにくくなるのをうまく回避できれば。
チェスでの知見は役に立たないものなのでしょうか？
stockfishのフォーラムではどういうふうにしているのかとか。
Stockfishのfishtestでは、テストごとに対局条件(対局回数と思考時間)を変えているような…。ものによっては1手1秒未満の短い時間でもやっているようですけど。
Stockfish も参加するコンピューターチェスの大会では互角局面を50か100用意して先後入れ換えで勝ち数競うとあったきがします。
開発中も同じやり方かはわかりませんが。
あと、９路盤で２子おいたオープニングは、組み合わせを網羅的に作成し、条件をかえながら先後ともGnuGoというソフトで１０回対戦させて 勝率の偏った物をスクリーニングして自前で用意しました。ただ、定石を実装する事を考え、今は２子置いた局面は利用していませんが。
将棋でも、自己対戦で勝率が偏らない局面を自動で収集する商法が使えるかもしれません。
強さが拮抗してくると、勝率5割に拮抗してくるんじゃないでしょうか。特にヒューリスティックな変更を加えたわけではないでしょうし、どっちも勝ちに来てるのだから同じ頭脳を使うことで、あとは先攻後攻くらいしか優劣が付かない感じかと思います。
その結果、頭脳が同じである程度ランダム性も拮抗していれば、最新に勝つことも負けることも拮抗して結果、片方の不得意で負けて得意でかつということになりませんかねぇ。それがトータルで数%しか変動しない理由かなーと思いました。
統計ではなく、エレメントである1局ごとに何らかの評価を付ける日が来たのでしょうか？？
ちょっと自分が何言ってるかわからなく・・・。Orz
どこかで棋力が頭打ちになり、思考時間を倍にしてもわずかにしか強くならない時はきそうですけど、まだ全然そんな段階ではないようですよ。
いつもお世話になっております。
初心者ながら生意気にも少し考えたことがありますので、ご参考になればと思い書かせて頂きます。
いろいろ問題点と思われることを書かれておられるのですが、これらの切り分けのために一つだけご提案させて頂こうと思いました。
2) 1手あたりの思考時間をランダム化する弊害
という点ですが、分かっておられるでしょうが、このようなことをしている場合、一万局程度でも、統計的には有意であっても、なおサンプル数が足りなく勝率がばらつくという可能性もあります。（どの程度のばらつきが出ているのかが分からないためにこのような書き方になることをお許しください）
なので、検証のために評価関数も同じものを用いて自己対戦した場合の勝率がどのようになるかを検証する必要があるのではないでしょうか。
ばらつかない場合は、ほかの問題点が考えられるということが確定する上に、先手、後手のどちらを持った場合に勝率が良くなるかの検証にもなり得ます。
つまらない考えかもしれませんが、どうぞご一考頂ければと思います
まあ、原因究明の一環として、まったく同じソフト同士を対局させて(統計的な意味での)分散がどれくらいになるかは調べておいたほうが良いですよね…。うーん、そうか…。
いつも大変お世話になっております
今回最新版のドキュメントを見て少し気になることがありましたのでコメントさせていただきます
一億局ほど対戦されても勝率が収束しないということを実験されているようですが、気になるのは、勝敗というのが一様分布であるかどうかという点です
たとえばですが、あるソフトの評価値が先手に＋1500点ほどになっていた場合、全ての手を詰みまで読むとき先手の勝ちが900万通り、後手の勝ちが100通りほどあるとすると、この場合、純粋な乱数で手を散らしてもこれから後手が勝てる割合は１割ほどしかないということになります
つまり、純粋にランダムに手を選択した場合であっても、早い段階で点差がつく手順と、比較的永い手順まで互角であるような場合は当然勝率が異なってくる場合があると思われます。
このような場合一様分布とは言えず、一億局の対戦であっても、勝率にばらつきがでる可能性はないでしょうか。
不勉強で統計学がこのあたりの問題をどう扱っているのかはわからないのですが、収束しないことを問題視されているようでしたので、問題提起をさせていただきました
また例によって慌て者のわたし故の過ちであったとすれば、先にお詫び申し上げます
お目汚し失礼しました
> 早い段階で点差がつく手順と、比較的永い手順まで互角であるような場合
まあ、急戦だと定跡を抜けて数手で優劣が決することはありますし、そういう形だと強いほうの力が出にくくて、勝率が5割に引き寄せられるというのはあるでしょうね。まあ、その局面がよくある進行の一つであるなら、そういうのも仕方ないかなと思いますけども。
いつも迅速なご返答ありがとうございます
説明が悪くて、意が十分通っていなかったかもしれないと思いまして補足させていただきます
ある局面から勝敗が決する局面数の多寡が勝敗の濃淡に影響している可能性もあると思います
つまり、勝ちが五万局面あるような手順と五〇万局面あるような手順を同等に比べられるのかという問題です
お忙しいところお手をとらせてばかりという気もしますが気になったものですから
> 勝ちが五万局面あるような手順と五〇万局面あるような手順
たぶん、それは一言で言うと、急戦と持久戦との差なんだと思いますよ。
持久戦模様の局面を開始局面として与えて対局させたほうが、そのソフトの実力は発揮しやすいです(実力を観測するのには優れています)
…が、実戦がそういう進行になるとは限らないので結局、勝率を見るときは、そういう定跡の選別をすると実戦の勝率と離れる傾向にはあるかも知れませんね。
メルセンヌツイスタも「少し偏りが生じるからランダムではない」という突っ込みを、意図的に散らばる用にした方がランダムであるとするような方面から受けていたような。
偏るというか、連続で同じ値が返る部分があるものはランダムと言えるかどうかみたいな。
メルセンヌツイスタ以上の乱数となると現状なかなか難しいでしょうね。
同じ数字が出続けるというのは自分はアリだと思います。
サイなら振り直すわけですからその引き直したサイから同じ数字を消すなんてかなりナンセンスですよ。
一度出た数字が気にくわないならとある区間で同じ数字があったら引き直せばいい話だと思います。そのとある区間も議論になるでしょうし、なかなかナンセンスだと思います。
１試合した時の
全探索node数って
どのくらいなのでしょうか？
まだ計測してないのでよくわからないですけども、0.1秒なら、600knps×0.1秒×140手 = 8.4Mnodesぐらいのはず…。
今の強化学習勢は、終盤の入り口で読み違える欠点を補えて居ないように思われます。
終盤ほど手番が重要になり、駒得や連係より速度、危険度の相対評価、王手が掛かるかどうかが必要になります。
PONANZA に勝つには、中終盤の課題局面を学習し、中盤スタートの自己対戦で検証した中終盤特化の評価関数テーブルが別途必要になる気がするんですが。
> 中終盤特化の評価関数テーブルが別途必要になる気がするんですが。
Ponanzaもそんなことはしてないです。3駒関係は、序盤にしか出現しない形、終盤にしか出現しない形などが比較的綺麗に分離されているので、序盤と終盤とで評価関数をスイッチングするなどはしても(いまのところ)効果がないようです。