6-7-фигурный эндшпильный генератор. 4-я версия

Обновил в интернете версию шахматного генератора. Последнюю, 4-ю версию можно скачать там же -

http://generatorchess.com/

По сравнению с предыдущей, 3-й версией, 4-я использует при генерации баз, еще меньше оперативной памяти - не более 8 GB, для любого типа 7-фигурного эндшпиля (а для многих 7-фигурных - вообще около 3 GB), для 6-фигурных - менее 250 MB и т.д. Впрочем, при выделении нужного типа, будет написано, сколько потребуется оперативной памяти, и сколько свободного места на винчестере. На нынешние персональные компьютеры можно установить до 16 GB, и скоро выпустят материнские платы, поддерживающие до 32 GB оперативной памяти. Поэтому, можно будет на одном персональном компьютере - параллельно запустить 4 генератора (каждый - на своем винчестере), и создавать параллельно и одновременно 4 типа 7-фигурных баз.

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

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

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

Генератор баз.

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

Любой тип 7-фигурной базы, с определенным соотношением фигур, после построения, будет сжат и один такой тип будет занимать от 400 GB, если с пешками, например 7_KRPP-KRP (ладья и 2 пешки против ладьи и 1 пешки), и до 4 GB, если пешек нет, и есть одинаковые фигуры.

Всего 7-фигурных - 1001 типов, и после того, как они будут построены, все эти базы будут занимать приблизительно 200 TB на жестких дисках. Недавно была изобретена новая технология записи, и в ближайшие 5 лет (примерно к 2016 году), появятся винчестеры объемом до 40 терабайт, т.е. поставив 5 таких винчестеров в один персональный компьютер, можно будет хранить все 7-фигурные базы. На одном компьютере. На данный момент, в 2011 году планируется выпустить максимум - 4-терабайтные винчестеры, и поэтому, пока хранить можно не все 1001, а только самые интересные базы. Прогресс за последние 12 лет - увеличение объемов винчестеров в 1000 раз, т.к. в 1999 году были винчестеры по 4 GB, а в нынешнем, 2011 году - уже будут 4 TB. Надеюсь, тепмы роста сохранятся.

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

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

Да, но вопрос как быстро?

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

А есть хоть порядок величин примерный для сложного эндшпиля с пешками?) Сколько примерно будет решать одну позицию? Час? День? Тысячелетие?

Kirr

На данный момент я посчитал все 3-5-фигурные. Все 5-фигурные можно посчитать за пару дней. И еще посчитал - половину 6-фигурных. Если есть хороший персональный компьютер, как у меня, с 6-ю винчестерами (8 GB оперативной памяти), то все 6-фигурные можно посчитать за 1 год примерно.

6-фигурные эндшпили эндшпили 5 против 1 - я пока не считал, т.к. они не интересны. Ои нужны будут только для того, чтобы считать потом 7-фигурные 5 против 2. (например три легкие фигуры с пешкой — против ферзя).

Но пару штук 6-фигурных я посчитал. Это 6_KRRRR-K, и 6_KQQQQ-K, они мне нужны были, чтобы посчитать пару 7-фигурных - 7_KRRRRR-K, и 7_KQQQQQ-K, они конечно, неинтересны, я их посчитал только для того, чтобы протестировать свою программу. Сколько времени заняло? Точно не помню, но где-то за пару дней. Пока считаю 6-фигурные, потом первым из интересных 7-фигурных - буду считать 7_KRBN-KQN, там кажется, должны быть позиции которые выигрываются за 545 ходов или более. (думаю, что он будет построен примерно за 2 месяца. хотя может и больше - т.к. будет слишком много итераций, >=545) Потом буду считать все младшие эндшпили для 7_KRPP-KRP, и сам этот эндшпиль, т.к. очевидно, чаще всего в партиях попадаем именно в него.

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

Поймите, что решение "одной позиции" может быть эквивалентно решению всех позиций с данным соотношением фигур. Если в позиции - мат в 3 хода, то конечно, ее можно быстро решить, не строя всей базы. А если в позиции мат в 100 ходов, то из нее можно попасть почти в любую другую позицию, поэтому приходится считать всю базу. Т.е. возможное будущее из этой позиции - почти все позиции с данным соотношением фигур. Мой генератор считает всю базу целиком, и потом можно уже сразу знать оценки для всех позиций и ВООБЩЕ ничего не считать. Время генерации целой 7-фигурной базы зависит от компьютера, и может быть - несколько месяцев. Всего 7-фигурных очень много - 1001 типов, поэтому чтобы посчитать их все - на одном компьютере, и на одном винчестере - нужно очень много времени, т.е. столетия. Чем больше компьютеров использовать для параллельного расчета типов эндшпилей (на каждом компьютере - считать свои типы. со своим соотношением фигур), тем быстрее будут построены ВСЕ 7-фигурные базы.

