База от данни за шахматни окончания

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

През 1965 г. Ричард Белман (на английски Richard Bellman) за първи път предлага използването на метода на ретроспективен анализ за създаване на база данни за решения на шахматни и шашечни ендшпили. За разлика от обикновеното пряко търсене, започващо с конкретна позиция, стояща на дъска, ендшпилните бази данни, включващи в себе си всички възможни премествания на фигурата, извършват търсене в обратна посока: започвайки с позиция, където една от страните вече е получила пат или мат, и завършвайки с конкретната позиция, стояща на дъската, позволяваща да се получи правилното решение с абсолютна точност. По този начин, шахматният компютър по време на играта повече не е необходимо да произвежда изчисления на ендшпила, а достатъчно само да види в базата данни предварително изчислен резултат и да направите идеален ход.

През 1970 г. Томас Щрьоляйн (на немски Thomas Ströhlein) защитава докторска дисертация, в която се анализират такива окончания, като ЦДЦ, ЦТЦ, ЦпЦ, ЦДЦТ, ЦТЦО и ЦТЦК. ^[2]

През 1977 г. Кен Томпсън на конференция на Международната федерация за обработка на информация в Торонто представя съставена от него таблица за всички възможни позиции в ендшпила „Цар и топ срещу цар и дама“ (ЦТЦД). Общият брой на позициите за него е около 4 милиона. Кен Томпсън провежда няколко показателни изяви — компютърна игра за играча, владеещ топа. Този ендшпил е теоретически изгубен и шахматист на ниво майстор, владеещ дамата, обикновено лесно го спечелва срещу всеки противник. Следователно на компютъра е поставена задача максимално да отдалечи своята теоретически неизбежна загуба. Резултатите от експериментите, в които компютърът е играл с шахматисти, са доста интересни. Против програмата се опитали да играят световният екс-шампион по кореспондентен шах Ханс Берлинър и шампионът на Канада Лоуренс Дей. Никой от двамата не успял да победи програмата, въпреки че произволно такава позиция се счита за спечелена. Същността е в това, че теоретически безупречната игра на компютъра често изглежда нелогично, противоречи на принципите, предписани от шахматната теория (например, обикновено се препоръчва да не се отдалечава топа от царя за избягване на възможни вилки, но програмата нерядко е направила това), необичайните ходове на компютъра обърквали шахматиста и той пропускал да спечели, не успявал за 50 хода да постави мат или да вземе топа.

През 70-те и 80-те години на ХХ век идеята за предварително изчислените окончания се развива много бавно, тъй като скоростта и паметта на компютрите от онова време са значително ограничение и не позволяват подробни бази данни. Въпреки това, Кен Томпсън и други ентусиасти продължават бавно да генерират ендшпили с малко фигури и след известно време са преброени всички окончания с 4 фигури, а до края на 80-те години – всички окончания с 5 фигури, включително такива интересни позиции като ЦООЦК (два офицера срещу кон), ЦДпЦД (дама и пешка срещу дама) и ЦТпЦТ (топ и пешка срещу топ). През 1995 г. Луис Стилър публикува работа, посветена на изследването на някои 6-фигурни окончания.

Каспаров срещу Света, 1999

	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

Позицията след 55.Д:b4; таблиците показват, че белите печелят в 82 хода.

Ейко Блайхер е адаптирал концепцията за таблична база към програма, наречена „Freezer“. Гай Хауърт, академик в Редингски университет, е публикувал много в ICGA Journal и другаде. Марк Бурзучки и Яков Коновал са си сътрудничили за анализиране на ендшпили със седем фигури на дъската. Петер Карер конструира специализирана база данни за ендшпила със седем фигури (ЦДп,ЦДпп) от кореспондентския мач Гари Каспаров срещу Света през 1999 г. След това в партията е използвана таблица за анализ на ендшпила с шест фигури (ЦДп,ЦДп), показан на диаграмата вдясно. ^[3]

Метрики и показатели

Преди да създаде база данни, програмистът трябва да избере метрика на оптималност – с други думи, трябва да определи в кой момент играчът е „спечелил“ играта. Всяка позиция може да бъде определена чрез нейната дълбочина или разстояние (т.е. броя на ходовете) от желаната крайна точка. Обикновено се използват два показателя:

