Добавлен: 09.01.2024
Просмотров: 105
Скачиваний: 3
ВНИМАНИЕ! Если данный файл нарушает Ваши авторские права, то обязательно сообщите нам.
Функция альфа бета отсечения
Описание функции альфа бета отсечения
Алгоритм альфа бета отсечения состоит из двух функций: нахождения наилучшей оценки для вершины дерева и выбора хода, если у корня есть несколько сыновей с одинаковой оценкой.
В первой функции осуществляется обход всех вершин и определение их оценки. Оценка листа определяется изходя из оценочной функции, оценка остальных листов определяется по правилу:
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
{
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
#include
#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;
}