Min-max algorithm and game theory

Quel est le terme utilisé pour décrire une structure de données où chaque nœud peut avoir plusieurs liens vers d'autres nœuds?

Quel élément d'une arborescence Unix est indiqué par la commande 'pwd'?

Comment appelle-t-on les nœuds qui sont les fins de mots dans un arbre lexical?

Quelle opération décrit l'arbre lexical représentant l'ensemble de mots {dans, de, des, la, le, les, lui, un, une}?

Quelle expression mathématique décrit l'arbre quartique d'une image carrée en noir et blanc?

Combien d'enfants ont les nœuds internes dans un quadtree?

Qu'est-ce qu'un jeu à somme nulle ?

Sur quoi repose l'algorithme du min-max dans les jeux à information complète ?

Quel rôle joue l'évaluation de la valeur d'une situation dans l'algorithme du minimax ?

Qu'est-ce qui caractérise un jeu à information complète selon le texte ?

Quelle est la fonction principale des arbres dans l'algorithme du min-max ?

Pourquoi l'évaluation de la valeur d'une situation est-elle importante dans la création d'une IA pour jouer aux jeux à information complète ?

Quelle est la complexité temporelle de l'algorithme de parcours en largeur si la file d'attente est correctement implémentée?

Que représente la liste 'Liste niveau' dans l'algorithme de parcours en largeur?

Que se passe-t-il si la file d'attente dans l'algorithme de parcours en largeur est mal implémentée?

Quelle structure de données est utilisée pour implémenter le parcours en profondeur dans l'algorithme présenté?

Quelle est la différence principale entre le parcours en profondeur et le parcours en largeur d'un arbre?

Jeux à information complète et à somme nulle

Les deux joueurs ont à tout moment toute l'information sur l'état du jeu.
Les gains réalisés par un joueur sont des pertes pour son adversaire, ce qui implique qu'il y a forcément un gagnant et un perdant (ou un match nul).
Les meilleurs coups de jeu pour l'un sont les pires pour l'autre.

Algorithme du min-max

Il permet de faire jouer "intelligemment" un programme à de tels jeux.
Il est basé sur des arbres.
Il permet de déterminer la meilleure prochaine situation à jouer.

Fonctions pour créer une IA avec l'algorithme du min-max

Détermine si une situation est finale ou non.
Calcule les situations suivantes d'une situation donnée.
Évalue la valeur d'une situation (la fonction eval).

Les arbres

Une liste est une séquence de boites où chaque boite donne accès à au plus une boite suivante.
Un arbre est une structure où chaque boite contient des liens vers plusieurs boites.
Les boites sont les nœuds de l'arbre.
Le premier nœud auquel on a accès est la racine de l'arbre.

Exemples d'arbres

L'arborescence Unix : la racine est /, un répertoire peut contenir des répertoires et des fichiers normaux.
Les expressions arithmétiques : l'arbre représente les opérations et les valeurs.
Les arbres lexicaux : les mots sont représentés par des arbres où les nœuds en gras désignent les fins de mots.
Les arbres quartiques : les nœuds internes ont 4 enfants, les feuilles sont colorées.

Algorithmes de parcours d'arbre

Algorithme de parcours en profondeur : utilise une pile pour stocker les nœuds à visiter.
Algorithme de parcours en largeur : utilise une file d'attente pour stocker les nœuds à visiter.
Temps d'exécution : O(n) si la file d'attente est correctement implantée.

Please use this form to submit feedback or report bugs. You can find answers to most questions in our Help Center.