• Дълбочина до мат (ДДМ) /на английски: Depth to mate (DTM)/. Матът е единственият сигурен показател за спечелване на играта.
• Дълбочина до преобразуване (ДДП) /на английски: Depth to conversion (DTC)/. По-силната страна може също да спечели чрез взeмане на материал, като по този начин позицията се преобразува в по-прост ендшпил с доказан изход. Например в позиция ЦДЦТ преобразуването става, когато белите вземат черния топ.

Диаграма 1

	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

Пример: ДДМ и ДДП.

Разликата между ДДМ и ДДП може да се разбере, като се анализира диаграма 1. Начинът, по който белите трябва да продължат, зависи от това кой показател се използва:

Според показателя ДДМ белите матират в два хода, така че ДДМ = ДДП = 2. За разлика от това, по показателя ДДП белите първо трябва да вземат топа, защото това веднага води до позиция, която със сигурност ще спечели (ДДП = 1), но всъщност ще са необходими още два хода, за да матират (ДДМ = 3).

Тази разлика е типична за много ендшпили. Обикновено ДДП е по-малък от ДДМ, но показателят ДДМ води до най-бързия мат. Изключения се случват, когато по-слабата страна има само цар и в необичайния ендшпил на два коня срещу една пешка; тогава ДДП = ДДМ, защото или няма защитен материал за взимане, или взимането на материала не носи никаква полза. Наистина, улавянето на защитаващата се пешка в последния ендшпил води до равенство, освен ако не води до незабавен мат.

Хауърт е обсъдил две други метрики по правилото за петдесет хода:

• Дълбочина до нулиране на ходовете (ДНХ) /на английски: depth to zeroing-move (DTZ)/. Ходът за нулиране е ход, който нулира брояча на последователните ходове, с които не е взета фигура, не е местена пешка или не е обявен мат съгласно правилото за 50 хода. ^[4] Табличните бази ДНХ за 7 фигури са публично достъпни от август 2018 г. ^[5]
• Дълбочина по правилото (ДПП) /на английски: depth by the rule (DTR)/. Табличните бази ДПП все още не са изчислени.

Етап 1: Генериране на всички възможни позиции

След като е избрана метрика, първият етап е да се генерират всички позиции с даден материал – с не повече от n фигури. Например, за да генерира таблична база ДДM за ендшпила цар и дама срещу цар (ЦДЦ), компютърът трябва да опише приблизително 40 000 уникални правилни позиции. Леви и Нюборн обясняват, че числото 40 000 възниква от съображения за симетрия.

Диаграма 2
Давид Леви – „Как компютрите играят шах“

	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

Десет уникални полета (със симетрия)

Черният цар може да бъде поставен на всяко от десетте полета: a1, b1, c1, d1, b2, c2, d2, c3, d3 и d4 (диаграма 2). Във всяка друга клетка нейната позиция може да се счита за еквивалентна чрез ротационна или огледална симетрия. По този начин няма значение дали черният цар е притиснат в ъгъла на a1, или на a8, h8 или h1. Умножава се това число 10 по 60-те легално възможни полета, за да се постави оставащия бял цар, и след това по 62-те полета за бялата дама: 10×60×62 = 37 200 позиции. Няколкостотин от тези позиции са незаконни, невъзможни или огледални копия една на друга, така че действителният брой е малко по-малък.^[6][7]

За всяка позиция базата данни оценява ситуацията поотделно: ако на ход са белите и ако на ход са черните. С дама белите печелят в почти всички случаи, налагайки мат за не повече от 10 хода. Някои позиции са равни поради патова ситуация или неизбежна загуба на дама.

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

Диаграма 3

	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

24 уникални пешечни полета (със симетрия)

Ендшпил с една или повече пешки увеличава трудността, тъй като аргументът за симетрия е намален. Тъй като пешките могат да се движат само напред, но не и настрани, въртенето и вертикалното отразяване на дъската води до фундаментални промени в естеството на позицията. ^[8] Най-доброто изчисление на симетрия се постига чрез ограничаване на една пешка до 24 квадрата в правоъгълника a2-a7-d7-d2 (диаграма 3). Всички други фигури и пешки могат да бъдат поставени на всяко от 64-те полета, които тази пешка позволява. Така ендшпил с пешки е 24/10 = 2,4 пъти по-сложен от ендшпил без пешки със същия брой фигури.

