Комп'ютерні шахи — популярна назва області дослідження штучного інтелекту, яка полягає в створенні програмного забезпечення і спеціальних . Крім того, комп'ютерними шахами називають гру проти комп'ютерної шахової програми, гру програм між собою, а також їхню розробку.
Історія
Історія шахових машин старша, ніж історія комп'ютерів. Ідея створити машину, що грає в шахи, датується ще вісімнадцятим століттям. Близько 1769 р. з'явився шаховий автомат Механічний турок. Він був призначений для розваги королеви Марії-Терезії. Машина справді непогано грала — усередині неї сидів сильний шахіст, який і робив ходи.
Дослідження механічних шахових автоматів припинилися з появою цифрових комп'ютерів близько 1950 р. У 1951 р. Алан Тюрінг написав алгоритм, за допомогою якого машина могла б грати в шахи, тільки в ролі машини виступав сам винахідник. Цей нонсенс навіть дістав назву — «паперова машина Тюрінга». Людині треба було більше ніж півгодини, щоб зробити один хід. Алгоритм був досить умовний, і зберігся навіть запис партії, де «паперова машина» Тюрінга програла одному з його колег. Через відсутність доступу до комп'ютера програма жодного разу не перевірялась в роботі.
Приблизно тоді ж, в 1951 році, математик Клод Шеннон написав свою першу статтю про шахове програмування. Він писав: «Хоча, можливо, це й не має жодного практичного значення, саме питання є, теоретично, цікавим, і сподіватимемося, що вирішення цієї задачі послужить поштовхом для вирішення інших задач аналогічної природи й більшого значення». Шенон також відзначає теоретичне існування найкращого ходу в шахах і практичну неможливість його знайти.
Наступним кроком у розвитку шахового програмування стала розробка в ядерній лабораторії Лос-Аламоса в 1952 році на комп'ютері Maniac 1 (тактова частота 11 кГц) шахової програми для гри на шахівниці 6x6, без участі слонів. Машина рахувала на 4 напівходи і витрачала на це 12 хвилин. Відомо, що цей комп'ютер зіграв одну партію проти сильного шахіста, вона тривала 10 годин і закінчилася перемогою шахіста. Ще одна партія була зіграна проти дівчини, що нещодавно навчилася грати в шахи. Машина перемогла на 23-му ході. Зараз це виглядає смішно, але для свого часу це було велике досягнення.
В 1957 році створено першу програму для гри на стандартній шахівниці і за участю всіх фігур. Машина прораховувала на 4 напівходи за 8 хвилин.
Важлива подія для комп'ютерних шахів відбулася у 1958 році, коли Ален Невелл, Джон Шоу та Герберт Саймон розробили алгоритм зменшення дерева пошуку відсічення альфа-бета, на основі якого побудовані функції пошуку всіх сильних сучасних програм.
Першою ж машиною, яка досягла рівня шахового майстра, була Belle, закінчена в 1983 р Джо Кондоном та Кеном Томпсоном. «Belle» був першим комп'ютером, який проектували тільки для гри в шахи. Його офіційний рейтинг Ело був 2250, таким чином, це була найсильніша шахова машина свого часу.
У 1994 Гаррі Каспаров програв програмі Fritz 3 турнірну бліц партію в Мюнхені. Програма також виграла у Вішванатана Ананда, Бориса Гельфанда і Володимира Крамника. Гросмейстер Роберт Гюбнер відмовлявся грати проти програми і автоматично програв. Каспаров зіграв другий матч із Фріцом і переміг з 4 виграшами і 2 нічиїми.
У лютому 1996 року Гаррі Каспаров переміг шаховий суперкомп'ютер Deep Blue з рахунком 4-2. Цей матч визначний тим, що першу партію виграв Deep Blue, ставши першим комп'ютером, що переміг чемпіона світу з шахів у турнірних умовах. Deep Blue обчислював 50 мільярдів позицій кожні три хвилини, тоді як Каспаров 10 позицій за цей самий час. У Deep Blue було 200 процесорів.
У 2015 році було створено найменшу шахову програму Super Micro, що займає лише 455 байт.
Відтоді шахові ентузіасти та комп'ютерні інженери створили багато шахових машин та комп'ютерних програм.
Шахові комп'ютери зараз доступні за дуже низьку ціну. З'явилося багато програм із відкритими кодами, зокрема Crafty, Fruit і GNU Chess, які можна вільно завантажити з Інтернету і котрі можуть перемогти багатьох професійних шахістів. А найкращі комерційні програми, наприклад, Shredder чи Fritz уже перевищили рівень людей-чемпіонів. Нині ж рушій Rybka перебуває на першому місці в таких комп'ютерних рейтинг-листах, як CEGT,CCRL, SCCT і CSS.
Мотивація
Першими мотивами для комп'ютеризації шахів було бажання розважитися, створити програми для комп'ютерних шахових турнірів та провести наукове дослідження, яке б дозволило глибше зрозуміти пізнавальну здатність людини. Для перших двох цілей комп'ютерні шахи мали феноменальний успіх: від перших спроб до створення шахової програми, яка могла на рівних змагатися з найкращими шахістами, минуло менше ніж п'ятдесят років.
Проте, на здивування і прикрість багатьох, шахи мало наблизили людей до створення машин з людиноподібним інтелектом. З цих причин комп'ютерні шахи більше не мають такого великого академічного інтересу як інші інтелектуальні ігри, наприклад, го. По суті шахові програми тільки досліджують величезне число можливих ходів обох гравців, застосовуючи відносно просту функцію оцінки, тоді як го вимагає від учених застосовувати більш умоглядні підходи до гри.
Проблеми реалізації
Розробники шахових програми повинні розв'язати низку задач при їх написанні. Вони включають:
Спосіб зображення шахівниці — представлення цільної позиції як структури даних. Методи пошуку — пошук можливих найкращих ходів. Листова оцінка — оцінка позиції без врахування подальших ходів.
Див. також:
Мінімакс Відсічення альфа-бета Killer-евристика Ітераційне заглиблення Евристика нульового ходу
Структура шахової програми Перше дослідження на тему шахового програмування зробив у 1950 році американський математик Клод Шеннон, успішно передбачивши два основних можливих методи пошуку, які можна використати, і назвав їх «Тип А» і «Тип B».
Програми типу А використовують так званий підхід «грубої сили» (brute force), вивчаючи кожну можливу позицію на фіксовану глибину за допомогою алгоритму мінімакс. Шеннон стверджував, що цей метод буде непрактичним через дві причини.
По-перше, з приблизно тридцятьма ходами, можливими в типовій позиції, на вивчення близько 10 000 000 000 вузлових позицій (прорахунок приблизно на три ходи вперед для обох сторін), треба приблизно 16 хвилин, навіть в «дуже оптимістичному» випадку, коли комп'ютер зможе оцінювати мільйон позицій за секунду. (Щоб досягти цього знадобилося сорок років.)
По-друге, програми Типу А нехтували так званою проблемою статичного стану, намагаючись оцінити позицію на початку обміну фігур або іншої важливої послідовності ходів (наприклад тактичних комбінацій). Тож Шеннон припускав, що із застосуванням алгоритму Типу А число позицій, які треба дослідити надзвичайно зросте, що значно сповільнить програму.
Замість марної трати обчислювальної потужності комп'ютера на дослідження поганих чи незначних ходів Шеннон запропонував використовувати програми Типу В. Цей метод має два вдосконалення: Застосовується пошук «по спокою» (quietness). Досліджують не всі, а тільки деякі придатні ходи для кожної позиції.
Це давало програмам змогу прораховувати найважливіші ходи на більшу глибину і робити це за прийнятний час. Перший підхід витримав випробування часом: всі сучасні програми застосовують кінцевий пошук «по спокою» перед оцінкою позиції.
Основні алгоритми сучасних програм
Комп'ютерні шахові програми розглядають шахові ходи як ігрове дерево. Теоретично, вони повинні оцінювати всі позиції, які виникнуть після всіх можливих ходів, потім всі можливі ходи після цих ходів і так далі. Кожний хід одного гравця називається «вузол». Перебирання ходів продовжується, поки програма не досягає максимальної глибини пошуку або визначає, що досягнута кінцева позиція (наприклад мат чи пат). І вже на підставі оцінки позиції обирає оптимальну стратегію. У кожній позиції кількість можливих ходів гравця близько 35. Для повного аналізу чотирьох напівходів (по два ходи кожного гравця) треба дослідити близько півтора мільйона можливостей, для шести — майже два мільярди. Аналіз на 3 ходи вперед — це, звичайно, дуже мало, щоб добре грати.
Програмісти намагаються по-різному обмежити обшир, який треба перебрати (обрізання дерева пошуку — game three pruning). Найпопулярнішим є відсічення альфа-бета, в якому не розглядаються позиції, що мають меншу оцінку ніж уже оцінені.
Приблизне здійснення: private int AlphaBeta(int color, int Depth, int alpha, int beta) { if (Depth == 0) return Evaluate(color); int bestmove; Vector moves = GenerateMoves(); for(int i = 0; i < moves.size(); i++) { makeMove(moves.get(i)); eval = -AlphaBeta(-color, Depth-1, -beta, -alpha); unmakeMove(moves.get(i));
if(eval >= beta) return beta;
if(eval > alpha) { alpha = eval; if (Depth == defaultDepth) { bestmove = moves.get(i);
return alpha;
Приклад першого виклику: AlphaBeta(1, 6, Integer.MIN_VALUE, Integer.MAX_VALUE);
При першому виклику метод (функція) викликається з максимальним вікном. При рекурсивних викликах змінні alpha і beta міняються місцями з інверсією знаку і «звужують» обшир пошуку.
Другим поширеним методом є ітераційне заглиблення. Спочатку перебирається дерево гри до певної глибини, після чого виділяється декілька найкращих ходів. Потім програма оцінює ці ходи до більшої глибини, щоб дізнатися більше про їхні наслідки. Ця операція повторюється до знаходження найкращого, з погляду програми, ходу. Такий підхід дає змогу швидко відкинути чималий відсоток неперспективних варіантів гри. Наприклад, не має сенсу досліджувати, що станеться, коли обміняти ферзя на пішака, якщо в позиції є кращі ходи.
Важливий елемент шахових алгоритмів — це система оцінки позиції. Не можна абсолютно точно оцінити позицію, бо для цього треба було б проаналізувати трильйони послідовностей ходів від початку і до завершення партії. Якби існувала функція, котра давала би змогу достеменно оцінити позицію, задача гри в шахи спростилася б до оцінки кожного з кількох десятків доступних у той момент ходів і не треба було б обчислювати подальші ходи.
Отже, оцінка програмою позиції дуже приблизна, хоча оцінні функції програм постійно удосконалюються. Функції оцінки зазвичай оцінюють позиції в сотих частинах пішака. Ці функції оцінюють тільки декілька простих параметрів:
перше, це оцінка матеріалу — кожен пішак — це 1 пункт, слон та кінь по 3, тура — 5, ферзь — 9. Король інколи ціниться у 200 пішаків (стаття Шеннона) або 1 000 000 000 пішаків (програма розроблена в СРСР у 1961 р.), щоб гарантувати, що мат переважить всі інші чинники. Розвиненіші функції мають точніше встановлені коефіцієнти цінності фігур, які залежать від стадії партії та позиції на шахівниці. друге, це позиційна перевага, яка залежить від положення фігур на шахівниці; наприклад заблокована фігура ціниться менше, аніж вільна, оцінюється також безпека короля, панування над центром шахівниці тощо; існують також значно складніші системи оцінки (деякі навіть використовують знання про нейронні мережі), проте навіть така проста функція дозволяє програмі грати дуже сильно; у шахах головна проблема полягає не в оцінці позиції, а в перебиранні дерева можливих ходів.
Функції оцінки позиції бувають неефективні, коли ситуація на шахівниці різко змінюється з кожним ходом, коли, наприклад, саме триває обмін фігур або реалізовано якусь шахову комбінацію. Звідси виникло поняття статичного стану (quiescent) і горизонту обчислення. У статичному стані на шахівниці точиться повільна позиційна боротьба, а вартий уваги горизонт обчислення дуже широкий. Це означає, що вирішальна переміна не настане в тому майбутньому, яке дається легко передбачити. За такої ситуації більшу роль відіграють функції оцінки позиції, аніж спроби обчислення можливих варіантів.