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

count_child - 1], i, j, i - 1, j); }

flag=check_cell(PNode, i, j, value, 'c', 1);

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

count_child - 1], i,

j, i + 1, j); }

flag=check_cell(PNode, i, j, value, 's', 1);

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

count_child - 1], i,

j, i, j+1); }

}

if (j == 9 && i != 0 && i != 9) {

flag = check_cell(PNode, i, j, value, 'c', -1);

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

count_child - 1], i,

j, i - 1, j); }

flag = check_cell(PNode, i, j, value, 'c', 1);

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

count_child - 1], i, j, i + 1, j); }

flag = check_cell(PNode, i, j, value, 's', -1);

if (flag == true) { is_square(PNode->child[PNode-> count_child - 1], i,

j, i, j - 1); }

}
if (i != 0 && i != 9 && j != 0 && j != 9) {

flag = check_cell(PNode, i, j, value, 's', -1);

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

count_child - 1], i,

j, i, j - 1); }

flag = check_cell(PNode, i, j, value, 's', 1);

if (flag == true) { is_square(PNode->child[PNode-> count_child - 1], i,

j, i, j + 1); }

flag = check_cell(PNode, i, j, value, 'c', -1);

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

count_child - 1], i,

j, i-1, j); }

flag = check_cell(PNode, i, j, value, 'c', 1);

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

count_child - 1], i,

j, i+1, j); }

}

}

}

}

}

---

Функция make_tree()

/*Функция постоения дерева возможных ходов

Параметры:

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

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

1)Функция повторяется, пока высота дерева не равна 5

2)Если высота текущего дерева нечетная, то следующий ход компьютера

2.1)Если на предыдущем ходу был собран квадрат, то добавляем сына с текущем состоянием поля т.к. человек пропускает ход

2.2)Если на предыдущем ходу не был собран квадрат, то вызываем функцию generation_move с параметром 2.

3)Если высота текущего дерева четная, то следующий ход человека

3.1)Если на предыдущем ходу был собран квадрат, то добавляем сына с текущем состоянием поля т.к. компьютер пропускает ход

3.2)Если на предыдущем ходу не был собран квадрат, то вызываем функцию generation_move с параметром 1.

*/

void make_tree(Tree_node* PNode) {

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

if (PNode->is_square == false) {

generation_move(PNode, 1);

}

else {

push(PNode, PNode->number, PNode->field);

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

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

PNode->child[0]->count_connections[i][j] =

PNode->count_connections[i][j];
PNode->child[0]->connections[i][j][0] =

PNode->connections[i][j][0];
PNode->child[0]->connections[i][j][1] =

PNode->connections[i][j][1];
PNode->child[0]->connections[i][j][2] =

PNode->connections[i][j][2];
PNode->child[0]->connections[i][j][3] =

PNode->connections[i][j][3];

}

}

}

}

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

if (PNode->is_square == false) {

generation_move(PNode, 2);

}

else {

push(PNode, PNode->number, PNode->field);

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

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

PNode->child[0]->count_connections[i][j] =

PNode->count_connections[i][j];
PNode->child[0]->connections[i][j][0] =

PNode->connections[i][j][0];
PNode->child[0]->connections[i][j][1] =

PNode->connections[i][j][1];
PNode->child[0]->connections[i][j][2] =

PNode->connections[i][j][2];
PNode->child[0]->connections[i][j][3] =

PNode->connections[i][j][3];

}

}

}

}

if (PNode->height <= 3) {

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

make_tree(PNode->child[i]);

}

}

}

Функция get_assessement()

/*Оценочная функция

Параметры:

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

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

1)Просматриваются значения клеток текущего поля

2)Если значение клетки равно 1, то она принадлежит компьютеру. К результату прибавляется количество связей этой клетки

3)Если значение клетки равно 2, то она принадлежит человеку. К результату вычитается количество связей этой клетки

*/

---

void get_assessment(Tree_node* PNode) {

int res = 0;

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

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

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

res = res + PNode->count_connections[i][j];

}

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

res = res - PNode->count_connections[i][j];

}

}

}

PNode->assessment = res;

}

Функция alpha_betta()

/*Функция альфа бетта отсечения

Параметры:

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   2   3   4   5   6   7   8   9   10

---

Функция choose_best_move()

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

Параметры:

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; }

}

}

}

}

}

Функция Print_field()

/*Функция вывода теущего поля

Параметры:

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

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

1)Если значение клетки равно 1, то выводим красную точку,2 - синию, 0-белую

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

3)Если у клетки есть связь с нижней, то выводим "|"соответствующего цвета " "

*/

void Print_field(Tree_node* PNode) {

cout << " \u001B[33m 0 1 2 3 4 5 6 7 8 9\n";

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

if (i > 0) {

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

bool f = false;

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

if (PNode->connections[i][j][k] ==(i - 1) * 10 + j) {

f = true;

}

}

if (f == true) {

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

cout << "\u001B[31m | ";

}

else {

cout << "\u001B[34m | ";

}

}

else {cout << " ";}

}

cout << "\n";

}

cout << "\u001B[33m" << i << " ";

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

if (PNode->field[i][j] == 1) {cout << "\u001B[31m.";}

if (PNode->field[i][j] == 2) {cout << "\u001B[34m.";}

if (PNode->field[i][j] == 0) {cout << "\u001B[32m.";}

bool f = false;

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

if (PNode->connections[i][j][k] == i * 10 + j + 1){

f = true;

}

}

if (f == true) {

---

if (PNode->field[i][j] == 1) {cout << "\u001B[31m - ";}

else {cout << "\u001B[34m - ";}

}

else {cout << " ";}

}

cout << "\n";

}

cout << "\n";

}

Функция create_root()

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

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

1)Матрица состояния текущего игровго поля

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

1)Создание новго узла с переданным значением

2)Высота узла равна 1

*/

Tree_node* creat_root(int start_field[10][10]) {

Tree_node* root = newNode(start_field);

root->height = 1;

return root;

}

Функция re_create_root()

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

Параметры:

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

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

1)Копирование состояния поля, связей клеток и их количества во временные переменные

2)Удаление дерева по указателю на корень

3)Создание нового корня, по переданному указателю

4)Сохранение значний переданного корня

*/

Tree_node * re_create_root(Tree_node* root) {

int field[10][10];

int count_connections[10][10];

int connections[10][10][4];

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

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

field[i][j] = root->field[i][j];

count_connections[i][j] = root->count_connections[i][j];

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

connections[i][j][k] = root->connections[i][j][k];

}

}

}

deletion(root);

root = creat_root(field);

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

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

root->count_connections[i][j] = count_connections[i][j];

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

root->connections[i][j][k] = connections[i][j][k];

}

}

}

return root;

}

Функция read_human_move()

/*Функция считывания хода человека

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

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

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

1)Считываются номера строки и столбца начальной клетки.

2)Если они выходят за диапозон [0;9], то сообщается об ошибке, функция перезапускается.

3)Считываются номера строки и столбца целевой клетки.

4)Если они выходят за диапозон [0;9], то сообщается об ошибке, функция перезапускается.

5)Если целевая и начльная клетка не соседние, то сообщается об ошибке, функция перезапускается.

6)Значение поля в целевой клетке заполняется значением "2".

7)К количествам связей начальной о целевой клеток добаляется единица.

8)Значения строк и столбцов начальной и целевой клеток записываются в соответствующие массивы соединённых клеток.

*/

void read_human_move(Tree_node* PNode) {

int start_string = 0, start_column = 0, finish_string = 0, finish_column = 0;

cout << "\u001B[37mВведите строку начальной клетки : ";

---