Теория игр: Minimax на C#

Прохладный мартовский вечер погрузил город в привычную темноту. Уличный шум практически сошёл на нет. И только лёгкий весенний дождь ритмично стучал в окно старшего разработчика Василия. Звуки дождя приятно успокаивали, особенно после нервного рабочего дня. Василий посильнее укутался в тёплое одеяло. Сегодня он твёрдо решил лечь спать пораньше, и казалось, всё способствовало ему в этом начинании.

— Тук-тук, тук-тук. Словно барабанщик! Или нет, как будто кто-то стучит по клавиатуре в офисе. Интересно, когда снова они откроются?

Василий вспомнил свой рабочий стол, кухню, кофемашину, своих коллег: Алекса, Антона, Майка. Майка? Только не он! Василий попытался выбросить мысли из головы, но ничего не получалось. Рабочий день опять всплыл перед глазами: очередная важная онлайн встреча, менеджер Алекс задаёт вопрос и… Василий подскочил: «Ох уж этот Алекс! Не мог он подождать со своим вопросом? Я бы в этот раз точно обыграл Майка!»

Майк был старшим разработчиком из отдела фронтэнд и частенько пересекался с Василием на этих важных совещаниях, а на одном из них зародилась традиция — играть в крестики-нолики. Это позволяло не только проводить время на встрече с пользой, но и сохранять серьёзное и задумчивое выражение лица, что определённо соответствовало общему формату и нравилось менеджерам.

Василий уже имел несколько поражений подряд, поэтому ему была необходима победа. Но неожиданный вопрос нарушил концентрацию, и он совершил досадную ошибку. «Спасибо за игру!» — написал Майк, что конечно означало «каково это в очередной раз проиграть?». «Тебе спасибо!» — ответил Василий, подразумевая «ничего, я отблагодарю тебя в следующий раз».

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

Minimax на примере крестиков-ноликов 3х3

Будем рассматривать игру со стороны первого игрока (ставящего крестики). Пусть за каждую победу игрок получает 1 очко, за поражение -1, а ничья эквивалента 0. Рассмотрим следующую расстановку на поле игры (ходит первый игрок). Ниже приведём различные развития игры для возможных ходов 1 и 2, где 1 — ход крестиком влево, а 2 — ход крестиком вниз (ход крестиком вправо аналогичен случаю 1):

Если второй игрок будет играть оптимально, то первый игрок проиграет (получит -1 очко) при ходах 1 или 3, и сыграет в ничью (получит 0 очков) при ходе 2. Поэтому правильным ходом для первого игрока будет ход 2. В этом и заключается ключевая идея алгоритма:

Minimax — это алгоритм минимизация потерь при развитии ситуации по наихудшему сценарию (в нашем случае — при оптимальной игре соперника).

Общий случай и реализация

С полной реализацией алгоритма на C# можно ознакомиться на GitHub проекта coding-interview. Ниже остановимся на самых интересных моментах. Пусть текущее состояние описывается следующим набором параметров и методов:

• Списком возможных ходов для текущего игрока GetPossibleMoves;
• Флагом, сигнализирующим, является ли текущее состояние завершающим (победа одного из игроков, либо ничья) IsTerminal;
• Текущим активным игроком ActivePlayer. Текущего активного игрока не будет, если состояние является завершающим;
• А также добавим методы для совершения и отмены хода MakeMove / UndoMove.

public interface IState<Player, Move>
    where Player: class
    where Move: class
{
    IList<Move> GetPossibleMoves();
    void MakeMove(Move move);
    void UndoMove();

    bool IsTerminal { get; }
    Player? ActivePlayer { get; }
}

Поскольку понятия Player и Move могут быть уникальными для каждой игры, мы их описываем Generic параметрами.

Перейдём непосредственно к реализации алгоритма. Как уже говорилось выше, мы пытаемся минимизировать потери, то есть выбрать такой ход, который при оптимальной игре второго игрока приведёт к наименьшим потерям. Другими словами, если мы можем получить оценки для всех возможных состояний при совершении хода, то мы выбираем тот ход, который даёт нам максимальную оценку.

Введём понятие оценочной функции в контексте нашего алгоритма:

Оценочная функция — это функция, которая для выбранного игрока даёт в общем случае примерную оценку текущему состоянию.

public interface IScoreFunction<State, Player>
{
    double Calculate(State state, Player player);
}

В примере, описанном выше, мы уже давали базовое понятие оценки для конечных состояний (-1, 0, 1). Пример реализации такой оценочной функции представлен ниже:

public class MinimaxScoreFunction : IScoreFunction<State, Player>
{
    public double Calculate(State state, Player player)
    {
        if (player == state.Game.FirstPlayer)
        {
            return CalculateForFirstPlayer(state);
        }
        else
        {
            return CalculateForSecondPlayer(state);
        }
    }

    private static double CalculateForFirstPlayer(State state)
    {
        return state.Game.State switch
        {
            GameState.FirstPlayerVictory => 1.0,
            GameState.SecondPlayerVictory => -1.0,
            _ => 0.0
        };
    }

    private static double CalculateForSecondPlayer(MinimaxAdapter state)
    {
        return state.Game.State switch
        {
            GameState.FirstPlayerVictory => -1.0,
            GameState.SecondPlayerVictory => 1.0,
            _ => 0.0
        };
    }
}

Возникает вопрос: что делать для промежуточных ходов? Как отмечалось выше, оценочная функция даёт примерные оценки текущему состоянию в общем случае, то есть это какая-то эвристика. Например, мы можем предполагать, что два крестика подряд для первого игрока лучше, чем отсутствие таковых и давать за такую позицию оценку 0.5, но, как показывалось в примере выше (ходы 1 и 3 удовлетворяют этому условию), такой подход может привести к поражению.

Эту проблему и решает алгоритм minimax. Рассмотрим какие задачи решает игрок (Игрок1) и оппонент (Игрок2) во время своего хода с точки зрения Игрока1:

Во время своего хода (Игрока1), Игрок1 должен выбрать такой ход, который приведёт его к победе, то есть максимизировать результат для Игрока1.

Во время хода оппонента (Игрока2), Игрок2 должен выбрать такой ход, который приведёт его к победе. Это эквивалентно поражению Игрока1. То есть с точки зрения Игрока1, Игрок2 должен выбрать такой ход, который минимизирует результат для Игрока1.

Реализуем это в виде рекурсивной функции. Данная функция принимает текущее состояние и игрока, для которого вычисляется оценка, и возвращает пару — численное значение оценки и ход, который необходимо совершить для получения этой оценки.

(double Score, Move? NextMove) Estimate(State state, Player player)
{
    if (state.IsTerminal)
    {
        return
        (
            Score: _scoreFunction.Calculate(state, player),
            NextMove: null
        );
    }

    var possibleMoves = state.GetPossibleMoves();

    var estimations = possibleMoves.Select((move) => {
        state.MakeMove(move);
        var (score, _) = Estimate(state, player, depth.HasValue ? depth - 1 : null);
        state.UndoMove();

        return (Score: score, Move: move);
    });

    var isOpponentTurn = player != state.ActivePlayer;

    return isOpponentTurn
        ? estimations.Aggregate((e1, e2) => e1.Score < e2.Score ? e1 : e2)
        : estimations.Aggregate((e1, e2) => e1.Score > e2.Score ? e1 : e2);
}

Оценка сложности и оптимизации

Так как в зависимости от игры будет различное разнообразие и количество ходов для каждого игрока, то оценка будет строиться на основе какого-то примера.

Вернёмся к крестикам-ноликам 3х3. Предположим, что игра ведётся не до победы одного из игроков, а до полного заполнения поля — так будет проще получить оценку. Тогда у первого игрока есть 9 вариантов совершения хода. У второго игрока остаётся только 8. Затем у первого игрока 7. И так далее. То есть 9! или O(n!) вариантов, где n — количество клеток.

Если мы рассмотрим более сложный вариант игры с большим полем (например, 20х20), где надо собрать 5 в ряд крестиков или ноликов, то, очевидно, что 400! вариантов перебора становится слишком много, поэтому необходимо вводить какие-то оптимизации.

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

(double Score, Move? NextMove) Estimate(State state, Player player, int? depth)
{
    if (state.IsTerminal)
    {
        return
        (
            Score: _scoreFunction.Calculate(state, player),
            NextMove: null
        );
    }

    if (depth.HasValue && depth <= 0)
    {
        return
        (
            Score: _scoreFunction.Calculate(state, player),
            NextMove: null
        );
    }

    var possibleMoves = state.GetPossibleMoves();
    var estimations = possibleMoves.Select((move) => {
        state.MakeMove(move);
        var (score, _) = Estimate(state, player, depth.HasValue ? depth - 1 : null);
        state.UndoMove();

        return (Score: score, Move: move);
    });

    var isOpponentTurn = player != state.ActivePlayer;

    return isOpponentTurn
        ? estimations.Aggregate((e1, e2) => e1.Score < e2.Score ? e1 : e2)
        : estimations.Aggregate((e1, e2) => e1.Score > e2.Score ? e1 : e2);
}

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