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

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

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

    • Команда форума
    Рег.:
    10.02.2006
    Сообщения:
    6.400
    Симпатии:
    2.554
    Репутация:
    164
    Оффлайн
    Пока совсем не забыл, ещё разок.

    О разделении проекта по метрикам.

    Оно всё-таки напрашиватеся. DTM во всех отношениях стоит особняком.
    А WDL-DTZ идут в обойме. Пятидесятки не очень серьёзно: правило искусственное, его могут в любой момент пересмотреть, особенно для компьютерных шахмат.
    То есть 1 генератор для DTM, и один - "для всего остального". Конечно, в идеале, чтобы как у танковых двигателей во время отчественной: "лёгким движением руки" 1500 лс превращаются в 500.

    Идея неполных таблиц для практиков.

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

    Как компенсировать нехватку младших таблиц, получаемых в результате превращений?
    Для требуемой таблицы с пешкой на c7, скажем, смотрим (не просчитанные таблично) позиции с ферзём на с8 и движком на небольшой глубине оцениваем её. В большинстве случаев будет выигрыш. Если ясного выигрыша не видно, проверить превращение в коня. Конечно, теоретически возможно, что позиция будет неясной (появится 2 ферзя), но в анализе практической партии такая вероятность пренебрежима мала. Я думаю, шахматисты-практики проголосуют двумя руками за такие таблицы. Вероятно, для таких таблиц нужна специальная метрика, чтобы при анализе было видно происхождение и достоверность результата.
    Если здесь не кроется невидимый мне изъян в рассуждениях, то такие таблицы можно построить очень быстро, на весьма скромных компьютерах, и сразу продолжить путь к 8фигуркам, соревнуясь с семифигурным DTM.
  2. Мобуту спаситель нации

    • Заслуженный
    • Ветеран
    Рег.:
    15.02.2006
    Сообщения:
    6.462
    Симпатии:
    2.076
    Репутация:
    105
    Адрес:
    Заир
    Оффлайн
    Мне тоже кажется, что "практические таблицы" - наиболее живое направление, т.к. прямой перебор всего и вся себя уже явно исчерпал. За десять лет ничего нового не сделано, по сути, перспективы - практически отсутствуют.

    Самое дикое, что я вижу в прямолинейной налимовщине - что позиции без пешек проще, чем позиции с пешками. Ведь по-человечески же наоборот: пешки - это упрощающий фактор, довольно малоподвижная структура. Стоит на своей линии, возможных полей для её расположения - с гулькин нос. А сверхстрогий налимовский подход говорит: что ты, каждая пешка может переместиться чуть ли не на любое поле, с e2 на b5 куда-нибудь. А потом и вовсе превратиться в кого угодно и ускакать в неизвестном направлении. Так что пока мы не изучили окончание "три коня против трёх слонов", нечего и мечтать подступиться к пешечнику три на три, f g h против f g h.


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

    Стоило бы потестировать разные предположения вроде этих на предмет эффективности, на предмет глючности - наверняка с их помощью можно выбраться за пределы и 7, и 8 фигур.
  3. TopicStarter Overlay

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

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

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

    Значит так, тут нужно ещё вспомнить, кто кого пытался обмануть. Данные для доски 4х4 я привёл в качестве иллюстрации идеи, и лишь потому, что данных для доски 8х8 у меня нет. Множество шахов на маленькой доске - довольно незначительный фактор, посколько 1. при ходе белых чёрные фигуры могут давать легальные шахи, и таких позиций всё равно очень много. 2. Большая часть избыточности индекса происходит из симметрий.

    А вот с вашей стороны, сначала фигурировал индекс 64*64*... , затем откуда-то из рукава был извлечён множитель 32 и заявлено что так и было задумано изначально. :) (Когда я уже не поленился оценить отношение числа позиций к числу дырок).

    По поводу сравнения CУБД и ручного доступа - моя оценка основана больше на общих соображениях. СУБД предоставляет некоторые удобства (сложные запросы, индексы и т.д.), которые при построении таблиц нам не нужны. С другой стороны, индексы занимают память или требуют лишних обращений к диску. В стандартных подходах к решению окончаний эффективнее всю имеющуюся память использовать как кэш таблиц. Цифр нет не только у меня, но и вообще, так как никто пока что не пробовал хранить таблицы в реляционной базе данных. Это просто не имеет смысла, по крайней мере таково моё сегодняшнее понимание вопроса. :)

    Буду только рад увидеть любые цифры или данные, как о дырявости индексов, так и о скорости реляционных баз при хранении таблиц.
  4. TopicStarter Overlay

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

    • Команда форума
    Рег.:
    11.02.2006
    Сообщения:
    1.208
    Симпатии:
    22
    Репутация:
    8
    Оффлайн
    Справедливые соображения. В моём генераторе примерно так и есть - индекс более-менее независим от собственно генератора, который общается с индексом через определённый интерфейс. Единственное, с чем несогласен - это с DLL. Индекс должен быть реализован на С/C++, и быть доступен в виде исходника. Иначе не вижу смысла возиться. Непереносимый код - пустая трата сил и времени. (Насчёт Java-ы, купленной и закрытой Ораклом, думаю мне даже не обязательно комментировать).

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

    Что такое "ПНП"? Перевод WDL?

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

    Если приз делить на WDL и всё остальное, то могут быть потенциальные проблемы. Например: DTZ-генерация должна уметь использовать WDL-таблицы. Но если WDL и DTZ-генераторы делаются разными людьми, то возможны какие-нибудь несовместимости.

    Интереснее всего, конечно, было бы услышать мнение потенциального разработчика. Мне пока здесь ничего не очевидно.
  5. MS Михаил Семионенков

    • Команда форума
    Рег.:
    10.02.2006
    Сообщения:
    6.400
    Симпатии:
    2.554
    Репутация:
    164
    Оффлайн
    Мы говорили немного о разных вещах. Естественно, в процессе построения таблиц нужно стараться по максимуму держать всё в памяти, реальной или виртуальной. Я говорю о хранении результата и доступе к нему. БД - это прежде всего - унифицированный интерфейс. Вместо того, чтобы придумывать формат файлов и писать программу доступа к нему, можно всё засунуть в базу и вытаскивать таблицу по SQL запросу "дай мне запись KRPg3Ph4KRPh5". И для этого случая, надеюсь, согласитесь, споры о потере эффективности по сравнении с файлами большого смысла не имеют.
  6. TopicStarter Overlay

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

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

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

    С другой стороны, если у нас уже, к примеру, есть команда, которая, пусть медленно, но что-то делает, тогда, конечно, стратегия имела бы смысл.
  7. MS Михаил Семионенков

    • Команда форума
    Рег.:
    10.02.2006
    Сообщения:
    6.400
    Симпатии:
    2.554
    Репутация:
    164
    Оффлайн
    Ну,на предмет DLL просто ляпнул - С действительно переносим только на уровне исходников (чем сильно уступает Java).

    А мнение Ваше о Java, скажем так, не единственное. Я работаю в компании с миллиардным оборотом. Значительная часть софта пишется на Java, по ощущениям - чем дальше, тем больше. В видимой мне (небольшой, конечно) части компании весь новый софт пишется на Java, С только поддерживатся. Никто не кричит: "Шэф, всё пропало". Компании это позволяет успешно паразитировать на Open Source, начиная с Апача (пакуемоего вместе с нашими продуктами), кончая библиотечками для твиттера и фейсбука. Лично я бы морально стареющие С сервера заменял на джавовские HTTP приложения под Апачем (и аналогами), но это уже профессиональный разговор.

    (У тех, кто в теме по поводу Java прошу прощения за небрежность в терминологии: подразумевался, конечно, Апач Томкат).
  8. TopicStarter Overlay

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

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

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

    Это личные предпочтения, если кому-то не хочется придумывать формат файлов и писать код чтения/записи, то база данных - вполне рабочий вариант. Но мне кажется, в этом случае в сумме придётся писать не меньше, но больше кода.
  9. MS Михаил Семионенков

    • Команда форума
    Рег.:
    10.02.2006
    Сообщения:
    6.400
    Симпатии:
    2.554
    Репутация:
    164
    Оффлайн
    Вы говорите в основном о создании и транспортировке таблиц, я смотрю с точки зрения использования.

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

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

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

    • Команда форума
    Рег.:
    10.02.2006
    Сообщения:
    6.400
    Симпатии:
    2.554
    Репутация:
    164
    Оффлайн
    Ещё раз про вкус.
    Поскольку мне бы и в голову не пришло передавать доступ к таблицам в виде программы доступа к файлам, до меня долго доходило, что делать это просто нельзя. Просто потому, что по определению программа, использующая таблицы такого размера, не будет иметь доступ к файловой системе, в которой хранятся таблицы. (доступ к файловой системе ещё можно открыть в интранете, но не интернете). Использующая программа один чёрт получит доступ к таблицам через сервер. Будет ли это HTTP сервер или SQL сервер - отдельный вопрос, но процедура доступа к файлам здесь не представляет никакой ценности. Можно сказать, что отгородим таблицы от пользователя HTTP сервером, "а дальше дело вкуса". Но наличие SQL сервера и в этом случае даст дополнительную гибкость. HTTP сервер имеет смысл, когда поверх запросов к таблице мы наворачиваем что-то (создаём HTML страницу, например). В конце концов, мы можем открыть доступ непосредственно к SQL серверу, полностью отдавая на откуп логику обработки пользовательской программе.
  11. TopicStarter Overlay

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

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

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

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

    Ручной доступ - значит fseek()/fread() вызывает наш код доступа, а не СУБД.
  12. TopicStarter Overlay

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

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

    Далее, пользователь движка должен тоже ставить и настраивать СУБД. Скачивание новых таблиц, или удаление ненужных, превращается в махинации с интерфейсом СУБД, вместо простого скачивания/удаления файла. Разнесение таблиц на разные физические диски - опять нетривиальные махинации с СУБД, вместо перенесения файлов. И т.д. и т.п. Простейшие и привычные операции с таблицами превращаются в головоломки, решать которые пользователь не готов.

    Сколько авторов движков вы опросили, и сколько проголосовали за доступ к таблицам через SQL? Сколько, вы думаете, проголосуют, если провести такой опрос?

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

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

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

    Как я понимаю, вы предпочитаете SQL для общения с сервером, и вам кажется совершенно ненужным отдельный локальный доступ. Моё предпочтение: локальный доступ необходим, общение с сервером я бы делал опять же кустарное через TCP, в погоне за меньшим временем доступа.
  14. MS Михаил Семионенков

    • Команда форума
    Рег.:
    10.02.2006
    Сообщения:
    6.400
    Симпатии:
    2.554
    Репутация:
    164
    Оффлайн
    Готов согласиться. Скажем, за пятифигурками нет особого резона бегать по сети.

    Локальный доступ принял. Погоню за меньшим временем - надо, мне кажется, эксперимент ставить, есть ли действительно выигрыш. Повторюсь - проценты не стоят борьбы, особенно если за них проиходится платить отходом от каких-то стандартных тракторов. Что касается именно SQL для удалённо доступа, то ещё надо подумать, поскольку всё действительно скрыто "в облаках": таблицы могут находится на разных серверах. Может, нужно обращаться к какому-то определённому HTTP серверу, который может переадресовать при необходимости запрос. HTTP, поскольку там механизм переадресации - родной, если я не ошибаюсь, что упростило бы логику доступа.

    Подытоживая: программа пользователя знает наличные таблицы и место доступа за удалёнными таблицами.
    Удалённый сервер может переадресовать запрос к серверу, где реально расположены таблицы.
    Хотя начинает появляться ощущение, что уже я начинаю заниматься кустарщиной :)
    Действительно неплохо на досуге заглянуть "в облака": наверняка такие вопросы уже отработаны.
  15. dan77790 Учаcтник

    • Участник
    Рег.:
    06.03.2008
    Сообщения:
    3.792
    Симпатии:
    16
    Репутация:
    0
    Оффлайн
    А облачные технологии тут не могут быть использованы?) Просто слово понравилось)
  16. MS Михаил Семионенков

    • Команда форума
    Рег.:
    10.02.2006
    Сообщения:
    6.400
    Симпатии:
    2.554
    Репутация:
    164
    Оффлайн
    Да мы о том и говрим. Теоретически могут, но и технологиям, и пользователям нужно ещё подрасти :)
  17. MS Михаил Семионенков

    • Команда форума
    Рег.:
    10.02.2006
    Сообщения:
    6.400
    Симпатии:
    2.554
    Репутация:
    164
    Оффлайн
    Ещё раз об эффективности: стоит ли тратиться на более эффективные реализации генератора и сервера доступа к построенным таблицам.

    По части сервера доступа (TCP vs HTTP) остаюсь при мнении, что HTTP предпочтительнее: это программирование на высоком уровне, на отлаженных и хорошо оптимизированных библиотеках, что сильно сократит время разработки, повысит надёжность и, соответственно, упростит сопровождение. Потерю эффективности можно компенсировать затратами на железо. Грубо говоря, использовать 2 сервера вместо одного - это более чем выгодная плата за экономию месяцев работы программиста.
    (В семидесятые ситуация была кардинально другая - дополнителная ЭВМ - это дополнительный этаж, дорогущая машина и десятки человек для круглосуточного обслуживания такого монстра).

    Что касается собственно генератора, то потенциальные миллионы процессорных часов на построение таблиц говорят о том, что задачи, где борьба за эффективность софта всё еще стоит программистских усилий, не перевелись.
    Использование С, а не, скажем, Java - выглядит вполне резонно, просто резон не в том, что Java "закрыта" Ораклом, а в том, что С всё-таки эффективнее, и экономия миллионов процессорных часов стоит усилий.
  18. TopicStarter Overlay

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

    • Команда форума
    Рег.:
    11.02.2006
    Сообщения:
    1.208
    Симпатии:
    22
    Репутация:
    8
    Оффлайн
    Я не против HTTP. Как вы уже заметили, TCP - это выжимание процентов. Можно обойтись и без выжимания, я не спорю. Вопрос личных предпочтений. И, для TCP тоже есть библиотеки. Но суть не в этом. В принципе можно вообще ничего не кодировать специальное, а прикрутить какой-нибудь p2p-swarm-клиент для обмена файлами, либо что-нибудь примитивно-скриптовое, с фтп-серверами и wput/wget, и т.д. Вариантов очень много, HTTP или TCP (или FTP) использовать - не так и важно.

    Согласен с выбором С. Про Яву лучше не буду здесь спорить.
  19. WinPooh В.М.

    • Команда форума
    Рег.:
    13.02.2006
    Сообщения:
    9.256
    Симпатии:
    2.573
    Репутация:
    90
    Адрес:
    Москва
    Оффлайн
    Кстати, про Яву.
    http://www.opennet.ru/opennews/art.shtml?num=30840

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

    • Команда форума
    Рег.:
    10.02.2006
    Сообщения:
    6.400
    Симпатии:
    2.554
    Репутация:
    164
    Оффлайн
    Надо размораживать "кофейную" тему. :)
    Честно говоря, был не в курсе, что у Апача такие запары.
  21. Skipper_NORTON Учаcтник

    • Участник
    Рег.:
    14.12.2007
    Сообщения:
    512
    Симпатии:
    1
    Репутация:
    0
    Оффлайн

    Magystr, судя по вашим постам, вы специалист, компьютерщик.
    И удивительно, почему вы не понимаете, о чем говорят, и что имеют в виду, говоря, "информация о позиции в среднем занимает 1,5 бита". Открою вам страшную тайну, информация о позиции может занимать и 0,5 бита. Или даже 0,1 бита.

    Вы что-нибудь про архиваторы слышали? Вот есть файлы, которые они СЖИМАЮТ. Например, вы набираете текст, "sdgtughc3t83djjce944tr4t58g..." содержащий 1 миллион символов. А один символ (простой char) - занимает 1 байт, т.к. всего имеется (допустим), 256 возможных вариантов символов. Этот текст вы сохраняете в txt-файле.

    Потом, в зависимости от того, какой там текст, архиватор этот файл СЖИМАЕТ. Если у вас будет текст из упорядоченных символов, например "ffffffffffhhhhhhhhhssssssssssssssttttttttttt...", то архиватор его ХОРОШО сожмет.

    Несжатый файл содержал 1 миллион символов (байт). Предположим, архиватор сжал ваш файл с текстом в 80 раз, т.е. ваш файл с текстом стал занимать 12500 байт. Но потерь никаких нет - ведь вы можете РАЗЖАТЬ его и восстановить все ваши 1 миллион символов! Значит, в сжатом виде, у вас информация о символе занимает в среднем 0,1 бита!

    :)

    Или что-то я неправильно сказал?

    Предложение -
    "Сначала 200 тысяч символов A, а потом 200 тысяч символов B, а потом 600000 символов С"
    содержит информацию о миллионе символов, но реально я в предложении написал 86 символов. :)

    Так же и шахматные базы. Если их сжать, то получается, в одном байте может храниться информация, хоть о 50 позициях. Потому что там, так сказать, структура информации совсем другая. Конечно, есть файлы, которые в принципе нельзя сжать никаким архиватором. Если энтропия (мера беспорядка) там максимальна. Это т.н. "белый шум".

    0,1 бита - такая же математическая абстракция, как и "1,6 человека". Т.е. хотя реально 1,6 человека мы не увидим, нам ничто не мешает сказать что-нибудь типа "В этом месяце, в стране, каждый литр спирта пришелся в среднем на 1,6 человека".
  22. Magystr Новичок

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

    Прежде всего, я вел речь об одной записи в таблице. Исходной и НЕСЖАТОЙ.
    Поэтому и говорил о том, что НЕСЖАТАЯ запись о ПОЗИЦИИ и ее ОЦЕНКЕ, а также о количестве ходов до цели или любой другой дополнительной информации ну никак не может храниться в одном-двух битах информации.
    Поэтому сравнивать гипотетический размер НЕСЖАТОЙ таблицы с таблицей, подвергшейся сжатию, просто некорректно.

    Предполагаемый размер 7-мифигурных таблиц (сжатых) оценивается в 300 Тб (примерно). И даже если разница будет в полтора-два раза - это никак не повлияет на мой вывод.
    В обозримом будущем такие таблицы никому не нужны. Никому - это значит широкому кругу шахматистов, использующих шахматные программы для тех или иных целей.
    То, что они были бы интересны узкому кругу специалистов и фанатов - тема другого обсуждения.
    По моим оценкам, чтобы какие бы то ни было ВСПОМОГАТЕЛЬНЫЕ таблицы были интересны многим, необходимо чтобы их размер (на настоящее время) был не более 4-5 Тб, а реально желательно не более 1,5-2 Тб.
    Я исхожу из того, что заглянув на Яндекс.Маркет, увидел - стоимость жесткого диска 2 Тб чуть более 2.000 рублей, 3 Тб - около 4.000 рублей. Далее цена возрастает непропорционально.
    Предлагать пользователям вкладывать тысячи американских или европейских денег ради удовольствия поднять рейтинг движка на 15-20 единиц ЭЛО считаю утопией.

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

    Какие есть способы?
    1. Сжатие готовых таблиц.
    2. Уменьшение размера (в Байтах или Битах) каждой записи в таблицах.
    3. Уменьшение количества записей в таблицах.

    Оценим эффективность каждого из способов.
    1. Насколько я понял, в настоящий момент сжатие уже используется. Вряд ли удастся существенно улучшить механизм архивации таблиц в том формате, который в настоящее время используется. Ну, предположим 1,5-2 раза. И это предел.
    2. В настоящее время существует 2 подхода, насколько я понял. Это бит-базы и собственно таблицы Налимова. Первые из них существенно меньше вторых. Не знаю на сколько (на порядок?). Уменьшить размер записи в каждом из вариантов хотя бы раза в полтора вряд ли удастся. Значит нужно решить, имеет ли смысл переходить на бит-базы, или при этом потерянные данные окажутся чрезвычайно важны. А может не чрезвычайно? А может не все заметят ту потерю? Пока вопросы.
    3. Резкое уменьшение объема таблиц за счет удаления из них записей, которые не являются очень информативными. В общем-то здесь предела нет. Принципиально можно сократить базы хоть в 10 раз, хоть в 50. Понятно, что чем больше их ужмем, тем вероятно больше информации потеряем. Но при этом соотношение оставшихся данных и удаленных будет по информативности несоизмеримо.

    Таким образом, позволю себе сделать вывод:
    - пунктами 1 и 2 безусловно нужно заниматься;
    - без решения по пункту 3 не обойтись. Путей решения может быть несколько, каждый может отстаивать тот, который ему ближе и понятнее.
    НО РЕШАТЬ ЕГО ВСЕ РАВНО ПРИДЕТСЯ тому, кто хочет продвигать идею Налимова дальше.

    В качестве примера:
    Возьмем двух королей (белого и черного), остальной комплект фигур и по 2-3 пешки белых и черных спрячем в мешок.
    Достанем из мешка наугад 5 фигур, добавим королей и бросим весь этот комплект на доску. Предположим все эти фигуры не скатились с доски, а каждая заняла случайное поле.
    Если позиция нелегитимная, просто повторим бросок.
    Предлагаю оценить вероятность того, что полученная таким образом случайная позиция со случайным набором фигур окажется очень интересной и нетривиальной и пути достижения оптимального результата будут сложны и недоступны современным движкам?
    По моим очень грубым оценкам где-то в районе 0,01 - 0,001.

    Ну и в завершение немного дополнений о современных СУБД.
    1. Существующие СУБД, я пока ограничу их список тремя (MySQL, ORACLE, PostgreSQL), сами умеют эффективно сжимать свои данные. Причем скорость обращения к таблицам после сжатия только возрастает.
    Особенно эффективно такое сжатие для таблиц, в которые не производится дальнейшей записи данных, а только запросы к существующим записям.

    Вот первая же ссылка, которую мне удалось нагуглить по запросу "сжатие данных в mysql".
    http://compression.ru/download/articles/db/smirnov_2003_database_compression_review/part4.html
    Вся статья была достаточно интересна для меня. Она написана понятным языком и небольшого объема. Впрочем все выводы находятся в части 4-й.
    Обращаю внимание, что статья написана в 2004 году. С тех времен сделаны громадные шаги вперед в этом направлении.
    Ну и еще одна ссылочка, на которую случайно натолкнулся:
    http://madjack.ru/developer/2009/08/mysql-vs-postgresql.html
    Помимо информации о современных СУБД в конце статьи есть любопытный подраздел "Лицензирование", который очень сильно перекликается с параллельной веткой о Рыбке. Может быть это кому-то будет небезынтересно.
  23. Skipper_NORTON Учаcтник

    • Участник
    Рег.:
    14.12.2007
    Сообщения:
    512
    Симпатии:
    1
    Репутация:
    0
    Оффлайн
    Дайте четкие критерии, какие именно позиции вы хотите "выбросить" из таблиц?
    И как индексировать оставшиеся позиции, если скажем, половина из них выброшена, по каким-то сложным причинам?
    Чем более сложная индексация, тем медленнее программа будет работать.
  24. NS Нефёдов Сергей

    • Заслуженный
    • Ветеран
    Рег.:
    02.05.2006
    Сообщения:
    6.811
    Симпатии:
    96
    Репутация:
    3
    Адрес:
    Санкт-Петербург
    Оффлайн
    Вообще обычно выбрасывание позиции из базы - это присваивание ей результата неопределено. Что позволяет сильнее сжимать базу. В шашках перед сжатием обычно выкидывают позиции с взятием.
  25. NS Нефёдов Сергей

    • Заслуженный
    • Ветеран
    Рег.:
    02.05.2006
    Сообщения:
    6.811
    Симпатии:
    96
    Репутация:
    3
    Адрес:
    Санкт-Петербург
    Оффлайн
    нееправильно выразился - правильней назвать присвоенный результат - неважно.
  26. Magystr Новичок

    • Новичок
    Рег.:
    19.04.2011
    Сообщения:
    62
    Симпатии:
    14
    Репутация:
    2
    Оффлайн
    Критерий тут один - удалить (или не создавать) те записи, без которых современные шахматные движки на современном компьютерном оборудовании найдут верное решение позиции и без таблиц.
    Под современными компьютерами я понимаю не эксклюзивные топовые супер дорогие процессоры, а стандартные, вроде Core-i7 или даже Core-i5. Ну или Phenom-2. Это кому как нравится.
    А вот как отсортировать позиции - где найдут, а где не найдут - тут подходы могут быть разные и обсуждаемые.
    В качестве одного из решений - это такие позиции, в которых в течении 15-ти ходов (30-ти полуходов) ставится мат или происходит переход в низший эндшпиль с известным результатом. Не нравится 15 ходов - ОК, пусть будет 12.
    Это может быть и большой материальный перевес, сохраняющийся в течении 2-4-х ходов без шахов.
    Да много чего можно напридумывать.

    Как индексировать эти таблицы? Хммм...
    Если речь идет о стандартных БД, то это уникальный индекс по позиции - первичный ключ (индекс). Самый простой. По одному полю. Работает мгновенно. При этом не надо производить архивацию-разархивацию таблиц.
    Если же речь идет об индексах непосредственно Налимовских таблиц, тут к сожалению ничего не могу сказать, потому что попытки узнать какую-то информацию по структуре, индексам, метрикам и т.п. существующих таблиц ни к чему не привели. Ни здесь на форуме, ни в поисковиках никакой реальной информации я не узнал. Как и не увидел попыток хоть кого-то, кто владеет этой информацией, вкратце понятным языком это рассказать. Так же как и рассказать, как осуществляется обмен информацией между движком и таблицами.

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

    В конце концов между Windows 3 и Windows Seven прошло много времени, вряд ли у них осталось хоть что-то общее, кроме идеи. Но никто не будет оспаривать преемственности.

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

    • Команда форума
    Рег.:
    10.02.2006
    Сообщения:
    6.400
    Симпатии:
    2.554
    Репутация:
    164
    Оффлайн
    Мне кажется, над сжатием собственно таблиц голову ломать особенно и не нужно. Чем проще индекс, тем лучше.
    Речь о том, что из 2000 эндшпилей выкинуть в итоге процентов 95. Можно, конечно, поломать голову и над сжатием оставшихся таблиц, но это уже второй знак. Традиционные методы сжатия здесь, собственно, не при делах: это вопрос отсева информации, не имеющей практического значения, а не сжатия.
  28. Skipper_NORTON Учаcтник

    • Участник
    Рег.:
    14.12.2007
    Сообщения:
    512
    Симпатии:
    1
    Репутация:
    0
    Оффлайн
    Magystr

    Объясняю пунктуально. И доступно. Чем отличаются мои и налимовские базы, от универсальных, например, SQL Server. Универсальные базы, хранили бы 1) - информацию о позиции (где расположены все фигуры), и 2) - оценку позиции. Из таких баз действительно, можно выбросить любые позиции. Но эта "информация о позиции" - скажем, в 10 раз больше, чем 2) - оценка позиции. Что такое оценка? Это 1 байт (в несжатом виде). В байт записываются значения, от -128, до 127. Если записан 0 - то позиция ничейная. Если 1, то на доске стоит мат, либо белые ставят мат в 1 ход. Если -3 - то черные выигрывают за 3 хода. Если в рамках данного эндшпиля, максимальный путь к мату 127 ходов, либо меньше, то информация о позиции - будет 1 байт, и это в несжатом виде. От -127 до 127, т.е. от выигрыша черных за 127 ходов, до выигрыша белых за 127 ходов.

    В моих базах и базах Налимова хранятся ТОЛЬКО оценки, там не хранится "информация о позиции", которая намного больше занимала бы места. А чтобы иметь возможность "выбросить" любые позиции из базы - ее НУЖНО хранить. Вы хотите выбросить более 90% позиций из базы? Это слишком много, и такая игра, по таким базам, будет чревата ошибками. Более того, построение самих баз, старших, не имеющих 90% требуемых позиций из младших эндшпилей приведет к лавинообразному накоплению ошибок в самих старших эндшпилях, через несколько этапов, это будут уже не базы, а неизвестно что. Обратившись в базу, и получив оттуда информацию. скажем, что белые выигрывают за 78 ходов, может оказаться так, что белые там выигрывают за 133 хода, или там вообще ничья на самом деле, а главное - движок перейдя в эту "выигранную" позицию, потом будет не в состоянии доказать это и выиграть.

    Выбросить позиции из базы, которая НЕ ХРАНИТ сами данные о позициях - будет очень проблематично, т.к. нет точных критериев для эндшпилей, какие именно позиции нужно выбрасывать, а главное - это сильно усложнит индексацию позиций, что сильно замедлит создание таких баз.
  29. Skipper_NORTON Учаcтник

    • Участник
    Рег.:
    14.12.2007
    Сообщения:
    512
    Симпатии:
    1
    Репутация:
    0
    Оффлайн
    Magystr

    Как же программы работают с базами, которые НЕ ХРАНЯТ данные о самих позициях, а хранят ТОЛЬКО оценки.
    Программа, получив какую нибудь игровую позицию, например
    Ka1, Qb1 - Kc8, Rd8 - переводит ее в ЧИСЛО, уникальный идентификатор.
    Каждая позиция переводится в какое то число, не больше чем полное количество всех позиций в рамках данного эндшпиля. И наоборот, каждое такое число, можно обратно перевести в позицию (и расставить фигуры на нужных местах). Это - БИЕКЦИЯ, т.е. взаимно-однозначное соответствие.

    Написать функцию, которая будет переводить позиции в эти числа, и наоборот, числа переводить в позиции - несложно, есть много подходов. Например, самый простой из них - программа получила позицию, из 4-х фигур, которые стоят на полях с номерами
    X,Y,Z,K, (от 1 до 64) определяем однозначно последовательность фигур, и число будет равно

    X*64*64*64 + Y*64*64 + Z*64 + K.

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

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

    Потому и никакие идентификаторы в базе хранить тоже не нужно. И обращение к винчестеру будет ТОЛЬКО ОДНО. Для получения информации об одной позиции.

    Чтобы выбрать наилучший ход, из какой то позиции, программа, делает все возможные ходы из этой позиции например есть 5 возможных ходов из позиции (какой выбрать?), и получившиеся позиции переводит в числа, потом лезет в нужные места в файле, читает все оценки, и видит , что после 1-го хода -
    +36, после 2-го +24, после 3-го хода +54, после 4-го - 0 (ничья), а после 5-го -22 (черные выигрывают за 22 хода).

    Значит, т.е. ход белых, то лучший ход для них - 2-й, т.е. с выигрышем за 24 хода.

    Это же настолько все просто, как мне кажется. Вам давно объясняют отличие универсальных баз от баз Налимова, а вы не понимаете.
  30. Skipper_NORTON Учаcтник

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

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

    Все подходы с "выбрасыванием" позиций тоже не годятся - это уже будут не шахматы, а по сути, другая игра. Данные из таких таблиц будут НЕВЕРНЫ.
  31. Skipper_NORTON Учаcтник

    • Участник
    Рег.:
    14.12.2007
    Сообщения:
    512
    Симпатии:
    1
    Репутация:
    0
    Оффлайн
    Самый лучший вариант, как мне кажется, построить все 7-фигурные базы в DTM, с помощью моего генератора, и хранить их (примерно 200 терабайт) пока - где нибудь в хорошем файлохранилище. И создать сайт для доступа к ним. А для программ пользователей, которые не могут иметь в ближайшие годы столько места на винчестерах - переконвертировать мои базы в формат WDL, и они будут занимать намного меньше места. И просто взять НУЖНЫЕ из них, типа KRPP-KRP, а ненужные, типа KQQQQQ-K - не брать, программа и без них выиграет.

    Это проще всего, и не надо изобретать велосипед.


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

    PPS "Не брать" эндшпильные базы - это значит не записывать себе на винчестер файл "7_KQQQQQ-K.tby", который и представляет собой базу для данного сочетания фигур. "Брать" эндшпильные базы - это значит записывать себе на винчестер файл, скажем "7_KBPP-KRP.tby", который будет полезен. :) Решил "разжевать", потому что, как оказывается, многие не понимают о чем речь.
  32. NS Нефёдов Сергей

    • Заслуженный
    • Ветеран
    Рег.:
    02.05.2006
    Сообщения:
    6.811
    Симпатии:
    96
    Репутация:
    3
    Адрес:
    Санкт-Петербург
    Оффлайн
    То есть в шашках годятся, а в шахматах нет?!
    Данные будут абсолютно верны, ведь например чтоб играть какой-нибудь KPPKP нам совершенно достаточно хранить в базе только позиции с ходом сильнейшей (KPP) стороны - вот уже сократили половину позиций.
  33. MS Михаил Семионенков

    • Команда форума
    Рег.:
    10.02.2006
    Сообщения:
    6.400
    Симпатии:
    2.554
    Репутация:
    164
    Оффлайн
    Спору нет, теоретически безупречно. Вопрос в реализуемости на практике в нынешних условиях: мобилизовать множество компов на многомесячную работу, проплатить хостинг для готовых таблиц. При нынешних ценах только стоимость дисков на такие таблицы - порядка 10 тыс у.е.


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

    • Новичок
    Рег.:
    17.06.2011
    Сообщения:
    18
    Симпатии:
    3
    Репутация:
    0
    Оффлайн
    С Мая читаю этот раздел, очень интересно. Особенно Kirr , Skipper_NORTON и NS.

    К Skipper_NORTON нельзя ли выложить 32 битный вариант генератора ( и дома и на работе 32 битные XP) .
    И второе выложите где-нибудь пример не сжатых баз 3-4 х фигурок в вашем формате что-бы
    можно было посмотреть насколько их можно сжать.
  35. Skipper_NORTON Учаcтник

    • Участник
    Рег.:
    14.12.2007
    Сообщения:
    512
    Симпатии:
    1
    Репутация:
    0
    Оффлайн
    MS, потратив приблизительно 200 тысяч долларов на компьютерные мощности, можно построить все 7-фигурные базы за 3 года. А генератор уже есть. Т.е. я предложил самое ДЕШЕВОЕ решение. (это если ПОКУПАТЬ компьютеры, а ведь есть люди, я читал на других форумах, имеющие доступ к суперкомпьютерам, и они и так простаивают - т.е. это было бы еще дешевле)

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

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

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

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

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