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

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

  1. MS Михаил Семионенков

    • Команда форума
    Рег.:
    10.02.2006
    Сообщения:
    6.390
    Симпатии:
    2.507
    Репутация:
    163
    Оффлайн
    "Выкидывание" - это забавно :)
    Фокус в том, выигрыш будет невелик. Сейчас на позицию тратится полтора бита. При выбрасывании 1 бит придётся потратить для каждой позиции на то, чтобы сообщить, вырожденная позиция или нет. Потом ещё бит - для оставшихся 25 процентов. Для ста позиций - 125 битов. Исходно - 150. Экономия меньше 20 процентов. Кое-что, но не в разы.
  2. TopicStarter Overlay

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

    • Команда форума
    Рег.:
    11.02.2006
    Сообщения:
    1.208
    Симпатии:
    22
    Репутация:
    8
    Оффлайн
    На самом деле всё ещё запущеннее, так как в стандартном формате Налимова хранятся не 3 возможные оценки, а расстояние до мата (DTM). Компактность достигается сжатием. Возьмём, к примеру, окончание knk, в котором 54926 легальных позиций (считая по Налимову). Допустим, мы тратим минимум 1 байт (как Налимов) для хранения DTM. Тогда для хранения всей таблицы knk нам потребовалось бы 54926 байт. Вместо этого можно было бы заметить, что мы храним одни ничьи, и записать просто значение для ничьей (допустим, 0) - 1 байт, и число повторений (54926), на которое, предположим, мы потратили 4 байта. В итоге получаем 5 байт. То есть 54926 позиций можно сохранить в 5 байтах, получая компкатность = 10985 позиций на байт. :)

  3. TopicStarter Overlay

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

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

    Не хочу остужать энтузиазм, но примерно так это для меня звучит. :)

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

    А по существу, как я уже упомянул, нужна демонстрация. Чем раньше вы начнёте пробовать, тем раньше встретитесь с реальностью, где маленькие сложности способны испортить большую идиллию. :)
  4. Magystr Новичок

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

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

    И что делать?
    Опять же нужно сначала ПОСЧИТАТЬ плюсы и минусы, сделать выводы и если есть возможность теоретического выигрыша ХОТЯ БЫ ПРИ КАКИХ-ТО УСЛОВИЯХ, делать опытный образец, вкладывая в него существенные средства.

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

    Я буду этим заниматься, когда (и если) пойму, что я получу на выходе.

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

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

    Ну и опять же, я предлагаю свои идеи всем желающим. Не обязательно, если я ими воспользуюсь сам. В настоящее время я достаточно сильно занят более самоокупаемыми проектами.
  5. miptus Заслуженный

    • Заслуженный
    • Участник
    Рег.:
    11.02.2006
    Сообщения:
    1.159
    Симпатии:
    78
    Репутация:
    5
    Оффлайн
    Вам не предлагают срочно заняться разработкой, а предлагают оценить эффект на простом случае, например шахмат 3х3 или трехфигурок в шахматах 8х8. Тут не надо годами думать, можно применить идею и быстро посмотреть на результат. Вы думаете, никому не приходило в голову "выбросить" все позиции с оценкой +10? Вопрос как это сделать, тут главное реализация, а не идея.
  6. TopicStarter Overlay

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

    • Команда форума
    Рег.:
    11.02.2006
    Сообщения:
    1.208
    Симпатии:
    22
    Репутация:
    8
    Оффлайн
    Конечно же, как уже сказал miptus, речь об упрощённой модели. Именно для того, чтобы вы сами смогли "ПОСЧИТАТЬ и ОЦЕНИТЬ" выигрыш. Как иначе вы собрались его оценивать? А главным образом - для того, чтобы вы ближе познакомились реальностью построения таблиц, так как без этого любые мысленные эксперименты бесполезны. Это как я бы сейчас стал с нуля проектировать у себя в голове гоночный болид. Даже если бы я не настаивал на использовании квадратных колёс, какая польза была бы от моих идей реальному болидостроению?

    Шахматная 3-х или 4-х фигурка была бы вполне подходящей моделью. Достаточно небольшая, чтобы просчитать и сохранить в любом вообразимом формате. В процессе вы бы увидели, на что и сколько расходуется памяти, какие операции занимают больше всего времени, сколько нужно работать с диском, и т.д. Посмотрев на эти цифры и на число позиций в 6 и 7-фигурке вы бы легко отделили мечты от реальности, поняли бы какие направления перспективны, какие - нет.

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

    В итоге имеем: 1. Горячее желание осуществить прорыв (выданное за оригинальное, но у кого нет такого желания?) 2. Демонстративное отбрасывание опыта предыдущих поколений (все дураки, сидите в тупике). 3. Нежелание что-то пробовать (я буду генерировать идеи, а вы проверяйте). Может быть, конечно, я что-то недопонял.

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

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

    Берем ВСЕ окончания "Король и Конь против Короля", "Король и Слон против короля" и просто удаляем эти файлы.
    Как отсутствие этих таблиц повлияет на результат ЛЮБОГО окончания?
    Приведите хоть один один пример того, когда наличие или отсутствие этих таблиц повлияет на результат или расчет, оценку позиции.

    Далее чуть-чуть сложнее.
    "Король и Ферзь против Короля".
    Выбрали все позиции, где получается ничья.
    Из легальных - это всего два типа. Либо пат, либо на ПЕРВОМ-же ходу бьется ферзь.
    Оставили эти позиции в таблице.
    ВСЕ ОСТАЛЬНЫЕ УДАЛИЛИ.
    Вместо них создали ОДНУ служебную запись - любая другая позиция, кроме тех, что оставили - это мат в 5 ходов.

    Как это повлияет на РЕЗУЛЬТАТ, на КАЧЕСТВО АНАЛИЗА и на СКОРОСТЬ?
    Да никак. Все будет то же самое.

    "Король и Ладья против Короля".
    Все аналогично предыдущему.

    И наконец "Король и пешка против Короля".
    Также оставляем все ничейные позиции.
    Оставляем все позиции, где выигрыш достигается более чем за 15 ходов. И то только на тот случай, если у нас слабенький комп и мы сомневаемся, что он упустит выигрыш в такой позиции. Во что я не верю. Но это для скептиков.
    Для всех остальных выигрышных позиций создаем одну СЛУЖЕБНУЮ запись - мат в 10 ходов.

    Можно не создавать, можно по отсутствию такой записи на запрос движка давать соответствующий одинаковый ответ.

    Итак, что имеем в итоге.
    У нас остались сильно урезанные (процентов на 95) окончания "К+Ф против К" и "К+Л против К" и серьезно уменьшенный (в 2 раза или даже более) файл "К+п против К".
    На ЛЮБОЙ запрос движка эти СОКРАЩЕННЫЕ таблицы дадут правильный ответ ЗА ТО ЖЕ САМОЕ ВРЕМЯ , любой выигранный эндшпиль движок доведет до победы, любой ничейный - соответственно завершит вничью.

    Теперь попрошу всех скептиков привести ХОТЬ ОДИН пример, когда это не будет работать.

    Реальное сокращение размера я бы оценил примерно в 4 раза. Причем, если для окончания "К+п против К" границу провести на уровне 20 ходов до мата, то сократятся раз в 6-8.

    Если тут вопросов нет - перейдем дальше к четырехфигуркам.....
  8. Magystr Новичок

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

    Большая к Вам просьба.
    Не приписывайте мне мысли, которых я не высказывал.
    Если то, что я пишу, Вам не интересно - я не обижусь, если Вы это оставите без комментариев.
  9. TopicStarter Overlay

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

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

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

    Вот, уже интересно. Вопросы:

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

    2. "позиция+оценка+ход" занимает N байт, в то время, как DTM (и тем более WDL) - меньше байта. Не берусь на глаз оценить разницу в окончательных размерах таблиц.

    3. В kqk человек, допустим, может понять, что ферзь должен быть взят на первом ходу. Но что делать с более сложными, 4-фигурными эндшпилями? Придётся решать целиком?

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

  10. Magystr Новичок

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

    Как-то достаточно давно решил написать программу для одного из видов логических игр. Поскольку, в отличие от шахмат, в ней число ходов строго ограничено и конечно (хотя и огромно), то возникла идея составить своего рода таблицы Налимова для нее. Тем более, что при соответствующих мощностях и времени вполне реально получить полные таблицы от начала и до конца игры.
    Потому с подобного рода задачей знаком не по наслышке.
    Таблицы использовал стандартные (MySql, Pervasive, Oracle).
    В процессе реализации возникали те или иные проблемы, рождались некие идеи, частью из них воспользовался, часть из них реализовал, часть по разным причинам осталась нереализованной.
  11. MS Михаил Семионенков

    • Команда форума
    Рег.:
    10.02.2006
    Сообщения:
    6.390
    Симпатии:
    2.507
    Репутация:
    163
    Оффлайн
    Вполне логично. Только прежде чем идти к четырёхфигуркам, неплохо иметь более серьёзную оценку выигрыша. Я думаю, что в налимовских трёхфигурках тоже львиная доля (хорошо за 90 процентов) уходит на KPk, поскольку остальные эндшпили ужаты до безобразия. Хочется "пощупать" результат.
  12. Crest Админ, МГ

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

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

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

    Примерно прикинул, размер одной записи.
    6 бит * N + 2 бит * (N-2) - положение на доске. (Непосредственно положение фигур на доске и указание, что за фигура. Первые две соответственно белый и черный король, для остальных нужно указать, что за фигура)
    1 бит - очередь хода
    2 бит - результат
    2 бит - оценка
    Для трехфигурок - это 3-4 байта (грубая оценка).
    Плюс наверное 1 байт - хранение ключа (не исследовал)
    Соответственно, если хранить в 3-х фигурках, как я описал, выше примерно 30 тысяч позиций, получается примерно 120 Кб.
    Но у меня есть серьезные подозрения, что каждое увеличение на 1 фигуру будет приводить к росту таблицы примерно в 50-60 раз, не более.
    У Налимова сейчас получается вроде бы примерно 200.

    По индексу (ключу) необходимая запись ищется МОМЕНТАЛЬНО не зависимо от количества записей в таблице.
    Если индекс не задан, то действительно осуществляется полное "перелистывание" таблиц.

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

    Надеюсь по трехфигуркам не осталось принципиальных вопросов.
    Тогда я наверное завтра попробую провести подобный анализ для 4-х фигурок.
  14. Magystr Новичок

    • Новичок
    Рег.:
    19.04.2011
    Сообщения:
    62
    Симпатии:
    14
    Репутация:
    2
    Оффлайн
    Налимовские 3-х фигурные базы 69 кБт. Из них с пешкой - 35 кБт. Половина
  15. Осипов Юрий Учаcтник

    • Участник
    Рег.:
    18.06.2007
    Сообщения:
    388
    Симпатии:
    394
    Репутация:
    11
    Адрес:
    Правда
    Оффлайн
    Есть еще один источник информации, где можно посмотреть реализацию баз KPK. Правда, боюсь, что Кириллу это может не понравиться.
    Речь о нашумевших в недавнем прошлом Ипполитах. Базы KPK встроены в исходный текст в виде массивов, правда остается непонятным, как они были получены. Можно попробовать побаловаться с этими массивами и попробовать отсечь от них все лишнее. Как их тогда индексировать - непонятно. Придется подумать о другом способе их представления.
  16. Magystr Новичок

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

    А принципиально это может быть реализовано на базе одного файла *.dll
    То есть библиотека принимает определенный запрос, обрабатывает и перенаправляет его в соответствующую таблицу, моментально получает ответ и готовый результат отдает движку.

    Хотя в большинстве случаев можно встроиться в уже существующий протокол обмена. В этом случае движку все равно от каких баз он получил ответ.
  17. Magystr Новичок

    • Новичок
    Рег.:
    19.04.2011
    Сообщения:
    62
    Симпатии:
    14
    Репутация:
    2
    Оффлайн
    Ну мне как раз понятно, как построить любую базу.
    Составляется полная таблица всех возможных позиций. Простым перебором.
    Далее составляются цепочки ходов, ведущие от одной позиции к другой до мата или перехода в младший эндшпиль с известным результатом. Потом из всех цепочек отсекаем по альфа-бета критерию худшие ходы. Метод мини-макс (правильнее макси-мин). Таким образом для любой позиции находим оптимальный вариант за обе стороны (цепочку) и переносим оценку конечной позиции на все промежуточные и исходную. В этот момент в промежуточных СЛУЖЕБНЫХ таблицах можно хранить и данные по количеству ходов до мата (для упрощения процесса генерации). В конечных таблицах (пользовательских) я считаю эту информацию избыточной.
    Далее по некоему критерию удаляем из таблицы все записи, где выигрыш достигается легко (а таких позиций обычно будет много). Получили компактную таблицу для определенного вида эндшпиля.
    Все это, как я предполагаю, примерно также делается и у Налимова. Кроме последнего действия - удаления позиций с очевидным для движка (да и для человека) решением.
    Оптимально было еще ДО ПОСТРОЕНИЯ этих цепочек удалить лишние записи. Но вот по какому критерию их удалять - пока не очень понятно.
    Один из вариантов - дать эти все позиции оценить какому-то движку и удалить сразу те, которые он гарантировано доведет до победы.
    Но возможно, что движок потратит не меньше времени на оценку всех позиций, чем мы, строя цепочки.
    Но уж по крайней мере размер усеченной таблицы должен быть заведомо меньшей, чем полной.

    Если привлечь специалиста по хранению информации в базах данных, может он предложит более компактный способ хранения усеченного файла, чем в обычных СТАНДАРТНЫХ профессиональных форматах, которыми я пользуюсь.

    У меня подобных задач никогда не было. С объемами в 50-100 миллионов записей работал. Там проблем компактности хранения не возникало. Скорее задача ставилась в гарантированной корректности записи на диск, хранения и отображения информации, независимо от объема.
  18. Magystr Новичок

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

    • Команда форума
    Рег.:
    10.02.2006
    Сообщения:
    6.390
    Симпатии:
    2.507
    Репутация:
    163
    Оффлайн
    УжОс :|
    Вот до чего доводит принципиальность :)
    Конечно, трёхфигурки никакого интереса не представляют: если не держаться за принцип полной таблицы, то всё стоит копейки.

    Представим эндшпиль не таблицей, а процедурой. K(B/N)k будут возвращать ничью, K(Q/R)k - результат, базирующийся на простеньком анализе, KPk будет возвращать результат на основе небольшого анализа на уровне третьеразрядника: за все про всё код будет стоить от силы несколько килобайт. А играющая программа, если дойдёт до позиции, сама досчитает до мата или перехода в другую таблицу.

    Самое время возвращаться к теме, т.е. семифигуркам.

    6-фигурки будут представлены процедурой доступа к Налимову.
    Заведём процедуру, которая для семифигурок с большим перевесом
    работает по принципу K(Q/R)k - т.е. за несколько полуходов убеждается, что пата нет и решающий перевес можно сохранить. Плюс выкидываем всю абракадабру. Из тысячи эндшпилей останется, наверное, несколько процентов.
    Посмотрим что-то содержательное, KRPPkrp.
    Здесь здорово ужаться за счёт знаний или коротенького анализа не удастся.
    Путь до мата или перехода к следующим таблицам может быть слишком долгим.
    И тут опять есть спрос на таблицы.
    Можно попробовать разбить эндшпиль на 6(число горизонталей пешки)*6*6 = 216 подэндшпилей.
    Теперь у играющей программы есть шанс добраться до младшего эндшпиля или мата, поскольку подэншпили отделяются всего одним пешечным ходом.
    Если мы потратим 1.5 бита на позицию (т.е. хранить только результат), то это, думаю, не уступит Налимову. Шкипер, конечно, знает точную оценку.
  20. Magystr Новичок

    • Новичок
    Рег.:
    19.04.2011
    Сообщения:
    62
    Симпатии:
    14
    Репутация:
    2
    Оффлайн
    Вот кстати очень интересный и правильный подход - разбить большую задачу на несколько маленьких.
    И параллельно решается проблема пресловутых 50-ти ходов. Если в пределах такого подэндшпиля укладываемся в 50 ходов, то нет необходимости проверять всю цепочку из всех этих подэндшпилей.
    Тут опять же время генерации будет существенно сокращено. Если выстроена победная цепочка предположим из 45-ти ходов, то нет необходимости искать улучшения за сильнейшую сторону. А значит количество вычислений до оценки позиции снижается очень существенно.
    В нашем прикладном случае мы не обязуемся (зачем?) выиграть выигранную позицию за минимально возможное количество ходов. Нам достаточно уложиться в правило 50-ти ходов и не упустить при этом победу. Вполне рациональный подход.

    Да и в целом идея очень интересная о которой думаю мало кто задумывался (для меня она в новинку).
    Подразделять компьютерные эндшпили не по количеству фигур, а по неким другим важным факторам.
    При этом в определенного вида интересных эндшпилях можно продвинуться до 8-ми, 9-ти фигур и выше, оставив пока не обсчитанными скажем 7-ми фигурки с лишней фигурой.
  21. Magystr Новичок

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

    Вот сейчас к примеру невозможно начать считать эндшпиль КРkp, пока не обсчитаны все переходы в другие эндшпили с превращениями в разные фигуры. Итого, мы должны предварительно посчитать 16 разных эндшпилей.

    Берем выше упомянутый KRPPkrp (Ладья и две пешки против ладьи с пешкой)

    Исходя из опыта и знаний (может быть беглого анализа) делаем вывод, что превращение пешки всегда должно быть в Ферзя. Или в Коня, ЕСЛИ ОН СТАВИТСЯ С ШАХОМ. (Превращения в ладью и слона с переходом в соответствующие эндшпили воообще и не пытаемся рассмотреть.)
    Значит нам нужно иметь предварительно всего 4 расчета, причем для превращения в ферзя такой расчет будет очень быстрым. Если за пару форсированных ходов ферзь (или ладья) не съедается, то очевидно это выиграно. А если съедается - переходим в ранее обсчитанный младший эндшпиль.
    Правда тут я немного не прав. Другая сторона тоже может поставить ферзя и этот эндшпиль потребует большого обсчета.
    Но ведь это и сам по себе интересный эндшпиль Ф+Л+п против Ф+Л.
    У Налимова сейчас предварительно нужно обсчитать 4*4*4 = 64 эндшпиля, большинство из которых практической ценности несут мало.
  22. MS Михаил Семионенков

    • Команда форума
    Рег.:
    10.02.2006
    Сообщения:
    6.390
    Симпатии:
    2.507
    Репутация:
    163
    Оффлайн
    Спасибо Kirr"у, за поддержание огня, и Magystr"у, всколыхнувшему дискуссию: удалось придать завершённую форму некоторым идеям.

    Создание генератора меня не интересует, а вот "Crestbook-подход" сформулирую и "запатентую". Может, кому и приглянется для реализации.

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

    Требования к игровой программе.

    1. Программа должна распаковать требуемые таблицы при первом обращении к ним.
    2. На программу возлагается необходимость отслеживать "прогресс": непрерывное уменьшение числа ходов до цели. Под целью понимается мат или переход в другую таблицу с сохранением оценки позиции.
    3. Продвижение пешки приравнивается к переходу в другую таблицу.

    Вот, собственно, и всё :)
  23. Андрей Г. Андрей Гуревич

    • Новичок
    Рег.:
    11.07.2007
    Сообщения:
    53
    Симпатии:
    23
    Репутация:
    1
    Адрес:
    Москва
    Оффлайн
    Можно выкинуть позиции с нулевой оценкой - отсутствие в таблицах и будет означать нуль. Прошу выдать мне авторское свидетельство.

    Еще вдвое сократить размер можно, выкинув позиции с отрицательной оценкой, но это будет означать два обращения к таблицам вместо одного. Если это не страшно, прошу выдать мне второе авторское свидетельство.
  24. TopicStarter Overlay

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

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

    Вообще, таблицы Налимова (и Нортона) - это совсем не эталон компкатности, так как хранят неэффективные DTM, вместо WDL/DTZ, или чего-нибудь ещё более прогрессивного. Скорее таблицы Налимова - хорошая "нижняя" планка для оценки альтернативных подходов.

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

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

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

    И потом, что такое "МОМЕНТАЛЬНО"? O(1)? Или, всё-таки O(log(N))? (Где N - число позиций в таблице).

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

    Прежде, чем переходить к 4-фигуркам, интересно было бы прикинуть, сколько байт в вашем формате займёт kpk?
  25. Killster Учаcтник

    • Участник
    Рег.:
    12.05.2011
    Сообщения:
    75
    Симпатии:
    0
    Репутация:
    0
    Оффлайн
    Еще одну идейку вам подкину - можно попробовать создать алгоритм хеширования каждой позиции (лучше как-то плясать от битборд), один раз проверить уникальность, и дальше уже находить позицию за O(ln(n)) времени (или ещё более оптимально, благо алгоритмы есть. Это позволит хранить нам меньшее количество позиций, выкинув, к примеру, все маты более 50 ходов и менее 5.
  26. TopicStarter Overlay

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

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

    Начиная с этого места уже непонятно. Что значит "составляются цепочки ходов". Сколько будет цепочек, какой они будут длины? Как их хранить, сколько памяти на них придётся выделить?

    Нужно подумать, как сохранить все цепочки ходов, например, в kqnkrbn. Сколько времени будет работать мини-макс на этих терабайтах цепочек.

    Очень интересно было бы увидеть эту компактную таблицу. У Налимова, конечно, совершенно не так. Никаких цепочек нет, есть лишь отдельные ходы.

    Всё-таки, зря вы не хотите попробовать экспериментировать. Уверен, что получилось бы что-то интересное.
  27. TopicStarter Overlay

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

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

    Рациональный и проверенный практикой подход. Правда, для DTM50 этой простой идеи недостаточно, но для DTZ50 и WDL50 она работает отлично.

    Простые варианты разбиения: По числу пешек и по числу фигур с каждой стороны. Например, можно считать только беспешечные эндшпили, хоть до 10-фигурных, потом с одной пешкой, и т.д. Или, считать эндшпили голый король против кучи фигур, опять же, хоть до 10-фигурных (Потом король + одна фигура против кучи фигур, и т.д.). С сожалению, эти простые схемы оставляют за бортом как раз самые интересные эндшпили, а не наоборот. Может быть, удастся найти какие-то более полезные факторы.
  28. TopicStarter Overlay

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

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

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

    Что подразумевается под отслеживанием "прогресса", тоже неясно. Допустим, мы в некой позиции. Видим 10 возможных ходов, из которых 5 - ничейны и 5 - выигрывают и не являются взятиями или продвижениями пешки (или пешек вообще нет на доске). Как выбрать ход, который не упустит выигрыш по правилу 50 ходов? (Если под отслеживанием подразумевается просто констатация факта, что вот, уже сделали 40 ходов, уже 45, и т.д., вплоть до ничьи по правилу 50 ходов, то это в движках обычно уже реализовано.)
  29. TopicStarter Overlay

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

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

    Вообще, несколько похожий метод уже реализован в таблицах Де Конинга.

    (Источник)
  30. TopicStarter Overlay

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

    • Команда форума
    Рег.:
    11.02.2006
    Сообщения:
    1.208
    Симпатии:
    22
    Репутация:
    8
    Оффлайн
    Можно чуть подробнее? Какие действия проделывает движок, чтобы посмотреть табличную оценку для конкретной позиции?
  31. Killster Учаcтник

    • Участник
    Рег.:
    12.05.2011
    Сообщения:
    75
    Симпатии:
    0
    Репутация:
    0
    Оффлайн
    Создает эту самую хешфункцию из позиции (я потому и предложил делать хеш на основе битборд) и ищет уже собственно в базе по хешу. Если, к примеру, позиции нет, то ничья (по правилу 50 ходов или ещё как-то - неважно). Если есть - получаем Distance To Mate - в оценочной части движка на этом мы прерываемся - у нас выигрыш, а когда настает время ходить просто генерируем все ходы и запрашиваем DTM по ним.

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

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

    Вот дали нам файл Excel в котором 10000 записей, расположенных в хаотичном порядке.
    И дали задание найти некую информацию, соответствующую записи с номером 2434.
    Как мы будем искать?
    Тупо просматривать все строчки подряд?
    Наверное выделим необходимое поле, нажмем кнопку "Сортировать по возрастанию (или убыванию)"
    Табличка выстроится по номерам с 1 до 10000.
    Далее мы не будем каждое из чисел 1,2,3 и т.д. сравнивать с необходимым числом.
    Мы перелистываем несколько страниц и смотрим на каком числе мы остановились. И таким образом найдем необходимое число и тут же увидим ту самую информацию, которую искали.
    А теперь представим, что записей не 10000, а 100000. Разве увеличится время поиска в 10 раз?
    Будет такое же, при условии, что листая страницы, Вы сразу попадете на нужную.

    Примерным образом и происходит поиск по ключевому полю в СУБД. Только все проделанные нами операции осуществляются автоматически.

    Вот если мы сделаем запрос, скажем такого типа - выдай хотя бы одну запись или выдай все записи (это разные запросы) в которых для ничьей нужно сделать 72 хода, то поскольку мы индекс на это поле не задали, будет анализироваться КАЖДАЯ запись на предмет сравнения с числом 72. И чем больше база, тем дольше будем ждать ответа.
    Также если мы попросим выдать значения ключевого поля, в котором есть цифра 3 предположим на втором от конца месте, то БД выстроит все записи по порядку и потом каждую начнет анализировать. Это будет долго.

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

    Я думаю скорость прежде всего определяется скоростью чтению с диска, а также в какой базе хранятся данные (ORACLE, MS SQL или другая). Но я уверен, что любая современная БД выдаст ответ на простой запрос по ключевому полю за миллисекунды, а может и за доли миллисекунд НЕЗАВИСИМО от количества записей. Опять же многое зависит от настроек БД. Если она ориентирована на обработку большого количества записей - настройки одни, если, как в нашем случае для пользователя, добавлять или изменять записи не надо, нужно только быстрее дать ответ на простой запрос - можно оптимизировать под эту задачу.

    Ну это примерно также, как если вы в командной строке наберете полный путь к некому файлу. Скорость доступа к нему не зависит от того, насколько занят в целом ваш жесткий диск, а также от того, сколько файлов лежит в необходимой папке: 2 или 5000.
    А вот если вы его будете искать "Поиском", то скорость нахождения в общем случае сильно зависит от заполненности диска.

    подробнее про индексы можно почитать на Википедии http://ru.wikipedia.org/wiki/Индекс_(базы_данных)
  33. MS Михаил Семионенков

    • Команда форума
    Рег.:
    10.02.2006
    Сообщения:
    6.390
    Симпатии:
    2.507
    Репутация:
    163
    Оффлайн
    Удивлён, что это считается проблемой. Нужно написать функцию, нумерующую позиции (для простоты можно и нелегальные позиции пронумеровать). Для этой идеи точно патент просить не буду :)
    И генератор, и играющая программа должны использовать одну и ту же функцию, и все дела.

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

    Эстеты борьбы 3-х коней с двумя слонами и т.п. (и ревнители правила 50 ходов) могут, конечно, заметить, что метод, строго говоря, не гарантирует от проблемы 50 ходов (но вычислить такой эндшпиль, где, с одной стороны, можно вписаться в правило 50, а с другой - алгоритм может под него подвести - это отдельная задача, исключительно эстетическая, для игровых программ значения не имеющая).
  34. Magystr Новичок

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

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

    Оперативной памяти для этого нужно оч мало. Ну предположим если 1000 ходов, то 1000*10 байт(грубо) = 10 кБт. Если 10000 ходов не произошло взятия, мата или повторения, соответственно нужно 100 кБт.
    В оперативке хранится только текущая НЕЗАВЕРШЕННАЯ ветка от исходной позиции.
  35. MS Михаил Семионенков

    • Команда форума
    Рег.:
    10.02.2006
    Сообщения:
    6.390
    Симпатии:
    2.507
    Репутация:
    163
    Оффлайн
    Опять немного недодумал. Программа не "должна", а "в частности, может". Информация нейтральна, она должна обеспечивать сходимость процесса для программы, у которой достаточно мозгов и мускулов. А что имеенно будет делать программа - это уже её дело.

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