Added Negamax

Yonaba · Yonaba · commit 1436d754b018 · 2014-03-19T21:49:18.000Z
diff --git a/Negamax/Lua/Yonaba/handlers/tree_handler.lua b/Negamax/Lua/Yonaba/handlers/tree_handler.lua
@@ -0,0 +1,52 @@
+-- Search tree class handler implementation
+
+local PATH = (...):gsub('handlers.tree_handler$','')
+local class = require (PATH .. '.utils.class')
+
+
+local tree = class ()
+
+-- Tree initialization
+function tree:initialize()
+  self.nodes = {}
+end
+
+-- Adds a node in the tree
+function tree:addNode(name, parent, value)
+  assert(not self.nodes[name], 'node already exist')
+  local node = {
+    name = name, value = value,
+    parent = parent, children = {}
+  }
+  if parent then
+    parent = self:getNode(parent)
+    assert(parent, 'parent not found')
+    table.insert(parent.children, node)
+  end
+  if not self.head then self.head = node end
+  table.insert(self.nodes, node)
+end
+
+-- Get the node by its name
+function tree:getNode(name)
+  for i, node in ipairs(self.nodes) do
+    if node.name == name then return node end
+  end
+end
+
+-- Checks if a given node is terminal (leaf) in the search tree
+function tree:isLeaf(node)
+  return #node.children == 0
+end
+
+-- Returns the node value
+function tree:heuristic(node)
+  return node.value
+end
+
+-- Returns the node's children
+function tree:children(node)
+  return node.children
+end
+
+return tree
diff --git a/Negamax/Lua/Yonaba/negamax.lua b/Negamax/Lua/Yonaba/negamax.lua
@@ -0,0 +1,27 @@
+-- Negamax search implementation
+-- See: http://en.wikipedia.org/wiki/Negamax
+
+-- Internal recursive Minimax search
+local function negamax(tree, node, depth, flag)
+  if depth == 0 or tree:isLeaf(node) then
+    return tree:heuristic(node) * flag
+  end
+  local children = tree:children(node)
+  local bestScore = -math.huge
+  for i, child in ipairs(children) do
+    bestScore = math.max(bestScore, -negamax(tree, child, depth - 1, -flag))
+  end
+  return bestScore
+end
+
+-- Performs Negamax search
+-- node  : the node from where to start the search, usually the head node
+-- tree  : the search tree
+-- depth : the maximum depth of search
+-- flag  : the player (+1) or the opponent (-1)
+return function(node, tree, depth, flag)
+  flag = (flag / math.abs(flag)) -- Gets the sign (either +1 or -1)
+  return negamax(tree, node, depth, flag)
+end
+
+
diff --git a/Negamax/Lua/Yonaba/negamax_test.lua b/Negamax/Lua/Yonaba/negamax_test.lua
@@ -0,0 +1,48 @@
+-- Tests for alpha_beta_pruning.lua
+local negamax = require 'negamax'
+
+local total, pass = 0, 0
+
+local function dec(str, len)
+  return #str < len
+     and str .. (('.'):rep(len-#str))
+      or str:sub(1,len)
+end
+
+local function run(message, f)
+  total = total + 1
+  local ok, err = pcall(f)
+  if ok then pass = pass + 1 end
+  local status = ok and 'PASSED' or 'FAILED'
+  print(('%02d. %68s: %s'):format(total, dec(message,68), status))
+end
+
+run('Testing Negamax', function()
+  local tree = require 'handlers.tree_handler'
+
+  local t = tree()
+  t:addNode('A',nil,0)
+  t:addNode('B1','A',0)
+  t:addNode('B2','A',0)
+  t:addNode('B3','A',0)
+
+  t:addNode('C1','B1',4)
+  t:addNode('C2','B1',12)
+  t:addNode('C3','B1',7)
+
+  t:addNode('C4','B2',10)
+  t:addNode('C5','B2',5)
+  t:addNode('C6','B2',6)
+
+  t:addNode('C7','B3',1)
+  t:addNode('C8','B3',2)
+  t:addNode('C9','B3',3)
+
+  local head = t:getNode('A')
+  assert(negamax(head, t, 3,  1) ==  5)
+  assert(negamax(head, t, 3, -1) == -3)
+end)
+
+print(('-'):rep(80))
+print(('Total : %02d: Pass: %02d - Failed : %02d - Success: %.2f %%')
+  :format(total, pass, total-pass, (pass*100/total)))
diff --git a/Negamax/Lua/Yonaba/utils/class.lua b/Negamax/Lua/Yonaba/utils/class.lua
@@ -0,0 +1,15 @@
+-- Minimalistic class implementation
+
+local class = function(attr)
+  local klass = attr or {}
+  klass.__index = klass
+  klass.__call = function(_,...) return klass:new(...) end
+  function klass:new(...)
+    local instance = setmetatable({}, klass)
+    if klass.initialize then klass.initialize(instance, ...) end
+    return instance
+  end
+  return setmetatable(klass,{__call = klass.__call})
+end
+
+return class
diff --git a/Negamax/tags b/Negamax/tags
@@ -0,0 +1 @@
+Search,Graphs,Minimax
