Alpha-Beta Dammen: door Tom Lauriks en Carsten van Weelden

Testresultaten.

Uit de testresultaten blijkt dat Alpha-Beta pruning wel duidelijke effecten heeft op het aantal bezochte states zodra de zoekdiepte hoger dan vier wordt. Maar in sommige gevallen, vooral gevallen waarbij er niet veel stenen meer op het bord aanwezig zijn, zorgen de extra berekeningen ervoor dat er geen reële tijdswinst is bij praktische zoekdieptes. (We hebben ondervonden dat een zoekdiepte van vijf nog net in acceptabele denktijden resulteert.)
Verder hebben we ondervonden dat de hekstellingen heuristiek computationeel eigenlijk veel te zwaar is en voor lange wachttijden resulteert. Vergelijk bijvoorbeeld de tijden tussen het vinden van een zet bij teststate3 met en zonder deze heuristiek. Zonder deze heuristiek gebeurt dat bijna instantieus, maar met de heuristiek is er een lange rekentijd.
Deze heuristiek zou beter vervangen kunnen worden. Het is (naar onzer inzicht) namelijk ook niet goed mogelijk om het algoritme efficiënter te maken.
Verder hebben we ondervonden dat een diepte onder de drie voor slechte spel resultaten zorgt. Dan worden situaties waarbij met 1 zet een val kan worden gezet namelijk niet herkend. Bij een diepte boven de drie zijn er echter niet echt waarneembare veranderingen in het spelgedrag, behalve bij het eindspel. Hierbij kan er soms nog net gewonnen worden bij een diepte van vijf, terwijl bij een diepte van drie de verkeerde zet wordt gevonden. Dit gebeurt voornamelijk in gevallen waarbij beide spelers nog maar 1 steen hebben, die ongeveer 3 tot 6 vakjes van elkaar vandaan staan.

Testing Minimax state 1 heuristic piece dif.:
Testing at depth: 0
State counter: 1
% 19 inferences, 0.00 CPU in 0.00 seconds (0% CPU, Infinite Lips)
Testing at depth: 1
State counter: 11
% 5,799 inferences, 0.00 CPU in 0.00 seconds (0% CPU, Infinite Lips)
Testing at depth: 2
State counter: 99
% 64,210 inferences, 0.03 CPU in 0.03 seconds (99% CPU, 2140333 Lips)
Testing at depth: 3
State counter: 708
% 421,374 inferences, 0.20 CPU in 0.25 seconds (79% CPU, 2106870 Lips)
Testing at depth: 4
State counter: 4673
% 2,972,489 inferences, 1.37 CPU in 1.41 seconds (97% CPU, 2169700 Lips)
Testing at depth: 5
State counter: 29288
% 17,653,624 inferences, 8.24 CPU in 8.35 seconds (99% CPU, 2142430 Lips)
Testing at depth: 6
State counter: 183331
% 114,863,366 inferences, 52.85 CPU in 53.44 seconds (99% CPU, 2173384 Lips)
Testing at depth: 7
State counter: 1125104
% 673,688,046 inferences, 306.49 CPU in 320.73 seconds (96% CPU, 2198075 Lips)

Testing AB state 1 A= -100, B = 100 heuristic piece dif.:
Testing at depth: 0
State counter: 1
% 19 inferences, 0.00 CPU in 0.00 seconds (0% CPU, Infinite Lips)
Testing at depth: 1
State counter: 11
% 5,878 inferences, 0.01 CPU in 0.00 seconds (381% CPU, 587800 Lips)
Testing at depth: 2
State counter: 99
% 64,990 inferences, 0.02 CPU in 0.03 seconds (68% CPU, 3249500 Lips)
Testing at depth: 3
State counter: 708
% 426,726 inferences, 0.20 CPU in 0.26 seconds (78% CPU, 2133630 Lips)
Testing at depth: 4
State counter: 4673
% 3,007,348 inferences, 1.34 CPU in 1.38 seconds (97% CPU, 2244290 Lips)
Testing at depth: 5
State counter: 24476
% 15,320,383 inferences, 6.92 CPU in 7.00 seconds (99% CPU, 2213928 Lips)
Testing at depth: 6
State counter: 131284
% 86,044,217 inferences, 38.33 CPU in 39.61 seconds (97% CPU, 2244827 Lips)
Testing at depth: 7
State counter: 708527
% 446,683,295 inferences, 200.04 CPU in 212.93 seconds (94% CPU, 2232970 Lips)

