Програмування шахів — основи

Ідеї: Francois-Dominic Laramee
Переклад + доповнення: Забайловіч Олексій
Постановка задачі
У даній статті я не ставлю перед собою мету ознайомити вас з ультрамодними алгоритмами шахового програмування. Моя мета — дати людині уявлення про те, що таке «штучний інтелект» в додатку до шахів:

а) що являє собою «мозок» шахової програми;
б) яким чином комп’ютер з моря варіантів вибирає єдиний;
в) що необхідно, щоб змусити комп’ютерного опонента грати швидше і т.д.

Новости сайта:замена масла

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

Спосіб зберігання інформації про поточної позиції

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

Правила гри

Тобто «пояснити» залізного друга як в даній ситуації ходити можна, а як заборонено.

спосіб вибору ходу

Мета — надати комп’ютеру засоби для вибору з всіляких доступних ходів одного.

можливість порівняння ходів і позицій

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

користувальницький інтерфейс

Я думаю тут все ясно J

Нижче коротко я розповім вам про кожного з них. Більш детально ми розглянемо їх пізніше.
Представлення даних
Кожен з нас по-різному сприймає вхідну інформацію. На полотні Леонардо Да Вінчі одна людина може побачити Джоконду, інший стодоларову купюру, третій тещу (або зятя). J Те ж саме і в шахах. Два суперника під час гри можуть бачити абсолютно «різні» позиції в один момент часу. На жаль, один з них часом буває неправий, тим більше прикро, якщо їм опиняєшся ти. L

Так чим же комп’ютер повинен відрізнятися від людини, запитаєте ви? Нічим. Комп’ютерні програми, як і люди, не схожі один на одного: «мислять» і зберігають інформацію вони по-різному. Але все ж одні з них грають краще, інші гірше. У чому секрет? З приводу комп’ютерного «мислення» ми ще поговоримо нижче, а зараз торкнемося теми зберігання даних.

У програмуванні дуже важливо правильно вибрати подання даних.

Я думаю, що будь-яка людина в змозі придумати який-небудь спосіб відображення поточної інформації на шахівниці. Наприклад, можна уявити шахівницю як таблицю (масив) розмірами 8х8, де порожній клітці відповідає число — 0, білому королю — 1, і т.д. На жаль, у цього способу поряд з перевагами існує і купа недоліків (поміркувати на дозвіллі — що це за недоліки J). Але прогрес, як мовиться, не стоїть на місці, і був придуманий (здогадайтеся де) досконаліший спосіб відображення інформації, що отримав назву «бітові поля» (Прим.авт. — Cразу ж прошу вибачення за фривольність перекладу; англ. — Bitboards). Це 64-бітове слово (тобто послідовність з 64 цифр, кожна з яких може мати значення 0 або 1), що містить інформацію про один аспект шахової гри. Кожен біт — це одне поле шахової дошки. (Відлік може вестися по-різному: поле а8 — це перший біт послідовності, h1 — останній, наприклад.)

Вони можуть містити:

поля, атаковані чорної пішаком е6 (d5, f5)

00000000
00000000
00000000
00010100
00000000
00000000
00000000
00000000

Для наочності число розбито по 8 біт, що зображують горизонталі дошки.

поля, зайняті білими пішаками (фігурами)
поля, куди може піти білий кінь і т.д.

Таким чином, це досить універсальний спосіб представлення інформації. Але це не найголовніше його перевага. Важливіше якраз те, що багато операцій, які виконуються періодично при аналізі шахової позиції, легко реалізуються як один цикл логічних операцій над «бітовими полями», що істотно прискорює процес пошуку відповіді.
Генерація ходів
Наступним завданням є навчити програму робити ходи. Правила гри в шахи мають багато аспектів, які необхідно враховувати при розробці. Серед них взяття на проході, рокіровка, прохід пішака у ферзі, і т.д.
Методи аналізу
Отже, комп’ютер зможе «бачити» дошку, робити всілякі доступні напрямки руху в даній позиції. Залишилася справа за малим: навчити його вибирати кращий хід і надати йому можливість оцінювати позицію, користуючись якимись критеріями, які ми йому надамо. Що стосується першого, то поки нічого кращого не придумано (принаймні, я не чув про це, якщо хто-небудь знає, то, будь ласка, напишіть), ніж лобове рішення: щоб вибрати кращий з двох ходів, аналізують наслідки кожного з них до якогось моменту, скажімо аналіз на 5-6 ходів вперед, з подальшою оцінкою вийшла позиції. При цьому робиться припущення, що суперники намагаються вибирати кращі відповіді на кожному ході. До речі, останнє припущення лежить в основі алгоритму MiniMax, що є ключовим для всіх шахових програм.

Все б було добре, але … не тут то було. Вам би довелося витратити п’ять, а може й більше, життів, щоб зіграти хоча б одну партію, нехай навіть з найшвидшим комп’ютером. Так що подумайте перш ніж сідати грати партію з комп’ютером J. Згодом я розповім, що було придумано, щоб змусити вашого залізного друга міркувати швидше.
Оцінка позиції
І останнє, що необхідно комп’ютерній програмі, щоб надати вам гідний опір — це дати їй можливість оцінювати позицію. Тобто ввести оцінну функцію, яка по положенню на дошці повертає число, відповідне, з її точки зору, поточному розкладу сил. Це теж не найпростіше завдання, хоча існує величезна кількість підходів до вирішення цієї проблеми.
Висновок
Тепер, коли ви отримали загальне уявлення про те, що ж таке програмування шахів, можна буде приступати до більш детального вивчення вищенаведених компонентів шахової програми.