Вступ
Розділ 1. Гра “Хрестики - нулики”
Розділ 2. Методи та засоби розв'язку задачі
Розділ 3. Практична реалізація розв'язку задачі
Висновки
Список використаної літератури
Додаток А. Схема алгоритму процедури game
Додаток Б. Текст програми
Додаток В. Тест програми
Вступ
Мови програмування - це формальні мови зв'язку людини з машиною‚ призначені для опису даних та алгоритмів(програм) їх обробки на ЕОМ. Алгоритмічні мови‚ існують в наш час‚ поділяються на три великих класи: машинно-орієнтовані‚ процедурно-орієнтовані та проблемно-орієнтовані. До машинно-орієнтованих відносяться мови‚ в яких з однієї сторони явно виражений зв'язок з конкретною ЕОМ (структура команд‚ пам'яті‚ зовнішніх пристроїв)‚ а з другої - в мову введено елементи‚ які спрощують і автоматизують процес програмування (символьне позначення команд і комірок пам'яті‚ широке застосування звичних для людини позначень і т.д.). Процедурно-орієнтовані мови є вищим рівнем мов програмування, призначені для різних сфер застосування ЕОМ і враховують специфіку їх застосування.
Особливий клас утворюють мови‚ призначені для опису спеціальних проблем і які носять назву проблемно-орієнтованих мов. Програма, реалізована на такій мові програмування містять крім опису умови задачі вказівку розв'язати задачу даного класу. Прикладом такої мови є, наприклад, мова Stress‚ яка призначається для опису задач конструювання. Програма на цій мові містить ряд загальних характеристик системи (розмірності‚ число вершин та ін.) і дані‚ а також вказівку - розв'язати задачу і представити певні дані у вигляді деякої таблиці.
Програмна реалізація курсового проекту здійснювалась на алгоритмічній мові С.

Розділ 1. Гра “хрестики - нулики”
Гра «хрестики-нулики» (англійська назва tic-tac-toe) є однією з найпростіших та найпоширеніших ігор. Грають два гравці. Ігрове поле представляє собою таблицю пустих кліток розмірності 3 ? 3 (див. мал. 1.1).

Гравці по черзі ставлять у пусті клітки значки «хрестик» та «нулик». Виграє той гравець‚ котрий першим побудує три однакових значки у ряд по горизонталі‚ вертикалі чи діагоналі.

Завдяки простоті алгоритму гра «хрестики-нулики» є чи не найбільш часто програмвованою грою. Через відсутність складних графічних елементів та простоту інтерфейсу гра може бути реалізована практично на довільній мові програмування‚ починаючи від зичайного GW-Бейсіка і закінчуючи Visual Basic чи Delphi.

Розділ 2. Методи та засоби розв'язку задачі

Іграми займається спеціальна галузь математики‚ яка носить назву теорії ігор - теорія математичних моделей прийняття оптимальних рішень в умовах конфлікту.

Теорія ігор як математична дисципліна зародилась одночасно з теорією ймовірності в середині 17 ст.‚ але на протязі майже 300 років не розвивалась. Першою суттєвою працею з теорії ігор слід вважати статтю Джона фон Неймана “До теорії статистичних ігор”‚ а з виходом монографії американських математиків Дж. фон Неймана та О.Моргенштерна “Теорія ігор та економічна поведінка” теорія ігор сформувалась як самостійна математична дисципліна. На відміну від інших галузей математики‚ корі мають фізичне або фізико-технічне походження‚ теорія ігор з самого початку свого розвитку була направлена на розв'язування задач‚ що виникають в економіці (а саме‚ в конкурентній економіці).надалі ідеї‚ методи та результати теорії ігор стали застосовувати і в інших областях знань‚ котрі мають справу з конфліктами.

Гра у “хрестики-нулики” відноситься до антагоністичних матричних ігор. В іграх такого типу обидва гравці мають скінчене число чистих стратегій. При виборі стратегій в матричних іграх гравцям доцільно керуватися принципом максиміна.

Реалізація гри в “хрестики-нулики” здійснена в середовищі програмування Turbo C++ версії 3.0.

Ігрове поле моделюється квадратною матрицею третього порядку. Для зручності виконання ходів ігрові поля пронумеровані цифрами від 1 до 9. (див. мал. 2.1). Комп'ютер (гравець 1) завжди грає “хрестиками”‚ а людина (гравець 2) -“нулики”. Перемагає той з гравців‚ котрому першому вдасться вибудувати рядок з трьох ігрових фігур (“хрестиків” чи “нуликів”) по горизонталі‚ вертикалі чи діагоналі. “Виграшні” комбінації у відповідності до вибраної нумерації полів мають такий вигляд:

(1‚ 2‚ 3) (4‚ 5‚ 6) (7‚ 8‚ 9)

(1‚ 4‚ 7) (2‚ 5‚ 8) (3‚ 6‚ 9)

(1‚ 5‚ 9) (3‚ 5‚ 7)