Как я уже писал, если использовать 25-30 хороших персональных компьютеров, и на каждом запускать к тому же, по ~ 4 генератора (каждый на своем винчестере), то все 7-фигурные можно посчитать всего за несколько лет. Ведь в компьютер можно поставить до 6 винчестеров. На одном винчестере неэффективно запускать два и более генератора, т.к. они будут "упираться" в его пропускную способность, и будут медленнее считать.

Как я уже писал, если на каждом компьютере запустить по 4 генератора, каждый на своем винчестере, и таких компьютеров будет 25, то получается, будет одновременно работать 100 генераторов, значит и время полной генерации 7-фигурных, сократится в 100 раз по сравнению со случаем, если запустить один генератор, выделить все 7-фигурные, и так оставить, пока он всё не посчитает.

База только для одного этого эндшпиля, 7_KRPP-KRP, будет занимать приблизительно 300 GB.

300 гигабайт - не так уж и много, учитывая, что существуют винчестеры объемом 3 TB, т.е. в 10 раз больше.
Сколько места при этом будут занимать базы для всех младших эндшпилей, точно сказать нельзя, но 3 терабайт точно не хватит Впрочем, можно установить и только этот один тип, 7_KRPP-KRP, на компьютер - тогда программа, играя его будет играть наилучшим образом, но только после превращений, дальше снова вынуждена будет считать, и играть не лучшим образом, т.к. не сможет увидеть оценки в младшем эндшпиле. Например, если сторона с ладьей и 2-мя пешками провела одну из пешек в ферзи, то мы попадем уже в эндшпиль 7_KQRP-KRP, и имея лишнего ферзя, программа выиграет даже не имея этой базы. Т.е. большое усиление игры программы будет наблюдаться, даже если на компьютере будет присутствовать только один тип - 7_KRPP-KRP.
А это всего 300 гигабайт.


PS. А вот чтобы посчитать 7_KRPP-KRP, как ни крути, но все младшие эндшпили - считать тоже придется. А это годы времени, и нужно несколько мощных персональных компьютеров.

Верно. (Ну можно еще 7_KQRP-KQR оставить)

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

Всего 7-фигурных типов - 1001. Полезных, думаю, штук 200, не больше. Вот все полезные и нужно посчитать в первую очередь. На данный момент я посчитал только пару 7-фигурных, и уже большинство 6-фигурных (200 из 295, не считая типы "5 фигур против одной", т.е. против одинокого короля). Когда закончу 6-фигурные, начну считать 7-фигурные.
Интересно посчитать 7_KRBN-KQN, там возможны маты в 550 и более ходов. Если у кого есть компьютер со свободным винчестером на 1 или 2 ТБ, то можете тоже посчитать какие нибудь 7-фигурные. Потом можно будет обменяться базами.

Где можно получить списки типов для 3-4-5-6-7 фигурных окончаний?

Заинтересовался я этим вопросом и не понравилось мне число типов 7- фигурных
окончаний (1001), решил проверить, получились вот такие результаты:

3-х 5 2 : 1 (5)
4-х 30 3 : 1 (15) 2 : 2 (15)
5-и 110 4 : 1 (35) 3 : 2 (75)
6-и 365 5 : 1 (70) 4 : 2 (175) 3 : 3 (120)
7-и 1001 6 : 1 (126) 5 : 2 (350) 4 : 3 (525)
8-и 2520 7 : 1 (210) 6 : 2 (630) 5 : 3 (1050) 4 : 4 (630)
9-и 5720 8 : 1 (330) 7 : 2 (1050) 6 : 3 (1890) 5 : 4 (2450)
10-и 12190 9 : 1 (495) 8 : 2 (1650) 7 : 3 (3150) 6 : 4 (4410) 5 : 5 (2485)

3-х 5
4-х 30 4/3 5.0
5-и 110 5/4 3.67
6-и 365 6/5 3.32
7-и 1001 7/6 2.74
8-и 2520 8/7 2.52
9-и 5720 9/8 2.27
10-и 12190 10/9 2.13


