7-men EGTB Bounty - Приз за создание 7-фигурного генератора

Мне кажется, это стандартный способ использования WDL информации. Другое дело, что до обнуления можно и не досчитаться, и в этом случае начинается бесцельное блуждание по выигранному эндшпилю.

Что понималось под "феней"? Если я что-то пишу непонятное, буду рад разъяснить.

Во всех существующих (и рабочих) методах построения таблиц окончаний, если окончание содержит N позиций, то в процессе построение мы осуществляем минимум на порядок больше обращений к той же самой таблице. Если таблица содержит 100 миллиардов позиций, мы сделаем 1 триллион обращений, обычно гораздо больше.

При одном обращении разница между O(1) и O(log N) - миллисекунды. При триллионе обращений - разница будет измеряться днями. Если же нам нужно для каждого обращения лезть на диск, то получаем разницу между возможным и невозможным. Нортон хорошо знает эти проблемы, но, к сожалению, молчит.

В этом случае вас могут сильно удивить мои недавние результаты в минишахматах. Плотность 8-фигурки 4х4 в метрике WDL составляет 38.6 позиций на байт. Или почти пять позиций на один бит. Для подсчёта плотности я использую только уникальные легальные позиции с ходом белых. (любые возможные симметрии учтены).

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

Ещё раз. Нет никаких таблиц соответствия. Позиции не хранятся, хранятся только значения метрики. По крайней мере, так будет до появления таблиц Магистра.

А почему дырки считаются столь большой проблемой? Самый тупой (и, соответственно, самый быстрый) индекс, когда каждую фигуру можно ставить на все 64 поля, едва ли хотябы удвоит таблицу. О чем сыр-бор, зачем компромис?
Программе одновременно нужно всего несколько таблиц (пример с семифигурками выше). Если я потрачу, скажем, 8 мегабайтов памяти для развёрнутых таблиц с дырками, вместо 4 для легальных - это трагедия? В сжатых же таблицах и лишний мусор, пусть и не на 100%, но сожмётся. Когда речь идёт об объёмах, бороться можно за порядки, на худой конец - разы. Борьбы за проценты - это "лихие семидесятые", когда стоимость часа машинного времени была сопоставима с месячной зарплатой программиста, а память измерялась килобайтами, если ещё кто помнит значение этого слова.

Тем, что не гарантируют выигрыша выигранной позиции. В 5-фигурке это может быть неактуально, так как до взятия или хода пешкой, наверное, можно досчитаться почти во всех случаях. В 6- и, тем более, в 7-фигурке, могут возникнуть проблемы. Но, опять же, неочевидно, что более информативная метрика (DTZ), компенсирует замедление, вызванное большим объёмом таких таблиц.

Да, примерно так и происходит. Приятно иметь дело с адекватным собеседником. Понимает объяснения, предлагает рабочие идеи.

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

Это, извините, диагноз.
Совершенно очевидно, что произойдет (если уже не произошёл) разрыв между теми, кто интересуется усилением движков, и теми, кого интересует чистое искусство DTM для беспешечных позиций и рекордные маты в сотни ходов.
Я за послендние лет 45 точно ни разу семифигурник без пешек не играл
Подозреваю, что некоторые движки и сейчас благополучно используют битбазы, не заморачиваясь об экзотике, в которой можно нарваться на пресловутое правило 50 ходов.

Но даже в рамках чистого искусства я сомневаюсь в продуктивности налимовских ухищрений по сжатию.
Если, скажем, для трехфигурок я построю полные таблицы DTM 64*64*64, по байту на позицию, и прогоню архиватор, то на выходе получу что-то сопоставимое с налимовским результатом. Наихудший прогноз - проигрыш вдвое (но сумлеваюсь я, если честно, что изобретальность человека, хорошого знающего предмет, побъёт вдвое универсальные алгоритмы современных архиваторов. Не удивлюсь, если результат будет обратным, и архиватор побьёт). Если учесть, что за время существования баз объём оперативки и дисков вырос во многие десятки раз, то усилия по запудриванию логики программы выглядят совсем уж небесспорными.

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

(Кстати, отдельное направление исследований посвящено определению того, как и чем лучше заполнять дырки для наилучшего сжатия. Например, можно писать туда ничьи, можно - значение из предыдущей позиции.)

Сколько получится дырок - легко проделать эксперимент. Мне неизвестно число уникальных легальных позиций в шахматах 8x8, поэтому возьму для примера доску 4х4.

