Головна > Дизайн > Деякі ідеї написання штучного інтелекту для шахів. Шах та мат, штучний інтелект: чому нас вчить досвід Гаррі Каспарова Навчальний проект шахи та штучний інтелект


Деякі ідеї написання штучного інтелекту для шахів. Шах та мат, штучний інтелект: чому нас вчить досвід Гаррі Каспарова Навчальний проект шахи та штучний інтелект




Рік тому програма AlphaGo сенсаційно обіграла найсильнішого у світі гравця в го, а тепер штучний інтелект AlphaZero розгромив найсильніший за рейтингом шаховий двигун.

Stockfish, який використовують для домашньої підготовки більшість гравців, переможець Чемпіонату TCEC 2016 року та Чемпіонату Chess.com серед комп'ютерних програм 2017 року виявився явно слабшим. У матчі зі 100 партій AlphaZero здобув 28 перемог при 72 нічиїх і жодного разу не програв.

До речі, AlphaZero витратив лише чотири години на «вивчення» шахів. Вибачте, люди, але вам за ним не наздогнати.

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

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

Поки що команда програмістів мовчить. Вони не дали коментарів Chess.com, посилаючись на те, що доповідь «поки знаходиться на розгляді», але тут ви можете прочитати його повний текст. До дослідницької групи входить Деміс Хасабіс, кандидат у майстри з Англії та співзасновник DeepMind (придбаний Google у 2014). Хасабіс, який брав участь у турнірі тандемів ProBiz на відкритті London Chess Classic, зараз перебуває на конференції Neural Information Processing Systems (Нейронні системи обробки інформації) у Каліфорнії, як співавтора доповіді на іншу тему.

Зате з Chess.com охоче поділився своїми судженнями шахіст, який має великий особистий досвід гри проти шахових комп'ютерів. МГ Гаррі Каспаров не здивований, що компанія DeepMind перейшла від го до шахів.

"Це помітне досягнення, хоча воно і було очікуване після AlphaGo", - заявив він Chess.com. «Воно наближається до "типу-Б", людиноподібного підходу до шахів, яким Клон Шеннон та Алан Т'юрінг мріяли замінити суцільний перебір».

Подібно до людини, AlphaZero розглядає менше позицій, ніж її попередниці. У звіті заявлено, що вона оцінює «всього» 80 тисяч позицій за секунду порівняно з 70 мільйонами за секунду Stockfish.

МГ Петер-Хайне Нільсен, багаторічний секундант чемпіона світу МГ ​​Магнуса Карлсена, відкрив своє захоплення, яке зближує його з президентом ФІДЕ: інопланетян. Він заявив Chess.com: «Прочитавши доповідь і, особливо, переглянувши партії, я подумав: „Мені завжди було цікаво, що було б, якби розумніший вигляд висадився на нашій планеті і показав нам своє мистецтво шахової гри. Здається, тепер я знаю, як це.

Ми також дізналися про значущість переваги виступу принаймні для штучного інтелекту. 25 із 28 перемог AlphaZero здобув білими (хоча результат +3=47-0 чорними проти Stockfish, чий рейтинг перевищує 3400, також непоганий).

У звіті показано і як часто двигун вибирав ті чи інші дебюти в міру навчання. Вибачте, любителі староіндійського захисту, але ви не у фаворі. Інтерес до французького захисту також згас з часом, а ось прагнення грати ферзевий гамбіт і, особливо, англійський початок лише зростав.

Що б ви зробили на місці невідомої втоми істоти, яка щойно освоїла гру з 1400-річною історією? Взялися б за іншу. Після матчу зі Stockfish програма AlphaZero витратила на навчання всього дві години і перемогла Elmo, найсильнішого з комп'ютерних двигунів для гри в сьоги.

Застосування цієї інноваційної програми, що самонавчається, зрозуміло, не обмежена іграми.

"Завжди вважалося, що в шахах від машини потрібно занадто багато емпіричних знань, щоб ті могли грати сильно "з нуля", взагалі не використовуючи людські знання", - сказав Каспаров. "Звичайно, мені буде цікаво подивитися, що ми зможемо дізнатися про шахів" За допомогою AlphaZero, який відкриває величезні перспективи машинного навчання в цілому-машини можуть знаходити закономірності, недоступні для людей. Очевидно, що наслідки простягаються далеко за межі шахів та інших ігор. - Це інструмент, що змінює світ».

Журналісти Chess.com опитали вісім із десяти учасників турніру в Лондоні про їхнє ставлення до матчу програм. Відео з інтерв'ю буде розміщено на сайті пізніше.

Найбільше різко критикував умови матчу МГ Хікару Накамура. Зараз триває гаряча дискусія про обчислювальну потужність противників, але Накамура вважає, що важливіше було інше.

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

"Я впевнений, що сам Господь бог не набрав би проти Stockfish 75 відсотків очок білими без будь-якої фори", - прокоментував він результат AlphaZero білими: 25 перемог та 25 нічиїх.

МГ Ларрі Кауфман, провідний шаховий консультант двигуна Komodo, сподівається побачити, наскільки добре працює нова програма на персональних комп'ютерах, не користуючись обчислювальними потужностями Google. Він також повторив висловлені Накамурою заперечення щодо того, що Stockfish грав без своїх звичайних дебютних знань.

«Звичайно, це майже неймовірно», сказав він, - «так, я чув про досягнення AlphaGo Zero у грі і очікував, що станеться щось подібне, враховуючи, що в команді розробників є шахіст Деміс Хасабіс. Однак, незрозуміло, чи зможе програма AlphaZero грати в шахи на звичайному комп'ютері, і наскільки добре це вийде. Можливо, сучасна перевага шахових двигунів, що використовують мінімаксну функцію, наближається до кінця, але поки що проголошувати це занадто рано. Варто зазначити, що за час навчання AlphaZero де-факто створила власну дебютну книгу, тому було б справедливіше використовувати її проти движка з гарною дебютною книгою».

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

"[Це] сучасний штучний інтелект", - сказав гросмейстер. «Він іде від чогось на зразок шахів до проблем, гідних нобелівських премій і навіть більшого. Думаю, нам пощастило, що вони вирішили витратити чотири години на шахи, але наслідки цього відкриття значно значніші».

Надіслати свою гарну роботу до бази знань просто. Використовуйте форму нижче

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

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

Розробкапрограмногомодуляштучногоінтелектудляігрившахи

шаховий комп'ютерний інтелект алгоритм

  • Вступ

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

* Є спільна впевненість, що завдання має відношення до проблеми штучного інтелекту, тому що шахи вважаються найінтелектуальнішою грою

