|
||
|
Вводные рассуждения. Основная идея заключается в том, что бы при возникновении уже просчитанных позиций использовать ранее полученные результаты. Для реализации мы должны, во-первых, запомнить позицию и информацию по ней, а во-вторых, при получении такой же увидеть, что мы ее уже ранее рассматривали и воспользоваться уже полученными данными. Если решать задачу в лоб, то мы должны запоминать позицию и потом сравнивать весь ранее запомненный массив позиций с текущей проверяя, что все фигуры находятся на тех же местах. Страшно даже представить, сколько времени это займет. Быстрее просчитать позицию по-новому. Для повышения эффективности используется хеш-ключ. Каждой позиции мы сопоставляем некоторое число. Причем, разным позициям должны быть приписаны разные числа, а одинаковым позициям должны соответствовать одинаковые числа. Например, возникла у нас определенная позиция, мы посчитали по ней хеш-ключ, запомнили его и всю сопутствующую информацию, такую как лучший ход, оценка и т.д. Во время дальнейшего перебора во всех возникающих позициях мы считаем хеш-ключ и смотрим - если он нам уже встречался, то значит, нам встречалась эта позиция, и мы используем ранее полученный результат. Конечно, возможна ситуация когда у разных позиций будут одинаковые ключи, потому что отображение множества позиций на множество ключей все-таки не однозначно, тогда возникает коллизия. Мы будем думать, что позиции одинаковы, а они разные и применение результатов одной к другой окажется ошибкой. Хеш-ключ. Как же привязать число к позиции? Вообще говоря, разные позиции отличаются друг от друга фигурами и расположением этих фигур. Поэтому естественным шагом будет использовать трехмерный массив 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 Надо еще добавить, что хеш-ход я вставляю в список первым. Для этого ищу его в списке ходов и если нашел, то ставлю первым, а если нет, то оставляю как есть, кстати, это и является защитой от коллизий. Правда защита не полная. |