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

Mustitz

Вы привели пример исключительный в своем роде. Конечно, для такой позиции проще сделать расчет. Но таких позиций очень мало.

bankuss

Если сжать утилитой из tbgen, то уверен что сожмутся не хуже чем у Налимова. WinRAR, по крайней мере, мои базы сжал лучше чем у Налимова. Но использовать чужие разработки как-то нехорошо, поэтому я написал свой собственный архиватор для баз, он сжимает-разжимает очень быстро, блоками по 10 килобайт, это гарантирует быстрый доступ к базам, но базы получились на 20 % больше по размеру, чем у Налимова, например, все 5-фигурные - у Налимова 7,1 GB, а у меня 8,8 GB. Архиватор у Налимова получился лучше. Но зато у меня программа очень хорошо оптимизирована по количеству используемой оперативной памяти, а также, по скорости генерации.

Архиватор, я так понял, писал не Налимов. Там совсем другой автор. Блоки там по 8192 судя по вызову из командной строки.

Один момент - WinRAR сожмет базы лучше чем у Налимова, если сжимать разжатые. Если сжимать базу уже после того как их сожмет моя программа, то конечно, сожмется хуже. Энтропия (мера беспорядка) растет от сжатия любым архиватором, следовательно каждое следущее сжатие уже сжатого будет менее эффективно.

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

В будущем еще хочу обычную программу шахматной игры вообще из любой позиции сделать.
А до сих пор что, шахматные программы не из любой позиции играть могут?

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

ProstoTak

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

Mustitz

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

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



Это самая неприятная в расчете позиция. Считаем: белая пешка может занять пять полей, черные пешки соответственно пять и четыре. Итого 100 вариантов. Вместо того, чтобы учитывать всевозможное расположение пешек: 60*59*58 = 205 000 вариантов. С учетом того, что надо искать мат в случае превращения и т. п. верхняя оценка сложности окончания в два раза превышает пятифигурное окончание.

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

Mustitz

Я понимаю, что вы хотите сказать. А если пешки превратятся в фигуры? Мы можем получить из этой позиции множество 7-фигурных опять же, младших эндшпилей. А фигуры-то в будущем могут стать куда угодно. Придется считать все возможные позиции в будущем из данной позиции, игнорировать что-то здесь нельзя (даже если нам кажется что это плохой вариант), т.к. там могут быть всякие скрытые возможности. И это намного больше чем число позиций в 5-фигурнике, и даже чем в 6-фигурнике. Ради одной этой позиции делать такой расчет смысла думаю, нет. А так мы сгенерировали все сразу - и программа мгновенно, за доли секунды получит точную оценку для ЛЮБОЙ 7-фигурной позиции. Вообще не нужно будет ничего считать, все будет рассчитано заранее. А для вашего случая, думаю подойдет Freezer. Я с ним не разбирался.

ну вот как 4 фигурку генерируешь ручным генератором - запускашь например KPKP - он начинает генерировать KNKN KBKB и тд. и только потом уже пишет сам KPKP. здесь так же?

Я это тоже понимаю. Только для генерации, например, базы ферзь с пешкой против ладьи с двумя пешками надо генерировать огромное количество промежуточных баз: два ферзя против ладьи и двух ферзей и т. п. С учетом вышесказанного время генерации общей семифигурной базы может быть очень велико. С другой стороны рассчитать конкретную 7-8-9 фигурную позицию не составит большого труда. Конечно, возможен вариант превращения пешки, но в этом случае я бы удовольствовался ответом: оценка неизвестна, игра сводится к такой-то позиции. Думаю, что еще один аналог freezer был бы полезным. Если у Вас нет желания развиваться в этом направлении, то я не могу иметь ничего против. Мое дело предложить

bankuss

Так же. Иначе быть не может. Чтобы рассчитать все позиции в эндшпиле KPKP, надо знать будущее этих позиций. А в будущем пешки могут превратиться в фигуры. Следовательно, эндшпиль KQKP например, будет младшим для KPKP, т.е. он уже должен быть построен, чтобы построить KPKP.

