Гра Хрестики-нулики (стр. 2 из 2)
Розробка даної програми дала мені змогу оволодіти основними засобами програмування на алгоритмічній мові С++ та здобути практичні навички розробки програм з використанням середовища програмування TurboC++ версії 3.0 фірми Borland International.
Використання мови С++ не дало змогу створити гнучкий графічний інтерфейс для поставленої задачі‚ чого можна було досягнути‚ використавши засоби візуального програмування. Однак використані засоби мови С++ дали змогу розробити програму‚ яка вірно функціонує.
Список використаної літератури
1. H. Вірт. Алгоритм + структура даних = програма. М., Мир. 1985. 406 с.
2. А. Ахо‚ Дж. Хопкрофт‚ Дж. Ульман. Построение и аналих вычислительных алгоритмов. М.‚ Мир. 1979. 536 с.
3. В.С. Проценко‚ П.Й. Чаленко‚ А.Б. Ставровський. Техніка програмування мовою Сі. К.‚ “Либідь”. 1993. 223 с.
4. М.И. Болски. Язык программирования Си. М.‚ Мир. 1986. 96 с.
Додаток А. Схема алгоритму процедури Game
Додаток Б. Текст програми
#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 }
};
/* Масив, який використовується в евристичній формулі для кожного ходу */
constintHeuristic_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');
}
Додаток В. Тест програми
Тест проводився на робочій станції з наступною конфігурацією:
- Pentium 166
- 32 Mb RAM
- SyncMaster 17Glsi
- S3 Trio64V+
- Windows 98
Компілятор Turbo C++ p був запущений у вікні Windows.
Малюнок 1
Малюнок 2
Малюнок 3