Шахи здаються глибоко людським заняттям. Вони потребують інтуїції. Вони потребують стратегічного передбачення. Тому ідея про те, що холодна машина може обіграти гросмейстера, здається майже чарівною. Але шаховий ІІ не грає у гру так, як це робимо ми. Він зводить дошку до чистої математики.
Згадайте, як ви вчилися грати у шахи. Ви починали з основ. Як ходить кінь. Як ходить слон. Як тільки правила ставали зрозумілими, ви могли реально пересувати фігури. Ранні поразки були невдачами. Вони були точками даних. “Я не бачив, що це мат”, – говорили ви. Ваш мозок убирав ці моменти. Ви запам’ятовували шахові позиції. Ви навчали прийоми. Ви вбирали нюанси.
Комп’ютери нічого цього не роблять. Вони не «думають» у біологічному сенсі. Вони обчислюють. Вони застосовують формули для знаходження кращого ходу. У міру розвитку цих двигунів їх точність швидко зростала. Сучасні ІІ-калькулятори – найсильніші гравці на Землі. Вони грають наосліп. Невблаганно. Грунтуючись виключно на обчисленнях.
Математика за ходами
Люди покладаються на розпізнавання патернів. Ми впізнаємо знайому пастку, бо бачили її раніше. Ми відчуваємо зміну динаміки. Комп’ютери нічого не відчувають. Вони розраховують мільйони позицій на секунду. Вони оцінюють кожен можливий результат. Потім вибирають той, який має найвищий числовий показник.
Не магія. Це груба логічна сила. І вона дуже ефективна.
Шаховий штучний інтелект виглядає як магія, але у своїй основі це наосліп виконувані обчислення методом грубої сили. Він не думає. Він обчислює.
Почніть зі стандартної дошки. Білі ходять першими. У вас є 20 варіантів. Два коні можуть вистрибнути. Вісім пішаків можуть зрушити на одну або дві клітини вперед. Ви обираєте один хід.
Чорні бачать ту саму дошку. Також 20 ходів.
Тепер білі знову ходять. Дошка змінилася, тому варіанти зміщуються, але їх однаково приблизно 20. Потім чорні відповідають. І так далі.
Кількість шляхів вибухає.
Білі роблять хід. Чорні мають 20 відповідей. Це 400 позицій. Білі відповідають на кожну з них. 8000 позицій. Чорні атакують у відповідь. 160000 позицій.
Саме так комп’ютер бачить дошку. Не як мистецтво. Як дерево.
Математика шахів
Якщо розгорнути це дерево, щоб охопити всі можливі партії у шахи, кількість позицій на дошці буде астрономічною.
Близько 10^120.
Це одиниця, за якою слідують 120 нулів.
Щоб зрозуміти масштаб, розглянемо вік Всесвіту. Пройшло близько 10^26 наносекунд з моменту Великого вибуху. Весь спостерігається Всесвіт містить приблизно 10^75 атомів. Навіть якщо підрахувати кожну зірку в кожній галактиці Чумацького Шляху та за його межами, ви все одно не зможете зрівнятися з кількістю можливих партій у шахи.
Шахи складні. Занадто складні для того, щоб будь-який комп’ютер міг вирішити їх повністю.
Жодна машина ніколи не буде обчислювати все дерево. Їй це не потрібне.
Наскільки глибоко заглядає комп’ютер?
Натомість двигун дивиться вперед. Він будує дерево глибиною в п’ять, десять чи двадцять ходів.
Припустимо, в середньому 20 ходів на позицію:
- Дерево глибиною в 5 ходів охоплює 3,2 мільйони позицій.
- Дерево глибиною 10 ходів охоплює 10 трильйонів позицій.
Глибина залежить від апаратного забезпечення. Найшвидші шахові комп’ютери оцінюють мільйони позицій на секунду. Вони прорізуються крізь дерево, знаходячи найкращий шлях у межах цього обмеженого вікна.
Але бачити позиції недостатньо. Комп’ютер потрібно знати, яка з них хороша.
Оцінка дошки
Тут входить у дію функція оцінки.
Як тільки двигун генерує дерево, він надає оцінку кожному вузлу. Це не просто підрахунок фігур. Звичайно, проста версія може віднімати фігури чорних із фігур білих. 11 білих фігур мінус 9 чорних фігур дають оцінку 2.
Це наївно. Це ігнорує матеріальну цінність. Ферзь коштує більше ніж пішака. Слон краще за коня у відкритих позиціях.
Таким чином, формула стає складнішою. Програмісти додають ваги типів фігур. Вони додають бонуси за контроль центру. Вони штрафують за вразливого короля. Вони враховують структуру пішаків.
Незалежно від того, наскільки складними ці параметри, результат завжди — одне число.
Одна оцінка, що становить «хорошість» цього стану дошки.
Як гросмейстери використовують ІІ
Це стосується не лише машин. Елітні люди використовують цю ж логіку як зброю.
Гросмейстери не грають проти комп’ютерів, щоб перемогти їх. Вони грають з ними, щоб стати краще.
ІІ-движки надають глибокий аналіз, який людське око не може помітити. Вони знаходять ходи, які логічно обґрунтовані, але психологічно контрінтуїтивні. Вони знаходять ресурси у програних позиціях, від яких люди здаються дуже рано.
Ось як елітні гравці використовують їх:
- Аналіз партій: Введення минулих матчів для виявлення втрачених можливостей.
- Дослідження стратегій: Перевірка альтернативних дебютів, що суперечать традиційній теорії.
- Розуміння позиційної гри: Побачення «істини» складної середньої партії, прорахованої на десять ходів уперед.
Це не обман. Це тренування.
У двигуна немає інтуїції. Має математику. Але, вивчаючи пропозиції двигуна, людські гравці будують глибшу і точнішу власну інтуїцію. Вони навчаються тому, що математика має на увазі про тиск, простір і час.
Дошка статична. Можливості нескінченні. Але поки що комп’ютер завжди знаходить найкращий хід на наступні десять кроків.
Нам просто треба наздогнати його.
Як насправді працює логіка мінімаксу AlphaGo
На діаграмі зображено дерево рішень із трьох рівнів. Воно проектує три ходи вперед. Кінцеві позиції дошки вже оцінені.
Комп’ютер грає білими. Чорні щойно зробили хід. Дошка знаходиться у верхній частині дерева. Білі мають три можливі відповіді. З кожного із цих трьох ходів чорні можуть відповісти трьома способами. Це створює 9 позицій дошки. З кожної з цих дев’яти позицій білі можуть зробити два можливі ходи.
Насправді фактор розгалуження значно вищий. З будь-якої позиції можна зробити близько 20 ходів. Намалювати таке дерево було б хаотично. Тому діаграма спрощена.
Щоб вирішити, який крок зробити наступним, комп’ютер аналізує це дерево. Він працює знизу нагору. Обчислення спрямовані на пошук найкращих позицій для кожної з можливих позицій, які займуть чорні. Він вибирає максимум.
Це суть алгоритму мінімаксу. Комп’ютер передбачає оптимальну гру з обох боків. Він мінімізує максимальну можливу втрату. У цьому конкретному розгалуженні він максимізує свою вигоду.
Комп’ютер працює знизу вгору, вибираючи максимальне значення для білих ходів і мінімальне — для чорних ходів.
Не магія. Це математика. Дерево – це просто уявлення можливостей. Функція оцінки надає оцінку кожному листовому вузлу. Потім алгоритм поширює ці оцінки нагору.
Білі хочуть максимізувати оцінку. Чорні хочуть мінімізувати її. Комп’ютер вибирає шлях, що веде до найбільшої оцінки для білих, припускаючи, що чорні гратимуть оптимально, щоб знизити її.
Ця логіка масштабується. Вгору. І ще вище. Поки що дерево не стає занадто великим для обчислень. Тоді використовуються евристики. Але ж тут? Це чистий розрахунок.
Передбачається, що чорні виберуть найгіршу для білих позицію. Береться мінімальне значення.
Потім вибирається максимум із цих трьох верхніх чисел: 7. Саме цей хід робить комп’ютер.
Після того як чорні роблять хід у відповідь, весь цикл перезапускається. Генерується нове дерево. Усі позиції на дошці оцінюються наново. Машина вважає свій наступний крок.
Це алгоритм Minimax. Він чергує вибір максимумів і мінімумів під час руху по дереву рішень.
Відсікання Alpha-Beta прискорює процес. Воно працює приблизно вдвічі швидше. Використовує значно менше пам’яті.
Процес повністю механічний. Тут немає мислення. Лише грубий розрахунок. Функція оцінки застосовується до кожної можливої позиції дерева заданої глибини.
Це добре працює. На досить швидкому комп’ютері алгоритм дивиться далеко вперед. Він дуже добре грає.
Додайте методи навчання. Змініть функцію оцінки на основі попередніх партій. Машина згодом покращує свої навички.
Але пам’ятайте про це. Це зовсім не схоже на людське мислення.
Коли ми зрозуміємо, як працює людське мислення, і створимо комп’ютер, який використовує ці принципи для гри в шахи, ми дійсно досягнемо чогось значущого.
Потужність сучасних шахових двигунів
Кожна система шахів на базі ІІ спирається на потужний двигун.
Цей двигун поєднує алгоритми пошуку. Використовує функції оцінки. У просунутих випадках застосовує машинне навчання.
Шахові двигуни тепер є абсолютними лідерами. Вони стабільно перевершують навіть найкращих людських гросмейстерів.
Чи то завдяки грубим обчисленням чи адаптивному навчанню, ІІ змінив ландшафт. Це незамінний інструмент для гравців, які прагнуть аналізувати партії та покращувати стратегії.
Ми оновили цю статтю спільно з технологіями ІІ, потім переконалися, що вона перевірена фактами та відредагована редактором HowStuffWorks.
