Hash позиции

Тема в разделе "Машинное отделение", создана пользователем Binary, 17 окт 2006.

  1. WinPooh В.М.

    • Команда форума
    Рег.:
    13.02.2006
    Сообщения:
    8.964
    Симпатии:
    2.172
    Репутация:
    85
    Адрес:
    Москва
    Оффлайн
    Мегабайты - это мегабайты. "Миллионы" байтов, а не "миллионы" записей.
    Правильно второе.

    Что принять за "миллион" - решайте сами :)
  2. варяг Учаcтник

    • Участник
    Рег.:
    23.10.2006
    Сообщения:
    98
    Симпатии:
    0
    Репутация:
    0
    Адрес:
    Гонду-Раша
    Оффлайн
    Как расшифровывается LMR и где можно достать описание метода?
  3. NS Нефёдов Сергей

    • Заслуженный
    • Ветеран
    Рег.:
    02.05.2006
    Сообщения:
    6.811
    Симпатии:
    96
    Репутация:
    3
    Адрес:
    Санкт-Петербург
    Оффлайн
    LMR - Late Move Reduction
    Сокращение перебора на ходах от которых мы ничего не ожидаем... (верояность что он опровергающий весьма мала)
    Обычно это нетактические и плохие по истории ходы (не взятие, не шах, не превращение, не киллер, не ход из Хеша).
    Описание его весьма простое - на плохих ходах сокращаем, но если вдруг "сокращенный" ход оказался опровергающим - считаем на полную глубину.
  4. варяг Учаcтник

    • Участник
    Рег.:
    23.10.2006
    Сообщения:
    98
    Симпатии:
    0
    Репутация:
    0
    Адрес:
    Гонду-Раша
    Оффлайн
    расскажите, как боретесь с аномалиями хэш-таблиц?
  5. WildCat Коршунов Игорь

    • Команда форума
    Рег.:
    04.05.2006
    Сообщения:
    3.599
    Симпатии:
    3
    Репутация:
    0
    Адрес:
    Гомель
    Оффлайн
    Что ты имеешь в виду? Но все равно я никак не борюсь.
  6. варяг Учаcтник

    • Участник
    Рег.:
    23.10.2006
    Сообщения:
    98
    Симпатии:
    0
    Репутация:
    0
    Адрес:
    Гонду-Раша
    Оффлайн
    Все, разобрался. Был баг с занесением информации в хэш
  7. TopicStarter Overlay

    Binary Учаcтник

    • Участник
    Рег.:
    27.08.2006
    Сообщения:
    135
    Симпатии:
    0
    Репутация:
    0
    Адрес:
    Мытищи
    Оффлайн
    прикручиваю к движку Transposition tables , в итоге играет даже хуже ...

    у меня к вам 2 вопроса
    1) на сколько должно сократиться время перебора по сравнению с без таблиц?
    скажем , у меня есть тестовая спокойная позиция , в которой без транс таблиц считает 7 ply за 0.700 сек -
    что следует ожидать?

    2) после нахождения хода из транс таблиц у меня происходит срез , поэтому PV не может ээ... "построиться"
    :) , скажем так ... в Fruit реализованы ф-ции pv_cat и pv_fill , но принцип их я так и не постиг ... одних search -ей там штук 10! - попробуй разберись без бутылки!...
    принцип вроде уловил :
    в функции итеративного углубления (в TSCP - "think()" наз - ся) после каждого вызова search(... , depth)
    вызываю ф-цию , которая ищет такущую позицию в тр . табл . делает ход из нее , заносит в PV , снова ищет в таблице и тд. пока есть ход в таблицах...
    вопрос : как это реализовать правильно?
  8. WinPooh В.М.

    • Команда форума
    Рег.:
    13.02.2006
    Сообщения:
    8.964
    Симпатии:
    2.172
    Репутация:
    85
    Адрес:
    Москва
    Оффлайн
    Рекомендую начинать прикручивать TT c простейшего варианта: в хэше хранится только лучший ход, никакая оценка из хэш-узла не используется.
    Только после того, как убедитесь, что нет багов, переходите к использованию оценки из хэша.
    Типичная ошибка - использование оценки с предыдущей итерации или из предыдущего поиска без надлежащей проверки глубины, типа узла и границ.
  9. WildCat Коршунов Игорь

    • Команда форума
    Рег.:
    04.05.2006
    Сообщения:
    3.599
    Симпатии:
    3
    Репутация:
    0
    Адрес:
    Гомель
    Оффлайн
    Где-то баги у тебя.

    1. у меня на начальной позиции 15 полуходов считает за 8.19 сек.
    51.94 - хеш не возвращает оценку и лучшие ходы
    29.15 - хеш не возвращает оценку
    15.54 - хеш не возвращает лучшие ходы

    2. PV не так уж важен. Если сложно его выковырять из хеша, то можешь его получать с помощью треугольной матрицы, как в TSCP.
  10. TopicStarter Overlay

    Binary Учаcтник

    • Участник
    Рег.:
    27.08.2006
    Сообщения:
    135
    Симпатии:
    0
    Репутация:
    0
    Адрес:
    Мытищи
    Оффлайн
    в принципе ТТ как раз работали без сбоев ... даже bench тот самый они выигрывают у обычной версии (где-то 0.600) только вот партии сливает , считает не так глубоко - я думаю шибка в неиспользовании PV
    первые 4 полухода из 6 (играют по 30 сек/партия) он находит в ТТ и не пишет в PV ничего , потом PV-хода-то
    нет ... и он задумывается надолго :rolleyes:
    его вывод в оболочку выглядит так (движок WB)
    Код:
    1 27 27      100
    2 27 27      100
    3 27 27      100
    4 27 27      100
    5 62 34 326439 b4c3 e5c6 b7c6 b2c3 h5e2
    6 62 87 906698 b4c3 e5c6 b7c6 b2c3 h5e2 d1e2 a5c3
  11. TopicStarter Overlay

    Binary Учаcтник

    • Участник
    Рег.:
    27.08.2006
    Сообщения:
    135
    Симпатии:
    0
    Репутация:
    0
    Адрес:
    Мытищи
    Оффлайн
    PV у меня сделан по-аналогии с TSCP - матрица PV[max_ply][max_ply] // max_ply = 32

    в начале search() в Fruit есть
    Код:
    // transposition table
    
       trans_move = MoveNone;
    
       if (UseTrans && depth >= TransDepth) {
    
          if (trans_retrieve(Trans,board->key,&trans_move,&trans_min_depth,&trans_max_depth,&trans_min_value,&trans_max_value)) {
    
             // trans_move is now updated
    
             if (node_type != NodePV) {
    
                if (UseMateValues) {
    
                   if (trans_min_value > +ValueEvalInf && trans_min_depth < depth) {
                      trans_min_depth = depth;
                   }
    
                   if (trans_max_value < -ValueEvalInf && trans_max_depth < depth) {
                      trans_max_depth = depth;
                   }
                }
    
                min_value = -ValueInf;
    
                if (DEPTH_MATCH(trans_min_depth,depth)) {
                   min_value = value_from_trans(trans_min_value,height);
                   if (min_value >= beta) return min_value;
                }
    
                max_value = +ValueInf;
    
                if (DEPTH_MATCH(trans_max_depth,depth)) {
                   max_value = value_from_trans(trans_max_value,height);
                   if (max_value <= alpha) return max_value;
                }
    
                if (min_value == max_value) return min_value; // exact match
             }
          }
       }
    всего 3 отсечения :
    какие из них причастны к PV ?
    я так подумал , что 3 и ,возможно, 2 - ;) свои ТТ организовал по - фруктовски ... вот только не до конца догнал
    необходимость хранить та min_value и vax_value одновременно ... может кто растолкует?
  12. TopicStarter Overlay

    Binary Учаcтник

    • Участник
    Рег.:
    27.08.2006
    Сообщения:
    135
    Симпатии:
    0
    Репутация:
    0
    Адрес:
    Мытищи
    Оффлайн
    шаманил я тут шаманил ...
    в search() вместо вызова quiescense() вставил сразу evaluate() - тем самым убрал некоторую неизвестность глубины перебора
    убрал sort_PV() , чтоб не сортировала ходы по принадлежности к PV -
    только тогда TT - версия стала где-то в 2 раза быстрее такой же "искалеченной" обычной
  13. WildCat Коршунов Игорь

    • Команда форума
    Рег.:
    04.05.2006
    Сообщения:
    3.599
    Симпатии:
    3
    Репутация:
    0
    Адрес:
    Гомель
    Оффлайн
    Делай лучше то, что догоняешь. А Фруктовсий код ты явно не понял, т.к. задаешь какие-то неадекватные вопросы.
    В Фрукте отсечения по хешу вообще не причастны к PV.
  14. NS Нефёдов Сергей

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

    • Заслуженный
    • Ветеран
    Рег.:
    02.05.2006
    Сообщения:
    6.811
    Симпатии:
    96
    Репутация:
    3
    Адрес:
    Санкт-Петербург
    Оффлайн
    Делай стандартную схему - глубина оценки, тип оценки (<=,==,>=), сама оценка.
    И не PV ветвях, если глубина нормальная, и оценка выходит за границу Альфа/Бета тогда отсечение...
    Если типоценки "==" или "<=" тогда
    Если ОценкаизХеша<=Альфа Тогда
    Отсекаем с ОценкаИзХеша

    Если типоценки "==" или ">=" тогда
    Если ОценкаизХеша=>Бета Тогда
    Отсекаем с ОценкаИзХеша

    //

    Запись оценки - если Оценка>Альфа и Оценка<Бета Тогда "=="
    //-// >=Бета //-// ">="
    //-// <=Альфа //-// "<="

    //
    Это стандартная схема Хеширования.
  16. WinPooh В.М.

    • Команда форума
    Рег.:
    13.02.2006
    Сообщения:
    8.964
    Симпатии:
    2.172
    Репутация:
    85
    Адрес:
    Москва
    Оффлайн
    Много раз такое слышал. А почему, кстати? Ведь наибольший эффект от сокращения веток достигается как раз у корня - отловив транспозицию на третьем полуходе, мы сразу режем очень и очень много...
  17. NS Нефёдов Сергей

    • Заслуженный
    • Ветеран
    Рег.:
    02.05.2006
    Сообщения:
    6.811
    Симпатии:
    96
    Репутация:
    3
    Адрес:
    Санкт-Петербург
    Оффлайн
    1. Количество совпадений значительно больше к концу варианта (при больших ply)
    2. При хорошей сортировке общее количество узлов в дереве падает быстрее, чем количество совпадающих (перекрестных) позиций (хорошая сортировка увеличивает процент совпадений позиции даже при той-же глубине)
  18. варяг Учаcтник

    • Участник
    Рег.:
    23.10.2006
    Сообщения:
    98
    Симпатии:
    0
    Репутация:
    0
    Адрес:
    Гонду-Раша
    Оффлайн
    Как можно проверить корректность работы хэш-таблицы? Программа периодически глючит непадетски, есть подозрения, что виноват хэш. Причем глюки проявляются только в ходе партии, а если эту же позицию поставить с пустым хэшем, то все в порядке. Может есть какие-нидь позиции, в которых при глючном хэше программа выбирает глючный ход? Брюс Морланд когда-то предлагал позу 8/k/3p4/p2P1p2/P2P1P2/8/8/K7 w - - 0 1 для тестирования хэша - здесь у меня все в порядке. Может еще кто какие-то позиции знает? Или может еще какая-нидь методика тестирования?
  19. WildCat Коршунов Игорь

    • Команда форума
    Рег.:
    04.05.2006
    Сообщения:
    3.599
    Симпатии:
    3
    Репутация:
    0
    Адрес:
    Гомель
    Оффлайн
    Самое первое это - хранить в хеше вместе с ключом и всю позицию, и проверять каждый раз когда совпадает ключ совпадение позиций.
  20. WildCat Коршунов Игорь

    • Команда форума
    Рег.:
    04.05.2006
    Сообщения:
    3.599
    Симпатии:
    3
    Репутация:
    0
    Адрес:
    Гомель
    Оффлайн
    Еще можно попробовать исключать их хеша классы позиций (<= alpha или >= beta или точные), и смотреть проявляется ли глюк.
  21. ChessTerminator75 Андрей

    • Участник
    Рег.:
    22.05.2007
    Сообщения:
    121
    Симпатии:
    0
    Репутация:
    0
    Адрес:
    Челябинск
    Оффлайн
    Вы не уточнили на какой машине считает движок.
    И все равно как вы достигли таких глубин?
    Лично я застрял на глубине 10.
    Очень интересно какие вы используете эвристики и какое приращение по глубине они дают.
    Кстати ответ что режу все подрят я уже слышал :):)
  22. WildCat Коршунов Игорь

    • Команда форума
    Рег.:
    04.05.2006
    Сообщения:
    3.599
    Симпатии:
    3
    Репутация:
    0
    Адрес:
    Гомель
    Оффлайн
    А ничего нового тут не добавишь. :)

    Машина весьма средняя. Выдает 1290 фрицевских попугаев.
  23. ChessTerminator75 Андрей

    • Участник
    Рег.:
    22.05.2007
    Сообщения:
    121
    Симпатии:
    0
    Репутация:
    0
    Адрес:
    Челябинск
    Оффлайн
    На мой взгляд хорошая машина.
    У меня атлон 3500+ выдает 1179 попугаев :)
  24. WildCat Коршунов Игорь

    • Команда форума
    Рег.:
    04.05.2006
    Сообщения:
    3.599
    Симпатии:
    3
    Репутация:
    0
    Адрес:
    Гомель
    Оффлайн
    А у меня Семпрон 3000+.
  25. WinPooh В.М.

    • Команда форума
    Рег.:
    13.02.2006
    Сообщения:
    8.964
    Симпатии:
    2.172
    Репутация:
    85
    Адрес:
    Москва
    Оффлайн
    Процессор сам по себе не определяет быстродействия системы. Узкое место - это скорость доступа к памяти.
  26. WildCat Коршунов Игорь

    • Команда форума
    Рег.:
    04.05.2006
    Сообщения:
    3.599
    Симпатии:
    3
    Репутация:
    0
    Адрес:
    Гомель
    Оффлайн
    Скорость движка прямопропорциональна частоте процессора. Значит память очень большого значения не имеет.
  27. WinPooh В.М.

    • Команда форума
    Рег.:
    13.02.2006
    Сообщения:
    8.964
    Симпатии:
    2.172
    Репутация:
    85
    Адрес:
    Москва
    Оффлайн
    Есть экспериментальные данные? Сколько точек на графике?
    Да, при прочих равных - это так. Но при одинаковом процессоре машина с лучшей памятью будет быстрее :)
  28. WinPooh В.М.

    • Команда форума
    Рег.:
    13.02.2006
    Сообщения:
    8.964
    Симпатии:
    2.172
    Репутация:
    85
    Адрес:
    Москва
    Оффлайн
    Функция f = x * y прямо пропорциональна значению x. Значит, y большого значения не имеет :)
  29. NS Нефёдов Сергей

    • Заслуженный
    • Ветеран
    Рег.:
    02.05.2006
    Сообщения:
    6.811
    Симпатии:
    96
    Репутация:
    3
    Адрес:
    Санкт-Петербург
    Оффлайн
    В том-то всё и дело, что понятно что такой вид функция иметь не может.
    Она имеет вид 1(k1/X+k2/Y), где X-скорость проца (Больше - быстрее), а Y - скорость памяти (больше-быстрее) И если при росте скорости проца в два раза, скорость шахматной программы вырастает тоже в два раза - значит k1>>k2

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