''' 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