Теперь о размерах
* Все 3-фигурные окончания занимают 80 КБ.
* Все 4-фигурные окончания занимают 30 МБ.
* Таблицы Налимова для всех 5-и фигурных окончаний занимают объём памяти в 7,03 ГБ.
* Полные таблицы для всех 6-и фигурных окончаний занимают 1,205 ТБ. (здесь видимо без 5:1)
* Все 7-и фигурные окончания будут занимать ориентировочно 200 ТБ.

4-х 4/3 375:1
5-и 5/4 234:1
6-и 6/5 171:1 (???)
7-и 7/6 165:1 (ориентировочно)
продолжим последоватеность
8-и 8/7 148:1
9-и 9/8 132:1
10-и 10/9 121:1

Может быть дальше пойдет не так страшно ?
Даешь 8-и фигурку через 3-4 года после 7-и фигурки !!!

NTFS и FAT32 сильно замедляется при работе с ~10k файлами в папке.

Интересно... Программку написали? А посчитайте, сколько всего типов 11-32-фигурных.

А почему вам так не понравилось число 1001 ?

Да все вокруг кратно 5. Да и строится из 5 фигур, а тут 1001.

Нет програмку не писал, посчитал все руками. Там гопая комбинаторика.

Число перестановок с повторениями из N по K. Считактся по формуле:
C( N, K ) = (N+K-1)! / ( (N-1)! * K! ).

С(5,0) = 4! / 4! = 1.
С(5,1) = 5! / 4! * 1 = 5.
С(5,2) = 6! / 4! * 2! = 15.
С(5,3) = 7! / 4! * 3! = 35
С(5,4) = 8! / 4! * 4! = 70.
С(5,5) = 9! / 4! * 5! = 126.
С(5,6) = 10! / 4! * 6! = 210.
С(5,7) = 11! / 4! * 7! = 330.
С(5,8) = 12! / 4! * 8! = 495.
и т.д.

для 6-и фигурок например:
С(5,4) * С(5,0) + С(5,3) * С(5,1) + С(R,2) =
где R = С(5,2).
= 70 * 1 + 35 * 5 + (15 * 16)/2 = 70 + 175 + 120 = 365.

для 7-и фигурок:
С(5,5) * С(5,0) + С(5,4) * С(5,1) + С(5,3) * С(5,2) =

= 126 * 1 + 70 * 5 + 35 * 15 = 126 + 350 + 525 = 1001.
ну и далее по тому же принципу.

Предлагаю совместно строить 7-фигурные базы и обмениваться ими.
Кто нибудь желает? Нужен в наличии компьютер с 750 МБ места на винчестере и 3,5 ГБ оперативной памяти. (это для беспешечных, можно начать с них).

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

Приветствую уважаемое сообщество!

Я желаю. :-[

А именно интересует конкретный 7-фигурный беспешечный эндшпиль. Имеется в наличии 980X с 12 Гб оперативки на борту. Из них могу под проект могу выделить 1 ядро, требуемые 3.5 Гб оперативной памяти и взять новый HDD.

Несколько практических вопросов:
1) имеется в наличии 550 Гб основных 6-фигурок Налимова. Можно ли ими воспользоваться для ускорения процесса, чтобы не считать младшие эндшпили?
2) в процессе расчета сохраняются ли промежуточные данные? Т.е. можно ли говорить, что допустим через месяц расчетов решено столько то процентов из всех позиций и для каждой из этих позиций посмотреть оценку.
3) что значит не выключать комп в течение месяцев? на сколько критична обычная перезагрузка?
4) оценка сроков? это самый критичный момент, т.к. не смогу поддерживать проект дольше 3-4 месяцев. Можно ли распараллелить вычисления, а именно ускорит ли работу подключение дополнительных ядер или дополнительных компов по локалке, или увеличение оперативки и т.д.
5) ускорит ли процесс, если считать только оценку выигрыш/ничью, а не оптимальную длину до мата.

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

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

Было бы можно, если переконвертировать базы Налимова в мой формат. Но для этого надо писать специальную программу, что будет дольше, чем посчитать требуемые 6-фигурные сразу в моем формате. Они строятся за несколько дней. Это намного меньше чем время на генерацию 7-фигурных (несколько месяцев, зависит от типа). В среднем 7-фигурная строится в 40-50 раз дольше, чем 6-фигурная. Потому, если у кого-то есть компьютерные мощности, позволяющие построить 7-фигурные за время N, то не проблема построить требуемые младшие 6-фигурные (скажем, 5 штук) + одну 7-фигурную за время 1,1 умножить на N.