Testing MiniMax state 3 heuristic piece dif. + hekstellingen:
Testing at depth: 0
State counter: 1
% 1,499,496 inferences, 0.58 CPU in 0.59 seconds (99% CPU, 2585338 Lips)
Testing at depth: 1
State counter: 3
% 5,304,318 inferences, 2.11 CPU in 2.15 seconds (98% CPU, 2513895 Lips)
Testing at depth: 2
State counter: 5
% 713,356 inferences, 0.28 CPU in 0.32 seconds (87% CPU, 2547700 Lips)
Testing at depth: 3
State counter: 13
% 6,968,866 inferences, 2.82 CPU in 2.86 seconds (98% CPU, 2471229 Lips)
Testing at depth: 4
State counter: 57
% 42,109,021 inferences, 16.69 CPU in 16.78 seconds (99% CPU, 2523009 Lips)
Testing at depth: 5
State counter: 350
% 291,750,272 inferences, 115.21 CPU in 115.53 seconds (100% CPU, 2532335 Lips)
Testing at depth: 6
State counter: 1971
% 1,499,818,029 inferences, 594.92 CPU in 601.84 seconds (99% CPU, 2521042 Lips)
Testing at depth: 7
State counter: 12643
% -1,856,696,988 inferences, 4373.82 CPU in 4500.16 seconds (97% CPU, -424502 Lips)

Testing AB state 3 A = -100, B = 100 heuristic piece dif. + hekstellingen:
Testing at depth: 0
State counter: 1
% 1,499,463 inferences, 0.60 CPU in 0.60 seconds (99% CPU, 2499105 Lips)
Testing at depth: 1
State counter: 3
% 5,304,253 inferences, 2.15 CPU in 2.18 seconds (98% CPU, 2467094 Lips)
Testing at depth: 2
State counter: 5
% 713,358 inferences, 0.29 CPU in 0.32 seconds (90% CPU, 2459855 Lips)
Testing at depth: 3
State counter: 13
% 6,968,927 inferences, 2.82 CPU in 2.86 seconds (98% CPU, 2471251 Lips)
Testing at depth: 4
State counter: 32
% 8,046,233 inferences, 3.27 CPU in 3.30 seconds (99% CPU, 2460622 Lips)
Testing at depth: 5
State counter: 183
% 102,891,150 inferences, 41.73 CPU in 41.86 seconds (100% CPU, 2465640 Lips)
Testing at depth: 6
State counter: 737
% 324,763,201 inferences, 131.43 CPU in 131.76 seconds (100% CPU, 2470997 Lips)
Testing at depth: 7
State counter: 3183
% -1,943,363,330 inferences, 953.85 CPU in 993.20 seconds (96% CPU, -2037389 Lips)

Testing MiniMax state 3 heuristic piece dif.:
Testing at depth: 0
State counter: 1
% 19 inferences, 0.00 CPU in 0.00 seconds (0% CPU, Infinite Lips)
Testing at depth: 1
State counter: 3
% 1,021 inferences, 0.00 CPU in 0.00 seconds (0% CPU, Infinite Lips)
Testing at depth: 2
State counter: 5
% 1,701 inferences, 0.00 CPU in 0.00 seconds (0% CPU, Infinite Lips)
Testing at depth: 3
State counter: 13
% 3,011 inferences, 0.00 CPU in 0.00 seconds (0% CPU, Infinite Lips)
Testing at depth: 4
State counter: 57
% 10,255 inferences, 0.00 CPU in 0.00 seconds (0% CPU, Infinite Lips)
Testing at depth: 5
State counter: 350
% 57,148 inferences, 0.03 CPU in 0.03 seconds (112% CPU, 1904933 Lips)
Testing at depth: 6
State counter: 1971
% 311,529 inferences, 0.16 CPU in 0.20 seconds (80% CPU, 1947056 Lips)
Testing at depth: 7
State counter: 12643
% 2,031,269 inferences, 0.98 CPU in 1.02 seconds (96% CPU, 2072723 Lips)

Testing AB state 3 A = -100, B = 100, heuristic piece dif.:
Testing at depth: 0
State counter: 1
% 19 inferences, 0.00 CPU in 0.00 seconds (0% CPU, Infinite Lips)
Testing at depth: 1
State counter: 3
% 1,022 inferences, 0.00 CPU in 0.00 seconds (0% CPU, Infinite Lips)
Testing at depth: 2
State counter: 5
% 1,703 inferences, 0.00 CPU in 0.00 seconds (0% CPU, Infinite Lips)
Testing at depth: 3
State counter: 13
% 3,072 inferences, 0.00 CPU in 0.00 seconds (0% CPU, Infinite Lips)
Testing at depth: 4
State counter: 57
% 10,617 inferences, 0.01 CPU in 0.01 seconds (181% CPU, 1061700 Lips)
Testing at depth: 5
State counter: 350
% 59,720 inferences, 0.02 CPU in 0.03 seconds (69% CPU, 2986000 Lips)
Testing at depth: 6
State counter: 1959
% 325,059 inferences, 0.17 CPU in 0.22 seconds (76% CPU, 1912112 Lips)
Testing at depth: 7
State counter: 12582
% 2,119,388 inferences, 1.02 CPU in 1.05 seconds (97% CPU, 2077831 Lips)