Идеи 💡 — Создание игры «крестики-нолики» на React с нуля

Приветствую тебя, собрат по разуму! 👋

ℹ️ Этот пост является частью серии, в которой я описываю свой путь, как я планирую и создаю игру крестики-нолики от идеи до релиза.

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

Я выбрал для себя систему управления проектами Notion — отличное приложение/веб-сайт, которое делает все — по крайней мере, все, что мне нужно. Я начинаю процесс планирования с новой страницы проекта, внутри которой у меня всего два раздела, не более. Встроенная база данных под названием Bucket будет хранить все, что я готовлю для помощи процессу, а в разделе Links я размещаю статьи и ресурсы из Интернета, которые считаю полезными.

Когда центр проекта создан, можно приступать к работе. ⏩

Определение функциональности приложения

При любом программировании важно сначала определить и разбить на части функциональность приложения. Какие минимально необходимые задачи должно выполнять наше приложение?

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

Чтобы реализовать это на практике, мы начинаем с широких целей, а затем работаем в обратном направлении, пока в итоге не получим очень конкретные, выполнимые цели.

По сути, цель приложения заключается в следующем:

1. Играть в игру(и) крестики-нолики.

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

1. Определить настройки игры
2. Играть в игру или несколько игр в крестики-нолики
3. Следить за результатами

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

Определение параметров игры

Какие параметры должны быть установлены в игре?

1. Режим игры (PvP или PvC?)
2. Размер сетки (3 — 5)
3. Имя игрока(ов)

Это три вещи, которые я считаю необходимыми для начала игры. Я ограничиваю размер сетки максимум 5×5, чтобы избежать слишком маленьких ячеек на некоторых экранах.

Сыграйте в игру или несколько игр в крестики-нолики

Каковы конкретные шаги в каждой игре?

1. Показать пустую сетку
2. Позволить игроку сделать ход
3. Переключить игроков
4. Для PvC: определить оптимальный ход для компьютера
5. Определить результат игры (победа/ничья).
6. Если есть результат, отобразите его
7. Если есть результат, повторите с 1.
8. В противном случае повторите пункт 2.

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

Ведение счета

1. Инициализируйте счет для обоих игроков равным 0.
2. В случае победы увеличивайте счет победившего игрока.
3. Если настройки изменены, повторите с 1.

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

Окончательный список целей

Давайте посмотрим на полный список в целом

1. Определить настройки игры
   1. Режим игры (PvP или PvC?)
   2. Размер сетки (3 — 5)
   3. Имя игрока(ов)
2. Сыграть партию или несколько партий в крестики-нолики
   1. Отображать пустую сетку
   2. Позволить игроку сделать ход
   3. Переключить игроков
   4. Для PvC: Определить оптимальный ход для компьютера
   5. Определить результат игры (победа/ничья)
   6. Если есть результат, отобразите его
   7. Если есть результат, повторите с 1.
   8. В противном случае повторите с 2.
3. Следить за счетом
   1. Инициализируйте очки для обоих игроков в 0.
   2. Если есть выигрыш, увеличьте счет выигравшего игрока.
   3. Если настройки изменены, повторите с 1.

Теперь у нас есть набор конкретных, выполнимых шагов, которые можно реализовать по отдельности. Отлично!

Предварительное решение логических проблем

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

Вывод результата игры

Ключевой вопрос: Как определить, когда игрок выиграл партию?

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

for row <- 1 to 3
    for col <- 1 to 2
        if grid[row][col] != grid[row][col + 1] then
            next row
    next col
    return true
next row
return false

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

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

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

Каждая пара значений в этой диаграмме хранит количество Х и О в своей строке/столбце/диагонали. Например, в главной диагонали есть 1 X и 1 O, поэтому счетчик главной диагонали хранит значения (1, 1).

После каждого правильного хода эти счетчики должны обновляться.

• Счетчики строк и столбцов всегда обновляются на основе строки и столбца выбранной ячейки сетки.
• Счетчик главной диагонали будет обновляться, если выбранная клетка сетки лежит на главной диагонали. Это можно проверить с помощью условия row === column.
• Счетчик противодиагоналей аналогично обновляется при проверке условия, row + column === size - 1, предполагая, что row и column имеют нулевой индекс, а size хранит количество клеток в любой строке/столбце.

В сетке крестики-нолики произвольного размера выигрыш возможен ровно через (size × 2) - 1 ходов. Это происходит потому, что на следующем же ходу начинающий игрок сделает достаточно ходов для совпадения. Обозначим это значение через minMoves.

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

После size × size ходов мы выполним эту проверку в последний раз, и если выигрыша по-прежнему нет, будет объявлена ничья и игра закончится.

Этот подход имеет временную сложность O(n), потому что единственным циклом, который требуется, будет перебор счетчиков строк/столбцов для обнаружения совпадения.

Сравните это с предыдущим подходом, который имел временную сложность O(n²), поскольку для обнаружения совпадения нужно было перебирать каждую строку и каждый столбец. У нас есть победитель! 🥳

Вывод оптимального хода для компьютера

Ключевой вопрос: Как определить, какой ход сулит наиболее благоприятный исход при данном состоянии сетки?

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

Предположим, что сейчас очередь Х, и текущее состояние сетки следующее:

X может сделать любой из следующих 3 ходов:

Мы видим, что ход №3 приводит к победе X, и поэтому мы присваиваем этому ходу значение +1. Однако для двух других ходов мы не достигли конечного состояния, поэтому продолжим перебирать возможные ходы, но на этот раз для O.

Мы видим, что ходы #1.1 и #2.2 приводят к проигрышу для X, поэтому мы присваиваем этим ходам значение -1.

Поскольку очевидно, что два других хода (#1.2 и #2.1) являются выигрышными для X, мы присваиваем этим ходам значение +1. Нет необходимости иллюстрировать дальнейшие ходы.

Теперь у нас есть следующее дерево возможных ходов с соответствующими значениями баллов:

Теперь X будет делать наиболее оптимальный ход из имеющихся вариантов, используя значение оценки каждого возможного хода. Однако мы все еще не присвоили значение баллов ходам №1 и №2. Это можно решить, оценив следующий набор ходов и выбрав значение оценки оптимального хода (здесь -1).

Это наводит на важную мысль, что оптимальный ход для X — это ход с большим значением оценки, а оптимальный ход для O — это ход с меньшим значением оценки. Таким образом, X является максимизирующим игроком, а O — минимизирующим. Отсюда и название — минимакс.

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

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

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

💭 Пожалуйста, прокомментируйте мою работу по объяснению этих алгоритмов. Понятны ли они?

Теперь у нас есть набор целей для игры, а также знания, необходимые для построения крестиков-ноликов в теории. Что будет дальше?

⚡ Оставайтесь с нами до следующего поста в этой серии, где мы будем использовать эти цели для создания каркаса и дизайна внешнего вида нашей игры.

❤ Не забудьте поставить лайк этому посту и оставить свои мысли в комментариях!

Фотография с обложки Мэтью Дэвиса на Unsplash
Узнайте больше об алгоритме Минимакс