'''
  tick.py
  Author: Paul Talaga
  Date: Nov 8, 2018
  Description: Demo Tic Tac Toe game with AI agent using the MiniMax search
               algorithm.
  Works in Python 2.X and 3.X
'''
max_depth = 0
minimax_calls = 0

'''A game state is an array of length 9 containing spaces, O or X characters in 
   row-major order.'''
def printState(state):
  for y in range(3):
    line = ""
    for x in range(3):
      line += state[x + y * 3] 
      if x < 2:
        line += "|"
    print( line )
    if y < 2:
      print("-----")
  print("Score for O: " + str(score(state)))
  print("")

'''Remembering what index corresponds to which place on the board can be hard.  Use
   this function to remind the player the mapping.'''
def printNumberHelp():
  print("Index Helper:")
  printState(list("0123456789"))

'''Provided a state (array of 9 characters) and a character to count (either O or X)
   return a 1 if that player won, or 0 if not.  Thus it can be used to check if either
   player won.'''
def scorePlayer(state, c):
  # Horizontal win in any row
  for y in range(3):
    r = y * 3
    if state[r] == c and state[r+1] == c and state[r+2] == c:
      return 1
  # Vertical win in any column
  for x in range(3):
    if state[x] == c and state[x+3] == c and state[x+6] == c:
      return 1
  # Diagonal down from upper left to lower right
  if state[0] == c and state[4] == c and state[8] == c:
    return 1
  # Diagonal down from upper right to lower left
  if state[2] == c and state[4] == c and state[6] == c:
    return 1
  return 0
  
'''Returns if that position on the current state is available to play: is a space.'''
def validMove(state, pos):
  return state[pos] == " "
  
'''Find the score of the game, as in 1 if X won, -1 if O won, and 0 if it is a tie, or no win yet.'''
def score(state):
  x = scorePlayer(state,'X')
  o = scorePlayer(state,'O')
  if x == o:
    return 0
  if x > o:
    return 1
  if x < o:
    return -1
    
'''Is the board full of marks/ can anyone play?'''
def isFull(state):
  return not " " in state
  
'''Returns a list of possible next moves for player 1 (O) or player -1 (X)
   Each move is a tuple of (play location, new state).    '''
def generateSuccessors(state, player):
  player_character = ''
  if player == 1:
    player_character = "O"
  else:
    player_character = "X"
  ret = []
  for i in range(9):  # Try all positions on the board
    if validMove(state,i):
      new_state = state[:]  # We want a duplicate board, so copy the state.
      new_state[i] = player_character
      ret.append((i,new_state))
  return ret
  
'''A recursive function to perform MiniMax (not depth limited) given a state
   , if it should maximize the score/minimize the score, and the current recursion
   depth. 
   Returns a tuple (best score, best move index)'''
def minimaxdecision(state, max_or_min, depth):
  # max_or_min if 1:max, if -1: min   Done so it is easy to switch using multiplication
  
  # For fun keep track of how many times this fn is called and the max depth
  global minimax_calls 
  global max_depth  
  minimax_calls +=1
  
  if depth > max_depth:  # Hint: here you could depth limit it!
    max_depth = depth
  if score(state) != 0:
    return 0  # The game loop should have caught the win  1 or -1 means someone won.
  state_scores = [] # For all possible next game states, keep track of their scores and move
  for (position, new_state) in generateSuccessors(state, max_or_min * -1):  # The -1 will alternate players
    # is this a winning board?
    if score(new_state) != 0:  # Someone won!
      state_scores.append( (score(new_state), position) )
    elif isFull(new_state):  # The board is full and no one won - A tie!
      state_scores.append( (0 , position) )
    else:  # recurse!
      (bscore, best_index) = minimaxdecision(new_state, max_or_min * -1, depth + 1)
      state_scores.append( (bscore, position))
  # Did we get any new states?
  if len(state_scores) == 0:
    return 0
  # now we have a full state_scores array with scores and positions to get there
  if max_or_min == 1: # Find the max board score of all child game states
      (bscore, best_index) = max(state_scores)
  else:  # Find the min board score of all child game states
      (bscore, best_index) = min(state_scores)
  #print("BScore: " + str(bscore) + " Depth: " + str(depth) + str(state_scores))
  return (bscore, best_index)
  
  
startState = [" "] * 9


state = startState

play = True
while play:
  print("")
  printNumberHelp()
  printState(state)
  move = input('Enter O placement:')
  move = int(move)
  if not validMove(state,move):
    print("That move is not valid, try again.")
    continue
  state[move] = "O"   # Place that piece in the game state
  if score(state) == -1:
    printState(state)
    print("You Won!!!!")
    play = False
    break
  if isFull(state):
    printState(state)
    print("Tie!")
    play = False
    break
  (bscore, move) = minimaxdecision(state, 1, 0)  # Start off maximizing the score for X
  state[move] = "X"   # Place that piece in the game state
  if score(state) == 1:
    printState(state)
    print("Computer Won.  ;-(")
    play = False
    break
  if isFull(state):
    printState(state)
    print("Tie!")
    play = False
    break
  # Print stats
  print("Minimax calls: " + str(minimax_calls))
  print("Max Depth: " + str(max_depth))
  max_depth = 0
  minimax_calls = 0