Hash позиции

Как расшифровывается LMR и где можно достать описание метода?

LMR - Late Move Reduction
Сокращение перебора на ходах от которых мы ничего не ожидаем... (верояность что он опровергающий весьма мала)
Обычно это нетактические и плохие по истории ходы (не взятие, не шах, не превращение, не киллер, не ход из Хеша).
Описание его весьма простое - на плохих ходах сокращаем, но если вдруг "сокращенный" ход оказался опровергающим - считаем на полную глубину.

расскажите, как боретесь с аномалиями хэш-таблиц?

Все, разобрался. Был баг с занесением информации в хэш

прикручиваю к движку Transposition tables , в итоге играет даже хуже ...

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

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

в принципе ТТ как раз работали без сбоев ... даже 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

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 одновременно ... может кто растолкует?

шаманил я тут шаманил ...
в search() вместо вызова quiescense() вставил сразу evaluate() - тем самым убрал некоторую неизвестность глубины перебора
убрал sort_PV() , чтоб не сортировала ходы по принадлежности к PV -
только тогда TT - версия стала где-то в 2 раза быстрее такой же "искалеченной" обычной

Пока глубина перебора равна 7 Ply (как понял еще и NullMove применяется... Глубина должна быть всяко больше чем 7 Ply) - Хеш перекрестных позиций почти ничего не даст. Чтоб он работал должны быть хорошо отсортированы ходы.

Делай стандартную схему - глубина оценки, тип оценки (<=,==,>=), сама оценка.
И не PV ветвях, если глубина нормальная, и оценка выходит за границу Альфа/Бета тогда отсечение...
Если типоценки "==" или "<=" тогда
Если ОценкаизХеша<=Альфа Тогда
Отсекаем с ОценкаИзХеша

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

//

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

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

1. Количество совпадений значительно больше к концу варианта (при больших ply)
2. При хорошей сортировке общее количество узлов в дереве падает быстрее, чем количество совпадающих (перекрестных) позиций (хорошая сортировка увеличивает процент совпадений позиции даже при той-же глубине)

Как можно проверить корректность работы хэш-таблицы? Программа периодически глючит непадетски, есть подозрения, что виноват хэш. Причем глюки проявляются только в ходе партии, а если эту же позицию поставить с пустым хэшем, то все в порядке. Может есть какие-нидь позиции, в которых при глючном хэше программа выбирает глючный ход? Брюс Морланд когда-то предлагал позу 8/k/3p4/p2P1p2/P2P1P2/8/8/K7 w - - 0 1 для тестирования хэша - здесь у меня все в порядке. Может еще кто какие-то позиции знает? Или может еще какая-нидь методика тестирования?

Вы не уточнили на какой машине считает движок.
И все равно как вы достигли таких глубин?
Лично я застрял на глубине 10.
Очень интересно какие вы используете эвристики и какое приращение по глубине они дают.
Кстати ответ что режу все подрят я уже слышал

На мой взгляд хорошая машина.
У меня атлон 3500+ выдает 1179 попугаев

В том-то всё и дело, что понятно что такой вид функция иметь не может.
Она имеет вид 1(k1/X+k2/Y), где X-скорость проца (Больше - быстрее), а Y - скорость памяти (больше-быстрее) И если при росте скорости проца в два раза, скорость шахматной программы вырастает тоже в два раза - значит k1>>k2