Transposition table

на главную страницу


Вводные рассуждения.

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

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

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

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

Хеш-ключ.

Как же привязать число к позиции? Вообще говоря, разные позиции отличаются друг от друга фигурами и расположением этих фигур.
Поэтому естественным шагом будет использовать трехмерный массив 64-битных чисел.
Хеш-ключ [цвет фигуры][имя фигуры][позиция фигуры]
Таким образом, мы имеем всевозможные фигуры на всевозможных позициях. Каждую ячейку этого массива мы заполним случайным 64
–битным числом. Почему именно 64 битное, а не 32 битное число? Потому что при использовании 32 битных слишком много
коллизий.

Для генерации случайного 64-битного числа можно воспользоваться следующей функцией.
Так это реализовано в Ифрите (Ifrit_b_2_5):
unsigned __int64 rand_64(){
//в основе генерации случайных чисел лежит стандартная функция библиотеки
//<cstdlib> возвращающая псевдослучайное число в диапазоне 0 до 32767
//int rand ( void );
//Returns a pseudo-random integral number in the range 0 to RAND_MAX.
//RAND_MAX is a constant defined in <cstdlib>. Its default value may vary between
//implementations but it is granted to be at least 32767.

  return rand() ^ ( ((unsigned __int64)rand() << 15) ^ ((unsigned __int64)rand() << 31) ^
                         ((unsigned __int64)rand() << 47) ^ ((unsigned __int64)rand() << 59));
}//unsigned __int64 rand_64(){

А можно использовать уже готовую таблицу, как это сделано во Фрукте.

Приведу функцию инициализирующую трехмерный массив хеш-ключей(Ifrit_b_2_5):
void Ini_random_piese_key(){
  for(int c=0 ; c<2 ; c++){
    for(int n=1 ; n<7 ; n++){
      for(int q=0 ; q<64 ; q++){
        random_piese_key[c][n][q]=rand_64();
      }//for(int q=0 ; q<120 ; q++){
    }//for(int n=1 ; n<7 ; n++){
  }//for(int c=1 ; c<3 ; c++){
}//Ini_random_piese_key(){

Теперь, когда у нас есть трехмерная таблица хеш-ключей, мы можем вычислить хеш-ключ конкретной позиции.
(Ifrit_b_2_5):
void Start_position_random_key(T_Bitboard * bitboard){
  int n_1 = 0;
  int colour=0;
  int name=0;
  unsigned __int64 key = U64(0xF3218F1C9510786C);
  n_1 = 0;
  while (n_1<64){
    name = bitboard->white_name_from_coord[n_1];
    if (name != 0) key = key ^ random_piese_key[1][name][n_1];

    name = bitboard->black_name_from_coord[n_1];
    if (name != 0) key = key ^ random_piese_key[0][name][n_1];
    n_1 = n_1 + 1;
  }//while (n_1<64){
  bitboard->hash_key=key;
}//Start_position_random_key(T_board_list_816 * board_list_816){
Мы просто бежим по позиции XORим полученные из массива числа. Раньше вместо XOR я использовал обычное сложение. Разницы почти
нет.
Конечно, каждый раз полностью считать хеш-ключ позиции не нужно. Достаточно только отобразить изменения. Т.е. если, к
примеру, фигура пошла из одного места в другое, то мы должны просто изменить хеш-ключ позиции, изменив хеш-число фигуры. И
вот тут проявляется удобная особенность XOR. Дело в том, что два XOR возвращают исходное число. Поэтому первый раз, применяя
XOR, мы добавляем число, а применив его второй раз, мы его убираем.
Это выглядит примерно так:
key=key_mem ^ random_piese_key[colour_figure][name_figure][initial_position];//убрали фигуру из старого места
key=key ^ random_piese_key[colour_figure][name_figure][final_position];//добавили в новом месте

Хеш-таблица.

