Minimax.Connect4/Connect4Minimax.cs

using System.Collections.Concurrent;
using Connect4;

namespace MinMaxAB;

/// <summary>
/// Реализация MiniMax-алгоритма для игры в 4 в ряд
/// </summary>
public class Connect4Minimax
{
    /// <summary>
    /// Посчитать счет доски из количества последовательностей игрока и ИИ
    /// </summary>
    /// <param name="player">Количество последовательностей игрока</param>
    /// <param name="computer">Количество последовательностей ИИ</param>
    /// <returns></returns>
    protected static int EvaluateScoreDiff(int player, int computer)
    {
        if ((player == 0 && computer == 0) || (computer > 0 && player > 0)) return 0;

        if (computer > 0)
        {
            // Последовательности растут экспоненциально. Для более агрессивной игры - увеличить значения
            return computer switch
            {
                1 => 1,
                2 => 8,
                3 => 64,
                _ => 0
            };
        }

        if (player > 0)
        {
            // Последовательности игрока проигрышны для ИИ. Для более пассивной игры ("в защиту") - увеличить значения
            return player switch
            {
                1 => -1,
                2 => -8,
                3 => -64,
                _ => 0
            }; ;
        }

        return 0;
    }

    /// <summary>
    /// Посчитать итоговый счет по всем направлениям для компьютера
    /// </summary>
    /// <param name="board">Игровая доска</param>
    /// <returns>Итоговый счет по всем направлениям для компьютера</returns>
    public static int CountSequences(GameBoard board)
    {
        int score = 0;

        // Считаем по горизонтали
        for (int col = 0; col < board.dimensions.Columns; col++)
        {
            for (int row = 0; row < board.dimensions.Rows - 3; row++)
            {
                int c = 0;
                int p = 0;

                for (int k = 0; k < 4; k++)
                {
                    if (board.cells[col][row + k] == Player.Computer) c++;
                    else if (board.cells[col][row + k] != Player.None) p++;
                }

                score += EvaluateScoreDiff(p, c);
            }
        }

        // По вертикали
        for (int col = 0; col < board.dimensions.Columns - 3; col++)
        {
            for (int row = 0; row < board.dimensions.Rows; row++)
            {
                int c = 0;
                int p = 0;

                for (int k = 0; k < 4; k++)
                {
                    if (board.cells[col + k][row] == Player.Computer) c++;
                    else if (board.cells[col + k][row] != Player.None) p++;
                }

                score += EvaluateScoreDiff(p, c);
            }
        }

        // По диагонали
        for (int col = 0; col < board.dimensions.Columns - 3; col++)
        {
            for (int row = 0; row < board.dimensions.Rows - 3; row++)
            {
                int c = 0;
                int p = 0;

                for (int k = 0; k < 4; k++)
                {
                    if (board.cells[col + k][row + k] == Player.Computer) c++;
                    else if (board.cells[col + k][row + k] != Player.None) p++;
                }

                score += EvaluateScoreDiff(p, c);
            }
        }

        // По второй диагонали
        for (int col = 3; col < board.dimensions.Columns; col++)
        {
            for (int row = 0; row < board.dimensions.Rows - 3; row++)
            {
                int c = 0;
                int p = 0;

                for (int k = 0; k < 4; k++)
                {
                    if (board.cells[col - k][row + k] == Player.Computer) c++;
                    else if (board.cells[col - k][row + k] != Player.None) p++;
                }

                score += EvaluateScoreDiff(p, c);
            }
        }

        return score;
    }

    /// <summary>
    /// Итерация minimax-алгоритма
    /// </summary>
    /// <param name="board">Копия игровой доски для текущей итерации</param>
    /// <param name="depth">Оставшаяся глубина просчета</param>
    /// <param name="maxPlayer">Максимизировать игрока (иначе - минимизировать)</param>
    /// <param name="alpha">Минимальный порог счета</param>
    /// <param name="beta">Максимальный порог счета</param>
    /// <returns>Счет ИИ для текущего хода</returns>
    private static int EvaluateMinMax(GameBoard board, int depth, bool maxPlayer = false, int alpha = int.MinValue, int beta = int.MaxValue)
    {
        var currentWinner = board.GetWinner();

        // Выходим, если выиграли или проиграли
        if (currentWinner == Player.Computer) return (depth + 1) * 100_000;
        else if (currentWinner == Player.Human) return -(depth + 1) * 100_000;

        // Выходим, если больше некуда ходить
        if (!board.HasEmptyColumns()) return 0;

        // Последняя итерация
        if (depth == 0) return CountSequences(board);

        int best = maxPlayer ? int.MinValue : int.MaxValue;

        // Считаем все возможные ходы
        for (int i = 0; i < board.dimensions.Columns; i++)
        {
            // Если невозможно сделать ход
            if (!board.PlaceCoin(maxPlayer ? Player.Computer : Player.Human, i)) continue;

            // Итерация оппонента
            int x = EvaluateMinMax(board, depth - 1, !maxPlayer, alpha, beta);
            // Выбираем лучший (или худший) исход
            best = maxPlayer ? int.Max(best, x) : int.Min(best, x);
            // Отменяем сделанный ход
            board.RemoveFromTop(i);

            // Обновляем альфа-бета значения
            if (maxPlayer) alpha = int.Max(alpha, best);
            else beta = int.Min(beta, best);

            // Если альфа и бета разошлись в противоположные стороны - выходим
            if (beta <= alpha) break;
        }

        return best;
    }

    /// <summary>
    /// Найти самый лучший следующий ход
    /// </summary>
    /// <param name="board">Текущее состояние доски</param>
    /// <param name="depth">Глубина просчета</param>
    /// <returns>Номер столбца для лучшего хода</returns>
    public static int GetBestMove(GameBoard board, int depth)
    {
        ConcurrentBag<(int Column, int Score)> moves = [];
        // Считаем все ходы параллельно
        Parallel.For(0, board.dimensions.Columns, i =>
        {
            // Копируем доску для этой вселенной (нужно для параллелизации)
            var newBoard = board.Clone();
            // Если поместить монетку в этот столбец уже нельзя - пропускаем
            if (!newBoard.PlaceCoin(Player.Computer, i)) return;
            // Сохраняем счет для этого хода
            moves.Add((i, EvaluateMinMax(newBoard, depth)));
        });

        // Находим счет с максимальным счетом, с приоритетом на центральные колонки
        return moves.OrderByDescending(m => m.Score).ThenBy(m => int.Abs(m.Column - (board.dimensions.Columns / 2))).First().Column;
    }
}