Дисклеймер: это моя первая статья на Хабре и я не программист.

Всем привет! Под катом небольшая история о том, как я делал свой первый, большой, самостоятельный (если его так можно назвать) "проект" – курсовую работу на тему "Игра в поддавки с компьютером". Если вам интересны алгоритмы для антагонистичесих игр, С# и особенности студенческой жизни – welcome!

Время неумолимо утекало, а преподаватель требовал отчитываться о состоянии курсача, но как вы понимаете, любой нормальный студент всё делает в последний момент – и я не исключение. Но всё-таки мне пришлось сесть за работу...

У меня был небольшой опыт в программировании – писал всякие скрипты и другую нужную мне автоматизацию на Python, какие-то простые программки на C, Ассемблере, Go (почти стандартный набор студента). Когда я узнал тему работы, то столкнулся с рядом проблем: во-первых, ограниченность в выборе стека технологий – С# с Windows Forms; во-вторых, нужно было написать оптимальный, быстрый и достаточно умный алгоритм, который будет двигать шашки и побеждать человека. На всякий случай уточню, "поддавки" это шашки наоборот, то есть побеждает тот, у кого не остается шашек.

Алгоритмы

Итак, я начал думать, как можно решить мою задачу. С ходу прилетело несколько идей:

• Bruteforce

• Machine Learning

• На основе знаний

• ...

Bruteforce – слишком долго, непонятно сколько комбинаций придётся перебирать, плюс сильно зависит от ресурсов машины на которой запускается. Machine Learning – тема для меня неизвестная и далёкая, да и я подумал, что мой курсач недостоин того, чтобы на него тратили столько времени. На основе знаний – предполагает использование базы данных, с уже за ранее известными ходами и комбинациями, а это, на секундочку, 10^20 значений. Этот метод тоже выходил за рамки курсача.

На этом мои идеи закончились и я пошёл на Хабр. Нашёл пару интересных для меня статей, где люди рассказывали о том, как решали похожие задачи. Я выделил два алгоритма – Монте-Карло и Минимакс. Заранее стоит оговориться, что эти алгоритмы мы применяем для поиска оптимальных ходов в дереве. Сейчас вкратце расскажу в чём их суть.

Монте-Карло

Для начала мы решаем задачу многорукого бандита для каждого узла, пока не будет найден узел, в котором пока ещё не все child-узлы имеют положительный для нас вариант. Затем, когда мы упираемся в потолок и задачу многорукого бандита решать больше невозможно, мы добавляем новый child-узел. После этого мы продолжаем ход, используя эвристические способы оценки ходов или же просто ходим на рандом. Самое главное что нам нужно извлечь – информацию о победителе. Эта информация распространяется вверх по дереву, обновляя информацию в каждом уже пройденном узле. Обновленные узлы увеличивают показатели количества игры, а узлы, которые совпали с победителем увеличивают показатели побед. В конечном итоге, для выбора хода берётся тот узел, который посетили наибольшее количество раз

Минимакс

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

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

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

Классы

Итак, с алгоритмом разобрались, осталось всё это дело реализовать. Я подготовил несколько классов, в каждом из которых реализовал вполне понятную логику:

• Board – описывает действия на доске, а также расчёт для стороны компьютера

• Cell – описывает клетку доски

• Checker – описывает шашку

• Combination – описывает комбинации ходов обеих стороны и пользу обеих сторон

• Move – описывает передвижение шашек по доске

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

private void CalculateCombinations(List<Move> lstOfMoves,
                                   List<Move> lstOfMovesForCombination) {
  /* lstOfMovesForCombination содержит список ходов с предыдущего уровня
   * рекурсии listOfMoves содержит список ходов одной из сторон с учетом
   * произведенных ходов в текущей комбинации */
  // Кстати, можно добавить метод, который будет сразу оценивать
  // пользу/адекватность этого хода Таким способом можно значительно сократить
  // ветвление рекурсии
  depthOfRecursion++;
  foreach (Move item in lstOfMoves) {
    if (depthOfRecursion <
        limitOfRecursion)  // Глубина рекурсии ограничена вручную
    {
      /*
       * Здесь мы добавляем новый ход в комбинацию Получаем новый список ходов
       * оппонента с учетом хода добавленного
       * в комбинацию. И Углубляемся дальше в рекурсию */
      lstOfMovesForCombination.Add(item);
      List<Move> listOfPotentionalMoves = new List<Move>();
      GetNewListOfMoves(listOfPotentionalMoves, item);
      if (listOfPotentionalMoves.Count != 0) Estimate(listOfPotentionalMoves);
      CalculateCombinations(listOfPotentionalMoves, lstOfMovesForCombination);
      RevertMove(item);
      lstOfMovesForCombination.Remove(item);
    } else
    /*
     * Только здесь в конце рекурсии создаем объект Комбинация Добавляем
     * последний ход в комбинацию, переписываем весь список ходов в комбинацию
     * Добавляем комбинацию в общий список комбинаций */
    {
      Combination newCombination = new Combination();
      List<Move> newListOfMovesForCombination = new List<Move>(
          lstOfMovesForCombination);  // ATTENTION!!! Обратить сюда внимание,
                                      // "копирование" не полное!
      newListOfMovesForCombination.Add(item);
      newCombination.combinationOfMoves = newListOfMovesForCombination;
      lstOfCombinations.Add(newCombination);
    }
  }
  depthOfRecursion--;

Что можно улучшить?

Когда я задал себе этот вопрос, появились весьма очевидные ответы:

• Добавить режим игры человек-человек – наверное самое простое что можно сейчас улучшить. Сейчас есть только режим игры с компьютером.

• Реализовать красивую анимацию с помощью Untiy движка

• Портировать игру на мобильные устройства (iOS/Android)

• Добавить режим игры по сети (SignalR/Socker/WCF/…)

Заключение

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

Для тех кто хочет запустить игру у себя или как то улучшить её – делюсь с вами ссылкой на Гитхаб репозиторий. Буду рад любым комментариям/предложениями.