3 фигуры: 10 таблиц, в сумме 3,378 уникальных легальных позиций. Тупой индекс здесь проиндексирует 10*16^3 = 40960 позиций - в 12.1 раз больше. Вот вам и разница на порядок.

4 фигуры: 55 таблиц, 227,362 уникальных легальных позиций. Тупой индекс: 55*16^4 = 3604480 позиций, в 15.9 раз больше. И так далее.

EDIT: Для 5, 6, 7 и 8-фигурки разница получается (в разах): 26.2, 53.1, 129.7, 381.2. То есть в 8-фигурке на одну уникальную легальную позицию приходится 380 дырок.

Разрыв уже успешно произошёл. DTM-базы Налимова и Нортона - очень неэффективны в реальном шахматном анализе. Будущее для практических шахмат - за WDL50, DTZ50, или какими-то вариациями на эти темы.

1. Даже грамотно заполненные дырки жмутся хуже чем отсутствие дырок.
2. Индексирование и сжатие - не противоречат, но дополняют друг друга. У Налимова - хорошее индексирование и посредственное сжатие. И то и другое можно и нужно улучшать.

Подбивая промежуточный итог, выражу текущую точку зрения.

Метрики можно обсуждать любые, а налимовскому формату пора сказать "спасибо"...
Нормальная общая процедура, для любых метрик - строить полные таблицы, 64*64*64*..., результат прогонять через архиватор, сжатый результат хранить в базе, вместе с информацией об архиваторе.
Играющая программа вытащит таблицу из базы и в памяти разархивирует.
Для беспешечных позиций и метрик с глубиной расчета 1 можно измельчить таблицы, например, позиции королей включить в определение таблицы.

1. Метрика DTC - это по сути недо-DTZ. Расстояние до мата уже потеряно, но пешечные ходы ещё не считаются промежуточными целями. Для чисто практических применений лучше сразу использовать DTZ/DTZ50. Хотя, наверное, у DTC имеется некоторая собственная эстетическая ценность.

2. Метрику DTC успешно использовал Кен Томпсон, а в последнее время Марк Буржуцкий и Яков Коновал. Почему не используются - таблицы Томпсона неэффективны, таблицы Буржуцкого и Коновала - недоступны.

3. Метрику DTC успешно использую я в мини-шахматах. В основном с целью сравнения с другими метриками.

Про таблицы Томпсона:

Источник

(Кстати, я хостю копию таблиц Томпсона, если кому-то интересно).

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

Дело не только в легальности, но и в уникальности позиций. Пример:

Это две разные позиции, или одна и та же? Для тупого индекса, понятное дело, разные. В Налимовском формате, и в моём формате - это одна и та же позиция, и хранится один раз.

Ну, уж это для очень тупого индекса
Просто не посчитал нужным употребить 32 вместо 64 для белого короля, для единообразия сказал 64.

Хорошо, идём дальше. Ещё два варианта той же позиции:

Эти варианты, опять же, не хранятся независимо в Налимовском формате.

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

Ещё более интересный вопрос: Так как индекс Налимова вычисляется за константное время (так же, как и тупой индекс), какие могут быть причины для возврата к менее компактным индексам?

Таблиц 5+1 в формате Налимова вообще нет в природе, а не только на сайте shredderchess.com.

Мой индекс остановится очень быстро. Лежащую на дороге зеркальную симметрию, я, конечно, подберу: это даёт зримый (50%) эффект. Крутить доску для беспешечников - сильно подумаю. Ни о чём другом просто и думать не буду: жизнь коротка, чтобы заниматься кустарной оптимизацией. Индекс должен прост и максимально удобен для работы, и его "задача" - ускорять время разработки (и, отчасти, работы) программы. Спроса на оптимизацию, пока не доберутся до 32-фигурок с их высокой плотностью заполнения доски и, соответственно, высокой долей нелегальных позиций, не вижу.

Коль уж у меня вырвался диагноз, то скажу ещё раз, просто для выпуклости: всё, что можно отдать профессионалам, нужно отдавать, заниматься нужно сугубо прикладной и специфической частью. Применительно к теме это означает

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

(сейчас, кажется, некоммерческие базы ещё не жмут толком, но, со временем, не исключено, возьмут на себя эту функцию. Тогда даже о сжатии думать не нужно будет - сунул табличку в базу, и забыл).

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

Рад, что хоть кому-то эта ветка оказалась полезной!

Согласен с этим пунктом, хотя подбор и настройка оптимальной обоймы архиваторов - отдельная нетривиальная задача.

