Разработка игры на C# (Mini RPG) Часть 5 из 5. Бот

За основу разработки алгоритма искусственного интеллекта взят алгоритм МиниМакс и адаптирован для игры. Для начала кратко разберемся с оригинальным алгоритмом, перед тем как его модифицировать. Алгоритм представляет из себя полный перебор. Легче всего понять идею алгоритма наглядно на графе.

Алгоритм минимакс

Предположим имеется текущее состояние игры. Оно расположено на уровне 0. Для текущего состояния генерируются все возможные ходы игрока 1. Все эти состояния располагаются на уровне 1. Для этого уровня, для каждого состояния генерируются следующие ходы (для игрока 2). Они размещаются на уровне 2, который является вторым шагом в игре. На каждом уровне производится оценка состояния для определенного игрока (противника того, кто сделал ход). Вызывается оценивающая функция и считается численное значение. Таким образом на 2-м уровне определяется худший для игрока 1 ход (минимум), на уровне 1 определяется лучший ход для игрока 1 и принимается решение о ходе.

Плюсы и минусы алгоритма

Можно добавить эвристику в виде отсечения некоторых веток при рассмотрении. Например при достижении граничных условий или совсем плохих.

В разрабатываемой игре у игрока есть 4 возможных хода: Атака, Покупка оружия, Покупка брони, Покупка лечения. При этом всегда доступна Атака, а покупки доступны только при наличии монет. Будем разрабатывать бота с полным незнанием информации о настройках игры. Это означает, что при любом изменении настроек игры и/или формул бот будет искать оптимальный ход. Для упрощения будем реализовывать бота, который старается выжить. Подсчитав сложность, выясняется, что для каждого уровня генерируется N! возможных ходов (в общем случае).

Определим модель узла.

public class Node
{
    private readonly ActionTypes _action;
    private readonly GameState _state;

    public Node()
    {
    }

    public Node(GameState state)
    {
        _state = state;
    }

    public Node(GameState state, ActionTypes action)
    {
        _state = state;
        _action = action;
    }

    public int Win { get; set; }
    public int Death { get; set; }
    public int Health { get; set; }

    public int Value
    {
        get
        {
            if (Death > Win)
                return Int32.MinValue;
            return Win + Health - Death*5;
        }
    }

    public GameState State
    {
        get { return _state; }
    }

    public ActionTypes ActionType
    {
        get { return _action; }
    }

    public override string ToString()
    {
        return string.Format("{0} ({1})", ActionType, Value);
    }
}

Value является оценочной функцией. Именно от этого значения зависят решения принимаемый алгоритмом. Видно, что эта функция оптимизирует Количество Win (о нем позже), значение здоровья и сильно пессимизирует Death. Другими словами бот будет стараться больше победить и накопить здоровья и будет стараться меньше умереть, что вполне логично. Определим метод, который ищет оптимальный ход.

public ActionTypes GetBestAction(GameState state, GameConfiguration config)

Чтобы не портить текущее состояние игры каждый раз будем копировать состояние GameState и «портить» копию. Так как в игре заложена вероятностная модель, то за 1 раз невозможно правильно выбрать ход. В ходе экспериментов было выявлено, что при 13 проходах алгоритма удается определить приемлемые значения хода.

List<Node> bestList = new List<Node>();

Parallel.For(0, ProcessCount, index =>
{
    Node start = new Node(state.DeepCopy());
    Node best = Iterate(start, Deep);
    bestList.Add(best);
});

Рассмотрим функцию генерации новых состояний из текущего. Эта функция должна учитывать количество монет и здоровье.

//Генерируем новые состояния
private List<Node> Children(GameState state)
{
    //Если игрок умер, дальше идти некуда
    if (state.CurrentPlayer.Health == 0)
        return new List<Node>();

    List<Node> resultNodes = new List<Node>();

    //Возможные состояния
    List<IAction> actions = new List<IAction>();
    actions.Add(new AttackAction());
    actions.Add(new HealAction());
    actions.Add(new BuyItemAction(ItemTypes.Weapon));
    actions.Add(new BuyItemAction(ItemTypes.Awmor));


    foreach (IAction action in actions)
    {
        GameState copy = state.DeepCopy();
        //Если можно выполнить действие
        if (action.CanApply(copy, _config))
        {
            //Выполняем его
            action.Process(copy, _config);
            //И записываем в новые состояния
            resultNodes.Add(new Node(copy, action.Type));
        }
    }

    return resultNodes;
}

Основная функция работы алгоритма

public Node Iterate(Node node, int depth)
{
    Node best = null;
    Node childReturn = null;
    
    //Если мы на последнем уровне или персонаж умер "глубже не копаем"
    if (depth == 0 || node.State.CurrentPlayer.Health == 0)
    {
        //Считаем результат для текущего состояния и возвращаем эту информацию
        var calcResult = Calculate(node.State);
        node.Win = calcResult.Item1;
        node.Death = calcResult.Item2;
        node.Health = node.State.CurrentPlayer.Health;
        return node;
    }

    //Если же игро выжил в этом состоянии
    //Генерируем все возможные новые состояния из текущего 
    //С учетом количества денег
    foreach (Node child in Children(node.State))
    {
        //Копаем глубже
        Node iteratedNode = Iterate(child, depth - 1);

        //Сравниваем с оптимальным
        if (best == null || iteratedNode.Value > best.Value)
        {
            best = iteratedNode;
            childReturn = child;
            childReturn.Win = best.Win;
            childReturn.Death = best.Death;
            childReturn.Health = best.Health;
        }
    }


    if (childReturn == null)
        return node;

    return childReturn;
}

Так как эта игра не друг против друга, а человек против игры не ищется минимальное состояние. Всегда ищется самое оптимальное состояние для некоторой глубины просмотра. В ходе экспериментов было установлено, что приемлемая скорость работы и качество достигается при глубине просмотра равном 3. После того, как мы получили список из 13 оптимальных ходов необходимо выбрать лучший. Стоит заметить, что оптимальный ход может с отрицательным значением Value оценочной функцией. Это означает, что с большой вероятностью это будет последний ход.

bestList = bestList.OrderByDescending(x => x.Value).ToList();


//medium by sum and positive value ("without" death)
var result = bestList.Where(x => x.Value > 0).ToList();
Node bestGroup = null;
if (result.Count > 0)
{
    bestGroup = result.GroupBy(x => x.ActionType)
        .OrderByDescending(x => x.Sum(a => a.Value))
        .First().First();
}


Node betsByValue = bestList.First();

Debug.WriteLine("1 = {0}, 2 = {1}", betsByValue.ActionType,
    (bestGroup != null ? bestGroup.ActionType.ToString() : "null"));

return (bestGroup ?? betsByValue).ActionType;

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

бот для игры C#

 

Для настроек игры, определенных в 4-й части замечено следующее. Бот при первой возможности старается купить оружие, тем самым повысив вероятность победы. Таким образом вероятность победы будет 60-65% из 70% возможных, а это означает, что дальнейшее развитие силы не является целесообразным. Далее бот атакует и лечится, практически не покупая броню. И кажется, что в этом тоже есть логика. Потому что броня увеличивает максимальное значение здоровья на 1-2 пункта и стоит монет. На этом мы закончим разработку игры на C#.

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

Разработка игры на C# (Mini RPG)

Скачать исходный код игры oxozle.minirpg.zip 46 Кб.

Комментарии

comments powered by Disqus