Реализация игры «крестики-нолики» на C++ MFC: Структура курсовой работы и программный код

Компьютерные игры давно перестали быть просто развлечением, превратившись в сложный класс задач для информатики и объект для изучения в области искусственного интеллекта. В этом контексте классическая игра «крестики-нолики» представляет собой идеальную модель для исследования теории игр и алгоритмов принятия решений. Несмотря на кажущуюся простоту, она является примером игры с нулевой суммой и полной информацией, что делает ее прекрасным полигоном для отработки стратегий ИИ. Целью данной курсовой работы является разработка программного продукта, реализующего игру «крестики-нолики» с интеллектуальным компьютерным противником. Для достижения этой цели были поставлены следующие задачи: изучить теоретические основы и математическую модель игры, исследовать алгоритм минимакс как ядро для логики ИИ, освоить базовые принципы разработки графического интерфейса пользователя (GUI) на базе фреймворка MFC, а также спроектировать и реализовать готовое к использованию приложение.

Глава 1. Теоретический анализ основ для разработки игры

1.1. Исследование предметной области и постановка задачи

Игра «крестики-нолики» (Tic-Tac-Toe) представляет собой детерминированную стратегическую игру для двух участников. Игровой процесс разворачивается на поле размером 3×3 клетки. Один игрок использует «крестики», другой — «нолики», совершая ходы поочередно в свободные клетки. Цель — выстроить ряд из трех своих символов по горизонтали, вертикали или одной из двух главных диагоналей. Победа достигается в момент создания такого ряда. Если же все клетки поля заполнены, а победитель не определен, игра завершается вничью.

Для программной реализации необходимо формализовать эти правила. Состояние игры в любой момент времени можно представить в виде матрицы 3×3, где каждая ячейка хранит одно из трех значений: «пусто», «крестик» или «нолик». Каждый ход игрока изменяет состояние этой матрицы. Состояние, при котором один из игроков победил или наступила ничья, называется терминальным. «Крестики-нолики» — это игра с полной информацией, поскольку оба игрока имеют исчерпывающие данные о текущем состоянии и всех возможных ходах. Более того, она относится к играм с так называемой «ничейной смертью»: при безошибочной, идеальной игре обоих соперников результат всегда будет ничьей.

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

• Создание графического интерфейса пользователя (GUI) для визуализации игрового процесса.
• Реализация режима игры «человек против компьютера».
• Четкое отображение текущего состояния игрового поля после каждого хода.
• Информирование пользователя о результате игры: победа, поражение или ничья.

1.2. Как алгоритм минимакс формирует основу для непобедимого ИИ

Чтобы компьютерный противник мог играть не случайным образом, а принимать оптимальные решения, необходим эффективный алгоритм. Для игр с полной информацией, таких как «крестики-нолики», идеальным выбором является алгоритм минимакс (Minimax). Это рекурсивный алгоритм, который помогает найти оптимальный ход, исходя из предположения, что противник также будет играть оптимально.

Название «минимакс» отражает его суть: один игрок (назовем его максимизирующим, MAX) стремится максимизировать свой итоговый счет, а второй игрок (минимизирующий, MIN) — минимизировать счет первого. Алгоритм строит и обходит полное дерево всех возможных игровых состояний, начиная от текущей позиции. Для каждой конечной (терминальной) позиции в этом дереве вычисляется оценка с помощью специальной оценочной функции. В «крестиках-ноликах» эта функция предельно проста:

• +1, если побеждает компьютер (AI, максимизирующий игрок).
• -1, если побеждает человек (минимизирующий игрок).
• 0, если игра заканчивается вничью.

Далее алгоритм начинает «подниматься» по дереву от терминальных узлов к текущей позиции. На каждом уровне он выбирает ход, руководствуясь своим принципом: на ходах игрока MAX выбирается ход, ведущий к состоянию с максимальной оценкой, а на ходах игрока MIN — ход, ведущий к состоянию с минимальной оценкой. Таким образом, оценка «пробрасывается» вверх по дереву до самого корня. В результате для каждого возможного хода из текущей позиции вычисляется его итоговая оценка, и AI просто выбирает тот ход, который ведет в состояние с наилучшим для него результатом.

Принцип работы минимакса можно описать следующим псевдокодом:
function minimax(position, depth, isMaximizingPlayer):
  if position is terminal or depth is 0:
    return static evaluation of position

  if isMaximizingPlayer:
    maxEval = -infinity
    for each possible move from position:
      eval = minimax(move, depth - 1, false)
      maxEval = max(maxEval, eval)
    return maxEval

  else (isMinimizingPlayer):
    minEval = +infinity
    for each possible move from position:
      eval = minimax(move, depth - 1, true)
      minEval = min(minEval, eval)
    return minEval

