'''
  ultimate-tick-alpha.py
  Author: Paul Talaga
  Date: Nov 8, 2018
  Description: Solution to Ultimate Tic Tac Toe game with AI agent using the AlphaBeta search
               algorithm.
  Works with Python 2.X and 3.X
'''

max_depth = 0
minimax_calls = 0

'''A board state is an array of 81 strings, where each string is either X, O, or a space.
   The inBox, getMiniBoard, getHighBoard, and minToBig functions allow this big state to
   be analyzed as a normal 3x3 board.'''

def inBox(box, x, y):
  #boxes are labeled 0 1 2    3 4 5    6 7 8
  return int(x / 3) == int(box % 3) and int(y / 3) == int(box / 3)
  
def getMiniBoard(big, box):
  (x,y) = (box%3, int(box / 3) )
  indexes = []
  indexes += map(lambda a: x*3 + a + y *27,range(3))
  indexes += map(lambda a: x*3 + a + y *27 + 9,range(3))
  indexes += map(lambda a: x*3 + a + y *27 + 18,range(3))
  # make subboard
  subboard = []
  for i in indexes:
    subboard.append(big[i])
  return subboard
  
  
def getHighBoard(big):
  ret = []
  for box in range(9):
    (x,y) = (box%3, int(box / 3) )
    indexes = []
    indexes += map(lambda a: x*3 + a + y *27, range(3))
    indexes += map(lambda a: x*3 + a + y *27 + 9, range(3))
    indexes += map(lambda a: x*3 + a + y *27 + 18, range(3))
    # make subboard
    subboard = []
    for i in indexes:
      subboard.append(big[i])
    if miniScorePlayer(subboard,'X') == 1: # If X won this miniboard, fill all with Xs
      ret.append('X')
    elif miniScorePlayer(subboard,'O') == 1:# If O won this miniboard, fill with all Os
      ret.append('O')
    elif isFull(subboard):  # No win, but a Tie
      ret.append('T')
    else:
      ret.append(' ')
  return ret
    
def minToBig(index, box):
  (x,y) = (box%3, int(box / 3) )
  return x*3 + (index % 3) + y *27 + int(index/3) * 9

def printState(state):
  (big, box) = state
  # Print the large board
  print("Large board state.  You must play on the . locations.")
  for y in range(9):
    line = ""
    for x in range(9):
      if big[x + y * 9] == " " and inBox(box,x,y):
         line += "."
      else:
        line += big[x + y * 9]
      if (x + 1) % 3 == 0 and x != 8:
        line += "|"
    print( line)
    if (y+1) % 3 == 0 and y != 8:
      print("-" * 11)
    print("Who is winning each small board:")
    mini = getHighBoard(big)
    print("")
    for y in range(3):
      line = ""
      for x in range(3):
        line += mini[x + y * 3] 
        if x < 2:
          line += "|"
      print( line)
      if y < 2:
        print("-----")
    print("Score for O: " + str(score(state)))
    print("")
  
def printNumberHelp():
  state = list("0123456789")
  print("Index Helper:")
  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("\n")


def miniScorePlayer(mini, c):
  # horizontal
  for y in range(3):
    r = y * 3
    if mini[r] == c and mini[r+1] == c and mini[r+2] == c:
      return 1
  # vertical
  for x in range(3):
    if mini[x] == c and mini[x+3] == c and mini[x+6] == c:
      return 1
  # diag down to right
  if mini[0] == c and mini[4] == c and mini[8] == c:
    return 1
  # diag down to left
  if mini[2] == c and mini[4] == c and mini[6] == c:
    return 1
  return 0
  
def validMove(state, pos): # Pos is 0-8 for a small 3x3 board.
  (big, box) = state
  miniboard = getMiniBoard(big, box)
  if pos < 0 or pos > 8:
    return False
  return miniboard[pos] == " "
  
def score(state):
  (big, box) = state
  mini = getHighBoard(big)
  x = miniScorePlayer(mini,'X')
  o = miniScorePlayer(mini,'O')
  if x == o:
    return 0
  if x > o:
    return 1
  if x < o:
    return -1
    
