Крестики-нолики с алгоритмом минимакса (на C#)


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

  • Что бы вы хотели изменить?
  • Я что-нибудь упустил, что может причинить вред?
  • Есть ли лучший подход или смысл оптимизации?

Плеер

Для того, чтобы избежать примитивных одержимость (работа со строками...) есть представительство плеер с необходимым методом для проверки равенства.

public class Player : IEquatable<Player>
{
    public static readonly Player Blank = new Player('\0');

    public Player(char mark)
    {
        Mark = mark;
    }

    public char Mark { get; }
    public static bool IsBlank(Player player) =>
        player == null || player.Equals(Blank);

    public bool Equals(Player other) =>
        other != null
        && Mark == other.Mark;

    public override bool Equals(object obj)
    {
        if (ReferenceEquals(null, obj))
        {
            return false;
        }

        return obj is Player player && Equals(player);
    }

    public override int GetHashCode() =>
        Mark.GetHashCode();
}

Представительство площадка

Игровое поле, зная их количество и то ли плеер забрали ее или нет. Базовый блок площадка.

[DebuggerDisplay("{Index}: {Player != null ? Player.Mark.ToString() : \"-\"}")]
public struct Field
{
    private Player _player;

    public Field(int index)
    {
        Index = index;
        _player = null;
    }

    public int Index { get; }
    public bool IsEmpty => _player == null;
    public Player Player
    {
        get => _player;
        set => _player = value ?? throw new ArgumentException("Cannot set null player.");
    }
}

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

public class Playground
{
    private static readonly (int, int, int)[] WinningCoords =
    {
        (0, 1, 2), // 1st row
        (3, 4, 5), // 2nd row
        (6, 7, 8), // 3rd row
        (0, 3, 6), // 1st col
        (1, 4, 7), // 2nd col
        (2, 5, 8), // 3rd col
        (0, 4, 8), // top left -> bottom right
        (2, 4, 6), // bottom left -> upper right
    };

    private readonly Field[] _fields;
    private readonly int _emptyFields;

    public Playground()
    {
        _fields = new Field[9];
        _emptyFields = _fields.Length;

        // initialize fields
        for (var i = 0; i < _fields.Length; i++)
        {
            _fields[i] = new Field(i + 1);
        }
    }

    private Playground(Field[] field)
    {
        _fields = field;
        _emptyFields = _fields.Count(f => f.Player == null);
    }

    public IReadOnlyList<Field> Fields => _fields;

    public Playground Turn(int index, Player player)
    {
        if (index < 1 || index > _fields.Length)
        {
            throw new ArgumentOutOfRangeException(
                nameof(index),
                $"Invalid turn, allowed index is in range [1..{_fields.Length}]");
        }

        if (Player.IsBlank(player))
        {
            throw new ArgumentException("Cannot turn with blank player.", nameof(player));
        }

        if (!_fields[index - 1].IsEmpty)
        {
            throw new ArgumentException($"Field {index} is already occupied.", nameof(index));
        }

        // copying array of structs - copying values
        var fields = new Field[9];
        _fields.CopyTo(fields, 0);

        // turn with player
        fields[index - 1].Player = player;

        return new Playground(fields);
    }

    public PlaygroundState GetState()
    {
        // player can win in 5th turn in the best case
        if (_emptyFields > 4)
        {
            return PlaygroundState.NotComplete;
        }

        bool FieldEqual(Field f1, Field f2)
        {
            return !Player.IsBlank(f1.Player) && f1.Player.Equals(f2.Player);
        }

        // try to find winner (rows, cols, diagonales)
        foreach ((int, int, int) i in WinningCoords)
        {
            (int a, int b, int c) = i;
            if (FieldEqual(_fields[a], _fields[b]) && FieldEqual(_fields[b], _fields[c]))
            {
                return PlaygroundState.Winner(_fields[a].Player);
            }
        }

        return _emptyFields == 0
            ? PlaygroundState.Tie
            : PlaygroundState.NotComplete;
    }
}

Чтобы сохранить площадку как минимальными, так как это может быть, есть метод расширения для пустых полей (ничего сложного).

public static class PlaygroundExtensions
{
    public static IEnumerable<Field> EmptyFields(this Playground playground)
    {
        if (playground == null)
        {
            throw new ArgumentNullException(nameof(playground));
        }

        return playground.Fields.Where(f => f.IsEmpty);
    }
}

Состояние спортивная площадка имеет необходимую информацию о состоянии игры - это просто контейнер для хранения информации.

public class PlaygroundState
{
    public static readonly PlaygroundState NotComplete = new PlaygroundState(GameState.NotComplete, Player.Blank);
    public static readonly PlaygroundState Tie = new PlaygroundState(GameState.Tie, Player.Blank);

    private PlaygroundState(GameState state, Player player)
    {
        State = state;
        Player = player;
    }

    public GameState State { get; }
    public Player Player { get; }

    public static PlaygroundState Winner(Player player) => new PlaygroundState(GameState.Winning, player);
}

... и само состояние игры.

public enum GameState
{
    NotComplete,
    Winning,
    Tie
}

Игры

И, наконец, крестики-нолики решатель.

public class Solver
{
    private readonly Player _player;
    private readonly Player _opponent;

    public Solver(Player player, Player opponent)
    {
        _player = player ?? throw new ArgumentNullException(nameof(player));
        _opponent = opponent ?? throw new ArgumentNullException(nameof(opponent));

        if (player.Equals(opponent))
        {
            throw new ArgumentException("Both players are the same, does not compute.", nameof(opponent));
        }
    }

    public (bool CanTurn, int Index) CalulateBestMove(Playground playground)
    {
        if (playground == null)
        {
            throw new ArgumentNullException(nameof(playground));
        }

        FieldScore result = MiniMax(playground, true);

        return result.Index > 0
            ? (true, result.Index)
            : (false, 0);
    }

    private FieldScore MiniMax(Playground playground, bool isMaximizing)
    {
        PlaygroundState state = playground.GetState();

        // board is in final state, return score immediately
        // (since we are not aware of previous move (chosen field)
        //  we return only score part)
        if (state.State != GameState.NotComplete)
        {
            return state.State == GameState.Tie
                ? new FieldScore { Score = 0 }
                : _player.Equals(state.Player)
                    ? new FieldScore { Score = 1 }
                    : new FieldScore { Score = -1 };
        }

        Player currentPlayer = isMaximizing 
            ? _player 
            : _opponent;

        // calculate scores for each possible move
        // (NB! recursion is about to happen)
        IEnumerable<FieldScore> moves = playground.EmptyFields()
            .Select(
                f => new FieldScore
                {
                    Index = f.Index,
                    Score = MiniMax(playground.Turn(f.Index, currentPlayer), !isMaximizing).Score
                });

        // captain obvious to the service:
        // player - get the highest score (ORDER BY score DESC)
        // opponent - get the lowest score (ORDER BY score ASC)
        moves = isMaximizing 
            ? moves.OrderByDescending(m => m.Score) 
            : moves.OrderBy(m => m.Score);

        return moves.First();
    }

    private struct FieldScore
    {
        public int Index { get; set; }
        public int Score { get; set; }
    }
}

Использование

// instantiate players
var p1 = new Player('X'); // human
var p2 = new Player('O'); // computer

// create solver for computer
var s = new Solver(p2, p1);

// initialize playground
var playground = new Playground();

// *** repeat until done ***

// let human turn
// ...

// find the best turn for computer and turn
(var canTurn, var idx) = s.CalulateBestMove(playground);
if (!canTurn) 
{
    // nope...
}

playground = playground.Turn(idx, p2);


672
3
задан 3 апреля 2018 в 05:04 Источник Поделиться
Комментарии
1 ответ

Вы написали хорошие комментарии и реализации чист, ИМХО. У меня только пару что доставит некоторое неудобство.

1) это контр-интуитивно понятный:

Player.IsBlank(null) == true
Player.Blank.Equals(null) == false

Может IsNullOrBlank было бы лучше назвать первый способ (так как он похож на String.IsNullOrEmpty).

2) есть какая-то магия цифры здесь и там, например:


if (_emptyFields > 4)

или


var fields = new Field[9];

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

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

4
ответ дан 10 апреля 2018 в 07:04 Источник Поделиться