Tic-Tac-Toe: Comment remplir l'arbre de décision?

Question

Je fais un programme Tic-Tac-Toe. Je prévois d'utiliser minimax avec elle. J'ai fait un arbre avec de l'espace pour toutes les séquences de jeu possibles et je cherche un moyen de le peupler. J'ai actuellement ce type:

typedef struct name 
{ 
    char grid [3] [3]; 
    struct name * child [9]; 
} node; 

et je suis à la recherche d'un moyen de remplir la grille comme il est montré here. Comment pourrais-je aller remplir la grille pour m'assurer que toutes les combinaisons possibles sont là? Mon plan est de faire en sorte que le jeu reconnaisse chaque mouvement que le joueur peut prendre et décide ensuite des étapes à suivre pour gagner (j'ai encore besoin de comprendre la partie décision, mais je le maintiens jusqu'à ce que je puisse remplir les grilles dans l'arbre) .

Answer 1

Sonne comme un candidat de choix pour la récursivité pour moi ...

Answer 2

pseudocode parce récursion est difficile à faire dans une liste:

function descend(X_or_O, board) 
    for square in board 
     If square isn't empty: continue 
     new_board = Fill in square with X_or_O. 
     Check for a winner (if yes, return) 
     newer_board = descend(opposite of X_or_O, new_board) 
     tack newer_board onto the tree. 
     clear out square 

Vous devriez être en mesure de le faire avec un couple for boucles et if déclarations.

Answer 3

Encoder les positions dans la base 3. Créer une grille inutilisée 0; une grille avec "X" a 1; et une grille avec "O" a 2. Donc le nombre maximum absolu de grilles complètes que vous pouvez avoir est 3^9 = 19683 (certaines de ces représentations tic-tac-toe sont invalides)

Donc disons que vous avez affaire à '020112021'. Ses enfants sont:

020112021 /* father */ (4759 base 10) 
========= 
020112022     father + 1 (1 base 3) 
0201120x1 /* invalid */ father + 3 (10 base 3) 
020112121     father + 9 (100 base 3) 
02011x021 /* invalid */ father + 27 (1000 base 3) 
020122021     father + 81 (10000 base 3) 
020212021     father + 243 
021112021     father + 729 
0x0112021 /* invalid */ father + 2187 
120112021     father + 6561 (100000000 base 3) 

Je pense que vous pouvez trouver un moyen de continuer à partir d'ici.

Answer 4

Child's play.

EDIT: Juste au cas où les pauses lien ci-dessus, il est une référence à une description de l'Tinkertoy informatique de Scientific American Octobre 1989, a également compilé et publié avec d'autres articles de loisirs SA du même auteur comme L'ordinateur Tinkertoy et d'autres Machinations. Les gars (et les filles) qui ont construit cette machine étaient assez intelligents pour éviter toute recherche alpha-bêta et comprimer le tableau en quelque chose qui pourrait facilement être calculé. Par Tinkertoys.

Answer 5

Ici vous avez une solution de travail. Il est implémenté en Python mais je pense que cela peut vous aider.

L'arborescence de jeu est créée récursivement par la fonction build_tree et est implémentée sous la forme d'une liste de listes.

La fonction build_tree prend une carte (un nœud de l'arbre) et la pièce qui a le tour de jouer comme paramètres d'entrée, et construit toutes les nouvelles cartes possibles résultant de l'application de la pièce à la carte. Ensuite, pour chacune de ces nouvelles cartes, il appelle à nouveau la fonction build_tree, mais cette fois en changeant la pièce qui a le tour de jouer. Lorsque la carte est terminale (pas de cases vides), la récursivité prend fin.

Ceci est l'arbre qui en résulte pour une carte de 1x3:

[(0, 0, 0), [[(x, 0, 0), [[('x', 'o', 0), [('x', 'o', 'x')]], [('x', 0, 'o'), [('x', 'x', 'o')]]] ], [(0, 'x', 0), [[('o', 'x', 0), [('o', 'x', 'x')]], [(0, 'x ',' o '), [(' x ',' x ',' o ')]]]], [(0, 0,' x '), [[(' o ', 0,' x ') , [('o', 'x', 'x')]], [(0, 'o', 'x'), [('x', 'o', 'x')]]]]] ]

Les carrés vides sont désignés par '0'.

Pour le jeu tactique, veuillez remplacer blank_board = (0,0,0) par blank_board = (0,0,0,0,0,0,0,0,0) afin d'avoir une carte 3x3.

def change_piece(piece): 
    if piece == 'x': return 'o' 
    return 'x' 

def is_terminal(board): 
    """Check if there are any empty square in the board""" 
    for square in board: 
     if square == 0: 
      return False 
    return True 

def build_tree(node, piece): 
    """Build the game tree recursively. 

    The tree is implemented as a list of lists. 
    """ 
    child_nodes = [] 
    for index, value in enumerate(node): 
     if value == 0: 
      new_node = list(node) 
      new_node[index] = piece 
      new_node = tuple(new_node) 
      if not is_terminal(new_node): 
       child_nodes.append(build_tree(new_node,change_piece(piece))) 
      else: 
       child_nodes.append(new_node) 
    if child_nodes: 
     return [node,child_nodes] 
    return 

if __name__ == "__main__": 
    blank_board = (0,0,0) 
    game_tree = build_tree(blank_board,'x') 
    print(game_tree) 

Answer 6

Ceci est un cas classique pour récursion:

typedef struct name 
{ 
    char grid [3] [3]; 
    struct name * child [9]; 
} node; 

node * new_grid(node *parent) { 
    node *n = calloc(1, sizeof(node)); 
    if (parent) 
     memcpy(n->grid, parent->grid, sizeof(grid)); 
} 

// is n a winner based on the move just made at x,y? 
int winner(const node *n, int x, int y) { 
    return (n->grid[x][0] == n->grid[x][1] == n->grid[x][2]) || 
      (n->grid[0][y] == n->grid[1][y] == n->grid[2][y]) || 
      ((x == y) && (n->grid[0][0] == n->grid[1][1] == n->grid[2][2])) || 
      ((2-x == y) && (n->grid[0][2] == n->grid[1][1] == n->grid[2][0])); 
} 

void fill(node *n, char c) { 
    int x, y, children; 
    node *child; 

    for (x = 0; x < 3; x++) { 
     for (y = 0; y < 3; y++) { 
      if (n->grid[x][y]) 
       continue; 
      child = n->child[children++] = new_grid(n); 
      child->grid[x][y] = c; 

      // recurse unless this is a winning play 
      if (!winner(child, x, y)) 
       fill(child, c == 'x' ? 'y' : 'x'); 
     } 
    } 
} 

int main(void) { 
    node *start = new_grid(0); 
    fill(start); 
}