Гра Хрестики-нулики

Зміст

Вступ

Розділ 1. Гра “Хрестики - нулики”

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

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

Висновки

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

Додаток А. Схема алгоритму процедури game

Додаток Б. Текст програми

Додаток В. Тест програми

Вступ

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

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

Програмна реалізація курсового проекту здійснювалась на алгоритмічній мові С.

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

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