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

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

 

Налимовский формат и использует индекс с дырками. Количество нелегальных позиций обычно ~ 5%-25% Плотность записи 2-5 позиций на байт. Все это можно посмотреть в *.tbs файлах.

 

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

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

 

Хм, может тогда попробовать совместить битбазы и DTM? К примеру, 1 - "выкинутая позиция" , 0 - "ничья", или уже стандартный DTM.

 

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

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

 

Кстати, а что о метрике DTC/DTC50? Я посмотрел на статистику, она требует мало памяти для генерации. Почему не используется сейчас?

 

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

 

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

 

Кстати, если посмотреть в таблицы KPK Ипполита (а там тупой размер [64][64][6][8] бит, 1 - выигрыш, 0 - ничья), то в них очень много длинных цепочек, состоящих из одних единиц или одних нулей. Архиваторы это дело любят и жмут хорошо.

 

А вот на сайте shredderchess.com в Таблицах Налимова часто бывает вместо решения какой-нить 6-фигурной позиции пишет NOT FOUND. Это глюк сайта или баг Таблиц?)

 

Там нет таблиц 5+1.

 

На этом сайте 6-фигурки все, как они сами пишут

 

А это то же самое, что и шестифигурки? Почему же тогда там большинство 6-фигурок есть? И что тогда на этом сайте?

 

если правило 50-ти ходов все-таки будет отменено, то получается, что эти таблицы только в мусор выкинуть.
потуги в отмене правила уже есть, осталось подождать, когда побольше народа созреет.
(имеется ввиду отмена в эдванс-шахматах)

 

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

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

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

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

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

 

Kirr, а можете выложить пару-тройку несжатых файлов, например, тот же KPK?
В разных метриках, я думаю, у Вас есть

 

Если я правильно понимаю, то конечно да

 

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

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

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

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

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

 

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

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

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

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

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

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

 

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

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

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

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

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