Алгоритмы Bitboard для размеров доски больше 64?

Я знаю, что метод Magic BitBoard удобен для современных игр с сеткой n 8x8, потому что он идеально согласуется с одним 64-битным целым числом, но можно ли расширить эту идею до размеров доски, превышающих 64 квадрата?

Некоторые игры, такие как Shogi, имеют большие размеры доски, такие как 81 квадрат, что не совсем соответствует 64-битному целому числу.

Я предполагаю, что вам придется использовать несколько целых чисел, но было бы лучше использовать 2 64-битных целых числа или что-то вроде 3 32-битных?

Я знаю, что, вероятно, нет тривиального ответа на этот вопрос, но какие знания мне понадобятся, чтобы исследовать что-то подобное? У меня есть только базовые/промежуточные знания алгоритмов и структур данных.


algorithm bitboard
person swigganicks    schedule 15.06.2018    source источник

Ответы (1)


arrow_upward
2
arrow_downward

Да, вы можете сделать это со структурой, содержащей несколько целых чисел различной длины. Например, вы можете использовать 11 байтов без знака. Или 64-битное целое число, 32-битное целое число и т. д. Все, что в сумме дает 81 или более битов.

Мне больше нравится идея трех 32-битных целых чисел, потому что вы можете хранить три строки для каждого целого числа. Это делает ваш код индексации проще, чем если бы вы использовали 64-битное целое число и 32-битное целое число. 9 16-битные слова тоже подойдут, но вы теряете почти половину своих битов.

Вы могли бы использовать 11 байтов без знака, но индексация выглядит уродливо.

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

person Jim Mischel    schedule 15.06.2018