"Практические эндшпильные таблицы" (базарим об идеях)

Эта тема навеяна обсуждением проекта создания генератора 7-фигурных эндшпильных таблиц.


Идея неполных (и неточных) эндшпильных таблиц для практиков.


Львиная доля усилий при генерации полных эндшпильных таблиц приходится на получение беспешечных и малопешечных окончаний, не имеющих смысла для практиков. Алгоритм ретроанаиза, положенный в основу построения эндшпильных таблиц, приводит к тому, что полезные окончания могут быть построены только после трудоёмкой работы по созданию беспешечных и малопешечных окончаний.

Полезные практикам окончания оказываются фактически заблокированы малопешечной экзотикой. Не удивительно, что семифигурные таблицы, годы спустя после построения шестифигурных, так и не были построены (частные успехи пионеров этого дела мы выносим за скобки).

Эта тема предлагается для обсуждения способов обхода суровых реалий "честного" ретроанализа. Программисты, шахматисты и все, кому интересно - добро пожаловать.

Стартовое предложение по семифигуркам.

Полностью отказываемся от таблиц менее чем с двумя пешками, выкидываем попутно всё двухпешечники с фигурами на одной стороне. (Можно и ещё немного почистить, но и так уже осталось процентов 5 от всех таблиц).

Идея ретроанализа по-прежнему лежит в основе, таблицы строятся от малых к большим, т.е. приступая к 7-фигуркам, мы имеем необходимые 6-фигурки. Попытка сэкономить основана на отказе от построения "младших" таблиц, содержащих позиции после превращения пешек в интересующих нам эндшпилях.

Как компенсировать для ретроанализа нехватку младших таблиц, получаемых в результате превращений?
Для требуемой таблицы с пешкой, скажем, на c7, смотрим (не просчитанные таблично) соответствующие позиции с ферзём на с8, и движком на небольшой глубине оцениваем их. В большинстве случаев будет выигрыш. Если ясного выигрыша не видно, проверить превращение в коня.
Возможные исходы:
1. пат или форсированное уменьшение матриала - у нас есть точная оценка
2. материальное соотношение после превращения форсированно не меняется - позиции присваивается оценка "практический выигрыш" (которую можно округлить до "выигрыш")
3. Другая сторона форсированно проводит ферзя - позиции даётся оценка "неясно"

Дальше по обычным процедурам ретроанализа.

Если здесь не кроется невидимый мне изъян в рассуждениях, то такие таблицы можно построить очень быстро, на весьма скромных компьютерах, и сразу продолжить путь к 8-фигуркам.

====

Отмечу мудрое наблюдение Вождя о том, что пешки сквозь друг друга не ходят, в симметричных пешечных структурах

т.е. перейти в младшие, уже посчитанные таблицы.

===

Конструктивная критика и свежие идеи приветствуются!

 

Спасибо за ссылку.

Мне тоже

 

Предлагаю какой-нибудь конкретный пример рассмотреть. Просто я не верю в возможность что-то родить, не вникая в специфику - условно говоря, не интересуясь, в шахматы мы играем или в шашки. Нужна шахматная конкретика какая-то.

Например, можно взять позиции типа "ладья и пешки g,h против слона и пешек g,h; пешки не прошли друг сквозь друга".



Формально это восьмифигурные позиции, но я их предлагаю рассматривать как четырёхфигурные (~64^4 расположений) плюс структура. Структура даёт сравнительно небольшой множитель. Если без взятий, то у пешек, хоть их и целых 4 штуки, а всего-навсего 15^2 = 225 расположений. Если пешка съела фигуру, то сразу понижается фигурность,трёхфигурные совсем уж легко перебрать. Если пешка съела пешку, то останется три пешки, у каждой не более 6 полей, т.е. 6^3 = 216 позиций. Ну, учтём ещё, что взятие может случиться на вертикали g и на вертикали h, белыми или чёрными - умножим ещё на 4. Всё равно скромное число. В общем, легко всё это перебирается.

Главная сложность - что пешки, которые так легко перебирать, могут превращаться в фигуры. Допустим, произошло такое взятие:



Теоретически дальше все пешки могут пройти, превратиться в кого угодно. Возникнут семифигурники, которые мы перебирать не умеем/не хотим. Чтобы этого не допустить, предлагаю немножко пихнуть шахматные правила вбок, навесив запрет на избыточное превращение пешек. Например, так:

Если на доске уже есть 6 фигур (считая королей и не считая пешки), то проводить пешку запрещено

Или:

Если игрок, у которого есть три фигуры (считая короля), провёл четвёртую, то он сразу выиграл

или:

При проведении 7-й фигуры включаем присуждающий алгоритм

Эти меры ограничивают число фигур, семифигурники исключаются. Максимум, что надо перебрать - это шестифигурные позиции, на которых впридачу есть одна белая пешка "h", которой можно ходить, но нельзя превращаться. Множитель она даст небольшой, всего 6. Вполне реально перебрать.

Если нам лень перебирать даже это, можно ещё более усилить запреты. Например, разрешить максимальное число фигур 5, пока никого не съели - пешки не проводим. Тогда смотреть придётся только пятифигурники с двумя малоподвижными пешками, которым до разменов нельзя превращаться.

Конечно, строгость малость нарушается. Но я думаю, что разумно выбранные дополнительные правила могут облегчить жизнь - и при этом не затронуть исход борьбы. Отсекаемые ими позиции больно уж дики. Ясно же, что при нормальной игре в положении, с которой я начал пост, не должно возникнуть три ферзя.

