# import MCTS
import math
from copy import deepcopy
from time import clock
from random import choice

from GameState import GameState

class Algo: # A class for defining algorithms used (minimax and alpha-beta pruning)
    
    def miniMax(State, Ply_num): # Function for the minimax algorithm

        for i in range(State.Current.dimY):
            for j in range(State.Current.dimX):
                if State.Current.Mat[i][j] == ' ' and (j, i) not in State.children:
                    State.Make(j, i, True)
                    if Ply_num < 2:
                        return (i, j)

        Minimum_Score = 1000
        i = 0

        
        j = 0
        for k, z in State.children.items():
            Result = Algo.Maximum(z, Ply_num - 1, Minimum_Score)
            if Minimum_Score > Result:
                Minimum_Score = Result
                i = k[0]
                j = k[1]

        return (i, j)


    def Maximum(State, Ply_num, Alpha): # Alpha-beta pruning function for taking care of Alpha values
        if Ply_num == 0:
            return State.CurrentScore

        for i in range(State.Current.dimY):
            for j in range(State.Current.dimX):
                if State.Current.Mat[i][j] == ' ' and (j, i) not in State.children:
                    State.Make(j, i, False)

        Maximum_Score = -1000
        i = 0
        j = 0
        for k, z in State.children.items():
            Result = Algo.Minimum(z, Ply_num - 1, Maximum_Score)
            if Maximum_Score < Result:
                Maximum_Score = Result
            if Result > Alpha:
                return Result

        return Maximum_Score


    def Minimum(State, Ply_num, Beta): # Alpha-beta pruning function for taking care of Beta values
        if Ply_num == 0:
            return State.CurrentScore

        for i in range(State.Current.dimY):
            for j in range(State.Current.dimX):
                if State.Current.Mat[i][j] == ' ' and (j, i) not in State.children:
                    State.Make(j, i, True)

        Minimum_Score = 1000
        i = 0
        j = 0
        for k, z in State.children.items():
            Result = Algo.Maximum(z, Ply_num - 1, Minimum_Score)
            if Minimum_Score > Result:
                Minimum_Score = Result
            if Result < Beta:
                return Result

        return Minimum_Score

# class MCTSNode(object):
#     """Monte Carlo Tree Node.
#     Each node encapsulates a particular game state, the moves that
#     are possible from that state and the strategic information accumulated
#     by the tree search as it progressively samples the game space.
#     """

#     def __init__(self, state, parent=None, move=None):
#         self.parent = parent
#         self.move = move
#         self.state = state

#         self.plays = 0
#         self.score = 0

#         self.pending_moves = state.get_moves()
#         self.children = []

#     def select_child_ucb(self):
#         # Note that each node's plays count is equal
#         # to the sum of its children's plays
#         def ucb(child):
#             win_ratio = child.score / child.plays \
#                         + math.sqrt(2 * math.log(self.plays) / child.plays)
#             return win_ratio

#         return max(self.children, key=ucb)

#     def expand_move(self, move):
#         self.pending_moves.remove(move)  # raises KeyError

#         child_state = deepcopy(self.state)
#         child_state.play_move(move)

#         child = MCTSNode(state=child_state, parent=self, move=move)
#         self.children.append(child)
#         return child

#     def get_score(self, result):
#         # return result
#         if result == 0.5:
#             return result

#         if self.state.player == 2:
#             if self.state.next_turn_player == result:
#                 return 0.0
#             else:
#                 return 1.0
#         else:
#             if self.state.next_turn_player == result:
#                 return 1.0
#             else:
#                 return 0.0

#         if self.state.next_turn_player == result:
#             return 0.0
#         else:
#             return 1.0

#     def __repr__(self):
#         s = 'ROOT\n' if self.parent is None else ''

#         children_moves = [c.move for c in self.children]

#         s += """Score ratio: {score} / {plays}
# Pending moves: {pending_moves}
# Children's moves: {children_moves}
# State:
# {state}\n""".format(children_moves=children_moves, **self.__dict__)

#         return s