def isFull(minBoard):
  return not " " in minBoard
  
def isBigFull(state):
  (big, box) = state
  return isFull(getHighBoard(big))
  
def generateSuccessors(state, player):
  # Returns a tuple, (index, new state)
  # if player = 1, O, if -1, X
  player_character = ''
  if player == 1:
    player_character = "O"
  else:
    player_character = "X"
  ret = []
  (big, box) = state
  if isFull(getMiniBoard(big,box)) or miniScorePlayer(getMiniBoard(big,box),'X') == 1 or  miniScorePlayer(getMiniBoard(big,box),'X') == 1:  #full or someone won
    # get to pick a random other board... lets just pick the next one that is free
    box = -1
    for i in range(9):
      if not isFull(getMiniBoard(big,i)) and miniScorePlayer(getMiniBoard(big,box),'X') == 0 and  miniScorePlayer(getMiniBoard(big,box),'X') == 0:
        box = i
        break
  state = (state[0], box)
  for i in range(9):
    if validMove(state,i):
      (big, box) = state
      newBig = big[:]
      newBig[minToBig(i,box)] = player_character
      ret.append((i, (newBig, i)))
  if len(ret) == 0:
    print("no options!")
  return ret
  
'''This is called in the game play.  Substitute your own function to change the AI method.
   This needs to return a move, which is an index to place their character.'''
def getAIMove(state, max_or_min):
  (_, move) = alphaBeta(state, max_or_min = 1, depth = 0, alpha = -99999, beta = 99999, limit =5)
  return move
  
# AI aspect: heuristic and alpha-beta pruning code below
def h(state):
  (big, box) = state
  mini = getHighBoard(big)
  return mini.count('X') - mini.count('O')
  
def alphaBeta(state, max_or_min, depth, alpha, beta, limit): # alpha is min, beta is max
  # max_or_min if 1, max, if -1 min
  # returns a tuple (best score, best index)
  # Make sure we don't have a winning board
  global minimax_calls
  global max_depth  
  minimax_calls +=1
  if depth > max_depth:
    max_depth = depth
    #print("Max Depth" + str(max_depth))
  if depth > limit:  # Depth limited!
    return (h(state), -1)
  ## Start of real stuff!

  bscore = (max_or_min * 99999 * -1 , -1)  # the best so far
  for (position, new_state) in generateSuccessors(state, max_or_min * -1):
    # is this a winning board?
    if score(new_state) != 0:  # Someone won!
      #print("Won")
      return (score(new_state), position) 
    elif isBigFull(new_state):  # A Tie
      return (0 , position) 
    else:  # recurse!
      # Update best so far
      if max_or_min == 1: # max
        (mbscore, best_index) = alphaBeta(new_state, max_or_min * -1, depth + 1, alpha, beta,limit)
        mbscore = (mbscore, position)
        bscore = max(bscore, mbscore)
        if bscore >= (beta, -1):
          # Out early!
          #print("Max out early")
          return bscore
        alpha = max(alpha, bscore[0])
      else:
        (mbscore, best_index) = alphaBeta(new_state, max_or_min * -1, depth + 1, alpha, beta,limit)
        mbscore = (mbscore, position)
        bscore = min(bscore, mbscore)
        if bscore <= (alpha, -1):
          # Out early!
          #print("Min out early")
          return bscore
        beta = min(beta, bscore[0])
  return bscore


#  -------------- Run the Game! -------------------

state = ([" "] * 81, 0)   # (full board, next subboard to play)


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
  (big, box) = state
  state[0][minToBig(move, box)] = "O"
  state = (state[0], move)
  (big, box) = state
  if score(state) == -1:
    printState(state)
    print("You Won!!!!")
    play = False
    break
  if isFull(getHighBoard(big)):
    printState(state)
    print("Tie!")
    play = False
    break
  move = getAIMove(state)  # This will call the alphaBeta function
  (big, box) = state
  state[0][minToBig(move, box)] = "X"
  state = (state[0], move)
  (big, box) = state
  if score(state) == 1:
    printState(state)
    print("Computer Won.  ;-(")
    play = False
    break
  if isFull(getHighBoard(big)):
    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