class AdversarialNode(State):
def _init_(self, value, name, isMax, children = []):
self._name = name
self._utility = value
self._isMax = isMax
self._children = children
self._move = 1
self._action = None
def isLeaf(self):
return len(self._children) == 0
def isMax(self):
return self._isMax
def isNextAgentMax(self):
return not self._isMax
def addChild(self,child):
self._children.append(child);
def getAction(self):
return self._action
def _str_(self):
s = "Name is %s, value is %d" %(self._name,self._utility)
s += "\n children are "
for ch in range(len(self._children)):
s+= str(self._children[ch])
return s
from abc import abstractmethod
class Game(object):
@abstractmethod
def _init_(self, params): pass
@abstractmethod
def getInitialState(self):pass
@abstractmethod
def getPlayer(self,state):pass
@abstractmethod
def getActions(self,state): pass
@abstractmethod
def getResult(self, state, action): pass
@abstractmethod
def terminalTest(self,state): pass
@abstractmethod
def utility(self,state,player): pass
@abstractmethod
def getAgentCount(self): pass
class State(object):
def _init_(self, params):pass
def isMax(self): pass
def isNextAgentMax(self): pass
def getAction(self):pass
import sys
class MinimaxTreeGame(Game):
def _init_(self):
bottom1 = [AdversarialNode(3,"E",True,[]),
AdversarialNode(12,"F",True,[]),
AdversarialNode(8,"G",True,[])]
bottom2 = [AdversarialNode(2,"H",True,[]),
AdversarialNode(4,"I",True,[]),
AdversarialNode(6,"J",True,[])]
bottom3 = [AdversarialNode(14,"K",True,[]),
AdversarialNode(5,"L",True,[]),
AdversarialNode(2,"M",True,[])]
b = AdversarialNode(-sys.maxsize-1,"B",False,bottom1)
c = AdversarialNode(-sys.maxsize-1,"C",False,bottom2)
d = AdversarialNode(-sys.maxsize-1,"D",False,bottom3)
a = AdversarialNode(-sys.maxsize-1,"A",True,[b,c,d])
self._root = a
def getInitialState(self):
return self._root
def getPlayer(self,state):
return state.isMax()
def getActions(self,state):
return [x for x in range(len(state._children))]
def getResult(self, state, action):
return state._children[action]
def terminalTest(self,state):
return state.isLeaf()
def utility(self,state,player):
return state._value
def getAgentCount(self):
return 2
def printState(self,state):
toPrintNodes = []
toPrintNodes.append(state)
while len(toPrintNodes) > 0:
node = toPrintNodes[0]
del toPrintNodes[0]
print("Name = %s, value = %d"%(node._name,node._utility))
toPrintNodes += node._children
class SimpleMinimax(object):
def _init_(self, game, listeners = []):
self._game = game
self.listeners = listeners
self._expandedNodes = 0
self._duplicateStates = {}
def minimax_decision(self,state):
self._duplicateStates[str(state)] = state
if self._game.terminalTest(state):
return state._utility
if state.isMax():
return self.maxvalue(state)
else:
return self.minvalue(state)
def minvalue( self,state):
ss = str(state)
if ss in self._duplicateStates and self._duplicateStates[ss]._utility > state._utility:
return state._utility
else:
self._duplicateStates[str(state)] = state
self._expandedNodes += 1
retValue = 1000000000000
# player = self._game.getPlayer(state)
actions = self._game.getActions(state)
for action in actions:
tempValue = self.minimax_decision(self._game.getResult(state,action))
if tempValue < retValue:
retValue = tempValue
state._utility = retValue
state._action = action
return retValue
def maxvalue(self,state):
ss = str(state)
if ss in self._duplicateStates and self._duplicateStates[ss]._utility > state._utility:
return state._utility
else:
self._duplicateStates[str(state)] = state
self._expandedNodes += 1
retValue=-1000000000000
# player = self._game.getPlayer(state)
actions = self._game.getActions(state)
for action in actions:
tempValue = self.minimax_decision(self._game.getResult(state,action))
if tempValue > retValue:
retValue = tempValue
state._utility = retValue
state._action = action
return retValue
if _name_ == "_main_":
game = MinimaxTreeGame()
minimax = SimpleMinimax(game)
initialState = game.getInitialState()
minimax.minimax_decision(initialState)
game.printState(initialState)
