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