C: Простой и быстрый хеш-стол для шахмат?

Question

Мне было интересно, знает ли кто-нибудь о хорошей реализации хэш-таблицы в C. Все, что я пытаюсь сделать, это хэш-шахматная доска. Я просто хочу, чтобы реализация была быстрой и с возможностью очистки таблицы за один раз. Любая помощь будет воспринята!

Answer 1

В шахматах это в основном называется «таблицей транспонирования». Это более специализированная структура данных, чем хеш-таблица.

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

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

• Сам
• Хэш функция hash что отображает позицию ключа таблицы транспонирования (для получения более подробной информации, посмотрите на Zobrist hashing)

Транспонирование таблицы само может быть очень легко. В начале, вы можете просто использовать один большой массив:

Entry* table = malloc(n * sizeof(Entry)); 
// ... 

// clear transposition table 
memset(table, 0, n * sizeof(Entry)); 

Position position; // the chess position 
// ... 

Key key = hash(position); 

// probe 
Entry entry = table[hash(position) % n]; 
if(entry.key == key) 
{ 
    // found something --> entry can be used 
    ... 
} 

// store 
table[hash(position) % n] = updated_entry; 

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

Вот некоторые дополнительные ссылки, которые должны помочь вам написать свой собственный:

• http://chessprogramming.wikispaces.com/Transposition+Table
• https://en.wikipedia.org/wiki/Transposition_table