Размещено на http://www.allbest.ru/

Размещено на http://www.allbest.ru/

Курсовой проект

Моделювання ігрової ситуації «Доміно»

Анотація

Курсовий проект присвячений розробці евристичного алгоритму для розв'язання ігрової ситуації „Доміно”.

На основі аналізу предметної області запропоновано оціночну функцію, яка забезпечує вибір високоефективних ходів, що підтверджують результати іспитів розробленої ігрової програми.

Програмну реалізація алгоритму здійснено мовою програмування високого рівня C#, яка має зручні засоби для створення, зручний графічний інтерфейс, щоб написати програму так, щоб було нескладно зрозуміти її текст.

Вступ

евристичний алгоритм програмна реалізація

Ефективне розв'язання логічних задач, які використовують режим гри людини з комп'ютером забезпечується з використанням систем штучного інтелекту, які базуються на евристичних методах пошуку рішень.

Гра доміно є логічною грою, в процесі якої вибудовується ланцюг кісточок («кісток», «каменів»), що стикаються половинками з однаковою кількістю очок.

Кісточки доміно пішли від всім відомих гральних кісток. Стандартний набір доміно включає в себе 28 кісточок. Кісточка доміно представляє собою прямокутну плитку. Її лицьова сторона розділена лінією на дві квадратні частини. Кожна частина містить від нуля до шести точок. У спеціалізованих наборах доміно можливу кількість точок може доходити до дев'яти, дванадцяти, п'ятнадцяти або вісімнадцяти.

Коріння гри в доміно йдуть в Індію і Китай, саме там з'явилися кістки у вигляді пластинок. Точки на кістках в китайському доміно різнокольорові (білі та червоні), в наборі немає пустушок. У XVIII столітті гра була привезена до Італії і видозмінена. Сучасне доміно також тісно пов'язано з грою в кості. Дві половинки кісточки доміно - це одна з можливих комбінацій, що випадають при кидку двох кісток. Вважається, що доміно була названа на честь чорно-білих маскарадних костюмів, які, в свою чергу, походять від шати монахів-домініканців, що носили білі плащі з чорними капюшонами. Метою проектування курсової роботи є створення комп'ютерної програми, яка б успішно грала у „Доміно” з людиною. Об'єктом даного курсового проекту є вивчення технологій застосування штучного інтелекту для розв'зання інтелектуальних ігрових задач, що не мають чітко визначених виграшних стратегій. Предметом проектування є комп'ютерне моделювання ігрової стуації „Доміно”.

1. Аналіз предметної області

Доміно - є відомою і дуже популярною грою, що базується на розв'язанні дедуктивної задачі.

Суть гри полягає в наступному. Грають від двох до чотирьох чоловік. Для двох здають по сім доміношек, для трьох або чотирьох - по п'ять. Решта розміщуються в закритому резерві («базарі»). Починає гравець, у якого на руках перебуває «дубль шість» або «дубль нуль» (0-0), залежно від правил гри. Наступні гравці виставляють камені з відповідними очками (6-1; 6-2; 6-3 ... або 0-1; 0-2; 0-3 ...). Якщо підходящих каменів немає, то доводиться добирати з резерву.

Якщо ні в кого з гравців немає на руках дубля 6-6, можна почати гру дублем 5-5. Якщо ж на руках немає жодного дубля, починають з каменя, що має найбільшу кількість (наприклад, 6-5).

Гра закінчується, коли один з гравців викладе останній камінь. Можливо закінчення гри «рибою» - так називається блокування викладення, коли на руках ще є каміння, але доповісти нічого. Якщо вам випадає кістка в два нулі, вам нараховується 25 очок. Закінчує гру той, хто ходив останнім.

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

1.1 Існуючі реалізації

На сьогоднішній день існує дуже велика кількість різноманітних розробок на тему "Доміно".

Нижче представлені деякі розробки гри доміно:

Ultimate Dominoes - гра для всієї сім`ї

Системні вимоги:

* Windows XP

* 300 МГц Pentium 2 або еквівалент

* 64 МБ оперативної пам'яті

* DirectX

Ще однією розробкою даної теми є «Домино любимая игра»

Особливості гри:

Зручна навчальна система

Змінний зовнішній вигляд кісточок і столу

Гра не має вікових обмежень і буде цікава всім і кожному

Мінімальні системні вимоги:

Windows XP SP2 (pyc.)

Pentium III 800 МГц

256Мб ОЗУ

Directx 9-сумісна 3D відеокарта

DirectX 9-сумісна звукова карта

100 Мб вільного місця на жорсткому диску

24x CD-ROM, Клавіатура, Миша

Доміно є досить давньою грою, яка на сьогоднішній день не втратила своєї актуальності, тому розробка такої гри, яка потребує найменше ресурсів комп'ютера є актуальною.

2. Обґрунтування методу розв'язання задачі

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

Отже, суть оціночної функції - оцінити наскільки вигідно нам вибрати з можливих в даний момент, ту чи іншу доміношку. Очевидно нам буває вигідно це зробити або для оборони, щоб залишити в себе найбільшу різноманітність кісток, або для зменшення результату загальної ваги доміно шок, що є в нього на руках.

Щоб написати алгоритм гри в “Доміно” потрібно створити оціночну функцію, яка буде рахувати кількість можливих доміношек і передаватиме їх в альфа-бета алгоритм, а потім за принципом міні-макс альфа бета алгоритм буде вибирати максимальне значення ваги доміношки і передавати його далі, після кожного ходу оціночна функція буде передавати значення доміношек в альфа-бета алгоритм.А після закінчення кожної партії, буде формуватися наступна підвершина альфа-бета графа, і буде перевірятись чи вага всіх доміношек не перевищує 100. Якщо вага доміношек буде рівна або більше ста, то буде визначено переможця гри і гру буде закінчено.

Стратегія гри залежить від таких факторів: значення виданих доміношек, хто перший ходить, врахування помилкових ходів та інші.

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

2.1 Загальні відомості про альфа-бета алгоритм

Альфа-бета відсічення (англ. Alpha-beta pruning) - це алгоритм пошуку, який прагне скоротити кількість вузлів, які оцінюються в дереві пошуку алгоритмом мінімакс. Цей алгоритм призначений для антагоністичних ігор і використовується для машинної гри (в шахах, го та інших). В основі алгоритму лежить ідея, що оцінювання гілки дерева пошуку може бути достроково припинено (без обчислення всіх значень оціночної функції), якщо було знайдено, що для цієї гілки значення оціночної функції в будь-якому випадку гірше, ніж обчислена для попередньої гілки. Альфа-бета відсікання є оптимізацією, тому що результати роботи оптимізується алгоритму не змінюються.

Оптимізація Мінімакс

Перевага альфа-бета відсікання фактично полягає в тому, що деякі з гілок підрівнів дерева пошуку можуть бути виключені після того, як хоча б одна з гілок рівня розглянута повністю. Так як відсікання відбуваються на кожному рівні вкладеності (крім останнього), ефект може бути досить значним. На ефективність методу суттєво впливає попереднє сортування варіантів (без перебору або з перебором на меншу глибину) - при сортуванні чим більше на початку розглянуто «хороших" варіантів, тим більше «поганих» гілок може бути відсічене без вичерпного аналізу.

Рисунок 2.1 - Ілюстрація альфа-бета алгоритму

3. Розробка оціночної функції

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

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

Досліджуючи гру доміно можна помітити, що майже кожна кісточка (дві клітини) доміно представляє собою своєрідний "перехідник" від однієї масті (0, 1, 2, 3, 4, 5, 6) до іншої, тому тут вони тісно взаємопов'язані.

Якщо згідно з правилами доміно з'єднати всі 28 кісточок в пряму лінію, то на кінцях столу буде обов'язково знаходитися одна і та ж масть. Це обумовлено тим, що кожна масть присутня у парному числі (8) клітин. Тому в цій грі можна виявити корисні евристичні закономірності, справедливі не абсолютно, а лише з певною (але досить високою) ймовірністю. Розглянемо ряд таких тактичних і стратегічних принципів.

Якщо гравець не має можливості виставити камінь ні до одного з країв "столу", він пропускає хід. Гра закінчується, коли один з її учасників першим встигає виставити всі свої кісточки. Зрозуміло, чим частіше конкретний гравець потрапляє "в прокат", тим менше у нього шансів першим виставити всі свої камені. При пошуку ефективних способів гри доцільно виділити дві прості (чисті) стратегії - оборонну і наступальну.

У першій гравець ходить так, щоб на кістках що у нього залишилися було найбільше розмаїття мастей. Дана стратегія дозволяє мінімізувати ймовірність потрапляння в "прокат" в майбутньому, при цьому важливо враховувати, те що після кожного закінчення партії на суму того хто виграв нараховуються вага тих доміно шок, які залишились в колоді того хто програв. Тому важливо враховувати вагу доміношки, при тому коли її викидати. Наприклад, якшо є кілька можливих доміно шок, якими можна походити, то потрібно вибирати з них, ту яка має більшу вагу, тоді меша ймовірність того, що при програші однієї партії гри можна зразу програти всю гру. Адже гра ведеться до 100 очок, тому є шанс у наступній партії виправити ситуацію. Тому для гри доміно можна передбачити оціночну функцію яка буде рахувати кількість можливих доміношек, при даному розкладі і потім буде передавати ці доміношки в альфа-бета алгоритм, який за принципом міні-макс буде визначати найбільш оптимальну доміношку для ходу в даній ситуації.

4. Розробка програмної частини

Правильне і конкретизоване моделювання ігрової ситуації гри «Доміно» дало можливість розробити програмну частину, в якій описується основний алгоритм роботи програми, а також наводиться блок-схема цього алгоритму.

Блок-схема алгоритму гри «Доміно» приведена на рисунку 4.1

Для кращого розуміння представленої блок-схеми, нижче приводиться детальний опис, кожного із вагомих блоків:

1. Програма запускається зразу з можливістю вибрати нову гру, рівень складності і допомогу.

2. Після вибраних параметрів для комп'ютера і гравця рандомно вибираються по сім доміношок.

3 Компютер по оптимальних параметрах вибирає хто буде робити перший хід. Після цього починається 1-ша партія гри.

4. В процесі гри хід за ходом визначається хто буде ходити і чи треба брати доміношки з базару.

5. Коли один з гравців викине всі доміношки, то визначається переможець в даній партії і підраховується кількість набраних ним очок, по тих доміношках які залишились в переможеного в даній партії. Також партія може бути закінчена, коли доміношки ще є на руках, але походити нема чим. Тоді партія закінчується «рибою».

6. Якщо після значення рахунку гравця або комп'ютера менше 100, то гра продовжується і починається нова партія.

7. Гра закінчується коли, або комп'ютер, або гравець набрали суму яка рівна або перевищує 100 очок.

Рисунок 4.1 - Блок-схема алгоритму гри «Доміно»

Додатки

Додаток А

(обов'язковий)

Міністерство освіти і науки, молоді та спорту України

Вінницький національний технічний університет

Інститут інформаційних технологій та комп'ютерної інженерії

ЗАТВЕРДЖУЮ

Зав. каф. КН, д.т.н., проф.

_____________ С.І. Перевозніков

«__» _____________ 2011 р.

ТЕХНІЧНЕ ЗАВДАННЯ

На моделювання ігрової ситуації «Доміно»

1 Найменування й область застосування

Робоча назва розроблюваного програмного комплексу (ПК) - «Моделювання ігрової ситуації «Доміно». Програма носить розважальний характер і може використовуватися для розвитку логічних здібностей.

2 Підстави для розробки

Завдання на курсове проектування, протокол засідання кафедри КН №2 від р.

3 Мета та призначення розробки

Програма призначена для демонстрації принципів використання евристичної функції для розв'язаання інтелектуальних задач (у даному випадку - гри Доміно).

4 Вимоги до програмного забезпечення

4.1 Вимоги до функціональних характеристик:

- режим гри „людина - комп'ютер”;

- можливість вибору режиму складності гри;

- можливість можливість взяття доміношок зі складу;

- інформація про правила гри.

- Формування поточної ситуації;

- Виведення оцінок можливих ходів;

- Вибір слідкуючої ситуації з урахуванням оцінки та стратегії гри;

- Виведення результату гри.

4.2 Вимоги до програмного середовища

Визначимо основні вимоги до мови програмування та програмного середовища, яке буде використана у процесі створення програмного забезпечення. Отже, до мови програмування висуваються такі вимоги:

- Об'єктно орієнтована мова;

- максимально автоматизована, та автоматична генерація коду програми;

- зручний інтерфейс;

- ефективне використання можливостей для роботи із графікою.

Розробка програмного забезпечення при виконанні курсового проекту здійснюється мовою програмування С#, що добре підходить для створення зручного інтерфейсу користувача.

4.3 Вимоги до інформаційного забезпечення

- інтерфейс ПЗ повинний:

відображати всю інформацію про хід гри;

б) надавати можливість вибору першого ходу гравцю або комп'ютеру, перший хід визначається правилами гри «Доміно».

в) надавати можливість завершення поточної гри і початку наступної.

5 Вимоги до технічного забезпечення

Робота повинна виконуватися на комп'ютерах, які знаходяться в робочих аудиторіях і підтримують вимоги щодо технічного забезпечення оболонки С#.

Додаток Б

Бібліографічні дослідження

1. Нильсон Н. Искусственный интеллект.- Москва: Мир, 2003.- 280 с.

В даній книзі детально описані основні положення штучного інтелекту. Детально описано методику представлення задачі у просторі станів, та алгоритми пошуку у просторі станів з теоретичним обґрунтуванням.

Покладаючись на дану книгу, було описано основи штучного інтелекту, його практичне використання в програмних проектах.

2. В.І. Месюра, Л.М. Ваховська Методичні вказівки до виконання курсового проекту з дисципліни “Основи проектування систем штучного інтелекту” для студентів напрямку підготовки 0804 - “Комп'ютерні науки”. - Вінниця: ВНТУ, 2004.

Посібник містить рекомендації по виконанню курсового проекту з дисципліни “Основи проектування систем штучного інтелекту”.

3. Месюра В.І., Ваховська Л.М. Основи проектування систем штучного інтелекту. Лабораторний практикум. Частина 1. Способи подання задач і пошуку розв'язків. Лабораторний практикум. - Вінниця: ВНТУ, 2009. - 108 с.

Посібник містить теоретичний матеріал і приклади розв'язування практичних задач з подання та пошуку розв'язків інтелектуальних задач.

Размещено на Allbest