Комп'ютерні шахи — популярна назва області дослідження штучного інтелекту, яка полягає в створенні програмного забезпечення і спеціальних комп'ютерів для гри в шахи. Крім того, комп'ютерними шахами називають гру проти комп'ютерної шахової програми, гру програм між собою, а також їхню розробку.
Історія
Історія шахових машин старша, ніж історія комп'ютерів. Ідея створити машину, що грає в шахи, датується ще вісімнадцятим століттям. Близько 1769 р. з'явився шаховий автомат Механічний турок. Він був призначений для розваги королеви Марії-Терезії. Машина справді непогано грала — усередині неї сидів сильний шахіст, який і робив ходи.
Дослідження механічних шахових автоматів припинилися з появою цифрових комп'ютерів близько 1950 р. У 1951 р. Алан Тюрінг написав алгоритм, за допомогою якого машина могла б грати в шахи, тільки в ролі машини виступав сам винахідник. Цей нонсенс навіть дістав назву — «паперова машина Тюрінга». Людині треба було більше ніж півгодини, щоб зробити один хід. Алгоритм був досить умовний, і зберігся навіть запис партії, де «паперова машина» Тюрінга програла одному з його колег. Через відсутність доступу до комп'ютера програма жодного разу не перевірялась в роботі.
Приблизно тоді ж, в 1951 році, математик Клод Шеннон написав свою першу статтю про шахове програмування. Він писав: «Хоча, можливо, це й не має жодного практичного значення, саме питання є, теоретично, цікавим, і сподіватимемося, що вирішення цієї задачі послужить поштовхом для вирішення інших задач аналогічної природи й більшого значення». Шенон також відзначає теоретичне існування найкращого ходу в шахах і практичну неможливість його знайти.
Наступним кроком у розвитку шахового програмування стала розробка в ядерній лабораторії Лос-Аламоса в 1952 році на комп'ютері (тактова частота 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, і GNU Chess, які можна вільно завантажити з Інтернету і котрі можуть перемогти багатьох професійних шахістів. А найкращі комерційні програми, наприклад, Shredder чи Fritz уже перевищили рівень людей-чемпіонів. Нині ж рушій Rybka перебуває на першому місці в таких комп'ютерних рейтинг-листах, як CCRL, [ 9 Травня 2020 у Wayback Machine.] і
Мотивація
Першими мотивами для комп'ютеризації шахів було бажання розважитися, створити програми для комп'ютерних шахових турнірів та провести наукове дослідження, яке б дозволило глибше зрозуміти . Для перших двох цілей комп'ютерні шахи мали феноменальний успіх: від перших спроб до створення шахової програми, яка могла на рівних змагатися з найкращими шахістами, минуло менше ніж п'ятдесят років.
Проте, на здивування і прикрість багатьох, шахи мало наблизили людей до створення машин з людиноподібним інтелектом. З цих причин комп'ютерні шахи більше не мають такого великого академічного інтересу як інші , наприклад, го. По суті шахові програми тільки досліджують величезне число можливих ходів обох гравців, застосовуючи відносно просту , тоді як го вимагає від учених застосовувати більш умоглядні підходи до гри.
Проблеми реалізації
Розробники шахових програми повинні розв'язати низку задач при їх написанні. Вони включають:
- Спосіб зображення шахівниці — представлення цільної позиції як структури даних.
- — пошук можливих найкращих ходів.
- — оцінка позиції без врахування подальших ходів.
Див. також:
Структура шахової програми
Перше дослідження на тему шахового програмування зробив у 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) і . У статичному стані на шахівниці точиться повільна позиційна боротьба, а вартий уваги горизонт обчислення дуже широкий. Це означає, що вирішальна переміна не настане в тому майбутньому, яке дається легко передбачити. За такої ситуації більшу роль відіграють функції оцінки позиції, аніж спроби обчислення можливих варіантів.
У ситуації гра, що спирається на функцію оцінки позиції, може призвести до абсолютно помилкових рішень. У крайньому разі, якщо програма має коротко настроєний горизонт обчислення і в ній береться до уваги тільки короткочасна оцінка позиції, то кінець може припасти саме на момент, коли триває обмін ферзів і один з них може бути вже побитий, а другий натомість ще ні. Оцінка програмою такого стану веде до зовсім помилкового висновку, що один з гравців має величезну перевагу, тоді як вона щезне через хід, якого проте програма не бачить. Якщо стан ще не статичний, то треба продовжити обмін до кінця, і оцінити ситуацію коли вже не має можливих радикальних змін. Люди в цілому інтуїтивно розрізняють ці дві ситуації, шахові ж програми повинні мати набір критеріїв, які дають змогу змінювати спосіб функціювання у статичних та динамічних станах.
Найважче дати оцінку ходам у дебюті. Більшість програм використовують при цьому написані заздалегідь , в яких є певна невелика кількість початкових ходів та відповідей до певного числа ходів, яке не є постійним, бо залежить від типу дебюту.
Комп'ютер проти Людини
Навіть у 70-80-х рр. залишалося відкритим питання, чи зможе колись шахова програма перемогти найсильніших шахістів. В 1968 р. міжнародний майстер [en] пішов на парі, що жоден комп'ютер не зможе обіграти його протягом найближчих десяти років. Він виграв парі, перемігши в 1978 р. програму (найсильніший на той час комп'ютер), але усвідомлював, що залишилось не так уже багато часу до того, коли комп'ютери перемагатимуть світових чемпіонів. В 1989 р. програма [en] виграла у Леві.
Але програми все ще були значно нижчі за рівень Світового Чемпіона, що продемонстрував Гаррі Каспаров, перемігши ту ж [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 було змінено між партіями для кращого розуміння машиною стилю гри Каспарова, допомагаючи уникнути пастки в ендшпілі, в яку двічі потрапляв штучний інтелект.
a | b | c | d | e | f | g | h | ||
8 | 8 | ||||||||
7 | 7 | ||||||||
6 | 6 | ||||||||
5 | 5 | ||||||||
4 | 4 | ||||||||
3 | 3 | ||||||||
2 | 2 | ||||||||
1 | 1 | ||||||||
a | b | c | d | e | f | g | h |
IBM розібрала Deep Blue після матчу, відтоді цей комп'ютер не грав ні разу. Хоча відбувалися інші матчі «Людина проти Машини».
Маючи дедалі більшу обчислювальну потужність, шахові програми, запущені на персональних комп'ютерах, стали досягати рівня найкращих шахістів. В 1998 р. програма 10 перемогла Вішванатана Ананда, який тоді займав друге місце у світі. Проте не всі партії гралися зі стандартним часовим контролем. Із восьми партій матчу, чотири гралися з бліц-контролем (п'ять хвилин плюс п'ять секунд за кожний хід), які Rebel виграла з рахунком 3-1. Ще дві гри були з напів-бліц контролем (п'ятнадцять хвилин на кожного), які програма також виграла (1,5-1). Насамкінець, дві останні партії були зіграні зі стандартним турнірним часовим контролем (дві години на 40 ходів і година на решту партії) і тут виграв уже Ананд з рахунком 0,5-1,5. На той час у швидких партіях комп'ютери грали краще за людей, але при класичному часовому контролі перевага була вже не така велика.
В 2000 р. комерційні шахові програми і Fritz могли звести внічию матчі проти попередніх світових чемпіонів Гаррі Каспарова та Володимира Крамника.
В жовтні 2002 Володимир Крамник і Deep Fritz змагалися у матчі з восьми партій на Бахрейні. Матч закінчився внічию. Крамник виграв другу та третю партії, використовуючи традиційну протикомп'ютерну тактику — грав обережно, маючи на меті довгострокову перевагу, яку комп'ютер не може побачити в своєму дереві пошуку. Та все ж, Fritz виграв п'яту партію після грубої помилки Крамника. Шосту партію багато турнірних коментаторів назвали дуже захопливою. Крамник, маючи кращу позицію на початку міттельшпілю, спробував пожертвувати фігурою, щоби створити сильну тактичну атаку (така стратегія — дуже ризикована проти комп'ютерів). Fritz знайшов сильний захист, і ця атака значно погіршила позицію Крамника. Крамник здав гру, вірячи, що партію програно. Проте післяігровий людський та комп'ютерний аналіз показав, що Fritz навряд чи зміг би довести гру до свого виграшу. Останні дві партії закінчилися внічию.
В січні 2003 р. Гаррі Каспаров грав проти програми в Нью-Йорку. Матч закінчився з рахунком 3-3.
В листопаді 2003 Гаррі Каспаров грав з . Матч закінчився з рахунком 2-2.
В 2005 р. , спеціальний шаховий комп'ютер з 64 процесорами, переміг Майкла Адамса, шахіста, котрий тоді був на сьомому місці у світі за рейтингом Ело, в матчі із шести партій з рахунком 5,5-0,5 (хоча домашня підготовка Адамса була набагато нижча, ніж у Каспарова у 2002 році). Деякі коментатори вірили, що Hydra кінець-кінцем здобуде безсумнівну перевагу над найкращими шахістами.
В листопаді-грудні 2006 Володимир Крамник грав з програмою Deep Fritz. Матч закінчився з рахунком 2-4.
Бази даних ендшпілю
Докладніше Бази даних ендшпілю
Комп'ютери використовуються для аналізу деяких ендшпільних позицій. Такі бази даних ендшпілю створюються, використовуючи ретроградний аналіз, починаючи з позицій, де кінцевий результат відомий (наприклад, де одній стороні був поставлений мат) і бачачи які інші позиції є на віддалі ходу, тоді на один хід від цих і т. д. Кен Томпсон, відомий як головний проектувальник операційної системи UNIX, був піонером в цій області.
Гра в ендшпілі довго була найпомітнішою слабкістю шахових програм, тому що глибина пошуку була недостатньою. Таким чином, навіть програми, які грали в силу майстра не спроможні були виграти в ендшпільних позиціях, де навіть шахіст середньої сили міг форсувати виграш.
Але результати комп'ютерного аналізу іноді дивували людей. В 1977 р. шахова машина Томпсона Belle, використовуючи ендшпільні бази даних король + тура проти короля + ферзя, була здатна звести внічию теоретично програшні ендшпілі проти титулованих шахістів.
Більшість гросмейстерів відмовлялися грати проти комп'ютера в ендшпілі ферзь проти тури, але Волтер Браун прийняв виклик. Позицію розставили так, що теоретично можна було виграти за 30 ходів з бездоганною грою. Брауну дали дві з половиною години на п'ятдесят ходів. Після сорока п'яти ходів Браун погодився на нічию, будучи не здатним виграти в останні п'ять ходів. В кінцевій позиції, Браун міг поставити мат тільки через сімнадцять ходів.
В 2002 р. були опубліковані основні формати ендшпільних баз даних, включаючи , і , які тепер підтримують багато шахових програм, такі як Rybka, Shredder і Fritz. Ендшпілі з п'ятьма або менше фігурами були повністю проаналізовані. Ендшпілі з шістьма фігурами були проаналізовані, за винятком позицій з п'ятьма фігурами проти одинокого короля. і проаналізували деякі ендшпілі з сімома фігурами. В усіх цих ендшпільних базах даних вважається, що рокіровка неможлива.
Бази даних генеруються з допомогою зберігання у пам'яті оцінок позицій, які виникали до того часу, і використання цих результатів для зменшення дерева пошуку, якщо такі позиції виникнуть знову. Хоча число можливих ігор після певного числа ходів зростає за експонентою з тим числом ходів, число можливих позицій з декількома фігурами зростають за експонентою тільки в числі фігур. Проста доцільність запам'ятовування оцінок всіх раніше досягнутих позицій означає, що обмежувальним чинником при розв'язанні ендшпілів є просто кількість пам'яті, яку має комп'ютер. Із зростанням місткості комп'ютерної пам'яті, ендшпілі підвищеної складності рано чи пізно будуть розв'язані.
Комп'ютер, що використовує буде, при досягненні позиції у них, спроможний грати бездоганно і невідкладно визначати чи позиція виграшна, програшна чи нічийна, плюс знаходити найшвидший і найдовший спосіб досягнення результату. Знання точної оцінки позиції також корисне в збільшенні сили комп'ютера, тому що це дозволить програмі вибирати шляхи досягнення мети залежно від ситуації.
Бази ендшпілів Налімова на п'ять фігур, які використовують методи сучасної , займають 7.05 гігабайт на жорсткому диску. Для зберігання баз даних на шість фігур треба приблизно 1.2 терабайт. Оцінено, що семифігурна база даних вимагатиме більше місця ніж буде доступно в найближчому майбутньому.
Гра проти програм
Комп'ютери відчутно переважають людей у коротких тактичних маневрах, які перебувають у межах глибини пошуку програми. Особливо небезпечним у таких випадках є ферзь, котрий прекрасно підходить для короткочасних маневрів. Тому у грі проти комп'ютера люди часто роблять спробу спонукати програму до розміну ферзів. Це відбувається, наприклад, коли людина на початку партії навмисно погіршує свою позицію, а комп'ютер розцінює це, як вигідне йому. Якщо програма установлює оцінку позиції на свою перевагу, то, скоріше всього, буде розмінювати фігури, а це вигідно людині. Звичайно, програмісти дізналися про такі «трюки», і це враховується в останніх версіях їхніх програм.
Натомість шахісти повинні грати проти комп'ютера довгостроковими маневрами, які програма не може побачити в рамках своєї глибини пошуку. Наприклад, Крамник у партії з Deep Fritz мав успіх за допомогою довгочасного просування прохідного пішака, яке Fritz побачив дуже пізно.
Шахи та інші ігри
Успіх шахових програм навіює думку, чи можна написати програми, що грають так само добре в інші ігри, такі як Сьоґі чи ґо.
Схожі алгоритми, мабуть, можна б використовувати й під час гри в інші різновиди шахів. У Сьоґі більше можливих ходів, матеріальна перевага значить набагато менше, зате набагато істотнішою є позиційна перевага. Будуються складні системи, що мають на меті гарантувати королю безпеку, але оцінка тих систем для комп'ютера нелегка. Кількість фігур у цій грі постійна, а тому гра не спрощується з часом, що робить неможливим створити базу ендшпілів. Нема тут також цілком статичних станів, адже гра протягом усього часу зводиться до позиційної боротьби. Тому написати гарну програму для гри в шоґі значно важче, аніж шахову програму, хоча багато досвіду з шахів можна перенести й до цієї гри.
Справжнім викликом для програмістів стало ґо. Складність обчислення ґо на кілька порядків більша за шахи. На кожному кроці можливі близько 200–300 ходів, статична ж оцінка життя груп пішаків фактично неможлива. Одним ходом тут можна цілком зіпсувати всю гру, навіть коли решта ходів були дуже добрі. Тому програми для гри в ґо не використовують таких алгоритмів, як шахові програми, а замість того зазвичай мають кілька десятків модулів для оцінки різних аспектів гри і під час аналізу намагаються послуговуватись тими ж поняттями, що й люди. Попри це і далі грали дуже слабко та програвали навіть не дуже сильним аматорам до 2015 року. У 2015 році AlphaGo зміг вщент розбити чинного чемпіона Європи з Ґо Фен Х'юї — комп'ютер виграв 5 ігор з п'яти.
Хронологія комп'ютерних шахів
- 1769 — збудував Шахіста-автомата, який став одною із найбільших містифікацій цього періоду.
- 1868 — представив автомат Ajeeb — в якому теж був схований шахіст.
- 1912 — збудував машину, яка могла грати ендшпілі Король + Тура проти короля.
- 1948 — книжка Норберта Вінера «Кібернетика» описує, як можна створити шахову програму, використовуючи пошук мінімакс із лімітованою глибиною та оціночною функцією.
- 1950 — Клод Шеннон опублікував «Програмування комп'ютера для гри в шахи», одну з перших статей про комп'ютерні шахи.
- 1951 — Алан Тюринг розробив на папері першу програму, здатну грати в шахи.
- 1952 — розробив програму, що розв'язувала шахові задачі.
- 1956 — Лос-Аламос — перша подібна шахам гра, яку змогли грати програми, розроблена та для комп'ютера .
- 1956 — Джон Маккарті винайшов альфа-бета-алгоритм пошуку.
- 1958 — NSS стала першою програмою, яка використовувала алгоритм альфа-бета-пошуку.
- 1958 — першими шаховими програмами, що могли грати повні шахові партії стали одна, створена і друга російськими програмістами.
- 1962 — першою програмою, яка грала правдоподібно стала Kotok-McCarthy.
- 1966–1967 — перший матч між програмами.
- 1967 — Mac Hack Six, розроблена стала першою програмою, що перемогла людину при турнірному контролі часу.
- 1970 — перший рік Північноамериканського комп'ютерного шахового чемпіонату.
- 1974 — Каісса виграла перший Світовий комп'ютерний шаховий чемпіонат.
- 1976 — став першим шаховим комп'ютером, який виграв «людський» шаховий турнір, а саме, турнір класу B Пола Масона в Північної Каліфорнії, його тодішній рейтинг Ело був 1950.
- 1976 — Chess 4.6 виграв великий турнір, Minnesota Open, перемігши в 5 партіях й програвши в одній, його рейтинг Ело становив 2271.
- 1977 — створена перша шахова програма для мікрокомп'ютерів .
- 1977 — створення Міжнародної комп'ютерної шахової асоціації.
- 1980 — перший рік Світового Мікрокомп'ютерного шахового чемпіонату.
- 1981 — виграв Чемпіонат штату Міссісіпі з 5-0 очками і рейтингом Ело 2258.
- 1982 — апаратний шаховий гравець Кена Томпсона Belle заробляє титул майстра США.
- 1988 — HiTech, розроблена і , виграє матч проти гросмейстера з рахунком 3.5 — 0.5.
- 1988 — [en] ділить перше місце з в Чемпіонаті програмного забезпечення Toolworks, попереду колишнього чемпіон світу Михайла Таля і декількох гросмейстерів, зокрема , Волтера Брауна, Ернста Грюнфельда і Михайла Гуревича. Програма завдає також поразки гросмейстеру Бенту Ларсену, і стає першим комп'ютером, який обіграв гросмейстера в турнірі.
- 1992 — вперше мікрокомп'ютер, Chessmachine Gideon 3.1, розроблений (Ed Schröder) виграє VII Світовий комп'ютерний шаховий чемпіонат попереду суперкомп'ютерів.
- 1997 — Deep Blue виграв матч проти Гаррі Каспарова +2-1=3.
- 2002 — Володимир Крамник звів внічию матч проти Deep Fritz.
- 2003 — Каспаров зіграв внічию матч проти .
- 2003 — Каспаров зіграв внічию матч проти .
- 2005 — виграла матч із Майклом Адамсом з рахунком 5,5-0,5.
- 2005 — команда комп'ютерів (, і Fritz), виграла 8.5-3.5 проти команди із людей (Веселін Топалов, Руслан Пономарьов і Сергій Карякін), які мали середній рейтинг Ело 2681.
- 2006 — чемпіон світу, Володимир Крамник, переможений 4-2 Deep Fritz.
Комп'ютерні шахові теоретики
- [en]
- Роберт Гаятт (автор шахової програми Crafty)
- Клод Шеннон
Див. також
Примітки
- . Smmax.sourceforge.net. Архів оригіналу за 6 Січня 2019. Процитовано 24 вересня 2016.
Посилання
- Історія комп'ютерних шахів
- Захист Честі Людства — стаття Тіма Краббе про «анти-комп'ютерний» стиль шахів [ 11 Грудня 2007 у Wayback Machine.]
- Computer-Chess Club — місце, де професійні автори обговорюють свої програми [ 29 Грудня 2007 у Wayback Machine.]
- Комп'ютерна шахова теорія Коліна Фрауна [ 1 Грудня 2005 у Wayback Machine.]
- Велика колекція комп'ютерних шахових програм Еда Шредера [ 20 Грудня 2007 у Wayback Machine.]
Вікіпедія, Українська, Україна, книга, книги, бібліотека, стаття, читати, завантажити, безкоштовно, безкоштовно завантажити, mp3, відео, mp4, 3gp, jpg, jpeg, gif, png, малюнок, музика, пісня, фільм, книга, гра, ігри, мобільний, телефон, android, ios, apple, мобільний телефон, samsung, iphone, xiomi, xiaomi, redmi, honor, oppo, nokia, sonya, mi, ПК, web, Інтернет
Komp yuterni shahi populyarna nazva oblasti doslidzhennya shtuchnogo intelektu yaka polyagaye v stvorenni programnogo zabezpechennya i specialnih komp yuteriv dlya gri v shahi Krim togo komp yuternimi shahami nazivayut gru proti komp yuternoyi shahovoyi programi gru program mizh soboyu a takozh yihnyu rozrobku IstoriyaShahovij komp yuter Istoriya shahovih mashin starsha nizh istoriya komp yuteriv Ideya stvoriti mashinu sho graye v shahi datuyetsya she visimnadcyatim stolittyam Blizko 1769 r z yavivsya shahovij avtomat Mehanichnij turok Vin buv priznachenij dlya rozvagi korolevi Mariyi Tereziyi Mashina spravdi nepogano grala useredini neyi sidiv silnij shahist yakij i robiv hodi Doslidzhennya mehanichnih shahovih avtomativ pripinilisya z poyavoyu cifrovih komp yuteriv blizko 1950 r U 1951 r Alan Tyuring napisav algoritm za dopomogoyu yakogo mashina mogla b grati v shahi tilki v roli mashini vistupav sam vinahidnik Cej nonsens navit distav nazvu paperova mashina Tyuringa Lyudini treba bulo bilshe nizh pivgodini shob zrobiti odin hid Algoritm buv dosit umovnij i zberigsya navit zapis partiyi de paperova mashina Tyuringa prograla odnomu z jogo koleg Cherez vidsutnist dostupu do komp yutera programa zhodnogo razu ne pereviryalas v roboti Priblizno todi zh v 1951 roci matematik Klod Shennon napisav svoyu pershu stattyu pro shahove programuvannya Vin pisav Hocha mozhlivo ce j ne maye zhodnogo praktichnogo znachennya same pitannya ye teoretichno cikavim i spodivatimemosya sho virishennya ciyeyi zadachi posluzhit poshtovhom dlya virishennya inshih zadach analogichnoyi prirodi j bilshogo znachennya Shenon takozh vidznachaye teoretichne isnuvannya najkrashogo hodu v shahah i praktichnu nemozhlivist jogo znajti Nastupnim krokom u rozvitku shahovogo programuvannya stala rozrobka v yadernij laboratoriyi Los Alamosa v 1952 roci na komp yuteri taktova chastota 11 kGc shahovoyi programi dlya gri na shahivnici 6x6 bez uchasti sloniv Mashina rahuvala na 4 napivhodi i vitrachala na ce 12 hvilin Vidomo sho cej komp yuter zigrav odnu partiyu proti silnogo shahista vona trivala 10 godin i zakinchilasya peremogoyu shahista She odna partiya bula zigrana proti divchini sho neshodavno navchilasya grati v shahi Mashina peremogla na 23 mu hodi Zaraz ce viglyadaye smishno ale dlya svogo chasu ce bulo velike dosyagnennya V 1957 roci stvoreno pershu programu dlya gri na standartnij shahivnici i za uchastyu vsih figur Mashina prorahovuvala na 4 napivhodi za 8 hvilin Vazhliva podiya dlya komp yuternih shahiv vidbulasya u 1958 roci koli ta Gerbert Sajmon rozrobili algoritm zmenshennya dereva poshuku vidsichennya alfa beta na osnovi yakogo pobudovani funkciyi poshuku vsih silnih suchasnih program Pershoyu zh mashinoyu yaka dosyagla rivnya shahovogo majstra bula Belle zakinchena v 1983 r Dzho Kondonom ta Kenom Tompsonom Belle buv pershim komp yuterom yakij proektuvali tilki dlya gri v shahi Jogo oficijnij rejting Elo buv 2250 takim chinom ce bula najsilnisha shahova mashina svogo chasu U 1994 Garri Kasparov prograv programi Fritz 3 turnirnu blic partiyu v Myunheni Programa takozh vigrala u Vishvanatana Ananda Borisa Gelfanda i Volodimira Kramnika Grosmejster Robert Gyubner vidmovlyavsya grati proti programi i avtomatichno prograv Kasparov zigrav drugij match iz Fricom i peremig z 4 vigrashami i 2 nichiyimi U lyutomu 1996 roku Garri Kasparov peremig shahovij superkomp yuter Deep Blue z rahunkom 4 2 Cej match viznachnij tim sho pershu partiyu vigrav Deep Blue stavshi pershim komp yuterom sho peremig chempiona svitu z shahiv u turnirnih umovah Deep Blue obchislyuvav 50 milyardiv pozicij kozhni tri hvilini todi yak Kasparov 10 pozicij za cej samij chas U Deep Blue bulo 200 procesoriv U 2015 roci bulo stvoreno najmenshu shahovu programu Super Micro sho zajmaye lishe 455 bajt Vidtodi shahovi entuziasti ta komp yuterni inzheneri stvorili bagato shahovih mashin ta komp yuternih program Shahovi komp yuteri zaraz dostupni za duzhe nizku cinu Z yavilosya bagato program iz vidkritimi kodami zokrema Crafty i GNU Chess yaki mozhna vilno zavantazhiti z Internetu i kotri mozhut peremogti bagatoh profesijnih shahistiv A najkrashi komercijni programi napriklad Shredder chi Fritz uzhe perevishili riven lyudej chempioniv Nini zh rushij Rybka perebuvaye na pershomu misci v takih komp yuternih rejting listah yak CCRL 9 Travnya 2020 u Wayback Machine iMotivaciyaPershimi motivami dlya komp yuterizaciyi shahiv bulo bazhannya rozvazhitisya stvoriti programi dlya komp yuternih shahovih turniriv ta provesti naukove doslidzhennya yake b dozvolilo glibshe zrozumiti Dlya pershih dvoh cilej komp yuterni shahi mali fenomenalnij uspih vid pershih sprob do stvorennya shahovoyi programi yaka mogla na rivnih zmagatisya z najkrashimi shahistami minulo menshe nizh p yatdesyat rokiv Prote na zdivuvannya i prikrist bagatoh shahi malo nablizili lyudej do stvorennya mashin z lyudinopodibnim intelektom Z cih prichin komp yuterni shahi bilshe ne mayut takogo velikogo akademichnogo interesu yak inshi napriklad go Po suti shahovi programi tilki doslidzhuyut velichezne chislo mozhlivih hodiv oboh gravciv zastosovuyuchi vidnosno prostu todi yak go vimagaye vid uchenih zastosovuvati bilsh umoglyadni pidhodi do gri Problemi realizaciyiRozrobniki shahovih programi povinni rozv yazati nizku zadach pri yih napisanni Voni vklyuchayut Sposib zobrazhennya shahivnici predstavlennya cilnoyi poziciyi yak strukturi danih poshuk mozhlivih najkrashih hodiv ocinka poziciyi bez vrahuvannya podalshih hodiv Div takozh Minimaks Vidsichennya alfa beta Evristika nulovogo hoduStruktura shahovoyi programiPershe doslidzhennya na temu shahovogo programuvannya zrobiv u 1950 roci amerikanskij matematik Klod Shennon uspishno peredbachivshi dva osnovnih mozhlivih metodi poshuku yaki mozhna vikoristati i nazvav yih Tip A i Tip B Programi tipu A vikoristovuyut tak zvanij pidhid gruboyi sili brute force vivchayuchi kozhnu mozhlivu poziciyu na fiksovanu glibinu za dopomogoyu algoritmu minimaks Shennon stverdzhuvav sho cej metod bude nepraktichnim cherez dvi prichini Po pershe z priblizno tridcyatma hodami mozhlivimi v tipovij poziciyi na vivchennya blizko 10 000 000 000 vuzlovih pozicij prorahunok priblizno na tri hodi vpered dlya oboh storin treba priblizno 16 hvilin navit v duzhe optimistichnomu vipadku koli komp yuter zmozhe ocinyuvati miljon pozicij za sekundu Shob dosyagti cogo znadobilosya sorok rokiv Po druge programi Tipu A nehtuvali tak zvanoyu problemoyu statichnogo stanu namagayuchis ociniti poziciyu na pochatku obminu figur abo inshoyi vazhlivoyi poslidovnosti hodiv napriklad taktichnih kombinacij Tozh Shennon pripuskav sho iz zastosuvannyam algoritmu Tipu A chislo pozicij yaki treba dosliditi nadzvichajno zroste sho znachno spovilnit programu Zamist marnoyi trati obchislyuvalnoyi potuzhnosti komp yutera na doslidzhennya poganih chi neznachnih hodiv Shennon zaproponuvav vikoristovuvati programi Tipu V Cej metod maye dva vdoskonalennya Zastosovuyetsya poshuk po spokoyu quietness Doslidzhuyut ne vsi a tilki deyaki pridatni hodi dlya kozhnoyi poziciyi Ce davalo programam zmogu prorahovuvati najvazhlivishi hodi na bilshu glibinu i robiti ce za prijnyatnij chas Pershij pidhid vitrimav viprobuvannya chasom vsi suchasni programi zastosovuyut kincevij poshuk po spokoyu pered ocinkoyu poziciyi Priblizna shema zdijsnennya alfa beta vidsichennya slabkih hodivOsnovni algoritmi suchasnih program Komp yuterni shahovi programi rozglyadayut shahovi hodi yak igrove derevo Teoretichno voni povinni ocinyuvati vsi poziciyi yaki viniknut pislya vsih mozhlivih hodiv potim vsi mozhlivi hodi pislya cih hodiv i tak dali Kozhnij hid odnogo gravcya nazivayetsya vuzol Perebirannya hodiv prodovzhuyetsya poki programa ne dosyagaye maksimalnoyi glibini poshuku abo viznachaye sho dosyagnuta kinceva poziciya napriklad mat chi pat I vzhe na pidstavi ocinki poziciyi obiraye optimalnu strategiyu U kozhnij poziciyi kilkist mozhlivih hodiv gravcya blizko 35 Dlya povnogo analizu chotiroh napivhodiv po dva hodi kozhnogo gravcya treba dosliditi blizko pivtora miljona mozhlivostej dlya shesti majzhe dva milyardi Analiz na 3 hodi vpered ce zvichajno duzhe malo shob dobre grati Programisti namagayutsya po riznomu obmezhiti obshir yakij treba perebrati game three pruning Najpopulyarnishim ye vidsichennya alfa beta v yakomu ne rozglyadayutsya poziciyi sho mayut menshu ocinku nizh uzhe ocineni Priblizne zdijsnennya 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 lt moves size i makeMove moves get i eval AlphaBeta color Depth 1 beta alpha unmakeMove moves get i if eval gt beta return beta if eval gt alpha alpha eval if Depth defaultDepth bestmove moves get i return alpha Priklad pershogo vikliku AlphaBeta 1 6 Integer MIN VALUE Integer MAX VALUE Pri pershomu vikliku metod funkciya viklikayetsya z maksimalnim viknom Pri rekursivnih viklikah zminni alpha i beta minyayutsya miscyami z inversiyeyu znaku i zvuzhuyut obshir poshuku Drugim poshirenim metodom ye Spochatku perebirayetsya derevo gri do pevnoyi glibini pislya chogo vidilyayetsya dekilka najkrashih hodiv Potim programa ocinyuye ci hodi do bilshoyi glibini shob diznatisya bilshe pro yihni naslidki Cya operaciya povtoryuyetsya do znahodzhennya najkrashogo z poglyadu programi hodu Takij pidhid daye zmogu shvidko vidkinuti chimalij vidsotok neperspektivnih variantiv gri Napriklad ne maye sensu doslidzhuvati sho stanetsya koli obminyati ferzya na pishaka yaksho v poziciyi ye krashi hodi Vazhlivij element ce Ne mozhna absolyutno tochno ociniti poziciyu bo dlya cogo treba bulo b proanalizuvati triljoni poslidovnostej hodiv vid pochatku i do zavershennya partiyi Yakbi isnuvala funkciya kotra davala bi zmogu dostemenno ociniti poziciyu zadacha gri v shahi sprostilasya b do ocinki kozhnogo z kilkoh desyatkiv dostupnih u toj moment hodiv i ne treba bulo b obchislyuvati podalshi hodi Otzhe ocinka programoyu poziciyi duzhe priblizna hocha ocinni funkciyi program postijno udoskonalyuyutsya Funkciyi ocinki zazvichaj ocinyuyut poziciyi v sotih chastinah pishaka Ci funkciyi ocinyuyut tilki dekilka prostih parametriv pershe ce ocinka materialu kozhen pishak ce 1 punkt slon ta kin po 3 tura 5 ferz 9 Korol inkoli cinitsya u 200 pishakiv stattya Shennona abo 1 000 000 000 pishakiv programa rozroblena v SRSR u 1961 r shob garantuvati sho mat perevazhit vsi inshi chinniki Rozvinenishi funkciyi mayut tochnishe vstanovleni koeficiyenti cinnosti figur yaki zalezhat vid stadiyi partiyi ta poziciyi na shahivnici druge ce pozicijna perevaga yaka zalezhit vid polozhennya figur na shahivnici napriklad zablokovana figura cinitsya menshe anizh vilna ocinyuyetsya takozh bezpeka korolya panuvannya nad centrom shahivnici tosho isnuyut takozh znachno skladnishi sistemi ocinki deyaki navit vikoristovuyut znannya pro nejronni merezhi prote navit taka prosta funkciya dozvolyaye programi grati duzhe silno u shahah golovna problema polyagaye ne v ocinci poziciyi a v perebiranni dereva mozhlivih hodiv Funkciyi ocinki poziciyi buvayut neefektivni koli situaciya na shahivnici rizko zminyuyetsya z kozhnim hodom koli napriklad same trivaye obmin figur abo realizovano yakus shahovu kombinaciyu Zvidsi viniklo ponyattya quiescent i U statichnomu stani na shahivnici tochitsya povilna pozicijna borotba a vartij uvagi gorizont obchislennya duzhe shirokij Ce oznachaye sho virishalna peremina ne nastane v tomu majbutnomu yake dayetsya legko peredbachiti Za takoyi situaciyi bilshu rol vidigrayut funkciyi ocinki poziciyi anizh sprobi obchislennya mozhlivih variantiv U situaciyi gra sho spirayetsya na funkciyu ocinki poziciyi mozhe prizvesti do absolyutno pomilkovih rishen U krajnomu razi yaksho programa maye korotko nastroyenij gorizont obchislennya i v nij beretsya do uvagi tilki korotkochasna ocinka poziciyi to kinec mozhe pripasti same na moment koli trivaye obmin ferziv i odin z nih mozhe buti vzhe pobitij a drugij natomist she ni Ocinka programoyu takogo stanu vede do zovsim pomilkovogo visnovku sho odin z gravciv maye velicheznu perevagu todi yak vona shezne cherez hid yakogo prote programa ne bachit Yaksho stan she ne statichnij to treba prodovzhiti obmin do kincya i ociniti situaciyu koli vzhe ne maye mozhlivih radikalnih zmin Lyudi v cilomu intuyitivno rozriznyayut ci dvi situaciyi shahovi zh programi povinni mati nabir kriteriyiv yaki dayut zmogu zminyuvati sposib funkciyuvannya u statichnih ta dinamichnih stanah Najvazhche dati ocinku hodam u debyuti Bilshist program vikoristovuyut pri comu napisani zazdalegid v yakih ye pevna nevelika kilkist pochatkovih hodiv ta vidpovidej do pevnogo chisla hodiv yake ne ye postijnim bo zalezhit vid tipu debyutu Komp yuter proti LyudiniNavit u 70 80 h rr zalishalosya vidkritim pitannya chi zmozhe kolis shahova programa peremogti najsilnishih shahistiv V 1968 r mizhnarodnij majster en pishov na pari sho zhoden komp yuter ne zmozhe obigrati jogo protyagom najblizhchih desyati rokiv Vin vigrav pari peremigshi v 1978 r programu najsilnishij na toj chas komp yuter ale usvidomlyuvav sho zalishilos ne tak uzhe bagato chasu do togo koli komp yuteri peremagatimut svitovih chempioniv V 1989 r programa en vigrala u Levi Ale programi vse she buli znachno nizhchi za riven Svitovogo Chempiona sho prodemonstruvav Garri Kasparov peremigshi tu zh en dvichi v 1991 r Ta use ce bulo do 1996 r koli vidbuvsya match Kasparova z komp yuterom Deep Blue firmi IBM de chempion prograv svoyu pershu partiyu Upershe komp yuterna shahova programa obigrala svitovogo chempiona pri standartnomu chasovomu kontroli Odnak Kasparov zminiv svij stil gri vigravshi tri i zvivshi vnichiyu dvi z p yati partij yaki zalishilisya V travni 1997 roku vdoskonalena versiya Deep Blue zavdala porazki Kasparovu z rahunkom 3 5 2 5 Piznishe IBM zvinuvatili sho pid chas partij firma vikoristovuvala lyudinu shahista shob zbilshiti strategichnu silu komp yutera U 2003 roci bulo znyato dokumentalnij film v yakomu doslidzhuvalis ci zakidi yakij maye nazvu Gru zaversheno Kasparov ta mashina angl Game Over Kasparov and the machine v yakomu stverdzhuvalos sho silno rozkruchuvana peremoga Deep Blue pidlashtovana dlya zbilshennya rinkovoyi vartosti IBM Chastkovo ci zakidi buli pravilnimi Pravila dozvolyali rozrobnikam zminyuvati programu mizh igrami Deep Blue bulo zmineno mizh partiyami dlya krashogo rozuminnya mashinoyu stilyu gri Kasparova dopomagayuchi uniknuti pastki v endshpili v yaku dvichi potraplyav shtuchnij intelekt abcdefgh8877665544332211abcdefghFinalna poziciya pershoyi partiyi matchu Deep Blue proti Kasparova 1996 roku IBM rozibrala Deep Blue pislya matchu vidtodi cej komp yuter ne grav ni razu Hocha vidbuvalisya inshi matchi Lyudina proti Mashini Mayuchi dedali bilshu obchislyuvalnu potuzhnist shahovi programi zapusheni na personalnih komp yuterah stali dosyagati rivnya najkrashih shahistiv V 1998 r programa 10 peremogla Vishvanatana Ananda yakij todi zajmav druge misce u sviti Prote ne vsi partiyi gralisya zi standartnim chasovim kontrolem Iz vosmi partij matchu chotiri gralisya z blic kontrolem p yat hvilin plyus p yat sekund za kozhnij hid yaki Rebel vigrala z rahunkom 3 1 She dvi gri buli z napiv blic kontrolem p yatnadcyat hvilin na kozhnogo yaki programa takozh vigrala 1 5 1 Nasamkinec dvi ostanni partiyi buli zigrani zi standartnim turnirnim chasovim kontrolem dvi godini na 40 hodiv i godina na reshtu partiyi i tut vigrav uzhe Anand z rahunkom 0 5 1 5 Na toj chas u shvidkih partiyah komp yuteri grali krashe za lyudej ale pri klasichnomu chasovomu kontroli perevaga bula vzhe ne taka velika V 2000 r komercijni shahovi programi i Fritz mogli zvesti vnichiyu matchi proti poperednih svitovih chempioniv Garri Kasparova ta Volodimira Kramnika V zhovtni 2002 Volodimir Kramnik i Deep Fritz zmagalisya u matchi z vosmi partij na Bahrejni Match zakinchivsya vnichiyu Kramnik vigrav drugu ta tretyu partiyi vikoristovuyuchi tradicijnu protikomp yuternu taktiku grav oberezhno mayuchi na meti dovgostrokovu perevagu yaku komp yuter ne mozhe pobachiti v svoyemu derevi poshuku Ta vse zh Fritz vigrav p yatu partiyu pislya gruboyi pomilki Kramnika Shostu partiyu bagato turnirnih komentatoriv nazvali duzhe zahoplivoyu Kramnik mayuchi krashu poziciyu na pochatku mittelshpilyu sprobuvav pozhertvuvati figuroyu shobi stvoriti silnu taktichnu ataku taka strategiya duzhe rizikovana proti komp yuteriv Fritz znajshov silnij zahist i cya ataka znachno pogirshila poziciyu Kramnika Kramnik zdav gru viryachi sho partiyu prograno Prote pislyaigrovij lyudskij ta komp yuternij analiz pokazav sho Fritz navryad chi zmig bi dovesti gru do svogo vigrashu Ostanni dvi partiyi zakinchilisya vnichiyu V sichni 2003 r Garri Kasparov grav proti programi v Nyu Jorku Match zakinchivsya z rahunkom 3 3 V listopadi 2003 Garri Kasparov grav z Match zakinchivsya z rahunkom 2 2 V 2005 r specialnij shahovij komp yuter z 64 procesorami peremig Majkla Adamsa shahista kotrij todi buv na somomu misci u sviti za rejtingom Elo v matchi iz shesti partij z rahunkom 5 5 0 5 hocha domashnya pidgotovka Adamsa bula nabagato nizhcha nizh u Kasparova u 2002 roci Deyaki komentatori virili sho Hydra kinec kincem zdobude bezsumnivnu perevagu nad najkrashimi shahistami V listopadi grudni 2006 Volodimir Kramnik grav z programoyu Deep Fritz Match zakinchivsya z rahunkom 2 4 Bazi danih endshpilyuDokladnishe Bazi danih endshpilyu Komp yuteri vikoristovuyutsya dlya analizu deyakih endshpilnih pozicij Taki bazi danih endshpilyu stvoryuyutsya vikoristovuyuchi retrogradnij analiz pochinayuchi z pozicij de kincevij rezultat vidomij napriklad de odnij storoni buv postavlenij mat i bachachi yaki inshi poziciyi ye na viddali hodu todi na odin hid vid cih i t d Ken Tompson vidomij yak golovnij proektuvalnik operacijnoyi sistemi UNIX buv pionerom v cij oblasti Gra v endshpili dovgo bula najpomitnishoyu slabkistyu shahovih program tomu sho glibina poshuku bula nedostatnoyu Takim chinom navit programi yaki grali v silu majstra ne spromozhni buli vigrati v endshpilnih poziciyah de navit shahist serednoyi sili mig forsuvati vigrash Ale rezultati komp yuternogo analizu inodi divuvali lyudej V 1977 r shahova mashina Tompsona Belle vikoristovuyuchi endshpilni bazi danih korol tura proti korolya ferzya bula zdatna zvesti vnichiyu teoretichno prograshni endshpili proti titulovanih shahistiv Bilshist grosmejsteriv vidmovlyalisya grati proti komp yutera v endshpili ferz proti turi ale Volter Braun prijnyav viklik Poziciyu rozstavili tak sho teoretichno mozhna bulo vigrati za 30 hodiv z bezdogannoyu groyu Braunu dali dvi z polovinoyu godini na p yatdesyat hodiv Pislya soroka p yati hodiv Braun pogodivsya na nichiyu buduchi ne zdatnim vigrati v ostanni p yat hodiv V kincevij poziciyi Braun mig postaviti mat tilki cherez simnadcyat hodiv V 2002 r buli opublikovani osnovni formati endshpilnih baz danih vklyuchayuchi i yaki teper pidtrimuyut bagato shahovih program taki yak Rybka Shredder i Fritz Endshpili z p yatma abo menshe figurami buli povnistyu proanalizovani Endshpili z shistma figurami buli proanalizovani za vinyatkom pozicij z p yatma figurami proti odinokogo korolya i proanalizuvali deyaki endshpili z simoma figurami V usih cih endshpilnih bazah danih vvazhayetsya sho rokirovka nemozhliva Bazi danih generuyutsya z dopomogoyu zberigannya u pam yati ocinok pozicij yaki vinikali do togo chasu i vikoristannya cih rezultativ dlya zmenshennya dereva poshuku yaksho taki poziciyi viniknut znovu Hocha chislo mozhlivih igor pislya pevnogo chisla hodiv zrostaye za eksponentoyu z tim chislom hodiv chislo mozhlivih pozicij z dekilkoma figurami zrostayut za eksponentoyu tilki v chisli figur Prosta docilnist zapam yatovuvannya ocinok vsih ranishe dosyagnutih pozicij oznachaye sho obmezhuvalnim chinnikom pri rozv yazanni endshpiliv ye prosto kilkist pam yati yaku maye komp yuter Iz zrostannyam mistkosti komp yuternoyi pam yati endshpili pidvishenoyi skladnosti rano chi pizno budut rozv yazani Komp yuter sho vikoristovuye bude pri dosyagnenni poziciyi u nih spromozhnij grati bezdoganno i nevidkladno viznachati chi poziciya vigrashna prograshna chi nichijna plyus znahoditi najshvidshij i najdovshij sposib dosyagnennya rezultatu Znannya tochnoyi ocinki poziciyi takozh korisne v zbilshenni sili komp yutera tomu sho ce dozvolit programi vibirati shlyahi dosyagnennya meti zalezhno vid situaciyi Bazi endshpiliv Nalimova na p yat figur yaki vikoristovuyut metodi suchasnoyi zajmayut 7 05 gigabajt na zhorstkomu disku Dlya zberigannya baz danih na shist figur treba priblizno 1 2 terabajt Ocineno sho semifigurna baza danih vimagatime bilshe miscya nizh bude dostupno v najblizhchomu majbutnomu Gra proti programKomp yuteri vidchutno perevazhayut lyudej u korotkih taktichnih manevrah yaki perebuvayut u mezhah glibini poshuku programi Osoblivo nebezpechnim u takih vipadkah ye ferz kotrij prekrasno pidhodit dlya korotkochasnih manevriv Tomu u gri proti komp yutera lyudi chasto roblyat sprobu sponukati programu do rozminu ferziv Ce vidbuvayetsya napriklad koli lyudina na pochatku partiyi navmisno pogirshuye svoyu poziciyu a komp yuter rozcinyuye ce yak vigidne jomu Yaksho programa ustanovlyuye ocinku poziciyi na svoyu perevagu to skorishe vsogo bude rozminyuvati figuri a ce vigidno lyudini Zvichajno programisti diznalisya pro taki tryuki i ce vrahovuyetsya v ostannih versiyah yihnih program Natomist shahisti povinni grati proti komp yutera dovgostrokovimi manevrami yaki programa ne mozhe pobachiti v ramkah svoyeyi glibini poshuku Napriklad Kramnik u partiyi z Deep Fritz mav uspih za dopomogoyu dovgochasnogo prosuvannya prohidnogo pishaka yake Fritz pobachiv duzhe pizno Shahi ta inshi igriUspih shahovih program naviyuye dumku chi mozhna napisati programi sho grayut tak samo dobre v inshi igri taki yak Sogi chi go Shozhi algoritmi mabut mozhna b vikoristovuvati j pid chas gri v inshi riznovidi shahiv U Sogi bilshe mozhlivih hodiv materialna perevaga znachit nabagato menshe zate nabagato istotnishoyu ye pozicijna perevaga Buduyutsya skladni sistemi sho mayut na meti garantuvati korolyu bezpeku ale ocinka tih sistem dlya komp yutera nelegka Kilkist figur u cij gri postijna a tomu gra ne sproshuyetsya z chasom sho robit nemozhlivim stvoriti bazu endshpiliv Nema tut takozh cilkom statichnih staniv adzhe gra protyagom usogo chasu zvoditsya do pozicijnoyi borotbi Tomu napisati garnu programu dlya gri v shogi znachno vazhche anizh shahovu programu hocha bagato dosvidu z shahiv mozhna perenesti j do ciyeyi gri Spravzhnim viklikom dlya programistiv stalo go Skladnist obchislennya go na kilka poryadkiv bilsha za shahi Na kozhnomu kroci mozhlivi blizko 200 300 hodiv statichna zh ocinka zhittya grup pishakiv faktichno nemozhliva Odnim hodom tut mozhna cilkom zipsuvati vsyu gru navit koli reshta hodiv buli duzhe dobri Tomu programi dlya gri v go ne vikoristovuyut takih algoritmiv yak shahovi programi a zamist togo zazvichaj mayut kilka desyatkiv moduliv dlya ocinki riznih aspektiv gri i pid chas analizu namagayutsya poslugovuvatis timi zh ponyattyami sho j lyudi Popri ce i dali grali duzhe slabko ta progravali navit ne duzhe silnim amatoram do 2015 roku U 2015 roci AlphaGo zmig vshent rozbiti chinnogo chempiona Yevropi z Go Fen H yuyi komp yuter vigrav 5 igor z p yati Hronologiya komp yuternih shahiv1769 zbuduvav Shahista avtomata yakij stav odnoyu iz najbilshih mistifikacij cogo periodu 1868 predstaviv avtomat Ajeeb v yakomu tezh buv shovanij shahist 1912 zbuduvav mashinu yaka mogla grati endshpili Korol Tura proti korolya 1948 knizhka Norberta Vinera Kibernetika opisuye yak mozhna stvoriti shahovu programu vikoristovuyuchi poshuk minimaks iz limitovanoyu glibinoyu ta ocinochnoyu funkciyeyu 1950 Klod Shennon opublikuvav Programuvannya komp yutera dlya gri v shahi odnu z pershih statej pro komp yuterni shahi 1951 Alan Tyuring rozrobiv na paperi pershu programu zdatnu grati v shahi 1952 rozrobiv programu sho rozv yazuvala shahovi zadachi 1956 Los Alamos persha podibna shaham gra yaku zmogli grati programi rozroblena ta dlya komp yutera 1956 Dzhon Makkarti vinajshov alfa beta algoritm poshuku 1958 NSS stala pershoyu programoyu yaka vikoristovuvala algoritm alfa beta poshuku 1958 pershimi shahovimi programami sho mogli grati povni shahovi partiyi stali odna stvorena i druga rosijskimi programistami 1962 pershoyu programoyu yaka grala pravdopodibno stala Kotok McCarthy 1966 1967 pershij match mizh programami 1967 Mac Hack Six rozroblena stala pershoyu programoyu sho peremogla lyudinu pri turnirnomu kontroli chasu 1970 pershij rik Pivnichnoamerikanskogo komp yuternogo shahovogo chempionatu 1974 Kaissa vigrala pershij Svitovij komp yuternij shahovij chempionat 1976 stav pershim shahovim komp yuterom yakij vigrav lyudskij shahovij turnir a same turnir klasu B Pola Masona v Pivnichnoyi Kaliforniyi jogo todishnij rejting Elo buv 1950 1976 Chess 4 6 vigrav velikij turnir Minnesota Open peremigshi v 5 partiyah j progravshi v odnij jogo rejting Elo stanoviv 2271 1977 stvorena persha shahova programa dlya mikrokomp yuteriv 1977 stvorennya Mizhnarodnoyi komp yuternoyi shahovoyi asociaciyi 1980 pershij rik Svitovogo Mikrokomp yuternogo shahovogo chempionatu 1981 vigrav Chempionat shtatu Missisipi z 5 0 ochkami i rejtingom Elo 2258 1982 aparatnij shahovij gravec Kena Tompsona Belle zaroblyaye titul majstra SShA 1988 HiTech rozroblena i vigraye match proti grosmejstera z rahunkom 3 5 0 5 1988 en dilit pershe misce z v Chempionati programnogo zabezpechennya Toolworks poperedu kolishnogo chempion svitu Mihajla Talya i dekilkoh grosmejsteriv zokrema Voltera Brauna Ernsta Gryunfelda i Mihajla Gurevicha Programa zavdaye takozh porazki grosmejsteru Bentu Larsenu i staye pershim komp yuterom yakij obigrav grosmejstera v turniri 1992 vpershe mikrokomp yuter Chessmachine Gideon 3 1 rozroblenij Ed Schroder vigraye VII Svitovij komp yuternij shahovij chempionat poperedu superkomp yuteriv 1997 Deep Blue vigrav match proti Garri Kasparova 2 1 3 2002 Volodimir Kramnik zviv vnichiyu match proti Deep Fritz 2003 Kasparov zigrav vnichiyu match proti 2003 Kasparov zigrav vnichiyu match proti 2005 vigrala match iz Majklom Adamsom z rahunkom 5 5 0 5 2005 komanda komp yuteriv i Fritz vigrala 8 5 3 5 proti komandi iz lyudej Veselin Topalov Ruslan Ponomarov i Sergij Karyakin yaki mali serednij rejting Elo 2681 2006 chempion svitu Volodimir Kramnik peremozhenij 4 2 Deep Fritz Komp yuterni shahovi teoretiki en Robert Gayatt avtor shahovoyi programi Crafty Klod ShennonDiv takozhProsunuti shahi Predstavlennya shahivnici Komp yuterne goPrimitki Smmax sourceforge net Arhiv originalu za 6 Sichnya 2019 Procitovano 24 veresnya 2016 PosilannyaIstoriya komp yuternih shahiv Zahist Chesti Lyudstva stattya Tima Krabbe pro anti komp yuternij stil shahiv 11 Grudnya 2007 u Wayback Machine Computer Chess Club misce de profesijni avtori obgovoryuyut svoyi programi 29 Grudnya 2007 u Wayback Machine Komp yuterna shahova teoriya Kolina Frauna 1 Grudnya 2005 u Wayback Machine Velika kolekciya komp yuternih shahovih program Eda Shredera 20 Grudnya 2007 u Wayback Machine