Главная » Игры, Структуры данных, Теория » Хеш-таблицы одним из самых мощных способов повышения про­изводительности компьютера

0

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

Для тех, кто не знаком с предметом, несколько слов о хешировании вооб­ще. Хеширование является методом ускорения поиска. Компилятор встре­чает некоторую лексему и пытается найти ее в своей базе данных или таб­лице символических имен. Таблица символических имен современного компилятора в MS Windows может содержать несколько тысяч или десятков тысяч лексем. Для ускорения поиска был придуман следующий прием. Компилятор, найдя лексему в тексте программы, определяет ее хеш-ключ. Наша лексема — это просто слово, состоящее из последовательности кодов символов. Для определения хеш-кода следует сложить все коды символов. Лексем с таким хеш-кодом в базе данных уже значительно меньше. Компи­лятор определяет номер списка с заданным кодом и перебирает этот спи­сок, а не всю базу данных. Все это в программе может выглядеть пример­но так:

//элемент связного списка typedef struct _tagHIten{

char lexem[40];       //лексема

struct _tagHItem* next; //следующий элемент списка }THItem,*PHItem;

//количество связных списков #defi,ne MAX_H_INDEX 1000 //массив связных списков PHItem hashTable[MAX_H_ITEM]; //функция возвращает хеш-код слова int GetHKey(char *lexem) (

unsigned int code = 0;

int n = 0;

while(lexem[n]) (

code = code л (code « n); n++;

}

return code % MAX_H_ITEM;

}

//поиск лексемы в таблице

int search(char *lexem) {

PHItem p;

// начало списка с данным хеш-кодом р = hashTable[GetHKey(lexem) ];

while(р)

{

if(!strcmp(p->lexem, lexem))

return 1; //точное совпадение p = p->next; //следующий элемент списка

}

return 0;

}

Хеш-код определяется не сложением кодов символов, а применением опе­рации исключающего ИЛИ. Это дает более равномерное распределение. Хеш-индекс не может быть больше размера таблицы, для этого возвращает­ся остаток от деления на размер. Могут быть коллизии: находится несколь­ко лексем с одним хеш-индексом. Для проверки точного совпадения нужно проверить весь список. Основная проблема состоит в поиске хеш-индекса, максимально точно идентифицирующего данную лексему. Идеальный хеш- индекс однозначно должен определять лексему.

При программировании шахмат тоже используется хеширование. Основная особенность состоит в том, что хеш-индекс должен очень точно отражать позицию, и поиск должен производиться максимально быстро. У нас даже нет времени на перебор списков с одним индексом. Списков, как правило, нет вообще. Для каждого значения хеш-ключа существует только одна по­зиция. Если возникла коллизия и встретилась позиция с таким же ключом, то она записывается поверх прежней. Зачем при программировании шахмат и других подобных игр хеширование и запоминание позиций? Дело в том, что при переборе мы имеем не дерево игры в прямом смысле, а граф. По­зиции повторяются через некоторое количество полуходов, и даже в одну и ту же позицию можно прийти различными путями. Можно воспользоваться некоторой информацией о позиции, которая уже встречалась. Самое про­стое и эффективное — это использовать позицию, чтобы улучшить порядок ходов. Это особенно выразительно при итеративных углублениях. Улучше­ние упорядочивания ходов — основное назначение хеш-таблицы. Переста­новки или повторы позиций тоже играют свою роль. Особенно их много в конце игры.

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

Хочется отметить, что хеш-таблицы являются практически неисчерпаемым источником ошибок в шахматных программах. Ошибки эти, как правило, трудно обнаруживаемые и очень досадные. Даже если бы мы имели идеаль­ный ключ, и не было бы коллизий, и наша программная реализация была бы стопроцентно верной, мы все равно получили бы одну досадную про­блему при использовании результата из хеш-таблицы. Проблема эта называ­ется нестабильностью поиска. Это когда расчет одного хода на одну глубину одной и той же функцией возвращает разный результат. Нестабильность поиска может быть вызвана многими причинами. Это — введение искусст­венных границ alpha-beta, различные схемы форвардного отсечения (отсе­чение ветвей без предварительного счета). Основной причиной является использование результата из хеш-таблицы. Даже обычный алгоритм NegaScout может из-за повторных переборов усиливать нестабильность по­иска. Типичный пример:

tmp = -NegaScout(-(alpha+1),-alpha); if(tmp > alpha && tmp < beta) tmp = -NegaScout(-beta,-tmp);

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

tmp = -NegaScout(-(alpha+1),-alpha); if(tmp > alpha && tmp < beta) tmp = -NegaScout(-beta,-alpha);

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

Основной проблемой является получение ключа, не связанного с позицией. Это достигается ставшей уже стандартной методикой ZObrist. Если нам, на­пример, нужно получить ключ для белого слона, стоящего в поле а4, мы поступаем следующим образом:

key = randTable [BISHOP] [WHITE] [A4];

Полный ключ для всей позиции вычисляется только в самом начале при помощи операции XOR. Дальше идет его пошаговая корректировка. На­пример, белая ладья переместилась из al в cl. Чтобы внести соответствую­щие изменения в хеш-ключ, мы должны сделать следующее:

nextKey = key л randTable [ROOK] [WHITE] [Al] л randTable [ROOK] [WHITE] [Cl];

Это позволяет быстро по шагам корректировать хеш-ключ. Он автоматиче­ски отслеживает все возможные повторы позиций. Системы программиро­вания, как правило, не позволяют получить случайное 64-битовое без знака. Можно легко написать свою функцию rand64, дающую такое число: typedef unsigned     int64 U64

(U64)rand() л ( (U64)rand() « 15) л ( (U64)rand() «30) л

При счете, т. к. мы используем alpha-beta пределы, оценка узла при записи в хеш-таблицу может быть трех видов.

D Меньше или равно alpha: мы не имеем лучшего хода, а только результат счета, который представляет собой максимум, достигнутый для этого уз­ла. Реальной оценки мы не знаем, т. к. в процессе перебора сработали отсечения за alpha-beta пределы.

?    Больше alpha, но меньше beta: мы имеем абсолютно точную оценку, как если бы мы перебирали алгоритмом NegaMax без всяких alpha-beta пре­делов. Имеется также лучший ход, посредством которого был получен данный результат.

?    Больше или равно beta: оценка не точная, но реальная. При полном пе­реборе для данного узла это минимум. Имеется также лучший ход.

Если мы в некотором узле нашли результат из хеша и хотим его использо­вать, то нужно проверить, какого типа этот результат. Если это оценка пер­вого вида, то использовать ее можно, только если она меньше или равна текущему значению alpha. Само собой, глубина узла из хеша должна быть, как минимум, равна глубине нашего текущего узла. Если оценка из хеша второго вида, т. е. точная, то использовать ее можно в любом случае. Если оценка узла из хеша третьего вида, то это минимум для данного узла, ис­пользовать его можно только в том случае, если он больше или равен теку­щему значению beta. Что касается этого третьего вида оценки, мы можем повышать alpha, т. к. alpha не может быть меньше данного минимума. При использовании результата из хеша хочется отметить один тонкий момент. В случае взятия короля оценка узла равна разности недосягаемого макси­мума infinity и глубины узла от 0, чтобы не оттягивать мат. При манипу­ляциях с оценкой из хеша нужно производить корректировку ply, чтобы соблюсти корректность глубины, на которой был поставлен мат:

if(score > INFINITY – MAX_PLY) score += ply; else if(score < -INFINITY + MAX_PLY) score -= ply;

При извлечении из хеша:

if(score > INFINITY-MAX_PLY) score -= ply; else if(score < -INFINITY+MAX_PLY) score += ply;

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

//виды элементов хеша #define EMPTY 0 #define EXACT 1

#define ALPHA 2 #define BETA 3 typedef struct tagHash{ U64 key; //хеш-ключ int depth; //глубина узла int flags; //тип узла int score; //оценка узла MOVE move; //лучший ход (если есть) }HItem;