* Існує об'єктивний критерій зробленої роботи - сила шахової програми

* велика диференційованість цього критерію є можливість поступового вдосконалення програми.

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

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

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

Слабкість гри комп'ютерів полягала саме у зловживанні матеріалом та неможливості здійснити «абсолютний перебір» варіантів. У шахових книгах 70-80-х років можна зустріти чимало зразково-показових прикладів гри людей з машинами, коли майстер чи гросмейстер вигравав партію за допомогою гарних жертв фігур та пішаків. Секрет вже зрозумілий: для людського інтелекту, на відміну штучного, було очевидним домінування позиційних чинників над матеріальними саме у ті моменти, коли здійснювалися жертви матеріалу.

Йшли роки, зі зростанням швидкодії ЕОМ збільшувалася глибина розрахунку, і водночас удосконалювалися алгоритми, що поліпшують складання функцій оцінки позицій. І в другій половині 90-х років комп'ютери вже стали успішно змагатися з гросмейстерами екстра-класу. Епохальна для «шахових кібернетиків» подія сталася у травні 1997 року. Створений корпорацією IBM комп'ютер Deep Blue у матчі з 6 партій переміг Гаррі Каспарова. Комп'ютер був оснащений спеціальним шаховим чіпом, причому машина переглядала близько 200 млн. позицій на секунду. Корпорація IBM для свого проекту залучила багатьох гросмейстерів, використовувалися останні досягнення шахової теорії для створення якомога досконаліших алгоритмів. І ось, як уже зазначалося, у 90-ті роки шахові програми для настільних ПК стали витісняти спеціалізовані комп'ютери.

З кожним місяцем сила шахових програм і потужність комп'ютерів невблаганно збільшується, випереджаючи навіть найсміливіші припущення оптимістів. Ще років 12-15 тому міркування на тему «Коли машина зможе обігравати гросмейстера?» в основному зводилися до питання «А чи здатна вона це зробити в принципі?». І якщо відповідь «Зможе» все ж таки вдавалося отримати, то час оцінювався в проміжку 15-25 років.

Насправді ж спростувала й ці прогнози. Все сталося набагато швидше! Вже в середині 90-х виявилося, що синтез «ігрова програма + комп'ютер» здатний змагатися з гросмейстером.

Метою роботи є розробка та реалізація програмного модуля штучного інтелекту для гри шахи, що включає:

1. дослідження існуючих ігрових алгоритмів застосовних для гри шахи

2. розробка алгоритму поведінки комп'ютерного опонента

3. визначення параметрів алгоритму поведінки комп'ютерного опонента

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

5. порівняння розробленого програмного забезпечення з існуючими аналогами.

1 . Історіярозвиткушаховихпрограм

У 1951 році Алан Т'юрінг написав алгоритм, за допомогою якого машина могла б грати у шахи. Тільки на той час у ролі машини виступав сам винахідник. У тому ж 1951 р. математик Клод Шеннон пише свою першу статтю про програмування шахів. Він описував дві стратегії пошуку кращого ходу, обидві ґрунтуються на евристичній функції оцінки кінцевих точок:

* тип А - перебір всіх можливих ходів на фіксовану глибину, з викликом наприкінці оцінної функції (бо неможливо здійснити перебір остаточно)

* тип В - виконує лише вибіркові розширення певних рядків, використовуючи накопичені шахові знання, щоб підрізати нецікаві гілки

Перший комп'ютер був спроектований фон Нейманом для ведення складних розрахунків під час створення ядерної зброї. У 1950 році з'явився перший зразок, здатний робити 10000 операцій на секунду. Одним із перших експериментів з апаратом стало написання шахової програми, щоправда, шахи були нестандартні – на дошці 6*6 без слонів.

Через кілька років цей комп'ютер (MANIAC) зіграв з людьми: сильний шахіст здобув впевнену перемогу, а новачок програв за 23 ходи.

