今回は思考時間制御部(time manager)です。現局面での次の1手に使うべき時間を計算します。
maximum search time = 今回の指し手で使える最大思考時間。fail high/fail lowした場合など、この最大時間までは使うものとします。(残りの手数に応じて時間をある程度残しておかないといけないので、この値は残り持ち時間のすべてではありません。)
optimum search time = 今回の指し手で使える平常時の目安時間。
unstable PV Extra Time = 反復深化のiterationを深くしていくときにPV(最善応手列)が変化したときは評価値が不安定な局面だということで与えられる追加の思考時間。
available search time = 今回は指し手ではだいたいこれくらい使えばいいかなという目安時間。反復深化のときに次回のiterationでこの時間を上回りそうなときは思考を切り上げます。
また、
available search time = optimum search time + unstable PV Extra Time
です。
今回のソースコードに限ったことではないですが、当時のStockfishのソースコード上のコメントには、私に英文の意味がよくわからないところが何箇所かあって、そういうところは翻訳コメント上に、”(?)”がつけてあります。
そういう箇所は、あとで英語に詳しい人に聞こうと思っていたのですが、そういう箇所はネイティブの人にも意味がわかりにくかったのか、最新のStockfishのソースコードではことごとく修正されいて、現在のソースコード上のコメントはわかりやすいものになっています。もし私の翻訳コメントでわかりにくい部分があれば、是非最新のStockfishのソースコードを確認してみてください。
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 |
/* Stockfish, a UCI chess playing engine derived from Glaurung 2.1 Copyright (C) 2004-2008 Tord Romstad (Glaurung author) Copyright (C) 2008-2013 Marco Costalba, Joona Kiiski, Tord Romstad Stockfish is free software: you can redistribute it and/or modify it under the terms of the GNU General Public License as published by the Free Software Foundation, either version 3 of the License, or (at your option) any later version. Stockfish is distributed in the hope that it will be useful, but WITHOUT ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License for more details. You should have received a copy of the GNU General Public License along with this program. If not, see */ #ifndef TIMEMAN_H_INCLUDED #define TIMEMAN_H_INCLUDED /// The TimeManager class computes the optimal time to think depending on the /// maximum available time, the move game number and other parameters. // TimeManagerクラスは、最大利用可能時間、開始局面からの手数とその他パラメーターに // 依存する思考のための最適な時間を計算する。 // ※ このクラスの使い方 : 思考開始時にinit()を呼び出し、反復深化のiterationごとに // pv_instability()を呼び出してavailable_time() , maximum_time()を見ながら適当なところで探索を打ち切る。 class TimeManager { public: // limits = UCIプロトコルで設定された持ち時間等の設定 // currentPly = 開始局面からの手数 // us = 現在の手番 void init(const Search::LimitsType& limits, int currentPly, Color us); // PV(最善応手列)がどの程度不安定なのかを設定する。 // これにより、追加の思考時間が設定される。 void pv_instability(double bestMoveChanges); // 利用可能時間。iteration終了時にこれの62%を超えていると今回の思考を終了。 int available_time() const { return optimumSearchTime + unstablePVExtraTime; } // 利用可能な最大の探索時間 int maximum_time() const { return maximumSearchTime; } // ※ 1手10秒固定などの場合、その10秒は使いきったほうがいいと思うのだが、そういう計算はしないようである。 // チェスは切れ負け設定が多いのだろうか？ private: // 最適な探索時間 int optimumSearchTime; // 利用可能な最大の探索時間 int maximumSearchTime; // 反復深化中のPVの変動が多いときに追加で用意される思考時間 int unstablePVExtraTime; }; #endif // #ifndef TIMEMAN_H_INCLUDED |
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 133 134 135 136 137 138 139 140 141 142 143 144 145 146 147 148 149 150 151 152 153 154 155 156 157 158 159 160 161 162 163 164 165 166 167 168 169 170 171 172 173 174 175 176 177 178 179 180 181 182 183 184 185 186 187 188 189 190 191 192 193 194 195 196 197 198 199 200 201 202 203 204 205 206 207 208 209 210 211 212 213 214 215 216 217 218 219 220 221 222 223 224 225 226 227 228 229 230 231 232 233 234 235 236 237 238 239 240 241 242 243 244 245 246 247 248 249 250 251 252 253 254 255 256 257 258 259 260 261 262 263 264 265 266 267 268 269 270 271 272 273 274 275 276 277 278 279 280 281 282 283 284 285 286 287 288 289 290 291 292 293 294 295 296 297 298 299 300 301 302 303 304 305 |
/* Stockfish, a UCI chess playing engine derived from Glaurung 2.1 Copyright (C) 2004-2008 Tord Romstad (Glaurung author) Copyright (C) 2008-2013 Marco Costalba, Joona Kiiski, Tord Romstad Stockfish is free software: you can redistribute it and/or modify it under the terms of the GNU General Public License as published by the Free Software Foundation, either version 3 of the License, or (at your option) any later version. Stockfish is distributed in the hope that it will be useful, but WITHOUT ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License for more details. You should have received a copy of the GNU General Public License along with this program. If not, see */ #include #include #include "search.h" #include "timeman.h" #include "ucioption.h" namespace { /// Constants // 定数 // 最大でこの手数だけ後ろに控えていると仮定して時間制御を計画する // ※ 最大で残り50手が指せる程度には時間を残しておくということ。 const int MoveHorizon = 50; // Plan time management at most this many moves ahead // トラブルがあったときに、我々はこの比率にもとづいて予備時間を踏み越える(使っていく)ことが出来る。 const double MaxRatio = 7.0; // When in trouble, we can step over reserved time with this ratio // いずれにせよ、我々はこの比率以上、残りの指し手から時間を盗むことはできない。 // ※ 残り時間がこの比率比率を下回らないようにする。 const double StealRatio = 0.33; // However we must not steal time from remaining moves over this ratio // MoveImportance[] is based on naive statistical analysis of "how many games are still undecided // after n half-moves". Game is considered "undecided" as long as neither side has >275cp advantage. // Data was extracted from CCRL game database with some simple filtering criteria. // MoveImportance[]は、「いくつの対局がn手のあとundecidedであったか」という // ナイーブな統計的解析に基づく。ゲームは両者いずれも275cp以下の優位性(スコア)であれば // "undecided"とみなす。データはいくつかの単純なフィルター判定条件でCCRLゲームデータベースから // 抽出されたものである。 // ※ 形勢に差が開いてからはあまり重要な局面ではなく、それまでに問題があるのだから、そこに // 思考時間を投与すべきという考え方。 // ※ 訳注 : ここのn half-movesはn手と訳して良い。full-movesは、先後両方が1手ずつ指したときに1手と数える数え方。 const int MoveImportance[512] = { 7780, 7780, 7780, 7780, 7780, 7780, 7780, 7780, 7780, 7780, 7780, 7780, 7780, 7780, 7780, 7780, 7780, 7780, 7780, 7780, 7778, 7778, 7776, 7776, 7776, 7773, 7770, 7768, 7766, 7763, 7757, 7751, 7743, 7735, 7724, 7713, 7696, 7689, 7670, 7656, 7627, 7605, 7571, 7549, 7522, 7493, 7462, 7425, 7385, 7350, 7308, 7272, 7230, 7180, 7139, 7094, 7055, 7010, 6959, 6902, 6841, 6778, 6705, 6651, 6569, 6508, 6435, 6378, 6323, 6253, 6152, 6085, 5995, 5931, 5859, 5794, 5717, 5646, 5544, 5462, 5364, 5282, 5172, 5078, 4988, 4901, 4831, 4764, 4688, 4609, 4536, 4443, 4365, 4293, 4225, 4155, 4085, 4005, 3927, 3844, 3765, 3693, 3634, 3560, 3479, 3404, 3331, 3268, 3207, 3146, 3077, 3011, 2947, 2894, 2828, 2776, 2727, 2676, 2626, 2589, 2538, 2490, 2442, 2394, 2345, 2302, 2243, 2192, 2156, 2115, 2078, 2043, 2004, 1967, 1922, 1893, 1845, 1809, 1772, 1736, 1702, 1674, 1640, 1605, 1566, 1536, 1509, 1479, 1452, 1423, 1388, 1362, 1332, 1304, 1289, 1266, 1250, 1228, 1206, 1180, 1160, 1134, 1118, 1100, 1080, 1068, 1051, 1034, 1012, 1001, 980, 960, 945, 934, 916, 900, 888, 878, 865, 852, 828, 807, 787, 770, 753, 744, 731, 722, 706, 700, 683, 676, 671, 664, 652, 641, 634, 627, 613, 604, 591, 582, 568, 560, 552, 540, 534, 529, 519, 509, 495, 484, 474, 467, 460, 450, 438, 427, 419, 410, 406, 399, 394, 387, 382, 377, 372, 366, 359, 353, 348, 343, 337, 333, 328, 321, 315, 309, 303, 298, 293, 287, 284, 281, 277, 273, 265, 261, 255, 251, 247, 241, 240, 235, 229, 218, 217, 213, 212, 208, 206, 197, 193, 191, 189, 185, 184, 180, 177, 172, 170, 170, 170, 166, 163, 159, 158, 156, 155, 151, 146, 141, 138, 136, 132, 130, 128, 125, 123, 122, 118, 118, 118, 117, 115, 114, 108, 107, 105, 105, 105, 102, 97, 97, 95, 94, 93, 91, 88, 86, 83, 80, 80, 79, 79, 79, 78, 76, 75, 72, 72, 71, 70, 68, 65, 63, 61, 61, 59, 59, 59, 58, 56, 55, 54, 54, 52, 49, 48, 48, 48, 48, 45, 45, 45, 44, 43, 41, 41, 41, 41, 40, 40, 38, 37, 36, 34, 34, 34, 33, 31, 29, 29, 29, 28, 28, 28, 28, 28, 28, 28, 27, 27, 27, 27, 27, 24, 24, 23, 23, 22, 21, 20, 20, 19, 19, 19, 19, 19, 18, 18, 18, 18, 17, 17, 17, 17, 17, 16, 16, 15, 15, 14, 14, 14, 12, 12, 11, 9, 9, 9, 9, 9, 9, 9, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 7, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 5, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 3, 3, 2, 2, 2, 2, 2, 1, 1, 1, 1, 1, 1, 1 }; // ply手目の重要性を返す。512手目以降はデータベースがないのでこれは511手目とみなす。 int move_importance(int ply) { return MoveImportance[std::min(ply, 511)]; } /// Function Prototypes // 以下のremaining()でTimeTypeとして用いる // OptimumTime(今回のための最適な思考時間) , MaxTime(今回のための最大思考時間) enum TimeType { OptimumTime, MaxTime }; template int remaining(int myTime, int movesToGo, int fullMoveNumber, int slowMover); } // PV(最善応手列)がどの程度不安定なのかを設定する。 // これにより、追加の思考時間が設定される。 void TimeManager::pv_instability(double bestMoveChanges) { // PVの変動した回数×標準思考時間 / 1.4 だけ追加で思考時間がもらえる。 // ToDo : この1.4というmagic number、√2っぽいが何か理論的根拠があるのだろうか。 // また、1.4で割るのを掛け算で書きなおすと0.714ぐらいだが…。 unstablePVExtraTime = int(bestMoveChanges * optimumSearchTime / 1.4); } // limits = UCIプロトコルで設定された持ち時間等の設定 // currentPly = 初期局面からの手数 // us = 現在の手番 void TimeManager::init(const Search::LimitsType& limits, int currentPly, Color us) { /* We support four different kind of time controls: increment == 0 && movesToGo == 0 means: x basetime [sudden death!] increment == 0 && movesToGo != 0 means: x moves in y minutes increment > 0 && movesToGo == 0 means: x basetime + z increment increment > 0 && movesToGo != 0 means: x moves in y minutes + z increment Time management is adjusted by following UCI parameters: emergencyMoveHorizon: Be prepared to always play at least this many moves emergencyBaseTime : Always attempt to keep at least this much time (in ms) at clock emergencyMoveTime : Plus attempt to keep at least this much time for each remaining emergency move minThinkingTime : No matter what, use at least this much thinking before doing the move */ /* 我々は4つのことなる時間制御をサポートする。 ※ incrementとは1手ごとの追加時間。 increment == 0 && movesToGo == 0 ならば: x 基準時間 [切れ負け!] increment == 0 && movesToGo != 0 ならば: x 手 を y 分で increment > 0 && movesToGo == 0 ならば: x 基準時間 + z 1手ごとに増加 increment > 0 && movesToGo != 0 ならば: x 手 を y 分で + z 1手ごとに増加 時間制御は、UCIのパラメーターによって調整される。 emergencyMoveHorizon: 少なくともこの手数をつねに(このあと)指すとして準備しておく。 emergencyBaseTime : つねにこの時間だけ残しておくように試みる。[ms]単位。 emergencyMoveTime : 残りの緊急の指し手のために、少なくともこの時間だけ、さらに追加で残しておくように試みる。 minThinkingTime : 指す前に少なくともこれだけの時間は使用する。 */ int hypMTG, hypMyTime, t1, t2; // Read uci parameters // uciパラメーターを読み込む // default = 40 int emergencyMoveHorizon = Options["Emergency Move Horizon"]; // default = 60 int emergencyBaseTime = Options["Emergency Base Time"]; // default = 30 int emergencyMoveTime = Options["Emergency Move Time"]; // 最小思考時間。これより少ない思考時間にはしない。 // 1手10秒のような設定の場合、これを設定すると良いのでは。 // default = 20 int minThinkingTime = Options["Minimum Thinking Time"]; // 序盤重視のパラメーターを100分率で。 // 100 = 通常、200 = 序盤重視、みたいな感じか。 // default = 70のようだが…。 int slowMover = Options["Slow Mover"]; // Initialize to maximum values but unstablePVExtraTime that is reset // 最大値で初期化するが、unstablePVExtraTimeはリセットする。 unstablePVExtraTime = 0; optimumSearchTime = maximumSearchTime = limits.time[us]; // We calculate optimum time usage for different hypothetic "moves to go"-values and choose the // minimum of calculated search time values. Usually the greatest hypMTG gives the minimum values. // 今回使用する最適時間を計算する。 // 我々は異なる仮説に基づく(?)"move to go"の値に対する最適な時間の使用について計算し、 // 計算された探索時間の値の最小値を選ぶ。通例、一番大きなhypMTGのときに // optimumSearchTime/maximumSearchTimeは最小値をとる。 // movestogoが指定されているときは、この手数だけ指さなければいけないので // その回数を指すことを基準として時間を計算する。 // ループ回数は、 // movestogoが指定されている(0以外の)場合、movestogoとMoveHorizonの小さいほう。 // MoveHorizonは、このあと指されると仮定している最大の手数なので、これより大きな値が // movestogoに指定されていてもそれは無視するようだ。 // また、movestogoが例えば5なら、どうあがこうが残り5手しかないので、それ以上時間を残すのは // 無駄以外なにものでもないのでこのような処理となっている。 // movestogoが0のときは、MoveHorizon分、最大で残り手数があるものとして考える。 for (hypMTG = 1; hypMTG <= (limits.movestogo ? std::min(limits.movestogo, MoveHorizon) : MoveHorizon); ++hypMTG) { // Calculate thinking time for hypothetic "moves to go"-value // 推測に基づく(?)"moves to go"の値に対する思考時間を計算する hypMyTime = limits.time[us] + limits.inc[us] * (hypMTG - 1) - emergencyBaseTime - emergencyMoveTime * std::min(hypMTG, emergencyMoveHorizon); /* N手先のhypMyTime = 残り時間 + 1手ごとの増加時間×N手 - emergencyBaseTime - emergencyMoveTime × min(N-1,emergencyMoveHorizon) inc[us]が0(将棋の場合)だと、結局、hypMyTimeは減っていくのみなので.. 結局、hypMyTimeが最大のときのものだけ考えればいい。 default値は emergencyMoveHorizon = 40 MoveHorizon = 50 なので、movestogo == 0 , inc[us] == 0だと hypMTG == 50でそのとき、ここがstd::min(hypMTG, emergencyMoveHorizon) == 40となる。 hypMyTime = limits.time[us] -60 -30×40 */ // 0未満なら0に。 hypMyTime = std::max(hypMyTime, 0); // 残り手数がhypMTGとしてremainingを計算しているようだが… t1 = minThinkingTime + remaining t2 = minThinkingTime + remaining // ※ ここでループごとにminを取りつづけるので、 // 結局、t1,t2の最小値がoptimumSearchTime,maximumSearchTimeになるということか。 optimumSearchTime = std::min(optimumSearchTime, t1); maximumSearchTime = std::min(maximumSearchTime, t2); } // Ponderが有効であるなら、1/4ぐらいはPonderがhitすると仮定できるから、探索時間を25%増しして考えておいていい。 if (Options["Ponder"]) optimumSearchTime += optimumSearchTime / 4; // Make sure that maxSearchTime is not over absoluteMaxSearchTime // maxSearchTimeが、absoluteMaxSearchTimeを絶対に超えないようにする。 // ※ ToDo : このコメントおかしくない？ // optimumSearchTimeがmaximumSearchTimeを超えないように、の間違いでは…。 optimumSearchTime = std::min(optimumSearchTime, maximumSearchTime); } namespace { // 残り時間を計算する関数 // T = OptimumTime(今回のための最適な思考時間) , MaxTime(今回のための最大思考時間) // のいずれか。 // myTime = 基準時間 // movesToGo = 残り手数制限があるときその手数 // currentPly = 初期局面からの手数 // slowMover = 序盤重視にするかのパラメーター template int remaining(int myTime, int movesToGo, int currentPly, int slowMover) { // TMaxRatioは何かトラブルがあったときに最大、この時間まで時間を追加するという許容範囲。 // OptimumTimeを計算するならは1倍。 // MaxTimeを計算するならばMaxRatio倍まで許容。 // TStealRatioは、いずれにせよこれ以上の比率まで残り時間を消費しないという限界比率。 // OptimumTimeのときは、0。(どんだけ使っても構わない？) // MaxTimeのときはStealRatioまで。 const double TMaxRatio = (T == OptimumTime ? 1 : MaxRatio); const double TStealRatio = (T == OptimumTime ? 0 : StealRatio); // この手数での重要性 × slowMover(序盤重視のパラメーターを100分率で) / 100 double thisMoveImportance = double(move_importance(currentPly) * slowMover) / 100; // 残り手数の重要性の和。 int otherMovesImportance = 0; // 残り手数分、加算していく。 for (int i = 1; i < movesToGo; ++i) otherMovesImportance += move_importance(currentPly + 2 * i); double ratio1 = (TMaxRatio * thisMoveImportance) / (TMaxRatio * thisMoveImportance + otherMovesImportance); double ratio2 = (thisMoveImportance + TStealRatio * otherMovesImportance) / (thisMoveImportance + otherMovesImportance); // 基本的には、 // 今回の指し手用の時間 ＝ 今回の指し手の重要度 ／ 残り手数分の重要度の和 × myTime(総残り時間) // で計算する。 // この計算式に、今回の指し手の重要度にTMaxRatioを掛けたものがratio1 // OptimalTimeの計算においてはStealRatio == 0なので、ratio1 == ratio2 // MaxTimeの計算においては、ratio2≒ StealRatioであり、以下でminをとっているので、 // いくらなんでも残り時間のこれ以上の比率を使うことが許されないの意味。 // StealRatio = 1/3ならば、残り時間の1/3以上はMaxTimeであれ使わないの意味。 // ※ この計算方式は15分切れ負け1手10秒とかのルールにはそぐわない感じもするが…。 return int(floor(myTime * std::min(ratio1, ratio2))); } } |