Mustitz
>> С другой стороны рассчитать конкретную 7-8-9 фигурную позицию не составит большого труда.

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

Что-нибудь типа freezer-a я мог бы написать, все таки у меня много готовых алгоритмов, и менять придется меньше чем писать с нуля. Но это все равно довольно долго будет по времени.

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

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

Kirr, вы конечно правы, надо будет сделать еще генератор эндшпильных баз, учитывая правило 50-ти ходов. Там много чего менять придется, но займусь как-нибудь в будущем. Заодно и с произвольными размерами доски буду проектировать. А пока у меня всё по той же системе, как и у Налимова. (Согласитесь, что такая система тоже должна иметь право на жизнь. Меня, например, часто интересует, можно ли выиграть из какой-то позиции В ПРИНЦИПЕ, а если бы были базы, только учитывая правило 50 ходов, то по ним могла бы быть ничья, а реально там мог бы быть выигрыш за 60 ходов например.)

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

Думаю у многих на форуме есть мощное железо. Не дома, так на работе.Где ты NS,Kirr? Была тут тема у кого какое железо.У Cresta вроде хоть и старенькое, но и сечас приличное.Если своп действительно ненамного задерживает процесс, то вполне могут попробовать посчитать.У меня то совсем мрачный ноутбук.2 гига максимум и винчестер более нескольких гигов не сунуть.IBM действительно, кроме кластеров безумно дорогих больше 8 гигов не тянут.Кстати сам искал материнки покруче и есть с 8-ю слотами под 4-х гиговую память. Но 8 умножить на 4 получается не 32, а 8 гигов максимум. Есть и шести слотовые по 4 гига, но 6*4 получается не 24, а 8 ((((. Может кто меня и поправит и найдет конкретную ссылку.( Ой!приходится редактировать. это я не нашел,а знакомый нашел за 16 000.вполне разумная цена. Еще и два 4ядерника хсенона серверного можно засунуть.Это и без всяких генераторов кошерно.Тока они дороже квадов стоят.) А вот Маки поддерживают 32 гигабайта памяти. И кучу винчестеров.Такой стоит 77 тысяч без памяти. В районе сотки все выйдет.А если не Мак, то в районе 60 тыс. рублей выйдет.Надо уточнять, но полюбому дешевле Мака. Налимову вполне такое железо дуступно.Те, кто генерил 7-фигурники с выигрышом в 570 ходов именно таким и пользовались, наверное.
Жаль Мак винду тока эмуляцию якобы использует. Еще тормозить будет.
В общем все не в железо, а деньги упирается.
Ну так пока сам то автор генератора сгенерил хоть пару баз?
Еще важно составить список интересных баз без мусора.Если в 6 фиг. куча 2 ферзя против 2 слонов, то в 7 фиг больше хлама будет типа 3 ферзя против 2 слонов. На самом деле в первом примере есть боевые позиции, когда один ферзь сразу забирается с шахом, а второй на связке оказывается ( слоны, разумеется одноцветные). С таким этюдом в кавычках можно и без компа разобраться)))А 7 фиг. тоже есть псевдо "боевые" , когда два слона против 3 ферзей побеждают типа мат сооружают. Вопрос в том,такое соотношение не может возникнуть на практике.Васик справедливо считает, что пешку всегда в ферзя надо превращать.
Не помню даже в коня может рыбка превращать? Забыл.
А вот 2 ферзя против 2 ферзей имеют большое теоретическое значения.Во время партии Каспаров-Мир оч. не хватало ее. И спецом генерили именно ее для конкретной головоломной позиции.
из 1000 позиций 7 фигур шахматист с квалификацией мастера должен отобрать явный мусор и маловероятные позиции.Скока останется на трубе?))) На глазок не представить.

