Файл: Курсовая работа Игра Точки и квадраты.docx

Алгоритм альфа бета отсечения состоит из двух функций: нахождения наилучшей оценки для вершины дерева и выбора хода, если у корня есть несколько сыновей с одинаковой оценкой. В первой функции осуществляется обход всех вершин и определение их оценки. Оценка листа определяется изходя из оценочной функции, оценка остальных листов определяется по правилу:1)Если проверены не все сыновья узла, то применяем функция к непроверенным сыновьям2)Если узел не является корнем, то копируем значения alpha и betta родителя узла3)Вычисляем значение проверенных сыновей4)Если проверены все сыновья, то узел проверен5)Если узел не корень:5.1) Если родитель находится на чётном уровне (минимума), то корректируем значение betta родителя узла5.2) Если родитель находится на нечётном уровне (максимума), то корректируем значение alpha родителя узла5.3) Если у родителя узла alpha 5.3.1) Значение оценки родителя равно оценке текущего узла5.3.2) Если у узла есть следующий брат, то переходим к нему5.3.3) Переходим к родителю текущего узла5.4) Если у родителя узла alpha> betta:5.4.1) Переходим к родителю текущего узла5.4.2) Количество проверенных сыновей = количество сыновей5.4.3) Узел проверенВторая функция копирует положение игрового поля первого сына корня с оценкой, равной оценке вершины, если встречается ещё один сын с такой оценкой, то с вероятностью 50% заменяется поле вершины.

Программная реализация

/*Функция альфа бета отсеченияПараметры:1)Указатель на узел дереваПринцип работы:1)Если узел является листом, то высчитываем его оценку2)Если проверены не все сыновья узла, то применяем функция к непроверенным сыновьям3)Если узел не является корнем, то копируем значения alpha и betta родителя узла4)Вычисляем значение проверенных сыновей

5)Если проверены все сыновья, то узел проверен6)Если узел не корень:6.1) Если родитель находится на чётном уровне (минимума), то корректируем значение betta родителя узла6.2) Если родитель находится на нечётном уровне (максимума), то корректируем значение alpha родителя узла6.3) Если у родителя узла alpha 6.3.1) Значение оценки родителя равно оценке текущего узла6.3.2) Если у узла есть следующий брат, то переходим к нему6.3.3) Переходим к родителю текущего узла6.4) Если у родителя узла alpha> betta:6.4.1) Переходим к родителю текущего узла6.4.2) Количество проверенных сыновей = количество сыновей6.4.3) Узел проверен*/void alpha_betta(Tree_node* PNode) { if (PNode->height == 5) { get_assessment(PNode); } if (PNode->count_check_child != PNode->count_child) { for (int i = PNode->count_check_child; i count_child; i++)

{

alpha_betta(PNode->child[i]);

}

}

if (PNode->height != 1) {

PNode->alpha = PNode->parent->alpha;

PNode->betta = PNode->parent->betta;

}

for (int i = 0; i < PNode->count_child; i++) {

if (PNode->child[i]->is_check == true) {

PNode->count_check_child++;

}

}

if (PNode->count_check_child == PNode->count_check_child) {

PNode->is_check = true;

}

if (PNode->height != 1) {

if (PNode->parent->height % 2 == 1) {

if (PNode->parent->betta > PNode->assessment)

PNode->parent->betta = PNode->assessment;

}

if (PNode->parent->height % 2 == 0) {

if (PNode->parent->alpha < PNode->assessment) {

PNode->parent->alpha = PNode->assessment;

}

}

if (PNode->parent->alpha < PNode->parent->betta) {

PNode->parent->assessment = PNode->assessment;

if (PNode->next_brother != nullptr) {

PNode = PNode->next_brother;

}

else {

PNode = PNode->parent;

}

}

else {

PNode = PNode->parent;

PNode->count_check_child = PNode->count_child;

PNode->is_check = true;

}

}

}

/*Функция поиска лучшего хода

Параметры:

1)Указатель на корень дерева

Принцип работы:

1)Проверяем оценку сыновей корня

2)Если значение оценки сына равно оценке корня, то меняем значение поля корня на значение поля текущего сына

3)Если встречается ещё один сын с оценкой, равной оценке корня, то с вероятностью 50%(проверяем остаток случайно сгенерированного числа от деления на 2) заменяем значение поля корня

*/

