На шляху до Deep Blue покроковий посібник зі створення простого ІІ для гри в шахи

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Ми будемо використовувати трохи скориговану версію квадратних таблиць, спочатку описаних у вікі Chess Programming.

Візуалізація квадратних таблиць. Ми можемо зменшити або збільшити оцінку залежно від розташування фігури.

Застосувавши це поліпшення, ми отримаємо алгоритм, який непогано грає у шахи, принаймні з погляду простого гравця:

Поліпшена оцінка та альфа-бета-відсікання з глибиною пошуку 3

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

Висновок

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

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

Ось деякі додаткові покращення, які ми могли б внести до алгоритму:

Якщо ви хочете дізнатися більше про шахові алгоритми, зайдіть на Chess Programming Wiki.

---