Программа "Крестики-нолики 5 в ряд на неограниченном игровом поле" (стр. 2 из 4)

void CChildView::OnX5050() – В главном меню выбран размер поля 50x50.

Входные параметры:

Нет.

Возвращаемое значение:

Нет.

Алгоритм работы:

Изменяются значения size_x, size_y. Вызывается функция new_game для начала новой игры. С помощью функции resize_window устанавливаются новые размеры окна.

void CChildView::OnX100100() – В главном меню выбран размер поля 100x100.

Входные параметры:

Нет.

Возвращаемое значение:

Нет.

Алгоритм работы:

Изменяются значения size_x, size_y. Вызывается функция new_game для начала новой игры. С помощью функции resize_window устанавливаются новые размеры окна.

void CChildView::new_game() – Функция начала новой игры.

Входные параметры:

Нет.

Возвращаемое значение:

Нет.

Алгоритм работы:

Функция начинает новую игру, при этом:

1) Перевыделяется память для динамических массивов fields и calc_fields в зависимости от значений old_size_x, old_size_y и size_x, size_y.

2) Сбрасывается в false флаг end_game.

3) Если переменная player_first_step равна false, то рассчитывается первый ход компьютера с помощью вызова функции ii.

void CChildView::resize_window() – Функция установки размеров окна.

Входные параметры:

Нет.

Возвращаемое значение:

Нет.

Алгоритм работы:

Устанавливает новые размеры окна, в зависимости от переменных size_x, size_y.

void CChildView::set_chеcked_menu(unsigned int old_id,unsigned int new_id) – Служит для снятия галочки и установки новой в главном меню при выборе размеров поля, уровня игры компьютера и очереднсоти хода.

Входные параметры:

unsigned int old_id – id элемента меню, с которого необходимо снять галочку;

unsigned int new_id – id элемента меню, на который необходимо поставить галочку;

Возвращаемое значение:

Нет.

Алгоритм работы:

Снимает галочку в главном меню с элемента, определяемого переменной old_id и ставит галочку на элемент, определяемый переменной new_id.

void CChildView::OnStepH() – В главном меню выбрана очередность хода – человек.

Входные параметры:

Нет.

Возвращаемое значение:

Нет.

Алгоритм работы:

Изменяется значение переменной player_first_step. Вызывается функция new_game для начала новой игры. Выполняется перерисовка окна.

void CChildView::OnStepС() – В главном меню выбрана очередность хода – компьютер.

Входные параметры:

Нет.

Возвращаемое значение:

Нет.

Алгоритм работы:

Изменяется значение переменной player_first_step. Вызывается функция new_game для начала новой игры. Выполняется перерисовка окна.

void CChildView::OnLevelBeg() – В главном меню выбран уровень сложности начинающий.

Входные параметры:

Нет.

Возвращаемое значение:

Нет.

Алгоритм работы:

Изменяется значение переменной comp_level. Значение коэффициента агрессивности игры компьютера attack_factor устанавливается в 1. Вызывается функция new_game для начала новой игры. Выполняется перерисовка окна.

void CChildView::OnLevelAmat() – В главном меню выбран уровень сложности любитель.

Входные параметры:

Нет.

Возвращаемое значение:

Нет.

Алгоритм работы:

Изменяется значение переменной comp_level. Значение коэффициента агрессивности игры компьютера attack_factor устанавливается в 1. Вызывается функция new_game для начала новой игры. Выполняется перерисовка окна.

5. Алгоритм работы программы

Алгоритм выполнения очередного хода:

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

Рисунок 1 – Блок-схема работы функции OnLButtonDown.

Алгоритм расчета очередного хода компьютерного соперника:

Расчет очередного хода компьютерного соперника выполняется при помощи вызова функции ii. Расчет производится при старте игры, если приоритет хода принадлежит компьютеру или после хода игрока вызовом из функции OnLButtonDown.

Расчет производится по следующему алгоритму:

1) Рассчитывается суммарная оценочная функция

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

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

Суммарная оценочная функция вычисляется по формуле:

, где

– значение суммарной оценочной функции;

– значение оценочной функции при постановке в клетку крестика, рассчитанное с помощью вызова функции calculate;

– значение оценочной функции при постановке в клетку нолика, рассчитанное с помощью вызова функции calculate;

– коэффициент агрессивности ИИ, задается переменной attack_factor.

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

