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

Нет DTZ в шашках. В шашках используют безранговые базы (во всяком случае я испльзую безранговые базы WildCat-а)
А DTZ - алгоритм выигрыша в безранговых базах - перебором находит кратчайший выигрыш по DTZ. Можно его модифицировать, что если может досчитаться, то считает по DTM, если не может, то по DTZ, а если и до этого не досчитывается, то считает по ОФ повыигранным позициям согласно ЭБ.

Игровые программы шахмат используют DTM, Налимова, и это было самое лучшее решение. Если бы их не было, а были всякие DTZ, DTC, то шахматистам скорее всего не понравилась бы такая "игра", похожая на убожество, не было бы красивых эффектых решений и т.д. И базы не были бы настолько популярны. Нужно все таки задумываться о том, что мы оставим потомкам. Захотят ли они развивать идею, создавать 8-9-10-фигурные и т.д. базы.

NS

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

В корне с битбазами не выиграешь. Все равно понадобится DTM, так зачем еще дополнительно битбазы держать, чтобы они место занимали? Все равно они полностью в память не грузятся, приходится обращаться к винчестеру в переборе. Кстати, моя программа быстро обращается, будь даже все 7-фигурные на винчестерах построены (неважно, битбазы или DTM) - ничего там долго грузиться не будет. Авторитетно заявляю. Так что если построить мои 7-фигурные базы - то можно их все использовать в переборе без какого-либо торможения программы (по сравнению с 6-фигурными).

Я вообще не понимаю, почему производители движков и Налимов - сделали так, что у них эти базы долго грузятся, если их много. Хотя и подозреваю, почему...

Вы похоже меня в упор не слышите.
1. Битбазы (безранговые) занимают меньше места.
2. Они помещаются в оперативную память (а как известно она "немного" быстрее)
3. Безранговых в шашках достаточно чтоб программа никогда не выпускала выигрыша в выигранных по ЭБ позициях.
Какой к черту DTM? :/

При расчетах, по битбазе - намного ближе считать до продвижения простой или взятия (DTZ на лету), до мата в большинстве позиций не досчитаться. До изменения ранга то досчитываемся далеко не всегда, но тут помогает ОФ при поддержке битбаз.

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

Добрый день. Запал я на это дело даже стал немного разбираться.

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

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


И еше вопрос к NS не по теме. Как там в шашках ? Когда 100 клеточные решат ? Можно ссылку на соответствующий форум.

Из популярных не решен пока ни один вид "классических" шашек даже на доске 8x8.
Крупнейший русскоязычный шашечный форум - shashki.com

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

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

Если в шашках безранговые битбазы помещаются в память, согласен, это хорошо. Но 7-фигурные, и даже 6-фигурные WDL, НЕ ПОМЕСТЯТСЯ в память. Не все ли равно, 0,01% позиций в памяти висит DTM, или 0,05% позиций WDL? в подавляющем большинстве случаев программе придется обращаться к диску. Из-за такой ничтожной разницы не вижу необходимости хранить еще и WDL, если есть DTM. Если нет возможности хранить DTM - тогда согласен - WDL лучший вариант! Для перебора. Но программа может не выиграть, если позиция будет в корне. Некоторые программы (Чессмастер) умудрялись не выиграть KQ-KR, ферзь против ладьи, а ведь все ходы которые они делали - приводили к выигрышным позициям, т.е. то же самое было бы если бы программы знали по WDL, что это "выигрышные" ходы, а какие выбирать непонятно.

А там много еще решать? Много вариантов не проанализировал Chinook?)

MS, чтобы посчитать все 7-фигурные, нужно примерно 200 тысяч долларов на компьютерные мощности, и даже с такими - придется считать ~ 3 года. У меня нет таких средств Какая квартира? Зачем вы мне миллионерское будущее предлагаете? Когда нибудь я их посчитаю, т.к. прогресс идет, и производительности компьютеров растут. Т.е. это будет дешевле. Сколько можно денег заработать когда такие базы будут, я не знаю, но вот по себе сужу - если бы существовал сайт, позволяющий обратиться к 7-фигурным базам, и анализировать любые 7-фигурные позиции, то 20 долларов я не пожалел бы чтобы там зарегистрироваться и пользоваться им (если бы сайт был платным). А вам было бы жалко 20 долларов?

По вашему не набралось бы 10 тысяч шахматистов (если бы такой сайт был разрекламирован и все шахматисты про него знали бы) во всем мире, чтобы пользоваться таким сайтом? Да 10 тысяч - только одних мастеров спорта наберется во всем мире, не говоря уже про разрядников и всяких любителей. (10 тысяч умножить на 20 долларов. вот и вернули вы свои 200 тысяч.)

