Ендшпільна база даних — занесена в комп'ютер база даних, яка містить попередньо обчислений вичерпний аналіз позицій шахових ендшпілів. Її зазвичай використовує комп'ютерний шаховий рушій під час гри, або людина чи комп'ютер, які ретроспективно аналізують вже завершену гру.
Вона містить теоретичну оцінку кожної позиції (виграш, програш або нічия) з точки зору кінцевого результату, до якого веде кожен можливий хід у кожному можливому положенні, і скільки ходів потрібно, щоб досягти цього результату за . Таким чином, вона свого роду відіграє роль оракула, завжди показує оптимальні ходи як для , так і для чорних. Зазвичай така база даних містить усі позиції, які можливі за певної кількості фігур, що залишилися на шахівниці.
Ендшпільні таблиці формуються за допомогою ретроспективного аналізу, який опрацьовує всі положення назад від мату або пату. До 2005 року всі шахові позиції з шістьма фігурами (включаючи двох королів) були вирішеними. До серпня 2012 року були вирішеними вже всі позиції до семи фігур (позиції з самотнім королем проти короля і п'яти фігур були опущені як "цілком очевидні").
Ці вирішення суттєво просунули вперед розуміння шаховим співтовариством теорії ендшпілю. Доведено виграшність деяких позицій, які люди раніше вважали нічийними. Аналізуючи деякі позиції за допомогою бази даних, можна знайти виграш у понад 500 ходів, а це не лише виходить далеко за межі пошуку людини, але й перебуває за межами можливостей комп'ютера під час гри. Тому бази даних також ставлять під питання правило п'ятдесяти ходів, оскільки тепер відомо багато позицій, які є виграшними, але все-одно ведуть до нічиєї через правило 50 ходів. Бази даних збагатили змагальні шахи і полегшили складання етюдів. Вони є потужним інструментом, який дає змогу шахістам вивчати найскладніші ендшпілі.
Хоча існують і ендшпільні бази даних для інших настільних ігор, таких як шашки,Website of KingsRow about the creation of a tablebases for 8x8 and 10x10 checkers некласичні варіанти шахівgothicchess.com; examples of long endings for Gothic Chess або млин , якщо гру не вказано, то за умовчанням йдеться про шахи.
Передумови Якщо не брати до уваги фізичних обмежень апаратного забезпечення, то в принципі можна за умови, що відома повна інформація і відсутня жодна випадковість. Сильні рішення, тобто алгоритми, які дають найсильнішу гру з будь-якої позиції, відомі для деяких простих ігор, таких як хрестики-нулики (нічия за ідеальної гри) і чотири в ряд (перший гравець виграє). існують для деяких дещо складніших ігор, таких як шашки (за ідеальної гри з обох сторін гра вважається нічийною, але не для кожної позиції, до якої привела неідеальна гра, відомий наступний ідеальний хід). Інші ігри, такі як шахи (від початкового положення) і ґо, не вирішені, оскільки перевищує можливості комп'ютерів станом на 2018 рік оцінити всі можливі позиції. Щоб зменшити складність гри, дослідники модифікували ці складні ігри, зменшивши розмір шахівниці, або кількість фігур, або обидва ці фактори.
Комп'ютерні шахи - одна з найдавніших галузей досліджень штучного інтелекту, яка бере свій початок у 1930-х роках. 1949 року Клод Шеннон запропонував формальні критерії для оцінки шахових ходів. У 1951 році Алан Тюрінг розробив примітивну шахову програму, яка присвоює значення для матеріалу та мобільності; програма "грала" в шахи на основі ручних обчислень Тюрінга.Levy & Newborn, pp. 25-38 Втім, навіть коли почали розвиватися змагальні шахові програми, вони показали кричущу слабкість у грі в ендшпілі. Програмісти застосовували конкретні евристики щодо ендшпілю – наприклад, король повинен рухатися до центру шахівниці.Levy & Newborn, pp. 129-30 Проте, було необхідне загальніше рішення.
1965 року Річард Беллман запропонував створити базу даних, яка б вирішила шаховий і шашковий ендшпілі за допомогою ретроспективного аналізу.Stiller, p. 84 Замість аналізу вперед починаючи з поточної позиції на шахівниці, база даних має аналізувати назад позиції, де один із гравців поставив мат або потрапив у становище пату. Таким чином, шаховий комп'ютер вже не змушений аналізувати ендшпільні позиції під час гри, оскільки їх вирішено заздалегідь. Він не буде припускатись помилок, оскільки база даних завжди показує найкращий хід.
1970 року Томас Штрьоляйн опублікував докторську дисертаціюSee also , яка містила аналіз таких класів ендшпілю: , , , , , а також . У 1977 році базу даних Томпсона KQKR використано в матчі проти гросмейстера Волтера Брауна.
Кен Томпсон та інші допомогли розширити ендшпільні бази даних, щоб вони охопити всі чотири- і п'ятифігурні ендшпілі, включаючи, зокрема, , і .Levy & Newborn, p. 144Див. також:
1995 року Льюїс Стіллер опублікував дисертацію з дослідженнями баз даних для деяких шестифігурних закінчень.Stiller, pp. 68-113Див. також:
Серед пізніших авторів, які зробили свій внесок:
, на честь якого названо популярні бази даних Налімова; Ейко Бляйхер, який адаптував концепцію баз даних до програми під назвою "Фрізер" (див. нижче); Гай Гаворт, науковець з , який багато публікувався на цю тему в та інших місцях; Марк Бурзуцький і Яків Коновал, які спільно аналізувати семифігурні ендшпілі; Пітер Каррер, який побудував спеціалізовану семифігурну базу () для ендшпілю онлайн-матчу ; Володимир Махнишев і Віктор Захаров з Московського державного університету, які закінчили створення 4+3 глибина до мату-ендшпільної бази даних (зокрема закінчення KPPPKPP на 525 ходів) у липні 2012 року. Вони називаються таблицями Ломоносова. Наступний набір 5+2 ГДМ-ендшпільних таблиць (350 закінчень, зокрема KPPPPKP) завершено в серпні 2012 року. Високої швидкості генерації варіантів розробники досягнули завдяки використанню суперкомп'ютера (Top500 світу ). Розмір всіх баз даних до семи фігур становить близько 140 ТБ.
Бази даних усіх ендшпілів до семи фігур доступні для безкоштовного скачування, а також доступ до них можна отримати через вебінтерфейси (див. зовнішні посилання нижче). База даних Налімова вимагає понад один терабайт дискового простору.
Генерація бази даних
Показники: глибина до переходу і глибина до мату
Перед створенням бази даних програміст повинен вибрати метрику оптимальності – іншими словами, повинен визначити, в який момент гравець "виграв" гру. Кожну позицію можна визначити у термінах відстані (тобто кількості ходів) від бажаної кінцевої мети. Зазвичай використовуються дві метрики:
Глибина до мату (ГДМ). Мат - єдиний спосіб виграти гру. Глибина до переходу (ГДП). Сильніша сторона може також перемогти, вигравши матеріал, таким чином перейшовши в простіший ендшпіль. Наприклад, у закінченні KQKR перехід відбувається, коли білі виграють чорну туру.
Крім того Гаворт розглянув дві інші метрики, а саме "глибину до ходу-обнулення" (ГДО) і "глибину за правилом" (ГЗП). Хід-обнулення - це хід, який скидає відлік руху до нуля за правилом п'ятдесяти ходів, тобто мат, побиття, або пересування пішака. Ці метрики підтримують правило п'ятдесяти ходів. Бази даних ГЗП станом на кінець 2018 року ще не розраховані. 7-фігурна база даних ГДО стала доступною публічно в серпні 2018 року.
Різницю між ГДМ і ГДП можна зрозуміти, аналізуючи діаграму праворуч. Подальші дії білих, залежать від їхнього вибору метрики. МетрикаГраГДПГДМГДП1. Qxd1 Kc8 2. Qd2 Kb8 3. Qd8#13ГДМ1. Qc7+ Ka8 2. Qa7#22 Діючи за метрикою ГДП, білі повинні побити туру, оскільки це відразу приводить до позиції, яка, безумовно, виграшною (ГДП = 1), але насправді поставити мат займе ще два ходи (ГДМ = 3). На відміну від цього, згідно з метрикою ГДМ білі матують у два ходи, тож ГДМ = ГДП = 2.
Ця різниця характерна для багатьох ендшпільних позицій. Зазвичай ГДП менша, ніж ГДМ, але ГДМ веде до найшвидшого мату. Винятки виникають тоді, коли слабша сторона має лише короля, а також у незвичайному ендшпілі два коня проти пішака; тут ГДП = ГДМ, оскільки відсутній матеріал захисту, який потрібно побити, або ж побиття не приносить бажаного результату. (Справді, побиття пішака в останньому з ендшпілів призводить до нічиєї, якщо сильніша сторона негайно не ставить мат.)
Крок 1: генерація всіх можливих позицій
Після вибору метрики першим кроком є генерація всіх позицій з заданим матеріалом. Наприклад, щоб створити базу даних ГДМ для ендшпілю: король і ферзь проти короля (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. Кілька сотень з цих позицій є нелегальними, неможливими, або симетричними віддзеркаленнями одна одної, тож реальна їх кількість дещо менша.Levy & Newborn, pp. 140-43See also Stiller 1995:93-98.
Для кожної позиції база даних оцінює ситуацію окремо, якщо хід білих і якщо хід чорних. Маючи ферзя білі виграють майже у всіх випадках, форсуючи мат не більш, як за десять ходів. Деякі позиції є нічийними через пат або ж неминучу втрату ферзя.
Кожна наступна фігура, додана до множить кількість унікальних позицій приблизно на 60, така приблизна кількість клітинок, ще не зайнятих іншими фігурами.
Ендшпіль з одним або кількома пішаками збільшує складність, оскільки аргумент симетрії зменшується. Оскільки пішаки можуть рухатись вперед, а не вбік, то обертання і вертикальне віддзеркалення шахівниці призводить до фундаментальних змін у характері позиції. Найкращий розрахунок симетрії досягається шляхом обмеження одного пішака до 24 квадратів у прямокутнику a2-a7-d7-d2. Всі інші фігури й пішаки можна розмістити на будь-якій з 64 клітинок, які дозволяє цей пішак. Таким чином, ендшпіль з пішаками має у 24/10 = 2.4 рази більшу складність, ніж безпішаковий ендшпіль з такою самою кількістю фігур.
Крок 2: Оцінка позицій за допомогою ретроградного аналізу Тім Краббе так пояснює процес створення бази даних:
"Ідея полягає в тому, що база даних містить усі можливі позиції з урахуванням матеріалу [примітка: як у попередньому розділі]. Потім підбаза даних складається з усіх позицій, де чорним ставлять мат. Потім йде підбаза, у якій білі можуть поставити мат. Потім підбаза, у якій чорні не можуть завадити білим поставити мат наступним ходом. Потім та, де білі завжди можуть досягнути позиції, коли чорні не можуть перешкодити їм поставити мат наступним ходом. І так далі, завжди на півхід далі від мату, поки не буде знайдено всі позиції, які таким чином до нього ведуть. Потім всі ці позиції за допомогою бази даних пов'язуються назад до мату найкоротшим шляхом. Це означає, що, крім еквіоптимальних ходів, всі ходи по такому шляху досконалі: хід білих завжди веде до найшвидшого мату, а хід чорних - до найповільнішого".
Ретроспективний аналіз необхідний лише від позицій мату. Від інших позицій не потрібно працювати, оскільки кожна позиція, якої не можна досягнути від позицій мату, є нічийною.
Рис. 1 ілюструє ідею ретроспективного аналізу. Білі матують за два ходи 1. Kc6, веде до позиції на рисунку 2. Тоді, якщо 1...Kb8 2. Фb7#, а якщо 1...Кd8 2. Фd7# (Рис. 3).
На рис. 3, ситуація перед другим ходом білих визначається як "мат в один ." На рис. 2, після першого ходу білих "мат у два півходи," незалежно від того, як грають чорні. Нарешті, початкове положення на Рис. 1 це "мат у три півходи" (тобто два ходи), тому що воно веде прямо до Рис. 2, вже визначеного як "мат у два півходи." Цей процес, який пов'язує поточне положення з іншим положенням, яке могло існувати на один півхід раніше, може тривати нескінченно.
Кожна позиція оцінюється як виграш чи програш за певну кількість ходів. Наприкінці ретроградного аналізу позиції, які не позначені як виграш чи програш, обов'язково є нічийними.