ＵＣＴはまだ効率をあげられるんじゃないのだろうか？

裸玉の詰め将棋を、証明数で解くのが非常に困難であることは知られているかと思いますが、UCTでこれを解決出来ないかなーなんていうことを結構前から考えてました。

ただ、効率のいい実装は、『詰み・不詰みが判明していないノードでは、読む優先順位として、証明数の代わりに詰む確率を用いる』だけで、中身は普通のMinMax探索に近いものになりそうな気がしています。

囲碁は、何と言うか、「少しの差を徐々に拡げて行って、大きな見落としがない限りはそのままの差でゴールできるゲーム」で、詰め将棋などはまさにその逆で、見落としが許されないゲーム、なのですよね。で、将棋は、詰め将棋に近い性格を持っている面がある気がします。（少々のリードを保っていても、最後にミスをすると負け）

で、こういうゲームをＵＣＴで解析するのは、無駄な部分が出るんじゃないかな、と。

こういうゲームでは、あるノードで正しい応手を指されたら負け、な局面は、それ以上シミュレートの対象にする必要のなくなったノード…勝率０が確定したノードになるのではないかと。今の私のＵＣＴの実装だと、以前にシミュレートした結果が残っている（例えば、その局面では、９９勝『1敗』、勝率０．９９だったかも知れない。）ので、いきなり勝率０にはならないんですよね。何回も、その『実は決定的な1敗』のノードをシミュレートしてみて、始めて勝率が０に近付いていく。多分、これって、無駄なんです。

ただし、『相手が正しい手を選べない可能性がある』ことを考慮すると、また話が変わってきます（苦笑）。勝負手として、『正しく指されたら負けることが分かっているけれど、その正しい応手を見つけられる可能性は低い』なんてことまで判断できると、対人ではまさに『理想的』です。

…相手がαβベースで全幅探索を行っているコンピュータだと、きっちり負けそうですけど（苦笑）。

そんなわけで、ＵＣＴの改良を少し思索中。…まだ試作に至る段階ではないです。

勝率の上位への繰上げをどう考えるか、なんですよねぇ。

今は、一回のシミュレーションの結果を最上位にまで一回の結果として伝えているだけ、なので、ここで大きな改造が出来そうな気がしています。

ただ、現実的には、『囲碁では』1回のシミュレーションの精度をあげるだけで、十分な成果があげられそうな気も『ものすごーく』しています。

え？

Lesserkaiがfloodgateにいますね…YSSとgps500に負けてますが。

Lesserkaiって名前からふつーに考えて、きっと『れさぴょん改』ですよね。

…私じゃないんですが（苦笑）、誰だろう？

あ、もう一つ、謎のプログラムであるところのcoredumpも今、参戦してる。

