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()