Здесь согласиться не могу. СУБД даже близко не сравнится по скорости с аккуратно настроенным ручным своппингом.

Для доски 4х4 устроит?

4x4 kpk, в 4-х метриках, несжатые

EDIT: Если что-то ещё нужно выложить, пишите.

Себя к их числу не относите?

"Приятно иметь дело с адекватным собеседником"

Подумать можно о встраивании архиватора в играющую программу. Правда, если "чукча хочет быть писателем", то думать об этом не обязательно: пусть читатели думают, как эффективнее распаковаться.

А Вы не пытаетесь обмануть, как с данными о малых досках на предмет избыточности индеска?

Если у Вас цифирь под рукой есть, не поделитесь, на каких задачах какие времена получались. Из всё тех же соображений: за что боремся, стоит ли овчинка выделки.

До собственно генератора предлагается определиться с

Индексацией,
Сжатием,
Метриками

Со сжатием мы, кажется, уже договорились - это не характеристика генератора.

Собственно, можно вынести за скобки и индексацию: нужна создать библиотеку для индексов (DLL, jar для Java и т.п). Никаких оснований для того, чтобы делать генератор зависимым от способа индексации я не вижу. индексация - это параметр генератора, а не его неотъемлимая часть.
Неплохо, конечно, со старта иметь доступную реализацию простенького индекса.

Метрики. Большое искушение метрики тоже объявить параметром, но здесь не всё так просто. Метрики есть зависящие от длины пути и ... все остальные, то есть ПНП.
Генераторы для двух этих классов - разные.
В терминах конкурса - малый сникерс за ПНП, и большой - за метрики, связанные с расстоянием. Во втором случае - метрика суть параметр генератора, и спор о метриках не должен тормозить разработку самого генератора.

Ну, площадку расчистили, можно и к генератору переходить.

Вынужден отвлечься, вернусь к обсуждению через пару дней.

Ну, и собственно о генераторе.
Очевидно, будь у нас комп с бесконечными памятью и быстродействием, разницы между трехфигурками и 32-фигурками - никакой.
Почему долго семифигурок нет? Ясно, задача упирается в ресурсы.
Где? Тоже ясно: беспешечные 6-фигурки и старшие по отношению к ним эндшпили.
Казалось бы, вырежи этот сегмент и двигайся по практическим эндшпилям, но...
По вере сообщества, старший эндшпиль нельзя строить, не построив все младшие.
DTM так просто невозможно. А беспешечные семифигурки, по теории - младшие эндшпили для всех эншпилей с пешками. Вот и ждёт народ, когда придёт герой и на беспешечные семифигурки замахнётся.

Какую задачу будут решать создатели генератора? Если кто думает про шахматы и таблицы - низачот. Сообщество будет решать древнюю, как компьютерный мир, задачу: Засунуть в Память То, Что в Память Не Засовывается.
Подход к задаче - почти такой же древний, и носит название Виртуальная Память.
Нынешние Винды и Юниксы имеют какую-то ВМ, но что ныне вкладывается в эти слова - мне не ведомо. В идеальном мире это означало бы, что мы можем отдать диск под виртуальную память, отдать процессу эту виртуальную, и процесс будет строить 7-фигурки по тому же алгоритму, что строили трёхфигурки, то есть какбы всё в памяти.
А что сейчас вокруг этого реально есть - это сообщество, конечно, внимательно изучит, и я с удовольствием попаразитирую на его усилиях

Конкурс. Я надеюсь, его не объявят сразу при завершении составления требований.
Проект, как я понимаю, открытый, и самое интересное было бы не рваться со старта одиночкам, а обсудить реализацию, основные проблемы и подходы, определить дизайн (см. Что Где Когда). разбить проект на модули, определить интерфейсы между модулями. Где есть расхождение во мнениях - желательно сделать (где можно) расхождение как разные реализации одного интерфеса. И уж здесь, поделив работу и минимизировав дублирование, рвануть.

Хотелось бы, чтобы в проекте нашлись атеисты, готовые отказаться от DTM и полных таблиц и быстренько построить полсотни самых ценных для практики эндшпилей и сразу рвануть на 8-фигурки.

И последнее. Где-то в начале темы мелькало, что генератор для 6-фигурок - это сурово, а 7 - это ещё круче. Не уверен. 6-фигурки делали в 32-разрядной архитектуре, когда не только памяти, но даже и адресного пространства не хватало. А теперь послабления вышли.