''' ultimate-tick-alpha.py Author: Paul Talaga Date: Nov 8, 2018 Description: Implements the Ultimate Tic Tac Toe game, but no AI is implemented. See the getAIMove to add an AI player. Works with Python 2.X and 3.X ''' '''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.") print("Box: %d" % box) 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("") print("Who is winning each small board:") mini = getHighBoard(big) 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): # As an example pick the first available spot to play options = generateSuccessors(state, 1) return options[0][0] # AI aspect: Insert your AI functions below # -------------- 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 AI agent (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