Мой опыт разработки программы для игры в шашки с помощью алгоритма минимакс

Об идее

В Интернете можно откопать сотни, а в англоязычном его сегменте — тысячи, статей о разработке алгоритмов и ИИ для игры в шахматы. Однако шашки почему-то не привлекают такого интереса. В Рунете мне не удалось найти почти ни одной интересной статьи о последовательной разработке алгоритма для игры в шашки, поэтому мне захотелось его создать самому.

Так как английские шашки (checkers) уже постигла ничейная смерть, я выбрал русские шашки, которые, кстати, сложнее английских. Краткие правила и тех и других приведены ниже:

• Шашки ходят только по клеткам черного цвета по диагонали.

• Простая шашка ходит только вперед на одно поле, а бьет — вперед и назад, перепрыгивая одно поле (в checkers — бьет только вперед)

• Дамка ходит и бьет вперед и назад на любое количество полей (в checkers — ходит вперед и назад только на 1 поле; бьет, перепрыгивая только 1 поле)

• Бить обязательно! При наличии нескольких вариантов боя — можно выбрать любой.

• Проигрывает тот, кто не может сделать ход.

Изначально я хотел писать на python, но потом решил сделать крутую красивую игру и выбрал Unity (C#). Спойлер: красивую игру я так и не сделал.

Реализация алгоритма

Разумеется классы, отвечающие за шашки на экране и в памяти алгоритма, разные. Я не буду останавливаться на MonoBehaviour Unity-скриптах и подробнее расскажу именно про мою реализацию алгоритма.

Сначала опишу, как я храню доску в памяти.

Класс шашки довольно прост: содержит, главное, тип шашки и ее позицию на поле, а также несколько вспомогательных переменных:

public enum PieceType
{
    EMPTY, WHITE_MAN, WHITE_KING, BLACK_MAN, BLACK_KING
}

public class Piece
{
    public PieceType Type { get; private set; }
    public Vector2Int Pos { get; private set; }
    public bool IsWhite { get; private set; }
    public bool IsKing { get; private set; }


    public Piece(PieceType type, Vector2Int pos)
    {
        Type = type;
        Pos = pos;
        IsWhite = type == PieceType.WHITE_MAN || type == PieceType.WHITE_KING;
        IsKing = type == PieceType.WHITE_KING || type == PieceType.BLACK_KING;
    }

    public void ChangePos(Vector2Int newPos)
    {
        Pos = newPos;
    }
    public void BecomeKing()
    {
        Type = IsWhite ? PieceType.WHITE_KING : PieceType.BLACK_KING;
        IsKing = true;
    }
    public void BecomeMan()
    {
        Type = IsWhite ? PieceType.WHITE_MAN : PieceType.BLACK_MAN;
        IsKing = false;
    }
}

Думаю, тут комментировать нечего.

Доска же это набор шашек и их ходов. Это не полный код доски, а только важное:

    public class Board
    {
        private Piece[,] _board = new Piece[8, 8]; // фигуры
        public List<Piece> Pieces { get; private set; } = new List<Piece>(); // те же фигуры, но в виде списка
        private List<Move> _currentMoves; // список возможных ходов
        private int[] _countCheckers = new int[5]; // счетчик шашек определенных групп (всех, белых обычных, белых дамок, черных обычных, черных дамок)
        private List<MemorisedMove> LastMoves = new List<MemorisedMove>();

      ...

        // Конструктор для установки доски по строке
        // searchAllMoves -- надо ли искать возможных ходы
        public Board (string arr, bool whitesMove = true, bool searchAllMoves = true)
        {
            int index = 0;
            // Проход по всем клеткам
            for (int y = 0; y < 8; y++)
            {
                for (int x = (y+1) % 2; x < 8; x += 2)
                {
                    if (arr[index] != '0')
                    {
                      // Индекс фигуры
                        int num = int.Parse(arr[index].ToString());
                      // Получаем фигуру
                        Piece piece = new Piece((PieceType) num, new Vector2Int(x, y));

                      // Устанавливаем и заносим в списки
                        _board[y, x] = piece;
                        Pieces.Add(piece);
                        _countCheckers[num]++;
                    }

                    index++;
                }
            }
            WhitesMove = whitesMove;
            _rowKingsMoves = 0;
            _jumpIndex = 0;
            _countCheckers[0] = _countCheckers[1] + _countCheckers[2] + _countCheckers[3] + _countCheckers[4];

            // Если нужно, ищем возможные ходы
            if (searchAllMoves)
                FindAllMoves();
        }

      ...
    }

• Конструктор Board() здесь строит доску по строке из цифр, где каждая цифра обозначает конкретную шашку (см. перечисление PieceType в классе Piece).

• Также есть конструктор, создающий глубокую копию доски.

(Разобью весь класс на части, чтобы не было пелены кода и можно было дать пояснения)

Следующие функции используются для поиска возможных ходов.

public void FindAllMoves ()
{
    List<Move> takingMoves = new List<Move>(); // взятия
    List<Move> simpleMoves = new List<Move>(); // простые ходы

    foreach (Piece piece in Pieces)
    {
        if (piece.IsWhite == WhitesMove)
        {
          // Для каждой фигуры сначала ищем все взятия
            takingMoves.AddRange(GetAllTakingMovesOfPiece(piece));
          // Если взятий нет, ищем простые ходы
            if (takingMoves.Count == 0)
                simpleMoves.AddRange(GetAllSimpleMovesOfPiece(piece));
        }
    }

    // Если есть взятия, отбрасываем простые ходы; иначе есть только простые ходы
    if (takingMoves.Count > 0)
    {
        // Взятия сортируем по убыванию количеству побитых шашек, чтобы сначала шли самые лучшие
        // Это поможет нам более эффективно искать сильнейшие ходы, оценивая потенциально лучшие первыми
        takingMoves.Sort((Move a, Move b) => -a.Taken.Count.CompareTo(b.Taken.Count));

        AllMoves = _currentMoves = takingMoves;
    }
    else
        AllMoves = _currentMoves = simpleMoves;
}

// Рекурсивная функция поиска взятий фигуры
// В массиве exc хранятся поля, шашки на которых мы уже побили, так как в русских шашках,
// согласно турецкому правилу, шашки снимаются с доски уже после хода (см. комментарий под кодом)
private List<Move> GetAllTakingMovesOfPiece (Piece piece, List<Vector2Int> exc = null)
{
    if (exc == null)
        exc = new List<Vector2Int>();
    List<Move> moves = new List<Move>(); // все взятия
    List<Move> movesWithFollowingTake = new List<Move>(); // взятия, после которых можно побить еще

    if (piece.IsKing)
    {
      // Перебираем все 4 направления движения
        for (int x = 1; x > -2; x -= 2)
        {
            for (int y = 1; y > -2; y -= 2)
            {
                bool opp_found = false;
                Vector2Int pos_opp = Vector2Int.zero;

              // Куда дамка встанет после прыжка
                Vector2Int target = piece.Pos + new Vector2Int(x, y);
                while (InField(target)) // Функция InField проверяет, что координаты (x, y) принадлежат полю
                {
                    if (IsEmpty(target)) // Функция IsEmpty проверяет, что поле не занято
                    {
                        if (opp_found) // Если, прыгнув на клетку target мы перепрыгнем шашку соперника, то это взятие
                            AddMove(piece.Pos, target, pos_opp); // Косвенно рекурсивно продолжаем поиск дальнейших прыжков со взятием
                    }
                    else if (_board[target.y, target.x].IsWhite == piece.IsWhite) // Если уперлись в свою шашку — то усё
                        break;
                    else
                    {
                        if (!opp_found) // Если уперлись в шашку соперника, запоминаем это
                        {
                            opp_found = true;
                            pos_opp = target;
                        }
                        else // Если уткнулись во 2-ю шашку соперника, то дальше прыгнуть не получится
                            break;
                    }
                    target += new Vector2Int(x, y);
                }
            }
        }
    }
    else
    {
      // Тут перебираем все 4 варианта взятия обычной шашки (для краткости показано только одно)
        // target - поле куда приземлимся, middle - поле, которое перепрыгнем. В данном случае прыгаем на увеличение обеих координат (вниз вправо)
        Vector2Int target = new Vector2Int(piece.Pos.x + 2, piece.Pos.y + 2);
        Vector2Int middle = new Vector2Int(piece.Pos.x + 1, piece.Pos.y + 1);
        if (InField(target) && IsEmpty(target) && !IsEmpty(middle) && _board[middle.y, middle.x].IsWhite != piece.IsWhite)
            AddMove(piece.Pos, target, middle);
        ...
        ...
        ...
    }
    if (movesWithFollowingTake.Count > 0)
        return movesWithFollowingTake;
    return moves;



    bool AddMove (Vector2Int fr, Vector2Int to, Vector2Int taken)
    {
      // Турецкий удар (см. в комментарии ниже)
        if (exc.Contains(taken))
            return false;

      // Моделируем доску, на которйо этот ход сделан
        Board nextBoard = new Board(this, deepCopyMoves:false);
        Piece thisPiece = nextBoard.MovePiece(fr, to);
        List<Vector2Int> newExc = new List<Vector2Int>(exc);
        newExc.Add(taken);

      // Проверяем, не превратилась ли наша шашка в дамку этим ходов
        bool isThisMoveKinging = !piece.IsKing && IsKinging(to, piece.IsWhite);
        List<Move> nextTakes = nextBoard.GetAllTakingMovesOfPiece(thisPiece, newExc);

        if (nextTakes.Count == 0)
        {
            moves.Add(new Move(new List<Vector2Int>() { fr, to }, new List<Vector2Int>() { taken }, isThisMoveKinging));
            return false;
        }
        else
        {
            foreach (Move nextTake in nextTakes)
            {
                List<Vector2Int> pos = nextTake.Pos;
                pos.Insert(0, fr);
                List<Vector2Int> takes = nextTake.Taken;
                takes.Add(taken);
                moves.Add(new Move(pos, takes, isThisMoveKinging || nextTake.IsKinging));
                movesWithFollowingTake.Add(new Move(pos, takes, isThisMoveKinging || nextTake.IsKinging));
            }
            return true;
        }
    }
}
// Эта функция ищет все простые ходы шашки. Она очень простая и не представляет особого интереса
private List<Move> GetAllSimpleMovesOfPiece (Piece piece)
{
    ...
}

• Здесь стоит обратить внимание на то, что все обычные ходы считаются равноценными, а взятия — нет: сильнейшие взятия это те, которые бьют больше шашек соперника.

• В функции GetAllTakingMoves, которая ищет все ходы-взятия, важную роль играет т.н. турецкое правило, согласно которому побитые шашки снимаются с доски после хода и могут мешать продолжить взятия. Например в позиции ниже, если белые возьмут дамкой e1:a5:d8:f6:d4, они не смогут взять еще и шашку c5, так как, хотя шашка b6 к тому времени уже будет побита, она все еще будет стоять на доске, мешаясь дамке белых.

  

• В функции AddMove() интерес также представляет отдельная обработка ситуации, когда шашка своим ходом превращается в дамку — в таком случае можно продолжить взятие по ее правилам.

Функция MakeMove совершает ход на доске:

public void MakeMove(Move move, bool memoriseMove = false)
{
    // Хапоминаем ход, если надо
    if (memoriseMove)
        LastMoves.Add(new MemorisedMove(move.Fr, move.To, null, move.IsKinging, _rowKingsMoves));

    // Двигаем фигуру (обновляет массив _board и позицию  в экземпляре самой фигуры,
    // возможно, также превращает экземпляр фигуры в дамку)
    MovePiece(move.Fr, move.To);

    // Удаляем из массивов побитые шашки
    foreach (Vector2Int taken in move.Taken)
    {
        Piece takenPiece = GetPiece(taken);
        _countCheckers[(int)takenPiece.Type]--;
        _countCheckers[0]--;

        Pieces.Remove(takenPiece);
        _board[taken.y, taken.x] = null;

        if (memoriseMove)
            LastMoves[LastMoves.Count - 1].AddTakenPiece(takenPiece);
    }
}

Разумеется, это только основные функции. Полный код, мониторящий доску, занимает почти 500 строк. Это довольно много, но не думаю, что можно как-то разделить ответственность: все относится непосредственно к свойствам нынешнего состояния игры.

Это все не очень интересно, и я даже мог бы найти и скачать готовый код шашек в Unity, но я решил написать его сам, чтобы лучше понимать игру. Возможно, тут можно что-то как-то кардинально улучшить и ускорить.

Перейдем к более интересным вещам

Разработка победного алгоритма

Выбранный алгоритм — минимакс. Это набор правил для принятия решений для игр с нулевой суммой (один выиграл — другой проиграл). Он основывается на том, чтобы для всех возможных ходов, предугадать ответы соперника, и для каждого ответа — выбрать свой ответ, на который опять предугадать возможные ответы соперника.

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

Если каждую позицию оценить одним числом (например, положительное — преимущество у белых, отрицательное — у черных), то на каждой итерации мы пытаемся максимизировать оценку позиции, если ход наш, и минимизировать, если ход соперника. Действительно, то что если позиция улучшается для соперника, то она ухудшается для нас. Отсюда название алгоритма -- минимакс.

Итак, к алгоритму.

Мне очень хочется назвать это не алгоритмом, а искусственным интеллектом, хотя он таковым не является. Это потому, что при разработке я назвал класс ИИ и так и продолжал о нем думать, поняв ошибку только позже.

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

Класс AI.sc умеет оценивать позицию, подсчитывая качества шашек обоих цветов на доске. Качество рассчитывается как произведение стоимости шашки, специального бонуса клетки (например, шашки в центре дороже шашек с левого или правого края доски) и Y-бонуса (бонус по вертикали: простая шашка тем дороже, чем ближе она к дамочным полям).

Качество шашки = value * _squareBonus * yBonus

Значения стоимостей и бонусов я выбрал такие:

int _checkerValue = 100; // стоимость простой шашки
int _kingValue = 250; // стоимость короля
float[,] _squareBonus = new float[8, 4] // бонус клетки
    {
        { 1.2f, 1.2f, 1.2f, 1.2f },
        { 1.15f, 1.2f, 1.2f, 1.15f },
        { 1.15f, 1.2f, 1.2f, 1.13f },
        { 1.0f, 1.2f, 1.15f, 1.0f },
        { 1.0f, 1.2f, 1.2f, 1.0f },
        { 1.0f, 1.0f, 1.0f, 1.0f },
        { 1.0f, 1.0f, 1.0f, 1.0f },
        { 1.0f, 1.0f, 1.0f, 1.0f },
    }; 

private float[] _yBonus = new float[8]; // Y-бонус

public float EvaluateMaterialAndPosition (Board board)
    {
        float eval = 0;
        // Рассчитываем качество каждой шашки
        foreach (Piece piece in board.Pieces)
        {
            Vector2Int coord = piece.Pos;
            switch (piece.Type)
            {
                case PieceType.WHITE_MAN:
                    eval += _checkerValue * _yBonus[coord.y] * _squareBonus[coord.y, coord.x / 2];
                    break;
                case PieceType.BLACK_MAN:
                    eval -= _checkerValue * _yBonus[7 - coord.y] * _squareBonus[7 - coord.y, 3 - coord.x / 2];
                    break;
                case PieceType.WHITE_KING:
                    eval += _kingValue;
                    break;
                case PieceType.BLACK_KING:
                    eval -= _kingValue;
                    break;
            }
        }
        return eval;
    }

Теперь, когда мы умеем оценивать позицию, будем рекурсивно перебирать все наши ходы, ответы на них соперника, наши ответы на ответы соперника и т.д.

Так как мы не знаем, насколько сложная нынешняя позиция и сколько таких итераций потребуется, то будем увеличивать количество итераций, т.е. сначала проанализируем позицию на глубину 2 хода, потом 4, 6 и т.д. Это называется поиск в глубину с итеративным углублением. При этом чтобы избежать бесконечного поиска введем максимальное время анализа: после его истечения мы немедленно выходим из всех функций и используем результат последней полностью завершенной итерации.

// Функция активного поиска хода запускает поиск лучшего ход в позиции
public void ActiveSearch ()
{
    int depth = 0,  startDepth = 2;
    CurrentBestMove = Move.None;
  // Единственный в позиции ход делается без раздумий
    if (_board.AllMoves.Count == 1)
    {
        CurrentBestMove = _board.AllMoves[0];
        return;
    }
    // Делаем копию доски, на которой будет проводить анализ
    // Это нужно, так как во время анализа мы будем передвигать фигуры
    Board boardCopy = new Board(_board, deepCopyMoves: true);
    _searchStartTime = DateTime.Now;
    IterativeDeepeningMinimax(boardCopy, _timeLimit, startDepth, ActiveSearchDepth, ref CurrentBestMove, ref depth, true);

    if (CurrentBestMove == Move.None)
        CurrentBestMove = boardCopy.AllMoves[new System.Random().Next(0, boardCopy.AllMoves.Count)];
}

// Функция минимакса с итеративным углублением: запускает минимакс со все большей и большей глубиной,
// при этом следя за ограничением во времени
public void IterativeDeepeningMinimax (Board board, float timeLimit, int minDepth, int maxDepth, ref Move bestMove, ref int depth, bool isWhileActiveSearch)
    {
        for (depth = minDepth; depth <= maxDepth; depth++)
        {  
            (float eval, Move tempBestMove) = Minimax(board, depth, board.WhitesMove, timeLimit);
            // Если успели полностью завершить итерацию, сохраняем ее результат
            if ((DateTime.Now - _searchStartTime).TotalSeconds < timeLimit && tempBestMove is not null && tempBestMove != Move.None)
            {    
                bestMove = (Move) tempBestMove.Clone();
            }
          // Если не успели и итерация завершилась экстренно, она неполная и ее результат нам не нужен
            else
            {
                depth -= 1;
                break;
            }
  
            // Мы перестаем искать, если на какой-то итерации найдем форсированный выигрыш
            if (eval >= Infinity && board.WhitesMove || eval <= -Infinity && !board.WhitesMove)
                break;
        }
    }

// Функция минимакса находит лучший ход в позиции за конкретного игрока
// Возвращает сам ход, а также оценку позиции, которая получится, если этот ход сделать
// depth показывает, на сколько еще итераций-рекурсий нам осталось углубиться (с каждым новым рекурсивным вызовом depth уменьшается)
// maximizingPlayer показывает, за какого игрока мы ищем лучший ход, т.е. позицию для какого игрока мы пытаемся улучшить
public (float, Move) Minimax (Board board, int depth, bool maximizingPlayer, float timeLimit)
        {
          // Проверка времени 
            if ((DateTime.Now - _searchStartTime).TotalSeconds >= timeLimit)
                return (0, null);

          // Проверяем нынешнее состояние позиции (возможно, уже гейм овер)
            GameState state = board.GetGameState();
            if (state != GameState.IN_PROCESS)
            {
                if (state == GameState.WHITE_WIN)
                    return (Infinity + depth, Move.None);
                if (state == GameState.BLACK_WIN)
                    return (-Infinity - depth, Move.None);
                else
                    return (0, Move.None);
            }

            // Если это последняя итерация, просто возвращаем оценку позиции
              // Ход здесь не важен, так как лучшим станет именно ход, ведущий к позиции с наилучшей оценкой
            if (depth == 0)
            {
                float eval = Evaluate(board);
                return (eval, Move.None);
            }

            // Если ход единственный -- см. комментарии под кодом
            if (board.AllMoves.Count == 1)
            {
                Move move = board.AllMoves[0];

                board.MakeMove(board.AllMoves[0], memoriseMove: true);
                board.OnMoveFinished(board.AllMoves[0]);
                float eval = Minimax(board, depth, alpha, beta, !maximizingPlayer, timeLimit, isWhileActiveSearch).Item1;
                board.UnmakeLastMove();
                _transpositions.Add(new Transposition(PositionCache, eval, Infinity, board.AllMoves[0]));
                return (eval, board.AllMoves[0]);
            }

            // Ищем лучший ход (за белых)
            Move bestMove = Move.None;
            if (maximizingPlayer)
            {
                float maxEval = -Infinity;
              // Проходимся по всем ходам
                foreach (Move move in board.AllMoves)
                {
                  // Делаем его
                    board.MakeMove(move, memoriseMove: true);
                    board.OnMoveFinished(move);
                  // И запускаем минимакс из полученной позиции, но со стороны ПРОТИВНИКА
                    (float eval, Move compMove) = Minimax(board, depth - 1, alpha, beta, false, timeLimit, isWhileActiveSearch);

                  // Отменяем сделанный ход
                    board.UnmakeLastMove();

                  // Проверка, что минимакс со стороны противника не завершился экстренно из-за нехватки времени
                    if (compMove == null)
                        return (0, null);
                  // Проверяем, является ли этот ход лучше наилучшего найденного
                    if (eval > maxEval)
                    {
                        maxEval = eval;
                        bestMove = move;
                    }
                }
                return (maxEval, bestMove);
            }
          // Аналогично за черных
            else
            {
                float minEval = Infinity;
                foreach (Move move in board.AllMoves)
                {
                    board.MakeMove(move, memoriseMove: true);
                    board.OnMoveFinished(move);

                    (float eval, Move compMove) = Minimax(board, depth - 1, alpha, beta, true, timeLimit, isWhileActiveSearch);
                    board.UnmakeLastMove();

                    if (compMove == null)
                        return (0, null);
                    if (eval < minEval)
                    {
                        minEval = eval;
                        bestMove = move;
                    }
                }
                return (minEval, bestMove);
            }
        }

• В функции IterativeDeepeningMinimax наглядно показано, как мы постепенно углубляемся в поиске. Если очередная итерация завершилась успешно, мы запоминаем лучший согласно ней ход; если она завершилась досрочно и экстренно из-за истечения времени поиска, то она неполная и ее результат, некорректный, нам не нужен.

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

Я считаю очень важным здесь то, что я не копирую доску, чтобы проанализировать каждый ход: ВЕСЬ поиск лучшего хода выполняется на одной доске (копии игровой), просто мы умеем совершать (make) и отменять ходы (unmake). Таким образом тяжелая функция глубокого копирования доски вызывается лишь единожды.

В целом, такой код уже способен более менее играть и даже не зевать фигуры в один-два хода!

Profit!

Улучшениe №1: alpha-beta pruning

Первым улучшением, которое в разы улучшило скорость анализа, стало альфа-бета отсечение.

Его суть заключается в том, что, например, предугадывая ход противника, мы даже не будет рассматривать откровенно глупые ходы, которые он не сделает. Ну, то есть он конечно может их сделать, но если они глупые — то нам же лучше!

Например, на картинке ниже мы (играя за максимизирующую оценку сторону (за белых)), просчитав первые 2 варианта хода, видим, что можем получить позицию с оценкой 6. Поэтому, когда мы рассчитываем третий ход и видим, что одна из его дальнейших ветвей приводит к позиции с оценкой 5, то дальше мы даже не рассчитываем, так как, даже если там и будет что-то повыше, соперник лучше выберет 5, ведь он — минимизирующая сторона (черные). А потому мы даже не будем дальше анализировать 3-ю ветку, ведь лучше просто пойти по 2-й.

Таким образом, мы можем отсечь (prune) много лишних ветвей, избавившись от заведомо ненужных вычислений. В интернете много информации об этом улучшении, поэтому я не буду дальше его разжевывать, просто скажу, как я его реализовал.

Функции минимакс я добавил аргументы alpha и beta, которые при первом вызове из IterativeDeepeningMinimax передаются как -Infinity и Infinity соответственно.

После 115-й строки я добавил проверку на отсечение по альфе:

...
alpha = Mathf.Max(alpha, eval);
if (beta <= alpha)
  break;
...

А после 139-й — по бете:

...
beta = Mathf.Min(beta, eval);
if (beta <= alpha)
    break;
...

Double profit!

Улучшениe №2: транспозиции

Во время просчета позиций часто возникают одинаковые позиции. Разумеется, нет смысла рассчитывать их снова и снова в разных ветках минимакса, а потому мы можем сохранять однажды найденный лучший ход позиции.

Стоит понимать, что если в позиции X на глубине d найден лучший ход n, то этот же ход является лучшим в той же позиции и на глубинах меньше d. А вот на глубинах больше d — не факт: возможно, нам казалось, что он лучший, но мы просто не досчитали и на самом деле ход проигрывающий. Если же в позиции X ход n ведет к форсированной победе, то глубину можно считать бесконечной, так как мы точно знаем, что ход выигрывающий.

Позиции считаются одинаковыми, если не только все шашки стоят на одинаковых местах, но и очередность хода совпадает.

Транспозиции будут храниться в списке private List<Transposition> _transpositions = new List<Transposition>();

Где класс транспозиции выглядит так:

public class Transposition
{
    public string Pos { get; private set; }
    public float Eval { get; private set; }
    public int Depth { get; private set; }
    public Move BestMove { get; private set; }

    public Transposition(string pos, float eval, int depth, Move bestMove)
    {
        Pos = pos;
        Eval = eval;
        Depth = depth;
        BestMove = bestMove;
    
    }
    public bool IsSameTo (string otherPos)
        => Pos == otherPos;
}

В начале функции Minimax() (после, конечно, проверки на истечение времени) будем проверять, не встречали ли мы ранее данную позицию на подходящей глубине:

string PositionCache = board.Board2Number(); // Переводит позицию в строку

Transposition pos_trans = null;
pos_trans = _transpositions.FirstOrDefault(tr => tr.IsSameTo(PositionCache));
if (pos_trans != null)
{
    if (pos_trans.Depth >= depth)
    {
        return (pos_trans.Eval, pos_trans.BestMove);
    }
}

Позиции, кстати, сравниваются как строки, т.к. каждую позицию можно однозначно представить как строку из 32 символов - фигур на черных полях (+1 символ для очередности хода).

Если же транспозиция не найдена, то запускаем обычный поиск. Когда мы завершаем цикл, перед тем как вынести решение по позиции, будем добавлять ее в список транспозиций, как вклад в будущее:

// за белых
AddTransposition(new Transposition(PositionCache, maxEval, depth, bestMove));
return (maxEval, bestMove);

// за черных
AddTransposition(new Transposition(PositionCache, minEval, depth, bestMove));
return (minEval, bestMove);

Функция AddTransposition просто добавляет транспозицию в список, не забывая убедиться, что там уже нет такой же позиции, но на меньшей глубине. В таком случае она стирается, так как зачем нам менее глубокий анализ, если уже подоспел более глубокий?!

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

Triple profit!

Улучшение №3: книга дебютов и эндшпилей

Особую сложность при расчетах представляют дебюты (начало игры) и эндшпили (ее окончание). Это так, потому что в дебюте нужно уметь считать очень далеко, чтобы понять последствия нашего хода, ведь фигуры только развиваются; в эндшпиле же фигур меньше, однако гораздо больше ходов (за счет наличия дальнобойных дамок) и анализ даже простейших позиций может быть долгим.

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

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

Однако мне удалось найти стандартизированные записи шашечных партий и выудить из них дебюты и эндшпили (несколько первых ходов из каждой партии и несколько последних). Поэтому я подключаю к своему алгоритму два блока:

private OpeningBook _openingBook;
private EndgameBook _endgameBook;

Классы OpeningBook и EndgameBook наследуются от абстрактного TheoryBook, который умеет искать данную позицию в справочнике и возвращать лучший в ней ход:

public abstract class TheoryBook
{
    protected abstract string TheoryPath { get; }
    private BookRecord _records;

    public TheoryBook()
    {
        Debug.Log(TheoryPath);
        using (StreamReader reader = new StreamReader(TheoryPath))
        {
            _records = JsonUtility.FromJson<BookRecord>(reader.ReadToEnd());
        }
        _records.BuildUpDictionary();
    }

    public bool TryGetBestMove(string pos, out string move)
    {
        if (_records.ContainsPosition(pos))
        {
            move = _records.GetMoveFor(pos, BookRecord.BookMoveSelector.Random);
            return true;
        }
        else
        {
            move = null;
            return false;
        }
    }
}

[System.Serializable]
public class BookRecord
{
    public List<string> positions;
    public List<string> moves;
    public int CountRecords => moves.Count;

    private Dictionary<string, List<string>> _pairs;

    public enum BookMoveSelector
    {
        Random, First, Last
    }

    public BookRecord()
    {
        positions = new List<string>();
        moves = new List<string>();
    }

    public void AddRecord(string pos, string move)
    {
        positions.Add(pos);
        moves.Add(move);
    }

    public void BuildUpDictionary()
    {
        _pairs = new Dictionary<string, List<string>>();
        for (int i = 0; i < CountRecords; i++)
        {
            if (_pairs.ContainsKey(positions[i]))
                _pairs[positions[i]].Add(moves[i]);
            else
                _pairs.Add(positions[i], new List<string>() { moves[i] });
        }
    }

    public bool ContainsPosition(string pos)
    {
        return _pairs.ContainsKey(pos);
    }
    public string GetMoveFor(string pos, BookMoveSelector selector)
    {
        switch (selector)
        {
            case BookMoveSelector.Random:
                return _pairs[pos][new System.Random().Next(0, _pairs[pos].Count)];
            case BookMoveSelector.First:
                return _pairs[pos][0];
            case BookMoveSelector.Last:
                return _pairs[pos][_pairs[pos].Count - 1];
            default:
                return _pairs[pos][0];
        }
    }
}

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

К сожалению, выборка партий была очень маленькой (несколько тысяч), а и эндшпили, и, особенно, дебюты в ней повторялись, поэтому очень сильного прироста качества игры это не дало. Найти же большую выборку или готовые базы мне не удалось...

Анализ результатов

Мы получили работающую программу для игры в русские шашки.

Лично меня она разносит в пух и прах (возможно, потому что еще за пару месяцев до начала разработки я не умел нормально играть в шашки и зевал фигуры каждый ход). Я также дал ей сыграть с некоторыми приложениями в плеймаркете и она обыгрывает многие из них на большинстве уровней сложности. Оно также обыгрывает любителей в приложении Quick Checkers.

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

Например, возможно, отношение стоимости обычной шашки к дамке должно быть не 100:250, а 100:150 или 100:500. Возможно, стоять в центре, а не на краю шашкам выгоднее не в 1.25 раза, а в 1.1 или 1.5.

Возможно, возможно, возможно...

Разумеется, это все можно настроить, если реализовать "турнир" между компьютерами и постепенно мутировать эти числа, однако чтобы программа могла адекватно играть, ей нужно 10-15 секунд на КАЖДЫЙ ХОД (что дает глубину анализа 9-10 ходов вперед). Так как в шашечной партии в среднем ходов 30, одна такая партия может занять 5-8 минут, а чтобы построить нормальный процесс мутационной эволюции потребуется организовать, пожалуй, сотни и тысячи партий.

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

P.S. Предложениям буду рад, конечно, всем, но что-то высшематематическое вряд ли смогу реализовать. Уровень продвинутой школьной математики:)