Plaatらによって考案されたMTD [1]はScoutおよびNegaScoutのその問題点を解決する。MTDは通常のαβ探索は一切行わず、Test関数のみを用いる。現在、αβ探索から派生した探索手法の中では最も高速な探索として知られている。
MTDにおけるTest関数はMemory-enhanced Test (MT)とよぶ。これは、NegaScoutのnull-window searchにTransposition tableを加えたものと考えてよい。（現論文ではスコアに実数値を使っているところが違うという記述があるが、そこは本質的な差ではないと思う。むしろ、alpha cut、beta cutの際に実際の値を返すところに差がある。）
def mt(node: N, gamma: Int, depth: Int): (Move, Int) = {
if (depth == 0 || node.isTerminal) {
return (Move.empty, score(node))
}
// check transposition table
val (recordedMove, recordedScore) = probeNode(node, depth, gamma - 1, gamma)
var moves = node.possibleMoves().toList
// use the recorded move if it is available
if (recordedMove != Move.empty && (moves contains recordedMove)) {
moves = recordedMove :: (moves filterNot {_ == recordedMove})
}
var bestMove = Move.empty
var g = Int.MinValue + 1
for (m <- moves) {
val n = node.play(m).get
val (_, s) = mt(n, -gamma + 1, depth - 1)
if (-s >= gamma) {
// record transpositon table
recordNode(node, depth, -s, TranspositionTable.BETA, m)
return (m, -s)
}
if (-s > g) {
bestMove = m
g = -s
}
}
if (g < gamma)
recordNode(node, depth, g, TranspositionTable.ALPHA, bestMove)
(bestMove, g)
}
そして、MTを使う、MT Driver関数が次のようになる。これは、最初、解の上限upperと下限lowerをそれぞれ+∞、-∞に設定し、適当な値fからMTを用いて解の探索を行い、upperとlowerが一致したとき、それが求めるminmax値になるというものである。 def mtd(node: N, f: Int, depth: Int): (Move, Int) = {
var g = f
var bestMove = Move.empty
var upper = Int.MaxValue
var lower = Int.MinValue + 1
while (lower < upper) {
val bound = if (g == lower) g + 1 else g
val (m, s) = mt(node, bound, depth)
g = s
bestMove = m
if (g < bound) {
upper = g
} else {
lower = g
}
}
return (bestMove, g)
}
ベンチマーク結果のNegaScoutとの比較は次のようになった。
端末ノード数
xtabs(node ~ name + depth + test, data=data)
, , test = end40.pos
depth
name 2 3 4 5 6 7 8 9 10
negascout 13 118 150 869 1426 6877 11739 50161 107685
negascout_k 13 118 141 902 1324 7883 10528 65640 88274
negascout_t 13 118 144 825 1217 5736 8835 36378 72029
negascout_kt 13 118 141 875 1138 7226 10083 53044 73327
mtdf 29 234 201 1173 1302 7735 9647 52626 63001
, , test = end41.pos
depth
name 2 3 4 5 6 7 8 9 10
negascout 30 277 498 3942 5522 38672 51316 637813 507317
negascout_k 26 205 328 2391 3854 21961 29935 379585 282423
negascout_t 30 255 423 3607 4750 34045 33459 504176 278609
negascout_kt 26 187 325 2184 3832 19717 25478 334212 205353
mtdf 26 210 280 2038 3523 23302 32603 182267 263264
, , test = end42.pos
depth
name 2 3 4 5 6 7 8 9 10
negascout 30 177 375 2436 3176 25612 42839 248198 549411
negascout_k 30 114 325 1181 2374 8101 27187 64654 213624
negascout_t 30 169 351 2638 3081 22922 36559 204722 367558
negascout_kt 30 114 310 1176 2352 8224 22283 57193 170565
mtdf 38 210 290 2563 2279 21173 17029 163380 125509
, , test = end43.pos
depth
name 2 3 4 5 6 7 8 9 10
negascout 49 64 455 1241 5358 13714 74902 246768 1342957
negascout_k 48 59 300 936 3259 8122 34030 82466 697031
negascout_t 49 64 452 1121 4794 11178 66526 159512 873095
negascout_kt 48 59 300 1122 2793 6589 28902 77931 833684
mtdf 78 103 795 1278 4137 9855 62631 83677 626759
, , test = end44.pos
depth
name 2 3 4 5 6 7 8 9 10
negascout 37 163 718 2376 6146 31217 41518 382253 369021
negascout_k 31 154 553 1903 4252 19442 32793 193691 250324
negascout_t 37 145 661 1978 5712 26938 35992 307232 271322
negascout_kt 31 134 526 1690 3977 19028 28238 198876 188543
mtdf 33 133 479 1493 3613 16429 20386 106444 138136
, , test = end45.pos
depth
name 2 3 4 5 6 7 8 9 10
negascout 34 341 307 5106 2720 48033 26628 663943 243477
negascout_k 24 263 246 4243 2446 42004 26254 542838 293315
negascout_t 34 350 293 4548 2435 44768 18250 507703 154510
negascout_kt 24 266 236 3649 2189 39254 24296 414675 204045
mtdf 26 348 197 3686 1771 32145 15908 357230 111041
, , test = end46.pos
depth
name 2 3 4 5 6 7 8 9 10
negascout 25 374 485 9812 9666 120794 121581 867828 1146500
negascout_k 24 239 412 4179 5676 34681 53114 199289 393103
negascout_t 25 346 440 8225 9262 92633 105958 674553 820007
negascout_kt 24 221 399 4038 5138 34552 50520 157812 320921
mtdf 28 331 337 2732 2064 25001 25891 206345 289721
, , test = end47.pos
depth
name 2 3 4 5 6 7 8 9 10
negascout 47 77 742 709 12574 6465 147226 35518 647303
negascout_k 36 76 661 635 7067 6277 95607 39140 374661
negascout_t 47 77 735 507 12231 4950 117537 20431 415691
negascout_kt 36 76 626 454 10148 4509 86232 17140 273479
mtdf 31 78 376 598 4341 3657 54517 20163 137717
, , test = end48.pos
depth
name 2 3 4 5 6 7 8 9 10
negascout 29 237 487 4048 8711 47471 101834 447611 1157189
negascout_k 28 215 426 2508 5893 27912 54901 234412 535168
negascout_t 29 225 435 3325 7348 38797 92198 342054 921632
negascout_kt 28 215 378 2523 5536 23540 57060 212023 430229
mtdf 46 260 452 2665 4791 21272 76293 188805 1262584
, , test = end49.pos
depth
name 2 3 4 5 6 7 8 9 10
negascout 34 278 539 1791 6544 15755 119662 171897 1286707
negascout_k 34 178 556 1283 7316 10730 84280 187484 469384
negascout_t 34 253 526 1578 5643 12621 96787 130468 741520
negascout_kt 34 170 523 1182 7096 9134 93741 147926 399412
mtdf 39 116 478 1031 6895 8009 67221 119862 584316
, , test = end50.pos
depth
name 2 3 4 5 6 7 8 9 10
negascout 33 323 675 12049 10445 311521 165628 8331136 2730443
negascout_k 33 307 540 5224 6775 77991 95550 1070570 1200398
negascout_t 33 323 604 10528 8292 248164 121633 0 1549757
negascout_kt 33 307 511 5195 5647 71885 70762 877446 783511
mtdf 39 362 454 6862 5704 58813 58077 580193 530472
, , test = end51.pos
depth
name 2 3 4 5 6 7 8 9 10
negascout 59 202 1030 1938 19853 24097 375925 327750 8490980
negascout_k 59 155 712 1635 9593 20397 82927 222009 969788
negascout_t 59 205 1005 2013 18482 20749 303961 247261 0
negascout_kt 59 145 661 1583 9301 19182 81196 146625 912394
mtdf 47 124 546 1780 7955 13778 59771 111734 458086
, , test = end52.pos
depth
name 2 3 4 5 6 7 8 9 10
negascout 63 180 902 1709 5654 19288 81468 195141 1277140
negascout_k 37 162 353 1527 3548 16149 44295 148178 676770
negascout_t 63 173 860 1687 4917 15049 67976 134405 922381
negascout_kt 37 163 327 1608 3252 13121 47402 111351 550509
mtdf 100 229 1386 2256 8565 17936 80934 139339 1002842
, , test = end53.pos
depth
name 2 3 4 5 6 7 8 9 10
negascout 43 349 1278 10972 25288 247619 274617 10298036 3186665
negascout_k 35 279 855 4318 11674 31320 158313 327077 1444664
negascout_t 43 320 1146 10194 22327 204413 250846 0 2293979
negascout_kt 35 271 782 4716 10903 29281 164489 260376 1312628
mtdf 42 198 583 2503 7333 22081 94618 190844 782647
, , test = end54.pos
depth
name 2 3 4 5 6 7 8 9 10
negascout 23 216 371 2194 5870 26600 92194 287651 927408
negascout_k 24 189 262 1950 2957 22626 34695 273318 345191
negascout_t 23 216 371 2066 5222 20270 70386 218128 615772
negascout_kt 24 181 261 1593 2659 18939 27884 212148 244200
mtdf 25 246 249 1644 2675 15708 20004 189045 172175
, , test = end55.pos
depth
name 2 3 4 5 6 7 8 9 10
negascout 49 295 857 4616 20627 59091 189197 1009661 3447413
negascout_k 46 281 784 3663 12208 42926 157864 535946 1913433
negascout_t 49 290 782 3765 19311 49978 174816 684694 2790214
negascout_kt 46 281 743 3258 13625 42493 152997 394130 1709642
mtdf 29 219 583 3210 8008 35739 102432 674335 894445
, , test = end56.pos
depth
name 2 3 4 5 6 7 8 9 10
negascout 56 120 1326 1596 14771 21502 222253 230785 6013316
negascout_k 54 111 825 1349 5028 14212 63928 147220 1852309
negascout_t 56 120 1226 1463 12164 18036 180860 163746 4371241
negascout_kt 54 111 768 1262 3992 11816 48671 105271 1901167
mtdf 39 130 849 1716 6891 12869 108870 105432 1541331
, , test = end57.pos
depth
name 2 3 4 5 6 7 8 9 10
negascout 38 237 507 4475 4477 61001 30822 849439 392082
negascout_k 37 161 480 2561 4497 16136 32622 163275 394994
negascout_t 38 237 496 4291 4445 52345 31573 716148 306181
negascout_kt 37 161 451 2463 4398 15841 36980 157818 383875
mtdf 46 283 390 2681 3991 26394 32885 212230 320514
, , test = end58.pos
depth
name 2 3 4 5 6 7 8 9 10
negascout 55 547 863 14095 16348 194209 211595 2727903 2286834
negascout_k 55 407 830 4674 13645 56220 170146 811251 1984559
negascout_t 55 498 847 11013 16801 159529 187444 2205883 1854687
negascout_kt 55 323 821 4154 15337 53196 183057 755832 1836974
mtdf 63 235 877 3600 10648 36041 106170 381251 1121595
, , test = end59.pos
depth
name 2 3 4 5 6 7 8 9 10
negascout 18 214 209 2844 2643 58239 30403 1008983 216835
negascout_k 18 197 205 2070 2262 36733 23426 345174 193849
negascout_t 18 217 204 2730 2126 46808 21839 489119 134627
negascout_kt 18 208 199 1969 2081 33587 19116 256418 137030
mtdf 24 225 243 2609 2325 27312 19056 241424 147367
内部ノード数
xtabs(inode ~ name + depth + test, data=data)
, , test = end40.pos
depth
name 2 3 4 5 6 7 8 9 10
negascout 11 25 146 228 1486 2075 12348 17988 110404
negascout_k 11 25 136 229 1365 2139 11491 19991 99489
negascout_t 11 25 144 228 1345 1922 9857 14867 78863
negascout_kt 11 25 136 229 1257 2011 11958 17234 87156
mtdf 51 84 444 474 2569 2858 14480 19742 87419
, , test = end41.pos
depth
name 2 3 4 5 6 7 8 9 10
negascout 11 99 187 1437 2399 15724 23784 276227 263413
negascout_k 11 81 171 1109 1951 11428 16272 209894 169736
negascout_t 11 99 187 1464 2427 14722 17715 260280 178906
negascout_kt 11 80 171 1067 2238 10939 14737 215444 136676
mtdf 14 92 372 1205 4666 16123 42790 112425 341222
, , test = end42.pos
depth
name 2 3 4 5 6 7 8 9 10
negascout 10 59 221 933 2237 9461 30490 93282 386576
negascout_k 10 46 193 579 1931 3864 23020 29194 181507
negascout_t 10 59 222 1011 2311 9476 27946 84480 286373
negascout_kt 10 46 197 590 2012 4532 20312 27993 158697
mtdf 28 232 475 2670 3482 20447 23804 150417 165449
, , test = end43.pos
depth
name 2 3 4 5 6 7 8 9 10
negascout 7 36 137 817 1623 9972 23253 175405 490033
negascout_k 7 31 110 662 1038 6449 10930 71533 227741
negascout_t 7 36 137 847 1515 9055 21982 133849 335105
negascout_kt 7 31 110 815 946 5840 9931 78039 271967
mtdf 75 162 995 2208 6432 19594 63710 192235 576167
, , test = end44.pos
depth
name 2 3 4 5 6 7 8 9 10
negascout 11 56 289 1066 2970 16492 22113 202603 199765
negascout_k 11 47 238 682 2221 9250 20116 100449 145518
negascout_t 11 52 289 1005 2982 14577 19810 172924 150666
negascout_kt 11 43 255 736 2183 9696 17478 104399 109212
mtdf 38 79 520 923 4652 9742 15219 75605 94409
, , test = end45.pos
depth
name 2 3 4 5 6 7 8 9 10
negascout 15 69 244 1148 2709 11993 28158 196678 275525
negascout_k 15 63 242 998 2675 10515 30380 159167 345525
negascout_t 15 69 244 1099 2825 12641 23895 169888 201339
negascout_kt 15 63 242 950 2745 11038 31767 149743 277033
mtdf 32 151 237 1421 2790 11477 23465 140888 163771
, , test = end46.pos
depth
name 2 3 4 5 6 7 8 9 10
negascout 13 85 283 3247 5509 45549 60467 352518 506864
negascout_k 13 80 238 1790 3208 16933 30125 93203 198553
negascout_t 13 85 259 3102 5496 38485 53279 307404 383787
negascout_kt 13 70 237 1962 3074 17963 28074 95152 170354
mtdf 54 327 779 3835 4706 40256 61445 342364 741716
, , test = end47.pos
depth
name 2 3 4 5 6 7 8 9 10
negascout 9 23 233 242 4412 2907 50354 16539 265864
negascout_k 9 23 237 218 2495 2557 35508 14928 170292
negascout_t 9 23 253 213 4536 2650 44470 11196 189768
negascout_kt 9 23 236 196 3402 2486 32863 9442 131268
mtdf 24 35 194 872 1816 7573 22351 40556 70613
, , test = end48.pos
depth
name 2 3 4 5 6 7 8 9 10
negascout 14 54 269 1162 4806 15760 57034 161902 590192
negascout_k 14 48 268 748 3740 8510 40008 78939 392969
negascout_t 14 53 246 1094 4298 14212 54275 136782 508642
negascout_kt 14 48 245 807 3636 7758 41386 76328 347276
mtdf 115 174 3686 1565 33706 11014 318696 87909 3335746
, , test = end49.pos
depth
name 2 3 4 5 6 7 8 9 10
negascout 9 87 175 665 2430 6695 50796 96831 633869
negascout_k 9 76 170 487 2145 5294 30454 89221 199667
negascout_t 9 87 174 656 2332 6067 45934 82621 411842
negascout_kt 9 74 173 486 2280 4719 35268 76532 185430
mtdf 18 59 398 425 4388 5808 43475 52318 436428
, , test = end50.pos
depth
name 2 3 4 5 6 7 8 9 10
negascout 16 58 381 2252 6548 61806 113884 1698516 2008267
negascout_k 16 59 318 1260 4729 18750 74147 278057 1047587
negascout_t 16 58 367 2221 5535 53573 90114 0 1304914
negascout_kt 16 59 319 1399 4528 17254 60574 237079 790573
mtdf 35 107 521 1606 5981 14810 61181 153408 602477
, , test = end51.pos
depth
name 2 3 4 5 6 7 8 9 10
negascout 11 52 300 652 5511 8643 101866 120491 2358758
negascout_k 11 51 272 577 3892 6765 42186 76838 473081
negascout_t 11 52 298 751 5326 9104 90639 110583 0
negascout_kt 11 51 262 579 3906 8330 40806 69717 430606
mtdf 26 47 300 1139 3389 8412 31932 77393 248831
, , test = end52.pos
depth
name 2 3 4 5 6 7 8 9 10
negascout 11 59 253 683 1842 8098 26735 85174 439938
negascout_k 11 50 168 640 1745 7181 21864 71238 303779
negascout_t 11 59 253 709 1704 7328 24112 69626 346116
negascout_kt 11 50 168 670 1638 6773 22229 62285 266658
mtdf 98 239 2778 2591 22377 21733 207041 177547 2162716
, , test = end53.pos
depth
name 2 3 4 5 6 7 8 9 10
negascout 12 89 346 2509 7090 55204 88090 2234507 1190850
negascout_k 12 86 308 1784 4077 13542 59671 148293 549581
negascout_t 12 88 319 2624 6861 52306 86502 0 961771
negascout_kt 12 84 283 2052 4077 15441 58487 147603 537028
mtdf 26 77 329 1186 3397 11747 43672 108713 424288
, , test = end54.pos
depth
name 2 3 4 5 6 7 8 9 10
negascout 11 50 175 531 2409 7285 37752 83641 392862
negascout_k 11 52 179 490 2438 6557 31799 79308 340974
negascout_t 11 50 175 514 2314 6773 33036 73678 301036
negascout_kt 11 51 179 427 2273 6603 28324 71890 267328
mtdf 13 129 186 663 2258 6736 21495 77638 198195
, , test = end55.pos
depth
name 2 3 4 5 6 7 8 9 10
negascout 15 65 404 1248 9188 19798 92140 392794 1662603
negascout_k 15 61 358 953 5513 12038 80770 157799 951606
negascout_t 15 65 408 1148 9117 17778 87351 304024 1364431
negascout_kt 15 61 360 905 6644 12260 78871 147038 837889
mtdf 26 62 425 1455 4854 17477 65316 379933 615088
, , test = end56.pos
depth
name 2 3 4 5 6 7 8 9 10
negascout 10 45 311 757 3912 12865 57796 140488 1530114
negascout_k 10 37 252 541 2067 8742 25142 94894 492491
negascout_t 10 45 317 742 3509 12036 51373 113677 1235365
negascout_kt 10 37 247 534 1841 8398 21623 80730 545025
mtdf 56 108 877 1530 8107 14727 110192 142411 1358622
, , test = end57.pos
depth
name 2 3 4 5 6 7 8 9 10
negascout 9 52 173 1432 1739 19135 13780 285120 168055
negascout_k 9 38 175 1049 1675 7488 14165 98433 164247
negascout_t 9 52 173 1530 1940 17446 14387 266146 140052
negascout_kt 9 38 172 1163 1844 7637 15122 104688 154033
mtdf 31 160 344 1521 2993 13571 26000 131647 242334
, , test = end58.pos
depth
name 2 3 4 5 6 7 8 9 10
negascout 14 172 303 4253 6287 61713 81874 882182 893434
negascout_k 14 111 262 1723 3872 25178 44528 357158 573485
negascout_t 14 172 303 3644 6467 55475 71662 784289 733810
negascout_kt 14 98 262 1657 4426 23251 49307 364851 532404
mtdf 34 85 426 2009 4704 28404 48100 333251 561307
, , test = end59.pos
depth
name 2 3 4 5 6 7 8 9 10
negascout 12 46 199 653 2777 14461 34540 261477 252083
negascout_k 12 47 197 541 2509 9757 27143 89008 225199
negascout_t 12 46 199 644 2475 12611 27142 141370 173857
negascout_kt 12 47 197 539 2396 9869 24011 73875 177330
mtdf 32 120 403 1202 3382 12808 27145 102514 201141
実行時間
xtabs(time ~ name + depth + test, data=data)
, , test = end40.pos
depth
name 2 3 4 5 6 7 8 9 10
negascout 146 290 496 725 1261 1963 5291 8146 33362
negascout_k 162 294 495 725 1244 1993 4737 9275 29403
negascout_t 181 301 496 709 1262 1836 4309 6832 24828
negascout_kt 160 299 507 761 1249 1994 5221 8312 27056
mtdf 340 470 721 933 1637 2272 5530 8861 25979
, , test = end41.pos
depth
name 2 3 4 5 6 7 8 9 10
negascout 173 496 605 1667 1977 8624 10067 120363 95956
negascout_k 174 463 578 1429 1749 6304 7540 86696 59828
negascout_t 173 508 604 1633 1961 7853 7756 108516 60461
negascout_kt 178 473 591 1433 1909 6113 6932 88807 48840
mtdf 191 481 720 1378 2644 7353 14772 43787 102702
, , test = end42.pos
depth
name 2 3 4 5 6 7 8 9 10
negascout 167 424 645 1352 1731 6502 11983 44883 124855
negascout_k 172 374 597 1037 1587 2970 9065 14075 58752
negascout_t 170 423 623 1444 1761 5906 10800 40040 93727
negascout_kt 175 384 606 1066 1679 3370 8448 13988 51949
mtdf 266 613 777 1993 2076 8051 9112 49056 51157
, , test = end43.pos
depth
name 2 3 4 5 6 7 8 9 10
negascout 177 316 553 1149 1696 6324 11723 83606 186748
negascout_k 183 332 541 1080 1391 4197 6140 32211 93706
negascout_t 184 326 603 1165 1729 5298 10554 58282 131350
negascout_kt 190 313 544 1231 1365 4115 5665 34501 117310
mtdf 403 505 1090 1638 3056 7782 20668 60042 169510
, , test = end44.pos
depth
name 2 3 4 5 6 7 8 9 10
negascout 189 388 750 1338 2393 8659 10858 85144 80372
negascout_k 196 370 702 1166 1941 5401 9315 43392 57375
negascout_t 193 396 757 1315 2350 7564 9461 71131 60152
negascout_kt 191 366 729 1193 1988 5652 8475 44551 44293
mtdf 289 420 872 1169 2545 5127 7184 28775 36413
, , test = end45.pos
depth
name 2 3 4 5 6 7 8 9 10
negascout 204 457 634 1568 1974 7181 12158 87261 99123
negascout_k 208 444 658 1469 1980 6405 12799 71853 120692
negascout_t 213 472 648 1536 2033 7233 9805 73823 69151
negascout_kt 205 451 674 1441 2050 6774 13111 66399 96151
mtdf 259 562 647 1578 1938 6295 9632 58944 55833
, , test = end46.pos
depth
name 2 3 4 5 6 7 8 9 10
negascout 193 484 741 2420 3799 19658 29535 132102 231939
negascout_k 200 457 697 1710 2632 7765 15340 36120 89377
negascout_t 205 524 710 2343 3764 16092 25815 113883 172976
negascout_kt 219 456 705 1829 2637 8310 14298 35768 76634
mtdf 312 692 937 2090 2706 11933 21978 85995 227521
, , test = end47.pos
depth
name 2 3 4 5 6 7 8 9 10
negascout 189 277 708 704 3187 2443 25664 7825 138700
negascout_k 185 274 739 687 2312 2133 17950 7385 72540
negascout_t 195 270 758 667 3258 2127 21355 5521 78977
negascout_kt 189 280 740 647 2957 2105 16781 4966 56960
mtdf 251 308 682 985 1873 3420 11653 13291 30711
, , test = end48.pos
depth
name 2 3 4 5 6 7 8 9 10
negascout 188 425 682 1623 2927 9997 21834 80545 213768
negascout_k 194 418 698 1286 2544 5719 15166 39882 134581
negascout_t 193 422 676 1549 2749 8907 20961 67341 184257
negascout_kt 197 417 719 1388 2550 5398 16376 39458 120786
mtdf 406 569 1609 1696 8698 6329 70877 40292 793007
, , test = end49.pos
depth
name 2 3 4 5 6 7 8 9 10
negascout 176 486 627 1114 2289 4473 24078 41946 264479
negascout_k 187 460 650 1005 2166 3613 15768 39655 88779
negascout_t 179 501 638 1105 2223 3883 21157 34196 168660
negascout_kt 195 475 660 1010 2344 3393 18102 33940 83500
mtdf 242 382 797 921 2991 3477 18092 24142 160935
, , test = end50.pos
depth
name 2 3 4 5 6 7 8 9 10
negascout 204 442 826 2346 3672 36083 45100 905580 693858
negascout_k 211 455 753 1726 2984 11536 28311 140752 364351
negascout_t 207 460 784 2383 3266 30463 33674 0 443437
negascout_kt 213 464 761 1830 2905 10904 22865 121707 272435
mtdf 288 530 852 1985 3388 9266 22517 79284 202871
, , test = end51.pos
depth
name 2 3 4 5 6 7 8 9 10
negascout 211 399 822 1149 4117 5536 55090 56954 1165039
negascout_k 214 387 800 1084 3100 4517 24468 36420 211630
negascout_t 211 410 856 1231 4000 5573 47679 50778 0
negascout_kt 218 393 788 1102 3167 5198 20978 32365 200718
mtdf 276 365 779 1289 2863 4561 15748 29685 107617
, , test = end52.pos
depth
name 2 3 4 5 6 7 8 9 10
negascout 206 432 737 1185 1827 5641 13071 45879 195934
negascout_k 193 406 613 1167 1692 5179 10211 39142 122034
negascout_t 207 428 750 1216 1771 5144 11997 36647 144741
negascout_kt 196 421 611 1232 1729 4937 11026 33539 109840
mtdf 440 629 1703 1993 7584 9989 54343 71080 541046
, , test = end53.pos
depth
name 2 3 4 5 6 7 8 9 10
negascout 210 500 901 2407 4884 31277 44704 1201767 553896
negascout_k 210 505 837 1891 3298 7955 30283 69314 262176
negascout_t 211 528 878 2504 4764 28718 43612 0 443394
negascout_kt 214 504 828 2102 3293 8745 30791 67698 253523
mtdf 290 451 802 1479 2718 6192 20951 45044 174004
, , test = end54.pos
depth
name 2 3 4 5 6 7 8 9 10
negascout 191 401 621 1095 2191 5277 18367 45771 168647
negascout_k 190 417 607 1066 2069 4777 15367 41653 145154
negascout_t 186 423 623 1089 2153 4653 15757 36421 126648
negascout_kt 193 429 626 1016 2078 4743 13757 37260 112983
mtdf 201 548 633 1131 2049 4325 10279 35448 81802
, , test = end55.pos
depth
name 2 3 4 5 6 7 8 9 10
negascout 228 451 867 1625 5865 11516 47866 191687 776131
negascout_k 229 452 879 1466 3990 7497 39249 79331 440569
negascout_t 232 468 887 1541 5690 9876 42431 138889 635360
negascout_kt 236 464 881 1455 4697 7738 38621 71558 397801
mtdf 263 423 880 1535 3578 8308 30333 147236 265348
, , test = end56.pos
depth
name 2 3 4 5 6 7 8 9 10
negascout 201 366 849 1204 3260 8014 31708 69252 806823
negascout_k 206 354 780 1057 2095 5503 13382 45388 247042
negascout_t 207 373 862 1199 2960 7195 27368 53603 606342
negascout_kt 208 354 804 1076 1963 5348 11614 37573 277568
mtdf 335 502 1111 1499 4333 7058 40382 52695 465928
, , test = end57.pos
depth
name 2 3 4 5 6 7 8 9 10
negascout 177 421 626 1772 1743 12042 7732 145348 74015
negascout_k 180 369 646 1480 1775 4947 7565 46505 73514
negascout_t 190 436 636 1795 1883 10308 7669 133608 61528
negascout_kt 185 373 655 1574 1906 5102 8252 49164 69514
mtdf 296 587 734 1641 2222 7370 11412 56582 90320
, , test = end58.pos
depth
name 2 3 4 5 6 7 8 9 10
negascout 237 651 855 3380 4692 32901 44719 449075 462755
negascout_k 244 584 809 1929 3465 13789 26732 171201 306630
negascout_t 238 693 847 3107 4734 29215 38682 396939 367758
negascout_kt 251 557 830 1918 3774 13085 29430 178562 287312
mtdf 323 491 940 1865 3498 12176 23809 124279 249729
, , test = end59.pos
depth
name 2 3 4 5 6 7 8 9 10
negascout 176 391 601 1270 2129 9195 15964 137736 108460
negascout_k 179 401 620 1092 2034 6278 12079 45030 88573
negascout_t 179 404 623 1228 2003 7652 12094 71868 70125
negascout_kt 184 413 623 1116 2004 6419 10978 38308 70561
mtdf 273 527 751 1520 2322 6888 11698 44938 76771
概ね高速であるが、ときどき非常に遅い時がある。
[1] Plaat and University of Alberta. Dept. of Computing Science. A new paradigm for minimax search. (1994)
0 件のコメント:
コメントを投稿