ちなみに、usa_testはしばしお休みを頂いております…(--;

今度は、千日手での停止とかTIME_UPで停止した場合の対応をちゃんとしてから再起動することにします。usa_testで使っているマシン、実は自宅に置いていないもので…OTL

misaki900に勝てなくなりました on floodgate

…というわけで、今後、usa_testはどんどんレーティングを落としていくものと思います。

…抜本的な対策を打たないとなぁ。

ＵＣＴなど

ねこにゃの開発は、少しだけ進展。

長らくバグっていた連の差分更新やらその他を諦めて、超シンプルなコードから書き直し。

この状態で、ほぼ完全にランダムに手を選択すると、

9路の初手からは、平均110手でシミュレート完了・1500Playout/sec位でした。

で、そのままＵＣＢ１・ＵＣＴを入れてみて、10秒思考で勝也と対局。

勝也は、ほとんどの局面で1手1秒もかけずにバシバシ打ってくるので、大分思考時間に差がありますが、どうやら『中国ルールなら』互角に戦えるっぽい感じです。

…そして、また『日本ルール』の壁にぶちあたってます。

単純に勝也がパスした局面でパスすると、ほぼ確実に負けてるんですよね（苦笑）。その後、ごちゃごちゃ打ってると、いつの間にか戦いが全盤面を巻き込んでいて、怪しげな手で『中国ルールなら』勝っているという感じ。

そう、日本ルールでは２～３目負けてるんです…ＯＴＬ

『日本ルール用終局判定』とか作成して、『日本ルールで』勝っていたら相手がパスしたらパスするとか、そういう工夫をするか、あらかじめ少しコミを大きめに設定しておくという手があるかと思うんですが…前者は結構実装が大変。そして後者については、試してみたら、『負けてる』と思い込んで、暴れまくって状況を悪くするケースが目立つ目立つ（苦笑）。

そして、この程度のシミュレーションの精度や速度では、１９路では使い物にならないこともほぼ明らか。

シミュレーションの精度をあげて行く工夫と、速度を上げるための何かを並行して考えていかないとダメですね。速度を上げるには、一つ比較的簡単な方法があって、モンテカルロシミュレーション部分を並列化するというのがあるのですが、手持ちのマシンでは所詮2倍とか4倍程度しか早くならないですし。精度を上げていく方は、読まなくてもいいような変な手も読んでいるので、これをどうにかしていく（パターンを使うことになるでしょうね）方向が一つと、ＵＣＴの各ノードで、とりあえず全候補手を（ランダムな順で）読んでみる代わりに、一部の候補手（たとえばアタリの石を逃げる手や石を取る手）の優先度をあげていくとか、最初は一部の候補手しか読まない（適当な回数シミュレートしてみて、どうも思わしい手がないと思ったら別の候補手も読む）とか、そういう工夫が必要そうです。

また、ＵＣＴに関しても、単純に上のノードに1回のシミュレーションの結果を繰り上げるのではなくて、もっとＭｉｎＭａｘ的なことをやってもいいような気がしています。

たとえば、あるノードで、次にある手を打たれたら「勝ちはない」のなら、そのノードの勝率は完全に０にしてしまうとか。…全然理論的な裏づけはないんですが（苦笑）。

うーん…先の、最初は一部の候補手しか読まないとか、キラー手的な手を先に読むだけで、同じような効果が得られるか…。

いまいち、どういう風にチューニングしていけばいいのか、という感覚が掴めない感じですね。未だにアルゴリズム的に何となく納得できていないっていうのが一番大きな理由かも知れません。うまく行くことは分かるんだけれど、っていう意味では、αβでも同じような感覚が未だにありますね、そういえば。

…長い長い呟きでした。しかも、誰の役にも立ちそうにないし（苦笑）。

季節外れ？に風邪など

…風邪引きで結構酷い目に合いました、というか、現在進行形でまだ風邪が治っていないというか。

まだ時々「ごほんごほん」といやぁな感じの咳をしてます。

そんな中、年度末進行…ＯＴＬ

思考時間を変えてみただけ…のはずだったのだけど on floodgate

何か異常に投げっぷりが良くなっている様な気がする、って、バグっぽいですね（ーー；

misaki900が来てます on floodgate

小宮日記より。

http://d.hatena.ne.jp/mkomiya/20080311/1205162418

＊現在のmisaki900なかなかいいですね

…misaki900に、MyMove900さんが追い越されました。

usa_testにもヒタヒタと迫っています…。

現在のレーティングは下記に。

http://wdoor.c.u-tokyo.ac.jp/shogi/logs/LATEST/players-floodgate.html

朝、起きたら既に追い越されているかも知れないですね(--;

四間飛車試験とりあえず終わり on floodgate

floodgateで四間飛車を指してみるテスト、とりあえず終わりです。

定跡不足でうまく駒組み出来なかったせいもありますが、『思ってたより変わらない』という結論のような気がしています（苦笑）。

ＵＣＴを組み込んでみる

『ねこにゃ』にＵＣＴを組み込んでみました。

ちょっとバグがありましたが、今回はすんなりと動きました。

が。現在は、動作に大問題あり。

シミュレーションの回数を多くすれば問題にならなそうですが、まだ探索していない手を優先的に探索するようにしているので、二手目以降、見込みのない手を無駄に多く探索してしまうんですよね。結構大真面目に対策を考えないと。

…Progressive wideningとか取り入れないとダメですかね…。

floodgateで四間を試験中

usa_testの序盤を、ここしばらく、居飛車固定（というよりは、相掛りになりやすいように誘導）にしてたんですが、今度は『出来るだけ』四間飛車を指すように固定してみました。

今までの経験上、勝率が明らかに落ちるはず、なんですが、場合に寄っては『苦手な相手に勝てる』かなぁとか。

それにしても、今日はgps500にぽこぽこ負けてますね（苦笑）。

昨日の『ねこにゃ』の勝ちはまぐれだったようです

ちょっとだけ、『梅沢由香里のやさしい囲碁』でトレーニング。

詰め碁を少し復習。（終盤でコウ絡みの詰め碁を間違えてひどい目にあったので。）

で。

あんまり争いにならないようにやったら、さっくり勝ってしまいました。

どう見てもダメな手を、何手かに一回打つんですよね。原因は割りとはっきりしていて、まだUCTを組み込んでいないのと、シミュレーションの精度が悪いせいで、こちら側の明らかな応手を見落としているせい。（より正確には、こちら側の明らかな応手を打つ確率が低く見積もられているせい、ですね。）

…さっさとUCTにしましょう。

あ。

UCB1を組み込むのは、昨晩やってみました。

最初はconstant exploration parameterを適当に設定してやってみたのですが、この値は真面目にチューニングしないと、かなりまずそうです。（探索の『偏り』が思ったようにいってない感じです。勝率が低くて切り捨てた手ももっとシミュレートして欲しい。）

…ちゃんとUCB1-TUNEDにするのがベストかな。

久し振りに進展

『ねこにゃ』の開発、久し振りに進展しました。

結局、速度向上のために差分で連を持っていたりするところを一旦全部捨ててみて、9路で初手からなら1500Playout/secでした。合法手の生成のところで重い処理をしているのをその気になれば省けるはずなので、3000Playout/sec位は（データ構造が盤面のみでも）出せそうですね。

で、モンテカルロシミュレーションを組み込むのは当たり前として、ＵＣＴやＵＣＢに行く前に、『シミュレーションの誤差』の方から考えてみることにしました。

シミュレーション自体がまだパターンも何も組み込んでいないのでシミュレーションの結果自体があんまり信用できないという問題はあるんですが（苦笑）。

n回のシミュレーションによる実際の値との誤差は、1/sqrt(n)に比例する（はず）と言うのを前提にプログラミング。

で、9路で10秒間＝初手なら15000Playoutでデータ測定。

とりあえず、『実際の値』と『本当の勝率』の間の誤差がどれ位あるのか、定数項の設定をまだ最適化していない（これは、同一の手を１０回・１００回・１０００回・１００００回とかシミュレートすることで定数項を推測は出来るはずですね。２＾ｎ乗でやるのがコンピュータ屋さん的な感じですかね？）状態ですが、現在、

初手
可能手８１手
総シミュレーション回数　15672回
一番シミュレートを多く行った手のシミュレート回数　198回
一番シミュレートの少ない手のシミュレート回数　80回

一番勝率の高かった手：（５，６）　勝率：0.555556

てな感じです。まだ何かでかいバグがありそうな気もするんですが、とりあえず…

・パターンを使って一回あたりのシミュレーションの精度を上げる
・まずは、ＵＣＢ１にしてみる＆ＵＣＴを組み込む

という、割と重めのテーマが残っています。

とはいえ、パターンの方は、元データのあてもできましたし、今のシミュレーション回数の割り当て方法をＵＣＢ１にするのもＵＣＢ－ＴＵＮＥＤにするのも比較的簡単です。また、ＵＣＴにするのも、まぁ大体作業的には見えています。（データ構造としては、この辺を意識した構造を構築済みなので。）

というわけで、久し振りに大分視界がクリアになった、これから一気に強くできるな、と思ったところで。

…現行の、いわば『しょぼい』バージョンに私が負けました（涙)。

…いくらなんでも、囲碁弱すぎだ、私。