Несмотря на свою эффективность, у минимакса есть недостаток — он перебирает все возможные варианты, что для сложных игр приводит к комбинаторному взрыву. Дерево решений для поля 3×3 содержит сотни тысяч узлов. Для его оптимизации часто применяют альфа-бета отсечение — метод, который позволяет «отсекать» заведомо проигрышные ветви дерева, не рассматривая их, что значительно сокращает количество вычислений без потери качества решения.

1.3. Обзор возможностей фреймворка MFC для создания графического интерфейса

Для реализации визуальной части приложения был выбран фреймворк MFC (Microsoft Foundation Classes). Это объектно-ориентированная библиотека C++, представляющая собой надстройку над Win32 API и предназначенная для упрощения и ускорения разработки приложений для операционной системы Windows. Выбор MFC для курсовой работы обусловлен несколькими ключевыми преимуществами:

• Инкапсуляция Windows API: MFC «оборачивает» сложные функции и структуры Win32 API в удобные и понятные C++ классы, скрывая низкоуровневые детали и позволяя сосредоточиться на логике приложения.
• Готовые компоненты GUI: Фреймворк предоставляет обширный набор готовых классов для создания элементов интерфейса, таких как окна, диалоги, кнопки, меню и т.д.
• Интеграция с Visual Studio: Глубокая интеграция со средой разработки Visual Studio, включая редакторы ресурсов и мастеров создания проектов, существенно ускоряет процесс проектирования интерфейса и написания кода.

В рамках данного проекта будут задействованы несколько основных классов MFC. Класс CWnd является базовым для всех оконных объектов, а его производный класс CDialog идеально подходит для создания главного окна нашего приложения. Управление событиями в MFC построено на системе сообщений Windows. Например, когда пользователь кликает левой кнопкой мыши по окну, система генерирует сообщение WM_LBUTTONDOWN. MFC позволяет легко перехватывать и обрабатывать такие сообщения, привязывая к ним соответствующие функции-обработчики, что делает реализацию интерактивности интуитивно понятной.

Глава 2. Процесс практической реализации игрового приложения

2.1. Проектирование архитектуры приложения и его классовой структуры

Перед началом кодирования важно спроектировать архитектуру приложения. Стандартное MFC-приложение, созданное на основе диалогового окна, уже задает базовую структуру: класс приложения (потомок CWinApp) и класс главного диалогового окна (потомок CDialog). Для инкапсуляции игровой логики и разделения ответственности мы введем дополнительные классы, что сделает код более чистым, модульным и легким для понимания.

Ключевая структура проекта будет состоять из следующих классов:

1. CMainDialog: Этот класс будет отвечать за всю визуальную часть и взаимодействие с пользователем. Он будет содержать код для отрисовки игрового поля и фигур, а также обработчики событий от мыши (клики по полю) и кнопок (например, «Новая игра»). Этот класс станет центральным узлом, координирующим работу других компонентов.
2. CGameBoard: Класс-модель, инкапсулирующий состояние игрового поля. Его основная задача — хранить матрицу 3×3, предоставлять методы для совершения хода (установки крестика или нолика в ячейку) и, что крайне важно, реализовывать логику проверки на победу, поражение или ничью после каждого хода.
3. CGameAI: «Мозг» нашего компьютерного противника. Этот класс будет полностью посвящен реализации алгоритма минимакс. Его главный метод будет принимать на вход текущее состояние доски от объекта CGameBoard, выполнять рекурсивный анализ дерева решений и возвращать наиболее оптимальный ход для компьютера.

Такое разделение позволяет четко разграничить зоны ответственности: CMainDialog ничего не знает об алгоритме минимакс, а CGameAI не имеет представления о том, как отрисовывается поле. Они обмениваются информацией через объект-состояние CGameBoard, что соответствует лучшим практикам объектно-ориентированного проектирования.

2.2. Разработка графического интерфейса и отрисовка игрового поля

Создание визуальной оболочки игры начинается в редакторе ресурсов Visual Studio, где проектируется главное диалоговое окно. На него можно добавить кнопки управления, например, «Начать заново», и статическое текстовое поле для вывода сообщений о статусе игры («Ваш ход», «Победил компьютер!»).

