I have recently implemented the code for a 4X4 tic tac toe game which is using minimax algorithm. However, my minimax function is calling itself recursively infinite no. of times.
Initial Board (4X4) tic tac toe ->
board = np.array([['_','_','_', '_'],['_','_','_', '_'],['_','_','_', '_'],['_','_','_', '_']])
Code for the computer's turn ->
import math
from utility import *
def minimax(board, spotsLeft, maximizing):
bestIdx = (0,0)
p1 = 'X'
p2 = 'O'
res, stat = checkGameOver(board, spotsLeft)
if res==True:
if stat == 'X': return 17-spotsLeft, bestIdx
elif stat == 'O': return -17+spotsLeft, bestIdx
else: return 0, bestIdx
if maximizing:
# return max score
bestMove = -math.inf
for i in range(4):
for j in range(4):
if board[i][j] == '_':
board[i][j] = p1
score, idx = minimax(board, spotsLeft-1, False)
print(score, idx)
board[i][j] = '_'
if bestMove<score:
bestMove = score
bestIdx = (i,j)
return bestMove, bestIdx
else:
# return min score
bestMove = math.inf
for i in range(4):
for j in range(4):
if board[i][j] == '_':
board[i][j] = p2
score, idx = minimax(board, spotsLeft-1, True)
print(score, idx)
board[i][j] = '_'
if bestMove>score:
bestMove = score
bestIdx = (i,j)
return bestMove, bestIdx
def ai(board):
spotsLeft = 16
p1 = 'X' # Computer
p2 = 'O' # Player
turn = p1
while True:
res, stat = checkGameOver(board, spotsLeft)
if res==False:
if turn == p1:
# AI
boardCopy = board[:]
score, idx = minimax(boardCopy, spotsLeft, True)
board[idx[0]][idx[1]] = turn
turn = p2
spotsLeft-=1
else:
# Human
inp = int(input(f"Your turn: "))
i, j = spotToIdx(inp)
if board[i][j]=='_':
board[i][j] = turn
turn = p1
spotsLeft-=1
else: return stat
printBoard(board)
In the above code
spotsLeft is the empty places on board,
checkGameOver returns "X" (if Player X wins), returns "O" (if Player O wins) & returns "T" (if game is tied)
checkGameOver function ->
def checkWin(board):
# Check Row
for i in board:
if len(set(i)) == 1 and i[0]!='_':
return i[0]
# Check Column
for i in range(4):
if (board[0][i] == board[1][i] == board[2][i] == board[3][i]) and board[0][i]!='_':
return board[0][i]
# Check Diagonals
if (board[0][0]==board[1][1]==board[2][2]==board[3][3]) and board[0][0]!='_':
return board[0][0]
if (board[0][3]==board[1][2]==board[2][1]==board[3][0]) and board[0][3]!='_':
return board[0][3]
# No One Won Yet
return -1
def checkGameOver(board, spotsLeft):
# t -> Game Tied
# x -> Player X won
# o -> Player O won
# if tied - all spots filled
if spotsLeft == 0:
return True, 'T'
# if any player won the game
result = checkWin(board)
if result!=-1:
return True, result
return False, -1
As Jenny has very well explained, the search tree is too large. Even if you would make improvements to the data structure and move-mechanics to make them more efficient and reduce the memory footprint, it will still be a challenge to have this search finish within an acceptable time.
In general you would go for the following measures to cut down on the search tree:
Stop at a certain search depth (like 4) and perform a static evaluation of the board instead. This evaluation will be a heuristic. For instance it will give a high value to a 3-in-a-row with a free cell available to complete it to a win. It would also give a significant value to a pair on a line that is not blocked by the opponent, ...etc.
Use alpha-beta pruning to avoid searching in branches that could never lead to a better choice at an earlier stage in the search tree.
Use killer moves: a move that was found good after a certain opponent move, could also turn out to be good in reply to another opponent move. And trying that one first may work well in combination with alpha-beta pruning.
Memoize positions that were already evaluated (by swapping of moves), and mirror positions to equivalent positions to reduce the size of that dictionary.
But to be honest, 4x4 Tic Tac Toe is quite boring: it is very easy to play a draw, and it requires really inferior moves for a player to give the game away to the other. For instance, neither player can make a bad first move. Whatever they play on their first move, it will still be a draw with correct play.
So... I would propose to only use a heuristic evaluation function, and not search at all. Or, perform a shallow minimax, and use such a heuristic evaluation at that fixed depth. But even replacing the minimax algorithm with just an evaluation function works quite well.
To implement that idea, proceed as follows:
Replace the AI part with this:
if turn == p1:
# AI -- a heuristic based approach
bestScore = -math.inf
bestMove = None
for i in range(4):
for j in range(4):
if board[i][j] == '_':
board[i][j] = turn
score = evaluate(board, turn)
if score > bestScore:
bestScore = score
bestMove = (i, j)
board[i][j] = '_'
i, j = bestMove
board[i][j] = turn
turn = p2
spotsLeft-=1
This calls evaluate which will give a numeric score that is higher the better it is for the given player (argument).
Add the definition for evaluate:
# winning lines
lines = [
[(i, j) for i in range(4)] for j in range(4)
] + [
[(j, i) for i in range(4)] for j in range(4)
] + [
[(i, i) for i in range(4)],
[(3-i, i) for i in range(4)]
]
def evaluate(board, player):
score = 0
for line in lines:
discs = [board[i][j] for i, j in line]
# The more discs in one line the better
value = [1000, 10, 6, 1, 0][sum(ch == "_" for ch in discs)]
if "X" in discs:
if not "O" in discs: # X could still win in this line
score += value
elif "O" in discs: # O could still win in this line
score -= value
# Change the sign depending on which player has just played
return score if player == "X" else -score
That's it! Optionally you can use the evaluate function to simplify the checkWin function:
def checkWin(board):
score = evaluate(board, "X")
if abs(score) > 500: # Take into account there could be some reduction
return "X" if score > 0 else "O"
# No One Won Yet
return -1
With this implementation you don't need the minimax function anymore, but you might want to keep it, and limit the search depth. When that depth is reached, make the call to evaluate, ...etc. Still I found the above implementation to play fine. You can't win a game against it.