Stockfish完全解析もいよいよ今回で最終回。今回は探索部です。探索部は指し手生成や指し手オーダリング部(move picker)などの上に成り立つので、ボトムアップ式に解説してきた結果、一番大切なところが一番最後になりました。
Bonanzaソース完全解析ブログのほうでも、探索部の解説はそんな理由で結局後回しになり、ろくに解説できてなかったのをいま思い出しました。
今回は、探索部に関して私の解説コメントつきのソースコードを掲載できたので、解説の役割は十分果たしたと思います。
予備校の授業や、大学のゼミなんかでも回を重ねるごとに出席者が減っていくと思いますが、この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 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 |
/* 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 SEARCH_H_INCLUDED #define SEARCH_H_INCLUDED #include #include #include #include #include "misc.h" #include "position.h" #include "types.h" struct SplitPoint; namespace Search { /// The Stack struct keeps track of the information we need to remember from /// nodes shallower and deeper in the tree during the search. Each search thread /// has its own array of Stack objects, indexed by the current ply. // このStack構造体は、探索中の探索木において浅いところ・深いところのnodeを覚えておく // ために必要とする情報を追跡するのに使う。 // それぞれの探索スレッドは、その自身のStackオブジェクトの配列を保持しており、 // 現在のply(探索深さ)がその配列の添え字として使われる。 struct Stack { // この局面でsplit(探索の並列化)を行ったときに使う、このnodeの情報を表すSplitPointへのポインター SplitPoint* splitPoint; // 現在の探索深さ int ply; // この局面での指し手 // 現在探索中の指し手を表示させたり、 // 指し手を進めた局面から、1手前の局面での指し手を調べたりするときに使う Move currentMove; // この指し手を除外して探索する。これは「部分探索(partial search)」と書いてある。 // 除外する指し手がない場合は、MOVE_NONE。これは「全探索(full search)」と書いてある。 Move excludedMove; // 各探索深さにおけるKiller Moveは2個 Move killers[2]; // このnodeで残り探索深さを減らした量(LMRで) // また、Null moveなどで親nodeでreductionをしたかどうかなどチェックしている Depth reduction; // 現局面の静的評価のスコア Value staticEval; // 探索においてNull moveをスキップするモード // このnodeだけの問題。Null moveを二手連続で行うとおかしくなるので、Null moveするときに // 局面を進めた次のnodeでのNull moveを禁止するために使うフラグ。 // 次の局面でまたfalseが代入されるのでnull move→普通の指し手→null moveのような手順は可能。 // ToDo : ここは何故intなのか?true/falseしか代入していないのでboolで良さそうなのだが…。 int skipNullMove; }; /// RootMove struct is used for moves at the root of the tree. For each root /// move we store a score, a node count, and a PV (really a refutation in the /// case of moves which fail low). Score is normally set at -VALUE_INFINITE for /// all non-pv moves. // RootMove構造体は、探索木の開始局面における指し手を表現するために使われる。 // それぞれのroot moveはスコア、nodeのカウント、PV(最善応手列)(fail lowした場合にも // おける本当の反駁手)を格納している。スコアは、non-pvの指し手においては通常 // -VALUE_INFINITEがセットされている。(non-pvではalpha値を超えるかどうかしか調べないため、 // alpha値を更新しなければ、初期値である-VALUE_INFINITEのままであるということか?) struct RootMove { // Root nodeでの指し手を引数に渡す // これはpv[0]に格納される。 RootMove(Move m) : score(-VALUE_INFINITE), prevScore(-VALUE_INFINITE) { // 渡された指し手はpv[0]に格納される。 // pv配列は末尾の要素がMOVE_NONEでなければならないのでそれも格納してある。 pv.push_back(m); pv.push_back(MOVE_NONE); } // RootMoveを並べ替えるときにスコアで昇順ソートするためにoperator<を定義しておく。 bool operator<(const RootMove& m) const { return score > m.score; } // Ascending sort // Moveと比較するためのoperatorも定義しておく。 bool operator==(const Move& m) const { return pv[0] == m; } // RootMove::extract_pv_from_tt()は、置換表から指し手を加えることによってPV(最善応手列)を構築する。 // BOUND_EXACTなnodeだけではなくfail highしたnodeも考慮するので、 // Root nodeでfail highしているときでさえ、いつでもponderすることを許す // 表示するための長いPV、それは局面解析のために重要である。 // ToDo : すまない。ここの英語いまひとつわからない。 void extract_pv_from_tt(Position& pos); // RootMove::insert_pv_in_tt()は、探索iterationの最後に呼び出され、 // PVを置換表に書き戻す。これは、たとえ、置換表の古いエントリーが上書きされていようとも、 // 古いPVの指し手が最初に探索されることを確実にする。 void insert_pv_in_tt(Position& pos); // root nodeでこの指し手を選択したときのスコア // ※ PVの指し手でない場合は、-VALUE_INFINITEがセットされている。 Value score; // 1つ前のiteration深さでのこの指し手のスコア // ※ PVの指し手でない場合は、-VALUE_INFINITEがセットされている。 // ※ 今回のaspiration searchの探索窓の幅を決定するときに使う。 // また、multi PVを出力するときにまだ今回のiterationでスコア更新が行われていないときに // 前回スコアを出力しなければならないのでそのときにも用いる。 Value prevScore; // 最善応手列。 // 終端要素はMOVE_NONEであることが保証されている。extract_pv_from_tt()でそういう処理をしているため。 // RootMoveのコンストラクタで渡された指し手はpv[0]に格納されているので、これは絶対に破壊してはならない。 // ※ 探索開始局面での指し手の数だけこのクラスのインスタンスが生成されているので、 // 探索開始局面からそれぞれの指し手に対する最善応手列を持っていることになる。 // 例えば、こちらの最善手に対する相手の応手(ponder用の指し手)は、RootMoves[0].pv[1]となる。 std::vector }; /// The LimitsType struct stores information sent by GUI about available time /// to search the current move, maximum depth/time, if we are in analysis mode /// or if we have to ponder while is our opponent's side to move. // LimitsTypeは、GUIから送られてきた情報(今回の指し手のための探索の利用可能時間、最大探索深さ、時間や // 検討モードであるとか、相手の指し手中にponderするであるだとかを格納する。 struct LimitsType { // コンストラクタではこの構造体をゼロクリア LimitsType() { std::memset(this, 0, sizeof(LimitsType)); } // 時間制御を行うのか。 // 詰み専用探索、思考時間0、探索深さが指定されている、探索ノードが指定されている、思考時間無制限 // であるときは、時間制御に意味がないのでやらない。 bool use_time_management() const { return !(mate | movetime | depth | nodes | infinite); } // time 残り時間(この1局について) [ms] // inc 1手ごとの増加時間。[ms] // 秒読みに似た概念だが、持ち時間が切れていなくともこれが加算されるところが異なる。 // movestogo = 次の時間制御までx手あるという意味らしい。 // これが指定されておらず、"wtime"と"btime"を受信したのならば切れ負けの意味。 // これが指定されているときは、手数制限的な意味だと思われる。(100手で引き分け、など) // depth = 探索深さ固定(0以外を指定してあるなら) // nodes = 探索ノード数固定(0以外を指定してあるなら) // movetime = 思考時間固定(0以外が指定してあるなら) // mate = 詰み専用探索(UCIの'go mate'コマンドを使ったとき) // 詰み探索モードのときは、ここに詰み手数が指定されている。(1以上の値) // その手数以内の詰みを発見すると探索を終了する。 // infinite = 思考時間無制限 // ponder = ponder中であるかのフラグ // これがtrueのときはbestmoveがあっても探索を停止せずに"ponderhit"か"stop"が送られてきてから停止する。 // ただし今回用の探索時間を超えていれば、stopOnPonderhitフラグをtrueにしてあるのでponderhitに対して即座に停止する。 int time[COLOR_NB], inc[COLOR_NB], movestogo, depth, nodes, movetime, mate, infinite, ponder; }; /// The SignalsType struct stores volatile flags updated during the search /// typically in an async fashion, for instance to stop the search by the GUI. // SignalsType構造体は、例えばGUIによる探索の停止というような、典型的には非同期なやり方で // 探索中に更新されるvolatileなフラグを格納する。 struct SignalsType { // stopOnPonderhit : ponder中であるが、しかし、今回のための探索時間は使いきっているか、 // あるいは探索は終了しているので(詰みを見つけたなど) // GUIから'ponderhit'がくれば即座に思考を停止して指し手を返すべきであるという状態。 // GUIから'stop'がくればもちろん停止する。 // firstRootMove : root nodeの最初の指し手について調べるのを開始するとtrueになる。 // stop : 停止信号であり、これがtrueになっていれば探索を停止させる。 // failedLowAtRoot : root nodeでfail low中の探索である(このときの中断は探索が不安定なのでやらないほうが良い) bool stopOnPonderhit, firstRootMove, stop, failedLowAtRoot; }; typedef std::unique_ptr // --- 探索関係のglobalっぽい何か。 // 探索の強制停止信号などのフラグの集合体。 // Signals.stopをtrueにしたあと返ってきた評価値は信用ならないので用いてはならない。 extern volatile SignalsType Signals; // UCIプロトコルで受け取った思考時間等の設定項目 extern LimitsType Limits; // 探索開始局面での指し手 extern std::vector // 探索開始局面 extern Position RootPos; // 探索開始局面での手番 extern Color RootColor; // 探索を開始した時刻。misc::time()にて探索開始時に取得。 // 探索が終了したときにこの値と引き算をして探索に要した時間を算出するのに使う。 extern Time::point SearchTime; // セットアップされた局面(UCIのpositionコマンドで渡された開始局面から探索を開始する直前の局面)までの // 局面のキーの追跡をする。 千日手の検出に必要とされる。 // ※ 実体はStateInfoのstackである。 extern StateStackPtr SetupStates; // 探索の初期化 extern void init(); // 指し手生成(合法手の生成)の検証のためのユーティリティ。 // すべてのリーフノードを与えられた探索深さdepthまで調べ、生成される指し手の数の合計を返す。 extern size_t perft(Position& pos, Depth depth); // 思考開始 extern void think(); } // namespace Search #endif // #ifndef SEARCH_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 306 307 308 309 310 311 312 313 314 315 316 317 318 319 320 321 322 323 324 325 326 327 328 329 330 331 332 333 334 335 336 337 338 339 340 341 342 343 344 345 346 347 348 349 350 351 352 353 354 355 356 357 358 359 360 361 362 363 364 365 366 367 368 369 370 371 372 373 374 375 376 377 378 379 380 381 382 383 384 385 386 387 388 389 390 391 392 393 394 395 396 397 398 399 400 401 402 403 404 405 406 407 408 409 410 411 412 413 414 415 416 417 418 419 420 421 422 423 424 425 426 427 428 429 430 431 432 433 434 435 436 437 438 439 440 441 442 443 444 445 446 447 448 449 450 451 452 453 454 455 456 457 458 459 460 461 462 463 464 465 466 467 468 469 470 471 472 473 474 475 476 477 478 479 480 481 482 483 484 485 486 487 488 489 490 491 492 493 494 495 496 497 498 499 500 501 502 503 504 505 506 507 508 509 510 511 512 513 514 515 516 517 518 519 520 521 522 523 524 525 526 527 528 529 530 531 532 533 534 535 536 537 538 539 540 541 542 543 544 545 546 547 548 549 550 551 552 553 554 555 556 557 558 559 560 561 562 563 564 565 566 567 568 569 570 571 572 573 574 575 576 577 578 579 580 581 582 583 584 585 586 587 588 589 590 591 592 593 594 595 596 597 598 599 600 601 602 603 604 605 606 607 608 609 610 611 612 613 614 615 616 617 618 619 620 621 622 623 624 625 626 627 628 629 630 631 632 633 634 635 636 637 638 639 640 641 642 643 644 645 646 647 648 649 650 651 652 653 654 655 656 657 658 659 660 661 662 663 664 665 666 667 668 669 670 671 672 673 674 675 676 677 678 679 680 681 682 683 684 685 686 687 688 689 690 691 692 693 694 695 696 697 698 699 700 701 702 703 704 705 706 707 708 709 710 711 712 713 714 715 716 717 718 719 720 721 722 723 724 725 726 727 728 729 730 731 732 733 734 735 736 737 738 739 740 741 742 743 744 745 746 747 748 749 750 751 752 753 754 755 756 757 758 759 760 761 762 763 764 765 766 767 768 769 770 771 772 773 774 775 776 777 778 779 780 781 782 783 784 785 786 787 788 789 790 791 792 793 794 795 796 797 798 799 800 801 802 803 804 805 806 807 808 809 810 811 812 813 814 815 816 817 818 819 820 821 822 823 824 825 826 827 828 829 830 831 832 833 834 835 836 837 838 839 840 841 842 843 844 845 846 847 848 849 850 851 852 853 854 855 856 857 858 859 860 861 862 863 864 865 866 867 868 869 870 871 872 873 874 875 876 877 878 879 880 881 882 883 884 885 886 887 888 889 890 891 892 893 894 895 896 897 898 899 900 901 902 903 904 905 906 907 908 909 910 911 912 913 914 915 916 917 918 919 920 921 922 923 924 925 926 927 928 929 930 931 932 933 934 935 936 937 938 939 940 941 942 943 944 945 946 947 948 949 950 951 952 953 954 955 956 957 958 959 960 961 962 963 964 965 966 967 968 969 970 971 972 973 974 975 976 977 978 979 980 981 982 983 984 985 986 987 988 989 990 991 992 993 994 995 996 997 998 999 1000 1001 1002 1003 1004 1005 1006 1007 1008 1009 1010 1011 1012 1013 1014 1015 1016 1017 1018 1019 1020 1021 1022 1023 1024 1025 1026 1027 1028 1029 1030 1031 1032 1033 1034 1035 1036 1037 1038 1039 1040 1041 1042 1043 1044 1045 1046 1047 1048 1049 1050 1051 1052 1053 1054 1055 1056 1057 1058 1059 1060 1061 1062 1063 1064 1065 1066 1067 1068 1069 1070 1071 1072 1073 1074 1075 1076 1077 1078 1079 1080 1081 1082 1083 1084 1085 1086 1087 1088 1089 1090 1091 1092 1093 1094 1095 1096 1097 1098 1099 1100 1101 1102 1103 1104 1105 1106 1107 1108 1109 1110 1111 1112 1113 1114 1115 1116 1117 1118 1119 1120 1121 1122 1123 1124 1125 1126 1127 1128 1129 1130 1131 1132 1133 1134 1135 1136 1137 1138 1139 1140 1141 1142 1143 1144 1145 1146 1147 1148 1149 1150 1151 1152 1153 1154 1155 1156 1157 1158 1159 1160 1161 1162 1163 1164 1165 1166 1167 1168 1169 1170 1171 1172 1173 1174 1175 1176 1177 1178 1179 1180 1181 1182 1183 1184 1185 1186 1187 1188 1189 1190 1191 1192 1193 1194 1195 1196 1197 1198 1199 1200 1201 1202 1203 1204 1205 1206 1207 1208 1209 1210 1211 1212 1213 1214 1215 1216 1217 1218 1219 1220 1221 1222 1223 1224 1225 1226 1227 1228 1229 1230 1231 1232 1233 1234 1235 1236 1237 1238 1239 1240 1241 1242 1243 1244 1245 1246 1247 1248 1249 1250 1251 1252 1253 1254 1255 1256 1257 1258 1259 1260 1261 1262 1263 1264 1265 1266 1267 1268 1269 1270 1271 1272 1273 1274 1275 1276 1277 1278 1279 1280 1281 1282 1283 1284 1285 1286 1287 1288 1289 1290 1291 1292 1293 1294 1295 1296 1297 1298 1299 1300 1301 1302 1303 1304 1305 1306 1307 1308 1309 1310 1311 1312 1313 1314 1315 1316 1317 1318 1319 1320 1321 1322 1323 1324 1325 1326 1327 1328 1329 1330 1331 1332 1333 1334 1335 1336 1337 1338 1339 1340 1341 1342 1343 1344 1345 1346 1347 1348 1349 1350 1351 1352 1353 1354 1355 1356 1357 1358 1359 1360 1361 1362 1363 1364 1365 1366 1367 1368 1369 1370 1371 1372 1373 1374 1375 1376 1377 1378 1379 1380 1381 1382 1383 1384 1385 1386 1387 1388 1389 1390 1391 1392 1393 1394 1395 1396 1397 1398 1399 1400 1401 1402 1403 1404 1405 1406 1407 1408 1409 1410 1411 1412 1413 1414 1415 1416 1417 1418 1419 1420 1421 1422 1423 1424 1425 1426 1427 1428 1429 1430 1431 1432 1433 1434 1435 1436 1437 1438 1439 1440 1441 1442 1443 1444 1445 1446 1447 1448 1449 1450 1451 1452 1453 1454 1455 1456 1457 1458 1459 1460 1461 1462 1463 1464 1465 1466 1467 1468 1469 1470 1471 1472 1473 1474 1475 1476 1477 1478 1479 1480 1481 1482 1483 1484 1485 1486 1487 1488 1489 1490 1491 1492 1493 1494 1495 1496 1497 1498 1499 1500 1501 1502 1503 1504 1505 1506 1507 1508 1509 1510 1511 1512 1513 1514 1515 1516 1517 1518 1519 1520 1521 1522 1523 1524 1525 1526 1527 1528 1529 1530 1531 1532 1533 1534 1535 1536 1537 1538 1539 1540 1541 1542 1543 1544 1545 1546 1547 1548 1549 1550 1551 1552 1553 1554 1555 1556 1557 1558 1559 1560 1561 1562 1563 1564 1565 1566 1567 1568 1569 1570 1571 1572 1573 1574 1575 1576 1577 1578 1579 1580 1581 1582 1583 1584 1585 1586 1587 1588 1589 1590 1591 1592 1593 1594 1595 1596 1597 1598 1599 1600 1601 1602 1603 1604 1605 1606 1607 1608 1609 1610 1611 1612 1613 1614 1615 1616 1617 1618 1619 1620 1621 1622 1623 1624 1625 1626 1627 1628 1629 1630 1631 1632 1633 1634 1635 1636 1637 1638 1639 1640 1641 1642 1643 1644 1645 1646 1647 1648 1649 1650 1651 1652 1653 1654 1655 1656 1657 1658 1659 1660 1661 1662 1663 1664 1665 1666 1667 1668 1669 1670 1671 1672 1673 1674 1675 1676 1677 1678 1679 1680 1681 1682 1683 1684 1685 1686 1687 1688 1689 1690 1691 1692 1693 1694 1695 1696 1697 1698 1699 1700 1701 1702 1703 1704 1705 1706 1707 1708 1709 1710 1711 1712 1713 1714 1715 1716 1717 1718 1719 1720 1721 1722 1723 1724 1725 1726 1727 1728 1729 1730 1731 1732 1733 1734 1735 1736 1737 1738 1739 1740 1741 1742 1743 1744 1745 1746 1747 1748 1749 1750 1751 1752 1753 1754 1755 1756 1757 1758 1759 1760 1761 1762 1763 1764 1765 1766 1767 1768 1769 1770 1771 1772 1773 1774 1775 1776 1777 1778 1779 1780 1781 1782 1783 1784 1785 1786 1787 1788 1789 1790 1791 1792 1793 1794 1795 1796 1797 1798 1799 1800 1801 1802 1803 1804 1805 1806 1807 1808 1809 1810 1811 1812 1813 1814 1815 1816 1817 1818 1819 1820 1821 1822 1823 1824 1825 1826 1827 1828 1829 1830 1831 1832 1833 1834 1835 1836 1837 1838 1839 1840 1841 1842 1843 1844 1845 1846 1847 1848 1849 1850 1851 1852 1853 1854 1855 1856 1857 1858 1859 1860 1861 1862 1863 1864 1865 1866 1867 1868 1869 1870 1871 1872 1873 1874 1875 1876 1877 1878 1879 1880 1881 1882 1883 1884 1885 1886 1887 1888 1889 1890 1891 1892 1893 1894 1895 1896 1897 1898 1899 1900 1901 1902 1903 1904 1905 1906 1907 1908 1909 1910 1911 1912 1913 1914 1915 1916 1917 1918 1919 1920 1921 1922 1923 1924 1925 1926 1927 1928 1929 1930 1931 1932 1933 1934 1935 1936 1937 1938 1939 1940 1941 1942 1943 1944 1945 1946 1947 1948 1949 1950 1951 1952 1953 1954 1955 1956 1957 1958 1959 1960 1961 1962 1963 1964 1965 1966 1967 1968 1969 1970 1971 1972 1973 1974 1975 1976 1977 1978 1979 1980 1981 1982 1983 1984 1985 1986 1987 1988 1989 1990 1991 1992 1993 1994 1995 1996 1997 1998 1999 2000 2001 2002 2003 2004 2005 2006 2007 2008 2009 2010 2011 2012 2013 2014 2015 2016 2017 2018 2019 2020 2021 2022 2023 2024 2025 2026 2027 2028 2029 2030 2031 2032 2033 2034 2035 2036 2037 2038 2039 2040 2041 2042 2043 2044 2045 2046 2047 2048 2049 2050 2051 2052 2053 2054 2055 2056 2057 2058 2059 2060 2061 2062 2063 2064 2065 2066 2067 2068 2069 2070 2071 2072 2073 2074 2075 2076 2077 2078 2079 2080 2081 2082 2083 2084 2085 2086 2087 2088 2089 2090 2091 2092 2093 2094 2095 2096 2097 2098 2099 2100 2101 2102 2103 2104 2105 2106 2107 2108 2109 2110 2111 2112 2113 2114 2115 2116 2117 2118 2119 2120 2121 2122 2123 2124 2125 2126 2127 2128 2129 2130 2131 2132 2133 2134 2135 2136 2137 2138 2139 2140 2141 2142 2143 2144 2145 2146 2147 2148 2149 2150 2151 2152 2153 2154 2155 2156 2157 2158 2159 2160 2161 2162 2163 2164 2165 2166 2167 2168 2169 2170 2171 2172 2173 2174 2175 2176 2177 2178 2179 2180 2181 2182 2183 2184 2185 2186 2187 2188 2189 2190 2191 2192 2193 2194 2195 2196 2197 2198 2199 2200 2201 2202 2203 2204 2205 2206 2207 2208 2209 2210 2211 2212 2213 2214 2215 2216 2217 2218 2219 2220 2221 2222 2223 2224 2225 2226 2227 2228 2229 2230 2231 2232 2233 2234 2235 2236 2237 2238 2239 2240 2241 2242 2243 2244 2245 2246 2247 2248 2249 2250 2251 2252 2253 2254 2255 2256 2257 2258 2259 2260 2261 2262 2263 2264 2265 2266 2267 2268 2269 2270 2271 2272 2273 2274 2275 2276 2277 2278 2279 2280 2281 2282 2283 2284 2285 2286 2287 2288 2289 2290 2291 2292 2293 2294 2295 2296 2297 2298 2299 2300 2301 2302 2303 2304 2305 2306 2307 2308 2309 2310 2311 2312 2313 2314 2315 2316 2317 2318 2319 2320 2321 2322 2323 2324 2325 2326 2327 2328 2329 2330 2331 2332 2333 2334 2335 2336 2337 2338 2339 2340 2341 2342 2343 2344 2345 2346 2347 2348 2349 2350 2351 2352 2353 2354 2355 2356 2357 2358 2359 2360 2361 2362 2363 2364 2365 2366 2367 2368 2369 2370 2371 2372 2373 2374 2375 2376 2377 2378 2379 2380 2381 2382 2383 2384 2385 2386 2387 2388 2389 2390 2391 2392 2393 2394 2395 2396 2397 2398 2399 2400 2401 2402 2403 2404 2405 2406 2407 2408 2409 2410 2411 2412 2413 2414 2415 2416 2417 2418 2419 2420 2421 2422 2423 2424 2425 2426 2427 2428 2429 2430 2431 2432 2433 2434 2435 2436 2437 2438 2439 2440 2441 2442 2443 2444 2445 2446 2447 2448 2449 2450 2451 2452 2453 2454 2455 2456 2457 2458 2459 2460 2461 2462 2463 2464 2465 2466 2467 2468 2469 2470 2471 2472 2473 2474 2475 2476 2477 2478 2479 2480 2481 2482 2483 2484 2485 2486 2487 2488 2489 2490 2491 2492 2493 2494 2495 2496 2497 2498 2499 2500 2501 2502 2503 2504 2505 2506 2507 2508 2509 2510 2511 2512 2513 2514 2515 2516 2517 2518 2519 2520 2521 2522 2523 2524 2525 2526 2527 2528 2529 2530 2531 2532 2533 2534 2535 2536 2537 2538 2539 2540 2541 2542 2543 2544 2545 2546 2547 2548 2549 2550 2551 2552 2553 2554 2555 2556 2557 2558 2559 2560 2561 2562 2563 2564 2565 2566 2567 2568 2569 2570 2571 2572 2573 2574 2575 2576 2577 2578 2579 2580 2581 2582 2583 2584 2585 2586 2587 2588 2589 2590 2591 2592 2593 2594 2595 2596 2597 2598 2599 2600 2601 2602 2603 2604 2605 2606 2607 2608 2609 2610 2611 2612 2613 2614 2615 2616 2617 2618 2619 2620 2621 2622 2623 2624 2625 2626 2627 2628 2629 2630 2631 2632 2633 2634 2635 2636 2637 2638 2639 2640 2641 2642 2643 2644 2645 2646 2647 2648 2649 2650 2651 2652 2653 2654 2655 2656 2657 2658 2659 2660 2661 2662 2663 2664 2665 2666 2667 2668 2669 2670 2671 2672 2673 2674 2675 2676 2677 2678 2679 2680 2681 2682 2683 2684 2685 2686 2687 2688 2689 2690 2691 2692 2693 2694 2695 2696 2697 2698 2699 2700 2701 2702 2703 2704 2705 2706 2707 2708 2709 2710 2711 2712 2713 2714 2715 2716 2717 2718 2719 2720 2721 2722 2723 2724 2725 2726 2727 2728 2729 2730 2731 2732 2733 2734 2735 2736 2737 2738 2739 2740 2741 2742 2743 2744 2745 2746 2747 2748 2749 2750 2751 2752 2753 2754 2755 2756 2757 2758 2759 2760 2761 2762 2763 2764 2765 2766 2767 2768 2769 2770 2771 2772 2773 2774 2775 2776 2777 2778 2779 2780 2781 2782 2783 2784 2785 2786 2787 2788 2789 2790 2791 2792 2793 2794 2795 2796 2797 2798 2799 2800 2801 2802 2803 2804 2805 2806 2807 2808 2809 2810 2811 2812 2813 2814 2815 2816 2817 2818 2819 2820 2821 2822 2823 2824 2825 2826 2827 2828 2829 2830 2831 2832 2833 2834 2835 2836 2837 2838 2839 2840 2841 2842 2843 2844 2845 2846 2847 2848 2849 2850 2851 2852 2853 2854 2855 2856 2857 2858 2859 2860 2861 2862 2863 2864 2865 2866 2867 2868 2869 2870 2871 2872 2873 2874 2875 2876 2877 2878 2879 2880 2881 2882 2883 2884 2885 2886 2887 2888 2889 2890 2891 2892 2893 2894 2895 2896 2897 2898 2899 2900 2901 2902 2903 2904 2905 2906 2907 2908 2909 2910 2911 2912 2913 2914 2915 2916 2917 2918 2919 2920 2921 2922 2923 2924 2925 2926 2927 2928 2929 2930 2931 2932 2933 2934 2935 2936 2937 2938 2939 2940 2941 2942 2943 2944 2945 2946 2947 2948 2949 2950 2951 2952 2953 2954 2955 2956 2957 2958 2959 2960 2961 2962 2963 2964 2965 2966 2967 2968 2969 2970 2971 2972 2973 2974 2975 2976 2977 2978 2979 2980 2981 2982 2983 2984 2985 2986 2987 2988 2989 2990 2991 2992 2993 2994 2995 2996 2997 2998 2999 3000 3001 3002 3003 3004 |
/* 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 #include #include #include #include #include "book.h" #include "evaluate.h" #include "movegen.h" #include "movepick.h" #include "notation.h" #include "search.h" #include "timeman.h" #include "thread.h" #include "tt.h" #include "ucioption.h" namespace Search { // -- 探索関係のフラグ // これらはglobalになっているが、クラス化しておかないと // 1スレッドずつ別別の局面を探索させるときに困るのではなかろうか…。 // 探索の強制停止信号などのフラグの集合体。 // Signals.stopをtrueにしたあと返ってきた評価値は信用ならないので用いてはならない。 volatile SignalsType Signals; // UCIプロトコルで受け取った思考時間等の設定項目 LimitsType Limits; // 探索開始局面での指し手 std::vector // 探索開始局面 Position RootPos; // 探索開始局面での手番 Color RootColor; // 探索を開始した時刻。misc::time()にて探索開始時に取得。 // 探索が終了したときにこの値と引き算をして探索に要した時間を算出するのに使う。 Time::point SearchTime; // セットアップされた局面(UCIのpositionコマンドで渡された開始局面から探索を開始する直前の局面)までの // 局面のキーの追跡をする。 千日手の検出に必要とされる。 // ※ 実体はStateInfoのstackである。 StateStackPtr SetupStates; } using std::string; using Eval::evaluate; using namespace Search; namespace { // Set to true to force running with one thread. Used for debugging // これをtrueにすると1スレッド実行になる。デバッグに使う。 const bool FakeSplit = false; // Different node types, used as template parameter // ノードの種別。C++のtemplate parameterとして使う。 enum NodeType { Root, PV, NonPV, SplitPointRoot, SplitPointPV, SplitPointNonPV }; // Dynamic razoring margin based on depth // Razoring枝刈りのときのdepthに対するマージン値。 // ゲーム木の性質に合わせて調整すべき。(将棋の場合、序盤と終盤で違うだろうし…) inline Value razor_margin(Depth d) { return Value(512 + 16 * int(d)); } // Futility lookup tables (initialized at startup) and their access functions int FutilityMoveCounts[2][32]; // [improving][depth] // Futility pruningで用いるマージン値。 // ※ Razoringと対称性はなくていいのか? inline Value futility_margin(Depth d) { return Value(100 * int(d)); } // Reduction lookup tables (initialized at startup) and their access function // Reduction(残り探索深さを減らす)のための参照テーブル (起動時に初期化される)と、 // これらにアクセスするための関数 int8_t Reductions[2][2][64][64]; // [pv][improving][depth][moveNumber] // i = improving = 局面の評価値が2手前から上昇したか // d = 残り探索深さ // mn = move number = この局面でMovePickerからもらった何番目の合法な指し手であるか // Reduction lookup tables (initialized at startup) and their access function template return (Depth)Reductions[PvNode][i][std::min(int(d) / ONE_PLY, 63)][std::min(mn, 63)]; } // PVSize : Options["MultiPV"]で設定された値 // ※ PVをRootMoveに対して何個目まで求めるのか // PVIdx : root nodeで現在何番目のPVの指し手を調べているかのカウンター size_t PVSize, PVIdx; // 時間制御用のクラス // これglobalなのか…。 TimeManager TimeMgr; // PVの変動性を表す量 // これは最善手が変化した回数であり、前の探索iterationで変化した分の重みを // 小さくするためにiterationごとに0.8掛けていく。この値を思考時間の調整のために使う。 // (例えば、PVの変動が激しければ持ち時間をもう少し投与するだとか) double BestMoveChanges; // 引き分けのときのみなしスコア // 千日手検出時や探索の中断のときに使われる。 Value DrawValue[COLOR_NB]; HistoryStats History; GainsStats Gains; CountermovesStats Countermoves; // search<>()はPVとnon-PVノード、通常およびSplitPointノードに対する探索のメイン関数である。 // ちょうどsplit pointのあと呼び出されたとき、探索は比較的単純である。なぜなら、 // 我々はすでにhash tableをprobe(テーブルにデータが記録されているか調べること)して、 // null move探索を済ませ、splitする前に最初の指し手の探索は終わっているので、 // これらすべての処理を再度行う必要はない。 // このとき我々は、hash tableに対して何も格納する必要もない。 // これは、split pointから戻ったあとに処置されるべきである。 template Value search(Position& pos, Stack* ss, Value alpha, Value beta, Depth depth, bool cutNode); template Value qsearch(Position& pos, Stack* ss, Value alpha, Value beta, Depth depth); // id_loop()は、メインの反復深化のループである。これは割り当てられた思考時間を消費するか、 // ユーザーが探索を中断するか、最大探索深さまで達するかするまで、 // depth(残り探索深さ)を増加させながらsearchを繰り返し呼び出す。 void id_loop(Position& pos); Value value_to_tt(Value v, int ply); Value value_from_tt(Value v, int ply); bool allows(const Position& pos, Move first, Move second); bool refutes(const Position& pos, Move first, Move second); string uci_pv(const Position& pos, int depth, Value alpha, Value beta); // 手加減のためのヘルパー struct Skill { Skill(int l) : level(l), best(MOVE_NONE) {} ~Skill() { if (enabled()) // Swap best PV line with the sub-optimal one // 最善応手列を二番目に最善な列と入れ替える? std::swap(RootMoves[0], *std::find(RootMoves.begin(), RootMoves.end(), best ? best : pick_move())); } // 手加減が有効なのか bool enabled() const { return level < 20; } // 2番目以降の最善手を選ぶ探索深さ。 bool time_to_pick(int depth) const { return depth == 1 + level; } // 手加減用の指し手の取得。 Move pick_move(); // ハンディキャップ戦用のパラメーター(小さいほどハンディキャップが大きい) // default == 20で、20だとハンディキャップなし。 int level; Move best; }; } // namespace /// Search::init() is called during startup to initialize various lookup tables // Search::init()は、種々のlookup用のテーブルを初期化するために起動時に呼び出される。 void Search::init() { int d; // depth (ONE_PLY == 2) int hd; // half depth (ONE_PLY == 1) int mc; // moveCount // Init reductions array for (hd = 1; hd < 64; ++hd) for (mc = 1; mc < 64; ++mc) { double pvRed = log(double(hd)) * log(double(mc)) / 3.0; double nonPVRed = 0.33 + log(double(hd)) * log(double(mc)) / 2.25; Reductions[1][1][hd][mc] = (int8_t)(pvRed >= 1.0 ? floor(pvRed * int(ONE_PLY)) : 0); Reductions[0][1][hd][mc] = (int8_t)(nonPVRed >= 1.0 ? floor(nonPVRed * int(ONE_PLY)) : 0); Reductions[1][0][hd][mc] = Reductions[1][1][hd][mc]; Reductions[0][0][hd][mc] = Reductions[0][1][hd][mc]; if (Reductions[0][0][hd][mc] > 2 * ONE_PLY) Reductions[0][0][hd][mc] += ONE_PLY; else if (Reductions[0][0][hd][mc] > 1 * ONE_PLY) Reductions[0][0][hd][mc] += ONE_PLY / 2; } // Init futility move count array for (d = 0; d < 32; ++d) { FutilityMoveCounts[0][d] = int(2.4 + 0.222 * pow(d + 0.0, 1.8)); FutilityMoveCounts[1][d] = int(3.0 + 0.3 * pow(d + 0.98, 1.8)); } } /// Search::perft() is our utility to verify move generation. All the leaf nodes /// up to the given depth are generated and counted and the sum returned. // 指し手生成(合法手の生成)の検証のためのユーティリティ。 // すべてのリーフノードを与えられた探索深さdepthまで調べ、生成される指し手の数の合計を返す。 static size_t perft(Position& pos, Depth depth) { StateInfo st; size_t cnt = 0; CheckInfo ci(pos); const bool leaf = depth == 2 * ONE_PLY; for (const ExtMove& ms : MoveList { pos.do_move(ms.move, st, ci, pos.gives_check(ms.move, ci)); cnt += leaf ? MoveList pos.undo_move(ms.move); } return cnt; } size_t Search::perft(Position& pos, Depth depth) { return depth > ONE_PLY ? ::perft(pos, depth) : MoveList } /// Search::think() is the external interface to Stockfish's search, and is /// called by the main thread when the program receives the UCI 'go' command. It /// searches from RootPos and at the end prints the "bestmove" to output. // Search::think()は、Stockfishの探索に対する外部インターフェースであり、 // プログラムがUCIの'go'コマンドを受信したときにメインスレッドから呼び出される。 // これはRootPos(探索開始局面)からの探索であり、最後に出力に対して"bestmove"を表示する。 void Search::think() { // 定跡のためのクラス。 // 擬似乱数発生器(PRNG)を一度だけ初期化するためにstaticで定義される。 static PolyglotBook book; // Defined static to initialize the PRNG only once // 探索開始局面での手番 RootColor = RootPos.side_to_move(); TimeMgr.init(Limits, RootPos.game_ply(), RootColor); // 探索開始局面での指し手がひとつもなかった。 if (RootMoves.empty()) { RootMoves.push_back(MOVE_NONE); sync_cout << "info depth 0 score " << score_to_uci(RootPos.checkers() ? -VALUE_MATE : VALUE_DRAW) << sync_endl; goto finalize; } // Options["OwnBook"]は定跡ファイルを持っているかのフラグ。 // "go infinite"のときは定跡を使わない思考(のようだ) if (Options["OwnBook"] && !Limits.infinite && !Limits.mate) { // 定跡にヒットするか。 // Options["Book File"] = 定跡ファイルのファイル名 // Options["Best Book Move"] = これがtrueだと定跡DBのその局面のなかで最大のスコアのものを選択。 // さもなくば、定跡DB上の指し手からランダムに1つ選ぶ。 Move bookMove = book.probe(RootPos, Options["Book File"], Options["Best Book Move"]); // 指し手が見つかり、その指し手がRootMovesのなかにあるなら if (bookMove && std::count(RootMoves.begin(), RootMoves.end(), bookMove)) { // RootMoves[0]がbestな指し手なのでそれと入れ替えてしまう。 std::swap(RootMoves[0], *std::find(RootMoves.begin(), RootMoves.end(), bookMove)); goto finalize; } } // 引き分けをどう扱うか。 // Contempt≒恥辱 // 引き分けをOptions["Contempt Factor"]は歩の何枚分の値だと評価するか。 if (Options["Contempt Factor"] && !Options["UCI_AnalyseMode"]) { int cf = Options["Contempt Factor"] * PawnValueMg / 100; // From centipawns cf = cf * Material::game_phase(RootPos) / PHASE_MIDGAME; // Scale down with phase // 引き分けのときのスコアの初期化。 // 探索の中断のときに使われる。 // RootColor = 探索開始局面の手番 = 思考エンジン側から見た手番。 DrawValue[RootColor] = VALUE_DRAW - Value(cf); DrawValue[~RootColor] = VALUE_DRAW + Value(cf); } else DrawValue[WHITE] = DrawValue[BLACK] = VALUE_DRAW; // 探索ログを書き出すならば if (Options["Write Search Log"]) { // 探索ログのファイル名 Log log(Options["Search Log Filename"]); // 探索中の局面をfen形式で出力。 log << "\nSearching: " << RootPos.fen() // 時間無制限か << "\ninfinite: " << Limits.infinite // ponderありか << " ponder: " << Limits.ponder // 持ち時間 << " time: " << Limits.time[RootColor] // 1手ごとの増加時間 << " increment: " << Limits.inc[RootColor] // moves to goはいくらに設定されているか << " moves to go: " << Limits.movestogo << std::endl; } // Reset the threads, still sleeping: will be wake up at split time // それぞれのスレッドをリセットするが、依然としてsleepしている。これはsplit時に起こされるであろう。 for (Thread* th : Threads) th->maxPly = 0; // IdleになったThreadをsleep(0)で待機させるのか(そのほうがレスポンスはよくなるがCPU負荷が高くなる)、 // シグナルで待機させるのか Threads.sleepWhileIdle = Options["Idle Threads Sleep"]; Threads.timer->run = true; // 定期的なタイマーを起動させる // ※ タイマー監視スレッドによる監視(定期的に思考時間が与えれた時間を超過していないかを監視)をスタートさせるの意味 Threads.timer->notify_one(); // Wake up the recurring timer // 探索の開始 id_loop(RootPos); // Let's start searching ! // タイマーの停止 Threads.timer->run = false; // Stop the timer // idleスレッドにsleepを要求 Threads.sleepWhileIdle = true; // Send idle threads to sleep // 探索結果ログを書き出すのであれば… if (Options["Write Search Log"]) { // 経過時間を計算する。ミリ秒未満繰り上げるために+1してある。 // SearchTimeは探索開始時刻 Time::point elapsed = Time::now() - SearchTime + 1; Log log(Options["Search Log Filename"]); // 探索したノード数 log << "Nodes: " << RootPos.nodes_searched() // 探索速度 1秒当たりのノード数 << "\nNodes/second: " << RootPos.nodes_searched() * 1000 / elapsed // 最善手 << "\nBest move: " << move_to_san(RootPos, RootMoves[0].pv[0]); // ponderの指し手(相手の指し手の予想) // こちらのbestmoveで1手進めてそこで相手側の指し手の予想手を出力 StateInfo st; RootPos.do_move(RootMoves[0].pv[0], st); log << "\nPonder move: " << move_to_san(RootPos, RootMoves[0].pv[1]) << std::endl; RootPos.undo_move(RootMoves[0].pv[0]); } finalize: // When search is stopped this info is not printed // 探索が終了させられたときにはこの情報は表示されない。 // 探索したノード数と探索に要した時間 sync_cout << "info nodes " << RootPos.nodes_searched() << " time " << Time::now() - SearchTime + 1 << sync_endl; // When we reach max depth we arrive here even without Signals.stop is raised, // but if we are pondering or in infinite search, according to UCI protocol, // we shouldn't print the best move before the GUI sends a "stop" or "ponderhit" // command. We simply wait here until GUI sends one of those commands (that // raise Signals.stop). // 我々がSignals.stopさえ生じずにmax depth(最大探索深さ)まで達したとき、 // しかし、ponder中であるか、または、infinite search(思考時間無制限での探索)であるなら // UCIプロトコルに従い、我々はGUIが"stop"か"ponderhit"コマンドを送るまでbest moveは表示すべきではない。 // 我々は単にGUIがそれらのコマンド(これによりSignals.stopが生じる)を送るまで単に待つ。 // Signals.stopになっておらず、ponderか思考時間無制限であるなら if (!Signals.stop && (Limits.ponder || Limits.infinite)) { // 探索は終わっているのでponderhitすれば即座にbestmoveを返すフラグをtrueに Signals.stopOnPonderhit = true; // あとはひたすらSignals.stopを待つ。 RootPos.this_thread()->wait_for(Signals.stop); } // Best move could be MOVE_NONE when searching on a stalemate position // スティールメイトの局面について探索しているとき最善手はMOVE_NONEでありうる。 // ※ 将棋だと指し手が存在しない局面。将棋のルールだと詰みなのだが、チェスだと引き分けなのだ。 // 将棋は、MOVE_NONEだったら、投了を送らないと…。 sync_cout << "bestmove " << move_to_uci(RootMoves[0].pv[0], RootPos.is_chess960()) << " ponder " << move_to_uci(RootMoves[0].pv[1], RootPos.is_chess960()) << sync_endl; } namespace { // id_loop() is the main iterative deepening loop. It calls search() repeatedly // with increasing depth until the allocated thinking time has been consumed, // user stops the search, or the maximum search depth is reached. // id_loop()は、メインの反復深化のループである。これは割り当てられた思考時間を消費するか、 // ユーザーが探索を中断するか、最大探索深さまで達するかするまで、 // depth(残り探索深さ)を増加させながらsearchを繰り返し呼び出す。 // pos : 探索開始局面 void id_loop(Position& pos) { // rootから現在探索中のnodeまでのnode情報を格納しておく配列。 Stack stack[MAX_PLY_PLUS_6], *ss = stack + 2; // To allow referencing (ss-2) // ss-2という参照のしかたを許すためstack[2]から使っていく。 // ssはStackの現在のnodeを示すところへのポインター // 反復深化のiteration深さ。 int depth; // alpha-beta探索の最大スコア , alpha値 , beta値 // delta : aspiration searchのときの探索窓の幅に使う値。 // fail high/lowするごとにこの値を1.5倍させながら、探索幅を広げていく。 Value bestValue, alpha, beta, delta; // 確保したStack構造体のゼロ初期化。ただし全体を初期化するのは無駄なので // 先頭5個だけ初期化する。どうせ次のノードを調べていくときに初期化するので。 // 0 1 2 3 4 // ↑ss=2個目を指しており、これが現在のノード(Root node)であるから、 // 2手先のノードまでゼロ初期化されることになる。 std::memset(ss - 2, 0, 5 * sizeof(Stack)); // 直前の指し手をMOVE_NULL扱いしておくことにより、gainのupdateをskipするhack // gainは統計情報的な何か。 (ss - 1)->currentMove = MOVE_NULL; // Hack to skip update gains // 探索iteration深さは0から。 depth = 0; // best moveがRoot nodeで変化した回数。 // これをベースに、探索時間の調整を行う。 BestMoveChanges = 0; // alpha = -∞ , beta = +∞ // deltaは、(alpha-delta,beta+delta)の範囲で探索するとして、-∞なら幅がゼロ未満になるので初期化用の値として適切。 bestValue = delta = alpha = -VALUE_INFINITE; beta = VALUE_INFINITE; // 置換表を新しい探索のために掃除する。(完全なclearではない) TT.new_search(); // history tableのクリア History.clear(); // gains tableのクリア Gains.clear(); // counterの指し手 tableのクリア Countermoves.clear(); // PVをRootMoveに対して何個目まで求めるのか PVSize = Options["MultiPV"]; // ハンディキャップ戦用のパラメーター(小さいほどハンディキャップが大きい) // default == 20で、20だとハンディキャップなし。 Skill skill(Options["Skill Level"]); // Do we have to play with skill handicap? In this case enable MultiPV search // that we will use behind the scenes to retrieve a set of possible moves. // スキルハンディキャップでプレーする必要があるのか? // この場合、我々は可能な指し手の集合を回収するために水面下で用いる // MultiPV探索を有効にする。 // ※ ハンディキャップ戦だと最善手以外にもPVが必要なので。 // ハンディキャップ戦ならばPVSizeは少なくとも4でないと。(4つ目の指し手までPVを求める) // defaultではskill.enable() == falseなのでこの処理は関係ない。 if (skill.enabled() && PVSize < 4) PVSize = 4; // PVSizeはPV lineを求める個数。 // root局面での指し手の数を超えて設定することは意味がないので頭打ちにする。 PVSize = std::min(PVSize, RootMoves.size()); // Iterative deepening loop until requested to stop or target depth reached // 停止することを要求されるか、目的の深さまで達するまで反復深化で回る。 // ※ depth = iterationカウンター。このループ内では1からスタートしてループごとに1ずつ増える。 while (++depth <= MAX_PLY && !Signals.stop && (!Limits.depth || depth <= Limits.depth)) { // Age out PV variability metric // PVの変動性を表す量を更新する // これは最善手が変化した回数であり、前の探索iterationで変化した分の重みを // 小さくするためにiterationごとに0.8掛けていく。この値を思考時間の調整のために使う。 // (例えば、PVの変動が激しければ持ち時間をもう少し投与するだとか) BestMoveChanges *= 0.8; // Save last iteration's scores before first PV line is searched and all // the move scores but the (new) PV are set to -VALUE_INFINITE. // PV lineが探索される前にひとつ前のiteration深さでのスコアを保存して、 // (新しく)PVの指し手となった手を除くすべての指し手スコアは-VALUE_INFINITEがセットされている。 for (RootMove& rm : RootMoves) rm.prevScore = rm.score; // MultiPV loop. We perform a full root search for each PV line // MultiPVのループ。※ 上位の候補手それぞれについてそのPVを探索するモードのとき。 // 我々はそれぞれのPV lineに対してfull root searchを行う。 // ※ デフォルトではMultiPVはオフであり、PVSize == 1。 for (PVIdx = 0; PVIdx < PVSize && !Signals.stop; ++PVIdx) { // Reset aspiration window starting size // aspiration探索の窓のサイズをリセットする。 // 5回目のiteration以降であれば.. if (depth >= 5) { // 前回のこの指し手の探索スコアの±16の範囲でaspiration searchを行う。 // prevScoreは-VALUE_INFINITE,+VALUE_INFINITEであることもあるので、 // この範囲を超えないようにmax()とmin()が書いてある。 delta = Value(16); alpha = std::max(RootMoves[PVIdx].prevScore - delta, -VALUE_INFINITE); beta = std::min(RootMoves[PVIdx].prevScore + delta, VALUE_INFINITE); /* https://chessprogramming.wikispaces.com/Aspiration+Windows Aspiration Windowsとはalpha-beta探索における探索空間を減らす方法である。 このテクニックは、期待する値の推測値(通例、反復深化における最後の反復したときのスコア)が使われ、 alpha-betaの範囲としてこの値(推測値)の付近の窓を使う。なぜなら、窓が狭いと多くのbeta cutoffが達成され、 探索は短い時間になる。この副作用は、真のスコアが窓の外である場合に、再探索のコストが必要になることである。 典型的には窓のサイズは推測値の両側においてPAWNの価値の1/2から1/4である。(※訳注 窓の幅としてはその倍) */ // ここではPAWNの価値(PawnValueMg == 198)に対して1/16.5という極めて小さな値に設定されていることに注意。 } // Start with a small aspiration window and, in case of fail high/low, // research with bigger window until not failing high/low anymore. // 小さなaspiration窓で開始し、fail high/lowの場合、もはやfail high/lowが起きないように // なるまで、より大きな窓で再探索する。 while (true) { bestValue = search // Bring to front the best move. It is critical that sorting is // done with a stable algorithm because all the values but the first // and eventually the new best one are set to -VALUE_INFINITE and // we want to keep the same order for all the moves but the new // PV that goes to the front. Note that in case of MultiPV search // the already searched PV lines are preserved. // best moveを先頭に持ってくる。ソートが安定アルゴリズムによって行われることが極めて重要である。 // なぜなら、最初の指し手と最後の(eventuallly)新しいbestな指し手を除く すべての指し手の値は-VALUE_INFINITEになり、 // 我々は手前に来たPV以外のすべての指し手に対して同じ順位を保っていて欲しい。 // ※ PVIdxは0からスタートなので現在探索を開始するPVの指し手を含み、末尾までのなかでベストなものが // RootMoves[PVIdx]に来るようにする。 std::stable_sort(RootMoves.begin() + PVIdx, RootMoves.end()); // Write PV back to transposition table in case the relevant // entries have been overwritten during the search. // 探索中に上書きされた関連する置換表のエントリーにPV(最善応手列)を書き戻す。 // ※ 置換表にPVを書き戻して置換表の破壊から防備している。ここまでしないといけないのか…。 for (size_t i = 0; i <= PVIdx; ++i) RootMoves[i].insert_pv_in_tt(pos); // If search has been stopped break immediately. Sorting and // writing PV back to TT is safe becuase RootMoves is still // valid, although refers to previous iteration. // もし探索が停止されたなら即座にbreakする。ソートとPVを置換表に書き戻したことは // 安全である。なぜなら、RootMovesは前回のiterationのものであるが、依然として有効であるからだ。 if (Signals.stop) break; // When failing high/low give some update (without cluttering // the UI) before to research. // 再探索の前に(UIを散らかさずに)fail high/lowがいくつかの更新をするとき // ※ UIにPV情報をしばらく出力しておらず、今回のfail high/lowによるPVの変化が // あったのであればそれをUIに出力するの意味。 // fail high/lowが起きて、かつ探索開始時刻から3秒以上経過している if ((bestValue <= alpha || bestValue >= beta) && Time::now() - SearchTime > 3000) sync_cout << uci_pv(pos, depth, alpha, beta) << sync_endl; // In case of failing low/high increase aspiration window and // research, otherwise exit the loop. // fail low/highが起きた場合、aspiration窓を増加させ再探索し、 // さもなくばループを抜ける。 if (bestValue <= alpha) { // fail lowしているので、下側をさらにdeltaだけ広げる alpha = std::max(bestValue - delta, -VALUE_INFINITE); // fail low中の探索であるフラグをtrueに Signals.failedLowAtRoot = true; // ponderがhitしても停止していい状態ではない。(このPV怪しいので) Signals.stopOnPonderhit = false; } else if (bestValue >= beta) // fail highならば、これ以上の値が期待できるわけでありponder hitすればこれをbest moveとして // 返しても問題がないはずで、上のような処理はなく、単に上側をdeltaだけ広げる。 beta = std::min(bestValue + delta, VALUE_INFINITE); else // fail lowもfail highもしていなければaspiration searchのループから抜ける。 break; // deltaを1.5倍していく。(指数関数的に増やすため) delta += delta / 2; assert(alpha >= -VALUE_INFINITE && beta <= VALUE_INFINITE); } // --- aspiration window探索の終わり。 // Sort the PV lines searched so far and update the GUI // これまで探索したPV lineをソートして、GUIを更新する。 // RootMovesのうち、先頭からPVIdx個の範囲でソートする。 std::stable_sort(RootMoves.begin(), RootMoves.begin() + PVIdx + 1); // MultiPVのときにに4個PVを調べる設定だとして4個目のPVを調べたあとであるか、 // もしくは探索開始時刻から3秒以上経過しているならPVを出力する。 if (PVIdx + 1 == PVSize || Time::now() - SearchTime > 3000) sync_cout << uci_pv(pos, depth, alpha, beta) << sync_endl; } // --- PVを複数求めるときのループの終わり // Do we need to pick now the sub-optimal best move ? // 二番目以降の最善手をいま選ぶ必要があるか? // ※ 手加減用。defaultではこの機能はオフ。 // skillとして事前に指定された探索深さになったときに手加減用の指し手を取得する。 if (skill.enabled() && skill.time_to_pick(depth)) skill.pick_move(); // 探索ログの書き出しオプションが指定されていたら if (Options["Write Search Log"]) { // 通例、RootMoves[0]がbest moveであるが、手加減モードだとskill.best != MOVE_NONEであることがあり、 // そのときはこれをbest move扱いしてそのPVを表示する必要がある。 RootMove& rm = RootMoves[0]; if (skill.best != MOVE_NONE) rm = *std::find(RootMoves.begin(), RootMoves.end(), skill.best); Log log(Options["Search Log Filename"]); log << pretty_pv(pos, depth, rm.score, Time::now() - SearchTime, &rm.pv[0]) << std::endl; } // Do we have found a "mate in x"? // x手での詰みを発見したのか? // ※ ここでLimits.mateを2倍しているのはチェスでの詰み手数は倍としてカウントするためか? // 将棋では、ここ、倍する必要はないように思われる。 if (Limits.mate && bestValue >= VALUE_MATE_IN_MAX_PLY && VALUE_MATE - bestValue <= 2 * Limits.mate) Signals.stop = true; // Do we have time for the next iteration? Can we stop searching now? // 次のiterationのための時間があるか? すぐに探索を停止することができるか? // 時間制御を用いるモードであり、Stop信号が来ておらず、かつstopOnPonderhit信号が来ていないなら if (Limits.use_time_management() && !Signals.stop && !Signals.stopOnPonderhit) { bool stop = false; // Local variable, not the volatile Signals.stop // ローカル変数であり、volatileなSignals.stopではない。 // 以下でいくつかの停止条件のテストを行い、このローカル変数のstopフラグがtrueになっていれば // 本当に停止する。 // Take in account some extra time if the best move has changed // もし最善手が変動したのならば、いくらか余分な時間を考慮時間に追加する // ※ depthが5以上50未満のときでPV lineを求める数が1のときは // 最善手が変化した回数をTimeMgr(時間制御クラス)に渡して、探索の不安定性から // 今回の考慮時間を増やしたりするときの参考とする。 if (depth > 4 && depth < 50 && PVSize == 1) TimeMgr.pv_instability(BestMoveChanges); // Stop search if most of available time is already consumed. We // probably don't have enough time to search the first move at the // next iteration anyway. // もし利用可能な時間の大半をすでに消費しているならば探索を停止させる。 // おそらく次のiterationにおける最初の手の探索のための十分な時間すらないだろうから。 // 探索開始時刻からの経過が、TimeMgr.available_time()×62%を超えているなら停止。 if (Time::now() - SearchTime > (TimeMgr.available_time() * 62) / 100) stop = true; // Stop search early if one move seems to be much better than others // もしひとつの手が残りの手より良い手に思えるならば探索を停止させてしまう。 // 条件) // 1. iteration depth >= 12 // 2. best moveが変化した回数が0回(※割り算誤差があるのでDBL_EPSILONという微小な0を意味する定数を使ってある) // 3. すでにstopすることが確定しているのでなく // 4. PVSize == 1 (※ MultiPVのときは複数のPVをそれぞれ比較したい?) // 5. bestValueが詰まされるスコアではない // ※ 詰まされるスコアのときはここで諦めずに回避手をめいいっぱい探すべき。 // 6. 探索開始時刻からの経過が、TimeMgr.available_time()×20%を超えていて if (depth >= 12 && BestMoveChanges <= DBL_EPSILON && !stop && PVSize == 1 && bestValue > VALUE_MATED_IN_MAX_PLY && (RootMoves.size() == 1 || Time::now() - SearchTime > (TimeMgr.available_time() * 20) / 100)) { // rBeta = (現在のbestValue - 歩2枚の価値) // として、いまのbest moveを除外してnull windowで探索して、これを超えるものがないかどうかを検証する。 Value rBeta = bestValue - 2 * PawnValueMg; // 探索のときに除外する指し手 = いまのPVの手 ss->excludedMove = RootMoves[0].pv[0]; // null window中なのでさらにnull moveはしない。 ss->skipNullMove = true; // null window探索。 Value v = search // 探索が終了したので上で一時的に設定したフラグを戻す ss->skipNullMove = false; ss->excludedMove = MOVE_NONE; // 上記の評価値がrBetaを上回らなかったので探索を停止する条件を満たした。 if (v < rBeta) stop = true; } // いずれかの探索終了条件を満たしたのであれば探索を終了させる。 if (stop) { // If we are allowed to ponder do not stop the search now but // keep pondering until GUI sends "ponderhit" or "stop". // もし、pomderすることが許されているのであれば、いまは探索を停止させず、 // GUIが"ponderhit"か"stop"を送るまでponderingを続ける。 if (Limits.ponder) Signals.stopOnPonderhit = true; else Signals.stop = true; } } } } // search<>() is the main search function for both PV and non-PV nodes and for // normal and SplitPoint nodes. When called just after a split point the search // is simpler because we have already probed the hash table, done a null move // search, and searched the first move before splitting, we don't have to repeat // all this work again. We also don't need to store anything to the hash table // here: This is taken care of after we return from the split point. // search<>()はPVとnon-PVノード、通常およびSplitPointノードに対する探索のメイン関数である。 // ちょうどsplit pointのあと呼び出されたとき、探索は比較的単純である。なぜなら、 // 我々はすでにhash tableをprobe(テーブルにデータが記録されているか調べること)して、 // null move探索を済ませ、splitする前に最初の指し手の探索は終わっているので、 // これらすべての処理を再度行う必要はない。 // このとき我々は、hash tableに対して何も格納する必要もない。 // これは、split pointから戻ったあとに処置されるべきである。 template Value search(Position& pos, Stack* ss, Value alpha, Value beta, Depth depth, bool cutNode) { // PVノードかどうかを表すフラグ。 // これは、PV(最善応手列)に絡む、大事なノード。 // RootとPVノード、およびそれをsplitしているときがあるのでSplitPointPV,SplitPointRoot。 const bool PvNode = (NT == PV || NT == Root || NT == SplitPointPV || NT == SplitPointRoot); // split(並列探索化)したノード。 const bool SpNode = (NT == SplitPointPV || NT == SplitPointNonPV || NT == SplitPointRoot); // Root(探索開始)ノード。 const bool RootNode = (NT == Root || NT == SplitPointRoot); // 以上のPvNode,SpNode,RootNodeのフラグはconstであり、コンパイル時に定まる定数。 // ゆえに、この変数がコンパイル時にfalseであることが確定すれば、 // if (PvNode) ... のように書いてある部分はコード生成のときに最適化により削除される。 // このsearch関数がtemplateになっているのにはそういう効果を狙ってのこと。 // alpha < betaでかつ、alpha,betaが有効な範囲内である。 assert(alpha >= -VALUE_INFINITE && alpha < beta && beta <= VALUE_INFINITE); // PvNodeでない(non PV node)ということはnull windowで探索しているはずなのでalpha == beta -1の幅で探索しているはず。 assert(PvNode || (alpha == beta - 1)); // 探索深さが0深さより大きい。 assert(depth > DEPTH_ZERO); Move quietsSearched[64]; StateInfo st; const TTEntry *tte; SplitPoint* splitPoint; // 現局面のハッシュキー。(置換表を見に行くときに必要) Key posKey; // ttMove : 置換表に載っていた現局面のbestな指し手 // excludedMove : この局面で探索から除外している指し手 // ※ 突出した指し手らしきものがあると思えるとき、その指し手より上回る指し手がないかをnull windowで探索するようなときに使う。 // ※ singular extensionのときもこれを使う。 Move ttMove, move, excludedMove, bestMove, threatMove; Depth ext, newDepth, predictedDepth; // bestValue = bestMove(最善手)のスコア // ttValue = 置換表に載っていたこの局面のスコア Value bestValue, value, ttValue, eval, nullValue, futilityValue; // pvMoveはPV(最善応手列)の指し手を調べているときにtrueになる。 // PV nodeにおける最初の手がPVの手としており、root nodeでは指し手はRootNodesに格納されているので // 前回のiterationで最大スコアであった指し手がこれ。 bool inCheck, givesCheck, pvMove, singularExtensionNode, improving; bool captureOrPromotion, dangerous, doFullDepthSearch; // moveCountはこの局面ですでに調べた、合法だった指し手の数。reductionなどに使う。0ならば詰みの局面。 // quietCountは静止探索で調べた指し手の数? int moveCount, quietCount; // Step 1. Initialize node // Step 1. nodeの初期化 // 自分のスレッド Thread* thisThread = pos.this_thread(); // この局面で王手がかかっているか。pos.checkersは王手している駒。 // inCheckはboolであり、ひとつでも王手している駒があればtrueになる。 inCheck = pos.checkers(); // splitしたnodeであるなら if (SpNode) { // splitしたnodeの情報構造体へのポインター splitPoint = ss->splitPoint; // splitPoint構造体から、指し手を調べていく上で最低限の情報だけ取得する bestMove = splitPoint->bestMove; threatMove = splitPoint->threatMove; bestValue = splitPoint->bestValue; // splitしたということは置換表にこの局面の情報がなかったからのはずであるから、 // 置換表の指し手はMOVE_NONE,置換表の指し手の評価値はVALUE_NONE扱い。 tte = nullptr; ttMove = excludedMove = MOVE_NONE; ttValue = VALUE_NONE; // bestValueがまともな評価値でなければおかしい。(1つは指し手を調べたはずだから) // またsplitPointの指し手が1個以上ないとsplitしたのはおかしい。 assert(splitPoint->bestValue > -VALUE_INFINITE && splitPoint->moveCount > 0); // 枝刈り等はすでに行っているはずなのですぐさま指し手を調べるループに。 goto moves_loop; } // moveCount(この局面で合法だった指し手の数をリセット) moveCount = quietCount = 0; // bestValueはマイナス∞にしておく。一つでも有効な指し手があれば、これ以上の値になっているはず。 bestValue = -VALUE_INFINITE; // 現在の指し手、bestの指し手、次の(1手進めた)局面における探索のときに除外する指し手はMOVE_NONEにしておく。 ss->currentMove = threatMove = (ss + 1)->excludedMove = bestMove = MOVE_NONE; // 現在の探索深さは前の探索深さ+1 ss->ply = (ss - 1)->ply + 1; // 特に理由のない限り、次の(1手進めた)探索nodeでnullMoveのskipはしないし(null moveの許可)、reductionもしない。 (ss + 1)->skipNullMove = false; (ss + 1)->reduction = DEPTH_ZERO; // killerの初期化 // ToDo : あれ?ここは、なぜに(ss+2) (ss + 2)->killers[0] = (ss + 2)->killers[1] = MOVE_NONE; // Used to send selDepth info to GUI // GUIに現在の選択探索深さを送るのに使う。 // PV nodeでかつ、このスレッドの最大探索深さmaxPlyが現在の探索深さより浅いなら、現在の探索深さで値を上書き。 // ※ thisThread->maxPlyは、このスレッドで最大何手深さまで探索したかを示す計測用の変数。 if (PvNode && thisThread->maxPly < ss->ply) thisThread->maxPly = ss->ply; // Root nodeでないなら if (!RootNode) { // Step 2. Check for aborted search and immediate draw // Step 2. 探索中断のフラグをチェックして、即座に引き分けの値を返す。 // 以下のいずれかの条件を満たすとき引き分けのときのスコアを返す // 1) Signals.stopは強制停止フラグ // 2) pos.is_draw()は、千日手判定や50手ルールによる引き分けの判定。 // 3) MAX_PLYは最大探索深さ。これを超えることは普通ありえないはずだが…。 // ※ 将棋の場合、王手千日手による負けのチェックが必要なのでこことis_draw()を書き換える必要がある。 if (Signals.stop || pos.is_draw() || ss->ply > MAX_PLY) return DrawValue[pos.side_to_move()]; // Step 3. Mate distance pruning. Even if we mate at the next move our score // would be at best mate_in(ss->ply+1), but if alpha is already bigger because // a shorter mate was found upward in the tree then there is no need to search // further, we will never beat current alpha. Same logic but with reversed signs // applies also in the opposite condition of being mated instead of giving mate, // in this case return a fail-high score. // Step 3. 王手の手数による枝刈り。例え、スコアが最短で(ss->ply+1)手以内の詰みである次の手で // 詰ませられるとしても、短い詰みが探索木に見つかっており、もしalphaがすでに大きいならば、 // これ以上探索する必要はなく、現在のalphaを打ち負かす(※訳注 : alpha値を更新する、それより // 高い値にする)ことは決してない。 // 符号が逆ではあるが同じ論理が詰ませる代わりに詰まされる側の相手側の状態についても適用でき、 // この場合、fail highのスコアを返す。 // ※ 訳文、よくわからん。いわゆるMate Distance Pruningのこと。 // cf . https://chessprogramming.wikispaces.com/Mate+Distance+Pruning alpha = std::max(mated_in(ss->ply), alpha); beta = std::min(mate_in(ss->ply + 1), beta); if (alpha >= beta) return alpha; } // Step 4. Transposition table lookup // We don't want the score of a partial search to overwrite a previous full search // TT value, so we use a different position key in case of an excluded move. // Step 4. 置換表のlookup // 前回のフル探索(この局面において除外する指し手がない探索)の置換表の値を上書きするために // 部分探索(特定の指し手を除外しての探索)のスコアは欲しくないので、 // この局面で除外された指し手がある場合、異なる局面のハッシュキーを用いる。 // この局面において除外する指し手があればそれを代入。 excludedMove = ss->excludedMove; // 現局面のハッシュキーを代入する。 // このnodeで除外する指し手があるなら、別のハッシュキーが返る。 // ToDo : この部分、exclusion_keyの引数はなくて、excludedMoveがなんであれ、必ず同じ値の // ハッシュキーが返るのだが、これでいいのか? // あまり良くない気がするのだが、root nodeで傑出した手であるか判定するためにbest moveを除外して // 探索するが、そのときに、そのあとのiterationで別の指し手がbest moveになったあと、同じように // その手を除外して探索したときに同じhash keyになってしまうが…。そのときはiteration回数が違うので // 問題ないということか…。 // → ああ、do_move()してそこでkeyは変わっているからいいのか。そうか…。 posKey = excludedMove ? pos.exclusion_key() : pos.key(); // 置換表のlookup。エントリーが見つかればtteにそのポインターが入る。 tte = TT.probe(posKey); // 置換表に登録されていた指し手として、root Nodeであれば、PVを見てそれが返る。 // さもなくば置換表の指し手の内容が返る。 // root Nodeで置換表が上書きで破壊されてしまい、変な指し手になることに対する対策。 // root NodeではsplitしないのでPVIdxが現在探索中のPVラインでそのpv[0]はroot nodeでの現在の最善手。 ttMove = RootNode ? RootMoves[PVIdx].pv[0] : tte ? tte->move() : MOVE_NONE; // 置換表に登録されていた現局面のスコア ttValue = tte ? value_from_tt(tte->value(), ss->ply) : VALUE_NONE; // この置換表の指し手をもって、今回の探索はしなくて済むと言えるのか? // At PV nodes we check for exact scores, while at non-PV nodes we check for // a fail high/low. Biggest advantage at probing at PV nodes is to have a // smooth experience in analysis mode. We don't probe at Root nodes otherwise // we should also update RootMoveList to avoid bogus output. // PV nodeにおいては、exact score(正確なスコア)であるかをチェックし、 // non PV nodeにおいては、fail high/lowをチェックしている。 // PV nodeにおけるこれをprobeする(置換表のエントリーにあるかを調べる)大きな長所は、 // 解析モードのスムーズな体験をすることである。 // Root nodeにおいてはprobeせず、またRootMoveListを更新もする。 // これはインチキの出力(※ 訳注:rootの局面の置換表エントリーが壊れていると // best moveの出力表示がおかしくなる)を避けるためである。 // 条件) // 1.root Nodeでない // 2.置換表にエントリーがある // 3.置換表に登録されていた指し手を得たときの残り探索深さが、現在の残り探索深さより深い。(意味のある指し手) // 4.ttValueがVALUE_NONEではない(アクセス競合が起きると稀にこの値になってしまう) // 5.PV nodeであるなら、BOUND_EXACTである // non PV nodeであれば置換表の値がbetaを超えているならBOUND_LOWER(真の値はこれより上なのでこのときbeta cutできる)であるか、 // betaを超えていないのであれば、BOUND_UPPER(真の値はこれより下なのでこのときbeta cutが起きないことが確定)である。 // 置換表にはPVのときとnon PVのときとで混ぜこぜに格納されていると思うのが、これは本当にいいのか? // PV nodeではnon PVで調べたときのスコアは信用すべきではないのでは? // → BOUND_EXACTはPV nodeでの探索結果なので、これで正しい。 // PV nodeでもBOUND_EXACTを信用していいのかという問題はあるのでは。 // 同じdepthであっても探索の幅が違うと枝刈りとかが変わってくるので。(aki.さん) if (!RootNode && tte && tte->depth() >= depth && ttValue != VALUE_NONE // Only in case of TT access race && (PvNode ? tte->bound() == BOUND_EXACT : ttValue >= beta ? (tte->bound() & BOUND_LOWER) : (tte->bound() & BOUND_UPPER))) { // 今回の探索より、置換表に登録されている結果のほうが優れているとみなせるので // 置換表の指し手を今回の探索結果とみなす。 // この置換表の指し手が役に立ったので、置換表のエントリーの世代を現在の世代にする。 TT.refresh(tte); ss->currentMove = ttMove; // Can be MOVE_NONE // killerの入れ替え // beta cutして、NULL MOVEではなくて、捕獲する手・成る手でもなくて // (それらは高くて当たり前だし、最初に試すのでkiller候補としてはふさわしくない) // 1番目のkillerでもなければ、1番目のkillerをこの手にして、2番目のkillerはいまの1番目のkillerにする。 if (ttValue >= beta && ttMove && !pos.capture_or_promotion(ttMove) && ttMove != ss->killers[0]) { ss->killers[1] = ss->killers[0]; ss->killers[0] = ttMove; } return ttValue; } // Step 5. Evaluate the position statically and update parent's gain statistics // Step 5. 局面を静的評価して、親のnodeのgainの統計をとる。 // ss->staticEval : この局面の静的評価 // eval : 置換表に登録されていた値(この局面の値として意味があるのならば) // 王手がかかっているならば、以下の枝刈りなどはすると正確な評価が得られないので // 静的評価は行わずに以下の枝刈り判定もskipして、指し手を調べるループに行く。 if (inCheck) { // この局面の静的評価は不明という扱いで。 ss->staticEval = eval = VALUE_NONE; goto moves_loop; } else if (tte) { // --- 置換表にエントリーが登録されていた場合 // Never assume anything on values stored in TT // 置換表に格納されている値に関して何も仮定しない。 // 置換表にスコアが格納されているとは限らない。(PVにおいて指し手のみ格納されているだけかも知れない) // 置換表に格納されていたスコアがVALUE_NONEであれば、評価関数を呼び出してやる if ((ss->staticEval = eval = tte->eval_value()) == VALUE_NONE) eval = ss->staticEval = evaluate(pos); // ToDo : このとき、置換表に評価値を書き戻さなくていいのだろうか? // → 置換表上にエントリー自体は存在していたわけだから、上書きする価値があるのかどうか… // Can ttValue be used as a better position evaluation? // 置換表に登録されていたスコアは、静的評価スコアより良い局面評価と言えるのか? // 条件) // 以下のa),b)のいずれか。 // a) 置換表に登録されていたエントリーのBOUNDがBOUND_LOWER(下限)もしくはBOUND_EXACTでかつ、置換表の値 > 静的評価スコア // → 置換表の値が静的評価をたぶん超えている // b) 置換表に登録されていたエントリーのBOUNDがBOUND_UPPER(上限)もしくはBOUND_EXACTでかつ、置換表の値 <= 静的評価スコア // → 置換表の値が静的評価をたぶん下回っている。 // このとき、evalとして、置換表の値を用いる // 意味) // BOUND_LOWERはこの局面のスコアの最低保証値であり、このnodeの真の評価値はttValue以上であることがわかっているので、 // この値より静的評価のスコアが低いならば、置換表の値のほうを信じて、ttValueであると考えるべき。逆も同様。 if (ttValue != VALUE_NONE) if (tte->bound() & (ttValue > eval ? BOUND_LOWER : BOUND_UPPER)) eval = ttValue; } else { // --- 置換表のエントリーがない場合 // evalはこの局面の静止評価(単に評価関数を呼び出して得た値) eval = ss->staticEval = evaluate(pos); // せっかく評価関数を呼び出したのでこの値を何はともあれ置換表に登録しておく。 // 探索深さ = DEPTH_NONE (探索なし) // 最善手 = MOVE_NONE (不明) // 評価値 = いまevaluate(pos)を呼び出して得た値 // BOUND = BOUND_NONE(探索していないスコアなので) // ToDo : 細かいことだがss->staticEvalだと最適化が阻害されるのでevalを引数に渡したほうがいいのではないか? TT.store(posKey, VALUE_NONE, BOUND_NONE, DEPTH_NONE, MOVE_NONE, ss->staticEval); } // 移動による駒の働きの上昇をGainsテーブルに記録する。 // 条件) // 1. 直前の指し手がcaptureではない。 // 2. staticEvalがVALUE_NONEではない。(静的評価をしたあとでないと差を計算できない) // 3. 1手前のstaticEvalがVALUE_NONEではない。(同上) // 4. 1手前がNULL_MOVEではない。(1手前で駒を動かしていないならば、駒の移動はさせていないので記録しても無駄) // 5. 指し手の種類が移動によるものである。 if (!pos.captured_piece_type() && ss->staticEval != VALUE_NONE && (ss - 1)->staticEval != VALUE_NONE && (move = (ss - 1)->currentMove) != MOVE_NULL && type_of(move) == NORMAL) { Square to = to_sq(move); Gains.update(pos.piece_on(to), to, -(ss - 1)->staticEval - ss->staticEval); // ToDo : あれ?符号おかしくない?1手前との評価値の差分であるなら1手前の符号は…。 // → 一手前は相手番なので評価値は相手から見た点数であり、符号は逆だから、これで正しい。 } // Step 6. Razoring (skipped when in check) // Step 6. Razoring (王手がかかっているときは適用しない) // このとき、beta-razor_marginを超えないことを確認するために、この値で静止探索を呼び出して、 // 確かにこれを下回るのであればRazoring枝刈りに成功したものとみなす。 // 条件 // 1.PV nodeではない。(PV nodeでは危ない枝刈りはしない) // 2.残りdepthが4手未満。 // 3. // eval : 静的評価値(この局面で評価関数を呼び出して得た値) // razor_marginは残り探索深さに比例して大きくなる関数として、 // eval + razor_margin < beta なら、残り探索深さを使ってもbetaを上回りそうにない。 // ( そこまで評価値が変動しないであろうから) // 4. 置換表の指し手がMOVE_NONE (≒新規ノード) // 5. betaが詰みの関係するスコアではない(≒詰み関連の探索中ではない) if (!PvNode && depth < 4 * ONE_PLY && eval + razor_margin(depth) < beta && ttMove == MOVE_NONE && abs(beta) < VALUE_MATE_IN_MAX_PLY && !pos.pawn_on_7th(pos.side_to_move())) { // depthでの評価値の変動幅はrazor_margin()で算出できるものとしてbeta - razor_marginを超えないことを検証する。 // ※ 細かいことだが、eval + razor_margin(depth) < betaのところ、 // eval < beta - razor_margin(depth)と書いたほうがこの部分と共通項になって最適化できるのではないか。 Value rbeta = beta - razor_margin(depth); // 残り深さ0、null windowで静止探索を呼び出して、rbetaを超えるかどうかを判定する。 Value v = qsearch if (v < rbeta) // Logically we should return (v + razor_margin(depth)), but // surprisingly this did slightly weaker in tests. // 論理的には、v + razor_margin(depth)を返すべきだが、 // 驚くべきことに、これはテストした結果、少し弱かった。 // ToDo : 何故v+razor_margin(depth)を返すべき?そして、何故弱くなるの? // → 前者の理由はよくわからないが、弱くなる理由は、vにrazor_margin(depth)の揺れ幅があるとして、 // この揺れ幅を最大にして返すよりは、揺れ幅の平均(0)をとって返すほうがだいたいの局面において // 正確なスコアリングと言えるからではないかな。 return v; } // Step 7. Futility pruning: child node (skipped when in check) // Step 7. Futility枝刈り : 子ノード(王手がかかっているときはこれは行わない) // 条件) // 1. PV nodeではない(PV nodeで適用していい枝刈りではない。PV大切!) // 2. ss->skipNullMoveフラグが立っていない。(前の局面でnull moveしてない) // ※ ss->skipNullMoveはnull move枝刈りをしない用のフラグで、これがtrueのときはfutility pruningも行わない // 3. // eval = 現局面での静的評価(評価関数そのまま呼び出した値) // eval - marginがbetaを超えるなら、この時点でbeta cutしてしまう。 // 4. 詰み探索中ではない。(詰み探索中はもっと短い手数の詰みを見つけたいのでここで枝刈りしては意味がない) // 5. evalが勝ち/負け関係のスコアではない。(勝ち/負けが確定しているときの探索では枝刈りしない) // 6. pos.non_pawn_material ← 将棋には関係なさげ // ↑これはPAWN以外の盤上の駒の価値を加算したもの。これが0だとPAWNとKINGしか残っていないということになる。 // たぶん終盤の寒い局面かどうかを判定しているのだと思われる。 if (!PvNode && !ss->skipNullMove && depth < 7 * ONE_PLY // 残り探索深さがある程度少ないとき && eval - futility_margin(depth) >= beta && abs(beta) < VALUE_MATE_IN_MAX_PLY && abs(eval) < VALUE_KNOWN_WIN && pos.non_pawn_material(pos.side_to_move()) ) return eval - futility_margin(depth); // Step 8. Null move search with verification search (is omitted in PV nodes) // Step 8. 検査を伴うNull move探索。(PV nodeでは省略される) // 条件) // 1. PV nodeではない // 2. Null moveをスキップするモード(ss->skipNullMove)ではない。(前の局面でnull moveしてない) // 3. 残り探索深さが2手以上 // 4. この局面の静的評価値 >= beta // 5. betaが詰み関係のスコアではない // 6. pos.non_pawn_material ← 将棋には関係なさげ // ↑これはPAWN以外の盤上の駒の価値を加算したもの。これが0だとPAWNとKINGしか残っていないということになる。 // たぶん終盤の寒い局面かどうかを判定しているのだと思われる。 if (!PvNode && !ss->skipNullMove && depth >= 2 * ONE_PLY && eval >= beta && abs(beta) < VALUE_MATE_IN_MAX_PLY && pos.non_pawn_material(pos.side_to_move())) { // この局面での指し手をMOVE_NULLとして次の局面に進めてみる ss->currentMove = MOVE_NULL; // Null move dynamic reduction based on depth // 残り探索深さに基づく、Null moveで減らす探索深さ // 減らす探索深さR = 3手 + 残り探索深さ /4 Depth R = 3 * ONE_PLY + depth / 4; // Null move dynamic reduction based on value // 評価値に基づく、Null moveで減らす探索深さ // 評価値 - 歩の中盤での価値 > beta // なら、さらに1手減らす。(これぐらい1手減らしてもbetaは下回らないとみなす) if (eval - PawnValueMg > beta) R += ONE_PLY; pos.do_null_move(st); // NullMoveを連続でするとおかしくなるのでそれは禁止しておく。 (ss + 1)->skipNullMove = true; nullValue = depth - R < ONE_PLY ? -qsearch : -search (ss + 1)->skipNullMove = false; pos.undo_null_move(); // betaを上回ることがわかった。 if (nullValue >= beta) { // Do not return unproven mate scores // 未検証の詰みのスコアを返さない // ※ 返してしまうとこのあとの詰みまでの手数の計算がおかしくなるので単にbetaを返す。 if (nullValue >= VALUE_MATE_IN_MAX_PLY) nullValue = beta; // 12手未満の残り探索深さなら、これをもってこのnodeの探索は終わり。 if (depth < 12 * ONE_PLY) return nullValue; // Do verification search at high depths // 大きな深さで検証の探索を行う。 // 12手以上の残り探索深さならもっと深くした探索で検証しなおす。 // null moveを連続でしないためのフラグをセットする ss->skipNullMove = true; Value v = search ss->skipNullMove = false; // それでもなおbetaを上回るならこのnodeの探索は終わり。 if (v >= beta) return nullValue; } else { // The null move failed low, which means that we may be faced with // some kind of threat. If the previous move was reduced, check if // the move that refuted the null move was somehow connected to the // move which was reduced. If a connection is found, return a fail // low score (which will cause the reduced move to fail high in the // parent node, which will trigger a re-search with full depth). // null moveがfaile lowだった。そのことは、我々が何かしらの脅威に // 直面しているということかも知れない。もし直前の指し手がreduce // (探索深さを減らす)されていたなら、そのnull moveをやり込めた指し手が // reduceされたその指し手と何らかの関連があるのかをチェックする。 // ※ これはallows()で行われる。allows()の実装を見よ。 // もし関連性が見つかったら、fail lowのスコアを返す。 // (これは、親ノードでfail highするようなreduceされた指し手を引き起こし、 // full depthでの再探索のトリガーとなる) threatMove = (ss + 1)->currentMove; // fail lowしたときのnull moveの次の相手番の指し手をthreatMoveと呼ぶ。 // これはなかなかに優れた手である可能性がある。 // これと1つ前の相手の手との関連性を調べる。1つ前の指し手によって、 // この次のthreatMoveが可能になったのであれば(2手一組の手順)、 // ここでnull move探索したのがおかしく、親ノードで再探索してもらうべき。 // そのためにalphaをそのまま返せば、親ノードではnull window探索が // fail highして再度念入りに探索される。 // 条件) // 1.残りDEPTHが5手未満 // 2.親nodeでreductionしている // 3.threatMoveがMOVE_NONEではない // 4.直前の相手の指し手と次の相手の指し手とは関連性がある。(allows()の実装を見よ) if (depth < 5 * ONE_PLY && (ss - 1)->reduction && threatMove != MOVE_NONE && allows(pos, (ss - 1)->currentMove, threatMove)) return alpha; } } // Step 9. ProbCut (skipped when in check) // If we have a very good capture (i.e. SEE > seeValues[captured_piece_type]) // and a reduced search returns a value much above beta, we can (almost) safely // prune the previous move. // Step 9. ProbCut (王手のときはskipされる) // もし非常に良い捕獲する指し手があるとして(例えば SEE値 > seeValues[直前で捕獲された駒種] ) // reduceされた探索がbetaを非常に超える値を返すとき、(ほぼ)安全に直前の指し手を // 枝刈りすることができる。 // 条件) // 1. PV nodeではない // 2. 残り探索深さが5手以上 // 3. Null Move探索をskipするモードではない(Null Moveの直後の局面ではない) // 4. betaが詰み探索に絡むスコアではない(詰み探索中ではない) if (!PvNode && depth >= 5 * ONE_PLY && !ss->skipNullMove && abs(beta) < VALUE_MATE_IN_MAX_PLY) { // いまのbetaより200点も上。 Value rbeta = beta + 200; // 4手浅く。 Depth rdepth = depth - ONE_PLY - 3 * ONE_PLY; assert(rdepth >= ONE_PLY); assert((ss - 1)->currentMove != MOVE_NONE); assert((ss - 1)->currentMove != MOVE_NULL); // MovePicekerにpos.captured_piece_type()を渡しているので、直前に取られた駒より大きな価値の駒を取る手のみを生成する。 MovePicker mp(pos, ttMove, History, pos.captured_piece_type()); CheckInfo ci(pos); while ((move = mp.next_move if (pos.legal(move, ci.pinned)) { // 前局面で取られた駒よりいい駒が取れるらしい駒取りの指し手で1手進めて ss->currentMove = move; pos.do_move(move, st, ci, pos.gives_check(move, ci)); // 少し浅い目の探索で、rbeta == beta + 200を上回るかをnull windowで調べる。 value = -search pos.undo_move(move); // 上回ったので探索終了。 if (value >= rbeta) return value; } } // Step 10. Internal iterative deepening (skipped when in check) // 多重反復深化(王手のときはskipする) 略称 : IID // // 残り探索深さが結構あるのに、置換表の最善手が取得できなかった時に // 浅い探索でのベストな指し手を調べる。(このあとの指し手のオーダリングに用いる) // // 条件) // 1. 残り探索深さがPV nodeであれば5手以上、non PV nodeであれば8手以上 // 2. ttMove(置換表にかかれている最善手)が登録されていなかった。 // 3. non PV nodeの場合、静的評価値 + 256 >= beta // → // 最善手のスコアがα値を超えない場合は、最善手が求まっても探索は何も早くならない。 // ところが、最善手のスコアがβ値を超える場合、その手でβ butできる。 // そこで、残り探索深さが結構あるときで、かつ、β値を超えそうな場合は、 // その手でβcutできて、いきなりこのnodeの探索を終了できる可能性があるので、こういう条件にしてある。(aki.さん) if (depth >= (PvNode ? 5 * ONE_PLY : 8 * ONE_PLY) && ttMove == MOVE_NONE && (PvNode || ss->staticEval + Value(256) >= beta)) { // 浅い範囲で探索しなおす。 // depth : 残り探索深さ // 今回の探索深さd = depth - 2手 - (non PV nodeに限り depth / 4) Depth d = depth - 2 * ONE_PLY - (PvNode ? DEPTH_ZERO : depth / 4); // 浅めの探索に移譲するので次のnodeでnull moveされて // それ以上精度が落ちるとこのnodeの指し手の参考にならない。 ss->skipNullMove = true; search ss->skipNullMove = false; // 探索したからには置換表にこの探索結果が書き込まれたはず // その最善手が書き込まれていればそれをttMoveに入れる tte = TT.probe(posKey); ttMove = tte ? tte->move() : MOVE_NONE; } moves_loop: // When in check and at SpNode search starts from here // 王手とSpNode(split node)探索のときはここから始まる。 // ※ ここ以下は、1手ずつ指し手を調べていくためのループ(が以下にある) // MOVE_NULLだと、piece_on(65) (※将棋だと82)をアクセスしていることになって、アクセス違反になるのだが…。 // → 違うわ。65に対するto_sq() == 1でアクセス違反にならないわ。 // 将棋のときMOVE_NULL = (1<<7)+1 == 129にすべきなのか…。なるほど。 // これしかし、1手前がMOVE_NULLのとき、Countermoves[pos.piece_on(1)][1]の指し手がCountermovesと // なってしまうが、こんなので本当にいいのだろうか.. Square prevMoveSq = to_sq((ss - 1)->currentMove); Move countermoves[] = { Countermoves[pos.piece_on(prevMoveSq)][prevMoveSq].first, Countermoves[pos.piece_on(prevMoveSq)][prevMoveSq].second }; MovePicker mp(pos, ttMove, depth, History, countermoves, ss); CheckInfo ci(pos); value = bestValue; // Workaround a bogus 'uninitialized' warning under gcc // '初期化されていない'という嘘のwarningがgccで出るのを回避 // 形勢が良くなってきているのかの判定 // 2手前の静的評価以上であるか、2手前の静的評価値がないか(王手がかかっていたなどの理由) // 今回の静的評価がない(同じく) improving = ss->staticEval >= (ss - 2)->staticEval || ss->staticEval == VALUE_NONE || (ss - 2)->staticEval == VALUE_NONE; // singular延長を行うノードであるかの判定 // 探索残り深さが十分残っていることが前提。 // ながとさんのコメント // http://d.hatena.ne.jp/mclh46/20110412/1302592124 // 評価値がlower boundな置換表の手だけで、singular extensionするらしい。 // Rybka 3がリバースエンジニアリングされて見つかったという黒い歴史があるらしい・・。 singularExtensionNode = !RootNode && !SpNode && depth >= 8 * ONE_PLY && ttMove != MOVE_NONE && !excludedMove // Recursive singular search is not allowed && (tte->bound() & BOUND_LOWER) && tte->depth() >= depth - 3 * ONE_PLY; // singular extensionする条件) // 1) root nodeではない // 2) split nodeではない(split nodeでやるとソースコードがくちゃくちゃになる?) // 3) 残り探索深さが8手以上 // 4) 置換表の指し手がMOVE_NONEではない(新規ノードではない) // 5) 指し手を除外しての探索中ではない // (excludedMoveが指定されている探索は、singular判定かそれに準ずるものなので、 // singular extensionと組み合わされと副作用がある) // 6) 置換表の指し手はBOUND_LOWERもしくはBOUND_EXACTである。 // (このnodeはもっといい値であることも期待できる) // 7) 置換表の指し手の探索時の深さが(いまの残り探索深さ-3)より大きい。 // (いまの残り探索深さとさほどかけ離れていない) // Step 11. Loop through moves // Loop through all pseudo-legal moves until no moves remain or a beta cutoff occurs // Step 11. 生成したそれぞれの指し手について調べるループ // 指し手がすべて尽きるか、beta cutoffが生じるまで、 // すべての仮の合法手(開き王手や自殺手を含む)について調べるループ。 // MovePickerから1手ずつもらう。このnodeの指し手がなくなればwhileループから抜ける。 while ((move = mp.next_move { assert(is_ok(move)); // このnodeで除外すべき指し手であるならskip if (move == excludedMove) continue; // At root obey the "searchmoves" option and skip moves not listed in Root // Move List, as a consequence any illegal move is also skipped. In MultiPV // mode we also skip PV moves which have been already searched. // root nodeでは"searchmoves"オプションに従い、Root Move Listにリストされていない // 指し手をskipする必要があり、この処理の結果としていかなる非合法手もskipされる。 // MultiPVモードでは、我々はすでに探索したPVの指し手もskipする。 // ※ RootNodeでかつ、探索済み指し手であるか、合法手でなければskipする。 if (RootNode && !std::count(RootMoves.begin() + PVIdx, RootMoves.end(), move)) continue; // split nodeならば if (SpNode) { // Shared counter cannot be decremented later if move turns out to be illegal // 共有カウンターは、もし指し手が非合法と判明したときにはこのあとデクリメントしてはならない。 // ※ 合法手の数をカウントし、その合法手が0であれば詰みと判定するため。 // 自殺手など非合法手であるならskipする if (!pos.legal(move, ci.pinned)) continue; // 合法な指し手だったのでこのnodeで調べた合法な指し手の数のカウンターをインクリメント。 // splitPoint->moveCountが共有カウンター。moveCountはローカルカウンター。 // 以下の処理を非split nodeと共通化するため、このローカルカウンターのほうに値をコピーしてある。 moveCount = ++splitPoint->moveCount; // 共有カウンターのインクリメントが終わったのでmutexをunlock()しておく。 // このあとでまたMovePickerから指し手をもらう直前(このwhileループの末尾あたり)でlock()する splitPoint->mutex.unlock(); } else // 非split nodeであるなら単に合法手の数のカウンターをインクリメントするだけで良い。 // ※ 合法手であるかどうかはのちほど調べる。 ++moveCount; // root node用の処理 if (RootNode) { // このフラグはroot nodeの最初の指し手について調べるのを開始するとtrueになる。 Signals.firstRootMove = (moveCount == 1); // このスレッドがメインスレッドでかつ、探索開始時刻から3秒を超過しているならば if (thisThread == Threads.main() && Time::now() - SearchTime > 3000) sync_cout << "info depth " << depth / ONE_PLY << " currmove " << move_to_uci(move, pos.is_chess960()) << " currmovenumber " << moveCount + PVIdx << sync_endl; // RootNodeにおける現在探索中の指し手 // このmoveは将棋所で探索中の指し手として表示される。 } // 延長深さの初期化。 // ※ このあとの条件次第でこれを増やしていく。 ext = DEPTH_ZERO; // この指し手は、成りか駒を捕獲する指し手か? captureOrPromotion = pos.capture_or_promotion(move); // この指し手で王手になるのかどうか givesCheck = pos.gives_check(move, ci); // 評価値が大きく変わる可能性がある指し手 // 条件) 以下のいずれか // 1. 敵王に対して王手になる手 // 2. pawn pushの条件を満たしている // 3. キャスリングの指し手 dangerous = givesCheck || pos.passed_pawn_push(move) || type_of(move) == CASTLE; // Step 12. Extend checks // Step 12. 延長すべき王手 // 王手となる指し手でかつ、SEEの符号が0かプラスならば1手延長 if (givesCheck && pos.see_sign(move) >= 0) ext = ONE_PLY; // Singular extension search. If all moves but one fail low on a search of // (alpha-s, beta-s), and just one fails high on (alpha, beta), then that move // is singular and should be extended. To verify this we do a reduced search // on all the other moves but the ttMove, if result is lower than ttValue minus // a margin then we extend ttMove. // Singular延長探索。もし1つの指し手を除くすべての指し手で(alpha-s,beta-s)の // 探索でfail lowして、その1つの指し手は(alpha,beta)でfail highであるなら、 // この指し手はsingularであり、延長されるべきである。このことを確認するため、 // ttMove(置換表の指し手)を除く他のすべての指し手に対して(深さを)縮めた探索を行い、 // もし結果が(ttValue - マージン値)未満であればttMoveを延長する。 // 条件) // 1. singular extension nodeであるのか。(さきほどの判定条件) // 2. 指し手が置換表に載っていた指し手であるのか // 3. まだこの段階では延長が決定していない指し手なのか。(王手でSEE>=0などではないけどいいかも知れない指し手を対象としたい) // 4. 合法な指し手か // 5. 置換表の指し手のスコアが詰みなどに絡むスコアではない if (singularExtensionNode && move == ttMove && !ext && pos.legal(move, ci.pinned) && abs(ttValue) < VALUE_KNOWN_WIN) { assert(ttValue != VALUE_NONE); // aki.さんによるコメント // http://d.hatena.ne.jp/ak11/20120722 // 置換表の指し手を探索する前に、置換表の指し手がSingularかどうかを深さを減らした探索で判定して、 // Singularだったら1手延長、という感じ。 // depth/2でsearch // ttValue = 置換表に書かれていた値 // 現在の指し手moveを除外して、浅い深さで調べ、その最大値が置換表の値 - depthを上回らないなら、 // この置換表の指し手は断トツで良いと判断できる。 // ToDo: depth引くのでいいの?これもう少し何らかの調整が要るのでは…。 // StockfishはONE_PLY == 2の実装では、残り深さ6(depth = 12)においてこのマージン値は12。 // この値のままだと、将棋だとほとんどがsingular扱いになってしまう。 // この値でnull window探索 Value rBeta = ttValue - int(depth); // この置換表の指し手を除外して浅い探索深さ(depth /2)で探索 ss->excludedMove = move; // null windowなのでnull moveとは相性が悪いので次のnodeでnull windowはしないる ss->skipNullMove = true; value = search ss->skipNullMove = false; ss->excludedMove = MOVE_NONE; // fail lowしたので延長を確定 if (value < rBeta) ext = ONE_PLY; } // Update current move (this must be done after singular extension search) // 現在の指し手を更新する (これは、singular延長探索のあと行われるべきである) // 残り探索深さ = 現在の残り探索深さ - 1手 + 上で決めた延長手数(1手 or 0手) newDepth = depth - ONE_PLY + ext; // Step 13. Pruning at shallow depth (exclude PV nodes) // Step 13. 浅い深さで枝刈りする (PV nodeは除外する) // 条件) // 1. PV nodeではない // 2. 捕獲する手や成る手ではない // 3. 王手がかかっていない // 4. bestValueが詰まされる値ではない if (!PvNode && !captureOrPromotion && !inCheck && !dangerous /* && move != ttMove Already implicit in the next condition */ && bestValue > VALUE_MATED_IN_MAX_PLY) { // Move count based pruning // 指し手生成カウントに基づく枝刈り // 以下の条件を満たしたらこの指し手についてはskipする。 // 条件) // 1. 残り探索深さが16手未満 // 2. 生成した指し手数カウント >= FutilityMoveCounts[2手前から評価値がよくなっているか][depth] // そのnodeでの生成数が多いと途中でこの手について調べることをリタイアする確率up // 3a. 次の指し手が脅威の指し手(threatMove)ではない。(threatMoveの条件はこのソースコードの上のほうを見ること) // 3b. 次の指し手が脅威の指し手(threatMove)であるとして、この指し手がthreatMoveの反駁手になっていない。 // ※ この3a.,3b.はOR条件 if (depth < 16 * ONE_PLY && moveCount >= FutilityMoveCounts[improving][depth] && (!threatMove || !refutes(pos, move, threatMove))) { // split nodeならば指し手生成のwhileループの末尾直前にsplitPoint->mutex.lock() // しないといけない決まりなのでここでやる。 if (SpNode) splitPoint->mutex.lock(); // この指し手をskipする continue; } // reductionに基づくdepth // 1. improving = 2手前から評価値が向上しているか // 2. depth = 残り探索深さ // 3. moveCount = このnodeで生成済みの指し手の数 // の3つから残り探索手数を縮める。 // ※ reductionする手数は、上の3つのパラメーターによる関数(数学的な意味で)となっている。 predictedDepth = newDepth - reduction // Futility pruning: parent node // Futility枝刈り : 親node // reduction適用後の残り探索深さが7手未満 if (predictedDepth < 7 * ONE_PLY) { // futility値 = 静的評価値 + futility_margin(reduction適用後の残り探索深さ) // + 128 + この指し手による駒の位置が変化したことにより得られるゲイン。 futilityValue = ss->staticEval + futility_margin(predictedDepth) + Value(128) + Gains[pos.moved_piece(move)][to_sq(move)]; // futilityValueがalphaを以下であれば、 // この指し手は頑張ってもalphaを超えそうにないのでskipしてしまう。 if (futilityValue <= alpha) { bestValue = std::max(bestValue, futilityValue); if (SpNode) { splitPoint->mutex.lock(); // split nodeであり、bestValueを更新しているならば共有データのほうのbestValueも更新してやる。 if (bestValue > splitPoint->bestValue) splitPoint->bestValue = bestValue; } continue; } } // Prune moves with negative SEE at low depths // 少ない残り深さにおいて負のSEEをもつ指し手を枝刈り // reduction適用後の残り探索深さが4手未満でSEEの符号がマイナスであるなら // この指し手について調べるのをスキップ。 if (predictedDepth < 4 * ONE_PLY && pos.see_sign(move) < 0) { if (SpNode) splitPoint->mutex.lock(); continue; } } // Check for legality only before to do the move // この指し手で局面を進める前に合法性だけチェックを行う // ※ 自殺手であるかなどはpos.legal()でチェックされる if (!RootNode && !SpNode && !pos.legal(move, ci.pinned)) { // 合法じゃなかったのでmoveCountを1減らす // root nodeでは事前に全合法手を生成しているのでこのチェックは不要。 // split nodeでは上でこのチェックをしているのでこのチェックはすでにやってある。 // split nodeでもここでやればいいと思うが、そうすると共有データの更新が複雑になるのか…。 moveCount--; continue; } // PV nodeにおける最初の指し手ならばpvMoveをtrueにする。 // root nodeにおいては前回のiterationの最善手がこれに相当する。 pvMove = PvNode && moveCount == 1; // 現在の探索中の指し手をStack::currentMoveにセットする。 // do_move()で局面を進めたときに1手前の局面での指し手を調べたりするためにこの処理が必要。 ss->currentMove = move; // split nodeでなく、捕獲・成りではなく、quietCountが64未満であるなら // quietsSearched[]に現在の指し手を格納していく。 // 調べた指し手を記録しておいて、βcutしたときにスコアリングのために // それらの指し手に加点/減点するためのもの。 if (!SpNode && !captureOrPromotion && quietCount < 64) quietsSearched[quietCount++] = move; // Step 14. Make the move // Step 14. この指し手で局面を進める pos.do_move(move, st, ci, givesCheck); // Step 15. Reduced depth search (LMR). If the move fails high will be // re-searched at full depth. // Step 15. 残り探索深さを減らす。(LMR) もし、この指し手がfail highを起こしたら // full depth(探索深さを減らしていない深さ)で探索しなおす。 // 条件) // 1. 探索残り深さが3手以上 // 2. 指し手がPVの指し手(PV nodeの第1手目)ではない。 // 3. 指し手が捕獲と成りではない // 4. 指し手が置換表の指し手ではない // 5. 指し手がKiller[0],[1]ではない。 if (depth >= 3 * ONE_PLY && !pvMove && !captureOrPromotion && move != ttMove && move != ss->killers[0] && move != ss->killers[1]) { // ss->reductionはこのnodeで減らす探索深さ ss->reduction = reduction // PV nodeでもcutNodeでもないならさらに1手減らす if (!PvNode && cutNode) ss->reduction += ONE_PLY; // 駒は打ったあとであるから、Dropであってもto_sq(move)にはすでに駒が打たれており、 // 以下のpiece_on()の書き方で問題ない。 // PV nodeかcutNodeの場合、 // Historyテーブルを見て、マイナスのスコアのものだけ1/2手だけ減らす。 else if (History[pos.piece_on(to_sq(move))][to_sq(move)] < 0) ss->reduction += ONE_PLY / 2; if (move == countermoves[0] || move == countermoves[1]) ss->reduction = std::max(DEPTH_ZERO, ss->reduction - ONE_PLY); // 残り探索深さは、newDepthからここで計算したss->reduction分だけ引き算したもの。 // ただし、1手未満になったら1手は探索するものとする。 Depth d = std::max(newDepth - ss->reduction, ONE_PLY); // split nodeであるなら、現在の(並列探索中の)alpha値を用いたほうがより正確である if (SpNode) alpha = splitPoint->alpha; // PVの指し手ではないのでnull move探索で探索してalphaを超えるかどうかを調べる。 value = -search // reductionして探索した結果、fail highになっているならfull depthで探索しなおす // null windowなのでvalue > alphaであるならfail highである。 doFullDepthSearch = (value > alpha && ss->reduction != DEPTH_ZERO); ss->reduction = DEPTH_ZERO; } else doFullDepthSearch = !pvMove; // pvMoveならば以下でFull Depth Searchを行わない。 // ※ pvMoveはPVnodeの第一手目かどうかのフラグ。 // Step 16. Full depth search, when LMR is skipped or fails high // Step 16. LMRがスキップされたときやfail highだった場合にfull depthで探索する if (doFullDepthSearch) { // split nodeならalpha値が更新されているかも知れないので共有データからもらう。 if (SpNode) alpha = splitPoint->alpha; // 残り探索深さが // 1手未満ならDEPTH_ZEROで(alpha,alpha+1)にて静止探索。 // 1手以上ならその残り探索深さで(alpha,alpha+1)にて静止探索。 value = newDepth < ONE_PLY ? givesCheck ? -qsearch : -qsearch : -search } // Only for PV nodes do a full PV search on the first move or after a fail // high, in the latter case search only if value < beta, otherwise let the // parent node to fail low with value <= alpha and to try another move. // PV nodeでだけ、第一手かfail highのあとfull PV探索する。後者(fail highのあと)の場合、 // value < betaのときだけに限る。さもなくば、親nodeに、value <= alphaでfail lowさせるか、 // 他の指し手を試させる。 if (PvNode && (pvMove || (value > alpha && (RootNode || value < beta)))) // 残り探索深さが // 1手未満ならDEPTH_ZEROで(alpha,beta)にて静止探索。 // 1手以上ならその残り探索深さで(alpha,beta)にて静止探索。 value = newDepth < ONE_PLY ? givesCheck ? -qsearch : -qsearch : -search // Step 17. Undo move // Step 17. 局面を戻す。 pos.undo_move(move); assert(value > -VALUE_INFINITE && value < VALUE_INFINITE); // Step 18. Check for new best move // Step 18. 新しいbest moveをチェックする // split nodeであるならalphaとbestValueが更新されているかも知れないので // それをもらう。 if (SpNode) { // split nodeであれば、もうそろそろwhileループの終端なので // 共有データを取得することだしここでlockしておく。 splitPoint->mutex.lock(); bestValue = splitPoint->bestValue; alpha = splitPoint->alpha; } // Finished searching the move. If Signals.stop is true, the search // was aborted because the user interrupted the search or because we // ran out of time. In this case, the return value of the search cannot // be trusted, and we don't update the best move and/or PV. // 指し手の探索を終了させる。もし、Signals.stopがtrueであるなら、探索は停止される。 // なぜなら、ユーザーが探索を中断したからであるか、または探索時間のための時間を使いきったからである。 // この場合、探索の返し値は信頼できる値ではないので、この場合、best move(最善手)やPVを更新すべきではない。 if (Signals.stop || thisThread->cutoff_occurred()) return value; // To avoid returning VALUE_INFINITE // ToDo : おや…splitPoint->mutex.unlock()は要らないのか? if (RootNode) { // Root nodeでの指し手のなかから、いま探索したばかりの指し手に関してそれがどこにあるかをfind()で探し、 // この指し手に付随するPV(最善応手列)を置換表から取り出して更新しておく。 // このfind()が失敗することは想定していない。 RootMove& rm = *std::find(RootMoves.begin(), RootMoves.end(), move); // PV move or new best move ? // これがPVの指し手であるか、もしくは(スコアを更新した)新しいbest moveであるか if (pvMove || value > alpha) { // root nodeでの新しいスコアを更新。 // rmは参照なので、RootMovesの当該エントリーのscore値が更新される。 rm.score = value; // 置換表からPVをRootMoveのメンバーであるpvという配列に取り出して保存しておく。 rm.extract_pv_from_tt(pos); // We record how often the best move has been changed in each // iteration. This information is used for time management: When // the best move changes frequently, we allocate some more time. // 我々はそれぞれのiterationにおいてどれくらいの頻度で最善手が変更されたかを記録する。 // この情報は思考時間制御に使われる。最善手が頻繁に変化しているとき、いくらか多く時間を割り当てる。 if (!pvMove) ++BestMoveChanges; } else // All other moves but the PV are set to the lowest value, this // is not a problem when sorting becuase sort is stable and move // position in the list is preserved, just the PV is pushed up. // PVの指し手以外の他のすべての指し手は最小スコア値にセットされるが、 // しかしこれはソートするときに問題とはならない。なぜならソートは安定ソートであり、 // リストのなかの指し手の位置は保存され、PVの指し手が押し上げられるだけである。 // ※ 訳注 : 一番上に来るの意味か。 // ※ この指し手はpvMoveの指し手ではないし、か、alpha値を更新しなかった指し手であるから // スコアは全く信頼にならない。(alpha値を超えないという事実がわかっただけ。) // そこでマイナス∞扱いにしておく。 // ToDo : これvalueを突っ込んだら何かまずいのか?安定ソートに余分に時間がかかるから // 損だという判断か? rm.score = -VALUE_INFINITE; } // valueがalpha,best valueを更新するのか? if (value > bestValue) { bestValue = SpNode ? splitPoint->bestValue = value : value; if (value > alpha) { bestMove = SpNode ? splitPoint->bestMove = move : move; if (PvNode && value < beta) // Update alpha! Always alpha < beta alpha = SpNode ? splitPoint->alpha = value : value; else { assert(value >= beta); // Fail high // betaを上回ったのでbeta cutoffが確定した。 // split nodeであればフラグを立てて他の探索スレッドにも通知。 if (SpNode) splitPoint->cutoff = true; break; } } } // Step 19. Check for splitting the search // Step 19. 探索のsplit(並列化)のチェック // 条件) // 1. split nodeではない // 2. 残り探索深さがオプションで設定されたminimumSplitDepth以上 // 3. 利用可能なスレッドが存在する // 4. このスレッドのsplit pointの個数がMAX_SPLITPOINTS_PER_THREAD以下である。 if (!SpNode && depth >= Threads.minimumSplitDepth && Threads.available_slave(thisThread) && thisThread->splitPointsSize < MAX_SPLITPOINTS_PER_THREAD) { assert(bestValue < beta); thisThread->split depth, threatMove, moveCount, &mp, NT, cutNode); // ここではまだ探索は終了していない。他のスレッドがこの探索に参加しはじめたというだけ。 if (bestValue >= beta) break; } } // split nodeであるならすべての指し手についてのチェックが終わったので // これにて自分の仕事は終わりであり、単にbestValueを返しておく。 if (SpNode) return bestValue; // Step 20. Check for mate and stalemate // All legal moves have been searched and if there are no legal moves, it // must be mate or stalemate. Note that we can have a false positive in // case of Signals.stop or thread.cutoff_occurred() are set, but this is // harmless because return value is discarded anyhow in the parent nodes. // If we are in a singular extension search then return a fail low score. // A split node has at least one move, the one tried before to be splitted. // Step 20. 詰みとステイルメイトのチェック // すべての合法な指し手は探索されたが、もしそこに合法な指し手がないとしたら、 // それは詰みかもしくはステイルメイトである。Signal.stop(ユーザーからの停止信号)や // thread.cutoff_occured() (split nodeで他のスレッドによる中断要求)の場合においては // false positive(やりすぎ?)でありうることを心に留めておくべきであるが、 // しかしこれは親nodesでどのみち破棄される値なので(ここでまともに計算するのは)害があるだけである。 // また、singular延長をしているなら、fail lowしたスコアを返す。 // あと、split nodeは少なくとも一つの指し手を持っているし、その指し手はsplitされる前に // 試されているものとする。 // 有効な指し手が1手もなかった。(将棋だと詰み) if (!moveCount) // 除外している指し手があるならば、その指し手での評価値はαであろうから、それを返す。 // 王手がかかっている→回避手がなかったということで詰みなので詰みのスコア(mated_in(ss->ply)を返す。 // チェスだと王手がかかっていないなら、ステイルメイトであり、これは引き分け扱い。 return excludedMove ? alpha : inCheck ? mated_in(ss->ply) : DrawValue[pos.side_to_move()]; // ※ 将棋だと王手がかかっていようがいまいが合法な指し手がゼロ = 詰みなので詰みスコアを返しておくべき。 // If we have pruned all the moves without searching return a fail-low score // すべての指し手を探索せずに枝刈りしてしまったのならばfail low扱いしてalphaを返す。 if (bestValue == -VALUE_INFINITE) bestValue = alpha; // 置換表に値を格納。 // value_to_ttは詰みのスコアの場合、現在の局面からの手数を表す数値に変換するためのヘルパー関数。 // beta cutしているならBOUND_LOWER(他にもっといい値を記録する指し手があるかも知れないので) // PvNodeでかつbestMoveが具体的な指し手として存在するなら、BOUND_EXACT // non PV nodeとか、bestMoveがない(適当な見積もりで枝刈りした場合など)は、この状態 // non PVだと、null windowで探索するので、仮にそれが[α-1,α]の範囲であれば、 // αを超えるか超えないかしかわからない。αを下回る値が返ってきたなら、このnodeの真の値は、 // その値以下であるから、BOUND_UPPER、また、αを上回る値が返ってきたら、このnodeの真の値は、 // その値以上であろうから、BOUND_LOWERである。 // このように、non PVにおいては、BOUND_UPPER、BOUND_LOWERしか存在しない。(aki.さん) TT.store(posKey, value_to_tt(bestValue, ss->ply), bestValue >= beta ? BOUND_LOWER : PvNode && bestMove ? BOUND_EXACT : BOUND_UPPER, depth, bestMove, ss->staticEval); // Quiet best move: update killers, history and countermoves // Quiet(駒取りや成りではない指し手)のbest move : killer,historyとcounterの指し手を更新する。 // 条件) // 1. bestValueがbetaを上回る素晴らしい手であった。 // 2. bestMoveはQuietな手(捕獲、成り、王手ではない) if (bestValue >= beta && !pos.capture_or_promotion(bestMove) && !inCheck) { if (ss->killers[0] != bestMove) { // killerを入れ替える。 ss->killers[1] = ss->killers[0]; ss->killers[0] = bestMove; } // Increase history value of the cut-off move and decrease all the other // played non-capture moves. // このbeta cutoffを起こした指し手のhistoryの値を増加させ、 // 捕獲しないここで生成した他の指し手に対して値を減少させる。 // depthの2乗をボーナスとして加算 Value bonus = Value(int(depth) * int(depth)); // ※ 将棋では、ここ、moved_piece()だと駒打ちにうまく対処できないので、そのへんを考慮する必要がある。 History.update(pos.moved_piece(bestMove), to_sq(bestMove), bonus); // bestMove以外の指し手(ここまで生成した残りの指し手はquietsSearched[0]~[quietCount-2]に格納されている) // についてhistoryの値を減点する。 for (int i = 0; i < quietCount - 1; ++i) { Move m = quietsSearched[i]; History.update(pos.moved_piece(m), to_sq(m), -bonus); } // ひとつ前の指し手がMOVE_NONEでないなら、その指し手に対するカウンター手として // 今回の指し手を登録しておく。 if (is_ok((ss - 1)->currentMove)) Countermoves.update(pos.piece_on(prevMoveSq), prevMoveSq, bestMove); // 現局面ではprevMoveの指し手は完了しているのでprevMoveの移動先であるprevMoveSqにはすでに駒が置かれている。 // ※ 駒打ちであっても同様。 // そして、現局面はbestMoveでdo_move()する前の局面であるから、prevMoveSqにある駒が捕獲されてしまっている // ことについては考慮に入れなくて良い。 } assert(bestValue > -VALUE_INFINITE && bestValue < VALUE_INFINITE); return bestValue; } // qsearch() is the quiescence search function, which is called by the main // search function when the remaining depth is zero (or, to be more precise, // less than ONE_PLY). // qsearch()は、静止探索関数で、探索メイン関数(seach)から残り探索深さがゼロのときに呼び出される。 // (正確に言うなら、残り探索深さがONE_PLY未満のときに呼び出される) template Value qsearch(Position& pos, Stack* ss, Value alpha, Value beta, Depth depth) { const bool PvNode = (NT == PV); assert(NT == PV || NT == NonPV); assert(InCheck == !!pos.checkers()); assert(alpha >= -VALUE_INFINITE && alpha < beta && beta <= VALUE_INFINITE); assert(PvNode || (alpha == beta - 1)); assert(depth <= DEPTH_ZERO); StateInfo st; const TTEntry* tte; Key posKey; Move ttMove, move, bestMove; Value bestValue, value, ttValue, futilityValue, futilityBase, oldAlpha; bool givesCheck, evasionPrunable; Depth ttDepth; // To flag BOUND_EXACT a node with eval above alpha and no available moves // BOUND_EXACTフラグのため、alpha値を超える評価値で利用可能な指し手がないnodeについて if (PvNode) oldAlpha = alpha; ss->currentMove = bestMove = MOVE_NONE; // 1手進める ss->ply = (ss - 1)->ply + 1; // Check for an instant draw or maximum ply reached // 最大手数に達した場合、引き分けスコアとみなす。 if (pos.is_draw() || ss->ply > MAX_PLY) return DrawValue[pos.side_to_move()]; // Decide whether or not to include checks, this fixes also the type of // TT entry depth that we are going to use. Note that in qsearch we use // only two types of depth in TT: DEPTH_QS_CHECKS or DEPTH_QS_NO_CHECKS. // 王手を含むか否かを決定する。これは、我々が使おうとしている置換表のエントリーの深さ // の種類を修正する。qsearchにおいて我々は置換表における2つの探索深さ、 // DEPTH_QS_CHECKS か DEPTH_QS_NO_CHECKS のみを用いることに注意。 // 王手がかかっているか残り探索深さが0以上であればDEPTH_QS_CHECKS(0手)、 // さもなくばDEPTH_QS_NO_CHECKS(-2 == -ONE_PLY)手とみなす。 ttDepth = InCheck || depth >= DEPTH_QS_CHECKS ? DEPTH_QS_CHECKS : DEPTH_QS_NO_CHECKS; // Transposition table lookup // 置換表の参照 posKey = pos.key(); tte = TT.probe(posKey); // 置換表の指し手 ttMove = tte ? tte->move() : MOVE_NONE; // 置換表上のスコア ttValue = tte ? value_from_tt(tte->value(), ss->ply) : VALUE_NONE; // 置換表のスコアが信用に足るならそのまま返す。 // 条件) // 1. 置換表にエントリーがあった // 2. 置換表のエントリーのdepthが今回の残り探索depth以上である // 3. 置換表のエントリーのスコアがVALUE_NONEではない。(置換表のアクセス競合のときにのみこの値になりうる) // 4. PV nodeのとき // 置換表のスコアのboundがBOUND_EXACTなら信用に足るので置換表の指し手をそのまま返す // non PV nodeのとき // 置換表のスコアのboundがBOUND_LOWERでttValue >= betaであればttValueでbeta cutはできるであろうからttValueを返す。 // 置換表のスコアのboundがBOUND_UPPERでttValue < betaであればどう頑張ってもttValueではbetaを超えないのでttValueを返す。 if (tte && tte->depth() >= ttDepth && ttValue != VALUE_NONE // Only in case of TT access race && (PvNode ? tte->bound() == BOUND_EXACT : ttValue >= beta ? (tte->bound() & BOUND_LOWER) : (tte->bound() & BOUND_UPPER))) { ss->currentMove = ttMove; // Can be MOVE_NONE return ttValue; } // Evaluate the position statically // 局面の静的評価 // 王手がかかっているなら、この局面では評価しない if (InCheck) { ss->staticEval = VALUE_NONE; bestValue = futilityBase = -VALUE_INFINITE; } else { // 王手はかかっていない if (tte) { // --- 置換表にエントリーが登録されていた場合 // Never assume anything on values stored in TT // 置換表に格納されている値に関して何も仮定しない。 // staticEvalに値がセットされていないなら評価関数を呼び出してしまう。 if ((ss->staticEval = bestValue = tte->eval_value()) == VALUE_NONE) ss->staticEval = bestValue = evaluate(pos); // Can ttValue be used as a better position evaluation? // ttValueはふさわしい局面の評価値として使えるのか? // ttValueがVALUE_NONEではなかったとしても、bestValueの値としてふさわしいかどうか。 // 1) 置換表のboundがBOUND_LOWER/BOUND_EXACTでttValue > bestValueなら、ttbestValueはbestValueより大きな値であろうと言える。 // 2) 置換表のboundがBOUND_UPPER/BOUND_EXACTでttValue < bestValueなら、ttbestValueはbestValueより小さな値であろうと言える。 if (ttValue != VALUE_NONE) if (tte->bound() & (ttValue > bestValue ? BOUND_LOWER : BOUND_UPPER)) bestValue = ttValue; } else // --- 置換表にエントリーが登録されていない場合 // 王手もかかっていないし、置換表にも値はないので評価関数を呼び出してしまう。 ss->staticEval = bestValue = evaluate(pos); // Stand pat. Return immediately if static value is at least beta // Stand patである。静的評価値が少なくともbeta以上であるなら即座に返る。 // bestValueがこの時点でbetaを上回るなら即座に帰る。 if (bestValue >= beta) { // 置換表にエントリーがなかったのであれば、 // このnodeについて静止探索はしていないが、bestValueよりはいい値であろうから、BOUND_LOWERにして置換表に書き出しておく。 if (!tte) TT.store(pos.key(), value_to_tt(bestValue, ss->ply), BOUND_LOWER, DEPTH_NONE, MOVE_NONE, ss->staticEval); return bestValue; } // PV nodeでかつbestValueでalphaを更新できるならalphaを更新しておく。 if (PvNode && bestValue > alpha) alpha = bestValue; // futility枝刈りのため、残り手数ではbestValue + 128を超えないと仮定する。 futilityBase = bestValue + Value(128); } // Initialize a MovePicker object for the current position, and prepare // to search the moves. Because the depth is <= 0 here, only captures, // queen promotions and checks (only if depth >= DEPTH_QS_CHECKS) will // be generated. // 現在の局面のためにMovePickerのobjectを初期化し、探索の指し手の準備をする。 // なぜならdepthが0以下であるなら、捕獲する指し手のみとクイーンの成りと、 // 王手生成(これはdepth >= DEPTH_QS_CHECKSのときのみ)がされるから。 // ※ to_sq((ss - 1)->currentMoveは、直前の指し手での移動先の升を意味している。 MovePicker mp(pos, ttMove, depth, History, to_sq((ss - 1)->currentMove)); CheckInfo ci(pos); // Loop through the moves until no moves remain or a beta cutoff occurs // 残りの指し手がなくなるか、beta cutoffが生じるまでループする。 // ※ next_move // falseとなっている。 while ((move = mp.next_move { assert(is_ok(move)); givesCheck = pos.gives_check(move, ci); // Futility pruning if (!PvNode && !InCheck && !givesCheck && move != ttMove && type_of(move) != PROMOTION && futilityBase > -VALUE_KNOWN_WIN && !pos.passed_pawn_push(move)) { futilityValue = futilityBase + PieceValue[EG][pos.piece_on(to_sq(move))] + (type_of(move) == ENPASSANT ? PawnValueEg : VALUE_ZERO); // ※ PieceValueは、後手の駒に対しても正の値を返す。 // ToDo : ここなぜ[EG]なのか? if (futilityValue < beta) { bestValue = std::max(bestValue, futilityValue); continue; } // Prune moves with negative or equal SEE and also moves with positive // SEE where capturing piece loses a tempo and SEE < beta - futilityBase. if (futilityBase < beta && pos.see(move, beta - futilityBase) <= 0) { bestValue = std::max(bestValue, futilityBase); continue; } } // Detect non-capture evasions that are candidate to be pruned // 枝刈りされる候補である捕獲しない回避手を検出 evasionPrunable = InCheck && bestValue > VALUE_MATED_IN_MAX_PLY && !pos.capture(move) && !pos.can_castle(pos.side_to_move()); // ここ、駒打ちの場合でもまだ駒は打っていないのでpos.capture()での判定は正しい。 // Don't search moves with negative SEE values // 負のSEE値の指し手は探索しない。 if (!PvNode && (!InCheck || evasionPrunable) && move != ttMove && type_of(move) != PROMOTION && pos.see_sign(move) < 0) continue; // Check for legality only before to do the move // 移動させる前にのみ合法手かどうかをチェックする if (!pos.legal(move, ci.pinned)) continue; ss->currentMove = move; // Make and search the move pos.do_move(move, st, ci, givesCheck); value = givesCheck ? -qsearch : -qsearch pos.undo_move(move); assert(value > -VALUE_INFINITE && value < VALUE_INFINITE); // Check for new best move if (value > bestValue) { bestValue = value; if (value > alpha) { if (PvNode && value < beta) // Update alpha here! Always alpha < beta { alpha = value; bestMove = move; } else // Fail high { TT.store(posKey, value_to_tt(value, ss->ply), BOUND_LOWER, ttDepth, move, ss->staticEval); return value; } } } } // All legal moves have been searched. A special case: If we're in check // and no legal moves were found, it is checkmate. // すべての合法な指し手は探索された。特殊なケース : もし王手されていて、 // 合法な指し手がなければ、これはチェックメイト(詰み)である。 // 王手されていて、bestValueが初期化したときの値から更新されていない(=合法な指し手なし) if (InCheck && bestValue == -VALUE_INFINITE) return mated_in(ss->ply); // Plies to mate from the root // rootから詰み局面までの手数 // oldAlphaはPV nodeでこのqsearchが呼び出されたときのalphaの値。 // ここから更新があったのかどうかが問題。 TT.store(posKey, value_to_tt(bestValue, ss->ply), PvNode && bestValue > oldAlpha ? BOUND_EXACT : BOUND_UPPER, ttDepth, bestMove, ss->staticEval); assert(bestValue > -VALUE_INFINITE && bestValue < VALUE_INFINITE); return bestValue; } // value_to_tt() adjusts a mate score from "plies to mate from the root" to // "plies to mate from the current position". Non-mate scores are unchanged. // The function is called before storing a value to the transposition table. // value_to_tt()は、詰みのスコアを「探索開始局面からの詰みまでの手数」から // 「現在の局面からの詰みまでの手数」に調整する。詰みでないスコアならば変更されない。 // この関数は置換表に値を格納する前に呼び出される。 Value value_to_tt(Value v, int ply) { assert(v != VALUE_NONE); return v >= VALUE_MATE_IN_MAX_PLY ? v + ply : v <= VALUE_MATED_IN_MAX_PLY ? v - ply : v; } // value_from_tt() is the inverse of value_to_tt(): It adjusts a mate score // from the transposition table (where refers to the plies to mate/be mated // from current position) to "plies to mate/be mated from the root". // value_from_tt()はvalue_to_tt()の逆である。これは置換表(現在の局面からの // 詰む/詰まされる手数について書いてある)の詰みのスコアを探索開始局面からの // 詰む/詰まされる手数に調整する。 Value value_from_tt(Value v, int ply) { return v == VALUE_NONE ? VALUE_NONE : v >= VALUE_MATE_IN_MAX_PLY ? v - ply : v <= VALUE_MATED_IN_MAX_PLY ? v + ply : v; } // allows() tests whether the 'first' move at previous ply somehow makes the // 'second' move possible, for instance if the moving piece is the same in // both moves. Normally the second move is the threat (the best move returned // from a null search that fails low). // allows()は1手前の局面での指し手'first'が何とかして、'second'の指し手を可能にするかを // テストする。例えば、動かした駒が両方の指し手において同一であるだとか。 // 通例、secondの指し手は脅威である。(fail lowしたnull searchによって返された最善手である) // ※ firstを指さないとsecondが指せないケースであるかをテストする。 bool allows(const Position& pos, Move first, Move second) { assert(is_ok(first)); assert(is_ok(second)); assert(color_of(pos.piece_on(from_sq(second))) == ~pos.side_to_move()); assert(type_of(first) == CASTLE || color_of(pos.piece_on(to_sq(first))) == ~pos.side_to_move()); Square m1from = from_sq(first); Square m2from = from_sq(second); Square m1to = to_sq(first); Square m2to = to_sq(second); // The piece is the same or second's destination was vacated by the first move // We exclude the trivial case where a sliding piece does in two moves what // it could do in one move: eg. Ra1a2, Ra2a3. // (1つ目と2つ目の指し手で)駒が同一(2つ目の指し手の移動先が1つ目の指し手の移動元)である、すなわち、 // もしくは2つ目の指し手の移動先が一つ目の指し手によって空けられた。 // 我々は遠方駒が2手かけて移動した(例えばRa1a2,Ra2a3というような1手)自明のケースを除外する。 // ※ 飛車を途中で停留させただけのような1手でいけるところを2手かけて行ったケースは意味がないので // 除外するの意味。 // secondの移動先がfirstの移動元であるか、もしくは // firstの移動先がsecondの移動元でかつfirstの移動元、移動先、secondの移動先が一直線上にならんでいない。 if (m2to == m1from || (m1to == m2from && !aligned(m1from, m2from, m2to))) return true; // 37銀~46銀みたいなのはOk。 // ※ ToDo : このコードおかしいのでは。 // m2to == m1fromだと、同じ駒を元の位置に戻す指し手も含まれてしまう。 // (m2to == m1from && m2from!=m1to )みたいなコードであるべきではないか。 // Second one moves through the square vacated by first one // firstの指し手によって空けられた升を経由するsecondの指し手が移動可能となった。 // ※ 歩がどいたために飛車の横移動が可能になった、みたいなケース。 // secondの指し手の移動した線分上にfirstの指し手の移動元が含まれている。 if (between_bb(m2from, m2to) & m1from) return true; // Second's destination is defended by the first move's piece // secondの指し手の行き先が、firstの指し手の駒で守られている。 // m1att = firstの移動先の升から、firstの移動先の駒の利き。ただし、secondの移動元の駒は除外して考える。 // このときm2fromを除外しているのは、このあと、開き王手判定をするため。 Bitboard m1att = pos.attacks_from(pos.piece_on(m1to), m1to, pos.pieces() ^ m2from); // m1attがsecondの移動先に利いていれば。 if (m1att & m2to) return true; // Second move gives a discovered check through the first's checking piece // secondの指し手はfirstの指の手が王手駒となる開き王手である。 // firstの駒の移動元においてsecondの駒を除外すれば利きが敵玉に到達している。 if (m1att & pos.king_square(pos.side_to_move())) { assert(between_bb(m1to, pos.king_square(pos.side_to_move())) & m2from); return true; } return false; } // refutes() tests whether a 'first' move is able to defend against a 'second' // opponent's move. In this case will not be pruned. Normally the second move // is the threat (the best move returned from a null search that fails low). // refutes()は、'first'の指し手が相手の'second'の指し手を防ぐことが可能かどうかをテストする。 // この場合、枝刈りされない。通例、後者の指し手は脅威(fail lowするnull searchから返される最善手)である。 bool refutes(const Position& pos, Move first, Move second) { assert(is_ok(first)); assert(is_ok(second)); Square m1from = from_sq(first); Square m2from = from_sq(second); Square m1to = to_sq(first); Square m2to = to_sq(second); // Don't prune moves of the threatened piece // 脅威駒の枝刈りはしない if (m1from == m2to) return true; // If the threatened piece has value less than or equal to the value of the // threat piece, don't prune moves which defend it. if (pos.capture(second) && (PieceValue[MG][pos.piece_on(m2from)] >= PieceValue[MG][pos.piece_on(m2to)] || type_of(pos.piece_on(m2from)) == KING)) { // Update occupancy as if the piece and the threat are moving Bitboard occ = pos.pieces() ^ m1from ^ m1to ^ m2from; Piece pc = pos.piece_on(m1from); // The moved piece attacks the square 'tto' ? if (pos.attacks_from(pc, m1to, occ) & m2to) return true; // Scan for possible X-ray attackers behind the moved piece Bitboard xray = (attacks_bb< ROOK>(m2to, occ) & pos.pieces(color_of(pc), QUEEN, ROOK)) | (attacks_bb // Verify attackers are triggered by our move and not already existing if (unlikely(xray) && (xray & ~pos.attacks_from return true; } // Don't prune safe moves which block the threat path if ((between_bb(m2from, m2to) & m1to) && pos.see_sign(first) >= 0) return true; return false; } // When playing with strength handicap choose best move among the MultiPV set // using a statistical rule dependent on 'level'. Idea by Heinz van Saanen. // 強さのhandicapつきでプレーしているとき、'level'に依存する統計的規則を用いて // MultiPV集合のなかからbest moveが選択される。 Move Skill::pick_move() { static RKISS rk; // PRNG sequence should be not deterministic for (int i = Time::now() % 50; i > 0; --i) rk.rand // RootMoves are already sorted by score in descending order int variance = std::min(RootMoves[0].score - RootMoves[PVSize - 1].score, PawnValueMg); int weakness = 120 - 2 * level; int max_s = -VALUE_INFINITE; best = MOVE_NONE; // Choose best move. For each move score we add two terms both dependent on // weakness, one deterministic and bigger for weaker moves, and one random, // then we choose the move with the resulting highest score. for (size_t i = 0; i < PVSize; ++i) { int s = RootMoves[i].score; // Don't allow crazy blunders even at very low skills if (i > 0 && RootMoves[i - 1].score > s + 2 * PawnValueMg) break; // This is our magic formula s += (weakness * int(RootMoves[0].score - s) + variance * (rk.rand if (s > max_s) { max_s = s; best = RootMoves[i].pv[0]; } } return best; } // uci_pv() formats PV information according to UCI protocol. UCI requires // to send all the PV lines also if are still to be searched and so refer to // the previous search score. // uci_pv()はUCIプロトコルに従ってPV情報を書式化する。UCIはすべての最善応手列を送ることを要求する。 // もし、依然として探索されているなら(探索中であるなら)、以前の探索スコアについてだ。 string uci_pv(const Position& pos, int depth, Value alpha, Value beta) { std::stringstream s; // 探索開始時刻からの経過時間 Time::point elapsed = Time::now() - SearchTime + 1; // PV lineを調べているRootでの指し手の数。 size_t uciPVSize = std::min((size_t)Options["MultiPV"], RootMoves.size()); int selDepth = 0; for (Thread* th : Threads) if (th->maxPly > selDepth) selDepth = th->maxPly; // MultiPV出力のためのループ for (size_t i = 0; i < uciPVSize; ++i) { // 今回のiterationによってこの指し手のスコア等が更新済みであるか。 // (まだ今回のiterationで更新されていなければprevScoreなど一つ前のスコアを参照して返す必要がある。) bool updated = (i <= PVIdx); if (depth == 1 && !updated) continue; int d = updated ? depth : depth - 1; Value v = updated ? RootMoves[i].score : RootMoves[i].prevScore; if (s.rdbuf()->in_avail()) // Not at first line s << "\n"; // ※ コンピューター将棋に対応させるとき、USIではmultipv未対応らしいのでi!=0のときはmultipvということで // これはinfo stringで送信してやる必要がある。注意。 s << "info depth " << d << " seldepth " << selDepth << " score " << (i == PVIdx ? score_to_uci(v, alpha, beta) : score_to_uci(v)) << " nodes " << pos.nodes_searched() << " nps " << pos.nodes_searched() * 1000 / elapsed << " time " << elapsed << " multipv " << i + 1 << " pv"; for (size_t j = 0; RootMoves[i].pv[j] != MOVE_NONE; ++j) s << " " << move_to_uci(RootMoves[i].pv[j], pos.is_chess960()); } return s.str(); } } // namespace /// RootMove::extract_pv_from_tt() builds a PV by adding moves from the TT table. /// We consider also failing high nodes and not only BOUND_EXACT nodes so to /// allow to always have a ponder move even when we fail high at root, and a /// long PV to print that is important for position analysis. // RootMove::extract_pv_from_tt()は、置換表から指し手を加えることによってPV(最善応手列)を構築する。 // BOUND_EXACTなnodeだけではなくfail highしたnodeも考慮するので、 // Root nodeでfail highしているときでさえ、いつでもponderすることを許す // 表示するための長いPV、それは局面解析のために重要である。 // ToDo : すまない。ここの英語いまひとつわからない。 // ※ TT = Transposition Tableの意味なので「TT table」という書き方はおかしい気がする。 // pos = PVの生成を開始する局面 void RootMove::extract_pv_from_tt(Position& pos) { // ToDo : これ、do_moveに渡しているが初期化しなくて大丈夫なのか? StateInfo state[MAX_PLY_PLUS_6], *st = state; const TTEntry* tte; int ply = 0; // root nodeでの最善手。 // RootMoveのコンストラクタで渡された指し手はpv[0]に格納されているので、これは絶対に破壊してはならない。 // これは置換表がなんであれ置換表の指し手では破壊しないものとする。 Move m = pv[0]; // 一度PVをクリアする。 pv.clear(); do { pv.push_back(m); assert(MoveList // 局面をこの指し手で進める。 pos.do_move(pv[ply++], *st++); // 置換表を調べる tte = TT.probe(pos.key()); } while (tte && pos.pseudo_legal(m = tte->move()) // Local copy, TT could change && pos.legal(m, pos.pinned_pieces(pos.side_to_move())) && ply < MAX_PLY && (!pos.is_draw() || ply < 2)); // ※ 置換表の検査だが、pseudo_legal()で擬似合法手かどうかを判定したあとlegal()で自殺手でないことを // 確認している。このためpseudo_legal()とlegal()とで重複する自殺手チェックは不要。 // do whileループの継続条件 // 1. 置換表にエントリーが存在する // 2. 置換表に登録されていた指し手が合法手(開き王手は考慮せず)である // (tte->moveは他スレッドからの書き換えによって変わりうるので変数mにローカルコピーしてある。) // 3. pinも考慮しても合法手である。 // 4. plyが最大探索深さ以内である // 5. 千日手や50手ルールなどの条件を満たしていない。(ただしそれでも2手目まではOk.) // 最後にMOVE_NONEを書き出しておく。これを終了の合図とする。 pv.push_back(MOVE_NONE); // Must be zero-terminating // 進めた局面を巻き戻す。 while (ply) pos.undo_move(pv[--ply]); } /// RootMove::insert_pv_in_tt() is called at the end of a search iteration, and /// inserts the PV back into the TT. This makes sure the old PV moves are searched /// first, even if the old TT entries have been overwritten. // RootMove::insert_pv_in_tt()は、探索iterationの最後に呼び出され、 // PVを置換表に書き戻す。これは、たとえ、置換表の古いエントリーが上書きされていようとも、 // 古いPVの指し手が最初に探索されることを確実にする。 void RootMove::insert_pv_in_tt(Position& pos) { StateInfo state[MAX_PLY_PLUS_6], *st = state; const TTEntry* tte; int ply = 0; do { // 置換表のlookup tte = TT.probe(pos.key()); // BOUND : 探索していないときのスコアとみなせるのでBOUNDはBOUND_NONE。 // 置換表のエントリーがないだとか、そのエントリーの指し手がpv[ply]でないだとか // したら、書き込んでおく。指し手が一致するときは、置換表上のエントリーのほうが // 探索深さや評価値の情報を持っているので価値が高いと考えられるのでそこは上書きしない。 if (!tte || tte->move() != pv[ply]) // Don't overwrite correct entries TT.store(pos.key(), VALUE_NONE, BOUND_NONE, DEPTH_NONE, pv[ply], VALUE_NONE); // PVの指し手が合法手でなければおかしいのでそのassert。 // extract_pv_from_tt()でそういう条件があるので、間違いなく合法手であり、 // 合法手でないとしたらどこかがこの配列を潰してしまっているということである。 assert(MoveList // 局面をPVの指し手で進める。 pos.do_move(pv[ply++], *st++); // PVの指し手配列pvの終端要素はMOVE_NONEになっている。 // これは、extract_pv_from_tt()でそういう処理をしているからである。 } while (pv[ply] != MOVE_NONE); // 局面を巻き戻す while (ply) pos.undo_move(pv[--ply]); } /// Thread::idle_loop() is where the thread is parked when it has no work to do void Thread::idle_loop() { // Pointer 'this_sp' is not null only if we are called from split(), and not // at the thread creation. So it means we are the split point's master. SplitPoint* this_sp = splitPointsSize ? activeSplitPoint : nullptr; assert(!this_sp || (this_sp->masterThread == this && searching)); while (true) { // If we are not searching, wait for a condition to be signaled instead of // wasting CPU time polling for work. while ((!searching && Threads.sleepWhileIdle) || exit) { if (exit) { assert(!this_sp); return; } // Grab the lock to avoid races with Thread::notify_one() std::unique_lock // If we are master and all slaves have finished then exit idle_loop if (this_sp && !this_sp->slavesMask) break; // Do sleep after retesting sleep conditions under lock protection, in // particular we need to avoid a deadlock in case a master thread has, // in the meanwhile, allocated us and sent the notify_one() call before // we had the chance to grab the lock. if (!searching && !exit) sleepCondition.wait(lk); } // If this thread has been assigned work, launch a search if (searching) { assert(!exit); Threads.mutex.lock(); assert(searching); assert(activeSplitPoint); SplitPoint* sp = activeSplitPoint; Threads.mutex.unlock(); Stack stack[MAX_PLY_PLUS_6], *ss = stack + 2; // To allow referencing (ss-2) Position pos(*sp->pos, this); std::memcpy(ss - 2, sp->ss - 2, 5 * sizeof(Stack)); ss->splitPoint = sp; sp->mutex.lock(); assert(activePosition == nullptr); activePosition = &pos; switch (sp->nodeType) { case Root: search break; case PV: search break; case NonPV: search break; default: assert(false); } assert(searching); searching = false; activePosition = nullptr; sp->slavesMask &= ~(1ULL << idx); sp->nodes += pos.nodes_searched(); // Wake up master thread so to allow it to return from the idle loop // in case we are the last slave of the split point. if (Threads.sleepWhileIdle && this != sp->masterThread && !sp->slavesMask) { assert(!sp->masterThread->searching); sp->masterThread->notify_one(); } // After releasing the lock we cannot access anymore any SplitPoint // related data in a safe way becuase it could have been released under // our feet by the sp master. Also accessing other Thread objects is // unsafe because if we are exiting there is a chance are already freed. sp->mutex.unlock(); } // If this thread is the master of a split point and all slaves have finished // their work at this split point, return from the idle loop. if (this_sp && !this_sp->slavesMask) { this_sp->mutex.lock(); bool finished = !this_sp->slavesMask; // Retest under lock protection this_sp->mutex.unlock(); if (finished) return; } } } /// check_time() is called by the timer thread when the timer triggers. It is /// used to print debug info and, more important, to detect when we are out of /// available time and so stop the search. // check_time()は、時間を引き金として、タイマースレッドから呼び出される。 // これは、デバッグ情報を出力するのに用いられ、そしてこちらのほうが重要であるのだが、 // 利用可能時間を使い切ったので探索を停止させないといけないことを検知するのにも使われる。 void check_time() { static Time::point lastInfoTime = Time::now(); int64_t nodes = 0; // Workaround silly 'uninitialized' gcc warning // 1秒ごとに統計情報をcerrに表示。 // dbg_print()はmisc.cppで定義されている。 // dbg_hit_on()を呼び出した回数などを表示する。 // 置換表のhit率やβcut率などを調べたいときに仕込む。 if (Time::now() - lastInfoTime >= 1000) { lastInfoTime = Time::now(); dbg_print(); } if (Limits.ponder) return; if (Limits.nodes) { Threads.mutex.lock(); nodes = RootPos.nodes_searched(); // Loop across all split points and sum accumulated SplitPoint nodes plus // all the currently active positions nodes. for (Thread* th : Threads) for (int i = 0; i < th->splitPointsSize; ++i) { SplitPoint& sp = th->splitPoints[i]; sp.mutex.lock(); nodes += sp.nodes; Bitboard sm = sp.slavesMask; while (sm) { Position* pos = Threads[pop_lsb(&sm)]->activePosition; if (pos) nodes += pos->nodes_searched(); } sp.mutex.unlock(); } Threads.mutex.unlock(); } // 探索開始時刻からの経過時間 Time::point elapsed = Time::now() - SearchTime; // maximum_timeを超えていないが停止させる // 条件) // 1. firstRootMoveがtrue(これは探索が開始してroot nodeで最初の指し手について調べるのを開始したかのフラグ) // 2. rootでfail lowしていないか(している限りはmaximum_time()まで使っていく) // 3. available_time()を超えている // → available_time()は絶対に使いきる実装だな…。 // ただ、aspiration search中にavailable_time()の62%以上使っていれば停止するので…。 bool stillAtFirstMove = Signals.firstRootMove && !Signals.failedLowAtRoot && elapsed > TimeMgr.available_time(); // 経過時間がmaximum_time()を超えていたら(計測の分解能を考慮して)、このタイミングで停止させなければならない。そのための判定。 bool noMoreTime = elapsed > TimeMgr.maximum_time() - 2 * TimerThread::Resolution || stillAtFirstMove; if ((Limits.use_time_management() && noMoreTime) || (Limits.movetime && elapsed >= Limits.movetime) || (Limits.nodes && nodes >= Limits.nodes)) Signals.stop = true; } |
やねうら王は探索はStockfishベースにしたと思うのですが、以下の部分ってやっぱりやねうら王も1.5倍ですか?
// deltaを1.5倍していく。(指数関数的に増やすため)
delta += delta / 2;
話は変わりまして、量子コンピューターなみの性能を持つ新型半導体コンピューターを日立が出しましたが、こういうのでコンピュータ将棋が変わるんでしょうかね?
チェスの評価値は比較的小さい幅でしか動かないためか、将棋だとそのへんは調整が必要ですね。ただ、そこ調整しても棋力にほとんど影響がないんですよね…。そこよりは、futilityのマージンとかの調整のほうが優先度高いです、たぶん。
> 量子コンピューターなみの性能を持つ新型半導体コンピューターを日立が出しましたが
D-Waveの量子コンピュータの正体も、案外これと同じ仕組だったりして…。
量子コンピュータ(もどき)が、コンピュータ将棋に使えるかどうかは私にはよくわかりません。量子コンピュータ向けに探索アルゴリズムを変形(?)する必要があって、それがすこぶる難しかったりするのではないでしょうか。
…と思ったら、量子アニーリング考案者の西森秀稔先生のコメントが出てました。
https://sites.google.com/site/comments250215/
上記記事が消えたので代わりに…。
http://machiner.hatenablog.com/entry/2015/02/23/101013