Структура данных для двумерных настольных игр на функциональных языках

9

Я создаю простую реализацию MiniMax на функциональном языке программирования Elixir. Поскольку существует множество игр с совершенным знанием (крестики-нолики, connect-four, шашки, шахматы и т. Д.), Эта реализация может стать основой для создания игровых ИИ для любой из этих игр.

Однако одна проблема, с которой я сталкиваюсь, заключается в том, как правильно сохранить состояние игры на функциональном языке. Эти игры в основном имеют дело с двумерными игровыми полями, где часто выполняются следующие операции:

  • Прочитайте содержимое определенного места на доске
  • Обновить содержимое определенного места на доске (при возврате новой возможности перемещения)
  • Рассматривая содержимое одного или нескольких местоположений, которые связаны с текущим местоположением (то есть следующее или предыдущее горизонтальное, вертикальное или диагональное местоположение)
  • Учитывая содержимое нескольких подключенных мест в любом направлении.
  • Учитывая содержимое целых файлов, рангов и диагоналей.
  • Поворот или зеркальное отображение доски (для проверки симметрий, которые дают тот же результат, что и что-то уже рассчитанное).

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

  • Связанные списки имеют O (n) (линейное) время поиска. Кроме того, поскольку мы не можем «сканировать и обновлять доску» за один проход по доске, использование списков представляется очень непрактичным.
  • Кортежи имеют O (1) (постоянное) время поиска. Однако представление доски в виде кортежа фиксированного размера очень затрудняет итерации по рядам, файлам, диагоналям или другим видам последовательных квадратов. Кроме того, и Elixir, и Haskell (это два известных мне функциональных языка) не имеют синтаксиса для чтения n- го элемента кортежа. Это сделало бы невозможным написание динамического решения, которое работало бы для плат произвольного размера.

Elixir имеет встроенную структуру данных Map (и Haskell Data.Map), которая позволяет O (log n) (логарифмический) доступ к элементам. Прямо сейчас я использую карту с x, yкортежами, которые представляют позицию в качестве ключей.

Это «работает», но неправильно использовать карты таким образом, хотя я не знаю точно, почему. Я ищу лучший способ хранения двумерной игровой доски на функциональном языке программирования.

Qqwy
источник
1
Я не могу говорить о практике, но две вещи приходят мне на ум от Haskell: молнии , позволяющие «шагать» в постоянном времени по структурам данных, и комонады, которые связаны с молнией по какой-то теории, которую я не помню и не понимаю; )
phipsgabler
Насколько велика эта игровая доска? Большой О характеризует, как алгоритм масштабируется, а не как быстро. На маленькой доске (скажем, менее 100 в каждом направлении) O (1) против O (n) вряд ли будет иметь большое значение, если вы прикоснетесь к каждому квадрату только один раз.
Роберт Харви
@RobertHarvey Это будет меняться. Но для примера: в шахматах у нас есть доска 64х64, но все вычисления позволяют проверить, какие ходы возможны, и определить эвристическое значение текущей позиции (разница в материале, король в чеке или нет, пройденные пешки и т. Д.) всем нужно получить доступ к квадратам доски.
Qqwy
1
У вас есть доска 8х8 в шахматах. В языке с отображением в памяти, таком как C, вы можете сделать математический расчет, чтобы получить точный адрес ячейки, но это не так в языках с управлением памятью (где порядковая адресация является деталью реализации). Меня не удивит, если переход через (максимум) 14 узлов займет примерно столько же времени, сколько и обращение к элементу массива в языке с управлением памятью.
Роберт Харви
См. Также stackoverflow.com/q/9611904/124319
coredump

Ответы:

6

A Mapявляется точно правильной базовой структурой данных здесь. Я не уверен, почему это заставит вас чувствовать себя неловко. У него хорошее время поиска и обновления, динамический размер и очень легко создавать производные структуры данных. Например (в haskell):

filterWithKey (\k _ -> (snd k) == column) -- All pieces in given column
filterWithKey (\k _ -> (fst k) == row)    -- All pieces in given row
mapKeys (\(x, y) -> (-x, y))              -- Mirror

Еще одна вещь, которую часто трудно понять программистам, когда они впервые начинают программировать с полной неизменностью, это то, что вам не нужно придерживаться только одной структуры данных. Обычно вы выбираете одну структуру данных в качестве «источника правды», но вы можете создать столько производных, сколько захотите, даже производных производных, и вы знаете, что они будут синхронизироваться столько, сколько вам нужно.

Это означает, что вы можете использовать Mapверхний уровень, затем переключиться на Listsили Arraysдля анализа строк, затем Arraysпроиндексировать другой способ для анализа столбцов, затем битовые маски для анализа шаблонов, а затем Stringsдля отображения. Хорошо разработанные функциональные программы не передают ни одной структуры данных. Это последовательность шагов, в которых используется одна структура данных и создается новая, подходящая для следующего шага.

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

Карл Билефельдт
источник
4

Я сделал это недавно в F #, и в итоге я использовал одномерный список (в F # это односвязный список). На практике скорость индексации списка O (n) не является узким местом для плат, пригодных для использования человеком. Я экспериментировал с другими типами, такими как 2d массив, но в конце концов это был компромисс либо написания моего собственного кода проверки на равенство значений, либо перевода ранга и файла в индекс и обратно. Последнее было проще. Сначала я бы сказал, чтобы он работал, а затем, при необходимости, оптимизировал тип данных. Это вряд ли будет иметь достаточно большое значение, чтобы иметь значение.

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

let pos r f = {Rank = r; File = f} // immutable record type
// or
let pos r f = OnBoard (r, f) // algebraic type
...
let testBoard =
    Board.createEmpty ()
    |> Board.setPiece p (pos 1 2)
    |> ...

К этому коду (или к любому вызывающему коду) не имеет значения, как будет представлена ​​доска. Правление представлено операциями над ним больше, чем его основной структурой.

Кейси Спикман
источник
Здравствуйте, у вас есть код где-то опубликован? В настоящее время я работаю над шахматной игрой на F # (проект для развлечения), и даже хотя я использую карту <Square, Piece> для представления доски, я бы хотел увидеть, как вы ее инкапсулировали в доску Тип и модуль.
Асибахи
Нет, это нигде не опубликовано.
Кейси Спикман
не могли бы вы взглянуть на мою текущую реализацию и посоветовать, как я могу ее улучшить?
Асибахи
Взглянув на типы, я остановился на очень похожей реализации, пока не добрался до типа Position. Я сделаю более тщательный анализ на Code Review позже.
Кейси Спикман