#Jay Summet # CS 1301 # Released to the public domain, Nov 2008 # #Data structure that represents the current gameboard. board = [ ' ', ' ', ' ', ' ', ' ', ' ', ' ', ' ', ' ' ] #A list of possible winning positions (rows, columns, diagonals) possWins = [ [0,1,2], [0,4,8], [0,3,6], [1,4,7] , [2,5,8], [3,4,5], [ 6,7,8], [2,4,6] ] #Returns the index (integer position) of all "empty" spaces on the # board (i.e. possible moves) def possMoves(board): moves = [] for pos in range(0, len(board) ): if (board[pos] == " "): moves.append(pos) return(moves) #returns X if X has won, O if O has won, " " if nobody has # won, or T if a tie has occured def checkWin(board): global possWins for pw in possWins: Letter = board[ pw[0] ] if (Letter != ' '): win = True for i in range(1, len(pw)): if (Letter != board[ pw[i]]): win = False if win: return Letter movesLeft = possMoves(board) if len(movesLeft) == 0: return 'T' return ' ' #Prints out a 3x3 board. def printBoard3(board): print board[0], "|", board[1], "|", board[2] print "--------" print board[3], "|", board[4], "|", board[5] print "--------" print board[6], "|", board[7], "|", board[8] #Utility function / helper function to find the other player. def opponent(player): if (player == "X"): return( "O") else: return("X") #This function will count the number of wins for X,O and Tie #that are possible from a given board (with player being the next player #to move. (Not used by the actual TTT playing program, but demonstrates #similar concepts in a simpler manner.) def countWins(board,player): xWin = 0 oWin = 0 ties = 0 nextPlayer = opponent(player) moves = possMoves(board) for move in moves: newBoard = board[:] newBoard[move] = player win = checkWin(newBoard) if (win == "T"): ties = ties+1 elif ( win == "X"): xWin = xWin + 1 elif ( win == "O"): oWin = oWin + 1 elif (win == " "): #Do the next move! result = countWins(newBoard, nextPlayer) xWin = xWin + result[0] oWin = oWin + result[1] ties = ties + result[2] #printBoard3(board) #print [ xWin, oWin, ties] #print "\n" return( [ xWin, oWin, ties] ) #Gets a move from the user, with appropriate error checking. def getUserMove(board): userMoveGood = False while(not userMoveGood): #Print the current board print "Current board:" printBoard3(board) #make a board showing only valid moves and show it #to the user cb = board[:] i = 0 while( i < len(cb)): if (cb[i] == ' '): cb[i] = i else: cb[i] = "-" i = i + 1 print "" printBoard3(cb) #Get user input userMove = raw_input("Enter number for your move:") #Validate user input. Repeat until valid: try: um = int(userMove) if (um in possMoves(board)): #User move is valid! Make the move and signal the #while loop to stop by toggling the boolean! print "Good move!" board[um] = "X" userMoveGood = True else: print "Sorry, that's not a valid move!" print "Try again!" except: print "Not a valid number, try again!" #This funciton returns a score, predicting how likley it #is that the computer will win. (Based upon the fact that #the player is trying to minimize the computers score!) #TODO: This function MUST try all possible moves to return a score. #it can NOT return a score after only looking ahead a few moves. #How would you improve the function so that it could be limited to only #look ahead a specified number of levels and give a "best guess" score? def lookAhead(board, player): #Terminating condition. result = checkWin(board) #If the game is won/lost or tied, we don't look any farther! if(result == "X"): return(-100) if(result == "O"): return(100) if(result == "T"): return(0) #Recursive part. We have at least one move left to play #Find the possible moves pm = possMoves(board) otherPlayer = opponent(player) #If we are the next player, maximize our score! if (player == "O"): score = -100 #Start low, try to get higher.... for move in pm: cb = board[:] cb[move] = "O" score = max( score, lookAhead(cb,otherPlayer)) else: #Player is human, minimize (the computers) score! score = 100 #Start high, try to go low for move in pm: cb = board[:] cb[move] = "X" score = min( score, lookAhead(cb,otherPlayer)) #Now that we have calculated the best (or worst) score possible #for this board, return it. Note that we do not tell which series of #moves results in this score, as we assume the computer will always #choose the best move based upon the score. return(score) #This function will try all possible remaining moves and use the lookAhead #function to get a score for each possible moves. It then actually does the #move that results in the highest score. #NOTE: Because Perfect TicTacToe will always result in a Tie, most moves will #score a zero (tie) or -100 (loss) unless the human makes a mistake. When the #human makes a mistake, one of our moves will score a 100, and we win! #TODO: This function always makes the FIRST valid move that has the lowest # score, even if multiple moves have the same highest score. Modify the function # so that it picks randomly between all possible "best moves". def makeComputerMove(board): pm = possMoves(board) ourMove = 0 bestScore = -100000 for move in pm: cb = board[:] cb[move] = 'O' tryScore = lookAhead(cb, "X") print "score for move:",move," is:", tryScore if( tryScore > bestScore): ourMove = move bestScore = tryScore #Now that we've found the best score, make that move! #Computer is always "O" and goes second. board[ourMove] = "O" #The actual code to play the game! done = False while(not done): getUserMove(board) result = checkWin(board) if(result == "T"): print "it's a tie!" done = True elif(result == "X"): print "You won!" done = True else: makeComputerMove(board) result = checkWin(board) if(result == "O"): printBoard3(board) print "Computer beat you!" done = True elif(result == "T"): printBoard3(board) print "It's a Tie!" done = True