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

Много кто экспериментировал с методами сжатия, разными метриками и т.п. разбираясь с генератором Налимова? С методами сжатия - не вопрос - могу дать исходник моего архиватора, вы по нему разархивируете базу и сможете потом заархивировать своим архиватором. Код доступа тоже сможете переписать - подсунув другие бинарники для разархивирования нужных блоков базы. Что еще? С разными метриками или методами индексации - такие эксперименты ничего не дадут, придется настолько сильно все менять, коренным образом, что проще будет написать другой генератор с нуля. Это мне проще создать генератор, скажем в формате DTZ-50, пользуясь идеями нынешнего, т.к. я там все знаю. А разобраться в ЧУЖОМ коде, настолько алгоритмически сложном, практически нереально.

Если бы я знал изначально, каких трудов мне это будет стоить, то я бы наверное, не взялся за эту работу... А потом уже я не мог остановиться... И я просто ощущал эстетическое удовольствие от того, как я каждый раз делаю программу-генератор, все более совершенной. Есть такой тип людей, которые могут сделать какой то объем работы, только потому, что им это ИНТЕРЕСНО. У меня этот показатель-объем большой. Но таких людей очень мало. И у меня уже кончилось терпение, делать что-то еще в формате DTZ-50, WDL и других, я уже "за просто так" не буду. Да и метрика DTM для меня самая важная и интересная (так же как и для Налимова). Лично мне - другие метрики уже не интересны.

Мы уже как-то спорили о том, какая метрика лучше. Но всем, кто достаточно поиграет, станет ясно - самая математически сильная игра, и самая эстетически красивая - когда программа играет по базе DTM. Она быстрее всего ломает все преграды, защиты и т.д. И быстрее всего ухудшает позиционную оценку соперника. Может сложиться такая ситуация - играя по одной линии (DTM), можно поставить мат в 45 ходов, и от такой игры программы - человек получит эстетическое удовольствие. А если программа будет играть в формате DTZ-50... Она вместо того чтобы играть и ставить мат через 45 ходов - будет стремиться разменять скажем, пешки, через 44 хода (видишь ли, на один ход раньше, и программе пофиг - мат там или всего лишь какой то дурацкий размен, хотя это абсолютно неравнозначные понятия для определения оценки позиции), после чего выиграть ТРУДНЕЕ - там до мата еще будет оставаться 100 ходов. Т.е. по сути, программа, играя по базе DTZ-50, может не только не сильно играть с точки зрения логики, а вообще, даже ТУПО играть. И многие кстати, жаловались на эту тупизну! DTZ-50 нужны только чтобы проверить, удовлетворяет ли позиция правилу 50 ходов. Не было бы этого правила - не было бы и этой ненужной на мой взгляд, метрики. (лучше уже DTM-50). Ну да ладно, я насчет метрик больше спорить не хочу. Кто захочет понять о чем я говорю - сам поймет.

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

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

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

Поэтому одно из решений данной проблемы (если уже вы хотите на 100% быть уверенным, что не было хардварных ошибок) - сгенерировать два раза каждую базу, без разницы, на разных компьютерах, или на одном.. Если окажутся одинаковыми контрольные суммы - т.е. количества выигрышных позиций по всем дистанциям до мата (у меня пишется в файл txt), то можно быть уверенным, что хардварных ошибок не возникало. (ну никогда никто не поверит, что на разных компьютерах, в одном и том же месте в нужное мгновение произошел одинаковый сбой железа ) Если же контрольные суммы окажутся разными - значит по крайней мере в одном случае сбой железа произошел, и придется перегенерировать, чтобы удостовериться, какая база из них правильная. Кстати, у меня итерации можно "откатить" назад, и перегенерировать с какой то произвольной точки, т.е. итерации. И еще можно делать промежуточные проверки, т.е. получение этих контрольных сумм на любой итерации, т.е. до окончания полной генерации. Если интересует, и вы будете генерировать базы, то могу рассказать, как все это сделать. Иначе, контрольные суммы (txt-файл) будут созданы только в самом конце, после завершения генерации данного типа эндшпиля.

Я пока еще дома генерирую 6-фигурные базы, и тут можно сгенерировать только 1 раз и потом убедиться, что ошибок не возникало, сравнив контрольные суммы с суммами в базах Налимова. Пока наблюдалось ПОЛНОЕ совпадение, ни одной хардварной ошибки, ни одного несовпадения, хотя я эти базы уже целый год генерирую. Поэтому, как видим, такие ошибки "железа" довольно редко встречаются. (скоро все 6-фигурки в моем формате у меня будут есть и пару 7-фигурных, сгенерировал ради интереса)

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

