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

Хороший пример.
Допустим появилась у меня идея, сделать квадратные колеса - нужно сразу делать демонстрацию? Тратить на это время, силы, материалы и т.п.
Или нужно сначала оценить плюсы и минусы подобной модернизации и понять, за счет чего я достигну выигрыша?

Известно, что при движении автомобиля по прямой желательно, чтобы его прижимная сила к поверхности дороги (трассы) была минимальной, а в повороте - максимальной, чтобы не "срывало" колеса. Тогда можно проходить поворот на большей скорости.
Вот как раз для этой цели лучше всего подходит переменный угол крыла, а не квадратные шины.
Отлично, идея появилась. Пора изготавливать опытный образец?
Нет, еще рано. Нужно оценить, а к каким отрицательным воздействиям это приведет?
Поскольку центробежную силу в поворотах никто не отменял, понятно, что прохождение поворотов на большой скорости приведет к усиленному износу резины, вплоть до отрывания кусочков шин.
Так что? Отказаться от этой идеи?
Нет. Нужно ПОСЧИТАТЬ и ОЦЕНИТЬ, насколько выигрыш на круге будет сопоставим с необходимостью чаще менять шины.
Второй вариант - использовать более жесткую резину. Тут опять же возникает противоречие. У более жесткой резины меньше пятно контакта с трассой и как следствие - чуть больше проскальзывание.

И что делать?
Опять же нужно сначала ПОСЧИТАТЬ плюсы и минусы, сделать выводы и если есть возможность теоретического выигрыша ХОТЯ БЫ ПРИ КАКИХ-ТО УСЛОВИЯХ, делать опытный образец, вкладывая в него существенные средства.

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

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

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

Уж не знаю, хорошо это или плохо, но уже давно не отношусь к категории людей, у которых основной лозунг: " А чего думать - трясти надо".

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

Вам не предлагают срочно заняться разработкой, а предлагают оценить эффект на простом случае, например шахмат 3х3 или трехфигурок в шахматах 8х8. Тут не надо годами думать, можно применить идею и быстро посмотреть на результат. Вы думаете, никому не приходило в голову "выбросить" все позиции с оценкой +10? Вопрос как это сделать, тут главное реализация, а не идея.

Угу.
Давайте конкретно.
Предположим, что у нас есть ТОЛЬКО рассчитанные трехходовки, которые можно скачать на любом сайте.

Берем ВСЕ окончания "Король и Конь против Короля", "Король и Слон против короля" и просто удаляем эти файлы.
Как отсутствие этих таблиц повлияет на результат ЛЮБОГО окончания?
Приведите хоть один один пример того, когда наличие или отсутствие этих таблиц повлияет на результат или расчет, оценку позиции.

Далее чуть-чуть сложнее.
"Король и Ферзь против Короля".
Выбрали все позиции, где получается ничья.
Из легальных - это всего два типа. Либо пат, либо на ПЕРВОМ-же ходу бьется ферзь.
Оставили эти позиции в таблице.
ВСЕ ОСТАЛЬНЫЕ УДАЛИЛИ.
Вместо них создали ОДНУ служебную запись - любая другая позиция, кроме тех, что оставили - это мат в 5 ходов.

Как это повлияет на РЕЗУЛЬТАТ, на КАЧЕСТВО АНАЛИЗА и на СКОРОСТЬ?
Да никак. Все будет то же самое.

"Король и Ладья против Короля".
Все аналогично предыдущему.

И наконец "Король и пешка против Короля".
Также оставляем все ничейные позиции.
Оставляем все позиции, где выигрыш достигается более чем за 15 ходов. И то только на тот случай, если у нас слабенький комп и мы сомневаемся, что он упустит выигрыш в такой позиции. Во что я не верю. Но это для скептиков.
Для всех остальных выигрышных позиций создаем одну СЛУЖЕБНУЮ запись - мат в 10 ходов.

Можно не создавать, можно по отсутствию такой записи на запрос движка давать соответствующий одинаковый ответ.