Сохраняются, но база будет несжата, и не готова для использования.

Базы строятся следующим образом. Сначала ищем позиции с оценками +-#1, т.е. с матом в 1 ход. Потом с оценками +-#2, потом с оценками +-#3. И так далее. Каждая итерация будет проходить скажем, за 1 день (зависит от типа выбранной базы). Если вы например, построили все позиции с оценками +-#65, это значит что в базе все позиции с матом в 65 ходов И МЕНЬШЕ - уже присутствуют. Вы видите итерацию
+-#65 ——> +-#66.
Значит в данный момент программа ищет все позиции с оценками +-#66.
Если в это время перезагрузить компьютер, то утрачены будут только позиции с оценками +-#66. При возобновлении работы, они будут строиться сначала. Т.е. итерация
+-#65 ——> +-#66
начнется сначала. Т.е. утрачены будут данные работы компьютера только нескольких часов. (сохранять все промежуточные данные, чтобы и этой утраты не было - было бы накладно и сама генерация проходила бы медленнее, потому сделано сохранение идет каждый раз после каждой полностью выполненной итерации). Нужно просто перезапустить программу и на жать на кнопку "Build". Если там что-то строилось до этого, то программа прочитает это в файлах и начнет заново с итерации
+-#65 ——> +-#66
а первые 65 итераций, которые строились до этого 1 или 2 месяца, сохранятся.
Время на полную генерацию будет зависеть от типа выбранного эндшпиля, ожидается, что если строить беспешечные 7-фигурные, то на 1 итерацию будет вначале уходить от 12 часов до 1 суток. Дальше итерации ускоряются, и итерации 99->100 будет выполняться скажем, уже только 6 часов, 199->200 - 1 час и т.д.
В результате, ожидается, что 7-фигурная беспешечная база (1 выбранный тип, например RBN-QN, т.е. ладья слон и конь против ферзя и коня) будет строиться 2-3 месяца. Всего этих типов много, но нам все не нужны, а нужны только самые важные, скажем те, которые будут потом младшими для важных пешечных, например BPP-RP (слон и 2 пешки против ладьи и 1 пешки), или RPP-RP (ладья и 2 пешки против ладьи и 1 пешки) и др.


Предположим, нам нужно построить 40 важных беспешечных 7-фигурных типов. Каждую базу, как я уже писал, выгодно запускать на 1 винчестере, потому что мой генератор загружает винчестер и производительность "упирается" в производительность винчестера. Если запустить на 1 компьютере, с 4 винчестерами, на всех 4 винчестерах параллельно 4 мои программы, то через 2-3 месяца будут построены сразу 4 беспешечные 7-фигурные базы. А через 2 года, мы построим все требуемые (важные) беспешечные 7-фигурные базы. А если использовать не 1 компьютер а больше, то можно еще быстрее все построить.

Ну вот, если запустить одновременно несколько программ для генерации, то этим самым вы и распараллелите вычисления. В рамках одного эндшпиля распараллелить больше нельзя. Программа сама пытается распараллелить, в несколько потоков, но упирается в производительность винчестера. Т.е. ваш винчестер будет загружен, а процессор будет "отдыхать", там в среднем не будет полностью загружаться даже одно ядро. Потому процессора у вас точно хватит, даже на 6 запущенных генераторов, лишь бы винчестеров хватило. Запускать 1 и более программы на одном винчестере по понятной причине, нецелесообразно.

не ускорит.

Сколько нужно оперативной памяти и свободного места на винчестере, где находится программа-генератор, отображается при выделении интересующего вас типа эндшпиля. Например, мы хотим построить 7_KRNN-KQN, т.е. ладья и 2 коня против ферзя и коня. Запускаем программу (Retrospective_Chess_Generator4.exe), выделяем тип 7_KRNN-KQN (на кнопку Build не нажимаем), и видим что потребуется 3,3 ГБ оперативной памяти, и 770 ГБ свободного места на винчестере. Если, например, не хватает свободного места на винчестере, то это приведет к краху всей генерации, т.к. программа не проверяет каждый раз свободное место на винчестере, и полагает что ее обеспечили всеми необходимыми ресурсами. Поэтому за этим делом нужно следить, что в принципе, несложно. Всего 2 вещи. Проверять сколько свободной оперативной памяти в таск менеджере, и сколько свободного места на винчестере (точнее, на диске, где находится сам экзешник программы-генератора) в начале, в процессе генерации, пока программа-генератор работает.

