Author: Dan Andersson
Date: 17:05:05 03/31/04
Hope this program runs correctly:
-- Written in Lua 5.1 work0, should run in Lua 5.x
-- Lua is available at http://www.lua.org/
-- A good second stop is http://lua-users.org/
-- that has tutorials. And links to pre-compiled
-- binaries for different platforms.
-- Run with the command $prompt lua progname.lua
-- Dan Andersson 2004-04-01
-- Initialize the pseudo random number generator
math.randomseed( os.time() )
math.random(); math.random(); math.random()
-- done. :-)
-- This initialization is from http://lua-users.org/wiki/MathLibraryTutorial
-- Caveat! There are better random generators out there
nodes = 0
minply = 2 -- must be even
maxply = 31
step = 2 -- must be even
maxiter = 10
function even(number)
if math.mod(number,2) == 0 then
return true
else
return false
end
end
-- Function to transform the distribution of values
function distribution(position)
return position -- Currently all values are unique
-- position is the binary value of the path tuple
end
-- Binary Alpha-Beta search
-- this one only works on even depths
function AlphaBeta(position, depth, alpha, beta)
local move
nodes = nodes + 1
if depth == 0 then return distribution(position) end
move = math.random(0,1)
val = -AlphaBeta(2 * position + move, depth - 1, -beta, -alpha)
if (val >= beta) then return beta end
if (val > alpha) then alpha = val end
move = math.abs(move - 1)
val = -AlphaBeta(2 * position + move, depth - 1, -beta, -alpha)
if (val >= beta) then return beta end
if (val > alpha) then alpha = val end
return alpha
end
assert(even(minply) and even(step), "minply and step must be even")
for depth = minply, maxply, step do
for i = 1, 10 do
nodes = 0
minimax = 2^depth
abnodes = math.sqrt(minimax)
print(AlphaBeta(0, depth,-1,2^depth + 1), depth, nodes, nodes/minimax,
nodes/abnodes)
end
end
Sample small run:
11184810 24 271041 0.016155302524567 66.172119140625
11184810 24 43485 0.0025919079780579 10.616455078125
11184810 24 73425 0.0043764710426331 17.926025390625
11184810 24 217481 0.012962877750397 53.095947265625
11184810 24 320444 0.019099950790405 78.2333984375
11184810 24 462298 0.027555108070374 112.86572265625
11184810 24 75023 0.0044717192649841 18.316162109375
11184810 24 402759 0.024006307125092 98.329833984375
11184810 24 312935 0.018652379512787 76.400146484375
11184810 24 45190 0.0026935338973999 11.03271484375
44739242 26 615089 0.0091655403375626 75.084106445313
44739242 26 553616 0.0082495212554932 67.580078125
44739242 26 799802 0.011917978525162 97.632080078125
44739242 26 365329 0.0054438263177872 44.595825195313
44739242 26 420228 0.0062618851661682 51.29736328125
44739242 26 904585 0.013479366898537 110.42297363281
44739242 26 1057092 0.015751898288727 129.03955078125
44739242 26 148841 0.0022179037332535 18.169067382813
44739242 26 332332 0.0049521327018738 40.56787109375
44739242 26 457586 0.006818562746048 55.857666015625
178956970 28 3509400 0.013073533773422 214.19677734375
178956970 28 1100111 0.0040982328355312 67.145446777344
178956970 28 328751 0.0012246929109097 20.065368652344
178956970 28 475738 0.0017722621560097 29.036743164063
178956970 28 1233768 0.0045961439609528 75.30322265625
178956970 28 1277071 0.0047574602067471 77.946228027344
178956970 28 1584855 0.0059040449559689 96.731872558594
178956970 28 1426565 0.0053143687546253 87.070617675781
178956970 28 1716825 0.0063956715166569 104.78668212891
178956970 28 1451030 0.0054055079817772 88.563842773438
715827882 30 3808583 0.0035470193251967 116.22872924805
715827882 30 349446 0.00032544694840908 10.664245605469
715827882 30 3732839 0.0034764772281051 113.91720581055
715827882 30 812952 0.0007571205496788 24.809326171875
715827882 30 4064015 0.0037849089130759 124.02389526367
715827882 30 4674993 0.0043539265170693 142.66946411133
715827882 30 2064967 0.001923150382936 63.017791748047
715827882 30 2578748 0.0024016462266445 78.697143554688
715827882 30 4620226 0.0043029207736254 140.99810791016
715827882 30 2202568 0.0020513013005257 67.217041015625
2863311530 32 8168259 0.0019018210005015 124.63774108887
2863311530 32 4717838 0.0010984572581947 71.988494873047
2863311530 32 5798345 0.0013500323984772 88.475723266602
2863311530 32 12448041 0.0028982853982598 189.94203186035
2863311530 32 6687763 0.0015571161638945 102.04716491699
2863311530 32 6669336 0.0015528257936239 101.76599121094
2863311530 32 5199660 0.0012106401845813 79.340515136719
2863311530 32 8104014 0.0018868627958 123.65744018555
2863311530 32 9545910 0.0022225803695619 145.65902709961
2863311530 32 4834027 0.0011255096178502 73.76139831543
MvH Dan Andersson
This page took 0.01 seconds to execute
Last modified: Thu, 15 Apr 21 08:11:13 -0700
Current Computer Chess Club Forums at Talkchess. This site by Sean Mintz.