ФЕДЕРАЛЬНОЕАГЕНТСТВО ПО ОБРАЗОВАНИЮ
Государственноеобразовательное учреждение высшего профессионального образования
«САНКТ-ПЕТЕРБУРГСКИЙГОСУДАРСТВЕННЫЙ УНИВЕРСИТЕТ АЭРОКОСМИЧЕСКОГО ПРИБОРОСТРОЕНИЯ»
Курсоваяработа
подисциплине: программирование
«Крестики-нолики5 в ряд на неограниченном игровом поле»
Выполнилстудент А.С.Лебедев
РуководительМ.Н.Суслов
Санкт-Петербург2010
СОДЕРЖАНИЕ
1. Цель работы
2. Описание игры
3. Описание входных и выходных данных
4. Описание переменных и функцийпрограммы
5. Алгоритм работы программы
6. Текст программы
7. Примеры выполнения программы
Выводы
Список литературы/>
программа игра данные алгоритм
1. Цель работы
Разработать программуигры в крестики-нолики пять в ряд на неограниченном поле. Программа должна бытьнаписана на языке С++ в среде VisualStudio 2008 или VisualStudio 2010./>
2. Описание игры
Игра ведется набесконечном поле, разлинованном в клетку. Перед игрой противники решают, ктобудет играть крестиками, а кто ноликами. В ходе игры противники ставят поочереди крестик или нолик (в зависимости от договоренности перед началом игры)в свободную клетку на поле.
Цель игры – построитьлинию из 5 стоящих рядом по вертикали, горизонтали или диагонали крестиков илиноликов. Первый игрок, построивший такую комбинацию из знаков своего типа(крестиков или ноликов) выигрывает.
Несмотря нато, что по определению игровое поле по определениюбесконечно, обычно пользуются ограниченными размерами поля. Например, в игрегомоку, поле имеет размер 15x15(ранее имело 19x19).
Пример игровой ситуациина игровом поле (показана только часть поля):X X X X X X X X
Пример выигрышакрестиков: X X X X X X X X X X
Пример выигрышаноликов:/>X X X X X X X X X X X X X X X X X X X X X X X X X X X
3. Описание входных ивыходных данных
Входные данные:
1) Размеригрового поля (10x10, 19x19,30x30, 50x50или 100х100) – задается из главного меню программы.
2) Уровеньигры компьютера (новичок, любитель или профессионал) – задается из главногоменю программы.
3) Очередностьпервого хода (человек, компьютер).
4) Координатыщелчка левой кнопкой мыши по игровому полю (x,y)– координаты очередного хода.
Выходные данные:
1) Игровоеполе, заполненное крестиками и ноликами, отображаемое на экран.
2) Вслучае выигрыша одного из игроков, отображение выигрышной последовательности исоответствующего сообщения./>
4. Описание переменныхи функций программы
Функции расчетаоценочной функции, состояния игрового поля, обработки нажатия клавиши мыши,вывода игрового поля на экран объявлены в классе представления клиентскойобласти главного окна CChildView.
Объявление классанаходится в модуле СhieldView.h.Определения функций и объявления глобальных переменных программы, отвечающих заалгоритм расчета расположены в модуле СhieldView.cpp.
Описание переменных:
unsigned char** fields– Динамический двумерный массив, представляющий игровое поле. Каждый элементмассива представляет клетку на поле. Индексы массива соответствуют положениюклеток на поле.
Элемент массива можетпринимать следующие значения:
0 – клетка пуста;
1 – в клетке нолик;
2 – в клетке крестик;
3 – в клетке нолик,входящий в выигрышный ряд по окончанию игры, служит для выделения другим цветомна поле выигрышного ряда;
4 – в клетке крестик,входящий в выигрышный ряд по окончанию игры, служит для выделения другим цветомна поле выигрышного ряда;
5 – в клетке нолик,поставленный последним ходом, служит для выделения другим цветом на полепоследнего хода;
6 – в клетке крестик,поставленный последним ходом, служит для выделения другим цветом на полепоследнего хода;
float** calc_fields –Динамический двумерный массив, представляющий значение оценочной функции длякаждой клетки игрового поля.
int size_x – Размеригрового поля по х, по умолчанию равен 19.
int size_y– Размер игрового поля по y,по умолчанию равен 19.
int old_size_x– Предыдущий размер игрового поля по x,используется при изменении размеров игрового поля.
int old_size_y– Предыдущий размер игрового поля по y,используется при изменении размеров игрового поля.
int attack_factor– Коэффициент агрессивности игры компьютера, используется при расчете оценочнойфункции. При меньшем значении данного параметра компьютер играет болееатакующе. По умолчанию равен 1 для игрока уровня эксперт.
int valuation_factor– Коэффициент, используемый при расчете оценочной функции. По умолчанию равен3.
bool end_game –Установка данной переменной в значение trueобозначает конец игры. Дальнейшие щелчки мышью по игровому полю невоспринимаются до старта новой игры. Начальное значение – false.
int last_x – Координатаx последнего хода.
int last_y– Координата y последнего хода.
boolplayer_first_step– Определяет приоритетность хода при старте новой игры. При значении trueпервым ходит человек, при false– компьютер. Значение по умолчанию – true.
intcomp_level– Уровень игры компьютера. Возможные значения:
0 – профессионал,сильный уровень, играет агрессивно;
1 – любитель,придерживается защитной стратегии;
2 – новичок, играетслабо, но достаточно агрессивно.
Описание функцийпрограммы:
voidCChildView::OnPaint()– выполняет перерисовку клиентской области окна.
Входные параметры:
Нет.
Возвращаемое значение:
Нет.
Алгоритм работы:
Производит перерисовкуклеток игрового поля. В зависимости от значений массива fields выводит вклетку:
0 – ничего не выводит;
1 – нолик синим цветом;
2 – крестик зеленымцветом;
3 – нолик краснымцветом (входит в выигрышный ряд);
4 – крестик краснымцветом (входит в выигрышный ряд);
5 – нолик желтым цветом(последний сделанный ход);
6 – крестик желтымцветом (последний сделанный ход);
voidCChildView::OnLButtonDown(UINT,CPoint xy) – Обработка нажатия левой кнопки мыши на клиентской области окна.
Входные параметры:
UINT– флаги, не используется;
CPointxy – координаты точки нажатия.
Возвращаемое значение:
Нет.
Алгоритм работы:
По нажатию левой кнопкимыши, если игра не закончена выполняются следующие действия:
1) Обновляетсямассив fieldsc учетом последнего поставленногонолика.
2) Осуществляетсяпроверка, не закончена ли игра с помощью функции end_analyze.
3) Вычисляетсяход компьютера с помощью функции ii.
4) Осуществляетсяпроверка, не закончена ли игра с помощью функции end_analyze.
5) Производитсяперерисовка окна.
Алгоритм работы функцииприведен на рисунке 1 в разделе 5.
intCChildView::end_analyze() – Функция определяет не закончена ли игра, т. е. несоставлен ли выигрышный ряд на поле одним из игроков, на основании значенийэлементов массива fields.
Входные параметры:
Нет.
Возвращаемое значение:
int– реузультат работы, = 1 – игра окончена, = 0 – игра не окончена.
Алгоритм работы:
Для каждой клетки наигровом поле просматриваются соседние клетки по горизонтали, вертикали, вниз ивправо по диагонали. Если в одном из направлений символы во всех клетках нарасстоянии до 4 совпадают с символом в текущей клетке, то игра считаетсявыигранной. К значениям найденных клеток в массиве fieldsприбавляется 2 для отображения выигрышной ситуации в окно.
void CChildView::ii() –Функция расчета очередного хода компьютера.
Входные параметры:
Нет.
Возвращаемое значение:
Нет.
Алгоритм работы:
Функция рассчитываетоценочную функцию для каждой клетки игрового поля, с помощью вызова функции calculate,и заносит рассчитанные значения в массив calc_field. Исходя из значений массиваcalc_field выбирает очередной ход компьютера.
Алгоритм работы функцииприведен в разделе 6.
unsigned longCChildView::calculate(int id,int x,int y) – Расчет оценочной функции для клеткиигрового поля, с учетом установки в нее крестика или нолика.
Входные параметры:
int id – определяеткакой символ ставится в клетку (= 1 – нолик, = 2 – крестик);
int x – координата xклетки.
int y – координата yклетки.
Возвращаемое значение:
unsignedlong – значение оценочной функции.
Алгоритм работы:
Алгоритм работы функцииприведен в разделе 6.
voidCChildView::OnNewGame() – В главном меню нажата кнопка «Новая игра».
Входные параметры:
Нет.
Возвращаемое значение:
Нет.
Алгоритм работы:
Вызывается функция new_gameдля начала новой игры. Перерисовывается игровое поле.
voidCChildView::OnX1010() – В главном меню выбран размер поля 10x10.
Входные параметры:
Нет.
Возвращаемое значение:
Нет.
Алгоритм работы:
Изменяются значения size_x,size_y.Вызывается функция new_gameдля начала новой игры. С помощью функции resize_windowустанавливаются новые размеры окна.
void CChildView::OnX1919()– В главном меню выбран размер поля 19x19.
Входные параметры:
Нет.
Возвращаемое значение:
Нет.
Алгоритм работы:
Изменяются значения size_x,size_y.Вызывается функция new_gameдля начала новой игры. С помощью функции resize_windowустанавливаются новые размеры окна.
voidCChildView::OnX3030() – В главном меню выбран размер поля 30x30.
Входные параметры:
Нет.
Возвращаемое значение:
Нет.
Алгоритм работы:
Изменяются значения size_x,size_y.Вызывается функция new_gameдля начала новой игры. С помощью функции resize_windowустанавливаются новые размеры окна.
voidCChildView::OnX5050() – В главном меню выбран размер поля 50x50.
Входные параметры:
Нет.
Возвращаемое значение:
Нет.
Алгоритм работы:
Изменяются значения size_x,size_y.Вызывается функция new_gameдля начала новой игры. С помощью функции resize_windowустанавливаются новые размеры окна.
voidCChildView::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.
voidCChildView::resize_window() – Функция установки размеров окна.
Входные параметры:
Нет.
Возвращаемое значение:
Нет.
Алгоритм работы:
Устанавливает новыеразмеры окна, в зависимости от переменных size_x,size_y.
voidCChildView::set_chеcked_menu(unsignedint old_id,unsignedint new_id)– Служит для снятия галочки и установки новой в главном меню при выбореразмеров поля, уровня игры компьютера и очереднсоти хода.
Входные параметры:
unsignedint old_id– id элемента меню, с которогонеобходимо снять галочку;
unsignedint new_id– id элемента меню, на которыйнеобходимо поставить галочку;
Возвращаемое значение:
Нет.
Алгоритм работы:
Снимает галочку вглавном меню с элемента, определяемого переменной old_idи ставит галочку на элемент, определяемый переменной new_id.
voidCChildView::OnStepH() – В главном меню выбрана очередность хода – человек.
Входные параметры:
Нет.
Возвращаемое значение:
Нет.
Алгоритм работы:
Изменяется значениепеременной player_first_step. Вызывается функция new_gameдля начала новой игры. Выполняется перерисовка окна.
voidCChildView::OnStepС() – В главном меню выбрана очередность хода – компьютер.
Входные параметры:
Нет.
Возвращаемое значение:
Нет.
Алгоритм работы:
Изменяется значениепеременной player_first_step. Вызывается функция new_gameдля начала новой игры. Выполняется перерисовка окна.
voidCChildView::OnLevelBeg() – В главном меню выбран уровень сложности начинающий.
Входные параметры:
Нет.
Возвращаемое значение:
Нет.
Алгоритм работы:
Изменяется значениепеременной comp_level.Значение коэффициента агрессивности игры компьютера attack_factorустанавливается в 1. Вызывается функция new_gameдля начала новой игры. Выполняется перерисовка окна.
voidCChildView::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
#definenew 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()
BOOLCChildView::PreCreateWindow(CREATESTRUCT& cs)
{
if(!CWnd::PreCreateWindow(cs))
returnFALSE;
cs.dwExStyle|= WS_EX_CLIENTEDGE;
cs.style&= ~WS_BORDER;
cs.lpszClass= AfxRegisterWndClass(CS_HREDRAW|CS_VREDRAW|CS_DBLCLKS,
::LoadCursor(NULL,IDC_ARROW), reinterpret_cast(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;//Рассчитанноезначение оценочной функции
int size_x =19;//Размер поля по x (19 — по умолчанию)
int size_y =19;//Размер поля по y (19 — по умолчанию)
int old_size_x =0;//Старый размер поля по x
int old_size_y =0;//Старый размер поля по y
int attack_factor =1; //Коэффициент агрессивности ИИ (1 — по умолчанию)
int valuation_factor =3;//Оценочный коэффициент (4 — по умолчанию)
bool end_game =false;//Наступил конец игры?
int last_x =0;//Координата x последнего хода
int last_y =0;//Координата y последнего хода
boolplayer_first_step = true;//Приоритетностьхода(true — человек)
int comp_level =0;//Уровень игры компьютера (0 — эксперт)
//Перерисовка окна
voidCChildView::OnPaint()
{
CPaintDCdc(this);
//Выведем поле
CBrushbrushBgnd(RGB(0xF4,0xA4, 0x60));//Кистьдля заднего фона
CPenpenO(PS_SOLID,2,RGB(0x00,0x00, 0xFF));//Перодля нолика
CPenpenX(PS_SOLID,2,RGB(0x00, 0x80, 0x00));//Перо для крестика
CPenpenWin(PS_SOLID,2,RGB(0xFF, 0x00, 0x00));//Перо для выигрышных крестика илинолика
CPen penLast(PS_SOLID,2,RGB(0xFF,0xFF, 0x00));//Перо для вывода последнего крестика или нолика
CPenpenBlack(PS_SOLID,1,RGB(0x00, 0x00, 0x00)); //Перо для вывода сетки
dc.SelectObject(&brushBgnd);//Выбираем кисть с задним фоном
for(int y=0;y
{
for(intx=0;x
{
//Выводимсетку
dc.SelectObject(&penBlack);
if((x == 0) && (y == 0))
{
dc.Rectangle(0,0,y*15+15,x*15+15);
}
elseif (x == 0)
{
dc.Rectangle(y*15-1,0,y*15+15,x*15+15);
}
elseif (y == 0)
{
dc.Rectangle(0,x*15-1,y*15+15,x*15+15);
}
else
{
dc.Rectangle(y*15-1,x*15-1,y*15+15,x*15+15);
}
//Устанавливаем перодля содержимого клетки
switch (fields[x][y])
{
case0:
continue;
break;
case1:
dc.SelectObject(&penO);
break;
case2:
dc.SelectObject(&penX);
break;
case3:
case4:
dc.SelectObject(&penWin);
break;
}
//Проверяем, не текущийли ход
if((last_x == x) && (last_y == y))
{
dc.SelectObject(&penLast);
}
//Выводимсодержимоеклетки
switch(fields[x][y])
{
case0:
continue;
break;
//Выводимнолик
case1:
case3:
case5:
dc.Ellipse(y*15+2,x*15+2,y*15+13,x*15+13);
break;
//Выодимкрестик
case2:
case4:
case6:
dc.MoveTo(y*15+2,x*15+2);
dc.LineTo(y*15+12,x*15+12);
dc.MoveTo(y*15+2,x*15+12);
dc.LineTo(y*15+12,x*15+2);
break;
}
//Возвращаем значениядля последних выведенных элементов
if((fields[x][y] == 5) || (fields[x][y] == 6))
{
fields[x][y] -= 2;
}
}
}
}
//Нажатие на левуюкнопку мыши, здесь производится основной расчет
voidCChildView::OnLButtonDown(UINT, CPoint xy)
{
//Проверка, незакончена ли игра
if (!end_game)
{
//Ставим в массивигрового поля нолик в зависимости от координат мыши
if(fields[xy.y/15][xy.x/15] == 0)
{
fields[xy.y/15][xy.x/15]= 1;
last_x= xy.y;
last_y= xy.x;
}
else
return;
//Проводим анализ, незакончена ли игра
if (!end_analyze())
{
//Игра не закончена
//Ход компьютера
ii();
//Проверяем, незакончена ли игра
if (end_analyze())
{
//Игра закончена,выводим сообщение и отрисовываем на экран
this->OnPaint();
this->Invalidate();
this->MessageBox(CA2T(«Выпроиграли»),0,0);
end_game =true;//Ставим признак конца игры
return;
}
}
else
{
//Игра закончена,выводим сообщение и отрисовываем на экран
this->OnPaint();
this->Invalidate();
this->MessageBox(CA2T(«Вывыиграли»),0,0);
end_game =true;//Ставим признак конца игры
return;
}
//Перерисовкаокна
this->OnPaint();
this->Invalidate();
}
return;
}
//Функция вычисления,не закончена ли игра
intCChildView::end_analyze()
{
//Проход по всему полю(расчет ведется для каждой клетки)
for(int i=0;i
{
for(int j=0;j
{
//Пропускаемпустуюклетку
if(fields[i][j]==0) continue;
int tek =fields[i][j];//Значение текущей клетки
int end;//Текущая длинаряда
int u;//Доп. счетчик
/////////////////////////////////////////
//Смотрим вправо оттекущей клетки
end = 0;
for(int k = j;k
{
if((k == size_y) || (fields[i][k] != tek))
{
//Нет ряда из 5
break;
}
end++;
}
if (end == 5)
{
//Есть ряд из 5 — конецигры
for(int k = j;k
{
fields[i][k]=tek+2;//Заполняем все клетки в ряду значением + 2 для отсветки красным цветом
}
return 1;
}
/////////////////////////////////////////
//Смотрим вниз и вправоот текущей клетки
end= 0;
u=i;
for(int k = j;k
{
if((k == size_y) || (u==size_x) || (fields[u][k] != tek))
{
//Нет ряда из 5
break;
}
end++;
u++;
}
if (end == 5)
{
//Есть ряд из 5 — конецигры
u=i;
for(int k = j;k
{
fields[u][k]=tek+2;//Заполняем все клетки в ряду значением + 2 для отсветки красным цветом
u++;
}
return 1;
}
/////////////////////////////////////////
//Смотрим вниз и влевоот текущей клетки
end= 0;
u=i;
for(int k = j;k>j-5;k--)
{
if((k == -1) || (u==size_x) || (fields[u][k] != tek))
{
//Нет ряда из 5
break;
}
end++;
u++;
}
if (end == 5)
{
//Есть ряд из 5 — конецигры
u=i;
for(int k = j;k>j-5;k--)
{
fields[u][k]=tek+2;//Заполняем все клетки в ряду значением + 2 для отсветки красным цветом
u++;
}
return 1;
}
/////////////////////////////////////////
//Смотрим вниз оттекущей клетки
end= 0;
for(int k = i;k
{
if((k == size_x) || (fields[k][j] != tek))
{
//Нет ряда из 5
break;
}
end++;
}
if (end == 5)
{
//Есть ряд из 5 — конецигры
for(int k = i;k
{
fields[k][j]=tek+2;//Заполняем все клетки в ряду значением + 2 для отсветки красным цветом
}
return 1;
}
}
}
//Игра не окончена
return 0;
}
//Функция расчетадействий компьютера
void CChildView::ii()
{
float max =-1;//Максимальное значение оценочной функции
int cur_x = 0,cur_y =0;//Текущие x и у
int povtor_num =0;//Количество повторов одинаковых значений оценочной функции
int cur_povtor =0;//Номер текущего повтора
//Расчитываем оценочнуюфункцию для всех клеток
for(int i=0;i
{
for(int j=0;j
{
if (fields[i][j] == 0)
{
//Расчет оценочнойфункции
calc_fields[i][j]= calculate(2,i,j) + calculate(1,i,j)*(float)attack_factor;
//Берем в расчет уровень(для профессионала случайности нет)
if (comp_level ==1)//Для любителя (небольшая случайность)
{
calc_fields[i][j]*= (1 + ((float)rand() / 32767)) / 2;
}
if (comp_level ==2)//Для новичка (максимальная случайность)
{
calc_fields[i][j]*= ((float)rand() / 32767);
}
if(calc_fields[i][j] == max)
{
//Еще одна клетка смаксимальным значением оценочной функции
povtor_num++;
}
if(calc_fields[i][j] > max)
{
//Клетка с максимальнымзначением оценочной функции
max= calc_fields[i][j];
povtor_num= 0;
cur_x= i;
cur_y = j;
}
}
}
}
//Проверяем, есть ливообще свободные клетки на поле
if (max == -1)
{
return;
}
//Выбираем куда сделатьход
if (povtor_num > 0)
{
//Выбираем куда ходитьслучайным образом из клеток с одинаковыми значениями оценочной функции
cur_povtor = rand() /(32767 / povtor_num);//Номер элемента, куда надо ходить
//Ищем его по полю
int buf_povtor = -1;
for(int i=0;i
{
for(int j=0;j
{
if(calc_fields[i][j] == max)
{
buf_povtor++;
if(buf_povtor == cur_povtor) //Клетканайдена
{
fields[i][j] =2;//Ставим крестик
last_x = i;//Запоминаемкоординаты последнего хода
last_y= j;
return;
}
}
}
}
}
else
{
//Одна клетка смаксимальным знаечением
fields[cur_x][cur_y] =2;//Ставим крестик
last_x =cur_x;//Запоминаем координаты последнего хода
last_y = cur_y;
}
}
//Функция расчетаоценочной функции
unsignedlong CChildView::calculate(int id,int x,int y)
{
//Подсчет оценочнойфункции
//Ставим в массивевременно значение == id
fields[x][y]= id;
intseries_length = 0;//Текущая длинаряда
unsigned long sum =0;//Общее значение оценочной функции
///////////Расчетсверху вниз/////////
//Проход по каждойклетки, которая может входить в ряд
for (int i =0;i
{
//Проверка, не вышли лиза границы поля
if((x-4+i)
if((x+i) > (size_x — 1)) break;
//Проход по всемвозможным рядам, отстоящим от клетки не более чем на 5
for(int j=0;j
{
if((fields[x-4+i+j][y] != id) && (fields[x-4+i+j][y] != 0))
{
//Конецряда
series_length= 0;
break;
}
if(fields[x-4+i+j][y] != 0) series_length++; //Рядувеличивается
}
if(series_length == 1) series_length = 0;//Рядизсамойклеткинеучитываем
if(series_length == 5) series_length = 100; //Выигрышнаяситуация,ставимбольшоезначение
//Плюсуемсериюкобщейсумме
unsignedlong pow_st = valuation_factor;
if(series_length == 100)
{
if(id == 2)
pow_st =10000;//Большое значение при своем выигрыше
else
pow_st = 1000;//Большое значение при выигрыше соперника, но меньшее, чем при своем
}
else
{
for (inti=0;i
{
pow_st*=valuation_factor;
}
}
sum+= pow_st;
series_length = 0;
}
///////////Расчет слеванаправо/////////
//Проход по каждойклетки, которая может входить в ряд
for (int i =0;i
{
//Проверка, не вышли лиза границы поля
if((y-4+i)
if((y+i) > (size_y — 1)) break;
//Проход по всемвозможным рядам, отстоящим от клетки не более чем на 5
for(int j=0;j
{
if((fields[x][y-4+i+j] != id) && (fields[x][y-4+i+j] != 0))
{
//Конецряда
series_length= 0;
break;
}
if(fields[x][y-4+i+j] != 0) series_length++; //Рядувеличивается
}
if(series_length == 1) series_length = 0; //Рядизсамойклеткинеучитываем
if(series_length == 5) series_length = 100; //Выигрышнаяситуация,ставимбольшоезначение
//Плюсуемсериюкобщейсумме
unsignedlong pow_st = valuation_factor;
if(series_length == 100)
{
if(id == 2)
pow_st =10000;//Большое значение при своем выигрыше
else
pow_st = 1000;//Большое значение при выигрыше соперника, но меньшее, чем при своем
}
else
{
for (inti=0;i
{
pow_st*=valuation_factor;
}
}
sum+= pow_st;
series_length = 0;
}
///////////Расчет подиагонали с левого верхнего/////////
//Проход по каждойклетки, которая может входить в ряд
for (int i =0;i
{
//Проверка, не вышли лиза границы поля
if((y-4+i)
if((x-4+i)
if((x+i) > (size_x — 1)) break;
if((y+i) > (size_y — 1)) break;
//Проход по всемвозможным рядам, отстоящим от клетки не более чем на 5
for(int j=0;j
{
if((fields[x-4+i+j][y-4+i+j] != id) && (fields[x-4+i+j][y-4+i+j] != 0))
{
//Конецряда
series_length= 0;
break;
}
if(fields[x-4+i+j][y-4+i+j] != 0) series_length++; //Рядувеличивается
}
if(series_length == 1) series_length = 0; //Рядизсамойклеткинеучитываем
if(series_length == 5) series_length = 100; //Выигрышнаяситуация,ставимбольшоезначение
//Плюсуемсериюкобщейсумме
unsignedlong pow_st = valuation_factor;
if(series_length == 100)
{
if(id == 2)
pow_st =10000;//Большое значение при своем выигрыше
else
pow_st = 1000;//Большое значение при выигрыше соперника, но меньшее, чем при своем
}
else
{
for (inti=0;i
{
pow_st*=valuation_factor;
}
}
sum+= pow_st;
series_length = 0;
}
///////////Расчет подиагонали с левого нижнего/////////
//Проход по каждойклетки, которая может входить в ряд
for (int i =0;i
{
//Проверка, не вышли лиза границы поля
if((y-4+i)
if((x+4-i) > (size_x — 1)) continue;
if((x-i)
if((y+i) > (size_y — 1)) break;
//Проход по всемвозможным рядам, отстоящим от клетки не более чем на 5
for(int j=0;j
{
if((fields[x+4-i-j][y-4+i+j] != id) && (fields[x+4-i-j][y-4+i+j] != 0))
{
//Конецряда
series_length= 0;
break;
}
if(fields[x+4-i-j][y-4+i+j] != 0) series_length++; //Рядувеличивается
}
if(series_length == 1) series_length = 0; //Рядизсамойклеткинеучитываем
if(series_length == 5) series_length = 100; //Выигрышнаяситуация,ставимбольшоезначение
//Плюсуемсериюкобщейсумме
unsignedlong pow_st = valuation_factor;
if(series_length == 100)
{
if(id == 2)
pow_st =10000;//Большое значение при своем выигрыше
else
pow_st = 1000;//Большое значение при выигрыше соперника, но меньшее, чем при своем
}
else
{
for (inti=0;i
{
pow_st*=valuation_factor;
}
}
sum+= pow_st;
series_length = 0;
}
//Возвращаем исходноезначение
fields[x][y] = 0;
return sum;
}
//В меню нажата кнопкаНовая игра
voidCChildView::OnNewGame()
{
new_game(); //Функцияначала новой игры
this->OnPaint();
this->Invalidate();
}
//Выбранополе10x10
voidCChildView::OnX1010()
{
//Ставимгалочкувменю
switch(size_x)
{
case19:
set_chеcked_menu(ID_X1919,ID_X1010);
break;
case30:
set_chеcked_menu(ID_X3030,ID_X1010);
break;
case50:
set_chеcked_menu(ID_X5050,ID_X1010);
break;
case100:
set_chеcked_menu(ID_X100100,ID_X1010);
break;
}
size_x= 10;
size_y= 10;
//Стартуем новую игру
new_game();
//Устанавливаем новыеразмеры окна
resize_window();
}
//Выбрано поле 19x19
voidCChildView::OnX1919()
{
//Ставим галочку в меню
switch (size_x)
{
case10:
set_chеcked_menu(ID_X1010,ID_X1919);
break;
case30:
set_chеcked_menu(ID_X3030,ID_X1919);
break;
case50:
set_chеcked_menu(ID_X5050,ID_X1919);
break;
case100:
set_chеcked_menu(ID_X100100,ID_X1919);
break;
}
size_x= 19;
size_y= 19;
//Стартуем новую игру
new_game();
//Устанавливаем новыеразмеры окна
resize_window();
}
//Выбрано поле 19x19
voidCChildView::OnX3030()
{
//Ставим галочку в меню
switch (size_x)
{
case10:
set_chеcked_menu(ID_X1010,ID_X3030);
break;
case19:
set_chеcked_menu(ID_X1919,ID_X3030);
break;
case50:
set_chеcked_menu(ID_X5050,ID_X3030);
break;
case100:
set_chеcked_menu(ID_X100100,ID_X3030);
break;
}
size_x= 30;
size_y= 30;
//Стартуем новую игру
new_game();
//Устанавливаем новыеразмеры окна
resize_window();
}
//Выбрано поле 50x50
voidCChildView::OnX5050()
{
//Ставим галочку в меню
switch (size_x)
{
case10:
set_chеcked_menu(ID_X1010,ID_X5050);
break;
case19:
set_chеcked_menu(ID_X1919,ID_X5050);
break;
case30:
set_chеcked_menu(ID_X3030,ID_X5050);
break;
case100:
set_chеcked_menu(ID_X100100,ID_X5050);
break;
}
size_x= 50;
size_y= 50;
//Стартуем новую игру
new_game();
//Устанавливаем новыеразмеры окна
resize_window();
}
//Выбрано поле 100x100
voidCChildView::OnX100100()
{
//Ставим галочку в меню
switch (size_x)
{
case10:
set_chеcked_menu(ID_X1010,ID_X100100);
break;
case19:
set_chеcked_menu(ID_X1919,ID_X100100);
break;
case30:
set_chеcked_menu(ID_X3030,ID_X100100);
break;
case50:
set_chеcked_menu(ID_X5050,ID_X100100);
break;
}
size_x= 100;
size_y= 100;
//Стартуем новую игру
new_game();
//Устанавливаем новыеразмеры окна
resize_window();
}
//Функция начала новойигры
voidCChildView::new_game()
{
if((old_size_x != 0) || (old_size_y != 0))
{
//Освобождаем памятьдинамических массивов
try
{
for(int i=0;i
{
deletefields[i];
deletecalc_fields[i];
}
deletefields;
deletecalc_fields;
}
catch(...)
{
this->MessageBox(CA2T(«Ошибкаработыспамятью»),0,0);
this->CloseWindow();
}
}
//Присваиваем старымзначениям новые
old_size_x= size_x;
old_size_y= size_y;
//Выделяем память подмассивы
try
{
fields= new unsigned char*[size_x];
calc_fields= new float*[size_x];
for(inti=0;i
{
fields[i]= new unsigned char[size_y];
calc_fields[i]= new float[size_y];
}
}
catch(...)
{
this->MessageBox(CA2T(«Ошибкавыделенияпамяти»),0,0);
this->CloseWindow();
}
//Обнуляеммассивы
for(int i=0;i
for(int j=0;j
{
fields[i][j] = 0;
}
//Сбрасываем флагначала игры
end_game = false;
//Проверяем, не долженли компьютер ходить первым
if(!player_first_step)
ii();
}
//Установка новыхразмеров окна
voidCChildView::resize_window()
{
//Устанавливаем размерыокна в соответствии с размером поля
RECT Rect;//Размерывнутренней области
RECTWindowRect;//Размеры окна
this->GetWindowRect(&Rect);
this->GetParent()->GetWindowRect(&WindowRect);
this->GetParent()->MoveWindow(WindowRect.left,WindowRect.top,
size_y*15+ 4 + (WindowRect.right — Rect.right) + (Rect.left — WindowRect.left),
size_x*15+ 4 + (WindowRect.bottom — Rect.bottom) + (Rect.top — WindowRect.top),1);
}
//Установкагалочкивменю
voidCChildView::set_chеcked_menu(unsignedint old_id,unsigned int new_id)
{
//Создаем структуруэлемента меню
MENUITEMINFOmenuItemInfo;
menuItemInfo.cbSize =sizeof(MENUITEMINFO);
menuItemInfo.fMask =MIIM_STATE;//Работа с состоянием элемента
//Получаем указатель наменю
CMenu*pMenu=this->GetParent()->GetMenu();
//Ставим галочку вновом элементе
menuItemInfo.fState =MFS_CHECKED;
pMenu->SetMenuItemInfoW(new_id,&menuItemInfo,0);
//Снимаемгалочкувстаромэлементе
menuItemInfo.fState= MFS_UNCHECKED;
pMenu->SetMenuItemInfoW(old_id,&menuItemInfo,0);
return;
}
//Выбранпервыйходчеловека
voidCChildView::OnStepH()
{
//Ставимгалочкувменю
if(player_first_step == false)
set_chеcked_menu(ID_STEP_C,ID_STEP_H);
player_first_step= true;
//Стартновойигры
new_game();
//Перерисовкаокна
this->OnPaint();
this->Invalidate();
}
//Выбран первый ходкомпьютера
voidCChildView::OnStepC()
{
//Ставим галочку в меню
if(player_first_step == true)
set_chеcked_menu(ID_STEP_H,ID_STEP_C);
player_first_step= false;
//Стартновойигры
new_game();
//Перерисовкаокна
this->OnPaint();
this->Invalidate();
}
//Выбран уровенькомпьютера — новичок
voidCChildView::OnLevelBeg()
{
//Ставим галочку в меню
if(comp_level == 0)
{
set_chеcked_menu(ID_LEVEL_PROF,ID_LEVEL_BEG);
}
elseif (comp_level == 1)
{
set_chеcked_menu(ID_LEVEL_AMAT,ID_LEVEL_BEG);
}
comp_level= 2;
attack_factor= 1;
//Стартновойигры
new_game();
//Перерисовкаокна
this->OnPaint();
this->Invalidate();
}
//Выбран уровенькомпьютера — любитель
voidCChildView::OnLevelAmat()
{
//Ставим галочку в меню
if(comp_level == 2)
{
set_chеcked_menu(ID_LEVEL_BEG,ID_LEVEL_AMAT);
}
elseif (comp_level == 0)
{
set_chеcked_menu(ID_LEVEL_PROF,ID_LEVEL_AMAT);
}
comp_level= 1;
attack_factor= 10;
//Стартновойигры
new_game();
//Перерисовкаокна
this->OnPaint();
this->Invalidate();
}
//Выбран уровенькомпьютера — профессионал
voidCChildView::OnLevelProf()
{
//Ставим галочку в меню
if(comp_level == 2)
{
set_chеcked_menu(ID_LEVEL_BEG,ID_LEVEL_PROF);
}
elseif (comp_level == 1)
{
set_chеcked_menu(ID_LEVEL_AMAT,ID_LEVEL_PROF);
}
comp_level= 0;
attack_factor= 1;
//Стартновойигры
new_game();
//Перерисовкаокна
this->OnPaint();
this->Invalidate();
}/>
7. Примеры выполненияпрограммы
Примеры выполненияпрограммы приведены на рисунках 2, 3, 4, 5.
/>
Рисунок 2 – Вид окнапрограмме при запуске.
/>
Рисунок 3 – Игроваяситуация при игре на поле 30x30на сложности любитель.
/>
Рисунок 4 – Выигрышкомпьютера при игре на сложности профессионал.
/>
Рисунок 5 – Победаигрока при игре на сложности любитель на поле 30x30.
Выводы
В ходе выполнениякурсовой работы был разработан алгоритм действий компьютерного игрока при игрев крестики-нолики пять в ряд на бесконечном поле.
В ходе выполненияработы удалось добиться достаточно сильного уровня игры на сложностипрофессионал.
Разработанный алгоритмбыл реализован на языке C++на платформе MicrosoftVisual Studio2008./>
Список литературы
1. АрчерТ., Уайтчепел Э. Visual C++ .NET. Библия пользователя — Вильямс, 2007.
2. ЛибертиД., Джонс Б. Освой самостоятельно C++ за 21 день. — Вильямс, 2007.
3. Материалысайта www.firststeps.ru/mfc/steps.
4. ПодбельскийВ.В. Язык C++. — М.:«Финансы и статистика», 2003.