#define MAX_H_ITEM (1 « 18)

//сама таблица

HItem hash[MAX_H_ITEM];

#define MAX_PLY 100 //максимальная глубина //запись в таблицу

void RecordHash(int depth, int score, int flag, U64 key, MOVE* move, int ply)

{

HItem *p = Shash [ key & (MAX_H_ITEM-1) ]; //остаток от деления //не перезаписываем узлы с лучшим ходом менее //ценными узлами с флагом ALPHA if(flag == ALPHA &&

(p->flags == EXACT || p->flags = BETA) return; //схема замены

//более глубокие узлы не затираем

if(p->depth <= depth) {

if(score > INFINITY – MAX_PLY) score += ply;

else if(score < -INFINITY + MAX_PLY) score -= ply;

p->depth = depth;

p->score = score;

p->flags = flag;

p->key = key;

if(flag != ALPHA) {

//скопируем лучший ход {…}

}

}

}

//использование хеша в функции поиска

int ALphaBeta(int alpha,int beta,int depth,int ply,U64 key) {

int oldAlpha = alpha; //запомним alpha

//получим ход из хеша

HItem *р = Shash [ key & (MAX_H_ITEM-1) ];

if(p->flags != EMPTY && p->key == key) {

//попробуем использовать оценку из хеша

if(ply >0 && p->depth >= depth) {

int score;

//корректировка оценки score = p->score; if(score > INFINITY-MAX_PLY) score -= ply; else if(score < -INFINITY+MAX_PLY) score += ply;

switch(p->flags) {

EXACT:BETA: {

if(score > alpha) alpha = score; if(alpha >= beta) return beta; } break ; ALPHA:{

if(score <= alpha) return alpha; }break; }//switch

}//endif

if(p->flag != ALPHA) {

//попробуем лучший ход из хеша MakeMove(&p->move);

tmp = -ALphaBeta(-beta,-alpha,depth-1,ply+1,NextKey(key,

&p->move); UnMakeMove(&p->move);

if(tmp > alpha) {

RecordHash(depth, tmp, tmp<beta?EXACT:BETA, key,

&p->move, ply); alpha = tmp;

if(alpha >= beta) return beta;

)

}

}//endif

GenerateAllMoves(); //перебираем все перемещения

//и записываем в хеш с соответствующим флагом while(move)

{

MakeMove(move);

tmp = -ALphaBeta(-beta,-alpha,depth-1,ply+l, NextKey(key,move);

UnMakeMove(move);

if(tmp > alpha) {

RecordHash(depth, tmp, tmp<beta?EXACT:BETA,

key,move, ply); alpha = tmp;

if(alpha >= beta) return beta;

}

move = move->next; }//while

//если программа дошла до этой точки и //значение alpha не повышалось, то запишем //данную позицию с флагом ALPHA //постараемся не перезаписать в хеше более //ценный узел с лучшим ходом if(alpha = oldALpha)

RecordHash(depth, alpha, ALPHA,key,NULL,ply); return alpha;

}

В данном примере значение alpha повышалось всегда, если флаг хода из хеша был exact или beta. Это увеличивает нестабильность поиска, но ошибки здесь нет. Обратите внимание на схему замены. Размер хеш- таблицы, как правило, всегда ограничен, и для одного и того же хеш- индекса могут быть узлы с разной глубиной и одним адресом в хеше. Здесь использовалась схема замены таким же узлом или более глубоким. Поверх­ностные узлы не затирают более глубокие и ценные. Узлы без лучшего хода (с флагом alpha) не затирают более ценные узлы с лучшими ходами. На­помним, что основной эффект хеш-таблицы заключается в использовании итеративных углублений, и узлы с ходами предыдущей итерации затирать нельзя. Так как размер хеша ограничен, то узлы с флагом alpha можно не использовать вообще, следовательно, флаг для узла из хеша не обязателен. Его оценкой всегда повышается текущее значение alpha. Узлы с флагом alpha имеют более низкий приоритет, по сравнению с другими узлами.

Помимо приведенной схемы замены существуют и другие. Например — "заменять всегда". В случае единственной хеш-таблицы предпочтительнее схема "такой же или более глубокий". Хороший эффект дают две хеш- таблицы: основная с такой схемой замены и вспомогательная (меньшего размера) со схемой замены всегда. Если вы хотите выжать из программы все, можно ввести вспомогательную хеш-таблицу с незначительным количе­ством элементов (например, 0 х FFFF). Особенно неплохо использование двух хеш-таблиц сочетается с внутренними итеративными углублениями. Если нет хода в хеше, мы перед началом перебора пытаемся получить луч­ший ход перебором на глубину N—2. Это, кроме всего прочего, упорядочи­вает вспомогательную хеш-таблицу и перебор (особенно на большую глуби­ну). В реальных программах размер хеша всегда ограничен реальной вели­чиной. Я обнаружил, что увеличение моей таблицы в два раза дало такой же эффект, что и использование маленькой вспомогательной таблицы со схе­мой "заменять всегда". Все это очень зависит от конкретной реализации.

В приведенном примере, помимо коллизий хеш-индекса (которыми можно пренебречь, т. к. иного выхода нет), есть опасность при использовании лучшего хода из хеша. Представьте себе ситуацию, когда лучший ход для узла был получен на глубине 10, а потом мы этот же узел считаем на глуби­не 2 и пытаемся использовать лучший ход из хеша. Из-за повторов позиций такая ситуация вполне может быть. Во избежание этого нужно при исполь­зовании лучшего хода из хеша проверять его легальность. Если в исходной клетке стоит та же фигура, то она вполне может пойти в целевую клетку. В целевой клетке не должно быть ничего или фигура противника. Для даль­нобойных фигур нужно строить линию, чтобы убедиться, что между исход­ной и конечной клеткой нет ничего. В целом, схема вполне работоспособ­ная, и даже использование результата из хеша не ведет к развалу просчета. Результат, как правило, используется на большой глубине. Чем больше глу­бина, тем меньше значение погрешности при вычислении.

При создании хеш-таблицы размер памяти, как правило, ограничен, а хо­чется поместить как можно больше элементов. Отсюда желание сделать размер одного описателя хеш-таблицы минимальным. Некоторые поля можно представить более компактно, в виде байта. Основной объем зани­мает хеш-ключ (8 байт) и описатель перемещения. В шахматах основную сложность представляют нестандартные ходы: рокировки и взятия пешки через битое поле. Двумерный массив игры [8][8] может быть заменен одно­мерным [64]. Таким образом, вместо двух индексов используется один.

Можно воспользоваться следующей схемой. Функция, генерирующая пере­мещения, возвращает, как правило, указатель на первый элемент списка перемещений. Для описателей перемещения она использует буфер, откуда берутся свободные описатели и соединяются в список. Буфер может распо­лагаться в стеке функции ALphaBeta. Важно то, что к любому описателю пе­ремещения можно обратиться по его адресу и номеру в буфере. Хеш- таблица может хранить только номер описателя перемещения в буфере. Та­ким образом, при использовании хода из хеша не нужно проверять его ле­гальность в данной позиции, и не страшны коллизии хеш-индекса. Единст­венный недостаток данной схемы — функция Generate, генерирующая пе­ремещения, должна быть вызвана перед использованием хода из хеша.

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

typedef struct{

U64 key;                //хеш-ключ

unsigned char moveNumber; //номер лучшего хода

signed char depth;      //глубина

}THItem;

Он имеет размер всего 10 байт. Если программа не собирается использовать хеш на большой глубине, или размер хеша ограничен, можно вместо типа U64 (64-битовое без знака) использовать 32-битовое без знака. Размер опи­сателя хеш-таблицы будет всего 6 байт! Какую схему использовать — дело вкуса и опыта в программировании.

Литература:

Корнилов Е. Н.  Программирование шахмат и других логических игр. — СПб.: БХВ-Петербург, 2005. – 272 е.: ил.

По теме:

  • Комментарии