Рубрики

Минимаксный алгоритм в теории игр | Набор 5 (Зобрист Хэширование)

Теория игр

Предыдущие сообщения на эту тему: минимаксный алгоритм в теории игр , функция оценки в теории игр , Tic-Tac-Toe AI — поиск оптимального хода , альфа-бета-обрезка .

Zobrist Hashing — это функция хеширования, которая широко используется в настольных играх для 2 игроков. Это самая распространенная функция хеширования, используемая в таблице транспозиции. Таблицы транспонирования в основном хранят оцененные значения предыдущих состояний платы, поэтому, если они встретятся снова, мы просто извлекаем сохраненное значение из таблицы транспонирования. Мы рассмотрим таблицы транспонирования в следующей статье. В этой статье мы возьмем пример шахматной доски и реализуем для этого функцию хеширования.

Псевдокод:

// A matrix with random numbers initialized once
Table[#ofBoardCells][#ofPieces] 

// Returns Zobrist hash function for current conf-
// iguration of board.
function findhash(board):
    hash = 0
    for each cell on the board :
        if cell is not empty :
            piece = board[cell]
            hash ^= table[cell][piece]
    return hash

Пояснение:

Идея Zobrist Hashing заключается в том, что для данного состояния доски, если в данной ячейке есть фигура, мы используем случайное число этой фигуры из соответствующей ячейки в таблице.

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

Кроме того, причина, по которой Zobrist Hashing широко используется в настольных играх, заключается в том, что когда игрок делает ход, нет необходимости пересчитывать значение хэша с нуля. Из-за характера операции XOR мы можем просто использовать несколько операций XOR для пересчета значения хеш-функции.

Реализация :

Мы попытаемся найти значение хеш-функции для данной конфигурации платы.

// Программа для иллюстрации алгоритма хеширования Zobeist
#include <bits/stdc++.h>

using namespace std;

  

unsigned long long int ZobristTable[8][8][12];

mt19937 mt(01234567);

  
// Генерирует число Рэндома от 0 до 2 ^ 64-1

unsigned long long int randomInt()

{

    uniform_int_distribution<unsigned long long int>

                                 dist(0, UINT64_MAX);

    return dist(mt);

}

  
// Эта функция связывает каждый кусок с
// число

int indexOf(char piece)

{

    if (piece=='P')

        return 0;

    if (piece=='N')

        return 1;

    if (piece=='B')

        return 2;

    if (piece=='R')

        return 3;

    if (piece=='Q')

        return 4;

    if (piece=='K')

        return 5;

    if (piece=='p')

        return 6;

    if (piece=='n')

        return 7;

    if (piece=='b')

        return 8;

    if (piece=='r')

        return 9;

    if (piece=='q')

        return 10;

    if (piece=='k')

        return 11;

    else

        return -1;

}

  
// Инициализирует таблицу

void initTable()

{

    for (int i = 0; i<8; i++)

      for (int j = 0; j<8; j++)

        for (int k = 0; k<12; k++)

          ZobristTable[i][j][k] = randomInt();

}

  
// Вычисляет значение хеша данной доски

unsigned long long int computeHash(char board[8][9])

{

    unsigned long long int h = 0;

    for (int i = 0; i<8; i++)

    {

        for (int j = 0; j<8; j++)

        {

            if (board[i][j]!='-')

            {

                int piece = indexOf(board[i][j]);

                h ^= ZobristTable[i][j][piece];

            }

        }

    }

    return h;

}

  
// Основная функция

int main()

{

    // Прописные буквы - белые фигуры

    // Строчные буквы - это черные фигуры

    char board[8][9] =

    {

        "---K----",

        "-R----Q-",

        "--------",

        "-P----p-",

        "-----p--",

        "--------",

        "p---b--q",

        "----n--k"

    };

  

    initTable();

  

    unsigned long long int hashValue = computeHash(board);

    printf("The hash value is     : %llu\n", hashValue);

  

    // Переместить белого короля влево

    char piece = board[0][3];

  

    board[0][3] = '-';

    hashValue ^= ZobristTable[0][3][indexOf(piece)];

  

    board[0][2] = piece;

    hashValue ^= ZobristTable[0][2][indexOf(piece)];

  

  

    printf("The new hash value is : %llu\n", hashValue);

  

    // Отмена хода белого короля

    piece = board[0][2];

  

    board[0][2] = '-';

    hashValue ^= ZobristTable[0][2][indexOf(piece)];

  

    board[0][3] = piece;

    hashValue ^= ZobristTable[0][3][indexOf(piece)];

  

    printf("The old hash value is : %llu\n", hashValue);

  

    return 0;

}

Выход :

The hash value is     : 14226429382419125366
The new hash value is : 15124945578233295113
The old hash value is : 14226429382419125366

Эта статья предоставлена Akshay L Aradhya . Если вы как GeeksforGeeks и хотели бы внести свой вклад, вы также можете написать статью с помощью contribute.geeksforgeeks.org или по почте статьи contribute@geeksforgeeks.org. Смотрите свою статью, появляющуюся на главной странице GeeksforGeeks, и помогите другим вундеркиндам.

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

Рекомендуемые посты:

Минимаксный алгоритм в теории игр | Набор 5 (Зобрист Хэширование)

0.00 (0%) 0 votes