実際の試合では通常、思考のための制限時間が設けられているがIterative Deepeningを用いることで、設定していた探索の最大深さnに達する前に深さiで制限時間がきた場合でも、深さi-1あるいはi-2での最善手を答えることができる。これは通常のαβ探索で、宣言時間が来た時点での最善手を出力したのよりはいい手であることが期待できる。（move orderingが問題なければ、それでも問題がない可能性もあるが、そもそもmove orderingが完璧なら探索は不要）
また、逆に制限時間ぎりぎりまで探索を行い、探索の最大深さnを予め設定しないという戦略も考えられる。
Iterative Deepeningを用いる欠点としては、何度も探索を繰り返すため、一度に深さnまで探索することに比べて、計算時間がかかるということがある。しかし、実際にはreversiで探索の深さを2つ増やすと10倍のノード数を探索することになることから、計算時間の殆どは最後の深さで費やされる。
また、killer heuristicあるいはhistory heuristicとtransposition tableを用いることで、一度、探索したノードに関してのmove orderingに関するヒントがあるため、2回目以降のあるノードの探索はそれ以前の探索よりも効率が改善される。
abstract class NegaAlphaBetaTKIPlayer[N <: Node[N]](
override val maxDepth: Int,
override val numKillerMoves: Int
) extends NegaAlphaBetaTKPlayer[N](maxDepth, numKillerMoves) {
override def play(ply: Int, node: N, last: Move): Move = {
initKillerMoves(maxDepth)
initTranspositionTable()
var m = Move.empty
var s = 0
for (d <- 1 to maxDepth) {
var ret = play(node, Int.MinValue + 1, Int.MaxValue, d)
m = ret._1
s = ret._2
}
m
}
}
また、MTD(f)で深さiの探索でスコアsiが得られたとき、次の深さi+1での探索で用いるf値としてsiを用いることで、効率の改善を行うことができる。 abstract class MTDfIPlayer[N <: Node[N]](override val maxDepth: Int, override val numKillerMoves: Int) extends MTDfPlayer[N](maxDepth, numKillerMoves) {
override def play(ply: Int, node: N, last: Move): Move = {
var m = Move.empty
var f = 0
for (d <- 1 to maxDepth) {
var ret = mtd(node, f, d)
m = ret._1
f = ret._2
}
m
}
}
実験結果は次のようになった。 mtdfi = MTD(f) + Iterative Deepeningはmtdf = MTD(f)と比較して、ずいぶんと遅くなってしまった。 reversiでは、1手ごとに盤面が大きく反転するため、各盤面のマーカーの数の差を評価関数としている今の実装では、1手ずつ深さを大きくしては評価関数が大きく異なってしまう。そこで、深さを2つずつ深くすることにしたのがmtdfiiである。 mtdfiiでは驚異的な高速化が実現できていることが分かる。Plaatも文献[2]でIterative Deepeningを用いたほうがMTD(f)は高速化できると述べているが、それが確認できた。これは上述したように、正しいf値がわかっていればMTD(f)が高速に実行できることによる。 xtabs(node ~ name + depth + test, data=data) xtabs(node ~ name + depth + test, data=data) , , test = end40.pos depth name 2 3 4 5 6 7 8 9 10 negaalpha_tki 27 144 312 1407 2748 12027 22896 95966 166264 mtdf 19 157 201 1145 2184 8630 19720 80814 125003 mtdfi 38 273 468 1350 2649 61645 71797 544975 617768 mtdfii 29 210 130 1222 977 9220 7333 70436 52315 , , test = end41.pos depth name 2 3 4 5 6 7 8 9 10 negaalpha_tki 48 320 1260 4601 16389 62575 134156 697922 1344073 mtdf 26 249 540 2540 10144 32079 89519 272946 730291 mtdfi 51 550 2193 7426 25878 114998 307825 1092744 2608613 mtdfii 26 140 245 1714 2528 21369 14180 293350 71827 , , test = end42.pos depth name 2 3 4 5 6 7 8 9 10 negaalpha_tki 47 240 880 3708 10722 38172 94721 284084 432764 mtdf 38 345 421 5835 4035 46867 34123 456385 278434 mtdfi 59 575 1580 8255 17903 96307 204907 1114367 1906220 mtdfii 38 107 181 843 1061 6954 5889 65086 37483 , , test = end43.pos depth name 2 3 4 5 6 7 8 9 10 negaalpha_tki 54 180 765 2536 13292 34713 116837 267089 1174524 mtdf 67 110 707 1647 5795 14456 71506 140004 910524 mtdfi 74 217 1015 3946 12843 51678 189323 661060 2500599 mtdfii 78 66 459 571 3030 3384 33946 22912 366578 , , test = end44.pos depth name 2 3 4 5 6 7 8 9 10 negaalpha_tki 52 344 1099 5003 15538 59180 147316 439640 997603 mtdf 40 240 499 2551 4997 25153 27638 185753 202377 mtdfi 37 165 606 2154 7053 22857 72144 283054 703381 mtdfii 33 127 292 1182 2762 10376 29753 64848 231725 , , test = end45.pos depth name 2 3 4 5 6 7 8 9 10 negaalpha_tki 43 482 1091 7021 12591 61363 112906 633612 1143702 mtdf 26 372 229 4987 2873 53545 25900 821370 264835 mtdfi 145 548 1825 6801 9686 50700 80793 719172 1015111 mtdfii 26 270 203 2918 1652 28193 13046 344268 106753 , , test = end46.pos depth name 2 3 4 5 6 7 8 9 10 negaalpha_tki 43 351 1251 6172 17777 63246 175963 527763 1486986 mtdf 39 281 523 4198 3262 39651 42332 329191 613156 mtdfi 88 330 1024 4863 16408 50115 247527 555860 3092708 mtdfii 28 198 308 1902 2881 16609 16787 121939 177208 , , test = end47.pos depth name 2 3 4 5 6 7 8 9 10 negaalpha_tki 44 203 894 2684 12688 31567 94186 200162 544096 mtdf 36 78 429 2577 4856 19380 67651 109788 197836 mtdfi 51 435 1284 5069 14830 49130 123938 351612 863045 mtdfii 31 88 335 522 3212 2880 41819 17430 186658 , , test = end48.pos depth name 2 3 4 5 6 7 8 9 10 negaalpha_tki 48 431 1052 8071 18760 81991 184514 788373 1864961 mtdf 67 326 915 4102 15734 29080 255981 243128 3512508 mtdfi 90 417 1938 6050 28545 70722 389946 779557 5202121 mtdfii 46 223 286 2382 4762 21489 45791 200969 416676 , , test = end49.pos depth name 2 3 4 5 6 7 8 9 10 negaalpha_tki 56 232 1242 4025 13435 49126 157654 453791 1133343 mtdf 38 156 885 1148 11959 9846 121120 159526 1046491 mtdfi 51 338 1367 5939 17179 51172 150261 758475 1685930 mtdfii 39 122 267 1296 2464 14150 23171 137191 176559 , , test = end50.pos depth name 2 3 4 5 6 7 8 9 10 negaalpha_tki 56 572 1332 13494 25639 172585 365969 2063853 3945385 mtdf 40 530 739 8118 10159 74391 123517 827792 1296946 mtdfi 65 1009 2034 28671 41322 395558 561635 4992068 6668513 mtdfii 39 304 334 5234 3586 46466 35443 567751 323205 , , test = end51.pos depth name 2 3 4 5 6 7 8 9 10 negaalpha_tki 71 315 1259 5109 18757 62872 173480 641455 2174737 mtdf 52 125 622 3728 8393 28470 78740 280931 615093 mtdfi 85 451 1392 8534 17525 78786 171940 838877 1961416 mtdfii 47 146 415 1166 5141 10768 61652 75997 639172 , , test = end52.pos depth name 2 3 4 5 6 7 8 9 10 negaalpha_tki 56 354 1211 4601 12285 46639 149329 504289 1772591 mtdf 86 222 1315 2712 10970 23226 138992 214488 1826514 mtdfi 103 286 1753 4269 18762 41305 238447 479219 3653675 mtdfii 100 148 411 1408 2408 10023 21096 77156 305320 , , test = end53.pos depth name 2 3 4 5 6 7 8 9 10 negaalpha_tki 55 450 1795 7861 27736 82230 299993 1027148 3897564 mtdf 39 230 852 3732 12847 32240 150454 339665 1530138 mtdfi 53 397 1274 6754 19627 75227 210558 888269 2105971 mtdfii 42 239 437 2554 6465 21991 43476 201229 253059 , , test = end54.pos depth name 2 3 4 5 6 7 8 9 10 negaalpha_tki 35 299 785 4811 11957 69781 154930 733142 1498804 mtdf 25 244 264 2154 2919 26304 27551 356998 277035 mtdfi 62 312 1215 3673 16481 47658 141373 617936 1525344 mtdfii 25 164 243 1698 2454 14098 19153 124606 154492 , , test = end55.pos depth name 2 3 4 5 6 7 8 9 10 negaalpha_tki 69 524 1400 6788 25108 95356 268716 1443151 4697020 mtdf 37 222 807 5464 9661 66834 129831 1378381 1613133 mtdfi 72 697 1431 15361 29588 161211 314955 2492192 4609357 mtdfii 29 227 547 2525 8511 30598 93606 351371 1157032 , , test = end56.pos depth name 2 3 4 5 6 7 8 9 10 negaalpha_tki 63 299 1484 5344 15299 57231 221934 698765 3553217 mtdf 54 129 983 1819 8245 17193 135445 175100 2163370 mtdfi 64 251 1404 4914 18623 61892 331602 895358 5403801 mtdfii 39 119 596 1174 3945 12069 56802 84958 990616 , , test = end57.pos depth name 2 3 4 5 6 7 8 9 10 negaalpha_tki 56 323 1064 5476 16899 54500 152238 553410 1779973 mtdf 42 360 471 3790 6903 32076 69937 324390 743752 mtdfi 66 617 1692 8459 22629 100704 266140 922625 3069773 mtdfii 46 176 219 1598 2162 18404 21477 111504 174753 , , test = end58.pos depth name 2 3 4 5 6 7 8 9 10 negaalpha_tki 82 663 2082 9142 35925 129141 421977 1384790 5002305 mtdf 65 351 1113 4090 17028 46623 194900 756321 2240661 mtdfi 50 765 1652 7709 18686 89967 228445 891754 1971828 mtdfii 63 403 428 3903 4312 48304 40838 413731 389535 , , test = end59.pos depth name 2 3 4 5 6 7 8 9 10 negaalpha_tki 33 271 555 3398 6433 37380 60376 305924 473199 mtdf 26 234 340 2702 4503 53546 43223 664528 400769 mtdfi 33 194 396 5297 7543 37372 52452 525732 932387 mtdfii 24 187 173 1990 1591 23700 15184 174436 146142 xtabs(inode ~ name + depth + test, data=data) , , test = end40.pos depth name 2 3 4 5 6 7 8 9 10 negaalpha_tki 12 35 175 425 1801 4229 16695 39191 128551 mtdf 20 40 217 308 2533 2516 22999 26555 153526 mtdfi 27 82 293 513 2092 18028 30854 170707 264561 mtdfii 51 110 181 457 1367 2586 20231 21128 163351 , , test = end41.pos depth name 2 3 4 5 6 7 8 9 10 negaalpha_tki 12 83 401 1688 6224 26529 61534 342616 710022 mtdf 13 79 204 1032 3885 15013 41419 128792 334734 mtdfi 18 166 663 2509 8855 43754 110265 430495 1003273 mtdfii 14 59 155 723 1886 10708 10919 184394 64339 , , test = end42.pos depth name 2 3 4 5 6 7 8 9 10 negaalpha_tki 11 58 344 1195 5207 14679 53900 121472 260799 mtdf 21 102 318 1858 3391 16191 30349 162371 247556 mtdfi 27 187 694 3024 8171 36022 88875 432348 862871 mtdfii 28 36 190 341 1451 3101 7970 36530 51367 , , test = end43.pos depth name 2 3 4 5 6 7 8 9 10 negaalpha_tki 8 56 196 1158 3951 17136 44746 149262 474638 mtdf 37 83 430 1387 3786 13279 37569 131401 442206 mtdfi 39 144 618 3189 8846 45974 112050 590142 1391417 mtdfii 75 37 356 466 1666 3203 20743 21112 172946 , , test = end44.pos depth name 2 3 4 5 6 7 8 9 10 negaalpha_tki 12 72 374 1593 6296 21843 62154 186770 486334 mtdf 27 64 360 767 3434 9050 18672 77939 127106 mtdfi 18 64 314 901 3379 10100 32943 111393 315380 mtdfii 38 41 212 475 1940 5170 22170 34052 162233 , , test = end45.pos depth name 2 3 4 5 6 7 8 9 10 negaalpha_tki 16 76 492 1689 6158 17622 61537 211198 692718 mtdf 17 93 236 1221 3221 13172 30165 224838 317661 mtdfi 83 191 1371 2590 5791 15514 50209 215649 570301 mtdfii 32 87 283 688 2704 6991 18780 111687 156860 , , test = end46.pos depth name 2 3 4 5 6 7 8 9 10 negaalpha_tki 14 82 447 2059 7448 25337 78953 225211 684600 mtdf 29 135 469 2330 3341 24990 40478 213988 580150 mtdfi 59 146 817 2600 13696 31254 217213 391750 2489635 mtdfii 54 76 273 689 2636 6915 31127 67477 452266 , , test = end47.pos depth name 2 3 4 5 6 7 8 9 10 negaalpha_tki 10 51 292 911 4514 14649 42732 90664 245612 mtdf 20 26 198 708 2143 6788 25443 36938 98494 mtdfi 24 144 449 1742 5672 18807 47613 145070 360800 mtdfii 24 28 256 224 1402 1665 21316 14008 86311 , , test = end48.pos depth name 2 3 4 5 6 7 8 9 10 negaalpha_tki 15 68 439 1909 8493 24921 92023 273357 1004646 mtdf 59 80 920 1342 16486 9785 277602 88358 3447820 mtdfi 62 149 1539 2876 23631 42225 360139 554422 4532668 mtdfii 115 56 498 671 3960 6040 37174 65008 339421 , , test = end49.pos depth name 2 3 4 5 6 7 8 9 10 negaalpha_tki 10 61 328 1439 4500 19206 62015 189614 516945 mtdf 14 46 266 473 3466 4445 38142 70714 391549 mtdfi 17 118 422 1992 5657 18011 54053 320202 681282 mtdfii 18 51 125 660 1630 9782 12386 79578 85884 , , test = end50.pos depth name 2 3 4 5 6 7 8 9 10 negaalpha_tki 17 88 541 2879 12255 44650 190361 612250 2196754 mtdf 25 96 457 1730 6632 17587 93442 205131 1057440 mtdfi 30 213 780 5795 13061 84063 198306 1206164 2473435 mtdfii 35 61 313 1376 3834 11202 43461 143730 415332 , , test = end51.pos depth name 2 3 4 5 6 7 8 9 10 negaalpha_tki 12 67 379 1547 6704 19270 73905 238106 1043256 mtdf 22 34 296 987 3345 7547 43402 77323 312141 mtdfi 30 116 495 2381 6075 22924 70092 264603 763406 mtdfii 26 36 202 511 4045 4537 33661 26643 465021 , , test = end52.pos depth name 2 3 4 5 6 7 8 9 10 negaalpha_tki 12 79 398 1421 5028 16171 66216 198423 850712 mtdf 54 100 992 1526 9120 13207 116745 121724 1447330 mtdfi 57 134 1216 2634 15355 30207 200087 375522 2724856 mtdfii 98 47 368 675 2033 4027 14491 33007 243152 , , test = end53.pos depth name 2 3 4 5 6 7 8 9 10 negaalpha_tki 13 84 511 2262 9718 27978 107702 403217 1574439 mtdf 17 61 292 1152 3918 11160 50430 120455 499125 mtdfi 17 113 404 2184 6164 26825 70732 309251 715027 mtdfii 26 110 228 1049 2818 6967 23303 67523 146003 , , test = end54.pos depth name 2 3 4 5 6 7 8 9 10 negaalpha_tki 12 61 347 1123 6213 19908 84094 231311 824160 mtdf 13 81 186 562 2415 7050 26675 95999 285069 mtdfi 39 117 876 1504 12164 19943 102348 220389 1096924 mtdfii 13 49 183 407 2193 5042 21355 37920 192041 , , test = end55.pos depth name 2 3 4 5 6 7 8 9 10 negaalpha_tki 16 76 470 1598 10615 28906 120124 467316 2071576 mtdf 25 46 411 1136 5360 14684 79257 363423 1027242 mtdfi 36 159 542 3274 10154 40651 123161 720938 1885125 mtdfii 26 62 428 592 8595 7518 64036 151976 798874 , , test = end56.pos depth name 2 3 4 5 6 7 8 9 10 negaalpha_tki 11 69 338 1693 4845 23624 75291 276756 1133606 mtdf 37 57 553 1019 4991 12052 69517 127131 933129 mtdfi 39 134 853 3004 11170 40989 137902 552298 2047606 mtdfii 56 43 393 487 2193 8249 35652 45701 517070 , , test = end57.pos depth name 2 3 4 5 6 7 8 9 10 negaalpha_tki 10 62 330 1810 5836 21013 63370 246939 734281 mtdf 18 111 204 1351 2652 12826 23726 141613 255644 mtdfi 25 192 536 2599 6837 34051 82945 326333 969907 mtdfii 31 122 146 1125 1340 9303 12345 55076 101367 , , test = end58.pos depth name 2 3 4 5 6 7 8 9 10 negaalpha_tki 15 127 597 2792 11048 41198 127573 477666 1925393 mtdf 27 78 402 1404 5113 19975 55775 286178 668517 mtdfi 24 197 520 2199 6113 29353 77148 293688 735727 mtdfii 34 155 240 1791 2478 15063 23048 239345 221394 , , test = end59.pos depth name 2 3 4 5 6 7 8 9 10 negaalpha_tki 13 54 262 853 3544 10599 38819 98781 320323 mtdf 22 70 330 860 4335 15360 45494 171830 442720 mtdfi 22 58 301 1392 4054 10364 28514 127138 616389 mtdfii 32 55 238 583 2039 6497 20395 42391 198626 xtabs(time ~ name + depth + test, data=data) , , test = end40.pos
, , test = end40.pos
depth
name 2 3 4 5 6 7 8 9 10
negaalpha_tki 192 344 591 967 1712 3217 7476 17203 45032
mtdf 212 360 673 864 1838 2277 8747 12284 47928
mtdfi 266 481 775 1008 1820 9848 14145 77050 106235
mtdfii 327 498 553 968 1296 2466 6302 11380 37774
, , test = end41.pos
depth
name 2 3 4 5 6 7 8 9 10
negaalpha_tki 200 532 950 1946 4173 14444 28540 159529 296993
mtdf 201 476 684 1431 2925 8170 18707 58725 134018
mtdfi 237 654 1233 2443 5786 23117 54947 205308 462909
mtdfii 194 403 555 1226 1667 6319 5240 80132 22742
, , test = end42.pos
depth
name 2 3 4 5 6 7 8 9 10
negaalpha_tki 197 448 839 1641 3339 8264 22135 52980 94388
mtdf 241 555 754 2117 2351 9530 12319 76665 85495
mtdfi 281 706 1145 2657 4913 18456 39600 198399 357176
mtdfii 273 351 583 883 1299 2705 3791 17235 16225
, , test = end43.pos
depth
name 2 3 4 5 6 7 8 9 10
negaalpha_tki 192 455 740 1554 3350 10251 23406 75513 216398
mtdf 343 467 914 1625 2849 7777 16976 60063 178443
mtdfi 350 563 1144 2700 5366 23269 51047 250602 583770
mtdfii 408 333 758 941 1619 2574 8574 10655 64743
, , test = end44.pos
depth
name 2 3 4 5 6 7 8 9 10
negaalpha_tki 218 520 934 1977 4436 13719 36305 99221 250647
mtdf 285 449 837 1289 2586 5851 9100 36664 52860
mtdfi 241 436 834 1444 3257 7220 21003 64578 172130
mtdfii 287 351 641 1026 1799 4056 9750 18874 61517
, , test = end45.pos
depth
name 2 3 4 5 6 7 8 9 10
negaalpha_tki 237 575 1017 2081 4110 10471 29125 102126 294069
mtdf 218 528 663 1708 2405 8171 13207 109720 117397
mtdfi 458 682 1565 2409 3791 9031 22507 103948 233756
mtdfii 259 472 672 1275 1994 5015 8518 51630 55499
, , test = end46.pos
depth
name 2 3 4 5 6 7 8 9 10
negaalpha_tki 234 584 1024 2177 5109 13252 39768 101521 322282
mtdf 302 610 938 2019 2970 10998 20808 80104 264504
mtdfi 412 594 1238 2398 8311 15621 102484 175383 1147167
mtdfii 320 445 732 1185 2251 4249 12565 28659 137486
, , test = end47.pos
depth
name 2 3 4 5 6 7 8 9 10
negaalpha_tki 211 407 845 1413 3666 8094 21691 42747 123128
mtdf 255 289 685 1233 2162 4401 13992 17980 45107
mtdfi 280 623 994 1986 4214 10705 25330 71187 175736
mtdfii 249 314 663 684 1610 1708 10429 6676 38406
, , test = end48.pos
depth
name 2 3 4 5 6 7 8 9 10
negaalpha_tki 220 510 947 2328 5209 15548 42680 146659 433613
mtdf 379 504 1166 1826 7198 6729 90920 46893 1165974
mtdfi 397 625 1546 2541 10675 20484 139057 237483 1724120
mtdfii 417 433 752 1275 2660 4618 14549 35254 119404
, , test = end49.pos
depth
name 2 3 4 5 6 7 8 9 10
negaalpha_tki 212 456 952 1861 3647 11814 32138 96812 241927
mtdf 223 387 816 1011 3061 3418 20681 34559 186244
mtdfi 247 564 1030 2249 4542 11233 30069 161707 341093
mtdfii 249 369 576 1121 1643 5605 7019 35260 40367
, , test = end50.pos
depth
name 2 3 4 5 6 7 8 9 10
negaalpha_tki 235 569 1002 2864 6552 24849 77082 298901 2002592
mtdf 267 573 911 2165 4071 11508 38965 110762 409172
mtdfi 298 781 1271 4687 7968 48354 93651 639259 1143363
mtdfii 299 466 736 1833 2501 7562 16264 76513 139852
, , test = end51.pos
depth
name 2 3 4 5 6 7 8 9 10
negaalpha_tki 233 527 970 1964 5067 11699 39280 120552 512157
mtdf 287 348 819 1535 2941 5385 22720 40695 148588
mtdfi 326 632 1079 2609 4727 14342 38478 142872 399493
mtdfii 288 351 686 1001 2814 3552 16272 14322 176716
, , test = end52.pos
depth
name 2 3 4 5 6 7 8 9 10
negaalpha_tki 213 564 947 1915 3675 10595 31643 106557 377542
mtdf 381 550 1282 1840 5208 8920 46244 67656 535107
mtdfi 395 577 1529 2411 8080 16423 83995 182167 1124812
mtdfii 445 396 758 1160 1762 3328 6937 18772 82253
, , test = end53.pos
depth
name 2 3 4 5 6 7 8 9 10
negaalpha_tki 232 561 1170 2668 7390 18835 65650 239651 902737
mtdf 252 452 847 1658 3404 7237 28050 62352 256171
mtdfi 250 575 1024 2608 5440 18398 47266 196535 446006
mtdfii 292 511 707 1559 2529 5695 12128 42288 66074
, , test = end54.pos
depth
name 2 3 4 5 6 7 8 9 10
negaalpha_tki 205 476 869 1738 4508 12885 41999 127080 392055
mtdf 203 497 636 1186 2198 5136 13612 52716 127569
mtdfi 354 564 1311 1880 7277 11499 47860 113797 489012
mtdfii 211 398 646 1015 2049 3526 10752 21598 83234
, , test = end55.pos
depth
name 2 3 4 5 6 7 8 9 10
negaalpha_tki 254 541 1037 2085 7345 17497 67683 249175 1083552
mtdf 285 412 948 1710 4070 9539 39537 190733 495246
mtdfi 355 688 1150 3265 7303 25520 69167 409245 1031610
mtdfii 266 437 855 1315 4756 5660 30332 70663 357100
, , test = end56.pos
depth
name 2 3 4 5 6 7 8 9 10
negaalpha_tki 223 492 965 2123 4420 14306 43053 152191 625376
mtdf 345 421 1093 1447 3981 7542 37263 63112 466109
mtdfi 353 601 1350 2810 7680 23314 78749 282362 1124166
mtdfii 341 385 842 1024 2111 5437 15539 24942 210108
, , test = end57.pos
depth
name 2 3 4 5 6 7 8 9 10
negaalpha_tki 202 493 1000 2350 4874 14416 36762 148146 411699
mtdf 248 627 686 1726 2438 8153 13480 72412 123414
mtdfi 289 721 1159 2927 5779 23182 54314 204918 591781
mtdfii 308 556 562 1439 1506 6935 6630 33987 43895
, , test = end58.pos
depth
name 2 3 4 5 6 7 8 9 10
negaalpha_tki 269 664 1279 3055 7966 25900 74164 266082 1047197
mtdf 319 521 988 1825 4327 11638 34256 150629 381071
mtdfi 303 759 1169 2598 5121 18952 47575 170188 422570
mtdfii 334 617 816 1902 2483 9966 13338 108924 107658
, , test = end59.pos
depth
name 2 3 4 5 6 7 8 9 10
negaalpha_tki 205 448 781 1462 2903 7098 18863 51594 140848
mtdf 252 479 775 1415 3074 9710 21045 92571 185497
mtdfi 259 437 765 1877 3263 7207 15440 73102 284825
mtdfii 282 422 676 1212 1788 5052 9615 25040 79079
[1] Marsland. Relative efficiency of alpha-beta implementations. Proceedings of the International Joint Conference on Artificial Intelligence (IJCAI-83) (1983) pp. 763–766
[2] Plaat and University of Alberta. Dept. of Computing Science. A new paradigm for minimax search. (1994)
