Discussion :

[shirya]

Bonjour, à tous,
j'essaie de faire un petit programme de tic tac toe. Seulement la taille du tableau pourra varier (de 3X3, 4X$....10X10).
Je suis un peu perdue... je ne sais trop comment commencer.
J'ai regarder l'algorithme minimax: En gros, on construit un arbre de toutes les possibilités de jeu à partir de la position courant et on évalue pour savoir quel est le meilleur mouvement à effectuer.
En fait, je ne sais pas trop quel genre d'arbre dois-je construire, pour me permettre d'évaluer chaque noeud et de dire: à cette feuille, Telle joueur est gagnant donc la feuille aura un plus....

Doi-je construire un arbre, où tout les noeuds ont le tableau du jeu (avecun mouvement de plus) ..Mais alors quand il y a 10X10 cases cela ne devient pas trop lourd.... Auriez-vous de meilleurs idées?
merci.

[TheLeadingEdge]

Bonjour,

Mais alors quand il y a 10X10 cases cela ne devient pas trop lourd...Auriez-vous de meilleurs idées?

Pour éviter l'explosion combinatoire tu dois élaguer le parcours de ton arbre. Il faut se limiter a évaluer les noeuds dont les valeurs changent et qui sont moins mauvais que le meilleur que tu as déjà calculé. Pour ça tu peux utiliser l'algo. de cutoff alphabeta.

PS: Je déplace ta question. Maintenant il y a un forum pour ce genre de sujets sur DVP
Intelligence Artificielle.
A +

[ToTo13]

Bonjour,

Doi-je construire un arbre, où tout les noeuds ont le tableau du jeu (avecun mouvement de plus) ..

Non, on ne construit pas l'arbre à proprement parlé
En revanche, le fait de parcourir exhaustivement toutes les possilités se shématise facilement par un arbre des possibilités.
Donc tu fais une récursivité qui va te faire faire toutes les possibilités pour un nombre de N coups à l'avance.

[shirya]

ok, je vais regarder l'algo alphabeta merci.

Non, on ne construit pas l'arbre à proprement parlé
En revanche, le fait de parcourir exhaustivement toutes les possilités se shématise facilement par un arbre des possibilités.
Donc tu fais une récursivité qui va te faire faire toutes les possibilités pour un nombre de N coups à l'avance.

on ne construit pas d'arbre?ok, je crois avoir mal compris alors...peux tu m,expliquer
Voilà ce que j'ai compris:
Lorsque c'est au tour de l'ordinateur de jouer, à partir du jeu courant, il va regarder toutes les possibilités et calculer le meilleur mouvement à effectuer. C'est pas là qu'il construit un arbre de possibilité?
Aussi, si c'est l'ordinateur qui commence,est ce que j'ai vraiment besoin de calculer toutes les possibilités?je peux directement mettre le jeton au milieu non?

[Alp]

L'ordinateur ne construit pas d'arbre.
Sa façon de parcourir toutes les possibilités lui permettant de voir N coups à l'avance, par contre, peut se schématiser sous forme d'arbre.

[Veovis]

Pour faire extrêmement simple voici l'algorithme minmax. Comme tu peux le voir je ne construit pas d'arbre. Juste je déroule toutes les possibilités du jeu.

On peut représenter l'ensemble des couts à jouer comme un arbre. C'est pour cela que nous parlons d'arbre, mais ce n'est qu'un abus de langage.

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
 
function minmax(depth, matrice, alpha, beta)
 g = -5000
 
 if depth == depth_max
   return evaluer(matrice)
 end
 
 v = Tous les couts a jouer de ta matrice
 for i = 0, i < v.size, i++
    Jouer le cout v[i] sur la matrice
    valeur = minmax(depth+1, matrice, -beta, -alpha)
    Dejouer le cout v[i]
    if valeur > g : g = valeur
    if valeur > alpha : alpha = valeur
  end
  return valeur
end

[shirya]

ok je crois que j'ai compris,
merci pour vos réponses

[shirya]

re-Bonjour,
je n'ai plus touché à mon projet depuis un bout, mais là je m'y remet:
je commence tranquillement à réfléchir à ma fonction d'évaluation de mon jeu et je me demande si vous auriez quelques suggestions car je ne suis pas trop sûre de comment l'implémenter.
(c'est un jeu Tic Tac Toe avec grille variable 3X3, 4X4,...,NXN)

Voilà mes priorités de mon plateu de jeu:

1. Il y a une ligne de mes X complétée(soit 3 X, 4 X ...).

2. Il y a une ligne O de mon adversaire de complétée.

3. J'ai mes X placés de telle que je peux gagner de deux façons(une fourchette je crois).

4. Mon adversaire peut créer une fourchette, le bloquer

5. jouer au centre

Je me demande donc comment faire pour évaluer un jeu avec ces priorités?

Faut-il en premier lieu que je regarde pour chaque ligne de ma matrice si il y a une ligne de mes X de complétée, ensuite chaque colonne... et comment fait-on pour les diagonale? Y a-t-il un moyen plus simple

Ensuite, je regarde pour les lignes de mon adversaire et je fais la même vérification.

Quel algorithme me permettrait de savoir s'il y a une fourchette? surtout que la taille de la grille peut varier

finalement, quelle valeur donner a mon évaluation si une victoire correspond à 100, une égalité à 0 et un défaite à -100??

Bref, je ne sais pas trop comment commencer, si vous avez des pistes, des sites, des conseils... tout me sera utile
merci
Shirya

[Veovis]

Tu peux combiner plusieurs fonctions d'évaluations :

En fonction des piéces joué le nombre d'ouverture possible de l'ordinateur - le nombre d'ouverture du joueur

La place des pions dans le jeu (par exemple pour le jeu d'échec, on va mettre plus de point pour les piéces au centre), etc...

Aprés tu peux imagnier, tout ce que tu veux...

[doccpu]

je serais toi j'essaierais de calculer les coups en regardant la configuration des pions sur la grille et d'en déduire les différents coups que le prochain joueur peut effectuer (dans le sens effectuer pour gagner) pour le prochain coup et ensuite peut être construire un arbre a partir de ce coup. Par exemple il est plus intéressant pour un joueur de jouer sur une ligne déjà remplie en partie (sans obstacle (pion adverses ou mur)). en gros cela reviens a vérifier que le coups qui viens d'être joué est dangereux ou non. si il l'est opposer un obstacle sinon jouer le meilleur coup possible.

pour un 3x3 il suffit de commencer et de prendre 3 angle pour gagner a tous les coups