Всього є вісім виграшних комбінацій. Один з прикладів виграшу одного з гравців представлено на мал. 2.2 (відповідає комбінації (1‚ 5‚ 9).

Вибір стратегії комп'ютером здійснюється евристичним методом за допомогою методу мінімаксу. Після кожного ходу людини комп'ютер прораховує ціну всіх ходів‚які він ще може зробити‚ сортує їх у порядку спадання цінності і вибирає хід з максимальною ціною. Щодо вибору стратегії гри гравцем-людиною то цей вибір може здійснюватись як інтуїтивним так і евристичним методом (якщо людина ним володіє).

Розділ 3. Практична реалізація розв'язку задачі

Практична реалізація гри в «хрестики-нулики» здійснена у середовищі програмування Turbo C++ версії 3.0.

Програма гри складається з наступних процедур.

Процедура Initialize - в циклі очищує всі клітки ігрового поля (записує в них значення змінної Empty).

Процедура Winner - після кожного ходу одного з гравців перевіряє‚ чи виявлено переможця. У разі виявлення переможця повертає через змінну Possible_Winner переможця. У випадку нічиєї повертає значення `c'‚ у випадку якщо гра незавершена - повертає Empty.

Процедура Print - здійснює вивід зображення ігрового поля на дисплей після кожного ходу одного з гравців.

Процедура Evaluate - здійснює евристичний аналіз пооного ходу комп'ютера. Використовується процедурою Best_Move.

Процедура Best_Move - здійснює перегляд можливих ходів для комп'ютера‚ з допомогою процедури Evaluate виконує оцінку кожного ходу‚ впорядковує ходи за спаданням оцінки і вибирає найкращий можливий хід для комп'ютера.

Процедура Play - виконує хід на ігровому полі.

Процедура Describe - виводить текст повідомлення за ціною ходу‚ виробленою процедурою Best_Move. Якщо ціна ходу від'ємна, то виводиться повідомлення «Ви маєте гарантований виграш»‚ якщо ж ціна ходу дорівнює нулю‚ то виводиться повідомлення «Я гарантувати Вам нічию».

Процедура Move - визначає‚ кому належить зроблений хід - людині (Player == 'O') чи комп'ютеру (Player == 'X'). Якщо хід зроблено комп'ютером‚ то відбувається виклик процедури Best_Move‚ яка здійснює вибір найкращого ходу для комп'ютера‚ виклик процедури Play‚ яка виконує цей хід і виводиться повідомлення «Хід __ Х ходить на ___». Якщо ж хід повинна зробити людина‚ то виводить запит «Хід __ Куди ходить О?» і після вводу номера ігрового поля‚ на яке ходить людина викликається процедура Play‚ котра і виконує хід на вибране поле.

Процедура Game - реалізує процес гри. Початково викликається процедура ‚ котра очищує ігрове поле від можливих попередніх ходів. Потім виводиться повідомлення «Хочете ходити першим?» і у випадку ствердної відповіді змінній Player присвоюється значення “О”‚ у протилежному випадку значення “Х”. Після цього у циклі з умовою Winner(Board) == ' ') здійснюється послідовний виклик процедур Print(Board) та Move(Board, Player, Move_Nbr)‚ які‚ власне‚ і реалізують саму гру. При виході з циклу аналізується значення змінної Winner(Board) і якщо воно не дорівнює значенню 'C' (гра була результативною)‚ то виводиться повідомлення про переможця‚ в протилежному випадку виводиться повідомлення «Нічия!».

Головна процедура (main) програми виводить на дисплей зображення ігрового поля та нумерацію полів і повідомляє «Комп'ютер грає X, ви граєте O». Після цього здійснюється циклічний виклик процедури Game‚ яка виконується до тих пір гравець-людина у відповідь на повідомлення «Хочете продовжувати?» дає ствердну відповідь (Y або y).

Висновки
Завершивши роботу над курсовим проектом можна зробити висновок про те, що мені вдалося досягти своєї мети і розробити програму комп'ютерної гри «хрестики-нулики». За допомогою засобів алгоритмічної мови C++ було створено програму Tic_Tac‚ яка дозволяє людині грати у гру «хрестики-нулики» з комп'ютером. Використання засобів процедурного програмування дало змогу досить просто справитись з поставленою задачею.

Розробка даної програми дала мені змогу оволодіти основними засобами програмування на алгоритмічній мові С++ та здобути практичні навички розробки програм з використанням середовища програмування Turbo C++ версії 3.0 фірми Borland International.

Використання мови С++ не дало змогу створити гнучкий графічний інтерфейс для поставленої задачі‚ чого можна було досягнути‚ використавши засоби візуального програмування. Однак використані засоби мови С++ дали змогу розробити програму‚ яка вірно функціонує.

Список використаної літератури

H. Вірт. Алгоритм + структура даних = програма. М., Мир. 1985. 406 с.

А. Ахо‚ Дж. Хопкрофт‚ Дж. Ульман. Построение и аналих вычислительных алгоритмов. М.‚ Мир. 1979. 536 с.

В.С. Проценко‚ П.Й. Чаленко‚ А.Б. Ставровський. Техніка програмування мовою Сі. К.‚ “Либідь”. 1993. 223 с.

М.И. Болски. Язык программирования Си. М.‚ Мир. 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 }

};

/* Масив, який використовується в евристичній формулі для кожного ходу */

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) %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