Как именно работает MiniMax Recursion?

StackOverflow https://stackoverflow.com//questions/11703846

Вопрос

Итак, я искал мини-макс для игры Tic-Tac-Toe, но не мог понять, как работала рекурсия?Хорошо, так в основном вот мои вопросы:

  1. Как miniMax знает, чья очередь это?Какой лучший способ указать игрок, чья поворот его генерирует?
  2. Как вы генерируете возможные движения?
  3. Как вы знаете, когда вы находитесь в узле терминала, и как вы генерируете узлы клемм?

    4. Например, в этом псевдокозе 

    function integer minimax(node, depth)
if node is a terminal node or depth <= 0:
    return the heuristic value of node
α = -∞
for child in node: # evaluation is identical for both players
    α = max(α, -minimax(child, depth-1))
return α
    .

    Генеракодицетагкод - это доска правильная?И это глубина, сколько слоев код должен идти в рекурсию?Также какова функция node и где из генерируемых узлов?

    Теперь, пока у меня есть этот код для создания доски: 

    class Board{
    public:
        Board();
        ~Board(){};
    public: // The board
        // In the board, 1 is x, 2 is o, 0 is empty square.
        int board[3][3];
};
    .

    Но как бы я узнал, чья очередь?И как я могу генерировать детские узлы для доски?

Это было полезно?

Решение

Мы будем использовать ваш Tic-Tac-Toe в качестве примера.

    .
  • Алгоритм MiniMax работает лучше всего для игр, где плееры чередуются повороты, но могут быть адаптированы к играм, где игроки могут сделать несколько шагов на поворот. Мы предположим, что бывшая, для простоты. В этом случае вам не нужно хранить «x, чтобы переместить» или «o переместить» с каждым узлом, потому что это может быть просто определено четностью глубины узла (будь то четный номер шагов или нечетное Количество шагов сверху).
  • Генерация возможных движений из каждой позиции требует, чтобы вы знали, чьи движутся он (который можно определить как раньше), а правила для законных ходов из определенной позиции. Для простой игры, такой как Tic-Tac-Toe, учитывая позицию, достаточно перечислять все состояния, которые состоят из копии текущей позиции плюс новую часть, принадлежащую текущему плееру, размещенным на каждом пустом квадрате. Для игр, таких как Othello, вы также должны проверить каждое размещение, чтобы гарантировать, что он следует за правилами и обновлять конечную позицию в соответствии с последствиями правила (для Отелло, переворачивая цвета кучу кусков). В целом, от каждой допустимой позиции вы отслеживаете, вы перечисляете все возможные размещения новой части и проверьте, какие из них разрешены на правила.
  • В общем, вы никогда не генерируете все дерево, так как размеры дерева игр могут легко превышать емкость хранения Земли. Вы всегда устанавливаете максимальную глубину итерацию. Затем клеммный узел - это просто узел на максимальной глубине или узел, из которого не существует никаких юридических движений (для TIC-TAC-TOE, доска с заполненной каждым квадратом). Вы не генерируете терминальные узлы заранее; Они генерируются естественным образом во время строительства игры. Tic-Tac-Toe достаточно просто, чтобы вы можете создать все игровое дерево, но затем не пытайтесь использовать свой код TIC-TAC-TAC для E.G. Отелло.

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

    .
  • max(a, b) - это любая функция, которая возвращает большую часть генеракодицетагкода или генеракодицетагкода. Это обычно предоставляется математической библиотекой или аналогичной.
  • Генеракодицетагкод - максимальная глубина, к которой вы будете искать.
  • Эвристическая ценность Вы вычислительные, - это некоторое числовое значение, которое описывает значение доски. Для игры, как Tic-Tac-Toe, которая достаточно проста, чтобы вы могли перечислить все игровое дерево, вы можете обозначить a для позиции доски, который выигрывает для игрока, выполняющего анализ, b для положения доски, который выигрывает для другого Игрок и генеракодицетагкод для любого неубедительного положения. В общем, вам придется приготовить эвристическое себя или использовать хорошо принятое.
  • Вы генерируете узлы на лету во время анализа на основе их родительских узлов. Ваш корневой узел всегда является положением, с которого вы делаете анализ.

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

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

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)
.

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

Другие советы

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

У вас есть этот аргумент depth.Если глубина даже, то поворот одного игрока, если это странно, то это другой поворот игрока.

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

Использование правил игры.В Tic Tac Toe возможный шаг означает размещение отметки в свободную клетку.

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

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

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

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

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

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

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

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

      .
    • вход: игрок перемещается и состояние платы.
    • Найти все пробелы, оставленные на доске.
        .
      • генерирует новую доску с ходом игрока в этом пространстве.
      • Если игра закончится, генерируйте узел результатом игры.
      • В противном случае запустите алгоритм, проходящий в другом игроке и новую доску и генерировать узел с результатом идеального движения противника.
    • определить, какой узел (перемещение) приводит к наилучшему наихудшемую страну.
    • Выход: лучший ход и информация о результате игры от нее.
Лицензировано под: CC-BY-SA с атрибуция
Не связан с StackOverflow
scroll top