void choose_best_move(Tree_node* PNode) {

int tmp = 0;

srand(unsigned int(time(0)));

for (int k = 0; k < PNode->count_child; k++) {

if (PNode->child[k]->assessment == PNode->assessment) {

tmp++;

if (tmp == 1) {

for (int i = 0; i < 10; i++) {

for (int j = 0; j < 10; j++) {

PNode->field[i][j] =

PNode->child[k]->field[i][j];

PNode->count_connections[i][j] =

PNode->child[k]->

count_connections[i][j];

for (int l = 0; l < 4; l++){

PNode->connections[i][j][l] =

PNode->child[k]->

connections[i][j][l];

}

}

}

if (PNode->child[k]->is_square == true) {

PNode->is_square = true;

}

}

else {

int r = rand() % 2;

if (r == 0) {

for (int i = 0; i < 10; i++) {

for (int j = 0; j < 10; j++) {

PNode->field[i][j] =

PNode->child[k]

->field[i][j];

PNode->count_connections[i][j] =

PNode->child[k]->

count_connections[i][j];

for (int l = 0; l < 4; l++) {

PNode->connections[i][j][l] =

PNode->child[k]->

connections[i][j][l];

}

}

}

if (PNode->child[k]->is_square == true) {

PNode->is_square = true;

}

}

}

}

}

}

1 2 3 4 5 6 7 8 9 10

Код Tree.h

#pragma once#ifndef _MyTree_H_#define _MyTree_H_#include

#define N 30 //Определение максимального количества

//сыновей

using namespace std;

// Класс узла дерева

struct Tree_node {

Tree_node* child[N]; //Массив указателей на сыновей

Tree_node* parent; //Указатель на родителя

Tree_node* next_brother; //Указатель на следующего брата

int field [10][10] ; //Состояние поля игры

int connections[10][10][4]; //Массив клеток, соединённых клеток

//с данной

int count_connections[10][10]; //Колличество клеток, соединённых

//с данной

int count_child; //Количество сыновей

int number; //Номер узла

int height; //Высота узла

int assessment; //Оценка текущего состояния игры

int alpha; //Параметр для альфа-бетта отсечения

int betta; //Параметр для альфа-бетта отсечения

int count_check_child; //Колличество просмотренных сыновей

//при поиске лучшего хода

bool is_check; //Был ли полностью рассмотрен узел

//т.е. рассмотрены все его сыновья

bool is_square; //Показывет был ли образован квадрат

//на этом ходу

Tree_node() {

for (int i = 0; i < 10; i++){

for (int j = 0; j < 10; j++){

field[i][j] = 0;

count_connections[i][j] = 0;

connections[i][j][0] = -1;

connections[i][j][1] = -1;

connections[i][j][2] = -1;

connections[i][j][3] = -1;

}

}

number = 0;

height = 0;

count_child = 0;

count_check_child = 0;

alpha = INT16_MIN;

betta = INT16_MAX;

assessment = INT16_MIN;

parent = nullptr;

next_brother = nullptr;

is_square = false;

is_check = false;

}

};

int num = 0; //Счётчик узлов

/*Функция для создания узла

Параметры функции:

1)Состояние поля

Результат - указатель на узел

*/

Tree_node* newNode(int value[][10] ) {

num++;

Tree_node* temp = new Tree_node;

for (int i = 0; i < 10; i++){

for (int j = 0; j < 10; j++){

temp->field[i][j] = value[i][j];

}

}

temp->number = num;

return temp;

}

/* Функция для добавления узла в дерево по индексу родителя

Параметры функции:

1)Указатель на корень дерева

2)Индекс родительского узла

3)Значение узла

*/

void push(Tree_node* PNode, int index, int key[][10]) {

if (PNode->number == index) {

if (PNode->parent == nullptr) {

PNode->height = 1;

}

PNode->count_child++;

PNode->child[PNode->count_child-1] = newNode(key);

PNode->child[PNode->count_child-1]->parent = PNode;

PNode->child[PNode->count_child-1]->height = PNode->height + 1;

if (PNode->count_child > 1) {

PNode->child[PNode->count_child - 2]->next_brother =

PNode->child[PNode->count_child - 1];

}

}

for (int i = 0; i < PNode->count_child; i++) {

push(PNode->child[i], index, key);

}

}

/*Функция удаления дерева

Параметры функции:

1)Указатель на корень дерева

*/

void deletion(Tree_node* PNode) {

for (int i = 0; i < PNode->count_child; i++) {

deletion(PNode->child[i]);

}

delete PNode;

num = 0;

}

#endif

Код основного файла

#include

#include // для функций rand() и srand()

#include // для функции time()

