Покроковий посібник зі створення простого шахового ШІ

Давайте вивчимо кілька основних концепцій, які допоможуть нам створити простий шаховий ШІ:

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

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

Остаточний алгоритм ШІ ви можете переглянути тут на GitHub.

Крок 1: Перемістіть генерацію та візуалізацію дошки

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

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

Ми почнемо із створення функції, яка просто повертає випадковий хід з усіх можливих ходів:

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

Крок 2: Оцінка позиції

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

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

Єдиним відчутним поліпшенням є те, що наш алгоритм тепер захопить фрагмент, якщо зможе.

Крок 3: Пошук дерева за допомогою Minimax

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

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

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

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

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

Крок 4: Обрізка альфа-бета

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

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

Обрізка альфа-бета не впливає на результат алгоритму мінімаксу - вона лише пришвидшує.

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

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

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

Крок 5: Покращена функція оцінки

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

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

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

Висновки

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

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

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

  • порядок переміщення
  • швидше переміщення поколінь
  • та оцінка конкретної гри.

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

Дякуємо за читання!