|
Комп'ютерні шахиКомп'ютерні шахи — популярна назва області дослідження штучного інтелекту, яка полягає в створенні програмного забезпечення і спеціальних комп'ютерів для гри в шахи. Крім того, комп'ютерними шахами називають гру проти комп'ютерної шахової програми, гру програм між собою, а також їхню розробку. Історія Історія шахових машин старша, ніж історія комп'ютерів. Ідея створити машину, що грає в шахи, датується ще вісімнадцятим століттям. Близько 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 байт.[1] Відтоді шахові ентузіасти та комп'ютерні інженери створили багато шахових машин та комп'ютерних програм. Шахові комп'ютери зараз доступні за дуже низьку ціну. З'явилося багато програм із відкритими кодами, зокрема Crafty, Fruit і GNU Chess, які можна вільно завантажити з Інтернету і котрі можуть перемогти багатьох професійних шахістів. А найкращі комерційні програми, наприклад, Shredder чи Fritz уже перевищили рівень людей-чемпіонів. Нині ж рушій Rybka перебуває на першому місці в таких комп'ютерних рейтинг-листах, як CEGT,CCRL, [Архівовано 9 Травня 2020 у Wayback Machine.]SCCT і CSS. МотиваціяПершими мотивами для комп'ютеризації шахів було бажання розважитися, створити програми для комп'ютерних шахових турнірів та провести наукове дослідження, яке б дозволило глибше зрозуміти пізнавальну здатність людини. Для перших двох цілей комп'ютерні шахи мали феноменальний успіх: від перших спроб до створення шахової програми, яка могла на рівних змагатися з найкращими шахістами, минуло менше ніж п'ятдесят років. Проте, на здивування і прикрість багатьох, шахи мало наблизили людей до створення машин з людиноподібним інтелектом. З цих причин комп'ютерні шахи більше не мають такого великого академічного інтересу як інші інтелектуальні ігри, наприклад, го. По суті шахові програми тільки досліджують величезне число можливих ходів обох гравців, застосовуючи відносно просту функцію оцінки, тоді як го вимагає від учених застосовувати більш умоглядні підходи до гри. Проблеми реалізаціїРозробники шахових програми повинні розв'язати низку задач при їх написанні. Вони включають:
Див. також: Структура шахової програмиПерше дослідження на тему шахового програмування зробив у 1950 році американський математик Клод Шеннон, успішно передбачивши два основних можливих методи пошуку, які можна використати, і назвав їх «Тип А» і «Тип B». Програми типу А використовують так званий підхід «грубої сили» (brute force), вивчаючи кожну можливу позицію на фіксовану глибину за допомогою алгоритму мінімакс. Шеннон стверджував, що цей метод буде непрактичним через дві причини. По-перше, з приблизно тридцятьма ходами, можливими в типовій позиції, на вивчення близько 10 000 000 000 вузлових позицій (прорахунок приблизно на три ходи вперед для обох сторін), треба приблизно 16 хвилин, навіть в «дуже оптимістичному» випадку, коли комп'ютер зможе оцінювати мільйон позицій за секунду. (Щоб досягти цього знадобилося сорок років.) По-друге, програми Типу А нехтували так званою проблемою статичного стану, намагаючись оцінити позицію на початку обміну фігур або іншої важливої послідовності ходів (наприклад тактичних комбінацій). Тож Шеннон припускав, що із застосуванням алгоритму Типу А число позицій, які треба дослідити надзвичайно зросте, що значно сповільнить програму. Замість марної трати обчислювальної потужності комп'ютера на дослідження поганих чи незначних ходів Шеннон запропонував використовувати програми Типу В. Цей метод має два вдосконалення:
Це давало програмам змогу прораховувати найважливіші ходи на більшу глибину і робити це за прийнятний час. Перший підхід витримав випробування часом: всі сучасні програми застосовують кінцевий пошук «по спокою» перед оцінкою позиції.  Основні алгоритми сучасних програмКомп'ютерні шахові програми розглядають шахові ходи як ігрове дерево. Теоретично, вони повинні оцінювати всі позиції, які виникнуть після всіх можливих ходів, потім всі можливі ходи після цих ходів і так далі. Кожний хід одного гравця називається «вузол». Перебирання ходів продовжується, поки програма не досягає максимальної глибини пошуку або визначає, що досягнута кінцева позиція (наприклад мат чи пат). І вже на підставі оцінки позиції обирає оптимальну стратегію. У кожній позиції кількість можливих ходів гравця близько 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 міняються місцями з інверсією знаку і «звужують» обшир пошуку. Другим поширеним методом є ітераційне заглиблення. Спочатку перебирається дерево гри до певної глибини, після чого виділяється декілька найкращих ходів. Потім програма оцінює ці ходи до більшої глибини, щоб дізнатися більше про їхні наслідки. Ця операція повторюється до знаходження найкращого, з погляду програми, ходу. Такий підхід дає змогу швидко відкинути чималий відсоток неперспективних варіантів гри. Наприклад, не має сенсу досліджувати, що станеться, коли обміняти ферзя на пішака, якщо в позиції є кращі ходи. Важливий елемент шахових алгоритмів — це система оцінки позиції. Не можна абсолютно точно оцінити позицію, бо для цього треба було б проаналізувати трильйони послідовностей ходів від початку і до завершення партії. Якби існувала функція, котра давала би змогу достеменно оцінити позицію, задача гри в шахи спростилася б до оцінки кожного з кількох десятків доступних у той момент ходів і не треба було б обчислювати подальші ходи. Отже, оцінка програмою позиції дуже приблизна, хоча оцінні функції програм постійно удосконалюються. Функції оцінки зазвичай оцінюють позиції в сотих частинах пішака. Ці функції оцінюють тільки декілька простих параметрів:
Функції оцінки позиції бувають неефективні, коли ситуація на шахівниці різко змінюється з кожним ходом, коли, наприклад, саме триває обмін фігур або реалізовано якусь шахову комбінацію. Звідси виникло поняття статичного стану (quiescent) і горизонту обчислення. У статичному стані на шахівниці точиться повільна позиційна боротьба, а вартий уваги горизонт обчислення дуже широкий. Це означає, що вирішальна переміна не настане в тому майбутньому, яке дається легко передбачити. За такої ситуації більшу роль відіграють функції оцінки позиції, аніж спроби обчислення можливих варіантів. У динамічній ситуації гра, що спирається на функцію оцінки позиції, може призвести до абсолютно помилкових рішень. У крайньому разі, якщо програма має коротко настроєний горизонт обчислення і в ній береться до уваги тільки короткочасна оцінка позиції, то кінець може припасти саме на момент, коли триває обмін ферзів і один з них може бути вже побитий, а другий натомість ще ні. Оцінка програмою такого стану веде до зовсім помилкового висновку, що один з гравців має величезну перевагу, тоді як вона щезне через хід, якого проте програма не бачить. Якщо стан ще не статичний, то треба продовжити обмін до кінця, і оцінити ситуацію коли вже не має можливих радикальних змін. Люди в цілому інтуїтивно розрізняють ці дві ситуації, шахові ж програми повинні мати набір критеріїв, які дають змогу змінювати спосіб функціювання у статичних та динамічних станах. Найважче дати оцінку ходам у дебюті. Більшість програм використовують при цьому написані заздалегідь дебютні бібліотеки, в яких є певна невелика кількість початкових ходів та відповідей до певного числа ходів, яке не є постійним, бо залежить від типу дебюту. Комп'ютер проти ЛюдиниНавіть у 70-80-х рр. залишалося відкритим питання, чи зможе колись шахова програма перемогти найсильніших шахістів. В 1968 р. міжнародний майстер Девід Леві[en] пішов на парі, що жоден комп'ютер не зможе обіграти його протягом найближчих десяти років. Він виграв парі, перемігши в 1978 р. програму Chess 4.7 (найсильніший на той час комп'ютер), але усвідомлював, що залишилось не так уже багато часу до того, коли комп'ютери перемагатимуть світових чемпіонів. В 1989 р. програма Deep Thought[en] виграла у Леві. Але програми все ще були значно нижчі за рівень Світового Чемпіона, що продемонстрував Гаррі Каспаров, перемігши ту ж Deep Thought[en] двічі в 1991 р. Та усе це було до 1996 р., коли відбувся матч Каспарова з комп'ютером Deep Blue фірми IBM, де чемпіон програв свою першу партію. Уперше комп'ютерна шахова програма обіграла світового чемпіона при стандартному часовому контролі. Однак Каспаров змінив свій стиль гри, вигравши три і звівши внічию дві з п'яти партій, які залишилися. В травні 1997 року вдосконалена версія Deep Blue завдала поразки Каспарову з рахунком 3,5—2,5. Пізніше IBM звинуватили, що під час партій фірма використовувала людину-шахіста, щоб збільшити стратегічну силу комп'ютера. У 2003 році було знято документальний фільм, в якому досліджувались ці закиди, який має назву «Гру завершено: Каспаров та машина» (англ. Game Over: Kasparov and the machine), в якому стверджувалось, що сильно розкручувана перемога Deep Blue підлаштована для збільшення ринкової вартості IBM. Частково ці закиди були правильними. Правила дозволяли розробникам змінювати програму між іграми. Deep Blue було змінено між партіями для кращого розуміння машиною стилю гри Каспарова, допомагаючи уникнути пастки в ендшпілі, в яку двічі потрапляв штучний інтелект.
Фінальна позиція першої партії матчу
Deep Blue проти Каспарова 1996 року
IBM розібрала Deep Blue після матчу, відтоді цей комп'ютер не грав ні разу. Хоча відбувалися інші матчі «Людина проти Машини». Маючи дедалі більшу обчислювальну потужність, шахові програми, запущені на персональних комп'ютерах, стали досягати рівня найкращих шахістів. В 1998 р. програма Rebel 10 перемогла Вішванатана Ананда, який тоді займав друге місце у світі. Проте не всі партії гралися зі стандартним часовим контролем. Із восьми партій матчу, чотири гралися з бліц-контролем (п'ять хвилин плюс п'ять секунд за кожний хід), які Rebel виграла з рахунком 3-1. Ще дві гри були з напів-бліц контролем (п'ятнадцять хвилин на кожного), які програма також виграла (1,5-1). Насамкінець, дві останні партії були зіграні зі стандартним турнірним часовим контролем (дві години на 40 ходів і година на решту партії) і тут виграв уже Ананд з рахунком 0,5-1,5. На той час у швидких партіях комп'ютери грали краще за людей, але при класичному часовому контролі перевага була вже не така велика. В 2000 р. комерційні шахові програми Junior і Fritz могли звести внічию матчі проти попередніх світових чемпіонів Гаррі Каспарова та Володимира Крамника. В жовтні 2002 Володимир Крамник і Deep Fritz змагалися у матчі з восьми партій на Бахрейні. Матч закінчився внічию. Крамник виграв другу та третю партії, використовуючи традиційну протикомп'ютерну тактику — грав обережно, маючи на меті довгострокову перевагу, яку комп'ютер не може побачити в своєму дереві пошуку. Та все ж, Fritz виграв п'яту партію після грубої помилки Крамника. Шосту партію багато турнірних коментаторів назвали дуже захопливою. Крамник, маючи кращу позицію на початку міттельшпілю, спробував пожертвувати фігурою, щоби створити сильну тактичну атаку (така стратегія — дуже ризикована проти комп'ютерів). Fritz знайшов сильний захист, і ця атака значно погіршила позицію Крамника. Крамник здав гру, вірячи, що партію програно. Проте післяігровий людський та комп'ютерний аналіз показав, що Fritz навряд чи зміг би довести гру до свого виграшу. Останні дві партії закінчилися внічию. В січні 2003 р. Гаррі Каспаров грав проти програми Junior в Нью-Йорку. Матч закінчився з рахунком 3-3. В листопаді 2003 Гаррі Каспаров грав з X3D Fritz. Матч закінчився з рахунком 2-2. В 2005 р. Hydra, спеціальний шаховий комп'ютер з 64 процесорами, переміг Майкла Адамса, шахіста, котрий тоді був на сьомому місці у світі за рейтингом Ело, в матчі із шести партій з рахунком 5,5-0,5 (хоча домашня підготовка Адамса була набагато нижча, ніж у Каспарова у 2002 році). Деякі коментатори вірили, що Hydra кінець-кінцем здобуде безсумнівну перевагу над найкращими шахістами. В листопаді-грудні 2006 Володимир Крамник грав з програмою Deep Fritz. Матч закінчився з рахунком 2-4. Бази даних ендшпілюДокладніше Бази даних ендшпілю Комп'ютери використовуються для аналізу деяких ендшпільних позицій. Такі бази даних ендшпілю створюються, використовуючи ретроградний аналіз, починаючи з позицій, де кінцевий результат відомий (наприклад, де одній стороні був поставлений мат) і бачачи які інші позиції є на віддалі ходу, тоді на один хід від цих і т. д. Кен Томпсон, відомий як головний проектувальник операційної системи UNIX, був піонером в цій області. Гра в ендшпілі довго була найпомітнішою слабкістю шахових програм, тому що глибина пошуку була недостатньою. Таким чином, навіть програми, які грали в силу майстра не спроможні були виграти в ендшпільних позиціях, де навіть шахіст середньої сили міг форсувати виграш. Але результати комп'ютерного аналізу іноді дивували людей. В 1977 р. шахова машина Томпсона Belle, використовуючи ендшпільні бази даних король + тура проти короля + ферзя, була здатна звести внічию теоретично програшні ендшпілі проти титулованих шахістів. Більшість гросмейстерів відмовлялися грати проти комп'ютера в ендшпілі ферзь проти тури, але Волтер Браун прийняв виклик. Позицію розставили так, що теоретично можна було виграти за 30 ходів з бездоганною грою. Брауну дали дві з половиною години на п'ятдесят ходів. Після сорока п'яти ходів Браун погодився на нічию, будучи не здатним виграти в останні п'ять ходів. В кінцевій позиції, Браун міг поставити мат тільки через сімнадцять ходів. В 2002 р. були опубліковані основні формати ендшпільних баз даних, включаючи Edward Tablebases, De Koning Endgame Database і Nalimov Endgame Tablebases, які тепер підтримують багато шахових програм, такі як Rybka, Shredder і Fritz. Ендшпілі з п'ятьма або менше фігурами були повністю проаналізовані. Ендшпілі з шістьма фігурами були проаналізовані, за винятком позицій з п'ятьма фігурами проти одинокого короля. Марк Буржуцький і Яків Коновал проаналізували деякі ендшпілі з сімома фігурами. В усіх цих ендшпільних базах даних вважається, що рокіровка неможлива. Бази даних генеруються з допомогою зберігання у пам'яті оцінок позицій, які виникали до того часу, і використання цих результатів для зменшення дерева пошуку, якщо такі позиції виникнуть знову. Хоча число можливих ігор після певного числа ходів зростає за експонентою з тим числом ходів, число можливих позицій з декількома фігурами зростають за експонентою тільки в числі фігур. Проста доцільність запам'ятовування оцінок всіх раніше досягнутих позицій означає, що обмежувальним чинником при розв'язанні ендшпілів є просто кількість пам'яті, яку має комп'ютер. Із зростанням місткості комп'ютерної пам'яті, ендшпілі підвищеної складності рано чи пізно будуть розв'язані. Комп'ютер, що використовує бази даних ендшпілів буде, при досягненні позиції у них, спроможний грати бездоганно і невідкладно визначати чи позиція виграшна, програшна чи нічийна, плюс знаходити найшвидший і найдовший спосіб досягнення результату. Знання точної оцінки позиції також корисне в збільшенні сили комп'ютера, тому що це дозволить програмі вибирати шляхи досягнення мети залежно від ситуації. Бази ендшпілів Налімова на п'ять фігур, які використовують методи сучасної компресії, займають 7.05 гігабайт на жорсткому диску. Для зберігання баз даних на шість фігур треба приблизно 1.2 терабайт. Оцінено, що семифігурна база даних вимагатиме більше місця ніж буде доступно в найближчому майбутньому. Гра проти програмКомп'ютери відчутно переважають людей у коротких тактичних маневрах, які перебувають у межах глибини пошуку програми. Особливо небезпечним у таких випадках є ферзь, котрий прекрасно підходить для короткочасних маневрів. Тому у грі проти комп'ютера люди часто роблять спробу спонукати програму до розміну ферзів. Це відбувається, наприклад, коли людина на початку партії навмисно погіршує свою позицію, а комп'ютер розцінює це, як вигідне йому. Якщо програма установлює оцінку позиції на свою перевагу, то, скоріше всього, буде розмінювати фігури, а це вигідно людині. Звичайно, програмісти дізналися про такі «трюки», і це враховується в останніх версіях їхніх програм. Натомість шахісти повинні грати проти комп'ютера довгостроковими маневрами, які програма не може побачити в рамках своєї глибини пошуку. Наприклад, Крамник у партії з Deep Fritz мав успіх за допомогою довгочасного просування прохідного пішака, яке Fritz побачив дуже пізно. Шахи та інші ігриУспіх шахових програм навіює думку, чи можна написати програми, що грають так само добре в інші ігри, такі як Сьоґі чи ґо. Схожі алгоритми, мабуть, можна б використовувати й під час гри в інші різновиди шахів. У Сьоґі більше можливих ходів, матеріальна перевага значить набагато менше, зате набагато істотнішою є позиційна перевага. Будуються складні системи, що мають на меті гарантувати королю безпеку, але оцінка тих систем для комп'ютера нелегка. Кількість фігур у цій грі постійна, а тому гра не спрощується з часом, що робить неможливим створити базу ендшпілів. Нема тут також цілком статичних станів, адже гра протягом усього часу зводиться до позиційної боротьби. Тому написати гарну програму для гри в шоґі значно важче, аніж шахову програму, хоча багато досвіду з шахів можна перенести й до цієї гри. Справжнім викликом для програмістів стало ґо. Складність обчислення ґо на кілька порядків більша за шахи. На кожному кроці можливі близько 200–300 ходів, статична ж оцінка життя груп пішаків фактично неможлива. Одним ходом тут можна цілком зіпсувати всю гру, навіть коли решта ходів були дуже добрі. Тому програми для гри в ґо не використовують таких алгоритмів, як шахові програми, а замість того зазвичай мають кілька десятків модулів для оцінки різних аспектів гри і під час аналізу намагаються послуговуватись тими ж поняттями, що й люди. Попри це і далі грали дуже слабко та програвали навіть не дуже сильним аматорам до 2015 року. У 2015 році AlphaGo зміг вщент розбити чинного чемпіона Європи з Ґо Фен Х'юї — комп'ютер виграв 5 ігор з п'яти. Хронологія комп'ютерних шахів
Комп'ютерні шахові теоретики
Див. такожПримітки
Посилання
|
||||||||||||||||||||||||||||||||||||||||||||||||||||||
