Наука Досвід саперу
Відноситься до розділу Наука
Два способи застосування МГА схеми для вирішення задачі відкриття поля в сапері (гра, що поставляється в комплекті з більшістю операційних систем)
Завдання відкриття поля в сапері досить тривіальне і має цілком конкретне давно відоме рішення. Але сенс застосування МДА підходу не в тому, щоб вирішити завдання, яке раніше не мало рішення. Планується продемонструвати ефективність МДА підходу для вирішення задачі за відсутності будь-яких початкових даних про неї і навіть не знаючи умов завдання.
Отже, що ж дано, якщо нічого не відомо?
Є сенсорна картина, тобто стандартне, наприклад піксельне, зображення поля сапера. У загальному випадку можна здійснювати різноманітні дії у зв'язку з наявністю сенсорної картини. Відома також кінцева мета - відкрити повністю поле. Важливо, що існують різні способи початкового формулювання цієї мети.
На початковому етапі пошуку рішення планується визначити, які дії призводять до зміни сенсорної картини. Для цього можна використовувати ГА. Допустимо цей етап пройдено і виявлено, що над клітинами можна здійснювати 3 дії: відкрити, поставити міну, подвійне клацання (відкрити прилеглі клітини у разі достатньої кількості мін навколо). Виявити останню дію не так то просто (я через пів року виявив), проте вирішити завдання можна і без нього. Крім пошуку дій, що призводять до зміни на екрані, можна також виділити мінімальну змінну ділянку сенсорної картини (клітину), і визначити всі властиві цій ділянці стану. Нагадаю, що у сапері досить обмежена кількість цих станів, 11 штук: 9 цифр, закрите поле, міна. Зазначу, що цей етап не вимагає навіть розуміння того, щозображено у клітці міна чи цифра (і якщо цифра, то яка).
Отже, всі необхідні компоненти для запуску ГА, націленого безпосередньо на пошук рішення, є. Цілком логічно, якщо ми моделюємо роботу ЦНС, шукати рішення у вигляді стимул — реакція. Стимулом є у разі зміна сенсорної картини, чи стану однієї чи певного числа клітин. Реакцією вважатимуться одне з трьох зазначених раніше действий. Якщо точніше, то дію, яку треба зробити над клітиною, залежить від поточного стану клітин на полі, а точніше оточуючих її клітин, але цю обставину можна виявити вже в процесі роботи ГА. Завдання можна розділити на частини: пошук шаблонів, тобто сукупності клітин на полі, від яких залежить поточний стан клітини. Пошук значень клітин шаблону, у яких над цією клітиною можна робити дію не побоюючись закінчити гру. Для того щоб виконати дію з появою потрібного шаблону в сенсорній картині можна використовувати спрощений нейрон. Його вхідними сигналами буде стан клітин шаблону, а вихідним сигналом буде дія, спрямоване зміну стану відповідної клітини. У разі появи відповідного сигналу, нейрон збуджуватиметься і пускатиме сигнал по аксону, внаслідок чого дія автоматично виконуватиметься. Серед популяцій такого роду нейронів і вестиме відбір ГА. Кінцеві результати цього відбору можна передбачити, виходячи зі знання евристичного рішення. Наприклад:
А в більш загальному випадку:
Де* – це не відкрите поле.
Показані шаблони для встановлення міни в нижньому лівому не відкритому кутку.
можна сміливо відкривати всі відкриті поля.
Інші типи шаблонів кожен може вивести сам. Потрібно лише враховувати, що крім показанихдев'ятиточкових шаблонів є варіанти шаблонів, що містять більше полів.
Які ж особливості такого підходу до пошуку рішень?
Перше, що можна відзначити, що навіть для такого простого завдання, як сапер, рішення шукається поступово в міру накопичення корисних шаблонів.
Друге - результатом оптимізації буде нейронна мережа, яка зможе відкривати практично миттєво будь-які поля, що не містять місць з неоднозначністю вибору.
Можна також спробувати підібрати двошарову нейронну схему, де другий шар реалізовуватиме роботу ГА з відбору корисних нейронів першого рівня, принцип дії яких описаний раніше. Я не знаю наскільки широко застосовуються нейронні мережі для вирішення подібних формалізованих завдань, проте рішення нейронної мережею такого завдання, за відсутності початкових уявлень про неї, буде важливим прецедентом їх застосування. Важливо згадати наступну властивість вже налагодженої нейронної мережі першого нейронного шару. Кількість тактів її роботи, необхідне повного відкриття поля в сапері, логарифмічно залежить кількості клітин на полі. Для систем з лінійною архітектурою, необхідно число тактів порядку квадрата числа клітин.
Ще варто відзначити, що рішення, отримане таким способом, буде прикладом інтуїтивного рішення задачі. У цьому випадку правила гри залишаться невідомими навіть після того, як програма навчиться вирішувати завдання. Таке просте пояснення інтуїтивних рішень і самого явища інтуїції дозволить уникнути апеляцій містиків до цієї здатності свідомості.
Корисно використовувати вже відкрите поле для того, щоб суттєво прискорити процес пошуку рішення. Адже у відкритому полі є велика кількість корисних шаблонів. Навіть якщо брати з відкритого поля шаблони з довільнимрозташуванням клітин як початкової популяції для ГА, це сильно підвищить швидкість його збіжності. Таким чином, можна говорити про успішність для МДА «навчання з прецедентів», тобто за прикладами правильних рішень, що також властиво природному інтелекту.
Тепер представимо другий варіант рішення сапера. У цьому випадку використовуватиметься ГА з умовою, а як умова використовуватимуться правила гри. Це має на увазі, що всі можливі дії та стани клітини, як і саме поняття клітини, відомі заздалегідь. Сама умова – кількість мін навколо кожної відкритої клітини відповідає цифрі в ній зазначеній.
ГА з умовою працюватиме в такий спосіб. Для кожної клітини є три варіанти дій. Якщо дія суперечить правилам гри, воно автоматично відкидається. Для клітин де залишається одне дію воно автоматично виконується, а інших нічого не робиться. Тепер потрібно з'ясувати, яким чином перевірятиметься виконання правил гри. Просто буде проводитися уявний експеримент, тобто буде «віртуально» виконуватися одна з дій і для всіх сусідніх клітин перевірятиметься умова виконання правил гри. Таким чином, ГА з умовою відразу працює як цілком ефективний алгоритм, який зможе частину полів відкрити повністю.
Є ще варіант з модифікацією першого способу рішень, коли шаблони нейронів будуть відразу перевіряться на відповідність правилам гри, замість того, щоб «проганяти шаблон» на декількох десятках полів.
Варто зазначити, що для обох варіантів вирішення є проблема початку гри, коли не відкрито жодної клітини. У цьому випадку, як і для евристичного підходу, нічого іншого не залишається, як відкривати клітини випадковим чином.
Для розглянутого прикладу застосування ГА зУмовою застосовується незвичайний прийом для перевірки наявності протиріччя з правилами гри, що є спрощеним варіантом уявного експерименту. Передбачається, що дія вчинена, і перевіряється до яких наслідків це призводить, у даному конкретному випадку перевіряється відповідність правилам. Виходячи з досвіду самоспостереження, можу сказати, що подібні уявні експерименти є незмінною властивістю природного інтелекту. А в математиці є окремі терміни, що застосовуються до таких уявних експериментів: приведення до протиріччя, або доказ від протилежного. І ще приклад на цю тему:
Відомий німецький алгебраїст Ернст Едуард Куммер (1810-1893) дуже погано вмів рахувати в умі. Якщо під час читання лекції йому треба було виконати простенький розрахунок, він зазвичай вдавався до допомоги студентів.
Одного разу йому треба було помножити 7 на 9. Він почав уголос міркувати:
- Гм. це не може бути 61, тому що 61 – просте число. Це не може бути і 65, тому що 65 ділиться на 5. 67 – теж просте число, а 69 – явно надто багато. Залишається лише 63.
(Цит. за книгою: Kutzler B. B. Mathematikerwitze & Mathematikwitze. 2006; переклад Ю. Фролова.)
Прийом «думкового експерименту», що застосовується для сапера в даному випадку, можна вдосконалити. Для цього після імовірної дії, потрібно відкрити кілька навколишніх клітин (все це «в умі») і перевірити, чи не виникне протиріччя після цього в клітинах, розташованих поряд з модифікованими під час уявного експерименту. Такий підхід є елементом реально застосовуваної свідомої (моєї, наприклад) тактики відкриття сапера.
Як самокритика можна сказати, що початковий етап пошуку можливих дій і мінімальної змінної ділянки сенсорної картини,може вимагати набагато більших ресурсів і таїти в собі набагато більше проблем, ніж пошук корисних шаблонів. Сам поділ завдання на дві частини може здатися дещо волюнтаристським. Однак, у тих випадках, коли людині нічого не відомо про проблему. Що вимагає рішення, його дії також спрямовані на виявлення всіх можливих методів впливу на ситуацію та методів оцінки зміни ситуації. І насправді цей етап вирішення проблеми найчастіше є найважчим і займає найбільше часу.
Два запропоновані методи дозволяють вказати на одну з фундаментальних властивостей МДА. Процес вирішення задачі, як і саме рішення, значною мірою залежать від попереднього досвіду, накопиченого МГА системою, і від того, яка частина цього досвіду використовується для вирішення конкретної задачі. Також вона прояснює наявність деяких завдань кількох альтернативних методів їх вирішення з принципово різною схемою, до того ж використовують різні передумови.
Послідовність навчальних завдань, від простих до складніших, що дозволяє МДА системі «зрозуміти» якусь фундаментальну науку, наприклад, елементарну алгебру, є темою окремого дослідження. Під словом «зрозуміти» мається на увазі подальше активне використання МДА системою її законів під час вирішення практичних завдань.
Оцінити статтюможна після того, як в обговоренні буде хоча б одне повідомлення.