CODEWITHSUNDEEP
pythonnumpyartificial-intelligenceminimax
97amarnathk
97amarnathk

Reputation: 1035

Minimax algorithm not working for 4x4 TicTacToe

Okay, So I wrote the following agent for a bot to play tic tac toe. I have used the traditional minimax algorithm without pruning. The thing is that it works perfectly for a 3x3 board.

But when I run this on a 4x4 board, it gets stuck computing. I am not able to understand why. I am passing the agent a numpy array perspectiveState, which has 0 for empty, 1 for the agents move, and -1 for the opponents moves. It returns the position of its next move (1).

The flow of control starts from the turn() function, which calls the minimax() function.

What am I doing wrong here?

class MiniMaxAgent:

def isMovesLeft(self, perspectiveState):
    size = perspectiveState.shape[0]
    #print('!!', np.abs(perspectiveState).sum())
    if np.abs(perspectiveState).sum() == size*size:
        return False
    return True

def evaluate(self, perspectiveState):
    size = perspectiveState.shape[0]
    rsum = perspectiveState.sum(axis=0)
    csum = perspectiveState.sum(axis=1)
    diagSum = perspectiveState.trace()
    antiDiagSum = np.fliplr(perspectiveState).trace()

    if size in rsum or size in csum or size == diagSum or size == antiDiagSum:
        return 10

    if -1*size in rsum or -1*size in csum or -1*size == diagSum or -1*size == antiDiagSum:
        return -10

    return 0

def minimax(self, perspectiveState, isMax):
    score = self.evaluate(perspectiveState)

    if score == 10:
        return score

    if score == -10:
        return score

    if not self.isMovesLeft(perspectiveState):
        return 0

    if isMax:
        best = -1000
        for i in range(perspectiveState.shape[0]):
            for j in range(perspectiveState.shape[0]):
                if perspectiveState[i,j]==0:
                    perspectiveState[i,j] = 1
                    #print('@', isMax)
                    best = max(best, self.minimax(perspectiveState, not isMax))
                    perspectiveState[i,j] = 0
        #print('#', best)
        return best

    else:
        best = 1000;
        for i in range(perspectiveState.shape[0]):
            for j in range(perspectiveState.shape[0]):
                if perspectiveState[i,j]==0:
                    perspectiveState[i,j] = -1
                    #print('@', isMax)
                    best = min(best, self.minimax(perspectiveState, not isMax))
                    perspectiveState[i,j] = 0
        #print('#', best)
        return best

def turn(self, perspectiveState):
    r,c = perspectiveState.shape
    bestVal = -1000
    bestR, bestC = -1, -1

    for i in range(r):
        for j in range(c):
            if perspectiveState[i,j] == 0:
                perspectiveState[i,j] = 1
                moveVal = self.minimax(perspectiveState, False)
                #undo
                perspectiveState[i,j] = 0
                if moveVal > bestVal:
                    bestVal = moveVal
                    bestR = i
                    bestC = j

    return bestR, bestC

Upvotes: 0

Views: 949

Answers (1)

falzberger
falzberger

Reputation: 88

I have used the traditional minimax algorithm without pruning .

And that is already the answer to your question. This is why pruning and remembering past states is such an important topic in algorithmic design.

If you increase the board size to 4x4 you'll have exponential growth and experience an explosion of computational time. If you estimate the possible number of moves in a 3x3 board, you will have (3x3)! = 9!, which equals 362 880 moves.

If you now do this for the possible moves on a 4x4 board, you will get 16! possible states, which is an incredibly large amount of 20 922 790 000 000 possible moves. Although these are just approximations, you can estimate that your computational time must be more than a million times higher.

For further explanation see: Tic-Tac-Toe minimax algorithm doesn't work with 4x4 board

Upvotes: 2

Related Questions