3D Tic Tac Toe с минимаксной и альфа-бета-обрезкой выбирает неоптимальные движения

Question

Я пытаюсь реализовать Minimax с отсечкой альфа-бета для игры 3D Tic Tac Toe. Однако, похоже, алгоритм выбирает субоптимальные пути.

Например, вы можете выиграть, просто пробежавшись по середине куба или по одной доске. Похоже, ИИ выбирает ячейки, которые будут оптимальными на следующий ход, а не на текущий ход.

Я попытался воссоздать и поиграть с эвристикой, которую я возвращаю для алгоритма, но я не добился большого прогресса. Независимо от сгиба у него, похоже, одна и та же проблема.

Код здесь.

Соответствующие части computers_move а также think_ahead (и варианты "2", это просто я экспериментирую с немного альтернативным подходом).

Я надеюсь, что это может быть что-то простое, что я упустил из виду, но, насколько я могу судить, я не уверен, в чем проблема. Если кто-то может пролить свет на проблему, я буду очень признателен.

def computers_move2(self):
    best_score = -1000
    best_move = None
    h = None
    win = False

    for move in self.allowed_moves:
        self.move(move, self.ai)
        if self.complete:
            win = True
            break
        else:
            h = self.think_ahead2(self.human, -1000, 1000)
        self.depth_count = 0
        if h >= best_score:
            best_score = h
            best_move = move
            self.undo_move(move)
        else:
            self.undo_move(move)

    if not win:
        self.move(best_move, self.ai)
    self.human_turn = True

def think_ahead2(self, player, a, b):
    if self.depth_count <= self.difficulty:
        self.depth_count += 1
        if player == self.ai:
            h = None
            for move in self.allowed_moves:
                self.move(move, player)
                if self.complete:
                    self.undo_move(move)
                    return 1000
                else:
                    h = self.think_ahead2(self.human, a, b)
                    if h > a:
                        a = h
                        self.undo_move(move)
                    else:
                        self.undo_move(move)
                if a >= b:
                    break
            return a
        else:
            h = None
            for move in self.allowed_moves:
                self.move(move, player)
                if self.complete:
                    self.undo_move(move)
                    return -1000
                else:
                    h = self.think_ahead2(self.ai, a, b)
                    if h < b:
                        b = h
                        self.undo_move(move)
                    else:
                        self.undo_move(move)
                if a >= b:
                    break
            return b
    else:
        diff = self.check_available(self.ai) - self.check_available(self.human)
        return diff

Answer 1

Оказывается, мой алгоритм работает нормально. Проблема была вызвана моими вспомогательными функциями move а также undo_move, Кроме того, основной проблемой был мой набор разрешенных ходов.

Я заметил, что во время исследования дерева количество ходов сильно уменьшилось во внешней петле computer_plays, Даже во время первого цикла число разрешенных ходов за пару ходов для компьютера и игрока снизится, скажем, с 27, до 20, затем 10 и, в конечном итоге, 5.

Оказывается, временно проверенные ходы не заменялись. Поэтому я поменял набор на стандартный список и отсортировал список после каждого перемещения / отмены и полностью решил свои проблемы.