А вычисление всех (тысячу) 7-фигурных будет идти годами.

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

Теоретически да, могут и черные быть в выигрышной. Но...
Не верю © Станиславский.

Чем больше фигур на доске, тем менее вероятны позиции с цугцвангом. Для 32 фигур такая вероятность практически равна нулю, ну может что нибудь порядка 0,000000000000000000000000000000001.

Почему вы так думаете?

А зачем ее учитывать? Я тоже не учитываю. Разве может быть такое, что 6-7 фигур на доске, и к тому времени еще можно рокироваться? Вот когда создам хотя бы 15-фигурные базы, то может, и рокировку учту

Давненько не брал в руки шашек и не читал о них, но, насколько я помню, статистика в них в пользу чёрных.

Месяцы мучений за черных при игре в адванс навсегда избавляют от таких мыслей.

Наверное с японскими шашками, рендзю перепутал. Там черные начинают :d

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

Из личного опыта. Через месяц я уже сам не могу в своем коде разобраться.

Для тех кому не хватает место под таблицы на винчестере http://habrahabr.ru/blogs/DIY/119367
Статья называется "А не сделать ли нам домашнюю файлопомойку на 90 терабайт?". Без учета винтов это стоит в пределах 40-50 тысяч рублей. По этому же принципу можно сделать любой объем файлового хранилица.

Как я уже писал в параллельной теме, последнюю версию моего эндшпильного генератора можно скачать здесь

http://generatorchess.com/

Всем привет!
Хотел бы поделиться некоторыми идеями по поводу построения и использования эндшпильных баз.

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

Важно правильно сформулировать цель - для чего же это все затевается.
Сначала немного помечтаем.
Самая желанная задача - создать и обсчитать все 32-хфигурки. Это было бы здорово. ПОСЛЕ этого никакие Рыбки и Гудини уже будут практически не нужны. По крайней мере их роль будет вторичной.
Увы. В настоящее время и в обозримом будущем эта цель очевидно недостижима.
И причины тут две:
1. Недостаточное быстродействие компьютеров для генерации соответствующих таблиц.
2. Огромный объем таблиц, которые необходимо постоянно хранить на жестком диске.

Так что же, объявить данную задачу нерешаемой и забросить?
Наверное нет.
Нужно просто переформулировать задачу.
На данный момент она видимо должна звучать примерно так:
ПОМОЧЬ существующим и будущим движкам ДАВАТЬ БОЛЕЕ ТОЧНУЮ ОЦЕНКУ текущей позиции за счет ранее рассчитанных N-фигурок, А ТАКЖЕ дать им ПОЛНУЮ ИНФОРМАЦИЮ о разыгрывании получившейся на доске N-фигурке.

Таким образом, данная задача уже сейчас разбивается на две подзадачи (на примере имеющихся 6-тифигурных таблиц):
1. Если в анализе, предположим 11-ти фигурного эндшпиля имеющегося сейчас на доске, в результате разменов возникает позиция с числом фигур 6, то движок автоматически получает от эндшпильных баз результат этого варианта в трех значениях - 1, 1/2 или 0. Обратим внимание, что на данном этапе ему (движку) совсем нет необходимости знать, какой ход (или какие ходы) ведут к этому результату и во сколько ходов достигается победа или ничья. Важно только получить РЕЗУЛЬТАТ. После чего он (движок) эту ветку бросает и переходит к следующей.
2. Когда в результате дальнейшего разыгрывания данной партии реально происходят размены и создается тот самый 6-ти фигурный эндшпиль, то в первую очередь движку интересен ход (или ходы) оптимально приводящие к требуемому результату. При том этот самый требуемый результат (1, 1/2, 0) вообще говоря ему сообщать и не обязательно.

Таким образом, мы видим, что в общем случае движку нужны 2 типа таблиц и 2 разных ответа от этих таблиц.
В настоящий момент, насколько мне известно, в обоих случаях используются одни и те же таблицы и, скорее всего, один и тот же протокол обмена (возможно избыточный).
Нужно ли создавать две разные таблицы или экономичней использовать общую под эти две задачи?
Пока у меня нет ответа.
Но мне представляется, что в первом случае (когда идет ДЛИТЕЛЬНЫЙ расчет ОГРОМНОГО КОЛИЧЕСТВА вариантов на большую глубину) необходимо давать моментальный ответ. А вот когда идет уже розыгрыш непосредственно N-фигурки, то можно не выдавать готовый ответ из таблицы (а следовательно и не хранить эти данные на диске), а НАПРИМЕР запустить встроенный генератор предложенный Skipper_NORTON для одной данной позиции. Я думаю одна конкретная позиция может быть обсчитана достаточно быстро.

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

