Если каждая плитка в игре может иметь одно из трех состояний в любой момент игры, то минимальный объем памяти, необходимый для «идеального хеширования» при хешировании всех возможных состояний игровой доски, в любой данный моментбудет
= мощность (3,8 * 8) отдельных хешей
= log2 (3 ^ 64) биты
= прибл.101,4 бита, поэтому вам понадобится как минимум 102 бита для хранения этой информации
На этом этапе вы можете просто сказать, что для каждой плитки есть 4 состояния, что приведет к необходимости 128 бит .
Как только вы это сделаете, довольно просто создать быстрый алгоритм хэширования для платы.
Например (написанный как c ++, может потребоваться изменить код, еслиплатформа не поддерживает 128-битные числа)
uint_128 CreateGameBoardHash(int (&game_board)[8][8])
{
uint_128 board_hash = 0;
for(int i = 0; i < 8; ++i)
{
for(int j = 0; j < 8; ++j)
{
board_hash |= game_board[i][j] << ((i * 8 + j) *2);
}
}
return board_hash;
}
Этот метод будет тратить только 26 бит (чуть более 3 байтов) на оптимальное решение из 102 бит, но вы сэкономите МНОГО времени обработки, котороеиначе было бы потрачено на математику с основанием 3.
Edit Вот версия, которая не требует 128 бит и должна работать на любом 16-битном (или лучше) процессоре
struct GameBoardHash
{
uint16 row[8];
};</p>
<p>GameBoardHash CreateGameBoardHash(int (&game_board)[8][8])
{
GameBoardHash board_hash;
for(int i = 0; i < 8; ++i)
{
board_hash.row[i] = 0;
for(int j = 0; j < 8; ++j)
{
board_hash.row[i] |= game_board[j] << (j*2);
}
}
return board_hash;
}