Головна > Різні ігри > Штучний інтелект та бази знань. Навчальний проект штучний інтелект Питання, що спрямовують проект

Штучний інтелект та бази знань. Навчальний проект штучний інтелект Питання, що спрямовують проект

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

переміщення;
оцінка шахівниці;
мінімакс;
альфа-бета-відсікання.

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

Готовий алгоритм можна знайти на GitHub.

Крок 1. Генерація ходів та візуалізація шахівниці

Ми будемо використовувати бібліотеки chess.js для створення ходів і chessboard.js для візуалізації дошки. Бібліотека для створення ходів реалізує всі правила шахів. Виходячи з цього ми можемо розрахувати всі ходи для даного стану дошки.

Візуалізація функції створення руху. Вихідне положення використовується як вхід, а на виході – всі можливі ходи з цієї позиції.

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

Var calculateBestMove = function(game) ( //Генерація всіх ходів для даної позиції var newGameMoves = game.ugly_moves(); return newGameMoves; );

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

Чорні грають випадковими ходами

JSFiddle.

Крок 2. Оцінка дошки

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

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

Var calculateBestMove = function (game) ( var newGameMoves = game.ugly_moves(); var bestMove = null; //Використовуйте будь-яке від'ємне число var bestValue = -9999; for (var i = 0; i< newGameMoves.length; i++) { var newGameMove = newGameMoves[i]; game.ugly_move(newGameMove); //Возьмите отрицательное число, поскольку ИИ играет черными var boardValue = -evaluateBoard(game.board()) game.undo(); if (boardValue >bestValue) ( bestValue = boardValue; bestMove = newGameMove ) ) return bestMove; );

Єдиним відчутним покращенням є те, що тепер наш алгоритм з'їсть фігуру, якщо це можливо:

Чорні грають за допомогою простої функції оцінки

Подивитися, що вийшло на цьому етапі, ви можете на JSFiddle .

Крок 3. Дерево пошуку та мінімакс

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

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

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

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

Візуалізація мінімаксу у штучному положенні. Найкращий хід для білих - b2-c3, так ми можемо гарантувати, що дістанемося до позиції, де оцінка дорівнює -50

Var minimax = function (depth, game, isMaximisingPlayer) ( if (depth === 0) ( return -evaluateBoard(game.board()); ) var newGameMoves = game.ugly_moves(); if (isMaximisingPlayer) ( var bestMove = -9999; for (var i = 0; i< newGameMoves.length; i++) { game.ugly_move(newGameMoves[i]); bestMove = Math.max(bestMove, minimax(depth - 1, game, !isMaximisingPlayer)); game.undo(); } return bestMove; } else { var bestMove = 9999; for (var i = 0; i < newGameMoves.length; i++) { game.ugly_move(newGameMoves[i]); bestMove = Math.min(bestMove, minimax(depth - 1, game, !isMaximisingPlayer)); game.undo(); } return bestMove; } };

З мінімаксом наш алгоритм починає розуміти основну тактику шахів:

Мінімакс з рівнем глибини 2

Подивитися, що вийшло на цьому етапі, ви можете на JSFiddle .

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

Крок 4. Альфа-бета-відсікання

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

З альфа-бета-відсіканням ми отримуємо значне покращення мінімаксу, як показано в наступному прикладі:

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

Подивитися, що вийшло на цьому етапі, ви можете на JSFiddle .

Крок 5. Поліпшена функція оцінки

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

1997, Нью-Йорк. Чемпіон світу з шахів Гарі Каспаров програє комп'ютеру «Deep Blue» фірми IBM, і ця битва стає найбільшою шахівницею всіх часів і народів. Про цю гру будуть говорити як про «останню битву людського розуму», багато хто порівнюватиме її з першим польотом братів Райт і висадкою астронавтів на Місяць.

20 липня – у міжнародний день шахів – розповімо вам про те, що було далі. А також про те, в чому штучний інтелект поступається людському, причому тут Алан Т'юрінг. Слово Гаррі Каспарову, чемпіону світу з шахів та автору книги.

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

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

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

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

Це дало мені ідею. Після того, як мої матчі з Deep Blue привернули таку пильну увагу, я хотів продовжувати шахові експерименти, незважаючи на те, що IBM від них відмовилася.

Мій план, простіше кажучи, був таким: якщо ви не можете їх перемогти, то приєднайтеся до них.

Я подумав: що якщо людина та машина будуть не противниками, а партнерами? Задум втілився в році в іспанському Леоні, де відбувся перший матч із просунутих шахів (advanced chess). Обидва партнери мали під рукою персональний комп'ютер і могли використовувати під час партії будь-яку програму на свій вибір. Мета полягала в тому, щоб вийти на новий, найвищий рівень гри завдяки синтезу найсильніших сторін людського та машинного інтелекту. Хоча, як ми побачимо далі, не все пройшло так, як замислювалося, разючі результати цих «битв кентаврів» переконали мене в тому, що шахи, як і раніше, можуть запропонувати дуже багато в такій галузі, як взаємодія людського розуму та штучного інтелекту.

До цього переконання я дійшов далеко не першим. Шахові машини були святим Граалем задовго до того, як люди навчилися створювати їх. І ось наука нарешті отримала доступ до цієї чаші — а я виявився тією людиною, яка тримає її в руках. Переді мною стояв вибір: відхилити дзвінок або прийняти його. Як я міг устояти? Це був шанс ще більше підняти популярність шахів та розширити аудиторію, завойовану ними після знаменитого матчу між Боббі Фішером та Борисом Спаським за часів холодної війни та після моїх поєдинків за світову корону з Анатолієм Карповим. Це дозволило б залучити у світ шахів армію щедрих спонсорів, особливо у складі високотехнологічних компаній. Так, корпорація Intel у середині 1990-х років спонсорувала цілу серію турнірів з швидких та класичних шахів та повний цикл чемпіонату світу, включаючи мій титульний матч з Вішванатаном Анандом, що проходив на верхньому поверсі Світового торгового центру. До того ж мною керувала непереборна цікавість. Невже машини справді можуть навчитися грати у шахи так само добре, як чемпіон світу? Невже вони справді здатні мислити?

Цікаво, що
перша шахова програма з'явилася раніше першого комп'ютера.

Її розробив геніальний британський математик Алан Т'юрінг, який зламав код нацистської шифрувальної машини «Енігма». В 1952 він написав на папері алгоритм, за допомогою якого машина могла б грати в шахи, - тільки в ролі центрального процесора виступав сам математик. "Паперова машина Тьюринга" виявилася цілком компетентним гравцем. Причина її конструювання виходила за межі особистого інтересу Тьюринга до шахів. Вміння грати в шахи здавна вважалося частиною людського інтелекту, і створення пристрою, здатного перемогти людину в цій грі, мало знаменувати появу справді розумної машини.

Ім'я Алана Тьюринга також назавжди пов'язане з назвою запропонованого ним уявного експерименту, пізніше проведеного в реальності і названого «тест Тьюринга». Суть його в тому, щоб визначити, чи зможе комп'ютер обдурити людину таким чином, щоб той думав, що має справу з людиною, і якщо зможе тест вважається пройденим. Ще до мого першого матчу з Deep Blue комп'ютери почали проходити те, що можна назвати «шаховим тестом Т'юрінга». Вони, як і раніше, грали досить погано і часто робили явно нелюдські ходи, але іноді їм уже вдавалося розігрувати партії, які б цілком доречно й у пристойному людському турнірі. З кожним роком машини ставали все сильнішими, але в процесі їх еволюції ми дізнавалися більше про самих шахів, ніж про штучний інтелект (ІІ).

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

По суті, «розум» Deep Blue нічим не відрізнявся від «розуму» будильника, що програмується.

Думка про це тільки посилювала для мене гіркоту поразки — програти будильнику, що програмується, нехай навіть вартістю $10 млн?!

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

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

Маю визнати, що повторний аналіз кожного аспекту того безславного поєдинку з Deep Blue виявився нелегкою справою.

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

Публікацій, присвячених Deep Blue, безліч, але ця книга — перша й єдина, де зібрані всі факти та вся історія розповідається так, як її бачу я. Незважаючи на болючість спогадів, це був повчальний та сприятливий досвід. Мій великий вчитель Михайло Ботвінник, шостий чемпіон світу з шахів, навчав мене шукати істину в кожній позиції. І я спробував виконати його завіт і пошукати істину в суті Deep Blue.

Ілюстрація: Shutterstock

Розроблена інженерами Массачусетського технологічного інституту. Фішер тричі поставив мат комп'ютеру та здобув беззаперечну перемогу. У своїх листах шахіст писав, що програми допускають «грубі помилки», а самі комп'ютери називав «марними шматками заліза».

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

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

Боббі Фішер після перемоги над комп'ютером Фото: Getty Images

Схоже, що люди мають якусь вроджену любов до інтелектуальних ігор. Коли 1649 року короля Англії Карла I засудили до смерті, він узяв із собою страту дві речі - біблію і набір шахів. Відомий художник XX століття Марсель Дюшан на піку своєї кар'єри раптово виїхав до Аргентини і почав займатися вирізанням шахових постатей з дерева, та й загалом захопився шахами. У ХІХ столітті у Японії відбулася загадкова історія, що з грою го. За легендою духи підказали одному знаменитому гравцю три блискучі ходи. В результаті він зміг перемогти, а його противник після партії впав на підлогу, захлинувся кров'ю та помер.

Комп'ютери далекі від всієї цієї містики, але лише за кілька десятків років вони вивчили інтелектуальні ігри глибше, ніж людство за тисячоліття. У 2014 році компанія придбала фірму DeepMind за $400 мільйонів для «проведення найнезвичайнішого та найскладнішого дослідження, кінцевою метою якого є розгадка сутності інтелекту». Зокрема вчені хотіли навчити комп'ютер грати у го. Ця гра значно складніша за шахів. У 1985 році один тайванський промисловий магнат сказав, що заплатить $1,4 мільйона за програму, яка зможе перемогти найкращого гравця в го. 1997 року магнат помер, а через три роки у його пропозиції минув термін дії - ніхто так і не зміг забрати приз.

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

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

Що стосується шахів, то людство втратило пальму першості в них ще за 20 років до цих подій, коли шахіст Гаррі Каспаров програв суперкомп'ютеру IBM Deep Blue. Шахи і го – не єдині ігри, яким намагаються навчити ІІ. Комп'ютер намагалися навчити шашкам, коротким нардам, реверсі, покеру та багатьом іншим настільним іграм. І людський інтелект уже не може зрівнятися у них зі штучним. Почасти це сталося через розвиток технологій. Наприклад, ще 1997 року комп'ютер Deep Blue займав 259-е місце у списку найшвидших суперкомп'ютерів у світі і міг виконувати близько 11 мільярдів операцій на секунду. Зараз завдяки сучасним алгоритмам навіть ваш смартфон здатний перемогти Каспарова.

Гаррі Каспаров проти комп'ютера Deep Blue. Ліворуч один з інженерів IBM Сюн Фейсюн. Фото: Getty Images

Такі досягнення ІІ викликали у людей цілком людські емоції: смуток, пригніченість та розпач. Після того, як Лі Седоль зазнав поразки від AlphaGo, він пережив екзистенційну кризу. «Я засумнівався у людській винахідливості, – зізнався він після матчу. - Я засумнівався, чи всі ходи в го, які я знаю, правильними». За словами одного з очевидців, після поразки Лі виглядав так, ніби йому було «фізично погано». Каспаров почував себе після програшу комп'ютеру не краще. Коли він повернувся до готелю, він просто роздягнувся, ліг у ліжко і дивився в стелю.

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

Deep Blue вперше показав громадськості, що комп'ютер здатний перевершити людину у вирішенні інтелектуальних завдань. «Тоді це викликало шок, – сказав Мюррей Кемпбелл, один із творців Deep Blue. - Зараз ми поступово звикаємо до цієї думки». Тим не менш, незрозуміло, що чекає людство в майбутньому. Як можна використати в реальному світі досягнення в іграх? Відповідь Кемпбелла це питання звучить песимістично. «Важко знайти добрий приклад застосування таких успіхів у настільних іграх, – сказав він. - На початку 90-х один із співробітників IBM на ім'я Геральд Тезауро намагався навчити ІІ грі в нарди і зробив деякі досягнення у стимульованому навчанні. Нині його методи часто використовуються у робототехніці. Однак його випадок – скоріше виняток із правил».

Історія розвитку автоматики та обчислювальної техніки дивним чином пов'язана з шахами. У XVIII ст. "Шахові автомати, що думають", служили для фокусів і містифікацій. Перший апарат із справжнім штучним інтелектом, створений в Іспанії на початку ХХ ст., був здатний поставити мат королем і човном шахісту, що грає королем. Мабуть, не випадково і те, що одним із перших справді інтелектуальних завдань, поставлених перед програмістами ще на зорі обчислювальної техніки, була гра в шахи. Про шахові програми та зв'язок цієї давньої гри з розвитком технологій штучного інтелекту розповідає один із тих, хто створював перші шахові програми, доктор технічних наук, професор Володимир Львович Арлазаров.

– Володимире Львовичу, а як прийшли до думки, що комп'ютер може вирішувати інтелектуальні завдання?

– Коли з'ясували, що комп'ютери вміють не лише обчислювати, як це було вигадано із самого початку, що за арифметичними діями є логічне дійство, яке не лише виконує допоміжні функції у діяльності обчислювальних програм, а й за допомогою якого можна вирішувати самостійні завдання, то стало ясно: варто спробувати покласти комп'ютер інтелектуальні завдання. Десь з кінця 40-х років і до кінця 50-х це активно обговорювалося, більше того, ставилися статі філософські питання: а може, комп'ютери будуть розумнішими за людей? І що тоді? І все цілком серйозно. Нині такі питання не ставлять, таки 40 років минуло. Тоді, на зорі обчислювальної техніки, ми тільки усвідомили, що можуть робити машини. Ми зрозуміли, що людський мозок є пристрій, аналогічний обчислювальній машині, і в тисячу, в мільйон разів потужніший, але він принципово трохи відрізняється. Стало зрозуміло, що принаймні більшість раціональних завдань, які вирішує людина, можуть бути поставлені перед машиною. Отже, можна спробувати написати програми, які ці завдання вирішують. Одну, дві, тисячу... адже людина теж вирішує не безліч завдань. І можна, як кажуть, всю інтелектуальну діяльність людини запрограмувати.

- А чому все ж таки вирішили звернутися до гри?

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

– А чому з ігор вибрали таки шахи? Можливо, традиція?

– Чому тільки шахи? Пробували і хрестикиноліки, інші ігри. Але у шахів чимало переваг перед іншими іграми. Якщо в простих іграх машина обігрує людину, це нікого не дивує. Шахи – гра складна, і перемога комп'ютера тут значуща. Потім у шахах, на відміну від інших ігор, багато диференційованих критеріїв якості, тобто можна визначити: машина грає добре, машина грає краще, краще, краще. Багато інших іграх подібні градації встановити дуже важко. У деяких з них машину або навчають грати абсолютно точно, і тим самим відразу втрачається будь-який інтерес до гри, або вона грає геть погано. А в шахах, не абстрактних, а, так би мовити, освоєних рівнів стільки, що за їх допомогою можна визначити клас гри машини.

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

– Із самого початку поступово освоювалася методика вирішення завдання шахової гри. В принципі, шахи - гра кінцева, і з математичною строгістю можна довести, що в будь-якій позиції абстрактно існує найкращий хід для кожного із супротивників, а отже, і якийсь результат. Тому потрібно описати алгоритм, у якому ця гра можна розрахувати остаточно. Єдиний недолік такого алгоритму полягає в тому, що він потребує багато часу. І ми не наблизилися до тих порядків часу, які потрібні, щоби розрахувати, скажімо, шахи до кінця з початкової позиції. За минулі п'ятдесят років завдання у сенсі часу так і залишилося нескінченно складним. Ну, нескінченність мінус десять – все одно нескінченність. Але якщо вам потрібен час, скажімо, 10 у 100-му ступені років, і ви прискорите машину, скажімо, у 100 разів, і отримаєте 10 у 98-му ступені років, то вам навряд чи від цього стане легше. Тому основний алгоритм - перебірний, тривіальний: якщо я піду так, то противник має стільки можливостей. Варіанти ростуть у геометричній прогресії та утворюють ланцюжки. Але кількість позицій взагалі звичайно, і їх на кожному ланцюжку не так багато. Ланцюжки поєднуються в дерева, які знову ж таки не нескінченні. Щоправда, зростають вони у геометричній прогресії, і кількість ланцюжків збільшується. Так ось, постає важливе питання: чи потрібен повний, до кінця, перебір - до всіх матів, патів, триразових повторень та інших закінчень гри за шаховими правилами? Адже якщо алгоритм веде до позицій, які не є обов'язковими на цьому дереві, то, можливо, все це дерево і не потрібно розглядати. Зауважте собі, що в диспозиції, де білі дають мат в один хід, можна побудувати таке ж нескінченне дерево, але розглядати його не потрібно, а достатньо знайти цей один-єдиний хід. Може, така сама ситуація і в шахах загалом? Взагалі алгоритм перебору, перебору варіантів має відношення до такої кількості вирішуваних людиною завдань, що, якби ми вміли його організовувати якимось дуже оригінальним способом, то він був би, в якомусь сенсі, як би винаходом колеса для людства - одного з фундаментальних відкриттів. Так ось, перебір міг би бути, а може, і є таким колесом штучного інтелекту.

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

- Так Так. Це завдання потрібно було швидко і ефективно вирішувати, і в шахах досить швидко дійшли наступної теоретичної постановки питання: а давайте дивитися не нескінченну кількість ходів, а лише кілька ходів уперед. Скажімо, подивимося на 5 ходів уперед. Це дуже багато. Якщо ви любите шахи і 5 ходів вам здається мало, то давайте візьмемо 10. І тоді машина на 10 ходів, на 20 півходів уперед не буде ні в чому помилятися і гарантує, що через 10 ходів у вас фігур виявиться не менше. Ясно, що ми маємо справу з сильною машиною, що грає. Так що дерево гри доведеться скоротити і вирішувати завдання в більш обмеженому просторі. Інше питання, що це дерево намагаються розглядати в повному обсязі, з допомогою математичних методів відсікання. Про один із них я вже розповідав: якщо є мат в один хід, нема чого переглядати інші варіанти. Інші алгоритми мають евристичний, не влучний характер. У середньому вони працюють правильно, багато абсолютно точних, але можуть і помилятися. Наприклад, ми можемо перебирати не всі ходи, а лише взяття, і прораховувати їх набагато вперед, бо взяття мало. Загальна поглибленість ходів невелика: понад тридцять дві фігури не з'їсти. Тому і довжини ланцюжків невеликі та розгалужень мало. Звичайно, ясно, що на одних взяттях не можна побудувати гру, повинні бути якісь позиційні міркування. Комбінація форсуючих (взяття, шах) та позиційних міркувань, а також деякої глибини перебору – основа всіх існуючих алгоритмів, і вона особливо не змінюється. Інше питання: як відбирати ті ходи, які я розглядатиму далі? Чи на підставі лише простих формальних критеріїв (взяття, шах) чи пов'язувати ці ходи, як шахісти люблять говорити, планом, вигадувати якісь ланцюжки, які мають якусь спільну властивість? Принаймні про це написано дуже багато серйозних робіт, що мають практичне застосування. Не дарма створенням шахових програм займаються досить солідні фірми.

– А коли з'явилися перші шахові програми?

– Реальні шахі програми вперше з'явилися десь наприкінці 50-х років в Америці, а потім десь на початку 60-х років – і у нас. Програми були дуже слабкі, бо тоді були й гранично примітивні машини і не звичне ще до новизни наше мислення. Включилися ми до цієї справи приблизно 1963 року. Тоді на наших вітчизняних машинах і були якісь матчі. На мою думку, в 1967 році був перший матч СРСР - США. Він так називався, хоч, звичайно, проходив між двома колективами, а не країнами. Це був матч між нашою програмою, розробленою в Інституті теоретичної та експериментальної фізики, та програмою Джона Маккарті, дуже відомої в комп'ютерному світі людини, однієї зі творців мов програмування, який захоплювався тоді шаховими програмами. Ходи передавалися по телеграфу, тоді ніяких мереж не було.

– І хто переміг?

– Ми тоді виграли 3:1. Грали 4 партії. Робився хід у день, оскільки в американців були більш потужні та глибокі програми, які довго думали, а ми грали на різних варіантах програм, які думають і швидко, і повільно. Наш виграш був першим нашим здобутком. Цей напрямок почав поступово розвиватися і особливо активізувався в 70-ті роки. Приблизно 1974 року відбувся перший чемпіонат світу серед шахових програм у Стокгольмі. Брало участь близько восьми програм, у тому числі й наших. І ми тоді теж перемогли та стали першими чемпіонами світу. З того часу чемпіонати світу проводяться регулярно, кожні 3 роки. Ми в них брали участь ще 2 рази - в 1977 р. і в 1980 р. Лаврів ми тоді не здобули, тому що в 1977 р. поділили 2-е та 3-тє місце (брало участь багато шахових програм, були навіть регіональні відбори), а 1980 р. - 4-те та 5-те місце. Загалом, потихеньку відкочувалися. Справа в тому, що до цього моменту вже був величезний прогрес у обчислювальній техніці, а ми все ще грали на комп'ютерах досить застарілих. І до 1980 р. нам стало ясно, що змагатися на тих машинах, на яких ми працюємо, втратило будь-який сенс, та й взагалі в Росії роботи в галузі шахових програм стали сходити нанівець. Хоча й було чимало цікавих теоретичних робіт. Трохи пізніше створили першу, мабуть, програму, яка пройшла світом, вона вміла абсолютно точно розігрувати складний ендшпіль, тобто ферзь і піша проти ферзя, або тура і піша проти човна. Такі ендшпілі програма просто до кінця розглядала, тобто у будь-якій позиції вона давала ідеально правильний хід. Алгоритм був побудований на трішки відмінних від простого перебору принципах, на повному огляді безлічі позицій. Ну і потім у шахах робили деякі роботи такого характеру. А з практичною грою ми тоді розпрощалися, бо різниці у швидкостях були вже в сотні разів. Але чемпіонати тривали, і розвиток шахових програм просунулося на зовсім новий рівень, як тільки все перейшло на РС. В результаті широкої комерціалізації, у шахові програми стали вкладати величезні гроші, одразу всі засекретили. А раніше вони належали вченим, які, якщо не змусити навмисне, не приховують своїх досягнень, а, навпаки, пропагують їх. У 1980 р. ми вперше відчули, що настав час комерційного програмування. Цей світ, звісно, своєрідний. По-перше, тому що в нього вкладаються гроші, по-друге, тому що з нього витягуються гроші. Хоча і існують журнали з шахових програм, але за останні 15 - 17 років реальний обмін ідеями сильно зійшов нанівець, тому що на PC вони стали величезним бізнесом.

- Але комерція стимулює розвиток ринку шахового ПЗ?

– Раніше комп'ютерні змагання приурочувалися до форумів обчислювальної техніки. Є така організація - МФІ (Міжнародна федерація з інформатики) і зазвичай до її конгресу приурочувалися чемпіонати світу. Нині вони стали абсолютно самостійними заходами, доволі престижними. Таких програм уже сотні та сотні. Сам рівень програмування і рівень наших знань вже такий, що зробити простеньку шахову програму не складає жодної праці. Це нормальна студентська робота. Я її якраз і доручаю якомусь студенту. Обіграти шахову програму стало так би мовити розхожим місцем.

– Але, як завжди, нижчий рівень спрощується, а найвищий ускладнюється?

- Саме так. Тому останні програми, ті, що зараз перемагають, зокрема, програма, яка перемогла Каспарова, стали набагато сильнішими. Глибина перебору значно зросла і, звичайно, це результат наших математичних поступів, а частково просто прогресу обчислювальної техніки. Адже якщо раніше розгляд 1000 позицій за секунду вважалося дуже багато, то зараз у тих деревах, про які ми з вами вже говорили, розглядається понад мільйон позицій. А зайвий мільйон – це кілька рівнів ходів за правильного відбору. А кожен рівень глибини перебору посилює програму. Кожен рівень на хід уперед – це приблизно розряд, і, скажімо, глибина перебору в чотири ходи – це третій розряд, у п'ять ходів – уже другий розряд. Коли ми досягаємо рівня в 11–13 ходів – це майстер-рівень і далі грати з машиною досить складно. Звичайно, зараз лідирують американці, бо вміють вкладати великі гроші у такі речі.

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

– Напевно ніхто не скаже, бо це предмет спекуляції. Були досить сильні програми з мінімальними знаннями, свідомо мінімальними, спеціально для того, щоб подивитися, що можна вичавити з чистої математики. Якогось моменту це було пов'язано з комерціалізацією і особливо з тим, що почали робити максимально сильні програми - не важливо вже за рахунок чого. Але частково через те, що робота із закладеними знаннями - самостійне завдання, їх стало дуже багато. Насамперед було створено величезний довідник. Нині довідники – це сотні тисяч позицій. Потім дуже багато шахового інтелекту завжди вкладають в оцінку позицій. Вона зводиться, звичайно, і до ігрового матеріалу, що є тривіальним, і до деяких позиційних факторів. Так ось, позиційні чинники - суто шаховий інтелект, який, звісно, програмується, але тут його закладається багато і він постійно вдосконалюється. І чим більше факторів туди вкладається, тим сильніша програма. У якомусь сенсі вміння оцінити позицію та глибина перебору – речі взаємозамінні. Якби ми вміли оцінювати позицію геніально, нам було б достатньо спробувати всі перші ходи. Це як крайній приклад. Зрозуміло, найкраща оцінка позиції відповідно більше впливає глибину перебору. Такий другий, важливий спосіб. Існує досить багато програм, де шаховий інтелект закладається у вибір самих розглянутих варіантів, тобто якихось суто шахових міркувань, якихось планів. Таких міркувань чимало, що обмежує коло перебору. Область їхньої дії не дуже широка, і інтелектуально-шахові специфічні дані уповільнюють перебір. До речі, саме за інтелектуальні речі колись дуже сильно боровся Ботвинник. Він був ентузіастом машинних шахів і вніс туди деякі ідеї. Хоча йому так і не вдалося створити діючу програму, проте його авторитет був тоді дуже високий. Так от, він дуже засмучувався, що загалом напрям не такий "інтелектуальний", як йому хотілося б, і в програми вкладався дуже обмежений обсяг чисто шахових знань.

– А спеціалізовані шахові комп'ютери? Вони, мабуть, чи діють саме методом генерації?

- Звичайно звичайно. По-перше, у сенсі генерації перебір схематичний. По-друге, не менш важливі всякі таблиці позицій, тому що в шахах повторюваність позицій дуже велика. Ви підете Е4Е6D4 або D4Е6Е4 - позиція вийде одна і та ж, а це всього лише 3 півходи. А коли ми починаємо заглиблюватись, то повторюваність позицій дуже велика. По-третє, технічна область. Взагалі свого часу ми будували теорії про те, для яких позицій локальні зміни принципово не можуть вести до зміни форсованих варіантів, як створювати свого роду шаблони. Шаблони таких варіантів добре вкладаються в різні суто технічні схеми комп'ютера. Звісно, дуже важливі довідкові схеми.

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

– Зрозуміло, що в плані конструктивності таке завдання сьогодні не вирішуване, не актуальне. Хоча багато інтелектуальних завдань зараз вирішуються, такі, наприклад, як розпізнавання тексту. Ви можете покласти в сканер листок з текстом і отримати його на екрані Word. Він сам прочитається, кожна літерка розпізнається. Реально ми просунулися у багатьох інтелектуальних завданнях. Одні вже вирішені, інші вирішуються. У чомусь виходить порівняно краще, ніж за участю людини, у чомусь поки що гірше. Можна навести багато прикладів практичних завдань. Що ж до універсального штучного розумового механізму, це, швидше, проблема філософська, ніж практична. Адже навіть для такої простої гри, як шахи, нам знадобилося 30 - 40 років, щоб фактично чогось досягти. Будь-яка філософія ґрунтується на думках. Кожен думає, що він має рацію, а може, кожен має рацію по-своєму. Наприклад, я все життя мав справу зі штучним інтелектом і вважаю, що мозок людини не більш ніж велика обчислювальна машина, отже, не можна сказати, що неможливо створити аналогічну їй. Питання у її потужності, швидкісних характеристиках, у наповненні її знаннями. Нічого незбагненного тут немає. Це моя особиста думка. Але є й інші думки. Звичайно, якщо ми визнаємо божественну природу людини, то тоді вже треба вибрати один із двох гносеологічних варіантів. Або так, ми маємо божественну природу, але вона пізнана. У такому разі нам не вдасться відтворити по-справжньому те, що зумів зробити Господь Бог, але принаймні ми зможемо Його творіння хоча б частково відтворити. Або ми стоїмо на позиції агностицизму, і тоді вона непізнавана, і питання повністю знімається. Виходить, деякі завдання людський мозок вирішує - і тут ні в кого сумнівів немає. Але наздогнати мозок ми не можемо, тому що, з одного боку, він створений Богом, а з іншого - пізнати його ми не можемо. Всі три позиції пов'язані з вірою, оскільки в реальності необов'язково пізнавати всі функції мозку. Якщо ми зробимо машину, за потужністю рівну мозку, їй ні до чого думати так, як мозок. Вона по-іншому працюватиме.

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

– Повно програм, які спеціально націлені на те, щоб створювати поняття, які абстрагуються від існуючого фактичного матеріалу. Такі програми добре працюють. Інше питання, що людина вміє створювати ці поняття як би за своїми власними законами, які він сам собі вигадує. Всі наші спроби перекласти ці його закони на мову логіки алгебри виявляються безперспективними. У людини набагато потужніший розумовий механізм, який ми просто не знаємо. Ми нічого не вміємо робити "взагалі". Ми створюємо необхідні нам формулювання, але висловити їх у точних машинних завданнях не можемо. До механічних завдань все зводиться насилу, і навіть якщо зводиться, то повільно. Напевно, ми поки що не знаємо пряміших шляхів до досягнення мети. Закласти в комп'ютер можна все, що завгодно. Питання в тому, що людина здатна маніпулювати цими знаннями весь час, але вона ще не вміє змусити робити те саме машину через обмежений обсяг і швидкість даних.

- Але, можливо, немає сенсу змушувати машину маніпулювати знаннями?

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

- Володимире Львовичу, скажіть, якби зараз знову була зоря комп'ютерної техніки, варто було б займатися шаховими програмами? Чи вони настільки сприяли прогресу?

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

Предмет, вік учнів

Інформатика та ІКТ,10-11клас

Коротка інструкція проекту

Проект розроблено в рамках дисципліни "Інформатика та ІКТ" для учнів 10-11 класу

Питання, що спрямовують проект

Основне питання

Чи може комп'ютер замінити людину?

Проблемні питання

1. Чи може ЕОМ сама ставити завдання та вирішувати їх?

2. Чи здатний комп'ютер відтворити всі дії та думки людини?

3. Чи здатна ЕОМ керувати людиною?

Навчальні питання

1. Які завдання вирішує комп'ютер?

2. Чи самонавчається ЕОМ?

3. Чи можуть автомати замінити людину?

4. Штучний інтелект = Інтелект людини?

5. Чи потрібно керувати роботою ЕОМ?

6. Чи можливо поставити робота "на чолі столу"?

7. Чи вміє думати комп'ютер?

8. Чи можна замінити людський мозок штучним?

9. Чи готова людина доручити всю роботу роботам?

План проведення проекту

Подання проблемної ситуації:

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

Робота над проектом:

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

Оформлення результатів проектної діяльності:

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

Захист проекту, опонування, дискусія:

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

Після закінчення роботи:

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