Мне кажется автору генератора стоило учесть, что кластеры, да и серваки не под виндой часто работают.
Но вот нашлась ( знакомый админ нашел) плата под винду 32 гига за 16 000 рублев. http://verba.ru/cgi/price/price.pl?id=44383&cmd=show_tech_info Вроде при выходе, недавнем причем она 3 тыщи баксов стоила. Ксеноны сами по себе, правда дорогие, чисто за бумажку, на которой написано название процессора. Но можно и один поставить, а потом копить деньги на второй процессор.
Но направление работы ясно. Надо трясти шахматистов - олигархов типа Маслака, чтобы они обновили свой 4-х ядерный хлам и прикупили хоть пару десятков винчестеров терабайтных.Трясти надо коллективно и жестко на разных гостевых,лично,вконтакте,через знакомых

комп то есть мощный, не проблема, но программа не умеет использовать 2-3-4 ядра. память дело наживное, а вот скорость на 1 ядре не увеличишь! только если ждать новых процов и разгонять их.
tbgen который с линуха, умеет 2 ядра юзать. 4 фигурку минут за 10 генерирует. т.е. прирост скорости заметен.

Ну никто скорости для генератора 7 фиг. не требует. А где с какой скоростью 4 фиг. генерятся не ориентир. Там видимо одно ядро половину ВСЕЙ БАЗЫ решает,а второе другой десяток позиций.Может 3 фиг база за секунду генерится, а на двухядернике за полсекунды)))) А в 7 фиг. одно соотношение фигур месяц надо решать и ПОКА автор ничего не говорил о многопоточности.
Да, ну если память дело наживное, а комп есть - вперед наживай память и отчет о проделанной работе! Ждем!
P.S. Вроде надо начинать с безпешечников, а там поменьше нужно памяти.Вперед, мои бедные румыны!Как говорил классик)))

Сергей С. Питер т.е. генерация таблицы за 1 неделю или за 2 разницы не имеет? скорость то как раз самое важное в этом деле.

Имеет значение, что база( одно соотношение 7 фигур) была создана в разумное время. А неделя-10 недель или 20 непринципиально.

bankuss

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

Короче, когда доделаю, то выложу в интернете и 2-ю версию генератора, можно будет скачать по той же ссылке, которую писал в самом первом сообщении. Думаю это будет скоро, в ближайшие недели.

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

короче хороший SSD не помешает генератору. там доступ менее 0.5 мсек.
на крайний случай можно сделать рейд из 2 хороших хардов (страйп) но все равно, до SSD ему, как до луны.

Пока мы спорили вышел процессор нового поколения типа iCore 7 , ну и плата под него, отнюдь не серверная, а демократичная типа 300 евро. Разумеется 24 гига поддерживает. Разумеется и цены вскоре упадут и на маму и ина процессор. По тестам вроде в 2 раза быстрее Коре Экстриме квадро.
Т.е фрицбенчмарк и будет соответственно под 40 000 килонодесов.
Дело осталось за жесткими дисками и развитием технологии записи, основанной на принципах, отличных от магнитных. Там физический предел виден.
p.s. кстати только сейчас заметил, что вся тема не про шахматные эндшпиля, а про генератора котов. Прочитайте внимательнее.
У меня знакомый их разведением занимается, думаю ему будет интересно. В ближайшее время к этой ветке присоединиться.

Генератор котов. ЛОЛ

Винни - только пожалуста не меняй тему - так прикольнее!
ok, не буду - WinPooh

У меня пропала кошка.
А зовут ее Матрешка.
Почему она пропала?
Я ее не обижала!
Только помню как то раз
Выбила я кошке глазю
Вот таким вот кубиком,
Суголком голубеньким....
Почему она пропала?
Я ее не обижала....
Только помню
Как то раз
Положила кошку в таз.
Мыла, терла, полоскала,
Мучила, топила, драла.
А потом сушила.
Кошка сохла, сохла...
А потом взяла и .....
Почему она пропала?
Я ее не обижала!

А если позволите офтоп, то неплохая подборка длиннейших выигрышей в 7-фиг эндшпиле с, Внимание!, включением этих всех 300-500 и более ходов))) http://www.gothicchess.com/javascript_8x8_chess_endings.html
Название сайти симптоматично - действительнго самые что ни на есть готические шахматы)))

готические шахматы это жеесссть)))))
точнее это кошмар

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