Етап 2: Оценяване на позициите с ретрограден анализ

Всички генерирани позиции се оценяват. Процесът на ретрограден анализ може да бъде описан относително просто в три стъпки:
1. Определят се всички печеливши позиции за белите.
2. Определят се всички печеливши позиции за черните.
3. Начертават се останалите позиции – реми.

Тим Крабе обяснява процеса на генериране на таблична база по следния начин:

„Идеята е да се направи база данни с всички възможни позиции с даден материал (както в предходния раздел). Прави се подбаза от данни за всички позиции, където черните са мат. След това такава, при която белите могат да дадат мат. Тогава една, при която черните не могат да спрат белите да дадат мат следващия ход. После такава, при която белите винаги могат да достигнат позиция, в която черните не могат да ги спрат да дадат мат следващия ход. И така нататък, винаги един слой по-далеч от съвпадението, докато не бъдат намерени всички позиции, които по този начин са свързани в съчетание. След това всички тези позиции се свързват обратно към мат по най-краткия път през базата данни. Това означава, че с изключение на „еквиоптималните“ ходове, всички ходове в такъв път са перфектни: ходът на белите винаги води до най-бързия мат, ходът на черните винаги води до най-бавния мат.“ ^[9]

Ретроградният анализ е необходим само от матирани позиции, тъй като всяка позиция, която не може да бъде достигната чрез движение назад от матирана позиция, трябва да бъде реми. ^[10]

Диаграма 4 илюстрира идеята за ретрограден анализ. Белите могат да наложат мат в два хода, като изиграят 1. Цc6, което води до позицията на диаграма 5. Има само два законни хода за черните от тази позиция, като и двата водят до мат: ако 1...Цb8 2. Дb7# и ако 1...Цd8 2. Дd7# (диаграма 6).

Диаграма 4 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 Белите на ход: мат в 3 слоя (Цc6)

Диаграма 5 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 Черните на ход: мат в 2 слоя (Цd8 или Цb8)

Диаграма 6 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 Белите на ход: мат в 1 слой (Дd7)

Диаграма 6, преди втория ход на белите, се определя като „мат в един слой“. Диаграма 5, след първия ход на белите, е „мат в два слоя“, независимо как играят черните. И накрая, началната позиция на диаграма 1 е „мат в три слоя“ (т.е. два хода), защото води директно към диаграма 5, която вече е дефинирана като „мат в два слоя“. Този процес, който свързва текуща позиция с друга позиция, която би могла да съществува един слой по-рано, може да продължи безкрайно дълго.

Всяка позиция се оценява като печалба или загуба в определен брой ходове. В края на ретроградния анализ позициите, които не са обозначени като печалби или загуби, задължително са равенства.

Етап 3: Проверка

След като табличната база е генерирана и всяка позиция е оценена, резултатът трябва да бъде проверен независимо. Целта е да се провери самосъгласуваността на резултатите от табличната база. ^[11]

Например, на фигура 1 по-горе, програмата за проверка вижда оценката „мат в 3 слоя (Цc6)“. След това разглежда позицията на фигура 2, след Цc6, и вижда оценката „мат в два слоя“. Тези две оценки са в съответствие една с друга. Ако оценката на фигура 2 беше нещо друго, тя би била несъвместима с фигура 1, така че табличната база ще трябва да бъде коригирана.

Взимане, произвеждане на пешка и специални движения

База данни за четири фигури трябва да разчита на база данни за три фигури, което може да се получи, ако една фигура бъде взета. По същия начин, база таблици, съдържаща пешка, трябва да може да разчита на други бази таблици, които се занимават с новия набор от материали след произвеждане на пешката в царица или друга фигура. Програмата за ретрограден анализ трябва да отчете възможността за вземане или произвеждане на пешка при предишния ход. ^[12]

Табличните бази предполагат, че рокадата не е възможна по две причини. Първо, в практическите ендшпили това предположение е почти винаги правилно. (Въпреки това, рокадата е разрешена по конвенция в съставени задачи и изследвания.) Второ, ако царят и топът са на първоначалните си полета, рокадата може или не може да бъде разрешена. Поради тази двусмисленост би било необходимо да се направят отделни оценки за състояния, в които рокадата е или не е възможна.

