Structure de données pour les jeux de société bidimensionnels dans les langages fonctionnels

Je crée une implémentation MiniMax simple dans le langage de programmation fonctionnel Elixir. Parce qu'il existe de nombreux jeux à connaissance parfaite (tic tac toe, connect-four, checkers, échecs, etc.), cette implémentation pourrait être un cadre pour créer des IA de jeu pour l'un de ces jeux.

Un problème auquel je suis confronté, cependant, est de savoir comment stocker correctement un état de jeu dans un langage fonctionnel. Ces jeux concernent principalement des plateaux de jeu à deux dimensions, où les opérations suivantes sont fréquentes:

• Lire le contenu d'un emplacement de carte spécifique
• Mettre à jour le contenu d'un emplacement de plateau spécifique (lors du retour d'une nouvelle possibilité de déplacement)
• Prise en compte du contenu d'un ou de plusieurs emplacements connectés à l'emplacement actuel (c'est-à-dire les emplacements horizontal, vertical ou diagonal suivant ou précédent)
• Tenir compte du contenu de plusieurs emplacements connectés dans n'importe quelle direction.
• Considérant le contenu de fichiers entiers, rangs et diagonales.
• Rotation ou mise en miroir de la carte (pour vérifier les symétries qui fournissent le même résultat que quelque chose déjà calculé).

La plupart des langages fonctionnels utilisent des listes et des tuples liés comme blocs de construction de base de structures de données multi-éléments. Cependant, ceux-ci semblent très mal faits pour le travail:

• Les listes liées ont un temps de recherche O (n) (linéaire). De plus, comme nous ne pouvons pas «scanner et mettre à jour la carte» en un seul balayage, l'utilisation de listes semble très peu pratique.
• Les tuples ont un temps de recherche O (1) (constant). Cependant, représenter le tableau comme un tuple de taille fixe rend très difficile l'itération sur les rangs, les fichiers, les diagonales ou d'autres types de carrés consécutifs. De plus, Elixir et Haskell (qui sont les deux langages fonctionnels que je connais) manquent de syntaxe pour lire le n ème élément d'un tuple. Cela rendrait impossible l'écriture d'une solution dynamique qui fonctionnerait pour des cartes de taille arbitraire.

Elixir a une structure de données de carte intégrée (et Haskell l'a Data.Map) qui permet l'accès O (log n) (logarithmique) aux éléments. Actuellement, j'utilise une carte, avec des x, ytuples qui représentent la position sous forme de clés.

Cela `` fonctionne '', mais il semble mal d'abuser des cartes de cette manière, même si je ne sais pas exactement pourquoi. Je cherche une meilleure façon de stocker un plateau de jeu bidimensionnel dans un langage de programmation fonctionnel.

A Mapest précisément la bonne structure de données de base ici. Je ne sais pas pourquoi cela vous mettrait mal à l'aise. Il a de bons temps de recherche et de mise à jour, sa taille est dynamique et il est très facile de créer des structures de données dérivées à partir de. Par exemple (dans 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

L'autre chose qui est souvent difficile à comprendre pour les programmeurs lorsqu'ils commencent à programmer avec une immuabilité totale est que vous n'avez pas besoin de vous en tenir à une seule structure de données. Vous choisissez généralement une structure de données comme «source de vérité», mais vous pouvez créer autant de dérivés que vous le souhaitez, même des dérivés de dérivés, et vous savez qu'ils resteront synchronisés aussi longtemps que vous en aurez besoin.

Cela signifie que vous pouvez utiliser un Mapau plus haut niveau, puis basculer vers Listsou Arrayspour l'analyse des lignes, puis Arraysindexé dans l'autre sens pour l'analyse des colonnes, puis les masques de bits pour l'analyse des modèles, puis Stringspour l'affichage. Des programmes fonctionnels bien conçus ne transmettent pas une seule structure de données. Il s'agit d'une série d'étapes qui prennent une structure de données et en émettent une nouvelle qui convient à l'étape suivante.

Tant que vous pouvez sortir de l'autre côté avec un mouvement dans un format que le niveau supérieur peut comprendre, vous n'avez pas à vous soucier de la façon dont vous restructurez les données entre les deux. C'est immuable, il est donc possible de tracer un chemin vers la source de la vérité au niveau supérieur.

Je l'ai fait récemment en F # et j'ai fini par utiliser une liste unidimensionnelle (en F #, c'est une liste à lien unique). En pratique, la vitesse de l'indexeur de liste O (n) n'est pas un goulot d'étranglement pour les tailles de carte utilisables par l'homme. J'ai expérimenté d'autres types comme le tableau 2d, mais à la fin, c'était le compromis d'écrire mon propre code de vérification d'égalité des valeurs ou une traduction de rank and file en index et en arrière. Ce dernier était plus simple. Je dirais que cela fonctionne d'abord, puis optimisez votre type de données plus tard si nécessaire. Il est peu probable que cela fasse une différence suffisamment importante pour être important.

En fin de compte, votre implémentation ne devrait pas avoir autant d'importance tant que les opérations de votre carte sont correctement encapsulées par le type et les opérations de la carte. Par exemple, voici à quoi pourraient ressembler certains de mes tests pour configurer une carte:

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)
    |> ...

Pour ce code (ou tout code appelant), la façon dont le conseil d'administration était représenté n'aurait pas d'importance. Le conseil d'administration est représenté par les opérations sur lui plus que sa structure sous-jacente.