Теперь, когда мы знаем, как для текущей позиции можно вычислить хеш-ключ, можно организовать хеш-таблицу. Надо сказать, что в
Ифрите хеш-таблица используется только для сортировки ходов, поэтому в ней я запоминаю только лучший для данной позиции ход.
Для этого использую следующую структуру(Ifrit_b_2_5):
struct T_hash_moves {
  // хеш ключ позиции
  unsigned __int64 key;
  // описание хода смотреть в струкутре T_list_surplus_moves
  int move;
  // глубина записи данного ключа
  int depth;
};//struct T_PV {

Есть еще один момент, на котором стоит остановиться. Перебирать каждый раз все хеш-ключи для того что бы выяснить есть ли у
нас такой или нет нежелательно. Поэтому индекс хеш-таблицы привязывается к хеш-ключу.
Просто использовать хеш-ключ в качестве индекса массива хеш-таблицы мы не можем, так как он слишком большой. Поэтому
прибегаем к следующему приему.
Для начала надо вспомнить, как работает &
и & 0 0 1 первый операнд
       0 1 1 второй операнд
       -----
       0 0 1 результат
Мы видим, что нули переходят в нули, и это будем использовать, но для этого максимальный индекс таблицы должен быть числом
вида
00..011111, тогда каким бы не был хеш-ключ мы никогда не выйдем за пределы максимального индекса и можно записать
hash_moves[(unsigned int)key & max_index_hash ]

Такое число это число вида (2 в степени n) -1

Выделение памяти под хеш-таблицу.

Так это сделано в Ifrit_b_2_5:
void Hash_size_ini_default(int hash_size){
  unsigned int hash_n = 0;
  // перегоняем размер в Мб в байты, а потом в количество элементов
  max_index_hash = (unsigned int)((hash_size * (1024 * 1024))/sizeof(T_hash_moves));
  // нам нужно получить размер (2 в степени n) -1 чтобы получилось
  // число вида 000..0111 и можно было вгонять хеш-индекс в пределы массива операцией &
  for (hash_n =2 ; hash_n <= max_index_hash ; hash_n = 2 * hash_n );
  hash_n = hash_n / 2;
  if ((hash_n & (hash_n - 1)) != 0) cout << "ЗАСАДА! размер не вида степени двух " << hash_n << "\n";
  max_index_hash = hash_n - 1;
  // резервируем память под таблицу и заполняем ее нулями
  hash_moves = (T_hash_moves*) calloc ((max_index_hash + 3),sizeof(T_hash_moves));
  if (hash_moves == NULL) {
    cout << "памяти нет " << "\n";
    exit(1);
  }//if (hash_moves == NULL) {
}//void Hash_size_ini_default(){

Заключительные замечания.

Посмотрим, что дает нам хеш-таблица

Альфа-бета с сортировкой взятий
8/8     00:07    3.151.926 607.473      +0,12  e2e4 e7e5 Ng1f3 Ng8f6 d2d4 e5xd4 Qd1xd4 Bf8e7
9/9     00:45    25.499.252 780.290    +0,29  e2e4 e7e5 Ng1f3 Bf8d6 d2d4 e5xd4 Qd1xd4 Ng8f6 Bf1c4
10/10 04:41    102.801.673 559.898  +0,09  e2e4 e7e5 Ng1f3 Ng8f6 d2d4 e5xd4 e4e5 Qd8e7 Qd1xd4 Nb8c6

Включена хеш-таблица
8/8     00:03    795.159 535.434         +0,12  e2e4 e7e5 Ng1f3 Ng8f6 d2d4 e5xd4 Qd1xd4 Bf8e7
9/9     00:17    8.755.251 737.652      +0,29  e2e4 e7e5 Ng1f3 Bf8d6 d2d4 e5xd4 Qd1xd4 Ng8f6 Bf1c4
10/10 01:46    39.045.546 545.722    +0,04  Nb1c3 d7d5 d2d4 Bc8f5 Ng1f3 Nb8c6 Bc1f4 Ng8f6 e2e3 Qd8d7

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

























Сайт создан в системе uCoz