Представление Совета Гомоку

Question

Я работаю над игрой в Гомоку, и мне нужна эффективная структура данных для хранения состояния плат, Я думал о ее хранении в 2D-массиве, но я уверен, что есть больше эффективный способ. Спасибо

Answer 1

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

С точки зрения экономии пространства:

Каждый квадрат может быть либо пустым, либо заполняется либо игрока. Таким образом, существует максимум 3 возможности. Для максимальной эффективности пространства мы могли бы хранить всю нашу плату в представлении base-3, но, поскольку компьютер работает в двоичном формате, нам нужно обработать всю доску, чтобы определить значение некоторого заданного квадрата (таким образом, простой поиск индекса будет время пропорционально размеру доски - если время действительно не проблема, вы могли бы подумать об этом). Вместо этого я бы рекомендовал использовать 2 бита на квадрат, что позволило бы указать одну из четырех возможностей (четвертая не используется).

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

Вам также нужен только один бит-разряд (а не 2D), поскольку в работе с 2D-структурами обычно возникает небольшая часть служебных данных памяти. Преобразование из 2D в 1D является простым - мы могли бы преобразовать 2D-индекс в 1D либо с x*height + y, либо с y*width + x.

Хотя я бы порекомендовал сначала убедиться, что вам нужно выполнить эту оптимизацию - я считаю, что платы Gomoku, как правило, небольшие, поэтому даже объемное представление будет работать отлично (хотя некоторые методы AI составляют много копий платы, если вы это сделаете, минимальное представление будет иметь смысл).