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

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

  1. Осипов Юрий Учаcтник

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

    Давайте подведем промежуточный итог.

    1. У Налимова на одну позицию приходится 1-2 бита. У вас получится несколько байт. С учетом хранения дополнительного индекса в виде B-дерева получится что-то порядка 10 байт на позицию.
    2. Поиск позиции у Налимова выполняется за одно обращение к таблице. У вас придется искать по индексу. Вам Kirr упоминал о логарифме, но вы похоже не обратили внимания. Так вот, поиск по индексу в базе данных пропорционален логарифму по основанию 2 от числа записей. Даже для миллиарда позиций понадобится около 30 обращений к диску. И в результате движок, перебиравший миллион позиций в секунду, будет перебирать десятки тысяч.
    3. При генерации ваших таблиц придется для принятия решения, помещать позицию в базу или нет, каждую позицию проверять движком - находит он в ней выигрыш или нет. На сколько (или на сколько порядков!) это замедлит генерацию - можно представить.

    Все это имеет смысл только в том случае, если в базу мы будем класть одну из сотен, тысяч или миллионов позиций. Но чтобы оценить это процентное соотношение, нужно просто взять и попробовать реализовать эту идею. Мысленными экспериментами и предварительными расчетами вряд ли можно точно это установить.
  2. Осипов Юрий Учаcтник

    • Участник
    Рег.:
    18.06.2007
    Сообщения:
    388
    Симпатии:
    394
    Репутация:
    11
    Адрес:
    Правда
    Оффлайн
    Магистр!

    И еще два вопроса, чтобы прояснить ваши идеи:

    1. Эндшпильные таблицы строятся на основе ретро-анализа. Не от вершины дерева вглубь, и из глубины к корню. Вы, похоже, предлагаете строить от корня вглубь. Я правильно вас понял?
    2. Вы предлагаете не проходить все дерево, а отсекать ненужные варианты, если достигнут определенный результат. Другими словами, если по цепочке ходов мы пришли к выигрышу, то не нужно искать усиления, поэтому другие "свои" ответвления в этом дереве можно пропускать. И наоборот - если мы не пришли к выигрышу, то не нужно проверять ответвления со стороны соперника.
    Однако, этот алгоритм давно известен под названием "альфа-бета". Ему уже лет 40, если не больше. Вы с ним знакомы?
  3. Magystr Новичок

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

    1. Я читал неоднократно эту оценку 1-2 бита. Я с ней не согласен. Открывать непродуктивную дискуссию на эту тему просто не хочу. хотелось бы услышать ту самую "плотность" для 4-х и 5-ти фигурок. Думаю она будет существенно выше. Если я создам пустую таблицу двухфигурок размером 1 Бт, то я получу плотность хранения 0,3 бит на позицию? Имеет ли физический смысл эта плотность записи?
    Или лучше оперировать тем, что понятнее пользователю? Например объемом занимаемым одинаковыми эндшпилями?
    Если в этом контексте, то с ростом количества фигур Налимовские таблицы по размеру догонят и перегонят стандартные реляционные базы.
    Опять же, почему таких баз не существует для других приложений? Или мы про них не знаем? Он сам придумал необыкновенно компактный способ хранения и быстрого доступа к информации, но не смог эту выдающуюся идею реализовать в серьезных коммерческих целях, кроме шахматных?
    За 15-20 лет и железо и софт достигли такого уровня, который был фантастикой. Но ни он сам, ни другие последователи так и не придумали хотя бы похожего способа?
    2. Уже неоднократно читал тут, что у Налимова обращение по индексу идет практически со скоростью света, а вот допустим в БД ORACLE ТОЖЕ ПО ИНДЕКСУ оно будет измеряться десятками секунд.
    У Налимова какие-то особенные индексы? И подскажите пожалуйста, по какой теории скорость обращения ко всем другим базам пропорциональна логарифму от количества записей. Просто ссылочку дайте, очень любопытно почитать. Желательно на русском.
    Я вот прекрасно знаю, что если скорость работы БД ORACLE по какой-то причине не устраивает пользователя, существует простое решение - ставится дополнительный диск, производится определенная настройка и скорость работы с базой практически удваивается. Это как-то учитывается в формуле с логарифмом? А если 5 дисков в RAID объединить? Ну и вообще, на Налимовские базы логарифмы не распространяются? Почему?

    Вот нашел в поисковике за пару минут:
    http://www.d2dev.ru/download/blog/broshures/OracleAdvancedCompression.pdf
    Почитайте прям сначала второй страницы. "Сжатие реляционных данных".

    Еще на днях находил сайт на английском языке, где описывались разные возможности и тесты ORACLE. Там был приведен реальный тест, помещения в простую БД огромного объема данных. Генерация чисел от 1 до 870 миллиардов по-моему и их запись на диск. Могу ошибиться в порядках.
    Но результат запомнился. В результате получилась таблица объемом 2 ТЕРАБАЙТА. Скорость генерации такой таблицы - 275 секунд. Меньше 5 минут. Задумайтесь, Вы сколько времени копируете с диска на диск один фильм размером 2 Гб. А тут не копирование, а генерация.
    Если найду - ссылку обязательно кину.
    Ради бога, не сравнивайте кустарное производство с огромной давно и успешно работающей структурой.
    Это примерно то же самое, что сказать - я знаю одного гения, он разработал новую операционную систему. Такая, что Windows и Linux вместе нервно курят в сторонке.

    3. Проверять не обязательно. Идеи были разные, в итоге выяснилось, что привлекать движки в помощь совсем не обязательно.

    Да, было бы здорово попробовать.
    Мне бы и самому было бы интересно.
    К сожалению реализовать что-то подобное у меня никак не получится в ближайшее время. Сильно занят по работе, да и компьютерных мощностей не хватит. Есть у меня Athlon 2800+. Только не спрашивайте про количество ядер в нем. Оперативка 500 Мб. Есть еще ноут с процессором Nano. Да, у жены еще есть двухъядерный ноут Феном, но она меня с него гоняет регулярно.
  4. Magystr Новичок

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

    • Новичок
    Рег.:
    19.04.2011
    Сообщения:
    62
    Симпатии:
    14
    Репутация:
    2
    Оффлайн
    Тут на днях беседовал с одним программистом, он очень нахваливал СУБД PostgreSQL. Он с ней постоянно работает, утверждает что она по многим параметрам превосходит ORACLE.
    Вот ссылка
    http://ru.wikipedia.org/wiki/PostgreSQL

    Обратите внимание - на ограничения
    Максимальный размер таблицы - 32 ТБайт.
    Максимум записей в таблице - нет ограничений.

    Я не силен в вычислениях логарифмов, да и таблиц Брадиса нет под рукой.
    Вы действительно считаете, что запрос одной записи по индексу будет длиться часами?
  6. Magystr Новичок

    • Новичок
    Рег.:
    19.04.2011
    Сообщения:
    62
    Симпатии:
    14
    Репутация:
    2
    Оффлайн
    Да, вот обещанная ссылка.
    http://structureddata.org/2010/04/2...tals-of-oracle-data-warehousing-data-loading/

    Конечно же ошибся в цифрах.
    Получается 7,8 млрд записей и "всего" 1Тб. Время 275 секунд. Хоть в чем-то не ошибся.

    Это все при том, что ORACLE не позиционирует свои продукты как суперскоростные.
    У них немного другие области приложения.
  7. MS Михаил Семионенков

    • Команда форума
    Рег.:
    10.02.2006
    Сообщения:
    6.384
    Симпатии:
    2.495
    Репутация:
    163
    Оффлайн
    Kirr, я чуток почитал вашу феню, попробую сказать:

    "Crestbook-подход" - это использование битбаз, при котором DTZ вычисляет играющая программа.
    Эта идея по каким-то причинам забракована сообществом?
  8. Killster Учаcтник

    • Участник
    Рег.:
    12.05.2011
    Сообщения:
    75
    Симпатии:
    0
    Репутация:
    0
    Оффлайн
    Все сильнейшие движки выводят статистику обращений к базам. У тех, кто читает с диска получается порядка 50000-60000 тысяч обращений (за минуту, в базах, хранящихся в памяти (tripple к примеру), на порядки больше), представьте, что было бы, если бы обращение к Налимову бы длилось O(lnN) вместо O(1).
  9. Осипов Юрий Учаcтник

    • Участник
    Рег.:
    18.06.2007
    Сообщения:
    388
    Симпатии:
    394
    Репутация:
    11
    Адрес:
    Правда
    Оффлайн
    Здесь мы немного не понимаем друг друга. У Налимова под индексом нужно понимать просто готовый адрес записи, в которой лежит нужная нам позиция. Вычисляем адрес и лезем по нему в таблицу.
    В СУБД (или отсортированной таблице) адрес записи нам неизвестен. Поэтому нужно искать. Для ускорения поиска (чтобы не читать все подряд) используется индексирование - это вспомогательная таблица, где для каждого значения ключа хранится адрес записи в основной таблице.
    Поиск выполняется методом деления пополам: сначала мы лезем в середину индексной таблицы, смотрим значение ключа и выбрасываем из поиска или верхнюю или нижнюю половину таблицы. Каждая следующая итерация сокращает объем поиска вдвое. В результате и получаем тот самый логарифм по основанию 2. Для 1000 записей получаем примерно 10 итераций, для 1.000.000 имеем 20 итераций, для 1000.000.000 - примерно 30.
    Если вы придумаете другой, более эффективный алгоритм поиска в СУБД, то вы совершите настоящую революцию.
  10. Magystr Новичок

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

    И нельзя ли придумать какой-то механизм, который позволяет распараллелить этот процесс.
    И если это теоретически возможно - уверяю Вас, что это давно уже реализовано.
  11. Magystr Новичок

    • Новичок
    Рег.:
    19.04.2011
    Сообщения:
    62
    Симпатии:
    14
    Репутация:
    2
    Оффлайн
    Вот нашел на форуме MySQL
    http://sqlinfo.ru/forum/viewtopic.php?pid=12341

    Обратите внимание на последний пост.
    У меня нет оснований не доверять сертифицированному специалисту MySQL, который является администратором соответствующей ветки форума.
    Тем более, что это очень хорошо соотносится с моими практическими знаниями.
    Когда производились замеры по скорости работы БД в пустой базе и в базе с 50 000 000 записей.
  12. Killster Учаcтник

    • Участник
    Рег.:
    12.05.2011
    Сообщения:
    75
    Симпатии:
    0
    Репутация:
    0
    Оффлайн
    В эндшпильных базах требуется значительно большая скорость, чем имеется в той же MySQL. Именно скорость случайного чтения.
  13. Magystr Новичок

    • Новичок
    Рег.:
    19.04.2011
    Сообщения:
    62
    Симпатии:
    14
    Репутация:
    2
    Оффлайн
    Случайные запросы не планируются.
    Планируется запрос (даже не выборка) РОВНО ОДНОЙ ЗАПИСИ ИСКЛЮЧИТЕЛЬНО ПО КЛАСТЕРНОМУ КЛЮЧУ.
  14. Killster Учаcтник

    • Участник
    Рег.:
    12.05.2011
    Сообщения:
    75
    Симпатии:
    0
    Репутация:
    0
    Оффлайн
    Да мы все поняли. А теперь подумайте, какое время работы бинарного поиска на данных порядка нескольких миллионов нам требуется уже 21 запрос, конечно, это на первый взгляд не так много, если не вспоминать про количество обращений.

    Число обращений к жесткому диску - это "горлышко бутылки" нынешних эндшпильных баз.
  15. Magystr Новичок

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

    Когда Вас зовут в гости первый раз, Вам сообщают адрес. Предположим, город Новопупкинск, ул. Старокоммунистическая, 28 корп. Б этаж 12 кв 84.
    При этом Вы не будете объезжать всю страну, а посмотрите на карту и доедете именно до этого города. Далее Вы, узнав направление движения, допустим попадете на необходимую улицу в районе дома 44. Вы не будете бегать по всей улице, узнавать с какого номера дома начинается и каким заканчивается улица, чтобы разбить этот интервал пополам, чтобы в 2 раза сузить поиск. Вы повернете (надеюсь) в сторону уменьшения нумерации. Дойдете (или доедите) до необходимого дома. Далее опять же, не будете узнавать общую этажность дома, а сразу сядете на лифт и доедете до нужного этажа, не останавливаясь на промежуточных с целью убедиться, что там нет необходимой нам квартиры. Далее, выйдя из лифта, вы не станете в беспорядке нажимать на все подряд звонки, а нажмете именно тот, рядом с которым необходимый номер квартиры.
    Я ничего не перепутал?
    А вот теперь представьте, что все квартиры во всех домах страны (или мира), это строки таблицы, хранящиеся в одной большой таблице.
    Сколько раз при этом вы заглянули в чужую квартиру и потратили на этом время?
    Как при этом изменился бы ваш маршрут, если бы эта улица была в 10 раз больше?
    А если бы дом был 120-ти этажный то Вам бы непременно пришлось заглянуть в 5-6 квартир, чтобы сузить поиск?
    Примерно также идет поиск в таблице ПО КЛАСТЕРНОМУ КЛЮЧУ.
    Когда идет запрос к БД по определенной позиции, СУБД точно знает, где находится эта запись. В момент, когда эта информация записывалась в таблицу, в ней проставлены соответствующие метки: город, улица, № дома и т.д.
    Причем никаких дополнительных битов и байтов это не требует.
    В самом числе, которое мы ищем СУБД знает, что (условно) первые два бита - это город, следующие три бита - улица, и следующие 3 бита - номер дома и т.д.

    Я открою вам секрет, в современных реляционных БД одна запись таблицы физически может храниться на разных жестких дисках. При этом скорость от этого только возрастет.

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

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

    Существуют фундаментальные законы информатики из которых известно, что минимальный объем информации - 1 бит. Условно говоря ответ - "Да" или "Нет".
    Когда мне говорят, что одна ЗАПИСЬ о шахматной позиции занимает в среднем 1,5 бита - это ..... без комментариев.
    Это примерно то же самое, что сказать, я знаю способ, как одним взвешиванием определить одну фальшивую монету из 4-х.
    Я хорошо понимаю, что ОДНА ЗАПИСЬ в таблице может соответствовать 8-ми позициям, получающимся в результате поворотов, симметричных отображений шахматной доски. И при этом размер этой одной записи - 12 бит. Более того, одна запись может содержать вдвое большее количество информации, если в ней хранить два результата - при ходе белых и ходе черных.
    Но у Налимова это две разные таблицы, судя по названиям файлов.

    Давайте оперировать одинаковыми понятиями.
    Или говорить об общем размере одной и той же таблицы, или сравнить РАЗМЕР ОДНОЙ ЗАПИСИ, но не забывать при этом об общем количестве записей.
  17. Осипов Юрий Учаcтник

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

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

    • Участник
    Рег.:
    18.06.2007
    Сообщения:
    388
    Симпатии:
    394
    Репутация:
    11
    Адрес:
    Правда
    Оффлайн
    Дык, почитайте теорию, и вам станет все понятно. Это не так сложно, как кажется.
    Представьте себе, что у вас есть таблица 3-фигурных эндшпилей в виде массива. Каждая из 3 фигур может занимать одно из 64 полей. Таблица представляет из себя массив размером [64][64][64] (точнее [64][63][62], но можно и меньше). На каждую позицию отводим ровно 1 бит - выиграно или ничья. Вот вам и 1 бит на позицию.
    Для 4-фигурных эндшпилей таблица будет размером [64][63][62][61], для 5-фигурных [64][63][62][61][60] и т.д.
    Главное - адрес вычисляется легко и быстро. И для поиска в таблице нужна всего 1 операция.
  20. Осипов Юрий Учаcтник

    • Участник
    Рег.:
    18.06.2007
    Сообщения:
    388
    Симпатии:
    394
    Репутация:
    11
    Адрес:
    Правда
    Оффлайн
    И где СУБД сохранила и запомнила?

    Давайте сначала.

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

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

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

    • Новичок
    Рег.:
    19.04.2011
    Сообщения:
    62
    Симпатии:
    14
    Репутация:
    2
    Оффлайн
    Еще раз. Оценка позици - 1 бит. Это понятно. Хотя скорее всего нужно 2.
    А размер массива 64*64*64 сколько занимает места? И где он хранится? А ссылка на то, что именно этому элементу массива соответствует именно этот результат?
  24. MS Михаил Семионенков

    • Команда форума
    Рег.:
    10.02.2006
    Сообщения:
    6.384
    Симпатии:
    2.495
    Репутация:
    163
    Оффлайн
    Я это уже прошёл :) , могу поделиться.
    Действительно, на оценку нужно ln3 (примерно 1.5) бита.
    Но это - до сжатия. Трехфигурки сожмутся раз в 5: там два вырожденных эндшпиля и 2 - почти вырожденных. Мы получим 3 позиции на бит. Даже Налимов, где больше информации, чем просто оценка, сжимается до полутора бит на позицию, с эффективностью выше, чем несжатая оценка.
    Как хранить собственно позиции? Ответ - никак.
    Если создатель таблиц и их пользователь пользуются одним и тем же соглашением о порядке хранения информации.
    Соглашение может быть закреплено материально: база должна поставляться вместе с процедурой доступа к произвольному элементу. Сейчас, конечно, я об идеальном мире говорю, но для демонстрации идеи оно вполне подходит.
  25. Magystr Новичок

    • Новичок
    Рег.:
    19.04.2011
    Сообщения:
    62
    Симпатии:
    14
    Репутация:
    2
    Оффлайн
    Прекрасная идея!
    Вместо позиции запрашивать ее порядковый номер, о котором ДОГОВОРИЛИСЬ разработчик таблиц и разработчик движка. Размер в байтах гораздо меньше и соответственно можно хранить больше информации. Это еще один путь к уменьшению размера баз. Дело за малым - кто будет договариваться с Васиком?
    И еще одна проблема. Если он действительно у себя в программе будет хранить такую таблицу соответствия размером 3-4 Байта на позицию - нафига ему запрашивать информацию количеством 1-2 бита?
    Я думаю он, используя возможности своей программы, сам дополнит таблицу в том виде, в каком она ему интересна.

    По этому пути и пошли, как я понимаю, разработчики Айвенго.

    Так что думаю пройдет 2-4 года и все, кому это интересно, встроят СВОИ СОБСТВЕННЫЕ эндшпильные таблицы, по крайней мере 6-ти фигурные в свои движки.
    А кто-то возможно реализует и 7-ми фигурки, хотя бы наиболее интересную их часть.
  26. MS Михаил Семионенков

    • Команда форума
    Рег.:
    10.02.2006
    Сообщения:
    6.384
    Симпатии:
    2.495
    Репутация:
    163
    Оффлайн
    Если играть по битбазам, горлылко не выглядит слишком узким. Сжатые битбазы для 5-фигурок (1G по порядку величины, если я ничего не напутал при грубых прикидках) можно поместить в память целиком. С учетом того, что реально во время работы нужны лишь мизерные доли процента полных таблиц, а именно - таблицы для достигнутной пешечной структуру, то для шестифигурок, и даже семифигурок, все сведётся к загрузке в память нескольких используемых таблиц.
    Скажем, Шкипер оценивает 7_KRPPkrp в 300-400G. Одна пешечная структура - это на 4 порядка меньше, легко можно загрузить за раз в память.
  27. Killster Учаcтник

    • Участник
    Рег.:
    12.05.2011
    Сообщения:
    75
    Симпатии:
    0
    Репутация:
    0
    Оффлайн
    Не очень понятно что можно оптимизировать в битах.. Биты - это конечно хорошо, но мы пытаемся найти пути в DTM базах.. Мы тут делом занимаемся - фантазируем.
  28. MS Михаил Семионенков

    • Команда форума
    Рег.:
    10.02.2006
    Сообщения:
    6.384
    Симпатии:
    2.495
    Репутация:
    163
    Оффлайн
    Во-первых, мне ещё не объяснили популярно, почему битбазы плохи.
    Но, в данном контексте, дело не в конкретном содержании информации, а возможности экономичного вычитывания её с диска. Не вижу, если честно, никаких узких мест.

    Допустим, мы перешли в KRPa3Pb3KRPa5

    Посылаем запросы базе на умомянутую структуру, плюс

    KRPa4Pb3KRPa5
    KRPa3Pb4KRPa5
    KRPa3Pb3KRPa4

    плюс запросы на соответствующие 6-фигурки, и мы в шоколаде, дальше работаем в оперативке.
  29. Magystr Новичок

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

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

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

    Попытки предложить всем вместе построить новую песочницу с привлечением тракторов, бульдозеров, подъемных кранов и другой современной техники для того, чтобы КАКОЙ-ТО ПЕРИОД ВРЕМЕНИ играться в лучших условиях, реально привели к тому, что общим хором мне было сказано, что руки и голова создателя заведомо лучше, чем все что может быть создано другими с привлечением любых средств и умов. Вот только помоги нам грибок поднять повыше, бо создатель че та давно к нам не заходил. А без него никто и не знает, как тут что-то поменять.

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

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

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

    Ребят задумайтесь, кому интересно.
    Windows 95, также как и DOS давно умер.
    Уже давно перешли на 64 разряда. Одноядерным процессором скоро будут пугать детей. Про прогресс в оперативной памяти и жестких дисках в столь интеллектуальном обществе даже как-то и говорить неудобно.
    Все компьютерные идеи, которые были актуальны 10-15-20 лет назад - уже мертвы, потому что это - объективный процесс эволюции.
    Как давно вы открывали предположим HIARCS 5.32? А про программу PcTools что-нибудь помните?
    Я вот лично изредка с большой ностальгией вспоминаю игрушку DIGGER...

    Впрочем нет. Одна идея до сих пор продолжает жить.
    И изменять в ней что-то, также как в учении Маркса-Ленина-Сталина, ничего нельзя по определению.
    "Учение Налимова бессмертно, потому что оно верно".....

    ....
    - А может все-таки поможешь грибок-то поднять хоть немного повыше. Неудобно же. Выросли мы уже.
    Ну ладно, тут заходят иногда добрые дяди, уж они-то обязательно поднимут ....
  30. TopicStarter Overlay

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

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

    Magystr, вы, видимо, идеалист, свято верящий в неудержимость технического прогресса. Прогресс, несомненно, продолжается, но вот распределён он очень неравномерно. Вам приходилось когда-нибудь держать в руках "Искусство Программирования" Кнута? Первая редакция увидела свет в 1968 году, но большая часть приведённых алгоритмов всё ещё актуальна и сегодня, спустя 40 с лишним лет.

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

    Я всё-таки не зря советовал вам пробовать реализовать ваши идеи. Вы бы избавились от иллюзий, и потратили бы ваше время с пользой, вместо того, чтобы тратить наше время на ерунду.
  31. TopicStarter Overlay

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

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

    В третьих. Просто выкидывание матов в более 50 ходов - не эквивалентно метрике DTM50. Построение таблиц в DTM50 - вообще очень нетривиальный процесс, на порядок сложнее чем, например, DTZ50.
  32. TopicStarter Overlay

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

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

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

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

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

    В многофигурных эндшпилях это может быть вполне актуальной проблемой.
  33. TopicStarter Overlay

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

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

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

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

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

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

  35. TopicStarter Overlay

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

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

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

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

    Часто есть противоречие между эффективностью и универсальностью решения. Реляционные базы данных - универсальны. Базы данных специального назначения - эффективны. И те и другие продолжат существовать и решать свои задачи.

    Мои таблицы - компактнее Налимовских. Но неизвестно, будет ли у меня время и силы перенести мои методы на доску 8х8.

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

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

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