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
CodePudding user response：
I think your code is fine, and doing what you want it to do. The issue is most likely due to the complexity of the problem, and for a lower dimension tic tac toe it would work fine.
Let's first simplify and look at a 2x2 case. For the first turn, you call minimax from the ai function, which will at the first level call itself 4 times. At the next level, each one of those calls will also call minimax, but one time less than at the previous level. To put it as a list:
- level 0 (
aifunction): 1 call tominimax - level 1: 4 calls
- level 2: 4x3 calls (each of the 4 calls above make 3 new calls)
- level 3: 4x3x2 calls
- level 4: 4x3x2x1 calls
Now using n-factorial notation as n!, we can compute the total number of calls as:
4!/4! 4!/(4-1)! 4!/(4-2)! 4!/(4-3)! 4!/(4-4!)
Which is the sum of n!/(n-k)! for k between 0 and n (included), n begin the number of cells on your board. The result here is 65 calls to minimax for a 2x2 board.
Put into a python code:
def factorial(n):
if n > 1: return n*factorial(n-1)
else: return 1
def tictactoeComplexity(gridsize):
return sum([factorial(gridsize)/factorial(gridsize-k) for k in range(gridsize 1)])
print(tictactoeComplexity(2*2)) # result is 65
Now let's check for a 3*3 board:
print(tictactoeComplexity(3*3)) # result is 986,410
Just going from 2x2 to 3x3, we go from around 100 to around 1,000,000. You can guess the result for a 4x4 board:
print(tictactoeComplexity(4*4)) # result is 56,874,039,553,217
So your program does what you are asking it to do, but you're asking quite a lot.
CodePudding user response：
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.
What to change
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-=1This calls
evaluatewhich 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.