Таким образом, возвращаемся к тому, что от ХРАНЯЩИХСЯ НА ДИСКЕ ТАБЛИЦ необходимо только получить готовый результат (1, 1/2, 0). Тут легко понять, что если, предположим, удалить из готовой таблицы все ничейные позиции, то удастся существенно (возможно в 1,5 - 2 раза) уменьшить их объем. При этом если в таблицах есть исходная позиция, то движок получает ответ - 1 или 0, если нет - ответ 1/2.

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

Собственно это ОДИН из вариантов решения проблемы большого объема таблиц.

Можно ли что-то придумать по скорости расчета?
Могу предложить такой вариант:
1. Создается (генерируется) таблица, в которой присутствуют ВСЕ теоретически возможные N-фигурные позиции.
2. Каждая из них выдается для анализа некоему приличному движку (на выбор).
3. Задаются критерии по времени и по оценке. Предположим 10 секунд и интервал оценки позиции от +5 до -5.
4. Всем позициям, которые оказались вне этого интервала СРАЗУ ЖЕ присваивается результат: 1 или 0 соответственно.
5. Естественно эти позиции далее генератором не обсчитываются.

Думаю при этом скорость генерации N-фигурных эндшпилей может возрасти в несколько раз, БЕЗ ПОТЕРИ ИНФОРМАТИВНОСТИ И ОБЪЕКТИВНОСТИ. Опять же, если данный конкретный эндшпиль возникнет в партии, то имеющийся генератор его очень быстро обсчитает.

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

Прежде всего хочу поблагодарить специалиста за конструктивную критику.

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

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

В качестве отправной точки попробуем взять историю развития непосредственно шахматных программ.
Первоначально в качестве основного ( а чаще всего и единственного) метода расчета позиций был метод "brute force" - то есть "грубой силы". Когда программа рассчитывала подряд все ветви дерева до определенной глубины и выбирала ход с наилучшей оценкой. Сейчас мы уже знаем, насколько это неэффективно. Программы играли убого, берегли каждую пешку, никаких серьезных идей не демонстрировали. Все потому, что были не в состоянии посчитать и оценить позицию на серьезную глубину.
Одним из прорывов (не единственным) в разработке шахматных программ стала как раз попытка отказаться от этого метода. И, как оказалось, попытка очень эффективная.

В разработке эндшпильных таблиц на первых порах (да похоже и сейчас тоже) используется все тот же метод "brute force". То есть попытка полного расчета всех вариантов соответствующего эндшпиля.
По моему мнению, путь утопический. Сумасшедшие цифры количества позиций, возможных ходов и т.п. заставляют задуматься о том, что на нашем веку с таким подходом удастся рассчитать данные дай бог для 8-9 -ти фигурок. Это скучно. Очень хочется какого-нибудь прорыва.

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

Это я предположил не для того, чтобы опять стирать какие-то уже обсчитанные позиции.
Идея в том, чтобы СУЩЕСТВЕННО в разы и на порядки уменьшить время генерации таблиц. А сокращение объема баз - это вторично.

В качестве самого простого примера:
Во всех эндшпильных базах в настоящее время хранится очень большое (думаю до 90%) ну не то, чтобы уж откровенного мусора, но практически не нужной для современных движков информации. Например, 3-х фигурный эндшпиль К+Ф против К. Понятно и очевидно, что любой современный движок из любой такой позиции поставит мат. Пусть даже не в минимальное количество ходов. Нет никакой проблемы, если до мата он сделает на 2-3 хода больше, чем это необходимо.

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

Интересен ли такой подход и соответственно гипотетически полученные таким образом результаты?

Могу предположить такую альтернативу:

1. Имеющими в настоящий момент способами в течение предположительно 3-4 -х лет удастся создать полную базу 7-мифигурок. В ней сразу известно, сколько ходов нужно сделать до мата, известны все ходы, которые ведут к победе, а которые к ничьей. И еще разная интересная, но наверное не очень важная информация.
2. В течение того же (примерно) промежутка времени построить неполные базы 7-ми и 8-ми фигурок. В них не будет позиций с заведомо определенным результатом (вроде Ф+Л+К против С+п), в них чаще всего не будет всех возможных ходов, даже возможно не все выигрышные ходы будут храниться. Для многих эндшпилей не будет рассчитано и точное количество ходов до победы.

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

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


