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

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

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

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

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

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

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.

1
2
3
4
5
6
7
8
9

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 параметрами.

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

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

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

1
2
3
4

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

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

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34

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.

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

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27

(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! вариантов перебора становится слишком много, поэтому необходимо вводить какие-то оптимизации.

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

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35

(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);
}

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