Как я могу извлечь свой лучший ход из Min Max в TicTacToe? - PullRequest
Новая
       21

Как я могу извлечь свой лучший ход из Min Max в TicTacToe?

1 голос
/ 10 февраля 2012 
        int minmax(Board game, int depth)
        {
            if (game.IsFinished() || depth < 0)
                return game.Score(game.Turn);

            int alpha = int.MinValue + 1;
            foreach (Point move in game.Generate_Moves())
            {
                Board currentBoard = game;
                currentBoard.Do_Move(move); 

                alpha = max(alpha, -minmax(currentBoard, depth-1));
                currentBoard.Undo_Move(move);
            }

            return alpha;
        }

Дело в том, что эта маленькая функция сообщает мне, является ли игра победой, проигрышем или ничьей, но как я могу получить ход, который приведет меня к победе? Мой класс Point - это простой класс с двумя координатами X, Y, и я хочу получить ответ в виде точки, чтобы я мог потом сказать что-то вроде game.Do_Move(myPoint).

В случае, если некоторые функции не очевидны:

game.IsFinished() - возвращает true, если победа / поражение / ничья в противном случае

game.Score(turn) - возвращает -1/0/1 в случае проигрыша / ничьей / выигрыша игрока со следующим ходом

game.Generate_Moves() - возвращает список доступных ходов

game.Do_Move() - пустота, применяющая ход к игре

game.Undo_Move() - говорит сам за себя

Ответы [ 2 ]

0 голосов
/ 14 февраля 2012

Было бы достаточно, если бы минимаксная функция, которая вызывается в корневом узле дерева игр, возвращает и выбранный ход, и счет.Для всех других узлов игрового дерева функция должна только возвращать счет.Таким образом, обычным способом является реализация двух слегка различающихся минимаксных функций - Посмотрите на примечание № 2 в описании к этой NegaMax Framework .
Применительно к вашему минимаксному интерфейсу у вас будет следующая дополнительная функция: 

int minimaxWithMove(Board game, int depth, Point& choosen)
{
    assert (!game.IsFinished() && depth > 0); // not possible at root node
    int alpha = int.MinValue + 1;
    foreach (Point move in game.Generate_Moves())
    {
        Board currentBoard = game;
        currentBoard.Do_Move(move);
        int score = -minmax(currentBoard, depth-1);
        if (score > alpha)
        {
            alpha = score;
            choosen = move;
        }
    }
    return alpha;
}

Обратите внимание, что я удалил вызов Undo_Move, так как он не нужен, потому что вы делаете копию game в каждой итерации.

0 голосов
/ 10 февраля 2012

Вам необходимо применить минимаксную теорему .

В основном вам нужно создать игровое дерево, где каждый узел в дереве - это позиция доски, а каждый дочерний элемент - результатзаконный ход.Листовые узлы (там, где игра заканчивается) будут иметь оценки в соответствии с game.score (), и один игрок пытается выбрать ход по пути, ведущему к высокой оценке, в то время как другой пытается выбрать ходы, которые приводят к низкойГол.Теорема поможет вам понять, как строго применить эту идею.

...