Минимаксный алгоритм не работает для 4x4 TicTacToe - PullRequest
Новая
       55

Минимаксный алгоритм не работает для 4x4 TicTacToe

0 голосов
/ 20 сентября 2018

Итак, я написал следующий агент для бота, чтобы играть в крестики-нолики.Я использовал традиционный минимаксный алгоритм без обрезки.Дело в том, что он отлично работает на плате 3х3.

Но когда я запускаю это на плате 4х4, он зависает в вычислениях.Я не могу понять, почему.Я передаю агенту массив NumPy perspectiveState, в котором 0 для пустых, 1 для ходов агентов и -1 для ходов противников.Он возвращает позицию своего следующего хода (1).

Поток управления начинается с функции turn(), которая вызывает функцию minimax().

Что я здесь не так делаю? 

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

1 Ответ

0 голосов
/ 20 сентября 2018

Я использовал традиционный минимаксный алгоритм без обрезки .

И это уже ответ на ваш вопрос.Вот почему сокращение и запоминание прошлых состояний является такой важной темой в алгоритмическом проектировании.

Если вы увеличите размер платы до 4x4, вы получите экспоненциальный рост и испытаете взрыв вычислительного времени.Если вы оцените возможное количество ходов на доске 3х3, у вас будет (3х3)!= 9 !, что равняется 362 880 ходам.

Если вы теперь сделаете это для возможных ходов на доске 4x4, вы получите 16!возможные состояния, что невероятно большое количество из 20 922 790 000 000 возможных ходов.Хотя это только приблизительные значения, вы можете оценить, что ваше вычислительное время должно быть более чем в миллион раз больше.

Для дальнейшего объяснения см .: Алгоритм минимакса Tic-Tac-Toe не работает с доской 4x4

...