Если с ресурсами ((1)ОП, и (2)свободное место на диске) проблем нет, и в процессе генерации на винчестере не появились бэд-блоки (т.е. нечитаемые), т.е. проблем с железом нет, тогда программа точно построит правильную базу, и оценит все позиции из множества с данным сочетанием фигур.

Нужно еще понимать, что "770 ГБ свободного места на винчестере" нужно ИМЕННО ДЛЯ ГЕНЕРАЦИИ, для разжатой строящейся базы и всех служебных файлов, сама же база, после того как будет построена, будет сжата и будет занимать намного меньше места. 7_KRNN-KQN может, даже и 70 ГБ не будет весить. Это еще зависит, какие там оценки позиций, количество ничейных позиций и т.д. Заранее это предсказать нельзя, насколько в конце сожмет базу мой архиватор.

Скачал программу, посмотрел требования - для интересующего меня эндшпиля KRBN-KRB требуется 1,5 ТБ и 6,7 ГБ ОЗУ, т.е. больше половины всей моей памяти Придется подождать апгрейда компа и увеличения памяти. Заодно может дождусь снижения цен на HDD. Есть какие-нибудь приоритеты в выборе жесткого диска? Если это самое узкое место - нельзя ли какую-то часть текущих расчетов делать с помощью небольшого SSD (80-160 ГБ), который может полноценно загрузить SATA-3?

SSD конечно выгоднее. Но дороже.
Вас интересует KRBN-KRB?
А меня интересуют типы, в которых может получиться новый известный мировой рекорд до мата. Пока известна позиция в KRBN-KQN с матом в 545 ходов. Эта база была построены в метрике DTС и точный рекорд до мата в KRBN-KQN неизвестен. Предполагаю, что в этом эндшпиле возможны позиции с матами в 550-560 ходов.

Но пока строили мало типов. Думаю, что в других могут быть новые рекорды. Подозрение падает на KQNN-KQN, KQNP-KQN и др. Вот их и планирую считать, когда винчестеров докуплю.

Было бы здорово найти следующую прогу - может уже кто-то реализовал. Создать легкоподключаемую бесплатную программу типа торрента или вируса, которая будет распределять работу компьютера - объединять много небольших по мощности компьютеров по интернету для выполнения какой-нибудь единой большой идеи - скажем подсчета 7-фигурных баз. Особенно полезна такая программа для любительских и бесплатных проектов. Надо разрешить программе постоянно выделять часть пропускной способности веб-канала, часть оперативной памяти, часть жесткого диска для выбранной пользователем работы. Главное сделать в интернете кнопку, на которую можно нажать пользователю, чтобы его компьютер начал автоматически выполнять такую работу. Автоматическое сохранение и отправление отчета о проделанной работе. Защита от сбоев связи/выключения компа аналогично торренту.

Вот что я нашел сходу: может сойдет
http://ops.rsu.ru/about.shtml
http://ru.wikipedia.org/wiki/Автоматическое_распараллеливание

boinc -проекты уже 10 лет как считает различные распределённые вычисления. В том числе шахматы 960. http://www.boinc.ru/

В каких программах образующиеся базы можно будет использовать? Только в приложенной RetroChess3?

А нельзя сделать чтобы SSD винчестер использовались как типо буферной, оперативной памяти для большого? По 60 Гб вполне себе стоят демократично, $100. На 30 Гб менее 1900руб. http://www.ulmart.ru/hdd/Насколько это по прикидкам ускорит процесс генерации котов?
И, кстати, как я считаю важное узкое место проекта - это отсутствие популяризации интересной идеи на мировых сайтах, англоязычных. Не коммуналках и форумах.
Не хотел бы написать статью для чессбэйса, например? Или какого то шахкомпьютерного рессурса? Может есть приятель, который это на английский переведет за несколько кружек пива?
Статья на топовом англоязычном шахсайте, по своему опыту скажу, поднимает интерес к теме в разы, да еще и с эффектом снежного кома. Это я свой ютубе канал имею ввиду. Может какой нибудь перец прочитать, имеющий доступ к хорошим компам, поделится идеей с другими...
Еще вопрос. Насколько безопасно для здоровья и самочувствия котоввинчестера его многомесячная работа?

Если для игры движков, я считаю, что только SSD и имеют смысл (вообще без старых жёстких дисков). Они настолько медленны, что замедляют поиск.

Для игры движков усиление в 10 -15 пунктов. Речь идет об анализе эндшпилей, конкретных. А точнее пока речь о тупо генерации идет.