Как именно работает минимаксная рекурсия?

Сначала мы будем использовать ваши крестики-нолики в качестве примера.

• Минимаксный алгоритм лучше всего работает для игр, в которых игроки делают ходы поочередно, но его можно адаптировать и к играм, в которых игроки могут делать несколько ходов за ход. Примем первое для простоты. В этом случае вам не нужно хранить «X для перемещения» или «O для перемещения» с каждым узлом, потому что это можно просто определить по четности глубины узла (будь то четное количество шагов или нечетное). количество шагов сверху).
• Генерация возможных ходов из каждой позиции требует, чтобы вы знали, чей это ход (который можно определить, как и раньше), и правила для допустимых ходов из конкретной позиции. Для простой игры, такой как крестики-нолики, для заданной позиции достаточно перечислить все состояния, состоящие из копии текущей позиции плюс новая фишка, принадлежащая текущему игроку, помещаемая по очереди на каждую пустую клетку. В таких играх, как «Отелло», вы также должны проверять каждое размещение, чтобы убедиться, что оно соответствует правилам, и обновлять конечную позицию в соответствии с последствиями правила (для «Отелло» — переворачиванием цветов группы фишек). В общем, из каждой действительной позиции, которую вы отслеживаете, вы перечисляете все возможные места размещения новой фигуры и проверяете, какие из них разрешены набором правил.
• В общем, вы НИКОГДА не генерируете все дерево целиком, так как размеры игрового дерева могут легко превысить емкость памяти Земли. Вы всегда устанавливаете максимальную глубину итерации. Таким образом, конечный узел — это просто узел на максимальной глубине или узел, из которого не существует допустимых ходов (для крестиков-ноликов — доска, на которой все клетки заполнены). Вы не создаете конечные узлы заранее; они генерируются естественным образом во время построения дерева игры. Крестики-нолики достаточно просты, чтобы вы могли сгенерировать все дерево игры, но не пытайтесь использовать свой код крестиков-ноликов, например, для Отелло.

Глядя на ваш псевдокод:

• max(a, b) — это любая функция, которая возвращает большее из a или b. Обычно это предоставляется математической библиотекой или чем-то подобным.
• depth — это максимальная глубина поиска.
• Эвристическое значение, которое вы вычисляете, представляет собой некоторое числовое значение, описывающее ценность доски. Для такой игры, как крестики-нолики, которая настолько проста, что вы МОЖЕТЕ перечислить все игровое дерево, вы можете обозначить 1 для позиции на доске, которая выигрывает для игрока, проводящего анализ, -1 для позиции на доске, которая выигрывает для другого игрока. игрок и 0 за любую неубедительную позицию. В общем, эвристику придется выдумывать самому или использовать общепринятую.
• Вы создаете узлы на лету во время анализа на основе их родительских узлов. Ваш корневой узел всегда является той позицией, с которой вы проводите анализ.

Если вы еще не работали с графами или деревьями, я предлагаю вам сделать это в первую очередь; в частности, примитив дерева необходим для решения этой проблемы.

В качестве ответа на комментарий в этой теме с просьбой привести пример определения того, чья сейчас очередь для данного узла, я предлагаю этот псевдо-Питон:

who_started_first = None

class TreeNode:
    def __init__(self, board_position = EMPTY_BOARD, depth = 0):
        self.board_position = board_position
        self.children = []
        self.depth = depth
    def construct_children(self, max_depth):
        # call this only ONCE per node!
        # even better, modify this so it can only ever be called once per node
        if max_depth > 0:

            ### Here's the code you're actually interested in.
            if who_started_first == COMPUTER:
                to_move = (COMPUTER if self.depth % 2 == 0 else HUMAN)
            elif who_started_first == HUMAN:
                to_move = (HUMAN if self.depth % 2 == 0 else COMPUTER)
            else:
                raise ValueError('who_started_first invalid!')

            for position in self.board_position.generate_all(to_move):
                # That just meant that we generated all the valid moves from the
                # currently stored position. Now we go through them, and...
                new_node = TreeNode(position, self.depth + 1)
                self.children.append(new_node)
                new_node.construct_children(max_depth - 1)

Каждый узел способен отслеживать свою абсолютную глубину от «корневого» узла. Когда мы пытаемся определить, как мы должны генерировать позиции на доске для следующего хода, мы проверяем, чей это ход, основываясь на четности нашей глубины (результат self.depth % 2) и нашей записи о том, кто сделал ход первым.

1) Как минимакс узнает, чья сейчас очередь? Как лучше всего указать игрока, чей ход он генерирует?

У вас есть этот depth аргумент. Если глубина четная, то ход одного игрока, если нечетная, то ход другого игрока.

2) Как вы генерируете возможные ходы?

Использование правил игры. В крестиках-ноликах возможный ход означает размещение метки в свободной клетке.

3) Как узнать, что вы находитесь в терминальном узле, и как вы генерируете конечные узлы?

Терминальный узел — это узел, в котором кто-то выиграл. Вы генерируете их рекурсией. Каждому рекурсивному вызову должно быть дано текущее состояние доски. Я предполагаю, что это параметры node и child в вашем псевдокоде. Так что, если в этой ситуации кто-то выиграл, то это терминально, иначе вы пробуете все допустимые ходы и рекурсивно.

Я могу дать некоторое представление о том, что вы ищете, поскольку я написал минимаксный алгоритм для крестиков-ноликов.

Чтобы ответить на ваши вопросы напрямую:

1. Мой минимаксный алгоритм этого не определил. Он принимал аргумент, который определял, какой игрок использовался алгоритмом.

2. Зная, какой игрок должен двигаться, пройдитесь по всем пустым клеткам на доске и для каждой сгенерируйте узел с жетоном текущего игрока в этой клетке. Рекурсивно продолжайте оттуда.

3. Я использовал функцию, которая возвращала значение, указывающее, закончилась ли игра, и была ли это ничья или выигрыш.

Мой основной алгоритм сделал это:

• Входные данные: игрок, которого нужно переместить, и состояние доски.
• Find all blank spaces left on the board.
  • Generate a new board with the player's move in that space.
  • Если игра окончена, сгенерируйте узел с результатом игры.
  • В противном случае запустите алгоритм, передав другого игрока и новую доску, и сгенерируйте узел с результатом идеального хода противника.
• Определите, какой узел (перемещение) ведет к наилучшему из возможных наихудших случаев.
• Выход: Лучший ход и информация о результате игры по нему.