Същата двусмисленост съществува и при вземане на преминаване през бито поле (ан пасан), тъй като възможността за преминаване зависи от предишния ход на опонента. Въпреки това практическите приложения на анпасан се срещат често в ендшпила с пешки, така че таблиците отчитат възможността за анпасан за позиции, при които и двете страни имат поне една пешка.

Използване на априорна информация

Съгласно метода, описан по-горе, базата на таблицата трябва да позволява възможността дадена фигура да заема някое от 64-те квадрата. В някои позиции е възможно да се ограничи пространството за търсене, без това да повлияе на резултата. Това спестява изчислителни ресурси и позволява търсения, които иначе биха били невъзможни.

Диаграма 7

	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

Пример за ендшпил ЦТп(a2)ЦОп(a3). Белите матират в 72 хода, започвайки с 1.Цh7! Други ходове на белите водят до равенство.

Ранен анализ от този тип е публикуван през 1987 г. в ендшпила ЦТп(a2)ЦОп(a3), където черният офицер се движи върху тъмните полета (примерната позиция на диаграма 7). ^[13] В тази позиция могат да се направят следните априорни допускания:

1. Ако фигура бъде взета, можем да се потърси получената позиция в съответната таблична база с пет фигури. Например, ако черната пешка бъде взета, новосъздадената позиция се търси в ЦТпЦО.
2. Бялата пешка остава на a2; движенията за вземане се обработват от 1-вото правило.
3. Черната пешка остава на a3; ходовете за вземане се обработват от 1-вото правило. ^[14]

Резултатът от това опростяване е, че вместо да се търсят 48 х 47 = 2256 пермутации за местоположението на пешките, има само една пермутация. Намаляването на пространството за търсене с коефициент 2256 улеснява много по-бързото изчисление.

Блайхер е проектирал комерсиална програма, наречена "Freezer", която позволява на потребителите да създават нови бази от таблици от съществуващи бази от таблици на Налимов с априорна информация. Програмата може да създаде база от таблици за позиции със седем или повече фигури с блокирани пешки, дори преди да станат достъпни бази от таблици за седем фигури. ^[15]

В компютърния шах един от най-популярните формати на бази данни за шахматни окончания са ендшпилните таблици на Налимов. Тази база данни (състояща се от много отделни таблични файлове) е кръстена на новосибирския програмист Евгений Налимов, който е предложил ефективен алгоритъм за генериране на бази данни за ендшпил. През 1998 г. Налимов създава генератор на шахматни окончания, който се оказва изключително ефективен. Благодарение на новия генератор и увеличаването на производителността на компютъра, до началото на 2000-те години всички завършеци от 6 фигури са изчислени, което прави истинска революция в разбирането на някои ендшпили. Скоро 6-фигурните окончания стават публично достъпни в Интернет и остават такива и до днес.

Таблиците на Налимов съдържат абсолютно точни варианти за развитие на шахматна игра в ендшпила. С помощта на тези таблици се определят всички възможни варианти за продължаване на играта, всички възможни резултати и броя на ходовете, чрез които при оптимална игра ще се стигне до мат на по-слабата страна. Таблиците на Налимов имат метрика ДДМ – дълбочина до мат (на английски: Depth to mate – DTM) – в спечелените позиции се указва броя на ходовете до мат. Базите от данни на Налимов изискват място за съхранение повече от един терабайт. ^[16][17]

Владимир Махничев и Виктор Захаров, служители на компютърно-изчислителния комплекс на Московския държавен университет „Михаил В. Ломоносов“, през пролетта и лятото на 2012 г. изчисляват 7-фигурни таблици до мат (ДДМ). През юли 2012 г. те завършват базите от данни за 4+3 фигури: 525 окончания, включително Цппп+Цпп. През август 2012 г. завършват таблиците за 5+2 фигури: 350 окончания, включително Цпппп+Цп. Високата скорост на генериране на табличните бази се дължи на използването на суперкомпютри на име Ломоносов и IBM Blue Gene/P, инсталирани в университета. Базите от данни се наричат таблици на Ломоносов. Таблиците за 7 фигури са активно използвани за първи път в анализа на партиите на Световното първенство по шах през 2012 г. ^[18][19] Размерът на всички таблични бази за седем фигури е около 140 TB. ^[20]

