Разработка игры «крестики-нолики»

• Постановка задачи и описание предметной области
• Обоснование выбора программных средств для решения задачи
• Описание применяемого алгоритма
• Блок-схема интеллектуального алгоритма
• Особенности реализации программы
• Описание работы программы
• Выводы
• Список использованной литературы

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

крестики нолики программа алгоритм

Дано бесконечное поле (n*n, где n = 1…65 536) для игры в «крестики-нолики».

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

Бесконечное поле — теоретически бесконечное поле (фактически поле n*n, где n = 1…65 536).

Клетка — минимальная единица из которой состоит поле.

Крестик — объект, использующийся одним из игроков, для реализации своего хода.

Использует 1 клетку поля.

Нолик — объект, использующийся одним из игроков, для реализации своего хода. Использует 1 клетку поля.

Игрок — один из двух участников игры, может ходить крестиком или ноликом, в зависимости от выбранного хода.

Обоснование выбора программных средств для решения задачи

Выбор языка программирования оказывает непосредственное влияние на быстроту разработки, надежность и эффективность программы. В качестве среды программирования для реализации программы была выбрана IDE Code Gear и язык программирования C++ (Code Gear/Builder C++), являющегося наследником Borland C++ Builder.

Интегрированная среда разработки Code Gear/Builder C++ с ее инструментами визуального редактирования, библиотекой компонент, механизмом баз данных и многим другим, идеально подходит для написания разумных 32/64-разрядных приложений Windows, используя популярный язык программирования С++, который является объектно-ориентированным.

Ключевые особенности среды разработки Code Gear/Builder C++:

· полная поддержка Unicode. Приложения могут выполняться на любой языковой версии Windows. Применение Unicode гарантирует, что приложения будут одинаково выглядеть и функционировать во всех языковых версиях Windows и поддерживать как Unicode-строки, так и ANSI-строки.

· новые элементы языков программирования, в том числе Generics и анонимные методы для C++, позволяют создавать более гибкий и качественный код и предоставляют новые возможности для рефакторинга;

· новая библиотека VCL включает в себя множество усовершенствований и новых компонентов для создания развитого графического интерфейса;

· веб-библиотека VCL позволяет создавать веб-приложения с развитым интерфейсом с поддержкой AJAX;

· уменьшено время передачи приложением сообщений операционной системе;

· визуальное проектирование и разработка баз данных благодаря входящему в состав редакции Builder Architect профессионального средства моделирования Embarcadero ER/Studio. [9]

Обоснованием выбора служат следующие факторы:

Быстрота разработки. От быстроты разработки зависит, прежде всего, цена программного продукта. Для увеличения скорости написания Windows-приложений необходимо использовать средства визуального программирования. Code Gear/Builder C++ как нельзя более подходит для выполнения данной задачи, так как назначение Code Gear/Builder C++ - быстрая разработка приложений (RAD — Rapid Application Development). Разработка приложений интерфейса пользователя с помощью Code Gear/Builder C++ - в основном процесс проектирования, с весьма небольшим количеством фактического программирования, что существенно сокращает время на создание удобного интерфейса, отвечающего стандартам разработки Windows-приложений. Code Gear/Builder C++ может компилировать 32/64-битные программы, обеспечивая высокую скорость выполнения.

Характер задачи. Рассматриваемая в дипломной работе задача относится к разряду вычислительных с использованием баз данных. В состав Code Gear/Builder C++ входит высокоэффективный компилятор с языка C++, основанном на концепции объектно-ориентированного программирования. Данный компилятор генерирует оптимизированный код, позволяющий увеличить скорость выполнения программ, что немаловажно для данного программного продукта. Code Gear/Builder C++ создает действительно откомпилированные программы, готовые для исполнения. Кроме того, для увеличения быстродействия программы и уменьшения объема занимаемой памяти используется возможность работы с динамическими структурами данных.

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

Создание приложений «Клиент — Сервер». В настоящее время широко используются многозвенные информационные системы. Code Gear/Builder C++ предоставляет широкие возможности для создания приложений, поддерживающих трехзвенную систему, компонентами которой являются «тонкий» клиент, сервер приложений и сервер баз данных.

Таким образом, среда программирования Code Gear/Builder C++ является оптимальным выбором для решения поставленной задачи, так как:

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

обладает широкими средствами визуального построения интерфейса;

Описание применяемого алгоритма

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

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

Критерий заключается в следующем:

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

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

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

Пример работы алгоритма минимакс можно представить в виде следующего графа:

Опишем используемые переменные:

Поле n*m, где n — количество полей по горизонтали, m — количество полей по вертикали.

weights[i, j] - вес поля i, j (оценка) на определенном ходу игры.

size — длина выигрышной линии.

