Je suis actuellement en train de mettre en œuvre quelque chose de tout à fait semblable aux dames. Donc, j'ai ce jeu de table et il y a des morceaux blancs et noirs. Où il n'y a ni morceaux blancs ni noirs, vous n'avez pas de morceaux.
Je fais actuellement la méthode Je me demande donc ce qui pourrait être le meilleur moyen de représenter le conseil d'administration. L'approche naïve serait d'avoir une matrice avec des 1 1 et des 2 d'une pièce, d'une pièce blanche et d'une pièce noire).
Autre idée serait à au lieu d'une représentation matricielle de la carte, dispose de 2 listes (ou de toute autre structure de données): une pour les pièces noires, autres pour le blanc.
Je suis en train de mettre en œuvre ce jeu pour tester certains algorithmes AI, alors ma principale préoccupation est la vitesse. Je mettrai fondamentalement 2 joueurs d'AI se jouer mutuellement, pour chaque tour que chaque joueur doit avoir une liste de tous ses mouvements valides, puis il choisira ce qui bouge à faire, cela se produisant toujours jusqu'à la fin du jeu (un joueur gagne ou il y a une cravate).
PS: Je ne demande pas à propos de l'algorithme IA, je veux juste savoir quelle serait la meilleure structure de données pour gérer le tableau, de sorte qu'il facilite la tâche de
getvalidmoves () qui retournera tous les mouvements actuels que l'on peut faire avec la carte actuelle.
6 Réponses :
Pensez à utiliser un bitmap: deux Ints non signés de 64 bits, un pour blanc et un pour le noir. Ensuite, vous pouvez représenter des mouvements et des positions de la carte en fonction de La plupart des trucs de position de la carte peuvent être effectués avec des arithmétiques entier, ce qui est à peu près aussi rapide que possible. (w x b) -> (w x b) où w , b représentent l'ensemble des positions noires blanches et possibles possibles respectivement.
Cela va fondamentalement la même chose qu'une matrice d'INT (c'est-à-dire une matrice 2D). Et cela sera encore plus lent qu'une matrice.
Ne soyez pas stupide. La gestion d'une matrice d'intens prend au moins 64 opérations à chaque fois. L'utilisation d'une carte de bits dans un Int 64 bits peut faire des comparaisons, etc. en une seule opération.
Je suis curieux de voir quelles opérations seraient nécessaires pour comprendre les mouvements possibles étant donné votre représentation bitmap.
Je suis trop. En supposant que j'ai un tableau vide avec seulement 1 pièce à (0,0), Ho voudrais-je voir à quels États je pourrais aller de là?
Index de bit MOD 8 avec des bords. Ou énumérer les cellules suivantes.
J'utiliserais également un bitmap pour cela. Les fonctions à vérifier pour 1, 2 et 3 seront un peu intuulées à écrire, mais devraient être très rapides.
Vous devez bien entendu faire attention aux cas de bord et une solution rapide impliquera probablement des arithmétiques entier et modulaires sur les index.
Un moyen courant de faire est avec une représentation binaire de type L'utilisation est simple - par exemple, si vous souhaitez vérifier si toutes les pièces peuvent bouger dire de haut et à droite, passez la représentation des pièces du lecteur 7 bits à gauche et vérifiez s'il y a des pièces adversaires là-bas, puis les déplacer 7. Les bits sont à nouveau laissés et vérifiez si ces carrés sont clairs ... long pour chaque joueur.
(Comme il y a 64 carrés sur la planche) .. comme Charlie déjà dit ..
Voici un très bon (mais le général General) Article Wiki .
Je l'ai utilisé dans une compétition Reversi une fois et peut dire que la mise en œuvre n'était pas trop difficile.
Hth.
En termes de listes, je recommanderais vivement contre l'utilisation d'une structure utilisant des listes liées dans cette situation. Vous connaîtrez probablement déjà les positions que vous souhaitez enquêter (coordonnées X-Y), et une liste liée) nécessiterait En termes de comment organiser les données, j'imagine qu'une implémentation où le noir et le blanc est stockée dans la même structure serait idéal. Vous aurez des frais générales depuis que Stockage J'espère que cela aide. O (n) temps pour saisir simplement la valeur de l'espace de damier. Comme d'autres réponses ont été mentionnées, un bitmap ou une approche longue serait idéal.
2 et 3 en binaire nécessite la même quantité de mémoire, cependant, si vous écrivez des dames, vous aurez probablement besoin de stocker " Kinged "des données quand même. Avoir la possibilité de vérifier si un espace est ouvert en effectuant une recherche unique devrait fournir une prestation de performance significative.
Tout d'abord, il convient de noter que dans les dames, la moitié des places sur les planches ne peut jamais être utilisée, vous n'avez donc pas besoin d'un tableau de 32 articles, pas 64. Prendre en compte les rois, vous obtenez des possibilités de 0 à 4 au lieu de 0 à 2 (bien que lorsque je l'ai fait, je l'ai trouvé plus facile à utiliser -3 à +3 à la place, les valeurs de rouge et de noir ont donc la même ampleur et les mêmes signes).
Cela dépend de ce que vos algorithmes d'IA vont faire. La plupart des algorithmes AI feraient une sorte de recherche sur les mouvements possibles au moins plusieurs étapes à venir. Dans ce cas, vous ferez beaucoup de copies de votre représentation du conseil et il est logique d'essayer de le garder petit que le temps de copier votre structure de données dominera le temps nécessaire pour obtenir une liste des mouvements possibles et de limiter la profondeur à que vous pouvez rechercher.
Cependant, si vous ne cherchez pas, je créerais une pièce de classe et stockerais la couleur, l'emplacement et si la pièce est un roi. J'aurais alors une gamme de références à 8 bidimensionnelles de 8 par 8 de 8 de 8. Une liste liée des pièces noires et une liste liée des morceaux rouges. Chaque élément de la matrice indiquerait une pièce de la liste rouge ou noire ou à un morceau "vide" (NULL fonctionnerait pour cela). Lorsque vous déplacez une pièce, vous mettez simplement à jour l'objet pièce dans la liste et déplacez la référence de son emplacement actuel vers le nouvel emplacement, en réglant l'ancien emplacement à la pièce vide. Pour une légère augmentation du coût d'une mise à jour, vous obtenez un moyen efficace de se déplacer efficacement des pièces de côté et une recherche constante de l'état de n'importe quel endroit particulier du tableau.
Vous devriez faire itérair la liste complète pour supprimer une pièce morte, mais cela peut également être efficace avec un léger changement en pièce. Vous pouvez stocker une "morte" bool dans l'objet pièce. Lorsqu'un morceau est tué, fixez-le sur TRUE et retirez-le de la planche en remplaçant la référence avec la pièce vide. Lorsque vous ithétiez l'une ou l'autre liste de pièces, supprimez simplement n'importe quelle pièce marquée comme morte de la liste.