Бази даних ендшпілю

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

Типовий інтерфейс для використання бази даних ендшпілю. Для кожного ходу білих таблиці показують число ходів до виграшу. Походивши Kc6 чи Фa6+, вони виграють за 5 ходів, отже, це оптимальні ходи.

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

Ендшпільні таблиці формуються за допомогою ретроспективного аналізу, який опрацьовує всі положення назад від мату або пату. До 2005 року всі шахові позиції з шістьма фігурами (включаючи двох королів) були вирішеними. До серпня 2012 року були вирішеними вже всі позиції до семи фігур (позиції з самотнім королем проти короля і п'яти фігур були опущені як "цілком очевидні").[1][2]

Ці вирішення суттєво просунули вперед розуміння шаховим співтовариством теорії ендшпілю. Доведено виграшність деяких позицій, які люди раніше вважали нічийними. Аналізуючи деякі позиції за допомогою бази даних, можна знайти виграш у понад 500 ходів, а це не лише виходить далеко за межі горизонту пошуку людини, але й перебуває за межами можливостей комп'ютера під час гри. Тому бази даних також ставлять під питання правило п'ятдесяти ходів, оскільки тепер відомо багато позицій, які є виграшними, але все-одно ведуть до нічиєї через правило 50 ходів. Бази даних збагатили змагальні шахи і полегшили складання етюдів. Вони є потужним інструментом, який дає змогу шахістам вивчати найскладніші ендшпілі.

Хоча існують і ендшпільні бази даних для інших настільних ігор, таких як шашки,[3] некласичні варіанти шахів[4] або млин[5], якщо гру не вказано, то за умовчанням йдеться про шахи.

Передумови

Якщо не брати до уваги фізичних обмежень апаратного забезпечення, то в принципі можна вирішити будь-яку гру за умови, що відома повна інформація і відсутня жодна випадковість. Сильні рішення, тобто алгоритми, які дають найсильнішу гру з будь-якої позиції,[6] відомі для деяких простих ігор, таких як хрестики-нулики (нічия за ідеальної гри) і чотири в ряд (перший гравець виграє). Слабкі рішення існують для деяких дещо складніших ігор, таких як шашки (за ідеальної гри з обох сторін гра вважається нічийною, але не для кожної позиції, до якої привела неідеальна гра, відомий наступний ідеальний хід). Інші ігри, такі як шахи (від початкового положення) і ґо, не вирішені, оскільки складність цих ігор перевищує можливості комп'ютерів станом на 2018 рік оцінити всі можливі позиції. Щоб зменшити складність гри, дослідники модифікували ці складні ігри, зменшивши розмір шахівниці, або кількість фігур, або обидва ці фактори.

Комп'ютерні шахи - одна з найдавніших галузей досліджень штучного інтелекту, яка бере свій початок у 1930-х роках. 1949 року Клод Шеннон запропонував формальні критерії для оцінки шахових ходів. У 1951 році Алан Тюрінг розробив примітивну шахову програму, яка присвоює значення для матеріалу та мобільності; програма "грала" в шахи на основі ручних обчислень Тюрінга.[7] Втім, навіть коли почали розвиватися змагальні шахові програми, вони показали кричущу слабкість у грі в ендшпілі. Програмісти застосовували конкретні евристики щодо ендшпілю – наприклад, король повинен рухатися до центру шахівниці.[8] Проте, було необхідне загальніше рішення.

1965 року Річард Беллман запропонував створити базу даних, яка б вирішила шаховий і шашковий ендшпілі за допомогою ретроспективного аналізу.[9][10] Замість аналізу вперед починаючи з поточної позиції на шахівниці, база даних має аналізувати назад позиції, де один із гравців поставив мат або потрапив у становище пату. Таким чином, шаховий комп'ютер вже не змушений аналізувати ендшпільні позиції під час гри, оскільки їх вирішено заздалегідь. Він не буде припускатись помилок, оскільки база даних завжди показує найкращий хід.

1970 року Томас Штрьоляйн опублікував докторську дисертацію[11][12], яка містила аналіз таких класів ендшпілю: KQK, KRK, KPK, KQKR, KRKB, а також KRKN.[13] У 1977 році базу даних Томпсона KQKR використано в матчі проти гросмейстера Волтера Брауна.

Кен Томпсон та інші допомогли розширити ендшпільні бази даних, щоб вони охопити всі чотири- і п'ятифігурні ендшпілі, включаючи, зокрема, KBBKN, KQPKQ і KRPKR.[14][15] 1995 року Льюїс Стіллер опублікував дисертацію з дослідженнями баз даних для деяких шестифігурних закінчень.[16][17]

Серед пізніших авторів, які зробили свій внесок:

  • Євген налімов, на честь якого названо популярні бази даних Налімова;
  • Ейко Бляйхер, який адаптував концепцію баз даних до програми під назвою "Фрізер" (див. нижче);
  • Гай Гаворт, науковець з Університету Редінга, який багато публікувався на цю тему в Журналі ICGA та інших місцях;
  • Марк Бурзуцький і Яків Коновал, які спільно аналізувати семифігурні ендшпілі;
  • Пітер Каррер, який побудував спеціалізовану семифігурну базу (KQPPKQP) для ендшпілю онлайн-матчу Каспаров проти світу;
  • Володимир Махнишев і Віктор Захаров з Московського державного університету, які закінчили створення 4+3 глибина до мату-ендшпільної бази даних (зокрема закінчення KPPPKPP на 525 ходів) у липні 2012 року. Вони називаються таблицями Ломоносова. Наступний набір 5+2 ГДМ-ендшпільних таблиць (350 закінчень, зокрема KPPPPKP) завершено в серпні 2012 року. Високої швидкості генерації  варіантів розробники досягнули завдяки використанню суперкомп'ютера Ломоносов (Top500 світу). Розмір всіх баз даних до семи фігур становить близько 140 ТБ.[18]

Бази даних усіх ендшпілів до семи фігур доступні для безкоштовного скачування, а також доступ до них можна отримати через веб-інтерфейси (див. зовнішні посилання нижче). База даних Налімова вимагає понад один терабайт дискового простору.[19][20]

Генерація бази даних

Показники: глибина до переходу і глибина до мату


abcdefgh
8
8
77
66
55
44
33
22
11
abcdefgh
Приклад: ГДП проти ГДМ

Перед створенням бази даних програміст повинен вибрати метрику оптимальності – іншими словами, повинен визначити, в який момент гравець "виграв" гру. Кожну позицію можна визначити у термінах відстані (тобто кількості ходів) від бажаної кінцевої мети. Зазвичай використовуються дві метрики:

  • Глибина до мату (ГДМ). Мат - єдиний спосіб виграти гру.
  • Глибина до переходу (ГДП). Сильніша сторона може також перемогти, вигравши матеріал, таким чином перейшовши в простіший ендшпіль. Наприклад, у закінченні KQKR перехід відбувається, коли білі виграють чорну туру.

Крім того Гаворт розглянув дві інші метрики, а саме "глибину до ходу-обнулення" (ГДО) і "глибину за правилом" (ГЗП). Хід-обнулення - це хід, який скидає відлік руху до нуля за правилом п'ятдесяти ходів, тобто мат, побиття, або пересування пішака.[21] Ці метрики підтримують правило п'ятдесяти ходів. Бази даних ГЗП станом на кінець 2018 року ще не розраховані. 7-фігурна база даних ГДО стала доступною публічно в серпні 2018 року.[22]

Різницю між ГДМ і ГДП можна зрозуміти, аналізуючи діаграму праворуч. Подальші дії білих, залежать від їхнього вибору метрики.

Метрика Гра ГДП ГДМ
ГДП 1. Qxd1 Kc8 2. Qd2 Kb8 3. Qd8# 1 3
ГДМ 1. Qc7+ Ka8 2. Qa7# 2 2

Діючи за метрикою ГДП, білі повинні побити туру, оскільки це відразу приводить до позиції, яка, безумовно, виграшною (ГДП = 1), але насправді поставити мат займе ще два ходи (ГДМ = 3). На відміну від цього, згідно з метрикою ГДМ білі матують у два ходи, тож ГДМ = ГДП = 2.

Ця різниця характерна для багатьох ендшпільних позицій. Зазвичай ГДП менша, ніж ГДМ, але ГДМ веде до найшвидшого мату. Винятки виникають тоді, коли слабша сторона має лише короля, а також у незвичайному ендшпілі два коня проти пішака; тут ГДП = ГДМ, оскільки відсутній матеріал захисту, який потрібно побити, або ж побиття не приносить бажаного результату. (Справді, побиття пішака в останньому з ендшпілів призводить до нічиєї, якщо сильніша сторона негайно не ставить мат.)

Крок 1: генерація всіх можливих позицій
Девід Леві, Як комп'ютери грають у шахи


abcdefgh
8
8
77
66
55
44
33
22
11
abcdefgh
Десять унікальних клітинок (з симетрією)


abcdefgh
8
8
77
66
55
44
33
22
11
abcdefgh
24 унікальні пішакові клітини (з симетрією)

Після вибору метрики першим кроком є генерація всіх позицій з заданим матеріалом. Наприклад, щоб створити базу даних ГДМ для ендшпілю: король і ферзь проти короля (KQK), комп'ютер повинен описати приблизно 40 000 унікальних легальних позицій.

Леві і Ньюборн пояснюють, що число 40,000 випливає з міркувань симетрії. Чорний король може розміститись на будь-якому з десяти квадратів: a1, b1, c1, d1, b2, c2, d2, c3, d3 і d4 (див. схему). На будь-якій іншій клітинці його положення можна вважати еквівалентним за симетрією обертання або віддзеркалення. Таким чином, немає жлдної різниці, чи чорний король перебуває в кутку на a1, чи на a8, h8, або h1. Помножте це число 10 на 60 легально можливих клітин розмістити білого короля, що залишилось, а потім на 62 клітини для білого ферзя. Виходить 10×60×62 = 37,200. Кілька сотень з цих позицій є нелегальними, неможливими, або симетричними віддзеркаленнями одна одної, тож реальна їх кількість дещо менша.[23][24]

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

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

Ендшпіль з одним або кількома пішаками збільшує складність, оскільки аргумент симетрії зменшується. Оскільки пішаки можуть рухатись вперед, а не вбік, то обертання і вертикальне віддзеркалення шахівниці призводить до фундаментальних змін у характері позиції.[25] Найкращий розрахунок симетрії досягається шляхом обмеження одного пішака до 24 квадратів у прямокутнику a2-a7-d7-d2. Всі інші фігури й пішаки можна розмістити на будь-якій з 64 клітинок, які дозволяє цей пішак. Таким чином, ендшпіль з пішаками має у 24/10 = 2.4 рази більшу складність, ніж безпішаковий ендшпіль з такою самою кількістю фігур.

Крок 2: Оцінка позицій за допомогою ретроградного аналізу

Тім Краббе так пояснює процес створення бази даних:

"Ідея полягає в тому, що база даних містить усі можливі позиції з урахуванням матеріалу [примітка: як у попередньому розділі]. Потім підбаза даних складається з усіх позицій, де чорним ставлять мат. Потім йде підбаза, у якій білі можуть поставити мат. Потім підбаза, у якій чорні не можуть завадити білим поставити мат наступним ходом. Потім та, де білі завжди можуть досягнути позиції, коли чорні не можуть перешкодити їм поставити мат наступним ходом. І так далі, завжди на півхід далі від мату, поки не буде знайдено всі позиції, які таким чином до нього ведуть. Потім всі ці позиції за допомогою бази даних пов'язуються назад до мату найкоротшим шляхом. Це означає, що, крім еквіоптимальних ходів, всі ходи по такому шляху досконалі: хід білих завжди веде до найшвидшого мату, а хід чорних - до найповільнішого".[26]

Ретроспективний аналіз необхідний лише від позицій мату. Від інших позицій не потрібно працювати, оскільки кожна позиція, якої не можна досягнути від позицій мату, є нічийною.[27]

Рис. 1 ілюструє ідею ретроспективного аналізу. Білі матують за два ходи 1. Kc6, веде до позиції на рисунку 2. Тоді, якщо 1...Kb8 2. Фb7#, а якщо 1...Кd8 2. Фd7# (Рис. 3).

На рис. 3, ситуація перед другим ходом білих визначається як "мат в один півхід." На рис. 2, після першого ходу білих "мат у два півходи," незалежно від того, як грають чорні. Нарешті, початкове положення на Рис. 1 це "мат у три півходи" (тобто два ходи), тому що воно веде прямо до Рис. 2, вже визначеного як "мат у два півходи." Цей процес, який пов'язує поточне положення з іншим положенням, яке могло існувати на один півхід раніше, може тривати нескінченно.

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

Рис. 1


abcdefgh
8
8
77
66
55
44
33
22
11
abcdefgh
Хід білих: мат за три півходи (Kc6)
Рис. 2


abcdefgh
8
8
77
66
55
44
33
22
11
abcdefgh
Хід чорних: мат за два півходи (Kd8 або Kb8)
Рис. 3


abcdefgh
8
8
77
66
55
44
33
22
11
abcdefgh
Хіт білих: мат за один півхід (Qd7)

Крок 3: верифікація

Після того, як базу даних створено, і кожну позицію оцінено, результат потрібно перевірити незалежно. Метою є перевірка самоузгодженості табличних результатів.[28]

Наприклад, на Рис. 1 програма перевірки бачить оцінку "мат у три півходи (Kc6)." Потім вона дивиться на становище на Рис. 2, після Kc6, і бачить оцінку "мат у два півходи." Ці дві оцінки узгоджуються між собою. Якби оцінка на Рис. 2 була якоюсь інакшою, то вона була б несумісною з Рис. 1, тоді базу даних потрібно було б виправити.[прояснити: ком.]

Побиття, просування пішака і спеціальні ходи

Чотирифігурна база даних має покладатись на трифігурну, яку можна отримати шляхом побиття однієї фігури. Подібно до цього, база даних з пішаком має покладатися на іншу базу даних, яка містить набір фігур, отриманий після заміни пішака на ферзя або іншу фігуру. Програма ретроградного аналізу має враховувати можливість побиття або заміни пішака на попередньому ході.[29]

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

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

Використання апріорної інформації


abcdefgh
8
8
77
66
55
44
33
22
11
abcdefgh
Приклад ендшпілю KRP(a2)KBP(a3). Білі матують за 72 ходи, починаючи з 1.Kh7! Інші ходи білих ведуть до нічиєї.

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

Ранній аналіз такого типу опубліковано 1987 року, в ендшпілі KRP(a2)KBP(a3), де слон чорних ходить по чорних полях (див. приклад на рис. праворуч).[30] У цій позиції можна зробити такі апріорні припущення:

1. Якщо фігуру побито, то можна перевірити отриману позицію за відповідною п'ятифігурною базою даних. Наприклад, якщо чорного пішака побито, то дивляться на новостворену позицію KRPKB.
2. Білий пішак стоїть на a2; ходи побиття здійснюються за першим правилом.
3. Чорний пішак стоїть на a3; ходи побиття здійснюються за першим правилом.[31]

Результатом такого спрощення є те, що, замість того щоб шукати 48 * 47 = 2,256 перестановок положень пішака, є тільки одна перестановка. Скорочення простору пошуку у 2256 разів набагато пришвидшує підрахунок.

Бляйхер розробив комерційну програму під назвою "Фрізер", що дозволяє будувати нові бази даних на основі апріорної інформації, яку містить база даних Налімова. Програма могла створювати бази даних для позиції з сімома або більше фігурами з заблокованими пішаками, ще до того, як стали доступними семифігурні бази даних.[32]

Застосування

Заочні шахи
Каспаров проти світу, 1999


abcdefgh
8
8
77
66
55
44
33
22
11
abcdefgh
Позиція після 55.Qxb4; база даних каже нам, що білі виграють за 82 ходи.

У шахах за листуванням гравець може звернутися по допомогу до шахового комп'ютера, за умови, що етикет змагань це дозволяє. Шестифігурну базу даних (KQQKQQ) було використано для аналізу ендшпілю, який трапився в партії за листуванням Каспаров проти світу.[33] Гравці також використовували ендшпільні таблиці після гри для аналізу ендшпілів, які виникають за шахівницею під час неї.

Гравці повинні знати, що деякі ендшпільні бази даних ігнорують правило п'ятдесяти ходів. Згідно з цим правилом, якщо п'ятдесят ходів проходять без побиття або ходу пішаком, то будь-хто з гравців може зафіксувати нічию. ФІДЕ змінювала правила кілька разів, починаючи з 1974 року, дозволивши сто ходів для ендшпілів, у яких п'ятдесят ходів було недостатньо для перемоги. 1988 року ФІДЕ допустила сімдесят п'ять ходів для ендшпілів KBBKN, KNNKP, KQKBB, KQKNN, KRBKR, а також KQPKQ з пішаком на сьомій горизонталі, оскільки бази даних виявили позиції в цих ендшпілях, які потребують понад п'ятдесят ходів для перемоги. У 1992 році ФІДЕ скасувала ці винятки і відновила початковий варіант правила п'ятдесяти ходів[21]. Таким чином база даних може визначити позицію як виграшну або програшну, хоча насправді вона може бути нічийною за правилом п'ятдесяти ходів. У 2013 році ICCF змінила правила для шахових турнірів за листуванням, починаючи з 2014 року; гравець може оголосити перемогу або нічию згідно з шестифігурною базою даних.[34] У цьому випадку правило п'ятдесяти ходів не застосовується, а кількість ходів до мату не береться до уваги.

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

Комп'ютерні шахи

Знання, що містяться в ендшпільних базах даних, дають комп'ютеру величезну перевагу в ендшпілі. Комп'ютери можуть не лише досконало зіграти вже отриманий ендшпіль, але й спростити гру до виграшного ендшпілю зі складнішого положення.[35] Для цієї мети деякі програми використовують "bitbases", які дають теоретичну оцінку позиції (виграш, програш або нічия) без вказання кількості ходів до переходу або мату. Іноді навіть ці дані стискаються і bitbase лише показує, чи є позиція виграшна чи ні, не розрізняючи програш і нічию. Наприклад Shredderbases, яку використовує програма Shredder, являє собою тип bitbase[36], який вміщує три-, чотири- і п'ятифігурні bitbases у 157 МБ. Це лише невелика частина від 7,05 ГБ, які потрібні для ендшпільних таблиць Налімова.[37] Деякі експерти комп'ютерних шахів відзначають практичні недоліки застосування ендшпільних баз даних.[38] На додаток до ігнорування правила п'ятдесяти ходів, комп'ютер у складному становищі може уникати програшного варіанту, показаного базою даних, хоча його суперник на практиці не може виграти з того положення, якщо сам не має бази даних. Негативним ефектом може бути передчасна здача, або ж вибір гіршого варіанту, який веде до поразки з меншим опором, ніж міг би бути в грі без використання бази даних.

Ще один недолік полягає в тому, що для зберігання багатьох тисяч позицій у базі даних потрібно багато комп'ютерної пам'яті. Ендшпільні таблиці Налімова з використанням передових методів стиснення даних методи вимагають 7,05 ГБ дискового простору для всіх п'ятифігурних ендшпілів. Шестифігурні ендшпілі займають приблизно 1,2 ТБ.[39][40] Для зберігання семифігурної бази даних Ломоносова потрібно 140 ТБ дискового простору.[41] Деякі комп'ютери грають загалом краще, якщо їхня пам'ять замість збереження цієї інформації повністю присвячена звичайному пошуку і оцінці. Сучасні рушії навчилися досить добре аналізувати далеко наперед елементарні ендшпілі, щоб впоратися з ними без звернення до бази даних (тобто не зазнаючи ефекту горизонту). Лише в складніших ендшпілях використання бази даних дозволяє таким рушіям суттєво підвищити рівень гри.

Ендшпільна база даних Syzygy, розроблена Рональдом де Маном, вийшла у квітні 2013 року, у вигляді, оптимізованому для використання шаховими програмами під час пошуку. Вона складається з двох окремих баз даних для кожного ендшпілю: менша ПНП-база (перемога-нічия-поразка), яка враховує правило 50 ходів, а також більша ВДН-база (відстань до нульового півходу, тобто ходу пішаком або побиття). ПНП-база, яка займає небагато місця і може вміститися на твердотілому накопичувачі, призначена для швидкого доступу під час пошуку, ВДН-база призначена для використання at the root position для вибору теоретично найшвидшого виграшу замість здійснення пошуку. База даних Syzygy доступна для всіх шестифігурних ендшпілів, а тепер її підтримують багато провідних рушіїв, включаючи Комодо, Діп Фріц, Гудіні і Стокфіш.[42]. Починаючи з серпня 2018 року всі[43] база даних для всіх семифігурних ендшпілів також стала доступною[44].

Теорія ендшпілю
Льюїс Стіллер, 1991
abcdefgh
8
8
77
66
55
44
33
22
11
abcdefgh
Позиція мат за 262 (хід білих). Білі виграють.

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

  • KBBKN — 1851 року Гернгард Горвіц і Йозеф Клінг припустили, що чорні можуть досягнути нічиєї, побудувавши захисну фортецю, але бази даних показали загальну перемогу білих, з максимальною глибиною до переходу 66 або 67 і глибиною до мату - 78.[45] (див. також безпішаковий ендшпіль.)
  • KNNKP — максимальні ГДП = ДТМ = 115 ходів.
  • KNNNNKQ — коні виграють у 62.5% позицій, а максимальна ГДМ становить 85 ходів.[46][47]
  • KQRKQR — попри рівність матеріалу, гравець, що ходить першим, виграє у 67.74% позицій.[48] Максимальна ГДП = 92, а максимальна ГДМ = 117. У цьому ендшпілі, а також у KQQKQQ, перший гравець, який робить шах, зазвичай перемагає.[49]
  • KRNKNN і KRBKNN — Фрідріх Амелунг проаналізував ці два закінчення в 1900-х роках.[50] KRNKNN і KRBKNN виграшні для сильнішої сторони відповідно у 78% і 95% випадків.[51] База даних ГДП Стіллера знайшла у цих ендшпілях кілька довших виграшів. Найдовша перемога у KRBKNN займає 223 ходи ГДП і 238 ходів ГДМ (не показано). Ще цікавіша позиція праворуч, де білі виграють, починаючи з 1. Ke6! Стіллер повідомляє про 243 ходи ГДП, пізніше встановлено, що ГДМ становить 262 ходи.[52]

Упродовж низки років позиція "мат-за-200" (перша діаграма нижче) утримувала рекорд як найдовший знайдений комп'ютерами форсований мат. (1889 року Отто Тітус Блаті склав композицію "мат за 292 ходи", хоча і з нелегального початкового положення.[53]) У травні 2006 року Бурзуцький і Коновал виявили позицію KQNKRBN з приголомшливою глибиною до перетворення 517 ходів.[54] Це більш як удвічі перевищує максимум Стіллера і майже на двісті ходів випереджає попередню ГДП 330 для позиції KQBNKQB_1001. За словами Бурзуцького: "Це був великий сюрприз для нас і велика данина складності шахів."[55][56] Пізніше, коли з'явилась семифігурна база даних Ломоносова, було знайдено позицію з глибиною до мату 546 ходів (третя діаграма знизу).[57][58]

abcdefgh
8
8
77
66
55
44
33
22
11
abcdefgh
Позиція мат за 200 (хід білих). Перший хід білого пішака на 119-му ході.
abcdefgh
8
8
77
66
55
44
33
22
11
abcdefgh
Позиція мат за 154 (хід чорних). Чорні виграють.
abcdefgh
8
8
77
66
55
44
33
22
11
abcdefgh
Позиція мат за 546 (хід білих).[58] Позицію знайдено за допомогою семифігурної бази даних Ломоносова. (У цьому прикладі 8-му фігуру забрано тривіальним побиттям на першому ході.)

Багато позицій є виграшними, хоча й можуть на перший погляд не здаватися такими. Наприклад, позиція на середній діаграмі є виграшною для чорних за 154 ходи (пішака білих вони б'ють приблизно на 80-му ході).[59]

Етюди
Е. Погосянц, EG 1978


abcdefgh
8
8
77
66
55
44
33
22
11
abcdefgh
Білі ходять і виграють. Композитор пропонував рішення 1. Ne3, але база даних показала, що 1. h4 також виграє.
Гаролд ван дер Гейден, 2001


abcdefgh
8
8
77
66
55
44
33
22
11
abcdefgh
Білі ходять і досягають нічиєї

Оскільки багато складених етюдів повторюють позиції в ендшпільних базах даних, то коректність таких етюдів можна перевірити за допомогою цих баз. У такий спосіб показано некоректність деяких етюдів. Рішення композитора може не працювати, або не бути єдино можливим. Інший спосіб, у який бази даних впливають на етюди, це зміни в оцінці ендшпілю. Наприклад, ендшпіль з ферзем і слоном проти двох тур раніше вважали нічийним, проте, ендшпільні бази даних показали, що ферзь і слон виграють. Тож майже всі етюди, які ґрунтуються на цьому ендшпілі, є некоректними.[60]

Наприклад, Ерік Погосянц склав перший етюд праворуч, у якому білі ходять і виграють. Його основною лінією була 1. Ne3 Rxh2 2. 0-0-0#! Проте, бази даних виявили, що 1. h4 також веде до перемоги білих, за 33 ходи, хоча чорні й можуть побити пішака (не найкращий хід чорних – у разі побиття вони програють за 21 хід, а Kh1-g2 програє за 32 ходи). До речі, бази даних не бачать рішення композитора, оскільки воно включає рокіровку.[61]

Хоча бази даних і показують некоректність деяких етюдів, але вони й допомагають скласти інші. Композитори можуть знайти в базі даних цікаві позиції, такі як цугцванг, за допомогою методу добування даних. Для всіх трьох-п'яти-фігурних ендшпілів і безпішакових шестифігурних ендшпілів складено і опубліковано повний перелік обопільних цугцвангів.[62][63][64]

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

Не тільки думки розходяться широко, але їх часто дотримуються твердо, навіть люто: на одному полюсі думка, що оскільки ми ніколи не можемо бути впевнені, чи комп'ютер був використаний, безглуздо намагатися відрізнити, тому ми повинні просто оцінити "етюд" за його змістом, без звернення до його походження; на іншому полюсі перебуває думка про те, що підняття цікавої позиції за допомогою 'миші' зі згенерованого комп'ютером готового списку в жодному разі не є композицією, тому ми повинні заборонити всі такі позиції.[65]

Сам Ройкрофт згоден з останнім підходом. Він продовжує: "одне тільки ясно: грань між класичною композицією і витвором комп'ютера потрібно зберегти якомога довше: якщо є ім'я, пов'язане з діаграмою етюду, то воно і є заявкою на авторство."[65]

Міжнародний майстер, шаховий тренер і автор Марк Дворецький зайняв більш терпиму позицію. Він так у 2006 році прокоментував етюд Гаролда ван дер Гейдена, опублікований 2001 року, у якому позиції праворуч досягнуто одразу після трьох вступних ходів. Нічийний хід білих - 4. Kb4!! (але не 4. Kb5), ґрунтуючись на взаємному цугцвангу, що може трапитись трьома ходами пізніше.

Дворецький це коментує так:

Тут ми змушені торкнутися одного делікатного питання. Я впевнений, що цю унікальну ендшпільну позицію виявлено за допомогою знаменитої комп'ютерної бази Томпсона. Чи є це 'недоліком', який применшує досягнення композитора? Так, комп'ютерна база даних є інструментом, доступним нині для будь-кого. З неї, безумовно, ми могли б отримати ще унікальніші позиції – є деякі шахові композитори, які роблять це регулярно. Стандартом для оцінки тут повинен бути досягнутий результат. Таким чином: чудеса, засновані на складному комп'ютерному аналізі, а не на гостроті власних ідей, напевно, цікаві лише деяким естетам.[66]

"Зіграй у шахи з Богом"

На сайті Bell Labs Кен Томпсон колись утримував посилання на якусь частину своєї бази даних. У заголовку було написано: "Зіграй у шахи з Богом".[67]

Маючи на увазі довгі шляхи до виграші Стіллера, Тім Краббе зробив подібну нотатку:

Гросмейстер не зіграв би ці ендшпілі краще, ніж той, хто навчився грати в шахи вчора. Це різновид шахової гри, який не має нічого спільного з шахами, це шахи, які ми не могли собі навіть уявити без комп'ютера. Ходи Стіллера чарівні, майже страшні, бо ти знаєш, що вони є істина, алгоритм Бога – це як ніби тобі відкрився сенс життя, але ти не розумієш жодного слова.

Книги

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

Таблиці
Семифігурні енндшпілі
Атакувальні фігуриЗахисні фігуриНайдовший виграш
476
380
400
186
143
140
549
260
201
143
211
211
298
261
293
217
224
259
228
297
176
182
184
296
269
191
104
79
92
189
77
88
70
98
262
246
246
238
105
149
140
232
86
102
210
176
304
152
262
212
84
134
112
117
122
182
120
195
229
150
192
176
197
545
169
106
115
154
141
94
141
107
247
213
184
239
192
297

Див. також

Примітки
  1. EGTBs Chessprogramming website
  2. Lomonosov Endgame Tablebases. ChessOK.
  3. Website of KingsRow about the creation of a tablebases for 8x8 and 10x10 checkers
  4. gothicchess.com; examples of long endings for Gothic Chess
  5. Ralpf Gasser (1996). Solving nine men's morris.
  6. Allis, Louis Victor (1994). Searching for Solutions in Games and Artificial Intelligence (PDF). Department of Computer Science, University of Limburg. с. 8. ISBN 90-900748-8-0. Процитовано 3 травня 2009.
  7. Levy & Newborn, pp. 25-38
  8. Levy & Newborn, pp. 129-30
  9. Stiller, p. 84
  10. R. E. Bellman (February 1965). On the application of dynamic programming to the determination of optimal play in chess and checkers. Proceedings of the National Academy of Sciences of the United States of America 53 (2): 244–246. doi:10.1073/pnas.53.2.244.
  11. T. Ströhlein (1970). Untersuchungen über kombinatorische Spiele [Translation: Investigations on Combinatorial Games] Ph.D. Thesis. Technical University of Munich.
  12. See also The 'End-Papers' (PDF). EG (52): 25. July 1978. Архів оригіналу за 25 березня 2009. Процитовано 1 квітня 2007. «Niblett and Kopec described, and later demonstrated, the optimal 0103 data base. (This work was in fact first done and published by Thomas Strohlein, Munich, in 1970, but only a single analytical line is contained in his doctoral thesis.)»
  13. T. Niblett; A. J. Roycroft (June 1979). How the GBR Class 0103 Data Base was Created (PDF). EG (56): 145–46. Архів оригіналу за 28 вересня 2007. Процитовано 4 травня 2007.
  14. Levy & Newborn, p. 144
  15. Див. також:
  16. Stiller, pp. 68-113
  17. Див. також: L. B. Stiller (1991). Some Results from a Massively Parallel Retrograde Analysis. ICCA Journal.
  18. Convekta Ltd. Lomonosov Endgame Tablebases.
  19. J. Hurd; G. McC. Haworth. Chess Endgame Data Assurance. (PDF). Процитовано 13 грудня 2008.
  20. Gary M. Danelishen (25 лютого 2008). The Final Theory of Chess. Open Wiki of Chess Openings. с. 6. ISBN 978-0-9815677-0-9. Процитовано 10 серпня 2011.
  21. G. McC. Haworth (March 2000). Strategies for Constrained Optimisation (PDF). ICGA Journal. Архів оригіналу за 29 вересня 2007. Процитовано 20 червня 2009.
  22. 7-piece Syzygy tablebases are complete. Lichess (англ.). Процитовано 27 серпня 2018.
  23. Levy & Newborn, pp. 140-43
  24. See also Stiller 1995:93-98.
  25. Muller, H.G. EGTB generator. Процитовано 3 травня 2009. «Pawns would break the front-back and diagonal symmetries, because they care about direction in their moves.»
  26. Tim Krabbé. Stiller's Monsters or Perfection in Chess. Процитовано 1 квітня 2007.
  27. Aaron Tay. A guide to Endgames Tablebase. Процитовано 2 травня 2009.
  28. M. Bourzutschky (27 серпня 2006). 7-man endgames with pawns. CCRL Discussion Board. Процитовано 14 червня 2010.
  29. Stiller, pp. 99-100
  30. H. J. Herik; I. S. Herschberg; N. Naka (1987). A Six-Men-Endgame Database: KRP(a2)KbBP(a3). ICGA Journal 10 (4): 163–180.
  31. E. Bleicher (26 серпня 2004). Building Chess Endgame Databases for Positions with many Pieces using A-priori Information. (PDF). Архів оригіналу за 27 вересня 2007. Процитовано 1 квітня 2007.
  32. K. Müller (May 2005). Freeze! (PDF). Endgame Corner. ChessCafe.com. Процитовано 1 квітня 2007.
  33. E. V. Nalimov; C. Wirth; G. McC. Haworth (1999). KQQKQQ and the Kasparov–World Game. ICGA Journal 22 (4): 195–212.
  34. The introduction of table base claims by Eric Ruch - ICCF President
  35. Steven A. Lopez (11 листопада 2006). Shredderbases. ChessBase.com. Процитовано 1 квітня 2007.
  36. Profile of Eiko Bleicher, co-developer of shredderbase. Процитовано 6 квітня 2013.
  37. Shredder Computer Chess Download - Shredderbases. Процитовано 9 серпня 2008.
  38. A. Tay (30 червня 2002). Can use of endgame tablebases weaken play?. Процитовано 1 квітня 2007.
  39. David Kirkby (12 березня 2007). Endgame Tablebases. ChessDB Tutorial. Процитовано 1 квітня 2007.
  40. Stefan Meyer-Kahlen. Shredder Computer Chess Download - Endgame Database Info. Процитовано 17 серпня 2008.
  41. Lomonosov Endgame Tablebases, http://chessok.com/?page_id=27966, 10 June 2017
  42. Syzygy Bases. Chess Programming Wiki. Процитовано 24 березня 2015.
  43. 7-piece Syzygy tablebases are complete.
  44. 7-man Syzygy download.
  45. A. J. Roycroft (1984). Two Bishops Against Knight (PDF). EG (75): 249. Архів оригіналу за 28 вересня 2007. Процитовано 4 травня 2007.
  46. Tim Krabbé (12 квітня 2005). 282. First 7-piece endgame database. Open Chess Diary. Процитовано 25 березня 2007.
  47. Emil Vlasák (21 липня 2005). News in 7 piece EGTB. Процитовано 25 березня 2007.
  48. G. McC. Haworth (August 2001). Discarding Like Pieces (PDF). Архів оригіналу за 29 вересня 2007. Процитовано 1 квітня 2007.
  49. Nunn, p. 379, 384
  50. Stiller, p. 81
  51. Tim Krabbé (8 квітня 2000). 60. Play chess with God. Open Chess Diary. Процитовано 13 травня 2007.
  52. Stiller, pp. 102-8
  53. Blathy. 21 червня 2003. Архів оригіналу за 25 жовтня 2009. Процитовано 4 травня 2007.
  54. Пал Бенко, Endgame Lab: The Magnificent Seven, Chess Life, April 2013, p. 44
  55. Tim Krabbé (31 березня 2006). 311. White plays and wins in 330 moves. Open Chess Diary. Процитовано 4 травня 2007.
  56. Tim Krabbé (26 травня 2006). 316. A 517-move win. Open Chess Diary. Процитовано 4 травня 2007.
  57. RybkaForum.net
  58. "Who wins from this puzzle?" A chess position with a mate-in-546 answer presented as a puzzle, and discussion.
  59. Six-Man Endgame Server
  60. Nunn, pp. 367-68
  61. Tim Krabbé (15 вересня 2006). 324. A cooked, correct study. Open chess diary. Процитовано 4 травня 2007.
  62. G. McC. Haworth (2001). 3–5 Man Mutual Zugzwangs in Chess. У J.W.H.M. Uiterwijk. Proceedings of the CMG 6th Computer Olympiad Computer-Games Workshop. TR CS 01-04.
  63. G. McC. Haworth (2001). Ken Thompson's 6-man Tables. ICGA Journal.
  64. G. McC. Haworth; P. Karrer; J. A. Tamplin; C. Wirth (2001). 3–5 Man Chess: Maximals and Mzugs. ICGA Journal 24 (4): 225–30.
  65. A. J. Roycroft (July 2003). Editorial (PDF). EG (149): 51. Архів оригіналу за 28 вересня 2007. Процитовано 4 травня 2007.
  66. M. Dvoretsky (July 2006). Study Composing Tourney (PDF). The Instructor. ChessCafe.com. Процитовано 1 квітня 2007.
  67. Ken Thompson (21 серпня 2002). Play chess with God. Архів оригіналу за 24 січня 2007. Процитовано 25 березня 2007.

Посилання
This article is issued from Wikipedia. The text is licensed under Creative Commons - Attribution - Sharealike. Additional terms may apply for the media files.