depth — глубина минимаксного алгоритма.

В качестве оценок будем использовать следующую схему:

за каждую линию, в которой получиться по 1-ой заполненной клетке — 2 очка.

за каждую линию, в которой получиться по 2-е заполненных клетки — 4 очка.

за каждую линию, в которой получиться по 3-и заполненных клетки — 8 очков.

за каждую линию, в которой получиться по size — 1 заполненной клетке — 2^size-1 очков.

за каждую линию, в которой получиться по size заполненной клетке — 2^size очков.

В итоге на глубине depth мы получим оценки каждого поля, в которое может сходить AI, и на шаге depth-1 выбрать максимальную оценку. На шаге depth-2 минимальную, и так далее, до тех пор пока глубина не будет = 1. После чего выбирается оптимальная оценка и выполняется ход AI.

Альфа-бета отсечение. Альфа-бета отсечение (англ. Alpha-beta pruning) — это алгоритм поиска, стремящийся сократить количество узлов, оцениваемых в дереве поиска алгоритмом минимакс. Этот алгоритм предназначен для антагонистических игр и используется для машинной игры (в шахматах, го и других). В основе алгоритма лежит идея, что оценивание ветви дерева поиска может быть досрочно прекращено (без вычисления всех значений оценивающей функции), если было найдено, что для этой ветви значение оценивающей функции в любом случае хуже, чем вычисленное для предыдущей ветви. Альфа-бета отсечение является оптимизацией, так как результаты работы оптимизируемого алгоритма не изменяются.

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

Изображение работы минимаксного алгоритма с альфа-бета отсечением:

Блок-схема интеллектуального алгоритма

Алгоритм поиска наилучшего хода можно представить в виде следующих блок-схемы:

Блок схема работы функции findMin:

Блок схема функции FindMax отличается от FindMin только знаком при сравнениях.

Особенности реализации программы

Программа реализована на языке программирования С++ в среде разработки Code Gear.

Выделен основной класс игры: TCrossZero.

Свойства и методы класса:

class TCrossZero {

public:

TCrossZero ();

~TCrossZero ();

int beginX, endX,

beginY, endY; // ограничение поиска (см. FindBorder)

int size; // длина выйграшной линии

int n, m; // размер поля

int** field; // поле боя, двумерный массив

// -1 пустое поле

// 1 — крестик

// 0 — нолик

int** weights; // массив оценочных весов

int depth; // глубина поиска решения

int mode; // 1 — человек-компьютер

// 2 — человек-человек

// 3 — компьютер-компьютер

int now; // true — ходит крестик сейчас

// false — ходит нолик

void setDelMem (int isSet); // выделение/освобождение памяти под массивы

// 0 — освободить, 1 — выделить

int check (); // произошел ли конец игры?

// -1 — нет

// 1 — выйграли крестики

// 0 — выйграли нолики

// 2 — ничья

// просматриваем есть соседи такого же знака (крестик, нолик)

// используется функцией check

// стоит отметить, что функция будет рекурсивной

// работает пока есть соседи и их число <= size

// если count = 0, значит кто-то выйграл

int neighbor (

int direction, // направление осмотра 1 — вправо

// 2 — вправо — вниз

// 3 — вниз

// 4 — влево — вниз

int x,

int y, // текущий элемент для которого ищем соседей

int count, // сколько уже соседей нашли

int who // кто сосед?

// 0 — нолик

// 1 — крестик

);

// процедура инициализации новой игры

void NewGame (int new_n, int new_m, int new_size, int new_mode, int new_depth);

// ход компьютера

// передаются var параметры int var res_x, res_y

void AI_turn (int who, int &res_x, int &res_y);

// who — чем ходит AI (true — крестик

// false — нолик)

// res_x, res_y — результат, куда ходит

// непосредственно вес считает эта функция (по всем направлениям)

// возвращает вес данной ячейки для who

// подсчитаем веса текущего игрока

int CalcWeight (int x, int y, int who);

// функция нахождения минимума

int FindMin (int dep, int who, int alpha, int beta);

// функция нахождения максимума

int FindMax (int dep, int who, int alpha, int beta);

int pow (int a, int n); // функция возведения в степень

// ибо что-то коряво работает стандартная ф-ия

// ограничиваем поиск решения

void FindBorder (int thickness);

// thickness — ширина ограничения

};

Описание работы программы

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

В этом поле можно указать параметры начала игры:

Столбцы и строки — это размер игрового поля.

Длина победной линии — количество крестиком или ноликов в ряд, которые необходимо построить чтобы победить в игре.

Режим игры определяет то в каком режиме будет происходить игра.

Глубина поиска — количество полуходов, которые совершает компьютер при поиске в глубину.

Выводы

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