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

Зміст

 

Вступ

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

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

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

Висновки

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

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

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

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

Вступ

 

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

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

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

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

 

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

 

	Мал. 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).

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