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

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

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

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

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

Магистр!

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

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

Нисколько не подвергая Ваши выводы, хотел бы заметить.
У каждого из решений есть плюсы и минусы.
Вы В ЭТОМ посте весьма однобоко рассматриваете их.

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. Да, у жены еще есть двухъядерный ноут Феном, но она меня с него гоняет регулярно.

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

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

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

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

Да, вот обещанная ссылка.
http://structureddata.org/2010/04/2...tals-of-oracle-data-warehousing-data-loading/

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

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

Все сильнейшие движки выводят статистику обращений к базам. У тех, кто читает с диска получается порядка 50000-60000 тысяч обращений (за минуту, в базах, хранящихся в памяти (tripple к примеру), на порядки больше), представьте, что было бы, если бы обращение к Налимову бы длилось O(lnN) вместо O(1).

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

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

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

Вот нашел на форуме MySQL
http://sqlinfo.ru/forum/viewtopic.php?pid=12341

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

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

Случайные запросы не планируются.
Планируется запрос (даже не выборка) РОВНО ОДНОЙ ЗАПИСИ ИСКЛЮЧИТЕЛЬНО ПО КЛАСТЕРНОМУ КЛЮЧУ.

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

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

Я, честно, уже устал устраивать уроки ликбеза. Становится откровенно скушно.
Ну задайте в поисковике "Кластерный ключ" и посмотрите результаты.

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

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

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

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

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

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

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

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

Дык, почитайте теорию, и вам станет все понятно. Это не так сложно, как кажется.
Представьте себе, что у вас есть таблица 3-фигурных эндшпилей в виде массива. Каждая из 3 фигур может занимать одно из 64 полей. Таблица представляет из себя массив размером [64][64][64] (точнее [64][63][62], но можно и меньше). На каждую позицию отводим ровно 1 бит - выиграно или ничья. Вот вам и 1 бит на позицию.
Для 4-фигурных эндшпилей таблица будет размером [64][63][62][61], для 5-фигурных [64][63][62][61][60] и т.д.
Главное - адрес вычисляется легко и быстро. И для поиска в таблице нужна всего 1 операция.

И где СУБД сохранила и запомнила?

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

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

1 бит - результат позиции. А сама позиция сколько места занимает?

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

Еще раз. Оценка позици - 1 бит. Это понятно. Хотя скорее всего нужно 2.
А размер массива 64*64*64 сколько занимает места? И где он хранится? А ссылка на то, что именно этому элементу массива соответствует именно этот результат?

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

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

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

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

В общем считаю, что пора подводить некие общие итоги совместного обсуждения. По крайней мере для себя лично.

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

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

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

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

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

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

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

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

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