Во всяком случае, такие запреты было бы интересно проверить. Игру в "ограниченные шахматы" по принципу минимаксов - сравнить с игрой в стандартные шахматы из здравого смысла.

 

Естественная и здоровая идея - оттолкнуться от реальных, статистически значимых пешечных структур. (Ретроанализ можно пока за скобками оставить). Есть подозрение,что их не так и много. Вообще, безотносительно семифигурок.
Можно собрать статистику по реальным 4-5 фигурным эндшпилям, безотносительно числа пешек.
Интересно, поддаётся ли автоматизации сбор такой статистики?

 

Очень похоже, что придется для каждого отдельного типа позиции писать свои правила..
С учетом того, что типов практических эндшпилей не так много, это можно осуществить

 

Может быть, правила даже более-менее унифицируемы. Просто не разрешаем всем пешкам сразу превращаться в фигуры. Ограничиваем максимально допустимое количество фигур за одну сторону, скажем, тремя.

 

Три фигуры (включая короля) - это для меня стартовая точка, определяющая набор интересующих позиций: пять фигур, 3+2, без ограничения пешек.
Или Вы говорите о трёх, не считая короля, запасаясь на одну превращённую фигуру?

 

Я в основном думаю о позициях, когда у каждого король, фигура и несколько пешек. Элементарные эндшпили или как там их Дворецкий называет. В таких позициях, с учётом превращений, вряд ли выйдет ограничиться 3+2 + пешки.



Вполне себе реалистичная позиция, запросто в партии может возникнуть.

1. g7 f2 2. g8=Q f1=Q - попробуйте, усильте.

В итоге 6 фигур возникло, 3+3, никуда не деться. Вот если чёрные как-то второго ферзя проведут, то это уж редчайшая экзотика, по-моему. И это можно присуждать практически без ущерба для точности оценки. А перебирать и оценивать с помощью минимаксов только 6-фигурные позиции с дополнительной пешкой на линии "e".

 

Я как раз об этих позициях (после появления первого ферзя) говорил как о позициях с оценкой "неясно", и это полностью, как я понимаю, совпадает с подходом, описанным в статье, предложенной Kirr'om.
Единственно я осознал, что добавление оценки не означает механическое расширение шкалы без дополнительнвх затрат на вычисление. Если WDL в рамках ретроанализа позволяет двигаться только от результативных позиций, то с расширенной шкалой такое движение просто потеряет дополнительную оценку: ничейные и неясные позиции сольются. Для поддержания метрики нужны дополнительные вычисления (ретроанализ от позиций с оценкой "неясно")

 

Хорошая идея. Но проще всего - переделать генератор, чтобы он превращал пешку только в ферзя. Процентное количество ошибочно оцененных позиций будет очень мало. Часто вы превращаете пешку не в ферзя? А количество требуемых младших эндшпильных баз сокращается в 10 и более раз (для многопешечных)

 

Выглядит достаточно практично. Превращение в коня с шахом встречается, однако. Когда используется оценка "неясно", то мы знаем, что мы знаем точно, а что - нет. В "ферзевых" таблицах все оценки под вопросом, но доля ошибок представляется терпимой для практических целей.

 

Добрый день. Запал я на 7-ми фигурные окончания. Разбираюсь потихоньку. Жаль времени не хватает

Наступает 2012 год, винты толстеют. Если бы не наводнение то и подешевели бы. В любом случае в
2012 году комп с 10-20тБ дискового пространства будет вполне обычным. Этого вполне достаточно для
примерно 200 видов 7-ми фигурных баз в метрике WDL. Поэтому я решил сделать небольшой генератор
в метрике WDL, для оценки насколько он может быть эфективен.
Хочу последовать примеру Kirr а, только не уменьшать количество полей при всех фигурах, а наоборот при полной доске обсчитать только Ферзей и Королей. Задача упростится и можно сосредоточится на
скорости вычислений и сжатии баз.
Как раз новый год, 2 недели без работы, если много не пить, надеюсь получить какие-то реальные
результаты. Жаль денег не наскреб на обновление компа до нового года,.но в планах стоит.
Хочу разбудить тему. Буду рад любому совету как ускорить вычисления.
.

 

Можно посчитать моим генератором и потом конвертировать в WDL, если вам так нужны WDL. Я уже на своем компьютере посчитал 296 6-фигурных, и считаю 7-фигурные. Если у вас есть компьютерные мощности, то можем обменяться посчитанными базами? Чем больше народа задействовать, тем лучше.

 

На мой взгляд, исключение слабых превращений было бы оптимальным решением с точки зрения соотношения практической ценности и вычислительных затрат.

Идею ввести оценку "неизвестно" для таких позиций я считаю удачной. Не вижу причин, почему нельзя пользоваться таблицами, в которых 99 процентов позиций имеют точные оценки, а остальные - оценку "неизвестно".

 

Если у нас цель - посчитать ВСЕ 7-фигурные (1001 тип), то толку от этого никакого - только базы станут не совсем точными.
Если же у нас цель - посчитать не все 7-фигурные, а например, какие то "полезные", типа
7_KRPP-KRP (ладья и 2 пешки против ладьи и 1 пешки), и на этом остановиться, тогда исключение слабых превращений уменьшит на порядок количество младших требуемых баз. Значит, и 7_KRPP-KRP можно будет посчитать БЫСТРЕЕ.

Но при этом база будет не совсем точной. Играть, получается, будем по одним правилам, где пешка может превратиться в любую фигуру, а по базе будет значение, как если она превращается только в ферзя.