Курсовая работа: Программа "Крестики-нолики 5 в ряд на неограниченном игровом поле"
Расчет производится по следующему алгоритму:
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)
NULL ));
//Глобальные переменные
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 последнего хода
bool player_first_step = true;//Приоритетность хода (true - человек)
int comp_level = 0;//Уровень игры компьютера (0 - эксперт)
//Перерисовка окна
void CChildView::OnPaint()
{
CPaintDC dc(this);
//Выведем поле
CBrush brushBgnd(RGB(0xF4, 0xA4, 0x60));//Кисть для заднего фона
CPen penO(PS_SOLID,2,RGB(0x00, 0x00, 0xFF));//Перо для нолика
CPen penX(PS_SOLID,2,RGB(0x00, 0x80, 0x00));//Перо для крестика
CPen penWin(PS_SOLID,2,RGB(0xFF, 0x00, 0x00));//Перо для выигрышных крестика или нолика
CPen penLast(PS_SOLID,2,RGB(0xFF, 0xFF, 0x00));//Перо для вывода последнего крестика или нолика
CPen penBlack(PS_SOLID,1,RGB(0x00, 0x00, 0x00)); //Перо для вывода сетки
dc.SelectObject(&brushBgnd); //Выбираем кисть с задним фоном
for (int y=0;y<size_y;y++)
{
for(int x=0;x<size_x;x++)
{
//Выводим сетку
dc.SelectObject(&penBlack);
if ((x == 0) && (y == 0))
{
dc.Rectangle(0,0,y*15+15,x*15+15);
}
else if (x == 0)
{
dc.Rectangle(y*15-1,0,y*15+15,x*15+15);
}
else if (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])
{
case 0:
continue;
break;
case 1:
dc.SelectObject(&penO);
break;
case 2:
dc.SelectObject(&penX);
break;
case 3:
case 4:
dc.SelectObject(&penWin);
break;
}
//Проверяем, не текущий ли ход
if ((last_x == x) && (last_y == y))
{
dc.SelectObject(&penLast);
}
//Выводим содержимое клетки
switch (fields[x][y])
{
case 0:
continue;
break;
//Выводим нолик
case 1:
case 3:
case 5:
dc.Ellipse(y*15+2,x*15+2,y*15+13,x*15+13);
break;
//Выодим крестик
case 2:
case 4:
case 6:
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;
}
}
}
}
//Нажатие на левую кнопку мыши, здесь производится основной расчет
void CChildView::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())
{
//Игра не закончена
//Ход компьютера
