search

Nyanyan / Egaroucid

Super Strong and Fast Othello AI / Computer Othello Reversi
https://www.egaroucid.nyanyan.dev/
GNU General Public License v3.0
109 stars 13 forks source link

Time Management System #351

Open Nyanyan opened 6 days ago

Nyanyan commented 6 days ago

Egaroucid for Consoleに、持ち時間を与えていい感じに対戦してくれる機能をつけたい。

Nyanyan commented 5 days ago

とりあえず簡易的な時間制限システムを作った。動くかは知らん。 todo:

Nyanyan commented 5 days ago

とりあえずコンパイルは通ったけどなんかおかしい

Nyanyan commented 5 days ago

いい感じに持ち時間を管理しながら思考できるようになった。

Nyanyan commented 5 days ago

ponderは #354 で実装する

Nyanyan commented 5 days ago

両方の手番の合計思考時間を考えてしまっていたので、思考時間は手番ごとに持つようにすべし

Nyanyan commented 4 days ago

残り時間に応じて読み切りタイミングを仮で設定すると良さそう

Nyanyan commented 3 days ago

完全読み/X%読み切りの時間を統計的に計測して、その値をもとに残り時間を見てどこで完全読み/読み切りするかを決めると良さそう。

Nyanyan commented 2 days ago

NPSと残り時間の兼ね合いで読み切りタイミングを決定すると良さそう。

Nyanyan commented 2 days ago

読み切り/完全読みを残りXマス空き、Nを訪問ノード数とすると T=N(X) / NPS であり、a、bを定数として N(X)=aexp(bX) なので、 T=a exp(bX) / NPS X= ln(T * NPS / a) / b

Nyanyan commented 2 days ago

Tはその手における計算時間、T_rは対局の残り時間とする。 完全読みするときはT=T_rくらいでOK MPCつき読み切りをするときにはT=T_r*0.25くらい？(探索確率ごとに適当に値を決めると良さそう)

Nyanyan commented 2 days ago

仮にa=1、b=2としてみる(あとで厳密に調査する)

Nyanyan commented 2 days ago

中盤読みでは、MCTSではノードの訪問回数の分布が変わらなくなるまで探索するなどしているらしい(結果が安定するまで探索する)ので、中盤読みでそういったアイデアを利用できそうな気がする

Nyanyan commented 2 days ago

中盤読みは深さやMPC確率を変えた探索をしてみたりしてブレを見るのもいいかも？もしくは雑に対戦させてしまうなど？

Nyanyan commented 1 day ago

とりあえず8分持ち(37秒/35秒残し)自己対戦でこれが打てたので、わりと良さそう 36手読み切り、30手完全読みした image XOT (f5d6c4d3c2b3b4b5) f5d6c4d3c2b3b4b5c7f4e3f3c3e2d2c5c6e6f1f6f2c1e7f7d1e8a6b2g5d7a5e1g6g4f8g3a1b1a2b8c8d8a8h5h6h7h4h3g7a3a4b6a7b7g2h2h1h8g1g8

Nyanyan commented 1 day ago

他のXOT棋譜 image

f5f6d3c5d6c7b5e3f4f3e2c6e6f7e7c4c3f8d7b6e8a5b4d8c8a3g8f2g3h4g4g6h3e1f1d2h6g7h5g5b3c2a4a6b1b2c1d1a1a2h8h7b7h2a7g2h1g1a8b8

|          Level|          Depth|           Move|          Score|           Time|          Nodes|            NPS| Remaining Time|
|              1|         1@100%|             b8|             +2|  000:00:00.000|              1|           1000|   45.13/186.71|
Nyanyan commented 1 day ago

15分持ち 38手読み切り/33手完全読み f5d6c4d3c2b3b4b5c7f4c5c6b6e6d7f6c3e2e3d1a5f7e7a4f1a6g3g4c1e1f2d2a3a2b2a1b1f8f3h3g5h4e8g6g8c8d8h8b8a8g7g2h2h6a7b7h5h1g1h7 image

Nyanyan commented 1 day ago

EdaxとEgaroucidで持ち時間480秒ponderなしで対戦させてみた。あまりにも同じすぎる

Edax: Black
Egaroucid White +2
f5d6c5b4d7f6b5g5c4d3d2c3c2c6e6a5b6e2f4e3a3a4a6b3f1f7e7e8g3g4f3c8h4f2h5c7e1c1a2d1b1h3g6h6g2g7d8b7a8b8h8h1g8h2a7f8h7g1b2a1

Edax: White +2
Egaroucid Black
f5d6c5b4d7f6b5g5c4d3d2c3c2c6e6a5b6e2f4e3a3a4a6b3f1f7e7e8f3f2a2d8g3h3g4c7h6b7g2d1a7e1a8c1b2a1b1g1g6h5h4h1h2h7b8c8g7h8f8g8
Nyanyan commented 1 day ago

初手から

Edax: Black
Egaroucid White +2
d3c5e6f5f6e3d6f7g6e7c6g5c4d7f4f3e2c7c8b6d8b5b4a3e8h6a5c2d2c3g4a4a6a7g3c1d1f8g8b7b1f2e1h4h5h3a8b8g7g1a2b2b3a1f1g2h2h1h8h7

Edax: White
Egaroucid Black +0
c4e3f6e6f5c5f4g6f7g5d6d3f3c3h4h5g4h3e2f2d2d1g3c1b6c2b4e7f8b3c6a4h7d7c7a6a5b5b7h2g2f1a7h6h1g1a3a8e1b2a2d8g7a1b1h8g8e8c8b8
Nyanyan commented 2 hours ago

完全読み深さと訪問ノード数の関係を雑に調べてみた(5-24手は100件、25手、26手は50件、27手は11件のデータ) image

Nyanyan commented 2 hours ago

15マス空き以降に限るとこうなった image

Nyanyan commented 2 hours ago

やっぱり訪問ノード数って2桁くらいの範囲でばらつくなぁ… つまり、ノード数=a exp(bx)としたときaが100倍くらい変わるということで… まあ、aは最小値を取るくらいでいいか。

Nyanyan commented 35 minutes ago

93%読みだとこんな感じ。 image