95 lines
2.5 KiB
Python
95 lines
2.5 KiB
Python
import random
|
|
|
|
|
|
class GameNode(object):
|
|
"""docstring for GameNode"""
|
|
|
|
def __init__(self, state, parent):
|
|
super(GameNode, self).__init__()
|
|
self.state = state
|
|
self.parent = parent
|
|
|
|
self.hits = 0
|
|
self.misses = 0
|
|
self.totalTrials = 0
|
|
|
|
def backPropagate(self, simulation):
|
|
if (simulation > 0):
|
|
self.hits += 1
|
|
elif (simulation < 0):
|
|
self.misses += 1
|
|
self.totalTrials += 1
|
|
|
|
if self.parent:
|
|
self.parent.backPropagate(-simulation)
|
|
|
|
def childPotential(self, child):
|
|
w = child.misses
|
|
n = child.totalTrials
|
|
|
|
# Chosen empirically
|
|
c = math.sqrt(2)
|
|
t = self.totalTrials
|
|
|
|
return (w / n) + (c * math.sqrt(log(t) / n))
|
|
|
|
def runSimulation(self):
|
|
print(self.state)
|
|
self.backPropagate(self.simulate())
|
|
|
|
def simulate(self):
|
|
state = self.state
|
|
|
|
while not state.gameOver():
|
|
moves = state.getPossibleMoves()
|
|
randomMove = random.choice(moves)
|
|
state = state.playMove(randomMove)
|
|
|
|
return self.state.result(state)
|
|
|
|
def getChildren(self):
|
|
possibleMoves = self.state.getPossibleMoves()
|
|
children = []
|
|
|
|
for move in possibleMoves:
|
|
newState = self.state.playMove(move)
|
|
childNode = GameNode(newState, self.state)
|
|
children.append(childNode)
|
|
|
|
return children
|
|
|
|
def chooseChild(self):
|
|
# Define children nodes
|
|
try:
|
|
self.children
|
|
except Exception as e:
|
|
self.children = self.getChildren()
|
|
|
|
if(len(self.children) == 0):
|
|
self.runSimulation()
|
|
else:
|
|
unexplored = []
|
|
|
|
# Get all unexplored nodes
|
|
for child in self.children:
|
|
if (child.totalTrials == 0):
|
|
unexplored.append(child)
|
|
|
|
# Pick a random unexplored node
|
|
# and run the simulation on it
|
|
if (len(unexplored) > 0):
|
|
random.choice(unexplored).runSimulation()
|
|
else:
|
|
# Find the best child
|
|
bestChild = self.children[0]
|
|
bestPotential = self.childPotential(bestChild)
|
|
|
|
for child in self.children:
|
|
potential = self.childPotential(child)
|
|
|
|
if (potential > bestPotential):
|
|
bestPotential = potential
|
|
bestChild = child
|
|
|
|
bestChild.chooseChild()
|