Представление дерева поиска

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

  1. TopicStarter Overlay

    atoku Модератор

    • Команда форума
    Member Since:
    05.02.2006
    Message Count:
    2.949
    Likes Received:
    9
    Репутация:
    0
    Location:
    USA
    Оффлайн
    Читая разные статьи, вдруг обнаружил, что народ не хранит все дерево, а вместо того, хранит просто ходы, которые привели из корня к конкретной позиции. Это что так и надо??? Все ли так делают и есть ли альтернативы? Кажется гораздо удобнее хранить все позиции.

    Я сейчас совершенно не говорю про хэш таблицы, в них я еще не разбирался.
    atoku, 7 Jul 2006
    #1

  2. WinPooh В.М.

    • Команда форума
    Member Since:
    13.02.2006
    Message Count:
    9.492
    Likes Received:
    3.122
    Репутация:
    95
    Location:
    Москва
    Оффлайн
    А память выделять под дерево кто будет, Пушкин? А время этому Пушкину кто выделит?
    Да и потом, самые распространённые tree-traversing алгоритмы совершенно не требуют хранить всё дерево. Во всяком случае, из класса depth-first.

    А хэш-таблица - да, это просто способ хранить дополнительно отдельные, наиболее важные для нас, узлы дерева.

    Надо ещё упомянуть такие алгоритмы, как conspiracy search. Вот в их реализации, да, иногда приходится хранить именно большие поддеревья. Но эти алгоритмы лежат несколько в стороне он альфа-бета мэйнстрима.
    WinPooh, 7 Jul 2006
    #2

  3. WinPooh В.М.

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

  4. krey Михаил Кройтор

    • Команда форума
    Member Since:
    10.04.2006
    Message Count:
    3.709
    Likes Received:
    50
    Репутация:
    1
    Location:
    Кишинев
    Оффлайн
    я вот что подумал... а почему бы Пушкину и не хранить все дерево?! :D
    krey, 7 Jul 2006
    #4

  5. WinPooh В.М.

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

  6. WinPooh В.М.

    • Команда форума
    Member Since:
    13.02.2006
    Message Count:
    9.492
    Likes Received:
    3.122
    Репутация:
    95
    Location:
    Москва
    Оффлайн
    Вот простая оценка. Пусть для хранения одной позиции нам требуется 64 байта (требование, кстати, заниженное).
    Тогда при типичной для современных персоналок скорости в 500 тысяч позиций в секунду дерево будет расти со скоростью 32 Мегабайта/сек. Таким образом, оперативная память размером в 1 Гигабайт будет "съедена" примерно за пол-минуты...
    WinPooh, 7 Jul 2006
    #6

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

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

  8. WinPooh В.М.

    • Команда форума
    Member Since:
    13.02.2006
    Message Count:
    9.492
    Likes Received:
    3.122
    Репутация:
    95
    Location:
    Москва
    Оффлайн
    Ну, 32 байта - какая разница... 64 клетки * минимум 4 бита для каждой.
    Порядок величин сохраняется. За минуту заполнится, а не за 30 секунд...
    WinPooh, 7 Jul 2006
    #8

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

    • Заслуженный
    • Ветеран
    • Старожил
    Member Since:
    02.05.2006
    Message Count:
    6.811
    Likes Received:
    96
    Репутация:
    3
    Location:
    Санкт-Петербург
    Оффлайн
    Первая - массив (дерево) позиций, реализуем через черно-красное, либо AVL дерево.
    В каждом узле храним Хеш (64 бита), ссылку на упорядоченный список ходов (32 бита), оценку (макс 32 бита вместе с глубиной), то есть на каждую позицию 16 байт вроде достаточно.
    Дерево строится по Хешу (нужно для перекрестных позиций)
    Список ходов - линейный массив, хранит Количество ходов в позиции, упорядоченные ходы. Вместе с ходом хранится ссылка на Позицию (не Хеш, а ссылка) из дерева. 16 бит на ход, 32 бита на ссылку - итого.
    128 бит на каждую позицию.
    48 бит на каждый ход.
    Тормоза будут очень жуткие (за счет поиска и добавлений узлов в AVL дереве для каждого сгенерированного хода из каждой "новой" позиции)
    NS, 7 Jul 2006
    #9

  10. WinPooh В.М.

    • Команда форума
    Member Since:
    13.02.2006
    Message Count:
    9.492
    Likes Received:
    3.122
    Репутация:
    95
    Location:
    Москва
    Оффлайн
    Ага, и непонятно, ради чего всё это нужно и как это улучшит поиск.
    WinPooh, 7 Jul 2006
    #10

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

    • Заслуженный
    • Ветеран
    • Старожил
    Member Since:
    02.05.2006
    Message Count:
    6.811
    Likes Received:
    96
    Репутация:
    3
    Location:
    Санкт-Петербург
    Оффлайн
    Для ускорения схемы можно сделать "страничный механизм + список, но будет ли это быстрее?
    +Я забыл 64 бита на две ссылки для организации бинарного дерева.
    NS, 7 Jul 2006
    #11

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

    • Заслуженный
    • Ветеран
    • Старожил
    Member Since:
    02.05.2006
    Message Count:
    6.811
    Likes Received:
    96
    Репутация:
    3
    Location:
    Санкт-Петербург
    Оффлайн
    Улучшит поиск здорово, так как упорядочены будет ВСЕ ходы и для ВСЕХ позиций, но при этом упираемся в ограничение на размер памяти + на снижение быстрордействия на организацию хренения в ХЕШ-е (Дереве, либо другой структуре) всех позиций - доступа к структуре, и механизме добавления данных в ХЕШ.

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

    Есно саму схему хранения нужно продумать получше.
    NS, 7 Jul 2006
    #12

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

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

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

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

    atoku Модератор

    • Команда форума
    Member Since:
    05.02.2006
    Message Count:
    2.949
    Likes Received:
    9
    Репутация:
    0
    Location:
    USA
    Оффлайн
    Очень интересно. То есть народ хранит серии ходов. Ну, положим, так и правда много меньше памяти уходит, а сделать ход куда быстрее, чем оценить позицию...

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

    Как вы делаете, если не секрет?
    atoku, 8 Jul 2006
    #15

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

    • Заслуженный
    • Ветеран
    • Старожил
    Member Since:
    02.05.2006
    Message Count:
    6.811
    Likes Received:
    96
    Репутация:
    3
    Location:
    Санкт-Петербург
    Оффлайн
    ? Как это никто не пишет?
    Везеде описана типовая организаций хеша.
    1. Хранится 64-битный хеш,
    2. Хранится лучший ход (если он есть)
    3. Хранится Оценка
    4. Хранится тип оценки
    5. Хранится Глубина (Depth) Для оценки/Лучшего хода.
    6. Хранится инфа для перезаписи.

    Структура хранения - массив на N элементов.
    Место- куда записывается инфа в массиве - (Хеш Мод N)

    Независимо от того, с какой стороны ты к позиции подлезешь :)))
    Хеш будет одинаковый :)
    NS, 8 Jul 2006
    #16
  17. TopicStarter Overlay

    atoku Модератор

    • Команда форума
    Member Since:
    05.02.2006
    Message Count:
    2.949
    Likes Received:
    9
    Репутация:
    0
    Location:
    USA
    Оффлайн
    Стоп стоп стоп! Мне, чайнику, надо подробнее :). Какой-такой хеш? Я до хеша еще не дошел в своих изысканиях на данную тему. Пока у меня есть граф позиций, из вершины в вершину путь описан легальным ходом. Позиции, как я понял (то есть вершины) хранить не надо, достаточно записать "ребра" - ходы. Что я представляю себе не так?
    atoku, 8 Jul 2006
    #17

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

    • Заслуженный
    • Ветеран
    • Старожил
    Member Since:
    02.05.2006
    Message Count:
    6.811
    Likes Received:
    96
    Репутация:
    3
    Location:
    Санкт-Петербург
    Оффлайн
    http://www.brucemo.com/compchess/programming/zobrist.htm
    Зачем полное дерево? Ход, опровергнутый по Альфе - не несет никакой смысловой нагрузки.
    Граф строить не надо - достаточно хранить Хеш позиции. Исполнив ход, и взяв ХЕШ получившейся позиции, мы можем посмотреть, встречалась ли эта позиция ранее.
    NS, 8 Jul 2006
    #18

Share This Page