Tic-tac-toe quantique avec élagage alpha-bêta - meilleure représentation des états?

Question

Pour ma classe AI, je dois faire un jeu quantum tic-tac-toe en utilisant l'élagage alpha-bêta. Je pense à la meilleure façon de représenter un état de la carte - ma première intuition est d'utiliser une sorte de matrice de voisinage, c'est-à-dire une matrice 9x9, et M[i,j] est l'entier qui représente le mouvement dans lesquels (tic-tac-toe) carrés i et j sont marqués (s'il n'y a pas une telle connexion - M[i,j] est zéro). M[i,i] n'est pas 0 si le carré i est réduit. Ensuite, je voudrais créer un arbre de jeu de telles matrices et utiliser le minimax classique avec l'élagage alpha-bêta. Cependant, il semble que cette approche serait assez coûteuse - il y aurait un facteur de branchement relativement grand plus les opérations de base pour chaque nœud - vérifier les cycles et trouver tous les états équivalents pour la matrice 9x9. J'ai l'impression qu'il doit y avoir une solution plus intelligente - peut-être quelque chose comme un jeu quantique comme un jeu de tic-tac-toe classique et une sorte de recherche minimax généralisée. tous régressent à un (petit) ensemble de problèmes classiques de tic-tac-toe? Je ne vois pas comment cela fonctionnerait exactement.

Quelqu'un at-il de l'expérience avec ce problème (ou un problème similaire), et pourriez-vous me diriger dans la bonne direction?

Answer 1

Si votre problème est juste Tic-Tac-Toe, que vous pouvez représenter votre conseil d'administration de la façon dont ce programme de la mine ne http://pastie.org/1715115

Il est une matrice de nombres à base ternaire. Un tableau est un nombre à 9 chiffres où chaque chiffre a l'une des 3 valeurs possibles: 0 pour vide, 1 pour x et 2 pour o.

Cette approche est excellente pour minimax car une carte peut être définie dans un seul entier! La matrice a une forme de:

int suc[TOTAL][2]={ { 0, 10000}, { 1, 20001}, { 10, 20010}, { 12, 1012}, { 21, 1021}, 
    { 100, 20100}, { 102, 100102}, ... 

où chaque paire de nombres correspond à (a) la position actuelle, et (b), la meilleure position suivante calculée au préalable par un Minimax. Donc, si la carte est vide (suc [0] [0] == 0) la meilleure position suivante est de mettre un 'x' dans la position 5, c'est-à-dire le centre (suc [0] [1] == 000010000)

En fait, avec ce programme, vous n'avez même pas besoin de créer un minimax car ce programme a déjà calculé toutes les réponses possibles dans la matrice ad-hoc. La fonction la plus importante, de choisir le prochain mouvement, se fait simplement à la recherche dans la matrice Suc (successeur):

/* find and return the next board after the given board terno */ 
int move(int terno) 
{ 
    int i; 

    for (i=0; i<TOTAL; i++) 
     if (suc[i][0]==terno) 
      return suc[i][1]; 
    return 0; 
} 

Il est une bonne approche pour les algorithmes quantiques (et les systèmes embarqués). J'espère que ceci vous aide.

prendre soin