I am currently making a TicTacToe game that uses a Minimax algorithm for Player vs Computer. As of right now, the code only has Hard mode on PvE. It is a working bot that you cant win against using Minimax algorithm. However, I need to find a way to incorporate a special rule...
Each player is only allowed to have 3 'tacs' on the board at a time. Once they reach 3, they have to move a tac from one spot to another. I am not entirely sure how to implement this, could someone give me some ideas?
"""
TicTacToe - 3 symbols max
By Gage Gunn (???), Trevor Purta (Player vs. Computer), Toby Howie (Player vs. Player), Rachel Powers (Computer vs. Computer)
"""
# -------- Modules --------
import os
import time
import random
# -------- Global Variables --------
human = 'O'
bot = 'X'
amount_of_x = 0
amount_of_o = 0
ID = '' #Detecting which game mode (PvP, PvE, EvE)
ID2 = '' #Detecting which difficulty in PvE
ID3 = '' #Detecting which difficulty in EvE
# -------- Functions --------
def printBoard(board):
print(board[1] + ' | ' + board[2] + ' | ' + board[3] + ' 1 | 2 | 3')
print(board[4] + ' | ' + board[5] + ' | ' + board[6] + ' 4 | 5 | 6')
print(board[7] + ' | ' + board[8] + ' | ' + board[9] + ' 7 | 8 | 9')
print('\n')
def spaceIsFree(position):
if board[position] == ' ':
return True
else:
return False
def insertLetter(letter, position):
if spaceIsFree(position):
board[position] = letter
printBoard(board)
if (checkDraw()):
print("Draw!")
exit()
if checkForWin():
if letter == 'X':
print("Bot wins!")
exit()
else:
print("Player wins!")
exit()
return
else:
print("Can't insert there!")
position = int(input("Please enter new position: "))
insertLetter(letter, position)
return
def checkForWin():
if (board[1] == board[2] and board[1] == board[3] and board[1] != ' '):
return True
elif (board[4] == board[5] and board[4] == board[6] and board[4] != ' '):
return True
elif (board[7] == board[8] and board[7] == board[9] and board[7] != ' '):
return True
elif (board[1] == board[4] and board[1] == board[7] and board[1] != ' '):
return True
elif (board[2] == board[5] and board[2] == board[8] and board[2] != ' '):
return True
elif (board[3] == board[6] and board[3] == board[9] and board[3] != ' '):
return True
elif (board[1] == board[5] and board[1] == board[9] and board[1] != ' '):
return True
elif (board[7] == board[5] and board[7] == board[3] and board[7] != ' '):
return True
else:
return False
def checkWhichMarkWon(mark):
if board[1] == board[2] and board[1] == board[3] and board[1] == mark:
return True
elif (board[4] == board[5] and board[4] == board[6] and board[4] == mark):
return True
elif (board[7] == board[8] and board[7] == board[9] and board[7] == mark):
return True
elif (board[1] == board[4] and board[1] == board[7] and board[1] == mark):
return True
elif (board[2] == board[5] and board[2] == board[8] and board[2] == mark):
return True
elif (board[3] == board[6] and board[3] == board[9] and board[3] == mark):
return True
elif (board[1] == board[5] and board[1] == board[9] and board[1] == mark):
return True
elif (board[7] == board[5] and board[7] == board[3] and board[7] == mark):
return True
else:
return False
def checkDraw():
for key in board.keys():
if (board[key] == ' '):
return False
return True
def playerMove():
position = int(input("Enter the position for 'O': "))
insertLetter(human, position)
return
def compMove():
bestScore = -800
bestMove = 0
for key in board.keys():
if (board[key] == ' '):
board[key] = bot
score = minimax(board, 0, False)
board[key] = ' '
if (score > bestScore):
bestScore = score
bestMove = key
insertLetter(bot, bestMove)
return
def minimax(board, depth, isMaximizing):
if (checkWhichMarkWon(bot)):
return 1
elif (checkWhichMarkWon(human)):
return -1
elif (checkDraw()):
return 0
if (isMaximizing):
bestScore = -800
for key in board.keys():
if (board[key] == ' '):
board[key] = bot
score = minimax(board, depth + 1, False)
board[key] = ' '
if (score > bestScore):
bestScore = score
return bestScore
else:
bestScore = 800
for key in board.keys():
if (board[key] == ' '):
board[key] = human
score = minimax(board, depth + 1, True)
board[key] = ' '
if (score < bestScore):
bestScore = score
return bestScore
board = {1: ' ', 2: ' ', 3: ' ',
4: ' ', 5: ' ', 6: ' ',
7: ' ', 8: ' ', 9: ' '}
def pick_game_type(): #Pick PvP, PvE, EvE
global ID
print("""
First, Pick which game mode you would like to play!
(Player vs. Player [1], Player vs. Computer [2], Computer vs. Computer [3])
""")
type_choice = input('> ')
if type_choice == "1": #Set global ID for [1]
ID = "1"
elif type_choice == "2": #Set global ID for [2]
ID = "2"
elif type_choice == "3": #Set global ID for [3]
ID = "3"
# -------- Script --------
os.system('cls') #Clear console
print("""
Welcome to Wacky Tacky Toe, Tac, Tic!
By Gage Gunn, Trevor Purta, Toby Howie, and Rachel Power with an s
""")
pick_game_type() #Choose gamemode
if ID == '1': #PvP Chosen
pass
elif ID == '2': #PvE Chosen
os.system('cls')
print('''
Welcome to Player vs Computer! In this version of Tic, Tac, Toe, each player can have a maximum of 3 tacs on the board at a time!
Decide which difficuly you would like to play? (Easy [1] or Hard [2])''')
ID2 = input('> ')
valid_input = False
while not valid_input: #Checks validity of ID2
if ID2 in ['1', '2']:
valid_input = True
else:
ID2 = input('> ')
if ID2 == '1': #Easy was chosen
pass
elif ID2 == '2':
print('You have chosen hard! You are X, the computer is O. The computer will go first')
while not checkForWin():
compMove()
playerMove()
elif ID == '3': #PvE Chosen
pass
You will need to isolate components of gameplay into reusable functions that can be combined to simulate moves for the minimax calculations.
Because you need simulations, it is a good idea to have a self contained data structure that represents the sate of the game (board) including who's turn it is to play (i'm using a 10 character string where the first character is the current player and the other 9 are the current state of the board).
The first thing you'll need to implement is a function to simulate a move (returning a new game state):
def playMove(game,toPos,fromPos):
played = [game[0] if i==toPos else "." if i==fromPos else p
for i,p in enumerate(game)]
return "".join(played)
You will also need a function to switch the current player. This needs to be separate so that you can easily evaluate the outcome for the current player before simulating the opponent's moves:
def switchPlayer(game):
return "XO"[game[0]=="X"]+game[1:] # returns a new game state
In order to recursively simulate moves, you'll need a function that gives a list of possible moves. Given your gameplay rules, a move is defined as a target position (toPos) and an optional origin position (fromPos). for the first 3 moves there will be no origin (lets make fromPos = toPos for those)
def getMoves(game):
player,*board = game
moves = [(i,i) for i,p in enumerate(board,1) if p=="."] # 1st 3 moves
if board.count(player)==3: # moves 4+
origins = [r for r,p in enumerate(board,1) if p==player ]
moves = [ (i,r) for i,_ in moves for r in origins] # add origins
return moves
For simulations and actual gameplay, you'll need a function to determine if the game is won:
winPatterns = [(1,2,3),(4,5,6),(7,8,9),(1,4,7),(2,5,8),(3,6,9),(1,5,9),(3,5,7)]
def isWin(game):
return any(all(game[i]==game[0] for i in p) for p in winPatterns)
Rating the outcome of a move could be some complex formula but, to keep it simple, let's just say that winning is 1 and not winning is zero. The minimax function will recursively simulate moves giving them a rating based on the "nearest" conclusive move (1 for wins, -1 for losses).
maxDepth = 6 # maximum depth = computer's skill
memo = dict() # memoization (for performance)
def minimax(game,depth=maxDepth):
if (game,depth) in memo: # known rating at this depth
return memo[game,depth]
if isWin(game): return 1 # no moves after a win (base condition)
if not depth: return 0 # limit depth (avoids infinite loops)
oGame = switchPlayer(game) # will simulate opponent's moves
oRatings = [] # opponent's minimax ratings
for move in getMoves(oGame):
played = playMove(oGame,*move) # simulate
oRatings.append(minimax(played,depth-1)) # get rating
rating = -max(oRatings or [1]) # worst countermove
for d in range(1,depth+1):
memo[game,d]=rating # memorize for this depth and lower
return rating
Because the game data structure is hashable (i.e. a string), it can be used for memoization which greatly increases performance of the minimax function.
With the minimax function, you can determine the best move to make for the computer player (the one with the highest minimax rating):
def bestMove(game):
return max(getMoves(game),key=lambda m:minimax(playMove(game,*m)))
You could shuffle the moves before getting the max() to randomize selection of the best move when more than one move has the highest rating
Putting it all together in a gameplay loop:
def printBoard(game):
for r in range(1,10,3):
print("("+") (".join(game[r:r+3])+")",list(range(r,r+3)))
from random import sample
while True:
player,computer = sample("XOXO",2) # random starter, random computer
game = player + "."*9
while True:
printBoard(game)
if isWin(game): break
game = switchPlayer(game)
player = game[0]
if player == computer:
toPos,fromPos = bestMove(game)
print(f"Computer plays {player} at {toPos}",end=" ")
print(f"from {fromPos}"*(fromPos!=toPos))
else:
strMoves = [(str(t),str(f)) for t,f in getMoves(game)]
while True:
fromPos = toPos = input(f"Position to play for {player}: ")
if not toPos in (f for f,_ in strMoves):
print("invalid position"); continue
if game[1:].count(player)<3: break
fromPos = input(f"Position to remove {player} from: ")
if (toPos,fromPos) not in strMoves:
print("invalid move")
else: break
game = playMove(game,int(toPos),int(fromPos))
print( f"{player}'s WIN !!!\n")
if input("play again (y/n)") != "y": break
print()
Sample Run:
(.) (.) (.) [1, 2, 3]
(.) (.) (.) [4, 5, 6]
(.) (.) (.) [7, 8, 9]
Computer plays O at 5
(.) (.) (.) [1, 2, 3]
(.) (O) (.) [4, 5, 6]
(.) (.) (.) [7, 8, 9]
Position to play for X: 1
(X) (.) (.) [1, 2, 3]
(.) (O) (.) [4, 5, 6]
(.) (.) (.) [7, 8, 9]
Computer plays O at 3
(X) (.) (O) [1, 2, 3]
(.) (O) (.) [4, 5, 6]
(.) (.) (.) [7, 8, 9]
Position to play for X: 7
(X) (.) (O) [1, 2, 3]
(.) (O) (.) [4, 5, 6]
(X) (.) (.) [7, 8, 9]
Computer plays O at 4
(X) (.) (O) [1, 2, 3]
(O) (O) (.) [4, 5, 6]
(X) (.) (.) [7, 8, 9]
Position to play for X: 6
(X) (.) (O) [1, 2, 3]
(O) (O) (X) [4, 5, 6]
(X) (.) (.) [7, 8, 9]
Computer plays O at 9 from 3
(X) (.) (.) [1, 2, 3]
(O) (O) (X) [4, 5, 6]
(X) (.) (O) [7, 8, 9]
Position to play for X: 3
Position to remove X from: 7
(X) (.) (X) [1, 2, 3]
(O) (O) (X) [4, 5, 6]
(.) (.) (O) [7, 8, 9]
Computer plays O at 2 from 4
(X) (O) (X) [1, 2, 3]
(.) (O) (X) [4, 5, 6]
(.) (.) (O) [7, 8, 9]
Position to play for X: 8
Position to remove X from: 3
(X) (O) (.) [1, 2, 3]
(.) (O) (X) [4, 5, 6]
(.) (X) (O) [7, 8, 9]
Computer plays O at 3 from 2
(X) (.) (O) [1, 2, 3]
(.) (O) (X) [4, 5, 6]
(.) (X) (O) [7, 8, 9]
Position to play for X: 7
Position to remove X from: 8
(X) (.) (O) [1, 2, 3]
(.) (O) (X) [4, 5, 6]
(X) (.) (O) [7, 8, 9]
Computer plays O at 4 from 9
(X) (.) (O) [1, 2, 3]
(O) (O) (X) [4, 5, 6]
(X) (.) (.) [7, 8, 9]
Position to play for X:
Position to play for X: 9
Position to remove X from: 1
(.) (.) (O) [1, 2, 3]
(O) (O) (X) [4, 5, 6]
(X) (.) (X) [7, 8, 9]
Computer plays O at 8 from 4
(.) (.) (O) [1, 2, 3]
(.) (O) (X) [4, 5, 6]
(X) (O) (X) [7, 8, 9]
Position to play for X: 2
Position to remove X from: 6
(.) (X) (O) [1, 2, 3]
(.) (O) (.) [4, 5, 6]
(X) (O) (X) [7, 8, 9]
Computer plays O at 1 from 3
(O) (X) (.) [1, 2, 3]
(.) (O) (.) [4, 5, 6]
(X) (O) (X) [7, 8, 9]
Position to play for X: 3
Position to remove X from: 7
(O) (X) (X) [1, 2, 3]
(.) (O) (.) [4, 5, 6]
(.) (O) (X) [7, 8, 9]
Computer plays O at 6 from 8
(O) (X) (X) [1, 2, 3]
(.) (O) (O) [4, 5, 6]
(.) (.) (X) [7, 8, 9]
Position to play for X: 7
Position to remove X from: 2
(O) (.) (X) [1, 2, 3]
(.) (O) (O) [4, 5, 6]
(X) (.) (X) [7, 8, 9]
Computer plays O at 4 from 1
(.) (.) (X) [1, 2, 3]
(O) (O) (O) [4, 5, 6]
(X) (.) (X) [7, 8, 9]
O's WIN !!!
play again (y/n) ? n