По-късно Сизиги успява да намали размера на базите данни за седем фигури до 18,4 TB с друг формат, наречен формат на Сизиги. ^[5] Базите таблици на Сизиги са разработени от Роналд де Ман и пуснати през април 2013 г. във форма, оптимизирана за използване от програма за шах по време на търсене. Тази разновидност се състои от две таблици за ендшпил: по-малка таблица „победа-равенство-загуба“ (ПРЗ) /win-draw-loss (WDL)/ – , която съдържа знания за петдесетходовото правило, и по-голяма таблица с метрика ДНХ. Таблиците ПРЗ са проектирани да бъдат достатъчно малки, за да се поберат на полупроводниково (статично) дисково устройство (диск SSD) за бърз достъп по време на търсене. Таблиците ДНХ са за използване в основната позиция, за да се избере теоретичното решение с най-малък брой ходове за нулиране на брояча на ходове по петдесет ходовото правило и запазване на печеливша позиция, вместо да се извършва търсене. Таблиците на Сизиги са достъпни за всички окончания с 6 фигури и сега се поддържат от много известни шахматни компютърни програми, включително Komodo, Deep Fritz, Houdini и Stockfish. ^[21] От август 2018 г. се предлагат и всички таблици на Сизиги за 7 фигури. ^[5]

През 2018 г. Боцзюн Го генерира 7-фигурни ендшпили във формат Сизиги, към тях е отворен бесплатен достъп онлайн. ^[22][23] Базите таблици на всички окончания с до седем фигури са достъпни за безплатно изтегляне и могат също да бъдат търсени чрез уеб интерфейси (вижте външните връзки по-долу).

Времето за изчисление и размерът на базите данни за шахматните окончания се увеличават експоненциално с броя на участващите фигури. Размерът на базата данни зависи както от броя на фигурите, така и от формàта на самата база данни. Текущото състояние на базите данни във формати на Налимов/Ломоносов и Сизиги е обобщено в следната таблица: ^[1]

В момента има бази данни за всички окончания с три, четири, пет, шест и седем фигури (включително двата царя). През 2021 г. Марк Бурзучки (на английски: Marc Bourzutschky) изчислява ендшпили с 8 фигури: позиции без пешки ^[25] и позиции с две блокиращи се една друга пешки – бели и черни. ^[26]

• Levy, David, Newborn, Monty. How Computers Play Chess. Computer Science Press, 1991. ISBN 0-7167-8121-2.
• Nunn, John. Secrets of Pawnless Endings. second. Gambit Publications, 2002. ISBN 1-901983-65-X.
• Stiller, Lewis Benjamin. Exploiting symmetry on parallel architectures // PhD Thesis, Johns Hopkins University, 1995. Архивиран от оригинала на 2007-09-30. Посетен на 2023-10-14.

• Aaron Tay – A guide to Endgames Tablebase (Aaрoн Taй – Ръководство за използване на таблични бази за ендшпил в компютърния шах)
• Изтегляне на таблични бази
  • Торент за завършени таблични бази на Налимов (3+4+5+6) фигури
  • Endgame Tablebases Online – 6-men endgame analysis free for everyone (Таблични бази онлайн – анализ на 6-фигурен ендшпил, свободно достъпен за всеки)
  • Robert Hyatt – 3-4-5 pieces (Робърт Хаят – 3-4-5 фигури /FTP сайт/)
• Извършване на заявки за бази от таблици в мрежата
  • Eiko Bleicher – Web Query for Nalimov Endgame TablebasesWeb query server for Nalimov tablebases (Ейко Блайхер – Сървър за уеб заявки за таблични бази на Налимов /до 6 фигури/)
  • Web query server for Nalimov tablebases at ChessOK (Сървър за уеб заявки за таблични бази на Налимов в ChessOK /до 6 фигури/)
  • Web query server for Nalimov tablebases by Lokasoft (Сървър за уеб заявки за таблични бази на Налимов в Lokasoft /до 6 фигури/)
  • Web query server for Nalimov tablebases at Shredder (Сървър за уеб заявки за таблични бази на Налимов в Shredder /до 6 фигури/)
  • Niklas Fiekas – Web query server for Syzygy tablebases (Никлас Фиекас – Сървър за уеб заявки за таблични бази на Сизиги /до 7 фигури/)
• Kirill Kryukov – Maximal positions (Кирил Крюков – Максимални позиции, т.е. най-дългите ДДM позиции за ендшпили с до пет фигури и някои с шест фигури)