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

Тема в разделе "Машинное отделение", создана пользователем Kirr, 18 апр 2011.

  1. WinPooh В.М.

    • Команда форума
    Рег.:
    13.02.2006
    Сообщения:
    9.248
    Симпатии:
    2.558
    Репутация:
    90
    Адрес:
    Москва
    Оффлайн
    Да, но большинство из этих миллионов просто для удовольствия играют в парке на скамеечке, и никакие таблицы им не нужны - ни 7-ми, ни даже 3-4-фигурные.
  2. Skipper_NORTON Учаcтник

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

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

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

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

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

    • Участник
    Рег.:
    14.12.2007
    Сообщения:
    512
    Симпатии:
    1
    Репутация:
    0
    Оффлайн
    Это всё я понимаю... Тут вы, как говорится, в самую точку попали. Единственный способ сделать систему устойчивой к появлению хардварных ошибок (т.е. ошибок компьютерного "железа") - делать дублирование данных, дополнительные проверки и т.п. В рамках генерации одного эндшпиля - это слишком накладно - генератор и так много места на винчестере использует.

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

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

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

    А вычисление всех (тысячу) 7-фигурных будет идти годами.
  4. Igor.Gabrielan Габриелян Игорь Хачатурович

    • Участник
    Рег.:
    24.01.2010
    Сообщения:
    453
    Симпатии:
    211
    Репутация:
    13
    Адрес:
    Харьков
    Оффлайн
    Теоретически начальная позиция может быть даже выигрышной для чёрных. Она может быть каким-то грандиозным цугцвангом. Вот в русских шашках же преимущество имеют чёрные.
    У Налимова рокировка не учитывается как возможный ход :)
  5. Skipper_NORTON Учаcтник

    • Участник
    Рег.:
    14.12.2007
    Сообщения:
    512
    Симпатии:
    1
    Репутация:
    0
    Оффлайн
    Теоретически да, могут и черные быть в выигрышной. Но...
    Не верю © Станиславский.
    :)
    Чем больше фигур на доске, тем менее вероятны позиции с цугцвангом. Для 32 фигур такая вероятность практически равна нулю, ну может что нибудь порядка 0,000000000000000000000000000000001. :)

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

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

    • Участник
    Рег.:
    24.01.2010
    Сообщения:
    453
    Симпатии:
    211
    Репутация:
    13
    Адрес:
    Харьков
    Оффлайн
    Давненько не брал в руки шашек и не читал о них, но, насколько я помню, статистика в них в пользу чёрных.
  7. Fruit Александр

    • Заслуженный
    • Участник
    • Старожил
    Рег.:
    11.02.2006
    Сообщения:
    2.193
    Симпатии:
    49
    Репутация:
    3
    Оффлайн
    Месяцы мучений за черных при игре в адванс навсегда избавляют от таких мыслей. :)
  8. TopicStarter Overlay

    Kirr Администратор

    • Команда форума
    Рег.:
    11.02.2006
    Сообщения:
    1.208
    Симпатии:
    22
    Репутация:
    8
    Оффлайн
    Мне кажется, будущее за комбинацией этих двух подходов. (см, например, Heinz 1999 "Knowledgeable Encoding and Querying of Endgame Databases", ICGA J., 22(2):81-97). Хотя и в чисто табличном подходе я вижу большой потенциал для усиления, и непочатый край работы.
  9. TopicStarter Overlay

    Kirr Администратор

    • Команда форума
    Рег.:
    11.02.2006
    Сообщения:
    1.208
    Симпатии:
    22
    Репутация:
    8
    Оффлайн
    Меньше итераций, меньше свопа на диск и с диска. Таблицы компкатнее (на порядок минимум) -> их проще копировать на другие узлы кластера.

    После стольких повторений уже не смешно про "самую математически сильную игру". Да, игра сильная, только выигрыш иногда упускает. В то время, когда есть метрики, гарантированно не упускающие выигрыш (DTZ50), которые даже проще строить, чем DTM.

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

    Как я уже писал, большое преимущество связки WDL+DTZ (и WDL50+DTZ50) - в том, что можно построить всю семифигурку в WDL (экономя сотни терабайт места), и потом строить интересные таблицы в DTZ. DTM такой оптимизации не позволяет.
  10. Сергей С. Питер Учаcтник

    • Участник
    Рег.:
    31.03.2006
    Сообщения:
    1.193
    Симпатии:
    60
    Репутация:
    11
    Оффлайн
    Наверное с японскими шашками, рендзю перепутал. Там черные начинают :d
  11. TopicStarter Overlay

    Kirr Администратор

    • Команда форума
    Рег.:
    11.02.2006
    Сообщения:
    1.208
    Симпатии:
    22
    Репутация:
    8
    Оффлайн
    С кодом Налимова проблемы в основном две:

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

    2. В том коде сам чёрт ногу сломит. Алгоритмически сложный код не обязательно должен выглядеть как победитель конкурса "Obfuscated C". Любой, даже самый сложный алгоритм может быть закодирован чисто и красиво. Продуманные интерфейсы, грамотное разделение на осмысленные модули, обильные комментарии - это всё необходимые качества нормального проекта. Проекта, который можно поддерживать, и который будут поддерживать после вас.

    Вы, по всей видимости, идёте по стопам Налимова. Я понимаю, что есть некоторый понт в том, чтобы написать код, который никто другой не разберётся, но это ребячество. Кодировать нужно так, чтобы в коде мог разобраться и младенец. В один момент придёт понимание того, что это эффективнее, даже если работаешь над проектом в одиночку. :)
  12. MS Михаил Семионенков

    • Команда форума
    Рег.:
    10.02.2006
    Сообщения:
    6.384
    Симпатии:
    2.495
    Репутация:
    163
    Оффлайн
    Конечно, трудно спорить с человеком, который глубоко в теме, но у меня лично сомнения в большом потенциале таблиц. Конечно, нет смысла отказываться от уже построенных таблиц и не строить то, что можно построить. Но ... 12-фигурник - этот лишь однофигурный эндшпиль с четырьмя пешками, не самое, прямо скажем, кудрявое окончание. А до 12-фигурок я не надеюсь дожить :) . Таблицы нужны не абсолютные, где всё просчитано до конца, а "умные", с данными о практически важных структурах. Ну, мне так кажется. Если под комбинацией понимается это, то я согласен. А вообще интересно будет вернуться к этому вопросу через несколько лет :)
  13. Skipper_NORTON Учаcтник

    • Участник
    Рег.:
    14.12.2007
    Сообщения:
    512
    Симпатии:
    1
    Репутация:
    0
    Оффлайн
    В таком сложном проекте не только младенец не разберется. А даже высококвалифицированный программист.
    Ни у меня, ни у Налимова не было никакого желания запутывать код, чтобы в нем никто не мог разобраться. Не знаю как у Налимова, но у меня написано так, чтобы было наиболее понятно, лично для меня, и у меня не было желания подстраиваться под кого-то. Но если код алгоритмически очень сложный, то как его ни напиши - все равно, начиная с какой-то определенной сложности и размера, люди перестанут понимать, как там оно все работает. Ну не безграничны же способности человеческого мозга! Есть проект, над осмыслением всех оптимизаций, у меня ушло больше года. А вы хотите понять, все что и как там работает, почему именно так а не иначе написано и т.д. - за недельку? Если в проекте 100000 строк кода, не каждый человек вообще сможет понять этот код. И уж если поймет, то затратит на это очень много времени. Поэтому я и уверен, что вряд ли кто-то будет разбираться.
  14. ProstoTak Ветеран

    • Ветеран
    Рег.:
    11.02.2006
    Сообщения:
    5.487
    Симпатии:
    123
    Репутация:
    1
    Оффлайн
    Из личного опыта. Через месяц я уже сам не могу в своем коде разобраться. :D
  15. TopicStarter Overlay

    Kirr Администратор

    • Команда форума
    Рег.:
    11.02.2006
    Сообщения:
    1.208
    Симпатии:
    22
    Репутация:
    8
    Оффлайн
    Да, знаю по себе, насколько это сильный наркотик. :)
  16. TopicStarter Overlay

    Kirr Администратор

    • Команда форума
    Рег.:
    11.02.2006
    Сообщения:
    1.208
    Симпатии:
    22
    Репутация:
    8
    Оффлайн
    Да, интересно будет вернуться. Я пока что работаю работаю над улучшением обычных "тупых" таблиц, в частности над совершенствованием сжатия. Согласен что просчитанность до конца нужна не всегда, вопрос в том как оставить важную информацию и выбросить менее важную.
  17. SkySandy Александр

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

    • Участник
    Рег.:
    14.12.2007
    Сообщения:
    512
    Симпатии:
    1
    Репутация:
    0
    Оффлайн
    Как я уже писал в параллельной теме, последнюю версию моего эндшпильного генератора можно скачать здесь

    http://generatorchess.com/
  19. Magystr Новичок

    • Новичок
    Рег.:
    19.04.2011
    Сообщения:
    62
    Симпатии:
    14
    Репутация:
    2
    Оффлайн
    Всем привет!
    Хотел бы поделиться некоторыми идеями по поводу построения и использования эндшпильных баз.

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

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

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

    Kirr Администратор

    • Команда форума
    Рег.:
    11.02.2006
    Сообщения:
    1.208
    Симпатии:
    22
    Репутация:
    8
    Оффлайн
    Очень приятно видеть свежие мысли и подходы, да и вообще интерес к проблеме генерации и хранения таблиц. Несколько комментариев:

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

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

    Классическая идея - решать и хранить эндшпиль целиком. Альтернативный подход - считать фрагмент эндшпиля, ограниченный, например, блокированными пешками - применяется в программе Freezer. Также, H.G. Muller долгое время пропогандирует генерацию необходимых эндшпилей во время партии, по мере надобности. Фундаментальное ограничение этих подходов - время, необходимое на то, чтобы полноценно просчитать более-менее интересный эндшпиль, обычно превышает продолжительность одной партии на порядки.

    Пока что не вижу идею, вижу мечту "качественно и быстро просчитать одну позицию". Если бы можно было быстро просчитать одну позицию, то и таблицы были бы не нужны.

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

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

    Генератор как правило тратит гораздо меньше 10 секунд, и даже секунды, на решение одной позиции.

    Пожалуйста, продолжайте исследования и творческий процесс!
  21. Magystr Новичок

    • Новичок
    Рег.:
    19.04.2011
    Сообщения:
    62
    Симпатии:
    14
    Репутация:
    2
    Оффлайн
    Прежде всего хочу поблагодарить специалиста за конструктивную критику.

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

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

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

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

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

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

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

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

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

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

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

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

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


    Пока так...
  22. bankuss Александр

    • Заслуженный
    • Участник
    • Старожил
    Рег.:
    23.05.2006
    Сообщения:
    1.073
    Симпатии:
    33
    Репутация:
    1
    Оффлайн
    предлагаете делать битбазы? в них нет хода, а только данные о результате, т.е. 1-0 0-1 или 1\2.
    размеры таких баз в разы меньше полных.

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

    Kirr Администратор

    • Команда форума
    Рег.:
    11.02.2006
    Сообщения:
    1.208
    Симпатии:
    22
    Репутация:
    8
    Оффлайн
    Не совсем понятна идея. При построении таблиц, как вы отметили, мы продвигаемся от конца к началу (от коротких выигрышей к длинным). Обычно именно короткие выигрыши являются тривиальными (с точки зрения движка). Если мы на них прерываем процесс, то мы никогда не доходим до нетривиальных, длинных выигрышей. То есть, при построении мы продвигаемся от простых позиций к сложным. Прервать построение в любой точке - означает оставить сложные позиции нерешёнными.
  24. Magystr Новичок

    • Новичок
    Рег.:
    19.04.2011
    Сообщения:
    62
    Симпатии:
    14
    Репутация:
    2
    Оффлайн
    bankuss'у:

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

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

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

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

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

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

    Kirr Администратор

    • Команда форума
    Рег.:
    11.02.2006
    Сообщения:
    1.208
    Симпатии:
    22
    Репутация:
    8
    Оффлайн
    Много идей. Нужна, наверное, какая-то демонстрация, чтобы понять, какие из них рабочие, какие - нет. Я свои идеи тестирую на мини-шахматах, но можно на чём угодно тестировать, хоть на крестиках ноликах. Потому что часто так бывает, что идея звучит хорошо, но оказывается нереализуемой или непрактичной.

    Ни в одном из известных мне форматов таблиц никто не хранит лучший ход. Если эта идея рабочая, то это будет интересный новый шаг.
  26. Magystr Новичок

    • Новичок
    Рег.:
    19.04.2011
    Сообщения:
    62
    Симпатии:
    14
    Репутация:
    2
    Оффлайн
    Да, я с Вами согласен. Пока все на уровне идей.
    Когда это все оформится во что-нибудь реальное - можно будет и попробовать.

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

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

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

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

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

    • Новичок
    Рег.:
    19.04.2011
    Сообщения:
    62
    Симпатии:
    14
    Репутация:
    2
    Оффлайн
    А вообще где-то можно почитать про формат, структуру баз Налимова?
  28. TopicStarter Overlay

    Kirr Администратор

    • Команда форума
    Рег.:
    11.02.2006
    Сообщения:
    1.208
    Симпатии:
    22
    Репутация:
    8
    Оффлайн
    Здесь. (Нужно кликнуть на "PDF").
  29. Magystr Новичок

    • Новичок
    Рег.:
    19.04.2011
    Сообщения:
    62
    Симпатии:
    14
    Репутация:
    2
    Оффлайн
    Спасибо.

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

    • Новичок
    Рег.:
    19.04.2011
    Сообщения:
    62
    Симпатии:
    14
    Репутация:
    2
    Оффлайн
    А еще вопрос, чтобы оценить время работы и предполагаемый размер таблиц.
    Известно ли точное (или приближенное) общее количество всех легальных позиций для 3-х, 4-х, 5-ти и 6-ти фигурок?
  31. TopicStarter Overlay

    Kirr Администратор

    • Команда форума
    Рег.:
    11.02.2006
    Сообщения:
    1.208
    Симпатии:
    22
    Репутация:
    8
    Оффлайн
    Это как раз ключевая статья о формате Налимова. Там описано самое главное - способ индексирования позиций. То есть, как хранить информацию о позициях (расстояние до мата), не храня сами позиции.

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

    Недавно Skipper_NORTON писал, что в шахматах 8х8 в 3-х фигурке 372,162 позиции, в Налимовском формате. Это не число уникальных легальных позиций, а чуть завышенное, так как некоторые позиции посчитаны дважды. 3-фигурка Налимова занимает 63,982 байта, поэтому её плотность составляет 5.82 легальных позиций на байт. Это то, что мы здесь пытаемся сделать существенно компактнее.
  32. Magystr Новичок

    • Новичок
    Рег.:
    19.04.2011
    Сообщения:
    62
    Симпатии:
    14
    Репутация:
    2
    Оффлайн
    Извините, что отвечаю далеко не сразу.
    Я пока не очень хорошо владею терминологией, которая тут регулярно используется.
    Да, я веду речь о тех самых битбазах, дополненных одним единственным полем - сильнейший ход в данной позиции.
    Таким образом мы ход за ходом сможем выстроить кратчайший путь к цели.
  33. MS Михаил Семионенков

    • Команда форума
    Рег.:
    10.02.2006
    Сообщения:
    6.384
    Симпатии:
    2.495
    Репутация:
    163
    Оффлайн
    На этом месте споткнулся. У каждой позиции - 3 возможные оценки, в один байт (2**8 = 256) можно запихнуть чуть больше 5 оценок (3**5 = 243). Как удалось выйти на уровень почти 6? И с чем связаны надежды, что это можно существенно улучшить? Большее сжатие достижимо, как мне кажется, только на совершенно иных принципах, когда из таблицы достаётся не результат, а нечто для дополнительного счёта.
  34. Magystr Новичок

    • Новичок
    Рег.:
    19.04.2011
    Сообщения:
    62
    Симпатии:
    14
    Репутация:
    2
    Оффлайн
    Kirr'у

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

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

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

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

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

    • Команда форума
    Рег.:
    04.02.2006
    Сообщения:
    52.221
    Симпатии:
    13.414
    Репутация:
    515
    Адрес:
    Москва, Россия
    Оффлайн
    Звучит разумно. Нынешние тотальные базы стоит назвать базами для чайников.
    С помощью урезания банальных поз и добавления новых актуальных можно создать более полезные, более компактные и, возможно, более глубокие базы для опытных... чайников. :)

Поделиться этой страницей