2020-04-20
89
#include <stdio.h>
#include <ctype.h>
#include <conio.h>
#define String_Length 80
#define Squares 9
typedef char Square_Type;
typedef Square_Type Board_Type[Squares];
const Square_Type Empty = ' ';
/* Максимальна величина оцінки ходу */
const int Infinity = 10;
/* Максимальна кількість ходів у грі */
const int Maximum_Moves = Squares;
int Total_Nodes;
/* Масив‚ що описує всім виграшних комбінацій */
#define Possible_Wins 8
const int Three_in_a_Row[Possible_Wins][3] = {
{ 0, 1, 2 },
{ 3, 4, 5 },
{ 6, 7, 8 },
{ 0, 3, 6 },
{ 1, 4, 7 },
{ 2, 5, 8 },
{ 0, 4, 8 },
{ 2, 4, 6 }
};
/* Масив, який використовується в евристичній формулі для кожного ходу */
const int Heuristic_Array[4][4] = {
{ 0, -10, -100, -1000 },
{ 10, 0, 0, 0 },
{ 100, 0, 0, 0 },
{ 1000, 0, 0, 0 }
};
/* Структура, що отримує хід та визначає його евристику */
typedef struct {
int Square;
int Heuristic;
} Move_Heuristic_Type;
/* Очистка ігрового поля */
void Initialize(Board_Type Board) {
int I;
for (I = 0; I < Squares; I++)
Board[I] = Empty;
}
/* Якщо гравець переміг, виводить переможця. Якщо гра нічийна, повертає 'C'. Якщо гра ще не завершена‚ повертає Empty. */
Square_Type Winner(Board_Type Board) {
int I;
for (I = 0; I < Possible_Wins; I++) {
Square_Type Possible_Winner = Board[Three_in_a_Row[I][0]];
|
|
|
if (Possible_Winner!= Empty &&
Possible_Winner == Board[Three_in_a_Row[I][1]] &&
Possible_Winner == Board[Three_in_a_Row[I][2]])
return Possible_Winner;
}
for (I = 0; I < Squares; I++)
if (Board[I] == Empty)
return Empty;
return 'C';
}
Square_Type Other(Square_Type Player) {
return Player == 'X'? 'O': 'X';
}
/* Виконання ходу на ігровому полі */
void Play(Board_Type Board, int Square, Square_Type Player) {
Board[Square] = Player;
}
/* Вивід ігрового поля */
void Print(Board_Type Board) {
int I;
clrscr();
for (I = 0; I < Squares; I += 3) {
if (I > 0)
printf("\t---+---+---\n");
printf("\t %c | %c | %c \n", Board[I], Board[I + 1], Board[I + 2]);
}
printf("\n");
}
/* Повертає використану евристику, щоб визначити команду, в якій розшукується підпорядкована вершина */
int Evaluate(Board_Type Board, Square_Type Player) {
int I;
int Heuristic = 0;
for (I = 0; I < Possible_Wins; I++) {
int J;
int Players = 0, Others = 0;
for (J = 0; J < 3; J++) {
Square_Type Piece = Board[Three_in_a_Row[I][J]];
if (Piece == Player)
Players++;
else if (Piece == Other(Player))
Others++;
}
Heuristic += Heuristic_Array[Players][Others];
}
return Heuristic;
}
/* Визначає ціну найкращого ходу‚ яка повертається в змінній *Square */
int Best_Move(Board_Type Board, Square_Type Player, int *Square, int Move_Nbr,
int Alpha, int Beta) {
int Best_Square = -1;
int Moves = 0;
int I;
Move_Heuristic_Type Move_Heuristic[Squares];
Total_Nodes++;
/* Знаходить евристику всіх ходів і сортує ходи по спаданню ціни */
for (I = 0; I < Squares; I++) {
if (Board[I] == Empty) {
int Heuristic;
int J;
Play(Board, I, Player);
Heuristic = Evaluate(Board, Player);
Play(Board, I, Empty);
for (J = Moves-1; J >= 0 &&
Move_Heuristic[J].Heuristic < Heuristic; J--) {
Move_Heuristic[J + 1].Heuristic = Move_Heuristic[J].Heuristic;
Move_Heuristic[J + 1].Square = Move_Heuristic[J].Square;
}
Move_Heuristic[J + 1].Heuristic = Heuristic;
Move_Heuristic[J + 1].Square = I;
Moves++;
}
|
|
|
}
for (I = 0; I < Moves; I++) {
int Score;
int Sq = Move_Heuristic[I].Square;
Square_Type W;
/* Виконання ходу та визначення його ціни */
Play(Board, Sq, Player);
W = Winner(Board);
if (W == 'X')
Score = (Maximum_Moves + 1) - Move_Nbr;
else if (W == 'O')
Score = Move_Nbr - (Maximum_Moves + 1);
else if (W == 'C')
Score = 0;
else
Score = Best_Move(Board, Other(Player), Square, Move_Nbr + 1,
Alpha, Beta);
Play(Board, Sq, Empty);
if (Player == 'X') {
if (Score >= Beta) {
*Square = Sq;
return Score;
} else if (Score > Alpha) {
Alpha = Score;
Best_Square = Sq;
}
} else {
if (Score <= Alpha) {
*Square = Sq;
return Score;
} else if (Score < Beta) {
Beta = Score;
Best_Square = Sq;
}
}
}
*Square = Best_Square;
if (Player == 'X')
return Alpha;
else
return Beta;
}
/* Виводить текст повідомлення за ціною ходу‚ яка повертається Best_Move */
void Describe(int Score) {
if (Score < 0)
printf("\tВи маєте гарантований виграш.\n");
else if (Score == 0)
printf("\tЯ можу гарантувати Вам нічию.\n");
else
printf("\tВиграш гарантує хід %d.\n",
Maximum_Moves - Score + 1);
}
/* Визначає хід людини або комп’ютера */
void Move(Board_Type Board, Square_Type Player, int Move_Nbr) {
int Square;
if (Player == 'X') {
Total_Nodes = 0;
Describe(Best_Move(Board, 'X', &Square, Move_Nbr, -Infinity, Infinity));
printf("\t%d вершина перевірена.\n", Total_Nodes);
Play(Board, Square, 'X');
printf("\tХўд #%d - X ходить на %d\n", Move_Nbr, Square + 1);
} else {
do {
printf("\tХўд #%d - Куди ходить O? ", Move_Nbr);
scanf("%d", &Square);
Square--;
} while (Board[Square]!= ' ');
Play(Board, Square, 'O');
}
}
/* Реалізація гри */
void Game() {
Square_Type Player;
char Answer[String_Length];
Board_Type Board;
int Move_Nbr = 1;
Initialize(Board);
printf("\n\tХочете ходити першим? ");
scanf("%s", Answer);
if (toupper(Answer[0]) == 'Y')
Player = 'O';
else
Player = 'X';
while(Winner(Board) == ' ') {
Print(Board);
Move(Board, Player, Move_Nbr);
Player = Other(Player);
Move_Nbr++;
}
Print(Board);
if (Winner(Board)!= 'C')
printf("\t%c виграли!\n", Winner(Board));
else
printf("\tНiчия.\n");
}
int main() {
char Answer[String_Length];
clrscr();
printf("\tГра у хрестики - нулики!\n\n");
printf("\tОзнайомтесь з нумерацією ігрового поля:\n");
printf("\t 1 | 2 | 3\n");
printf("\t---+---+---\n");
printf("\t 4 | 5 | 6\n");
printf("\t---+---+---\n");
printf("\t 7 | 8 | 9\n");
printf("\n");
printf("\tКомп'ютер грає X, ви граєте O.\n");
do {
Game();
printf("\n\tХочете продовжувати? ");
scanf("%s", Answer);
} while (toupper(Answer[0]) == 'Y');
}
