Какая структура данных лучше всего подходит для представления доски для шашек, когда главное - скорость?

Question

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

В настоящее время я использую метод GetValidMoves(), который возвращает все текущие ходы, которые можно сделать с текущей доской.

Мне интересно, что может быть лучшим способом представить доску.Наивным подходом было бы иметь матрицу с 0, 1 и 2 (без фигуры, белой фигуры и черной фигуры).

Другая идея состояла бы в том, чтобы вместо матричного представления доски иметь 2 списка (или любая другая структура данных): одна для черных фигур, другая для белых.

Я реализую эту игру для тестирования некоторых алгоритмов ИИ, поэтому моя главная проблема - скорость.Я в основном поставлю двух игроков ИИ, играющих друг с другом, для каждого хода у каждого игрока должен быть список всех его действительных ходов, и затем он будет выбирать, какой ход делать, это всегда происходит до конца игры (какой-то игрок выигрывает илиtie).

PS: я не спрашиваю об алгоритме ИИ, я просто хочу знать, какова будет лучшая структура данных для управления платой, чтобы упростить

1. Поиск всех действительных ходов для текущего игрока
2. Выполнение хода
3. Убедитесь, что игра не окончена (она заканчивается, когда один игрок потерял все свои фигуры или один игрок достигдругая сторона доски).

Answer 1

Рассмотрите возможность использования растрового изображения: две 64-битные беззнаковые целые, одна для белого и одна для черного.Затем вы можете представить ходы и позиции на доске как функцию от (W x B) -> (W x B), где W , B представляют набор возможных позиций белого и возможного черного соответственно.

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

Answer 2

Обычный способ сделать это с двоичным представлением типа long для каждого игрока.
(поскольку на доске 64 квадрата) .. Как уже сказал Чарли ..
Вот очень хорошая (но довольно общая) статья в вики .

Использование простое - например, если вы хотите проверить, все ли части могут двигаться, скажем, вверх и вправо, сдвиньтевоспроизведение фигур игрока на 7 битов влево и проверьте, есть ли там фигуры противника, затем сдвиньте их на 7 битов еще раз, и проверьте, свободны ли эти квадраты ...
Я использовал это в соревновании Реверси один раз, иМожно сказать, что реализация не была слишком сложной.
HTH.

Answer 3

Прежде всего, стоит отметить, что в шашках никогда нельзя использовать половину квадратов на досках, поэтому вам нужен только массив из 32 предметов, а не 64. Учитывая короли, вы получаете возможности от 0 до4 вместо 0 до 2 (хотя, когда я это сделал, мне было проще использовать от -3 до +3, поэтому значения для красного и черного имеют одинаковую величину и противоположные знаки).

Answer 4

Я бы также использовал для этого растровое изображение.Функции для проверки 1, 2 и 3 будут немного неинтуитивными для написания, но должны быть очень быстрыми.

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

Answer 5

Это зависит от того, что будут делать ваши алгоритмы ИИ. Большинство алгоритмов ИИ будут осуществлять поиск возможных шагов, по крайней мере, на несколько шагов вперед. В этом случае вы будете делать множество копий представления вашей доски, и имеет смысл попытаться сохранить его небольшим, так как время на копирование вашей структуры данных будет доминировать над временем получения списка возможных перемещений, а также ограничением глубины до который вы можете искать.

Однако, если вы не ищете, я бы создал классную фигуру и сохранил цвет, местоположение и то, является ли фигура королем. Я бы тогда имел двумерный массив 8 на 8 ссылок на пьесы и связанный список черных фигур и связанный список красных фигур. Каждый элемент массива будет указывать либо на фрагмент из красного или черного списка, либо на «пустой» фрагмент (для этого будет работать null). Когда вы перемещаете фигуру, вы просто обновляете объект фигуры в списке и перемещаете ссылку из ее текущего местоположения в новое местоположение, устанавливая старое местоположение в пустой фрагмент. Для небольшого увеличения стоимости обновления вы получаете эффективный способ итерации по обеим сторонам и постоянный поиск по времени состояния любого конкретного места на доске.

Вы должны были бы перебрать весь список, чтобы удалить мертвую часть, однако это также можно сделать эффективным с небольшим изменением части. Вы можете хранить bool "dead" в объекте Piece. Когда часть убита, установите мертвым значение true и удалите ее с доски, заменив ссылку на нее пустой частью. Когда вы просматриваете любой из списков, просто удалите из списка любой кусочек, помеченный как мертвый.

Answer 6

С точки зрения списков, я бы настоятельно рекомендовал не использовать структуру, которая использует связанные списки в этой ситуации.Вы, вероятно, уже знаете позиции, которые вы хотите исследовать (координаты xy), и поэтому для связанного списка потребуется O(n) время, чтобы просто получить значение пространства шахматной доски.Как уже упоминалось в других ответах, идеальным вариантом будет растровый или длинный подход.

С точки зрения организации данных, я мог бы представить, что реализация, в которой черный и белый цвета хранятся в одной и той же структуре, будетидеально.У вас будут некоторые накладные расходы, поскольку для хранения 2 и 3 в двоичном виде требуется одинаковый объем памяти, хотя, если вы пишете контролеры, вам, вероятно, все равно придется хранить «королевские» данные.Возможность проверить, открыто ли пространство, выполнив один поиск, должна значительно повысить производительность.

Надеюсь, это поможет.