Основная работа по отрисовке происходит в обработчике события OnPaint, который вызывается каждый раз, когда окно требует перерисовки. Для рисования используется контекст устройства (Device Context, DC), который предоставляет GDI-функции. Сначала рисуется сетка игрового поля. Это достигается с помощью вызовов функций MoveTo() для перемещения «пера» в начальную точку линии и LineTo() для проведения самой линии. Четырех таких вызовов достаточно для создания сетки 3×3.

Отрисовка крестиков и ноликов происходит также внутри OnPaint. Программа пробегает по матрице состояния игры и, если ячейка не пуста, рисует в соответствующей ей области окна нужный символ. «Нолик» легко рисуется с помощью функции Ellipse(), а «крестик» — двумя пересекающимися линиями с помощью тех же MoveTo() и LineTo().

Самая важная часть интерактивности — обработка клика мыши. Для этого создается обработчик сообщения WM_LBUTTONDOWN. Внутри этого обработчика мы получаем координаты курсора в момент клика. Эти экранные координаты необходимо преобразовать в логические координаты ячейки игрового поля (например, из пикселей в индекс матрицы). Это делается простым целочисленным делением координат на ширину и высоту одной ячейки. После определения ячейки, по которой кликнул пользователь, программа проверяет, свободна ли она, и если да, то совершает ход игрока и запускает процедуру перерисовки окна вызовом Invalidate().

2.3. Программирование игровой логики и интеграция AI-противника

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

1. Обновляет внутреннее состояние игрового поля (матрицу в классе `CGameBoard`), устанавливая в выбранную ячейку символ игрока.
2. Вызывает метод проверки на завершение игры. Этот метод последовательно проверяет все горизонтали, вертикали и диагонали на наличие трех одинаковых символов. Если победитель найден или все клетки заполнены (ничья), игра останавливается и выводится соответствующее сообщение.
3. Если игра не закончена, управление передается AI для совершения ответного хода.

Реализация хода компьютера — это практическое применение алгоритма минимакс, описанного в теоретической главе. Создается главная функция, например, `FindBestMove()`, которая перебирает все пустые клетки на доске. Для каждой такой клетки она «примеряет» ход компьютера и вызывает рекурсивную функцию `minimax()`, чтобы оценить, насколько хороша полученная позиция. Функция `minimax()` рекурсивно строит дерево игры, возвращая оценку (+1, -1 или 0) для каждой ветви. `FindBestMove()` собирает эти оценки и в итоге выбирает тот ход, который привел к позиции с максимальной оценкой.

Ключевой фрагмент кода для проверки победителя может выглядеть так:
// Проверка строк и столбцов
for (int i = 0; i < 3; i++) {
  if (board[i] == board[i] && board[i] == board[i] && board[i] != EMPTY) return board[i];
  if (board[i] == board[i] && board[i] == board[i] && board[i] != EMPTY) return board[i];
}
// Проверка диагоналей
if (board == board && board == board && board != EMPTY) return board;
if (board == board && board == board && board != EMPTY) return board;

После того как AI выбрал свой лучший ход, программа обновляет состояние игрового поля уже его символом, снова вызывает функцию перерисовки `Invalidate()`, и вновь выполняется проверка на победу или ничью. Таким образом, игровой цикл "ход игрока -> проверка -> ход AI -> проверка" продолжается до тех пор, пока не будет определен исход партии.

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

В результате проделанной работы можно сделать вывод, что цель курсового проекта была успешно достигнута. Было разработано полнофункциональное приложение "крестики-нолики" с использованием языка C++ и фреймворка MFC, реализующее игру человека против компьютера. В ходе работы были решены все поставленные задачи: изучена теория игр на примере классической задачи, детально разобран и реализован алгоритм минимакс для создания непобедимого искусственного интеллекта, а также освоены базовые навыки разработки графического интерфейса пользователя в среде Windows с помощью Microsoft Foundation Classes. Созданное приложение полностью соответствует изначально сформулированным требованиям, демонстрируя стабильную работу и корректную игровую логику.

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

• Оптимизация AI: Внедрение алгоритма альфа-бета отсечения для сокращения времени расчета хода, что будет особенно актуально при расширении игрового поля.
• Расширение режимов игры: Добавление режима "человек-человек" для игры двух пользователей за одним компьютером.
• Масштабирование игры: Реализация игры на поле большего размера (например, 5x5) с изменением правила победы (например, собрать 4 символа в ряд).
• Сетевая игра: Разработка сетевого режима, позволяющего пользователям играть друг с другом через локальную сеть или интернет.