На шляху до Deep Blue: покрокове керівництво по створенню простого ШІ для гри в шахи [*]


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

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

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

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

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

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

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

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

var calculateBestMove = function (game) { //Генерація усіх ходів для цієї позиції var newGameMoves = game.ugly_moves (); return newGameMoves[Math.floor (Math.random () * newGameMoves.length)];};

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

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

Подивитися, що вийшло на цьому етапі, ви можете на 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. Поліпшена функція оцінки

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

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

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

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

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

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

Висновок

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

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

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

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

Переклад статті "A step - by - step guide to building a simple chess AI"

Залишити відповідь

Ваша e-mail адреса не оприлюднюватиметься. Обов’язкові поля позначені *