Пока так...

предлагаете делать битбазы? в них нет хода, а только данные о результате, т.е. 1-0 0-1 или 1\2.
размеры таких баз в разы меньше полных.

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

bankuss'у:

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

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

Еще есть идея такая: создать ДВЕ РАЗНЫХ группы таблиц.
Одна из них - условно назовем ее "крепости". То есть позиции с изначально большой оценкой, но тем не менее заканчивающиеся вничью. Это должна быть полная таблица, аналогичная существующим на данный момент. Потому что движок самостоятельно не сможет найти в ней узкую тропинку к ничьей. Но записей в ней будет очень мало. Причем наверное за слабейшую сторону достаточно хранить только те ходы (1-2-3, вряд ли больше), которые в итоге приводят к ничьей, а за сильнейшую (которая пытается выиграть) все возможные, ну кроме может быть откровенных зевков, которые ведут к проигрышу.
При этом те позиции, которые приводят к закономерному результату - не хранятся и НЕ ОБСЧИТЫВАЮТСЯ при составлении таблиц. Вот таких позиций, которые занимают, насколько я понимаю, большое место в базе и на точный расчет которых тратится много времени и ресурсов, в этой таблице не будет.

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

Для понимания того, насколько существенной может быть экономия сил (времени генерации) и средств (места на диске) наверное можно взять все имеющиеся на данный момент 3-х - 6-ти фигурки и выделить из них общее количество тех, в которых изначально оценка достаточна для выигрыша (те же самые пресловутые +5). Я думаю таких позиций никак не меньше половины. Если же из этой выборки попытаться найти те, которые заканчиваются вничью, то вряд ли там будет сколько-нибудь значимое количество.

Опять же, я пока не пытаюсь описать, каким путем подобные таблицы будут строиться (хотя некоторые мысли есть), а пытаюсь понять, будет ли такой подход эффективным или нет.

Да, я с Вами согласен. Пока все на уровне идей.
Когда это все оформится во что-нибудь реальное - можно будет и попробовать.

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

Почему бы таблицы не хранить в таком формате:

1. ID позиции (с указанием положения на доске, очереди хода, возможностей рокировок, взятия на проходе и т.п.)
2. Оценка
3. Лучший ход (или ссылка на ID позиции после лучшего хода)

С учетом описанного мной ранее, если оценка какой-то позиции >+5, то ссылка может быть =0. Это означает, что данная позиция только получила оценку (каким-то способом), а лучший ход в ней при построении таблиц не искали, движок сам сможет довести ее до победы.

Опять же, с учетом изложенного мной ранее, в поле оценка могут храниться следующие числа: 0, +300, -300, или в диапазоне от 5 до предположим 50.
Первое число указывает, что при лучшей игре получается ничья и можно по ссылкам выстроить линию, ведущую к ничьей. Второе и третье - указывают на выигрыш белых или черных.

А вообще где-то можно почитать про формат, структуру баз Налимова?

Спасибо.

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

А еще вопрос, чтобы оценить время работы и предполагаемый размер таблиц.
Известно ли точное (или приближенное) общее количество всех легальных позиций для 3-х, 4-х, 5-ти и 6-ти фигурок?

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

Kirr'у

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

Еще раз попытаюсь сформулировать свою мысль.
Я не веду речь об уплотнении структуры существующих баз.
Я говорю о том, что ЗАВЕДОМО ВЫИГРЫШНЫЕ ПОЗИЦИИ вообще исключить из баз.
Или ХОТЯ БЫ не обсчитывать их вообще при генерации.
Пусть это будут те же налимовские базы.
Таких никому не интересных позиций в этих таблицах думаю процентов 75. А может и поболее.

Сейчас же говорится о том, что допустим позиция "Два ферзя против трех пешек" никого не интересует.
Так зачем тратить месяцы на ее обсчет? Зачем хранить потом по этому соотношению терабайты информации?

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

И еще раз.
В том виде в котором это все на данный момент существует - это тупик.
Никакого прорыва добиться не удастся. Обсчитанные 7-ми фигурки - это предел, которого и в скором времени не удастся добиться. При этом подразумевается, что только для хранения всех этих таблиц потребуются затраты, сравнимые со стоимостью автомобиля. Кому оно в таком виде будет интересно?
Можно тратить кучу времени на оптимизацию кода и т.д., но существенного результата не будет. А тот, который получится мало кого устроит. Лучше это время потратить на поиск и генерацию идей для выхода на какой-то принципиально новый уровень.