У 1957 році на IBM704 (42 кГц, 7 Кбайт-пам'ять) був реалізований тип програми на повній дошці, за участю всіх фігур. Машина рахувала 4 півходи за 8 хвилин. Рівень гри – аматорський.

У 1962 році Ньюел, Саймон і Шоу відкривають алгоритм, який отримав назву альфа-бета (alpha-beta), він давав результат не гірше, ніж повний перебір, не досліджуючи всіх варіантів. У ньому не були потрібні ніякі спеціальні шахові знання, і він міг бути застосований для вирішення будь-якої перебірної задачі. Суть алгоритму в тому, що в кожному рядку гри, для білих і чорних відслідковуються їх максимальні результати, і якщо в деякій точці чорні вже отримали результат, який зрівнявся з максимумом білих, досягнутим до цього, далі переривати немає сенсу. Коли перебір повернеться в точку, де було досягнуто максимум білих, результат все одно буде відкинутий. В основі всіх сучасних шахових програм лежить одна з удосконалених версій даного алгоритму.

Приблизно до 1973 року всі шахові програми були типу В. Вони головним чином ґрунтувалися на генераторах правдоподібних переміщень, відсікаючи статичною малоправдоподібною оцінкою. З появою більш потужних процесорів програмісти стали перемикатися на тип А. Першими були Teach і Chess4, це були програми «грубою сили», щойно вони досягали глибини 5 півходів середньої стадії гри, вони починали перемагати у змаганнях із програмами типу В.

У 1975 році Роберт Х'ят починає розробляти CrayBlitz, який довгий час був найшвидшою шахівницею і в період з 1983 по 1989 роки. - Світовим чемпіонам серед шахових програм. Він шукав приблизно 40-50 тис. позицій на секунду (1983 року), що для свого часу було великим досягненням.

У 1977 році Томпсон і Кондон із лабораторії Bell створюють перший спеціалізований шаховий комп'ютер. Основна ідея була в реалізації деяких частин шахової програми (генератора ходів, функції оцінки позиції, детектора шахів тощо) на апаратному рівні, що позбавляло програмних затримок у кожній позиції, не чекаючи збільшення потужності процесорів. Найкращі комп'ютери того часу могли досліджувати до 5 тисяч позицій за секунду, а машина Кена Томпсона, яку назвали Belle, обробляла 180 тисяч рядків за секунду. Belle міг продумувати позиції на 8-9 півходів наперед, що ставило його на рівень майстра. Він перемагав на багатьох комп'ютерних шахових турнірах. Але незважаючи на те, що спеціалізоване залізо набагато швидше, ніж звичайна машина, програма CrayBlitz на надсучасній тоді машині все одно грала краще.

У 90-х Річард Ленг, пишучий виключно на асемблері, зробив дуже сильну програму вибіркового пошуку Genius. До цього часу ця програма стабільно тримає 5-6 місце на світових комп'ютерних шахових чемпіонатах. Так само в 90-і роки стали сильно розвиватися шахі алгоритми, з'явилася евристика порожнього ходу (NullMove), вибіркове відсікання прикордонних гілок дерева перебору.

Окремо варто розглянути найвідомішу шахівницю, шаховий супер комп'ютер - Deep Blue. У 1987 році Deep Blue починалася як студентська розробка – цікаво було групі здатних студентів спробувати свої сили, та й тема для диплома відмінна. Прогрес технології дозволив зробити першу версію процесорів (названу ChipTest) дуже швидкими. Настала наступна, вдосконалена версія, названа Deep Thought. У цей момент групу помітив маркетинговий департамент фірми IBM і звернувся до неї із пропозицією, від якої неможливо було відмовитись. Результатом стали Deep Blue та Deep Blue II. Таким чином, Deep Blue II - це результат більш ніж 10 років роботи дуже здатної групи, в якій були як програмісти/залізничники, так і сильні гросмейстери. Фінансувалася вся робота фірмою IBM, таким чином група мала ресурси, які й не снилися академічним організаціям. Deep Blue II зроблена на основі потужного сервера RS/6000 фірми IBM. У сервері є 31 стандартних процесора; один оголошений головним, йому підпорядковуються 30 інших. До кожного «робочого» процесора підключено 16 спеціалізованих шахових процесора, таким чином є 480 шахових процесорів. Весь комплекс обробляв понад мільярд позицій на секунду.

11 травня 1997 року Deep Blue II здобув перемогу над чемпіоном світу з шахів Гарі Каспаровим у матчі з 6 партій. Після матчу з чемпіоном Deep Blue був розібраний.

Як видно, починаючи з найперших і закінчуючи найсучаснішими програмами, шахові програми будувалися на основі перебору можливих ходів, але були і спроби побудувати більш "інтелектуальні" алгоритми, відмінні від перебірного. Багато відомих шахісти намагалися розробити такі алгоритми, але результати не задовольняли вимогам. Наприклад, Ботвинник М.М., будучи чемпіоном світу і автором численних робіт з теорії шахів, понад 20 років займався створенням шахової програми, але програма так ніколи і не заграла.

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

2. Загальніпоняттятеоріїігор

2.1 Деревоможливихпозицій

Нехай задано кінцеве орієнтоване дерево G, безліч його вершин складено з двох непересікаючих підмножин B0 і B1 , а будь-якій вершині p B , яка не є початком ніякої ланки цього дерева, поставлене у відповідність дійсне число Oe (p) . Це визначає гру двох супротивників з повною інформацією. Вершини орієнтованого дерева G, що належать підмножині B0 називаються позиціями з ходом білих, а належать підмножині B1 - позиціями з ходом чорних; Ланки цього дерева називаються ходами білих або чорних залежно від того, якому з підмножин B0 або B1 належить їх початок. Якщо позиції p B поставлено у відповідність число Oe(p), вона називається заключною, а Oe(p) називається статичною оцінкою цієї позиції.

Орієнтоване дерево G називається деревом гри.

Згідно з визначенням для будь-якої позиції p B існує єдиний шлях L(p0 > p1, p1 > p2 , ..., pk > p ) з початком в корені p0 орієнтованого дерева Г і кінцем у розглянутій позиції, такий шлях називається партією, що призводить до позиції p.

Корінь p0 дерева гри G є виділеною позицією. Це позиція, запропонована програмі, і завдання полягає в тому, щоб знайти в ній найкращий хід. Для цього достатньо визначити Oep0 та Oepi для всіх позицій, які виходять із p0 за один хід. Визначення оцінки початкової позиції p0 виконується схемою повного перебору, а в теорії ігор цей алгоритм називається алгоритмом negamax.

Складність ігрового дерева обчислюється за формулою: w^d, де w-середня кількість можливих ходів, а d-глибина дерева.

Малюнок 1 - Дерево можливих позицій

2.2 Принципмінімаксу

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

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

Малюнок 2 - Пошук у дереві алгоритмом мінімакс

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

Цей алгоритм здійснює повний перебір усіх варіантів. Число розглянутих позицій оцінюватиметься як W у ступені D, де W – приблизна кількість ходів в одній позиції, D – глибина прорахунку. Для шахів W приблизно дорівнює 40, це означає, що рахуючи на глибину 4, ми повинні перебрати 40 4 = 2560 тис. позицій, а для глибини 5 - 10240 тис. позицій.

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

На малюнку 3 представлена ​​блок-схема алгоритму мінімакс на вибір кращого ходу, представлений алгоритм повертає кращий хід по оцінці, отриманої при більш глибокому аналізі. Блок-схема алгоритму пошуку оцінки в глибину представлена ​​малюнку 4.

Малюнок 3 - Блок-схема на вибір кращого ходу

Малюнок 4 - Блок-схема пошуку оцінки в глибину

При виклик алгоритму пошуку оцінки в глибину з дуже великою необхідною глибиною отримаємо оцінку при повному переборі всіх можливих ходів.

2.3 Методнегативногомаксимуму(NegaMax)

У даному алгоритмі статична оцінка позиції для однієї зі сторін, так само статична оцінка іншої сторони зі зворотним знаком.

Малюнок 5 - Метод негативного максимуму

2.4 Статичнаоцінкапозиціїіосновнівимогидооцінноїфункції

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

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

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

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

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

* позиційна - показує якість розташування фігур гравця

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

* відстеження кінця гри - у випадки виграшу (взяття короля суперника), має давати максимальну оцінку, зазвичай + нескінченність, у випадки програшу (втрати короля), має повертати мінімальну оцінку, зазвичай - нескінченність

Для гри шахи треба враховувати зміну оцінки позиції залежно від стадії партії.

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

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

Істотне значення має значення обраної характеристики. Важливість визначається шляхом домноження обраної характеристики на відповідний коефіцієнт. Цей коефіцієнт повинен мати статистичне обґрунтування.

Отже, оцінну функцію можна представити у такому вигляді:

F(p) - оцінна функція за позицією р,

Коефіцієнт важливості для i-ої характеристики,

Перша характеристика позиції p.

2.5 Постановказавдання

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

За підсумками дипломної роботи необхідно:

ü реалізувати досліджувані алгоритми мовою програмування С#

ü реалізувати їх різні модифікації, використовуючи додаткові модулі

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

ь розробити зручний та інтуїтивно зрозумілий інтерфейс

3. Досліджуваніалгоритмиідоповнення

3.1 Альфа-бетавідсікання

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

Малюнок 6 - Алгоритм альфа-бета відсікання

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

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

На вхід цього алгоритму подаються параметри alpha та beta, їх називають вікном перебору. Ці параметри відповідають за межі відсікання на першому рівні, при поглибленні в дерево гри ці параметри змінюються. Алгоритм alpha-beta з параметрами alpha = + нескінченність і beta = - нескінченність (перебір з повним вікном) дає результат такий самий, як і алгоритм negamax, тобто повний перебір. На малюнку 7 представлено блок-схему алгоритму alpha-beta за підрахунком оцінки позиції в глибину.

Малюнок 7 - Блок-схема alpha-beta для пошуку оцінки в глибину

3.1.1 прикладстандартноговідсікання

Рисунок 8 - Приклад стандартного відсікання

Розглянемо приклад стандартного альфа бета відсікання. У позиції А хід вибираємо ми, отже виберемо найбільше значення з позицій В і С. Значення В уже пораховано - це 10. При розрахунку позиції З з'ясувалося, що один із вузлів має значення 5. У позиції С хід робитиме наш суперник, а значить вибере найменше значення. З цього випливає що значення позиції буде від 5 і нижче, отже ми завжди виберемо В-варіант. Тому розрахунок решти вузлів С ми не проводимо.

3 .1.2 прикладпоглибленоговідсікання

Рисунок 9 - Приклад поглибленого відсікання

Розглянемо приклад глибокого відсікання. У позиції А ми вибиратимемо між ходами в позиції В і С. Значення В = 15. Ми починаємо розрахунок С. У позиції Е один із вузлів дав значення 5. У позиції Е вибір ходу належить супернику, а значить підсумкове значення Е буде від 5 і нижче. Якщо значення С виявиться рівним Е, ми виберемо варіант У, оскільки він привабливіший. Отже нам не обов'язково знати точне значення позиції Е, тому всі інші гілки, що виходять з нього, обрізаються.

3 .2 Ітераційнезанурення(IteratedDeepening)

Сенс віяла перебору або ітераційного поглиблення полягає в викликі процедури перебору, що повторюється, на фіксовану глибину зі збільшенням глибини, поки встановлений ліміт часу не перевищений або максимальна глибина пошуку не досягнута. Перевага цього методу полягає в тому, що ви не повинні вибирати глибину пошуку заздалегідь; Крім цього, ви можете завжди використовувати результат останнього закінченого пошуку. Значення, повернені від кожного пошуку, можуть використовуватися, щоб коригувати вікно прагнення наступного пошуку.

Загалом, альфа-бета відсікання викликається з вершини дерева на інтервалі (-?; +?). Проте використовуючи ітераційне занурення ми можемо змінити його.

Припустимо, що Х - значення оптимального ходу знайдене на попередній ітерації, а числом Epsilon позначимо передбачувану різницю в результатах між пошуком на глибину D-1 і глибину D. Далі ми просто викликаємо відсікання альфа-бета з вершини дерева з передбачуваним інтервалом: alphabeta(D, x-epsilon, x+epsilon).

1. Значення повернеться в інтервалі (x-epsilon, x+epsilon) – це коректне значення, ми можемо його використати.

2. Значення повернеться поза інтервалом (x-epsilon, x+epsilon) необхідно повторити обчислення зі зміненим інтервалом.

Навіть якщо припустити, що метод альфа-бета відсічень не дасть жодного виграшу, загальне збільшення часу аналізу насправді виявиться відносно невеликим. Дійсно, якщо припустити, що середня кількість варіантів на кожному рівні дорівнює D, а кількість аналізованих рівнів становить p, то ітеративний пошук до першого рівня, потім до другого і т.д. рівня p, еквівалентний (без альфа-бета відсікань) перегляду D + + ...+ позицій.

Ця сума дорівнює, тоді як кількість позицій, що переглядаються при звичайному аналізі, дорівнює. Співвідношення між цими двома числами при великих p приблизно одно і, отже, близько до 1 у випадках, коли D досить велике

Також під час використання ітеративного пошуку можна ввести контроль часу, що дозволить комп'ютеру будь-якої миті запропонувати задовільне рішення. Таким чином, якщо час на роздум обмежений 5 секундами, він розгляне всі позиції до рівня 2, наприклад, за 0.001 секунду, до рівня 3 - за 0.01 секунду, до рівня 4 - за 1 секунду, а потім, після початку аналізу на рівні 5 буде змушений перерватися через брак часу. Однак при цьому комп'ютер вже матиме досить гарне рішення, знайдене на рівні 4.

В результаті комп'ютер здатний дати відповідь у вказаний час (наприклад, зробити 50 ходів за 2 години). Також очевидно, що програма, яка підтримуватиме подібний метод, гратиме з різною силою на різних комп'ютерах.

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

3.3 Сортуванняходів

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

У першому випадку проведемо розрахунок розсортувавши ходи «від гіршого на краще»

Малюнок 10 - Альфа-бета відсікання з ходами «від гіршого на краще»

Як видно з прикладу, не було відсічено жодної гілки дерева.

Тепер відсортуємо ходи «від найкращого до гіршого»

Малюнок 11 - альфа-бета відсікання з ходами «від кращого до гіршого»

За оптимальних обставин перебір з альфа-бета відсіканням має переглянути W^((D+1)/2) + W^(D/2) - 1 позицію. Це набагато менше, ніж мінімакс.

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

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

Для інших ходів алгоритм віддає перевагу ходам із шахами та взяттями.

3 .4 Нега-Скаут(NegaScout)

NegaScout - надбудова над бета-альфа. Це спрямований алгоритм пошуку обчислення мінімаксного значення вузла.

NegaScout – найпопулярніший на сьогодні алгоритм грубого зусилля. Він надзвичайно простий і дає деяке (до 50%) прискорення, не вносячи жодної додаткової похибки до обчислення. Він дуже добре поєднується із сучасними атрибутами шахових програм - хеш-таблицями.

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

Алгоритм NegaScout перевіряє перший вузол з повним вікном (Alpha, Beta), вважаючи цей варіант найкращим. Наступні вузли намагається відсікти перебором з нульовим вікном, тобто. вікном (Alpha, Alpha+1). Якщо результат рахунку покращує альфа, то це означає, що 1 вузол не був кращим, а цей вузол потрібно перевірити з повним вікном, проте замість Alpha ми може взяти отримане значення (Value, Beta). Код цього методу наведено нижче:

public int NegaScout(Cell[,] CopyBoard, int Depth, int FinalDepth, int Alpha, int Beta, int PossibleMoves, bool IsMy)

int Value = 0, MaxValue = -1000, leight = 0;

Cell [,] Board = New Cell;

Point[,] Moves = new Point;

Point Move = New Point;

FindMoves(Moves, ref leight, Board, true, true);

PossibleMoves = leight;

FindMoves(Moves, ref leight, Board, false, true);

PossibleMoves += leight;

if ((Depth == FinalDepth) || GameIsOver(Board, IsMy))

return Eval (Board, PossibleMoves);

return -1 * Eval (Board, PossibleMoves);

FindMoves(Moves, ref leight, Board, HaveRequiredMove(Board, IsMy), IsMy);

int a = Alpha, b = Beta;

for (int i = 0; i< leight; i++)

CopyMove(Move, Moves, i);

DoMove (Board, Move);

Value = -1 * NegaScout (Board, Depth + 1, FinalDepth, -1 * b, -1 * a, PossibleMoves, ! IsMy);

if (Value>a && Value 0 && (Depth

a = -1 * NegaScout (Board, Depth + 1, FinalDepth, -1 * Beta, -1 * Value, PossibleMoves, !IsMy);

if (Value > a)

CopyPosition(Board, CopyBoard);

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

3 .5 Хеш-таблиці

3 .5 .1 Теорія

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

Найкращий хід для глибини N може бути кращим і для глибини N+1. Тобто, крім свого початкового призначення, таблиця хеш виявляється корисною і для впорядкування ходів. Тут ще зненацька допомагає ітеративне поглиблення - коли ми починаємо наступну ітерацію, хеш таблиця виявляється заповнена інформацією від попередньої, і до якогось моменту (до глибини 1) всі позиції просто є в ній, з найкращим ходом на глибину N-1.

Програма, що використовує ітеративне поглиблення та хеш-таблиці, часто виконує всі ітерації від 1 до N у кілька разів швидше, ніж якби вона відразу почала ітерацію N, т.к. з ймовірністю 75% вона завжди першим вибирає найкращий хід, а з ймовірністю ~90% найкращий хід виявляється серед перших трьох розглянутих.

3 . 5 .2 Реалізація

Хешування є одним із найпотужніших способів підвищення продуктивності комп'ютера. Використання хеш таблиць є основним інструментом програмування шахових ігор.

Хеш таблиця - являє собою велику індексовану таблицю, в комірках яких зберігатиметься така інформація:

· 2 хеш індексу

· Глибина прорахунку для цього ходу

· Оцінка цього ходу

Вибір алгоритму підрахунку хеш індексу ходу є найважливішим моментом, при використанні алгоритмів хешування. При виборі алгоритму розрахунку хеш індексу треба враховувати 2 найважливіші моменти:

Індекс повинен найбільше відображати унікальну інформацію про хід, щоб максимально скоротити кількість колізій

Хеш індекс має бути простим для підрахунку

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

Для підрахунку індексу була обрана операції з деякими, випадково згенерованими масками.

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

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

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

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

3.6 Використаннябібліотекдебютів

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

3 .7 Оцінкапозиції

p align="justify"> При розробці алгоритму статичної оцінки позиції (функції якості) існує невизначеність вибору між якістю і швидкістю роботи. Якісні оціночні функції, засновані на статистичній базі, працюють повільно, але дають дуже точні оцінки, деякі навіть без застосування перебору виявляють задатки інтелекту.

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

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

Графічно ця залежність зображена малюнку як сімейства гипербол.

Рисунок 12 - Приклад поглибленого відсікання

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

Шахи прийнято розділяти на етапи: дебют - відкриття партії, міттельшпіль - середина гри, ендшпіль - заключна стадія. Для алгоритму вирішено розділити партії на 3 етапи за кількістю фігур, що залишилися на дошці комп'ютерного гравця. Спочатку на дошці по 16 фігур у гравців. У таблиці представлена ​​залежність етапу гри від кількості фігур, що залишилися:

Таблиця 1 - Етапи гри

3 . 7 .1 Матеріальнаоцінка

Матеріальна перевага одного з гравців вважається найважливішим параметром у шаховій теорії, отже матеріальна оцінка вносить найбільший вплив на загальну оцінку позиції. Матеріальна оцінка вважається сумою вагових коефіцієнтів всіх фігур на дошці. Король не входить у матеріальну оцінку, оскільки у разі втрати короля, гравець автоматично програє. Оцінка ваг фігур є основним завданням при побудові оцінної функції. Для визначення ваг фігур було вирішено скористатися самонавчальним алгоритмом, заснованим на генетичному алгоритмі. Вага фігур не залежить від етапу гри. Генетичний алгоритм - це евристичний алгоритм пошуку, що використовується для вирішення задач оптимізації та моделювання шляхом випадкового підбору, комбінування та варіації шуканих параметрів з використанням механізмів, що нагадують біологічну еволюцію, вперше запропоновані Холландом (1975).

3 . 7 . 2 Описроботигенетичногоалгоритму

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

Після цього з використанням отриманих значень пристосованості вибираються вектори (селекція), допущені до схрещування. До цих векторів застосовуються генетичні оператори (зазвичай схрещування і мутація), створюючи таким чином наступне покоління. Особи наступного покоління також оцінюються, потім проводиться селекція, застосовуються генетичні оператори тощо.

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

Знаходження оптимального рішення;

Вичерпання числа поколінь, відпущених еволюцію;

Вичерпання часу, відпущеного на еволюцію.

Генетичні алгоритми служать, головним чином, пошуку рішень у дуже великих, складних просторах пошуку.

Таким чином, можна роботу генетичного алгоритму можна уявити на наступній схемі:

Рисунок 13 - Приклад поглибленого відсікання

3 . 7 . 3 Етапироботигенетичногоалгоритму

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

Відбір (селекція) - з усієї популяції вибирається певна частка, яка залишиться «в живих» цьому етапі еволюції. Схрещування (розмноження) - у тому, щоб зробити нащадка, потрібні кілька батьків; зазвичай, звичайно, потрібні рівно два. Розмноження у різних алгоритмах визначається по-різному - воно, звісно, ​​залежить від представлення даних. Головна вимога до розмноження – щоб нащадок чи нащадки мали можливість успадкувати риси обох батьків, «змішавши» їх у якийсь досить розумний спосіб.

Мутації – стохастичне зміна частини особин (хромосом).

3 . 7 . 4 Визначеннявагфігурздопомогоюгенетичногоалгоритму

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

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

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

При схрещуванні використовується метод одноточкового схрещування.

Береться випадковим чином 2 батьки, вибирається випадково число, за якою хромосома розділиться, схема показана малюнку №14. В результаті кожного нащадка будуть риси як від першого так і від другого батька.

Рисунок 14 - Приклад поглибленого відсікання

Мутації виконується наступним чином: вибираються з деякою ймовірністю хромосоми, і у них кожен «ген» змінюється на випадкове число в діапазоні [-50; 50], крім значення статичних оцінок ферзя та пішака.

Для фінальних значень ваги діляться на 100.

3 . 7 . 5 Сумарнаоцінка

При оцінці позиції звертається увага на 8 складових:

1. Матеріальні сили суперників

2. Кількість полів під боєм

3. Заняття ключових полів

4. Прохідні пішаки

5. Здвоєні пішаки

6. Рокування

7. Просування пішака

8. Пішакові ланцюги [*1]

Кількість полів під боєм розраховується на глибині дерева 2, зважаючи на великі продуктивні витрати. За кожне поле, яке б'є фігура комп'ютера, до оцінки позиції додається 1 очко, за поля, які б'ються фігурами гравця, знімається по окуляру. Отримане значення передається вниз дерева як параметр. Так само на глибині 2 проводиться розрахунок балів за пішакові ланцюги, прохідні та здвоєні пішаки. За наявність стикаються зліва або праворуч пішаків сторона отримує по 1 балу. Пішак вважається прохідним, якщо на її вертикалі, а так само на сусідніх з нею, немає пішаків суперника, які можуть перешкодити їй пройти до кінця. Здвоєні пішаки - 2 пішаки одного кольору, що стоять на одній вертикалі. За наявність здвоєних пішаків зі сторони знімається 4 очки, за наявність кожного прохідного пішака додається 5 очок. У шахах є ключові поля:

Малюнок 15 - Ключові поля

За зайняття кожного з них даються додаткові 4 очки.

Т.к. після рокування король перебуває в дуже стійкому положенні, за досконале рокіровування сторона отримує 3 очки.

Чим ближче пішака до останньої для неї горизонталі, тим вона ближча до перетворення. За кожну пройдену вперед клітину до цінності пішака додається 1.

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

4 . Розробкапрограмы

4 .1 Вимогидошаховомуалгоритму

Під час розробки моделі програмного модуля для гри в шахи слід враховувати наступні параметри:

* Шахові алгоритми дуже вимогливі до продуктивності, і сила гри програми безпосередньо залежить від продуктивності програми.

* модулі програмного забезпечення повинні бути легкими у розробці та тестуванні

* інтерфейс повинен бути легким, легко настроюваним і масштабованим

4 .2 Видишаховихалгоритмів

Більшість сучасних програм можна розбити на 3 категорії:

* Перша категорія Fast searchers - ідея полягає в тому, що, спростивши до межі оцінну функцію, і ретельно оптимізувавши всю програму в цілому (що зазвичай досягається шляхом написання програми на асемблері), можна довести кількість позицій, що розглядаються програмою (nps - nodes per second) до астрономічного числа, наприклад до 150-200k nps на P/200. Тобто на кожну позицію програма витрачає близько однієї-двох тисяч машинних команд. У це число входить роблення ходу з попередньої позиції в цю оцінку позиції, генерація ходів з даної позиції, керуюча логіка і т.д. На власне оцінну функцію залишаються взагалі крихти - близько сотні команд. Програми виходять дуже швидкими і чудово поводяться в складних тактичних позиціях, а також відмінно вирішують комбінаційні завдання, але мають слабку позиційну гру

* Друга категорія - knowledge-based програми. Тут всі сили кинуті написання складної оцінної функції. Враховується і взаємодія постатей одна з одною, і прикритість короля, і контроль позицій, і чи не фаза місяця. У термінах nps програма працює у 10-100 разів повільніше, ніж fast searches, але грає у добрі позиційні шахи. Точніше, хорошими ці шахи є лише тоді, коли на дошці немає глибокої тактики, або ж контроль часу такий, що програма має достатньо часу, щоб цю тактику прорахувати.

4 .3 Контрольчасувшаховихалгоритми

Найважливішим параметром у побудові алгоритму штучного інтелекту шахового опонента є контроль часу ходу. Від контролю часу залежить сила гри шахової програми. Перед початком "обдумування" ходу комп'ютером має бути обчислено час, доступний комп'ютеру.

При розрахунку часу доступного на хід треба виходити з двох параметрів:

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

* час очікування відповіді комп'ютерного опонента не повинен бути занадто великим. За основу можна взяти міжнародні правила шахів, у яких є кілька видів партій: бліц – 15 хвилин на партія, швидкі – 60 хвилин на партію, класичні – більше 60 хвилин на партію.

Виходячи з необхідних параметрів, вирішено час доступний для ходи перед початком кожного ходу комп'ютера обчислювати за такою формулою: де: time - час на хід; full_game_time – загальний час партії; avg_moves – середня кількість ходів гравця в партії; collect_time – додатково накопичений час; Д - невелике скорочення часу, необхідне додаткові розрахунки. Параметри загального часу партії та середня кількість ходів гравця в партії – два основні зовнішні параметри, змінюючи які можна змінювати силу гри. За статистикою шахового порталу TheChess.ru, середня кількість ходів гравців за партію дорівнює 30, тому вирішено взяти середню кількість ходів гравця в партії рівному 30. Таким чином, з-за загальний час партії. При розробці алгоритму поведінки комп'ютерного опонента (штучного інтелекту) було використано такі алгоритми:

* алгоритм ітеративного пошуку, з контролем часу

* алгоритм alpha-beta відсікання та Nega-Scout

* бібліотеки дебютів

* хеш-таблиці

* Для сортування ходів використовувалися евристики вбивці та історії.

4 .4 Розробленапрограма

У програмі мовою програмування С# було реалізовано перераховані вище алгоритми і доповнення.

Скріншоти програми наведені нижче:

Малюнок 16- Вибір кольору

Малюнок 17 - Скріншот програми

Малюнок 18 - Скріншот програми

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

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

4 .5 Базовийциклпошукукращогохода

Головним завданням базового циклу пошуку кращого ходу є знаходження та виконання найкращого ходу комп'ютерного опонента. Цикл використовує бібліотеки дебюту та ітеративний пошук із контролем часу. На малюнку 12 представлений процес пошуку кращого ходу:

Рисунок 19 - Базовий цикл пошуку кращого ходу

4 .6 Пошуккращогоходапершогорівня

Головним завданням роботи алгоритму пошуку кращого ходу першого рівня (відповіді супротивника) є знаходження найкращого ходу опонента першому рівні. Алгоритм побудований на алгоритмі NegaScout, що використовує оцінювання в глибину для визначення оцінки поточного ходу. На малюнку 13 представлено процес роботи алгоритму:

Рисунок 20 - Пошук кращого ходу першого рівня

4 .7 Знаходженняглибиннийоцінкихода

Головним завданням знаходження глибинної оцінки - знаходження оцінки поточного ходу, використовуючи алгоритм NegaScout, евристику нульового ходу, дані з хеш таблиці та статичну оцінку позиції. На малюнку 14 представлений процес підрахунку оцінки ходу у глибину:

Малюнок 21 - Знаходження глибинної оцінки ходу

4.8 Іншімоделіідіаграми

Математична модель програми виглядає так:

Малюнок 22 - Математична модель

Від абстрактного класу Figure створюються 7 класів спадкоємців, що описують дії та властивості фігур. Так само є клас Еmpty, що означає, що клітина порожня. Дошка є масивом з 64 елементів Figure, кожен з яких може ставати будь-яким із класів-спадкоємців. Хід у комп'ютері представляється як 4 цифр - координат (від 1 до 8) точки початку ходу і координат точки кінця ходу. Нижче наведено діаграму станів для програми:

Малюнок 23 - Діаграма станів

5 . Експериментальнаоцінкаякостіреалізіваннихалгоритмів

Реалізовані алгоритми були піддані порівняльному аналізу з метою виявлення оптимальної швидкодії та якості здійснення ходу конфігурації. У ході експерименту проводилася низка турнірів між кожною парою різних реалізацій.

5 .1 ОцінкароботиАльфа-Бетавідсікання

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

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

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

Таблиця 1 - Порівняння показників алгоритму альфа-бета відсікання з алгоритмом мінімаксу.

Результати експериментів показують, що альфа-бета відсікання набагато краще простого мінімакс пошуку.

5 .2 Оцінкароботиітераційногозануренняісортуванняходів

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

Подібні документи

    Опис правил гри "Морський бій". Особливості сучасних комп'ютерів та штучного інтелекту. Створення загальної блок-схеми програми, її зовнішній вигляд. Необхідні змінні, процедури та функції. Характеристика об'єктів, які у додатку.

    курсова робота , доданий 05.11.2012

    Розробка на основі гри "Точки" підходу до програмування "штучного інтелекту" у позиційних іграх та можливість застосування даного підходу для вирішення завдань у галузі економіки, управління та інших галузях науки. Модель ігрової ситуації.

    дипломна робота , доданий 21.07.2013

    Структурна діаграма програмного модуль. Розробка схеми програмного модуля та інтерфейсу користувача. Реалізація програмного модуля: код програми; опис використаних операторів та функцій. Вигляд форми користувача з заповненою матрицею.

    курсова робота , доданий 01.09.2010

    Дослідження загальних правил гри в шашки, інструкції користувача та програміста. Характеристика основних алгоритмів, що виконують завдання класу Life Widget. Оцінка ходів комп'ютера та людини. Побудова дерева пошуку кращого ходу, виходячи з оцінки функцій.

    контрольна робота , доданий 20.12.2012

    Основні стадії розробки, принципи тестування та налагодження програмного модуля "VFS". Особливості проектування мовою UML. Методи "грубою сили" та їх застосування при налагодженні програми. Шкідливі чинники, присутні на робочому місці програміста.

    дипломна робота , доданий 07.03.2012

    Аналіз моделей та методів реалізації інтелектуальних ігор у системі людина-робот. Середовище розробки Choreographe. Алгоритми модуля розпізнавання, обробки даних, функцій модуля гри. Тестування програмного комплексу, виправлення та редакція помилок.

    дипломна робота , доданий 12.08.2017

    Сутність та проблеми визначення штучного інтелекту, його основних завдань та функцій. Філософські проблеми створення штучного інтелекту та забезпечення безпеки людини під час роботи з роботом. Вибір шляхів створення штучного інтелекту.

    контрольна робота , доданий 07.12.2009

    Ігрова програма "шашки" для гри між людиною та комп'ютером. Розробка алгоритмів, історична лінія розвитку задач. Різні підходи до побудови систем. Скорочений листинг програми та опис алгоритму. Компоненти штучного інтелекту.

    курсова робота , доданий 26.03.2009

    Побудова та аналіз математичної моделі гри. Визначення ймовірності виявлення кораблів при всілякому їх розташуванні та різних системах пошуку. Розробка алгоритмів до роботи штучного інтелекту. Структура програми та її компоненти.

    курсова робота , доданий 22.12.2012

    Поняття штучного інтелекту як властивості автоматичних систем брати він окремі функції інтелекту людини. Експертні системи у галузі медицини. Різні підходи щодо побудови систем штучного інтелекту. Створення нейронних мереж.




Предмет досліджень та мета розробок Предметом вивчення науки «штучний інтелект» є людське мислення. Вчені шукають відповідь на запитання: як людина мислить? Ціль цих досліджень полягає в тому, щоб створити модель людського інтелекту і реалізувати її на комп'ютері. Предметом вивчення науки "штучний інтелект" є людське мислення. Вчені шукають відповідь на запитання: як людина мислить? Ціль цих досліджень полягає в тому, щоб створити модель людського інтелекту і реалізувати її на комп'ютері.


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


Неформальний виконавець Розробники систем штучного інтелекту якраз і намагаються навчити машину, подібно до людини, самостійно будувати програму своїх дій, виходячи з умови завдання. Можна сказати так: ставиться мета перетворення комп'ютера з формального виконавця в інтелектуального виконавця. Розробники систем штучного інтелекту якраз і намагаються навчити машину, подібно до людини, самостійно будувати програму своїх дій, виходячи з умови завдання. Можна сказати так: ставиться мета перетворення комп'ютера з формального виконавця в інтелектуального виконавця.








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


Експертні системи Одним із видів систем штучного інтелекту є Експертні системи. Одним із видів систем штучного інтелекту є Експертні системи. Призначення експертних систем – консультації користувача, допомога у прийнятті рішень. Призначення експертних систем – консультації користувача, допомога у прийнятті рішень.

культури. Дисер. Канд. Пед наук. Ростов-на-Дону. 2003.

2.Азарова Є.А. Деструктивні форми сімейного виховання, актуальні проблеми сучасності, злочини останніх часів: духовно-моральний та кримінофамілістичний аспекти. - Ростов-на-Дону: Вид-во РГПУ, 2005.

3.Габдрєва ГШ. Основні аспекти проблеми тривожності у психології // Шкільний психолог. – 2004. – N° 8. – С. 9.

4. Єніколопов С.М. Проблеми сімейного насильства// Проблеми психології. -2002. -№5-6.

5.Целуйко В.М. Психологія неблагополучної сім'ї: Книга для педагогів та батьків. - М: Вид-во ВЛАДОС-ПРЕС, 2003.

6. Шапар В.Б. Практична психологія. Психодіагностика відносин між батьками та дітьми. -Ростов н/Д: Фенікс, 2006.

© Азарова Є.А., Жуліна Г.М., 2016

А.І. Аліфіров

канд. пед. наук, доцент РДСУ, м. Москва, РФ

І.В. Михайлова канд. пед. наук, доцент РДСУ, м. Москва, РФ

«ШТУЧНИЙ ІНТЕЛЕКТ» У ШАХМАТАХ

Анотація

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

Ключові слова

Комп'ютерні технології у шахах, шахові програми, шахи.

Сьогодні під терміном "штучний інтелект" (ІІ) розуміється теорія створення програмних та апаратних засобів, здатних здійснювати інтелектуальну діяльність, яку можна порівняти з інтелектуальною діяльністю людини. При вирішенні практичних завдань найчастіше користуються завданням зі списку, вважаючи у своїй, що й комп'ютерна система може вирішити ці завдання, вона і є системою ИИ. Часто в цей список включають гру в шахи, доказ теорем, вирішення діагностичних завдань з вихідного неповного набору даних, розуміння природної мови, здатність до навчання та самонавчання, здатність до класифікації об'єктів, а також здатність виробляти нові знання на основі створення нових правил та моделей регуляризації знань.

Однією з найважливіших проблем нової науки – кібернетики стала проблема, як покращити управління, як удосконалити ухвалення рішень. Один із засновників кібернетики К. Шеннон (Shannon C.) запропонував формалізувати та програмувати шахи для того, щоб використовувати шаховий комп'ютер як модель, для вирішення аналогічних завдань управління. Авторитет К. Шеннона був настільки великий, що його ідеї негайно започаткували новий науковий напрям. Ідеї ​​К. Шеннона були використані у роботах А. Тьюринга, К. Цузе, Д. Принца.

Автор теорії інформації. К. Шеннон писав: "Шахова машина ідеальна, щоб з неї почати, оскільки (1) завдання чітко визначається допустимими операціями (ходи) і кінцевою метою (мат); (2) вона не надто проста, щоб бути тривіальною, і не занадто складна для отримання задовільного рішення; дискретна структура шахів добре вкладається в цифрову природу сучасних комп'ютерів.

Надалі шахи стали предметом змагання природного та штучного інтелекту, і було зіграно низку матчів провідних шахістів світу проти комп'ютерів. 1995 року в інтерв'ю популярному журналу Wired Г.К. Каспаров виклав свій погляд на шахову гру: "Шахати - це не математика. Це фантазія та уява, це людська логіка, а не гра з передбачуваним результатом. Я не думаю, що теоретично гру в шахи можна вмістити в набір формул або алгоритмів". Через два роки суперкомп'ютер DEEP BLUE, перемігши 13-го чемпіона світу Г.К. Каспарова у матчі-реванші з шести партій зняла з порядку денного питання про можливості шахового штучного інтелекту. DEEP BLUE зберігала в пам'яті повну базу даних по всіх партіях та аналізувала виключно стратегію розрахунком. Після матчу Г.К. Каспаров змінив свою думку, визнавши, що: " Шахи - це єдине полі, у якому можна зіставити людську інтуїцію і творчі здібності з силою і машини " . Матч змінив хід розвитку як класичних, і комп'ютерних шахів. У системі тренування стала широко використовуватись допомога штучного інтелекту. Д.І. Бронштейн у своїй книзі "Давид проти Голіафа" (2003 р.) писав: "Ботвинник вважав, що шахи - це мистецтво аналізу, а час одинаків-імпровізаторів на кшталт Андерсена, Морфі, Цукерторта пішло назавжди. Дивлячись на сучасні шахи, треба визнати Ботвинник виявився правим. "Комп'ютерні хлопчики" довели його ідею про необхідність домашнього аналізу до абсурду. з Анандом стояла в нього на комп'ютері!

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

1. Аліфіров А.І. Профорієнтаційна робота у середніх загальноосвітніх школах засобами шахів / Аліфіров О.І. // Проблеми розвитку науки і освіти: теорія та практика. Збірник наукових праць за матеріалами Міжнародної науково-практичної конференції 31 серпня 2015 р.: у 3 частинах. Частина ІІ. М.: "АР-Консалт", 2015 р. – С. 13-14.

2. Михайлова І.В., Аліфіров А.І. Тактичні дії шахістів/Михайлова І.В., Аліфіров А.І. //Результати наукових досліджень Збірник статей Міжнародної науково-практичної конференції. Відповідальний редактор: Сукіасян Асатур Альбертович (15 лютого 2016 р.) о 4 год. Ч/3 - Уфа: АЕТЕРНА. -2016.С. 119-121.

3. Михайлова І.В., Аліфіров А.І. Теоретико-методологічні засади методу мислення схемами шахістів / Михайлова І.В., Аліфіров О.І. //Результати наукових досліджень Збірник статей Міжнародної науково-практичної конференції. Відповідальний редактор: Сукіасян Асатур Альбертович (15 лютого 2016 р.) о 4 год. Ч/3 - Уфа: АЕТЕРНА. – 2016. С. 123-125.

4. Михайлова І.В. Підготовка юних висококваліфікованих шахістів за допомогою комп'ютерних шахових програм та "інтернет": автореф. дис. ... канд. пед. наук: 13.00.04 / Михайлова Ірина Віталіївна; РГУФК. – М., 2005. – 24 с.

© Аліфіров А.І., Михайлова І.В., 2016

УДК 378.046.2

А.І. Аліфіров

К.п.н., доцент РДСУ, м. Москва, РФ В.В. Федчук, к.п.н.

ТОВ «Благополуччя», старший інструктор методист, м. Москва, РФ ДОСЛІДЖЕННЯ РІВНЯ ФІЗИЧНОГО ЗДОРОВ'Я ПІДЛІТКІВ

Анотація

У статті розглядається проблема фізичного здоров'я підлітків та вплив різних факторів