Итак, что имеем в итоге.
У нас остались сильно урезанные (процентов на 95) окончания "К+Ф против К" и "К+Л против К" и серьезно уменьшенный (в 2 раза или даже более) файл "К+п против К".
На ЛЮБОЙ запрос движка эти СОКРАЩЕННЫЕ таблицы дадут правильный ответ ЗА ТО ЖЕ САМОЕ ВРЕМЯ , любой выигранный эндшпиль движок доведет до победы, любой ничейный - соответственно завершит вничью.

Теперь попрошу всех скептиков привести ХОТЬ ОДИН пример, когда это не будет работать.

Реальное сокращение размера я бы оценил примерно в 4 раза. Причем, если для окончания "К+п против К" границу провести на уровне 20 ходов до мата, то сократятся раз в 6-8.

Если тут вопросов нет - перейдем дальше к четырехфигуркам.....

Безусловно Вы очень большой специалист в области табличных окончаний. Я ни в коей мере не пытаюсь это оспорить или принизить. Я тут совсем не для этого.

Большая к Вам просьба.
Не приписывайте мне мысли, которых я не высказывал.
Если то, что я пишу, Вам не интересно - я не обижусь, если Вы это оставите без комментариев.

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

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

Спасибо за критические комментарии.
Есть, что конкретно обсуждать.
Я не разбирался со структурой Налимовских баз.
Могу себе чисто теоретически представить, что компактность хранения осуществляется с помощью некоей закольцованности что ли всех позиций в данной таблице. И разрушение этого кольца вызывает в общем случае разрушение целостности данных.
Поскольку Вы в них хорошо разбираетесь, предлагаю Вам подумать, можно ли подобное кольцо создать не для полного количества позиций, а только для ранее отобранной известной части.

Я предложил то, что хорошо понимаю и чем владею.
Стандартная таблица, в которой содержатся те самые поля: непосредственно позиция на доске, результат, оценка.
Индекс по первому полю (позиция).

Примерно прикинул, размер одной записи.
6 бит * N + 2 бит * (N-2) - положение на доске. (Непосредственно положение фигур на доске и указание, что за фигура. Первые две соответственно белый и черный король, для остальных нужно указать, что за фигура)
1 бит - очередь хода
2 бит - результат
2 бит - оценка
Для трехфигурок - это 3-4 байта (грубая оценка).
Плюс наверное 1 байт - хранение ключа (не исследовал)
Соответственно, если хранить в 3-х фигурках, как я описал, выше примерно 30 тысяч позиций, получается примерно 120 Кб.
Но у меня есть серьезные подозрения, что каждое увеличение на 1 фигуру будет приводить к росту таблицы примерно в 50-60 раз, не более.
У Налимова сейчас получается вроде бы примерно 200.

По индексу (ключу) необходимая запись ищется МОМЕНТАЛЬНО не зависимо от количества записей в таблице.
Если индекс не задан, то действительно осуществляется полное "перелистывание" таблиц.

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

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

Налимовские 3-х фигурные базы 69 кБт. Из них с пешкой - 35 кБт. Половина

Есть еще один источник информации, где можно посмотреть реализацию баз KPK. Правда, боюсь, что Кириллу это может не понравиться.
Речь о нашумевших в недавнем прошлом Ипполитах. Базы KPK встроены в исходный текст в виде массивов, правда остается непонятным, как они были получены. Можно попробовать побаловаться с этими массивами и попробовать отсечь от них все лишнее. Как их тогда индексировать - непонятно. Придется подумать о другом способе их представления.

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

А принципиально это может быть реализовано на базе одного файла *.dll
То есть библиотека принимает определенный запрос, обрабатывает и перенаправляет его в соответствующую таблицу, моментально получает ответ и готовый результат отдает движку.

Хотя в большинстве случаев можно встроиться в уже существующий протокол обмена. В этом случае движку все равно от каких баз он получил ответ.