Вы явно недооцениваете количество людей, интересующихся шахматами.

Kirr, если локально хранить полезные, типа 7_KRPP-KRP, это уже намного усилит игру программ в эндшпиле.

Kirr, а вы сами пробовали строить WDL, с нуля, а не конвертируя их из других метрик? Если пробовали, то скажите, во сколько раз они у вас быстрее строятся, чем в других метриках? В своих шахматах 4х4

WildCat, я отлично понимаю, что вы хотите сказать. Конечно, в переборе, на самых нижних "листях" (кто знаком с теорией алгоритмов, поймет) - можно уже и не пользоваться базами. Чтобы не лезть на винчестер очень уж часто. Но если программа по этой ветке - намерена перебрать еще в глубину, скажем на 5 полуходов, то уже лучше 1 раз обратиться к базам на винчестере (кстати, она часто будет при этом попадать в кэшированные участки - тогда запрос пойдет в память, либо в кэш винчестера - и это будет намного быстрее). Получив точную оценку, мы углублятьcя уже не должны. а иначе нам надо было бы еще глубже перебирать десятки или сотни тысяч позиций, ИЗ ДАННОЙ, что в результате было бы медленнее. Не знаю как в других программах, но в своей я настроил разумно - она обращается к базам в переборе и от этого только польза.

Это потому что часто сдаются не доиграв до малофигурного эндшпиля. Если будем разыгрывать 10-фигурные позиции и часто попадать в эти эндшпили, то программа с 5-фигурной WDL с треском проиграет в матче против программы с любой 7-фигурной. Программы, имеющие доступ к 7-фигурной базе, намного лучше будут понимать эндшпиль.
Не надо это недооценивать. А если попали в позицию где трудно выиграть - то вклад таблиц будет вообще существенным! Великий Чессмастер без таблиц не смог выиграть даже 4-фигурный KQ-KR. Ферзь против ладьи.
Это меня просто поразило в свое время... А если у нас ладья с 2-мя пешками против ладьи с 1 пешкой? И до мата 100 ходов.

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

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

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

Не понял, что вы имеете в виду.

Хорошо, я обратился к 7-фигурным базам на винчестере, в позиции, на глубине 1 от корня. И получил оценку позиции за несколько миллисекунд. Глубже ничего копать не надо. Если бы баз не было - программа ушла бы в перебор и за те же миллисекунды перебрала бы все позиции + обратилась бы ко всем возникающим ниже 5-фигурным битбазам в памяти - на глубину ДО 20 полуходов??

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

С 7-фигурными не проводили таких тестов, т.к. они еще не созданы.
А от 5-фигурных толку мало, да. В большинстве случаев программа получит преимущество РАНЬШЕ, и потому сможет выиграть легко и без баз. А вот если уже 7-фигурные есть - это ощутимый эффект. Будет у вас позиция, скажем
7_KRPP-KRP, ладья и 2 пешки против ладьи и 1 пешки , и программа без баз ее не выиграет, и программа с 5-фигурными ее не выиграет. А выиграет только если есть 7-фигурные. (4-й фигурный ферзь против ладьи неспособны выиграть даже)

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

Насчет скорости обращения к винчестеру и скорости чтения - есть прогрессивные SSD-винчестеры, с ними будет еще быстрее.

Зато 7 фигурки дадут новый вклад в теорию эндшпилей, думаю для исследования шахмат это будет интересно.

Да, правильно. Но на самом деле разница не в миллион раз, а несколько меньше, поэтому успеет посчитать примерно на 10-15 полуходов за это-же время.

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

преувеличиваете... (даже для старых HDD).

а для SSD преувеличиваете сильно

Для совсем новых - 8.5 - это очень хороший результат. Так что 10 мс.
Возьмите Любой файл на Терабайт, и сделайте тест случайного доступа. И увидите результат.

В случае больших ЭБ (например полная шестифигурка) - Кеш, и чтение блоками - практически не дают никакого выигрыша. и разница получается - доступ к диску - 10 мс. (100 позиций в секунду), доступ к памяти - соскоростью перебора. На среднем компе порядка 10 миллион позиций в секунду. Разница в 100 000 раз.
Допустим виндовый кеш, эндшпильный кеш движка, блочное чтение и скорректирует разницу, но на больших базах, и с большим числом обращений - выигрыш будет очень маленький.

http://www.ixbt.com/portopc/hdd-ssd-1.shtml
В этом сравнении есть тоже время случайного доступа.
Насчет SSD похоже на шутку, даже чтоб хранить полную шестифигурку на SSD нужно быть весьма состоятельным человеком.