Значение коэффициента агрессивности на уровнях новичок и профессионал равно 1, компьютер ведет себя агрессивно. На уровне любитель значение равно 10, алгоритм находится в глубокой обороне.

Для уровней новичок и любитель также дополнительно вносится случайность значения суммарной оценочной функции: на уровне новичок значение суммарной оценочной функции умножается на случайное число, принимающее значение [0,1], на уровне любитель умножается на случайное число, принимающее значение [0.5,1].

2) Находится клетка с максимальным значением суммарной оценочной функции. Если таких клеток несколько, то из них выбирается случайная. Ход делается в найденную клетку, массив fields обновляется путем установки соответствующего элемента в значение 2.

Алгоритм расчета оценочной функции:

Расчет оценочной функции для клетки игрвого поля производится вызовом функции calculate. Входными параметрами являются индексы поля в массиве fields (текущая клетка) и идентификатор, какой символ(крестик или нолик) будет поставлен в текущую клетку. Этот символ временно ставится в массив fields до окончания работы функции.

Расчет производится по следующей схеме. Просматриваются все ряды, продолжением которых может являться текущая клетка. Под рядом подразумевается последовательность из 5 клеток, каждая из которых может быть пустой или содержащей такой же символ, как и в текущей. Для этого проходятся все клетки на расстоянии не более 4 от данной, сначала по вертикали, затем по горизонтали, затем по 2 диагоналям. Для каждой проходимой клетки рассчитывается длина ряда, в которую она входит вместе с текущей. Под длиной ряда понимается количество одинаковых символов(крестиков или ноликов) в последовательности из 5 клеток. Если ряд прерывается противоположным символом, то длина ряда принимается равной нулю.

Значение оценочной функции рассчитывается по формуле:

, где – общее количество ненулевых длин рядов;

– коэффициент оценочной функции;

– длина -го ряда.

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

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

6. Текст программы

Файл ChildView.cpp:

//Модуль, содержащий основной алгоритм работы программы

#include "stdafx.h"

#include "XO.h"

#include "ChildView.h"

#ifdef _DEBUG

#define new DEBUG_NEW

#endif

// CChildView

CChildView::CChildView()

{

}

CChildView::~CChildView()

{

}

BEGIN_MESSAGE_MAP(CChildView, CWnd)

ON_WM_PAINT()

ON_WM_LBUTTONDOWN()

ON_COMMAND(ID_NEW_GAME, &CChildView::OnNewGame)

ON_COMMAND(ID_X1010, &CChildView::OnX1010)

ON_COMMAND(ID_X100100, &CChildView::OnX100100)

ON_COMMAND(ID_X1919, &CChildView::OnX1919)

ON_COMMAND(ID_X3030, &CChildView::OnX3030)

ON_COMMAND(ID_X5050, &CChildView::OnX5050)

ON_COMMAND(ID_STEP_H, &CChildView::OnStepH)

ON_COMMAND(ID_STEP_C, &CChildView::OnStepC)

ON_COMMAND(ID_LEVEL_BEG, &CChildView::OnLevelBeg)

ON_COMMAND(ID_LEVEL_AMAT, &CChildView::OnLevelAmat)

ON_COMMAND(ID_LEVEL_PROF, &CChildView::OnLevelProf)

END_MESSAGE_MAP()

BOOL CChildView::PreCreateWindow(CREATESTRUCT& cs)

{

if (!CWnd::PreCreateWindow(cs))

return FALSE;

cs.dwExStyle |= WS_EX_CLIENTEDGE;

cs.style &= ~WS_BORDER;

cs.lpszClass = AfxRegisterWndClass(CS_HREDRAW|CS_VREDRAW|CS_DBLCLKS,

::LoadCursor(NULL, IDC_ARROW), reinterpret_cast<HBRUSH>(COLOR_WINDOW+1), NULL);

srand((unsigned)time( NULL ));

//Начало новой игры

new_game();

return TRUE;

}

//Глобальные переменные

unsigned char** fields;//Игровое поле ( = 0 - ничего нет, = 1 - нолик,

//= 2 - крестик, = 3 - выигравший нолик, = 4 - выигравший крестик

//= 5 - последний поставленный нолик, = 6 - последний поставленный крестик)

float** calc_fields;//Рассчитанное значение оценочной функции