Ну мне как раз понятно, как построить любую базу.
Составляется полная таблица всех возможных позиций. Простым перебором.
Далее составляются цепочки ходов, ведущие от одной позиции к другой до мата или перехода в младший эндшпиль с известным результатом. Потом из всех цепочек отсекаем по альфа-бета критерию худшие ходы. Метод мини-макс (правильнее макси-мин). Таким образом для любой позиции находим оптимальный вариант за обе стороны (цепочку) и переносим оценку конечной позиции на все промежуточные и исходную. В этот момент в промежуточных СЛУЖЕБНЫХ таблицах можно хранить и данные по количеству ходов до мата (для упрощения процесса генерации). В конечных таблицах (пользовательских) я считаю эту информацию избыточной.
Далее по некоему критерию удаляем из таблицы все записи, где выигрыш достигается легко (а таких позиций обычно будет много). Получили компактную таблицу для определенного вида эндшпиля.
Все это, как я предполагаю, примерно также делается и у Налимова. Кроме последнего действия - удаления позиций с очевидным для движка (да и для человека) решением.
Оптимально было еще ДО ПОСТРОЕНИЯ этих цепочек удалить лишние записи. Но вот по какому критерию их удалять - пока не очень понятно.
Один из вариантов - дать эти все позиции оценить какому-то движку и удалить сразу те, которые он гарантировано доведет до победы.
Но возможно, что движок потратит не меньше времени на оценку всех позиций, чем мы, строя цепочки.
Но уж по крайней мере размер усеченной таблицы должен быть заведомо меньшей, чем полной.

Если привлечь специалиста по хранению информации в базах данных, может он предложит более компактный способ хранения усеченного файла, чем в обычных СТАНДАРТНЫХ профессиональных форматах, которыми я пользуюсь.

У меня подобных задач никогда не было. С объемами в 50-100 миллионов записей работал. Там проблем компактности хранения не возникало. Скорее задача ставилась в гарантированной корректности записи на диск, хранения и отображения информации, независимо от объема.

Я про это не знал.
Возможно эти "народные умельцы" уже реализовали подобную идею.
И возможно не одну эту.
А может быть двигаются в неком параллельном направлении.

Вот кстати очень интересный и правильный подход - разбить большую задачу на несколько маленьких.
И параллельно решается проблема пресловутых 50-ти ходов. Если в пределах такого подэндшпиля укладываемся в 50 ходов, то нет необходимости проверять всю цепочку из всех этих подэндшпилей.
Тут опять же время генерации будет существенно сокращено. Если выстроена победная цепочка предположим из 45-ти ходов, то нет необходимости искать улучшения за сильнейшую сторону. А значит количество вычислений до оценки позиции снижается очень существенно.
В нашем прикладном случае мы не обязуемся (зачем?) выиграть выигранную позицию за минимально возможное количество ходов. Нам достаточно уложиться в правило 50-ти ходов и не упустить при этом победу. Вполне рациональный подход.

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

Тут сразу куча идей, пока не до конца обдуманных.

Вот сейчас к примеру невозможно начать считать эндшпиль КРkp, пока не обсчитаны все переходы в другие эндшпили с превращениями в разные фигуры. Итого, мы должны предварительно посчитать 16 разных эндшпилей.

Берем выше упомянутый KRPPkrp (Ладья и две пешки против ладьи с пешкой)

Исходя из опыта и знаний (может быть беглого анализа) делаем вывод, что превращение пешки всегда должно быть в Ферзя. Или в Коня, ЕСЛИ ОН СТАВИТСЯ С ШАХОМ. (Превращения в ладью и слона с переходом в соответствующие эндшпили воообще и не пытаемся рассмотреть.)
Значит нам нужно иметь предварительно всего 4 расчета, причем для превращения в ферзя такой расчет будет очень быстрым. Если за пару форсированных ходов ферзь (или ладья) не съедается, то очевидно это выиграно. А если съедается - переходим в ранее обсчитанный младший эндшпиль.
Правда тут я немного не прав. Другая сторона тоже может поставить ферзя и этот эндшпиль потребует большого обсчета.
Но ведь это и сам по себе интересный эндшпиль Ф+Л+п против Ф+Л.
У Налимова сейчас предварительно нужно обсчитать 4*4*4 = 64 эндшпиля, большинство из которых практической ценности несут мало.

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

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

