Структуры данных для дебютной библиотеки

Discussion in 'Машинное отделение' started by NS, 26 Jul 2006.

  1. TopicStarter Overlay

    NS Нефёдов Сергей

    • Заслуженный
    • Ветеран
    • Старожил
    Member Since:
    02.05.2006
    Message Count:
    6.811
    Likes Received:
    96
    Репутация:
    3
    Location:
    Санкт-Петербург
    Оффлайн
    В каждом узле - Список ходов, с каждого хода в списке - ссылка на Узел. :)
    NS, 26 Jul 2006
    #1

  2. WinPooh В.М.

    • Команда форума
    Member Since:
    13.02.2006
    Message Count:
    9.492
    Likes Received:
    3.122
    Репутация:
    95
    Location:
    Москва
    Оффлайн
    Непонятно, как перестановки ходов тогда отслеживать. Вроде 1. e4 e6 2. d4 и 1. d4 e6 2. e4.
    Я выбрал другую схему - храним хэш код позиции плюс статистику. При поиске хода в книге генерим все возможные ходы, и смотрим какие из них присутствуют. Для хранения используем бинарное дерево.
    WinPooh, 26 Jul 2006
    #2
  3. TopicStarter Overlay

    NS Нефёдов Сергей

    • Заслуженный
    • Ветеран
    • Старожил
    Member Since:
    02.05.2006
    Message Count:
    6.811
    Likes Received:
    96
    Репутация:
    3
    Location:
    Санкт-Петербург
    Оффлайн
    Я в 1С 7.7 Тоже использовал Хеш... (Хотя там Был не совсем Хеш, а полностью позиция :))
    Достаточно отсортировать по возрастанию, и бинарным поиском...
    Если Без Хеша, а ссылками - то занимает меньше места и быстрее работает (не нужен бинарный поиск), а перекрестные позиции можно отслеживать обработкой (Обработкой сворачиваются ссылки на одинаковые позиции - то есть в разных узлах, возможно с разных ходов - идет ссылка на один и тот-же узел)
    NS, 26 Jul 2006
    #3

  4. WinPooh В.М.

    • Команда форума
    Member Since:
    13.02.2006
    Message Count:
    9.492
    Likes Received:
    3.122
    Репутация:
    95
    Location:
    Москва
    Оффлайн
    Ещё есть соображение, чтобы работа с книгой в памяти по минимуму отличалась от работы с файлом - т.е. не всегда же книгу целиком в памяти держать... Сейчас в Греке она целиком в памяти только на этапе генерации, потом пишем в файл (уже в сортированном по хэшу виде), и дальше - бинарный поиск с помощью файловых операций.
    WinPooh, 26 Jul 2006
    #4
  5. TopicStarter Overlay

    NS Нефёдов Сергей

    • Заслуженный
    • Ветеран
    • Старожил
    Member Since:
    02.05.2006
    Message Count:
    6.811
    Likes Received:
    96
    Репутация:
    3
    Location:
    Санкт-Петербург
    Оффлайн
    Бинарный с помощью файловых... Точно так-же в Памяти окажется, только GUI обманешь :) (в Файловом Кеше всё сидеть будет)
    NS, 26 Jul 2006
    #5

  6. WinPooh В.М.

    • Команда форума
    Member Since:
    13.02.2006
    Message Count:
    9.492
    Likes Received:
    3.122
    Репутация:
    95
    Location:
    Москва
    Оффлайн
    Ты хочешь сказать, что если у меня файл в 100 мегабайт, и я говорю:

    FILE* psrc = fopen("file", "rb");
    fseek(psrc, 500000, SEEK_SET);
    fread(bla-bla-bla);

    - то все 100 мегабайт окажутся у меня в памяти? Не верю.
    WinPooh, 26 Jul 2006
    #6

  7. WinPooh В.М.

    • Команда форума
    Member Since:
    13.02.2006
    Message Count:
    9.492
    Likes Received:
    3.122
    Репутация:
    95
    Location:
    Москва
    Оффлайн
    В кэше будут реально сидеть только те позиции, которые я запросил из файла. Т.е. не более чем два десятка позиций на каждый поиск.
    WinPooh, 26 Jul 2006
    #7
  8. TopicStarter Overlay

    NS Нефёдов Сергей

    • Заслуженный
    • Ветеран
    • Старожил
    Member Since:
    02.05.2006
    Message Count:
    6.811
    Likes Received:
    96
    Репутация:
    3
    Location:
    Санкт-Петербург
    Оффлайн
    Зачем дебютная на 100 Мегабайт?
    NS, 26 Jul 2006
    #8
  9. TopicStarter Overlay

    NS Нефёдов Сергей

    • Заслуженный
    • Ветеран
    • Старожил
    Member Since:
    02.05.2006
    Message Count:
    6.811
    Likes Received:
    96
    Репутация:
    3
    Location:
    Санкт-Петербург
    Оффлайн
    2 десятка позиций из разных мест :) по 64 Килобайта на позицию (размер записи в Кэше) - 1.3 метра.
    NS, 26 Jul 2006
    #9

  10. WildCat Коршунов Игорь

    • Команда форума
    Member Since:
    04.05.2006
    Message Count:
    3.599
    Likes Received:
    4
    Репутация:
    0
    Location:
    Гомель
    Оффлайн
    Если книга очень большая (гигабайты), то в кеше будет очень малая ее часть. И бинарный поиск будет работать очень быстро.

    А зачем отказываться от прелестей Си++? Ведь можно на С++ кодить в силе Си, когда это необходимо. И пользоваться такими вещами, как std::map, если они нужны.
    WildCat, 26 Jul 2006
    #10
  11. TopicStarter Overlay

    NS Нефёдов Сергей

    • Заслуженный
    • Ветеран
    • Старожил
    Member Since:
    02.05.2006
    Message Count:
    6.811
    Likes Received:
    96
    Репутация:
    3
    Location:
    Санкт-Петербург
    Оффлайн
    Если Книга Гигабайты, и выборка идёт из 20 мест - то будет сидеть в Кеше чуть больше метра, но чтоб провести каждый бинарный поиск - на миллиарде записей Это 30 обращений в разные места - итого в Кэше будет храниться 30*20=600 Блоков.
    То есть выборка идёт ведь не из 20 мест, а из 600!!!
    NS, 26 Jul 2006
    #11

  12. WinPooh В.М.

    • Команда форума
    Member Since:
    13.02.2006
    Message Count:
    9.492
    Likes Received:
    3.122
    Репутация:
    95
    Location:
    Москва
    Оффлайн
    Так это пусть у операционной системы голова болит. На то он и кэш - чтобы она за ним следила, и время от времени обновляла. Он так или иначе присутствует, файлы-то всё время кто-то читает :)
    WinPooh, 26 Jul 2006
    #12

  13. WildCat Коршунов Игорь

    • Команда форума
    Member Since:
    04.05.2006
    Message Count:
    3.599
    Likes Received:
    4
    Репутация:
    0
    Location:
    Гомель
    Оффлайн
    Хранить или не хранить куски файла в кеше - это решает система. Я думаю она это делает только если есть лишняя память. Так что не стоит очень беспокоиться об этом.
    По-любому загружать большие файлы в память плохо. По себе знаю. Был как-то у меня комп с 32 МБ ОЗУ и сделали мне дебютник > 10 Мб. И прога загружала его в память. После этого компу становилось грустно и было совсем не до игры двух движков.
    WildCat, 26 Jul 2006
    #13
  14. TopicStarter Overlay

    NS Нефёдов Сергей

    • Заслуженный
    • Ветеран
    • Старожил
    Member Since:
    02.05.2006
    Message Count:
    6.811
    Likes Received:
    96
    Репутация:
    3
    Location:
    Санкт-Петербург
    Оффлайн
    Так зачем тогда издеваться над системой? Врятли Библиотека будет больше десятка мегабайт - почему-же её тогда не хранить в памяти?
    Вот - Шреддер - Эндшпильные Таблицы в памяти хранит. (хотя тут конечно скорость доступа намного важнее, но и объемы значительно больше)
    Намного лучше и для Кэша, и для быстродействия будет если всё-таки хранить дерево в виде дерева (с ссылками)
    (тогда уже можно и не грузить в память)
    NS, 26 Jul 2006
    #14
  15. TopicStarter Overlay

    NS Нефёдов Сергей

    • Заслуженный
    • Ветеран
    • Старожил
    Member Since:
    02.05.2006
    Message Count:
    6.811
    Likes Received:
    96
    Репутация:
    3
    Location:
    Санкт-Петербург
    Оффлайн
    У многих движков нижний предел размера Хеша больше 32метров :) (у меня ровно 32)
    NS, 26 Jul 2006
    #15

  16. WildCat Коршунов Игорь

    • Команда форума
    Member Since:
    04.05.2006
    Message Count:
    3.599
    Likes Received:
    4
    Репутация:
    0
    Location:
    Гомель
    Оффлайн
    Может быть сегодня 32 и прокатит. Но 10 лет назад это было не допустимо. Все равно, что сейчас минимально брать 8 Гб.
    WildCat, 26 Jul 2006
    #16

  17. WinPooh В.М.

    • Команда форума
    Member Since:
    13.02.2006
    Message Count:
    9.492
    Likes Received:
    3.122
    Репутация:
    95
    Location:
    Москва
    Оффлайн
    Да, я думал о структуре со ссылками в файле. Но тогда опять вылезает вопрос с транспозициями + процедура записи в файл при генерации усложняется.
    WinPooh, 26 Jul 2006
    #17
  18. TopicStarter Overlay

    NS Нефёдов Сергей

    • Заслуженный
    • Ветеран
    • Старожил
    Member Since:
    02.05.2006
    Message Count:
    6.811
    Likes Received:
    96
    Репутация:
    3
    Location:
    Санкт-Петербург
    Оффлайн
    Записыывать в Файл уже полностью сформированное дерево (в случае изменений перезаписывать) - а тут даже не нужен обход Дерева, так как физически оно хранится в линейном массиве (в двух, если списки ходов храним в отдельной структуре)
    В случае изменений (если файл в виде Хеш таблицы) - то практически идёт та-же перезапись всего Файла из-за
    1. Сортировки
    2. Изменения размера записи (Может поменяться в дереве количество ходов в позиции)
    NS, 26 Jul 2006
    #18

  19. WinPooh В.М.

    • Команда форума
    Member Since:
    13.02.2006
    Message Count:
    9.492
    Likes Received:
    3.122
    Репутация:
    95
    Location:
    Москва
    Оффлайн
    Запись имеет фиксированный размер. Я не храню ходы. Я храню позиции после этих ходов.
    WinPooh, 26 Jul 2006
    #19
  20. TopicStarter Overlay

    NS Нефёдов Сергей

    • Заслуженный
    • Ветеран
    • Старожил
    Member Since:
    02.05.2006
    Message Count:
    6.811
    Likes Received:
    96
    Репутация:
    3
    Location:
    Санкт-Петербург
    Оффлайн
    Ход - по максимуму 14 бит - хеш по минимуму 64. :)
    Так если у нас хороший ход был один, то позиция после хода одна, а если в дебютном дереве два хода, то позиции две...
    К чему привязывать ВЕСА и СТАТИСТИКУ ходов в дебютной библиотеке?
    NS, 26 Jul 2006
    #20

  21. WinPooh В.М.

    • Команда форума
    Member Since:
    13.02.2006
    Message Count:
    9.492
    Likes Received:
    3.122
    Репутация:
    95
    Location:
    Москва
    Оффлайн
    Пример. Первый ход e2e4, после него белые взяли 60% очков. Ход d2d4 - 55% очков.
    Делаем эти ходы на внутренней доске, берем у получившихся позиций хэши, и пишем в книгу записи:

    {хэш после е4; 60%}
    {хэш после d4; 55%}

    Дальше понятно?
    WinPooh, 26 Jul 2006
    #21

  22. WinPooh В.М.

    • Команда форума
    Member Since:
    13.02.2006
    Message Count:
    9.492
    Likes Received:
    3.122
    Репутация:
    95
    Location:
    Москва
    Оффлайн
    Когда надо сыграть по книге из некоторой позиции:

    а) генерим все ходы
    б) по очереди делаем их на внутренней доске, берем для каждого потомка хэш
    в) лезем в книгу, ищем запись с этим хэшом - для некоторых найдем, для некоторых нет
    г) среди тех, для кого нашли, выбираем наилучший
    WinPooh, 26 Jul 2006
    #22
  23. TopicStarter Overlay

    NS Нефёдов Сергей

    • Заслуженный
    • Ветеран
    • Старожил
    Member Since:
    02.05.2006
    Message Count:
    6.811
    Likes Received:
    96
    Репутация:
    3
    Location:
    Санкт-Петербург
    Оффлайн
    То есть мы храним статистику не для хода, а только для позиции....
    Тогда получается не 20 поисков, а значительно больше - Мы в каждой позиции генерируем все ходы, и для каждой получившейся позиции - ищем её в Файле, и если она есть - то берем статистику? Я правильно понял?
    NS, 26 Jul 2006
    #23

  24. WinPooh В.М.

    • Команда форума
    Member Since:
    13.02.2006
    Message Count:
    9.492
    Likes Received:
    3.122
    Репутация:
    95
    Location:
    Москва
    Оффлайн
    Да, именно так. Поисков становится действительно больше. Но реализация проще :)
    WinPooh, 26 Jul 2006
    #24
  25. TopicStarter Overlay

    NS Нефёдов Сергей

    • Заслуженный
    • Ветеран
    • Старожил
    Member Since:
    02.05.2006
    Message Count:
    6.811
    Likes Received:
    96
    Репутация:
    3
    Location:
    Санкт-Петербург
    Оффлайн
    Кому как - для меня однинакова, и книга с статистикой по ходам более гибка, и просто сама по себе лучше! :)
    Плюс - если организовывать без Хеша - то намного меньше обращений (получается в 40(количество ходов)*30 (бинарный поиск на миллионе записей)=1200 раз), а чтение из файла в любом случае идет блоками. (а в схеме с большим количеством поисков - все данные в разных местах файла)
    NS, 26 Jul 2006
    #25

  26. WinPooh В.М.

    • Команда форума
    Member Since:
    13.02.2006
    Message Count:
    9.492
    Likes Received:
    3.122
    Репутация:
    95
    Location:
    Москва
    Оффлайн
    Для надёжности ещё можно проверять присутствие исходной позиции в книге.
    Чтобы избежать варианта 1. e4 e5 2. Nf3 a6 3. Bb5 Nc6??, с переходом в книгу (пример из Хьятта).
    Но тогда не будут отслеживаться многие перестановки ходов.
    WinPooh, 26 Jul 2006
    #26

  27. WinPooh В.М.

    • Команда форума
    Member Since:
    13.02.2006
    Message Count:
    9.492
    Likes Received:
    3.122
    Репутация:
    95
    Location:
    Москва
    Оффлайн
    А кто-нибудь знает, как устроены форматы коммерческих книг, от Chessbase?
    WinPooh, 26 Jul 2006
    #27
  28. TopicStarter Overlay

    NS Нефёдов Сергей

    • Заслуженный
    • Ветеран
    • Старожил
    Member Since:
    02.05.2006
    Message Count:
    6.811
    Likes Received:
    96
    Репутация:
    3
    Location:
    Санкт-Петербург
    Оффлайн
    А вот для этого - к каждой позиции навесить дополнительно Хеш, и после вылета из книги до определенного хода - искать Хеш позиции в книге. Удобней наверно сделать с Индексным файлом (Хотя никто не мешает отсортировать Дерево с пересчетом ссылок БЕЗ индексного файла)
    NS, 26 Jul 2006
    #28
  29. TopicStarter Overlay

    NS Нефёдов Сергей

    • Заслуженный
    • Ветеран
    • Старожил
    Member Since:
    02.05.2006
    Message Count:
    6.811
    Likes Received:
    96
    Репутация:
    3
    Location:
    Санкт-Петербург
    Оффлайн
    Порыскал по просторам - "с ходу" описание формата не нашел.
    NS, 26 Jul 2006
    #29

Share This Page