Удобный решатель крестиков-ноликов: Часть 2

В A Handy Tic-Tac-Toe Solver: Part 1 мы начали разработку текстового проигрывателя Tic-Tac-Toe. В частности, мы занялись проблемами (1) создания и отображения доски Tic-Tac-Toe, (2) предоставления пользователю возможности сделать ход и проверки его достоверности и (3) проверки того, выиграл ли пользователь или компьютер игра.

Прочтите, чтобы узнать, как реализовать оптимальную компьютерную стратегию и победить противника, не забывая при этом об объектно-ориентированном дизайне!

Так далеко…

Наш решатель «крестики-нолики» пока позволяет пользователю делать ход, а также проверяет, выиграл ли пользователь или компьютер игру. Но он еще не выполняет автоматических действий в ответ на пользователя! Вот видео о состоянии игры на данный момент:

В этом посте мы и сделаем именно это! Добавьте новую компьютерную стратегию.

Паттерн стратегии:

Мы собираемся использовать шаблон разработки стратегии и разрабатывать стратегию вне нашего класса TicTacToe. Согласно Википедии:

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

Мы собираемся разработать несколько компьютерных стратегий, независимых от класса TicTacToe, и выбрать одну из них во время выполнения (из main.cc). Начнем с определения класса.

стратегия.h

Мы определили чистый виртуальный класс Strategy с одним виртуальным методом: GetMove, который выбирает следующий ход, который должен сделать компьютер. Давайте также включим этот Strategy класс в нашу TicTacToe доску. Давайте также определим ComputerMove метод, который использует стратегию и делает ход по доске.

TicTacToe.h

Простая стратегия:

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

Strategy.h:

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

main.cc:

Наконец, не забудьте написать несколько модульных тестов для SimpleStrategy

Пришло время демонстрации ...

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

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

В следующем разделе мы собираемся разработать стратегию на основе дерева решений с немного сложным кодированием. Но все же обратите внимание, что мы не собираемся изменять какой-либо код из класса TicTacToe и вносить минимальные изменения в функцию main при разработке любой новой стратегии.

Продвинутая стратегия:

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

  1. Присвойте Score каждой пустой (i, j) ячейке частично заполненной доске. Более высокий балл означает, что вам, возможно, следует поместить следующий маркер в ячейку (i, j). Меньшая (или отрицательная) оценка означает, что держитесь подальше от клетки (i, j)!
  2. Мы должны использовать какую-то эвристику для вычисления этой оценки. Вот эвристика простого кода
  • Если размещение компьютерного маркера на (i, j) приводит к немедленной победе компьютера, присвойте положительный результат (i, j). Мы присваиваем таким выигрышным ходам оценку 1.
  • Если размещение пользовательского маркера на (i, j) приводит к немедленной победе пользователя, присвойте отрицательный результат (i, j). В этом посте мы присваиваем этим проигрышным ходам оценку -2. Итак, мы наказываем проигрыш больше, чем награждаем победой!
  • В противном случае возьмите средний балл каждой пустой (i, j) ячейки, рекурсивно вызывая нашу функцию.

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

Вот код этой рекурсивной стратегии.

Strategy.h:

Strategy.cc:

Единственное, что требуется сейчас, - это изменить одну строку в main.cc.

DecisionTreeStrategy strat; 
t.SetStrategy(&strat);

Лучшая демонстрация:

Вот видеоролик о стратегии, основанной на дереве решений:

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

Вот и все, ребята ... Несколько мыслей на прощание

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

  1. Еще больше стратегий. Как насчет награды за выигрышные стратегии больше, чем просто +1? Можем ли мы также вознаграждать более короткие игры (быстрые победы) и наказывать более длинные? Может быть, введя фактор спада в оценку?
  2. Поддержка нескольких раундов игры с чередованием «Пользователь / Компьютер» между крестиком и точкой. Мы также можем расширить это, добавив оценки для пользователя и компьютера.
  3. Общая nXn доска. Вы должны убедиться, что ваша стратегия не занимает слишком много времени для вычисления и / или не исчерпывает память :).

Многие кандидаты предпочитают интерпретируемые (и динамически типизированные) языки, такие как Python, для такого рода собеседований по кодированию. В C ++ определенно отсутствует быстрый REPL (цикл чтения-оценки-печати) этих языков, и в системе с множеством единиц компиляции, подобной той, что описана в этом посте, нам также нужна столь же сложная система BUILD. Ниже мы воспроизводим Makefile, используемый для компиляции всех классов и основного файла, а также даем инструкции по запуску программы.

Makefile:

(Полный исходный код доступен здесь).

Первоначально опубликовано на https://cppcodingzen.com 16 сентября 2020 г.