База от данни за шахматни окончания е компютъризирана база данни, съдържаща предварително изчислен, изчерпателен анализ на шахматни ендшпили. Такава база данни съхранява резултати (победа, равенство, загуба) за всяка възможна позиция от шахматното окончание, както при ход на белите, така и при ход на черните. Някои бази данни, например таблиците на Налимов, съдържат оценки на позиции при ход само на едната страна - само бели или само черни. Една и съща позиция с различен ред на ход се съдържа в различни таблици. Някои често срещани бази данни също съдържат броя ходове, необходими за постигане на теоретичен резултат (мат, преминаване към печеливш ендшпил и т.н.) с най-добрата игра от двете страни. Базите данни за шахматните окончания се създават чрез ретроспективен анализ, като се движат от всички възможни крайни позиции в обратната посока – в посока на увеличаване на броя ходове, необходими за постигане на тези крайни позиции.
Стандартният шах може да има 29 045 304 различни ендшпила, на които съответстват 58 084 310 ендшпила + комбинации за ход.
История В историята на компютърния шахмат има няколко изследователи, дали и реализирали идеята за компютърни игри в малкофигурни окончания, използвайки предварително разчетена изчерпваща таблица на всички възможни позиции.
През 1965 г. Ричард Белман ( Richard Bellman) за първи път предлага използването на метода на ретроспективен анализ за създаване на база данни за решения на шахматни и шашечни ендшпили. За разлика от обикновеното пряко търсене, започващо с конкретна позиция, стояща на дъска, ендшпилните бази данни, включващи в себе си всички възможни премествания на фигурата, извършват търсене в обратна посока: започвайки с позиция, където една от страните вече е получила пат или мат, и завършвайки с конкретната позиция, стояща на дъската, позволяваща да се получи правилното решение с абсолютна точност. По този начин, шахматният компютър по време на играта повече не е необходимо да произвежда изчисления на ендшпила, а достатъчно само да види в базата данни предварително изчислен резултат и да направите идеален ход.
През 1970 г. Томас Щрьоляйн ( Thomas Ströhlein) защитава докторска дисертация, в която се анализират такива окончания, като ЦДЦ, ЦТЦ, ЦпЦ, ЦДЦТ, ЦТЦО и ЦТЦК. Използвани съкращения: Ц – цар, Д – дама, Т – топ, О – офицер, К – кон, п – пешка. Първо се изброяват белите фигури, започвайки с царя, след това черните.
През 1977 г. Кен Томпсън на конференция на Международната федерация за обработка на информация в Торонто представя съставена от него таблица за всички възможни позиции в ендшпила „Цар и топ срещу цар и дама“ (ЦТЦД). Общият брой на позициите за него е около 4 милиона. Кен Томпсън провежда няколко показателни изяви — компютърна игра за играча, владеещ топа. Този ендшпил е теоретически изгубен и шахматист на ниво майстор, владеещ дамата, обикновено лесно го спечелва срещу всеки противник. Следователно на компютъра е поставена задача максимално да отдалечи своята теоретически неизбежна загуба. Резултатите от експериментите, в които компютърът е играл с шахматисти, са доста интересни. Против програмата се опитали да играят световният екс-шампион по кореспондентен шах Ханс Берлинър и шампионът на Канада Лоуренс Дей. Никой от двамата не успял да победи програмата, въпреки че произволно такава позиция се счита за спечелена. Същността е в това, че теоретически безупречната игра на компютъра често изглежда нелогично, противоречи на принципите, предписани от шахматната теория (например, обикновено се препоръчва да не се отдалечава топа от царя за избягване на възможни вилки, но програмата нерядко е направила това), необичайните ходове на компютъра обърквали шахматиста и той пропускал да спечели, не успявал за 50 хода да постави мат или да вземе топа.
През 70-те и 80-те години на ХХ век идеята за предварително изчислените окончания се развива много бавно, тъй като скоростта и паметта на компютрите от онова време са значително ограничение и не позволяват подробни бази данни. Въпреки това, Кен Томпсън и други ентусиасти продължават бавно да генерират ендшпили с малко фигури и след известно време са преброени всички окончания с 4 фигури, а до края на 80-те години – всички окончания с 5 фигури, включително такива интересни позиции като ЦООЦК (два офицера срещу кон), ЦДпЦД (дама и пешка срещу дама) и ЦТпЦТ (топ и пешка срещу топ). През 1995 г. Луис Стилър публикува работа, посветена на изследването на някои 6-фигурни окончания.
Ейко Блайхер е адаптирал концепцията за таблична база към програма, наречена „Freezer“. Гай Хауърт, академик в Редингски университет, е публикувал много в ICGA Journal и другаде. Марк Бурзучки и Яков Коновал са си сътрудничили за анализиране на ендшпили със седем фигури на дъската. Петер Карер конструира специализирана база данни за ендшпила със седем фигури (ЦДп,ЦДпп) от кореспондентския мач Гари Каспаров срещу Света през 1999 г. След това в партията е използвана таблица за анализ на ендшпила с шест фигури (ЦДп,ЦДп), показан на диаграмата вдясно.
Генериране на бази от данни Метрики и показатели Преди да създаде база данни, програмистът трябва да избере метрика на оптималност – с други думи, трябва да определи в кой момент играчът е „спечелил“ играта. Всяка позиция може да бъде определена чрез нейната дълбочина или разстояние (т.е. броя на ходовете) от желаната крайна точка. Обикновено се използват два показателя:
Дълбочина до мат (ДДМ) //. Матът е единственият сигурен показател за спечелване на играта. Дълбочина до преобразуване (ДДП) //. По-силната страна може също да спечели чрез взeмане на материал, като по този начин позицията се преобразува в по-прост ендшпил с доказан изход. Например в позиция ЦДЦТ преобразуването става, когато белите вземат черния топ.
Разликата между ДДМ и ДДП може да се разбере, като се анализира диаграма 1. Начинът, по който белите трябва да продължат, зависи от това кой показател се използва: Метрика Ходове ДДМ ДДП ДДM 1. Дc7+ Цa8 2. Дa7(Дс8)Х. 2 2 ДДП 1. Д:d1 Цc8 2. Дd5 Цb8 3. Дd8(Дb7)Х. 3 1
Според показателя ДДМ белите матират в два хода, така че ДДМ = ДДП = 2. За разлика от това, по показателя ДДП белите първо трябва да вземат топа, защото това веднага води до позиция, която със сигурност ще спечели (ДДП = 1), но всъщност ще са необходими още два хода, за да матират (ДДМ = 3).
Тази разлика е типична за много ендшпили. Обикновено ДДП е по-малък от ДДМ, но показателят ДДМ води до най-бързия мат. Изключения се случват, когато по-слабата страна има само цар и в необичайния ендшпил на два коня срещу една пешка; тогава ДДП = ДДМ, защото или няма защитен материал за взимане, или взимането на материала не носи никаква полза. Наистина, улавянето на защитаващата се пешка в последния ендшпил води до равенство, освен ако не води до незабавен мат.
Хауърт е обсъдил две други метрики по правилото за петдесет хода: Дълбочина до нулиране на ходовете (ДНХ) //. Ходът за нулиране е ход, който нулира брояча на последователните ходове, с които не е взета фигура, не е местена пешка или не е обявен мат съгласно правилото за 50 хода. Табличните бази ДНХ за 7 фигури са публично достъпни от август 2018 г. Дълбочина по правилото (ДПП) //. Табличните бази ДПП все още не са изчислени.
Етап 1: Генериране на всички възможни позиции След като е избрана метрика, първият етап е да се генерират всички позиции с даден материал – с не повече от n фигури. Например, за да генерира таблична база ДДM за ендшпила цар и дама срещу цар (ЦДЦ), компютърът трябва да опише приблизително 40 000 уникални правилни позиции. Леви и Нюборн обясняват, че числото 40 000 възниква от съображения за симетрия.
Черният цар може да бъде поставен на всяко от десетте полета: a1, b1, c1, d1, b2, c2, d2, c3, d3 и d4 (диаграма 2). Във всяка друга клетка нейната позиция може да се счита за еквивалентна чрез ротационна или огледална симетрия. По този начин няма значение дали черният цар е притиснат в ъгъла на a1, или на a8, h8 или h1. Умножава се това число 10 по 60-те легално възможни полета, за да се постави оставащия бял цар, и след това по 62-те полета за бялата дама: 10×60×62 = 37 200 позиции. Няколкостотин от тези позиции са незаконни, невъзможни или огледални копия една на друга, така че действителният брой е малко по-малък.Levy & Newborn, pp. 140-43Вижте също Stiller 1995:93-98.
За всяка позиция базата данни оценява ситуацията поотделно: ако на ход са белите и ако на ход са черните. С дама белите печелят в почти всички случаи, налагайки мат за не повече от 10 хода. Някои позиции са равни поради патова ситуация или неизбежна загуба на дама.
Всяка допълнителна фигура, добавена към ендшпил без пешки, умножава броя на уникалните позиции с коефициент около 60, което е приблизителният брой полета, които все още не са заети от други фигури.
Ендшпил с една или повече пешки увеличава трудността, тъй като аргументът за симетрия е намален. Тъй като пешките могат да се движат само напред, но не и настрани, въртенето и вертикалното отразяване на дъската води до фундаментални промени в естеството на позицията. Най-доброто изчисление на симетрия се постига чрез ограничаване на една пешка до 24 квадрата в правоъгълника a2-a7-d7-d2 (диаграма 3). Всички други фигури и пешки могат да бъдат поставени на всяко от 64-те полета, които тази пешка позволява. Така ендшпил с пешки е 24/10 = 2,4 пъти по-сложен от ендшпил без пешки със същия брой фигури.
Етап 2: Оценяване на позициите с ретрограден анализ Всички генерирани позиции се оценяват. Процесът на ретрограден анализ може да бъде описан относително просто в три стъпки: 1. Определят се всички печеливши позиции за белите. 2. Определят се всички печеливши позиции за черните. 3. Начертават се останалите позиции – реми.
Тим Крабе обяснява процеса на генериране на таблична база по следния начин: „Идеята е да се направи база данни с всички възможни позиции с даден материал (както в предходния раздел). Прави се подбаза от данни за всички позиции, където черните са мат. След това такава, при която белите могат да дадат мат. Тогава една, при която черните не могат да спрат белите да дадат мат следващия ход. После такава, при която белите винаги могат да достигнат позиция, в която черните не могат да ги спрат да дадат мат следващия ход. И така нататък, винаги един слой по-далеч от съвпадението, докато не бъдат намерени всички позиции, които по този начин са свързани в съчетание. След това всички тези позиции се свързват обратно към мат по най-краткия път през базата данни. Това означава, че с изключение на „еквиоптималните“ ходове, всички ходове в такъв път са перфектни: ходът на белите винаги води до най-бързия мат, ходът на черните винаги води до най-бавния мат.“
Ретроградният анализ е необходим само от матирани позиции, тъй като всяка позиция, която не може да бъде достигната чрез движение назад от матирана позиция, трябва да бъде реми.
Диаграма 4 илюстрира идеята за ретрограден анализ. Белите могат да наложат мат в два хода, като изиграят 1. Цc6, което води до позицията на диаграма 5. Има само два законни хода за черните от тази позиция, като и двата водят до мат: ако 1...Цb8 2. Дb7# и ако 1...Цd8 2. Дd7# (диаграма 6).
Диаграма 6, преди втория ход на белите, се определя като „мат в един слой“. Диаграма 5, след първия ход на белите, е „мат в два слоя“, независимо как играят черните. И накрая, началната позиция на диаграма 1 е „мат в три слоя“ (т.е. два хода), защото води директно към диаграма 5, която вече е дефинирана като „мат в два слоя“. Този процес, който свързва текуща позиция с друга позиция, която би могла да съществува един слой по-рано, може да продължи безкрайно дълго.
Всяка позиция се оценява като печалба или загуба в определен брой ходове. В края на ретроградния анализ позициите, които не са обозначени като печалби или загуби, задължително са равенства.
Етап 3: Проверка