Еще одну идейку вам подкину - можно попробовать создать алгоритм хеширования каждой позиции (лучше как-то плясать от битборд), один раз проверить уникальность, и дальше уже находить позицию за O(ln(n)) времени (или ещё более оптимально, благо алгоритмы есть. Это позволит хранить нам меньшее количество позиций, выкинув, к примеру, все маты более 50 ходов и менее 5.

Создает эту самую хешфункцию из позиции (я потому и предложил делать хеш на основе битборд) и ищет уже собственно в базе по хешу. Если, к примеру, позиции нет, то ничья (по правилу 50 ходов или ещё как-то - неважно). Если есть - получаем Distance To Mate - в оценочной части движка на этом мы прерываемся - у нас выигрыш, а когда настает время ходить просто генерируем все ходы и запрашиваем DTM по ним.

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

Попробую рассказать механизм запроса к базе данных простым языком.

Вот дали нам файл Excel в котором 10000 записей, расположенных в хаотичном порядке.
И дали задание найти некую информацию, соответствующую записи с номером 2434.
Как мы будем искать?
Тупо просматривать все строчки подряд?
Наверное выделим необходимое поле, нажмем кнопку "Сортировать по возрастанию (или убыванию)"
Табличка выстроится по номерам с 1 до 10000.
Далее мы не будем каждое из чисел 1,2,3 и т.д. сравнивать с необходимым числом.
Мы перелистываем несколько страниц и смотрим на каком числе мы остановились. И таким образом найдем необходимое число и тут же увидим ту самую информацию, которую искали.
А теперь представим, что записей не 10000, а 100000. Разве увеличится время поиска в 10 раз?
Будет такое же, при условии, что листая страницы, Вы сразу попадете на нужную.

Примерным образом и происходит поиск по ключевому полю в СУБД. Только все проделанные нами операции осуществляются автоматически.

Вот если мы сделаем запрос, скажем такого типа - выдай хотя бы одну запись или выдай все записи (это разные запросы) в которых для ничьей нужно сделать 72 хода, то поскольку мы индекс на это поле не задали, будет анализироваться КАЖДАЯ запись на предмет сравнения с числом 72. И чем больше база, тем дольше будем ждать ответа.
Также если мы попросим выдать значения ключевого поля, в котором есть цифра 3 предположим на втором от конца месте, то БД выстроит все записи по порядку и потом каждую начнет анализировать. Это будет долго.

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

Я думаю скорость прежде всего определяется скоростью чтению с диска, а также в какой базе хранятся данные (ORACLE, MS SQL или другая). Но я уверен, что любая современная БД выдаст ответ на простой запрос по ключевому полю за миллисекунды, а может и за доли миллисекунд НЕЗАВИСИМО от количества записей. Опять же многое зависит от настроек БД. Если она ориентирована на обработку большого количества записей - настройки одни, если, как в нашем случае для пользователя, добавлять или изменять записи не надо, нужно только быстрее дать ответ на простой запрос - можно оптимизировать под эту задачу.

Ну это примерно также, как если вы в командной строке наберете полный путь к некому файлу. Скорость доступа к нему не зависит от того, насколько занят в целом ваш жесткий диск, а также от того, сколько файлов лежит в необходимой папке: 2 или 5000.
А вот если вы его будете искать "Поиском", то скорость нахождения в общем случае сильно зависит от заполненности диска.

подробнее про индексы можно почитать на Википедии http://ru.wikipedia.org/wiki/Индекс_(базы_данных)

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

Эти ветки дерева пробегаем по очереди. Когда возвращаемся назад в узлы (надеюсь понятно, что это такое) всю ветку от этого узла и до конца варианта удаляем из оперативной памяти, оставляя в служебной таблице в оперативной памяти только ее оценку, ну и возможно еще (не обязательно!) длину ветки. Все ходы, ведущие к этому узлу стираем из оперативки и заносим в таблицу, т.к. их точная оценка уже известна.
Длина такой цепочки принципиально может быть любой, хоть 1000 ходов. Она заканчивается или переходом в младший эндшпиль, или матом (патом) или повторением какой-либо предыдущей позиции из этой ветки. Или позицией с уже известным результатом из ранее рассчитанной цепочки.

Оперативной памяти для этого нужно оч мало. Ну предположим если 1000 ходов, то 1000*10 байт(грубо) = 10 кБт. Если 10000 ходов не произошло взятия, мата или повторения, соответственно нужно 100 кБт.
В оперативке хранится только текущая НЕЗАВЕРШЕННАЯ ветка от исходной позиции.