#include"Tree.h"

using namespace std;

Функция game_is_over()

/*Функция проверки завершенности игры

Параметры функии:

1)Указатель на узел дерева

Результат - значние логического типа: истина или ложь

Принцип работы:

1)Нулевая гипетеза- игра не закончена.

2)Если в поле встречается "0"-незанятая клетка, то гипотеза опровергается.

*/

bool game_is_over(Tree_node* PNode) {

bool res = true;

for (int i = 0; i < 10; i++) {

for (int j = 0; j < 10; j++) {

if (PNode->field[i][j] == 0) {

res = false;

}

}

}

return res;

}

Функция check_cell()

/*Функция проверки клеткиПараметры:1)Указатель на узел дерева2)Значение строки текущей клетки3)Значение столбца текущей клетки4)Значение целого типа: 1 или 2- значение человека или компьютера5)Значение типа char: s или с - направление смещения: по строке илистолбцу6)Значение целого типа: 1 или -1 - значение смещенияПринцип работы:1)Копируем значение текущего поля2)Смотрим значние параметра direction, если он равен s, то смещаемсяна значение параметра step по строке, если directon равен c, то смещаеся по столбцу3)Если значение рассматриваемой клетки равно переданному и заданнаяклетка не с ней имееет связь, то добавляем сына текущему узлу*/bool check_cell(Tree_node* PNode, int string, int column, const int value, char direction, const int step) { bool flag=false; int field[10][10]; for (int i = 0; i < 10; i++) { for (int j = 0; j < 10; j++) { field[i][j] = PNode->field[i][j]; } } if (direction == 'c') { if (field[string + step][column] == 0) { field[string + step][column] = value; } if (field[string + step][column] == value) { bool res = false; for (int i = 0; i < 4; i++) { if (PNode->connections[string][column][i] ==(string + step) * 10 + column) { res = true; } } if (res == false) { flag = true; push(PNode, PNode->number, field); for (int i = 0; i < 10; i++) { for (int j = 0; j < 10; j++) { PNode->child[PNode->count_child - 1]->count_connections[i][j] = PNode->count_connections[i][j]; PNode->child[PNode->count_child - 1]->connections[i][j][0] =PNode->connections[i][j][0]; PNode->child[PNode->count_child - 1]->connections[i][j][1] =PNode->connections[i][j][1]; PNode->child[PNode->count_child - 1]->connections[i][j][2] =PNode->connections[i][j][2]; PNode->child[PNode->count_child - 1]->connections[i][j][3] =PNode->connections[i][j][3]; } } PNode->child[PNode->count_child - 1]->connections[string + step][column][PNode->child[PNode->count_child - 1]->count_connections[string + step][column]] =string * 10 + column; PNode->child[PNode->count_child - 1]->connections[string][column][PNode->child[PNode->count_child - 1]->count_connections[string][column]] =(string + step) * 10 + column; PNode->child[PNode->count_child - 1]->count_connections[string][column]++; PNode->child[PNode->count_child - 1]->count_connections[string + step][column]++; } } } if (direction == 's') {

if (field[string][column + step] == 0) { field[string][column + step] = value; } if (field[string][column + step] == value) { bool res = false; for (int i = 0; i < 4; i++) { if (PNode->connections[string][column][i] ==string * 10 + column + step) { res = true; } } if (res == false) { flag = true; push(PNode, PNode->number, field); for (int i = 0; i < 10; i++) { for (int j = 0; j < 10; j++) { PNode->child[PNode->count_child - 1]->count_connections[i][j] =PNode->count_connections[i][j]; PNode->child[PNode->count_child - 1]->connections[i][j][0] =PNode->connections[i][j][0]; PNode->child[PNode->count_child - 1]->connections[i][j][1] =PNode->connections[i][j][1]; PNode->child[PNode->count_child - 1]->connections[i][j][2] =PNode->connections[i][j][2]; PNode->child[PNode->count_child - 1]->connections[i][j][3] =PNode->connections[i][j][3]; } } PNode->child[PNode->count_child - 1]->connections[string][column + step][PNode->child[PNode->count_child - 1]->count_connections[string][column + step]] = string * 10 + column; PNode->child[PNode->count_child - 1]->connections[string][column][PNode->child[PNode->count_child - 1]->count_connections[string][column]] =string * 10 + column + step; PNode->child[PNode->count_child - 1]->count_connections[string][column]++; PNode->child[PNode->count_child - 1]->count_connections[string][column + step]++; } } } return flag;}