Discussion :

[Miksimus]

Voilà le programme Minmax tel que j'ai pu le prendre sur http://www.seanet.com/~brucemo/topics/topics.htm

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
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
int MinMax(int depth)
{
    if (SideToMove() == WHITE)    // White is the "maximizing" player.
        return Max(depth);
    else                          // Black is the "minimizing" player.
        return Min(depth);
}
 
int Max(int depth)		// Au tour des BLANCS de jouer
{
    int best = -INFINITY;
 
    if (depth <= 0)
        return Evaluate();
    GenerateLegalMoves();
    while (MovesLeft()) {
        MakeNextMove();
        val = Min(depth - 1);
        UnmakeMove();
        if (val > best)
            best = val;
    }
    return best;
}
 
int Min(int depth)		// Au tour des NOIRS de jouer
{
    int best = INFINITY;  // <-- Note that this is different than in "Max".
 
    if (depth <= 0)
        return Evaluate();
    GenerateLegalMoves();
    while (MovesLeft()) {
        MakeNextMove();
        val = Max(depth - 1);
        UnmakeMove();
        if (val < best)  // <-- Note that this is different than in "Max".
            best = val;
    }
    return best;
}

GenerateLegalMove()
MakeNextMove()
MovesLeft()
UnmakeMove()
Ces quatres fonctions (bien que je ne vois pas encore commment je vais m'y prendre) semble réalisable
Cependant je n'arrive pas à comprendre à quoi sert la fonction Evaluate() et même si j'ai une petite idée, je ne vois pas comment la réaliser...

Pourriez-vous m'apporter vos lumières ?...

[fearyourself]

Premièrement: Où est le C dans la question? D'accord tu as du code C mais cela ne veut pas dire que tu dois mettre ton message ici! Ta question a sa place dans le forum Algorithme...

La fonction Evaluate évalue le jeu courant. Généralement, cette évaluation se fait sous forme d'entier avec la convention:

Plus le nombre est grand, mieux c'est pour le joueur qui évalue. Donc si j'évalue un état de jeu dans lequel j'ai gagné, j'aurais un très bon score et si c'est un état où j'ai perdu, la fonction va me rendre un entier très petit (voir même négatif, cela dépend des implémentations...).

Finalement, la fonction Evaluate est au centre de la réussite de ce genre d'algorithme. En choisissant mal, l'IA fera tout et n'importe quoi...

Jc

[fearyourself]

Premièrement: Où est le C dans la question? D'accord tu as du code C mais cela ne veut pas dire que tu dois mettre ton message ici! Ta question a sa place dans le forum Algorithme... Sauf si tu as déjà un algorithme pour ta fonction, mais

Cependant je n'arrive pas à comprendre à quoi sert la fonction Evaluate() et même si j'ai une petite idée, je ne vois pas comment la réaliser...

me fait douter...

La fonction Evaluate évalue le jeu courant. Généralement, cette évaluation se fait sous forme d'entier avec la convention:

Plus le nombre est grand, mieux c'est pour le joueur qui évalue. Donc si j'évalue un état de jeu dans lequel j'ai gagné, j'aurais un très bon score et si c'est un état où j'ai perdu, la fonction va me rendre un entier très petit (voir même négatif, cela dépend des implémentations...).

Finalement, la fonction Evaluate est au centre de la réussite de ce genre d'algorithme. En choisissant mal, l'IA fera tout et n'importe quoi...

Jc

[EDIT]
Mon ordinateur rame, voici une des conséquences... hmpffff
Je l'effacerais bien mais bon... Montrons au grand jour ma .....
[/EDIT]

[Trap D]

Intéressant ce second post

[Miksimus]

Premièrement: Où est le C dans la question? D'accord tu as du code C mais cela ne veut pas dire que tu dois mettre ton message ici! Ta question a sa place dans le forum Algorithme...

OK, toutes mes excuses.
Si j'ai bien compris, le gros du boulot ici, c'est cette fonction Evaluate().

Bon on théoriquement, construit un arbre qui représente les choix possible de l'adveraire (qui minimisera le score rendu par Evaluate()) et les choix possibles de l'I.A. (qui augmentera ce même score)

La théorie, ça va...
Mais mettre ça en C, j'ai un peu du mal... Je ne vois pas quoi utiliser...
Dois-je faire des listes ? ou autres choses ?

Donc tout ceci aura sa place dans la fonction Evaluate() ?

Merci...

[fearyourself]

Premièrement: Où est le C dans la question? D'accord tu as du code C mais cela ne veut pas dire que tu dois mettre ton message ici! Ta question a sa place dans le forum Algorithme...

OK, toutes mes excuses.
Si j'ai bien compris, le gros du boulot ici, c'est cette fonction Evaluate().

Bon on théoriquement, construit un arbre qui représente les choix possible de l'adveraire (qui minimisera le score rendu par Evaluate()) et les choix possibles de l'I.A. (qui augmentera ce même score)

La théorie, ça va...
Mais mettre ça en C, j'ai un peu du mal... Je ne vois pas quoi utiliser...
Dois-je faire des listes ? ou autres choses ?

Généralement, c'est plutôt un arbre qui est construit. On le voit comme un arbre mais c'est l'algorithme Min-Max qui fera ton travail...

C'est ce qui est fait ici:

Code :

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

1
2
3
4
5
 
while (MovesLeft()) {
        MakeNextMove();
        val = Min(depth - 1);
        UnmakeMove();

Bien sûr, dépendant du jeu, UnmakeMove n'est pas toujours facile à faire.

Donc tout ceci aura sa place dans la fonction Evaluate() ?

Merci...

Non, ta fonction Evaluate évalue un état de jeu, c'est à l'algorithme Min-Max de faire le parcours dans les états différents.

Jc

[Miksimus]

ok merci pour tes réponses...

Généralement, c'est plutôt un arbre qui est construit. On le voit comme un arbre mais c'est l'algorithme Min-Max qui fera ton travail...

C'est ce qui est fait ici:

Code :

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

1
2
3
4
5
 
while (MovesLeft()) {
        MakeNextMove();
        val = Min(depth - 1);
        UnmakeMove();

Ok, ok.

Bien sûr, dépendant du jeu, UnmakeMove n'est pas toujours facile à faire.

Donc tout ceci aura sa place dans la fonction Evaluate() ?

Merci...

Non, ta fonction Evaluate évalue un état de jeu, c'est à l'algorithme Min-Max de faire le parcours dans les états différents.

Jc

D'accord, donc si j'ai bien compris, c'est cette fonction Evaluate() qui va m'aider à choisir le meilleur déplacement que l'AI devra effectuer...

j'ai commencé à coder...
voici GenerateLegalMove() qui a été réalisé pour les deplacements de pions de reversi (othello), ces déplacements se caractérisent de 3 façons que j'ai mis en commentaire.

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
19
20
21
22
23
int* GenerateLegalMoves()
{
	int i;
	int* legalMoves;
	if (SideToMove()=="B")
	{
		for (i=0; i++; i<8)
		{
			for (j=0; j++; j<8)
			{
				if (EstVide(Case(i,j)) /*A son tour de jeu, le joueur doit poser un pion de sa couleur sur une case vide de l'othellier,...*/ 
					   && ProcheAdv(i,j) /* ...adjacente à un pion adverse...*/ 
					   && PionEncadre(i,j))// ...Il doit également, en posant son pion, encadrer un ou plusieurs pions adverses entre le pion qu'il pose et un pion à sa couleur, déjà placé sur l'othellier.
				{
					legalMove = ajoute((i,j)) ???// si la case correspond à un mouvement possible, on ajoute les coordonnées à legalMove
				}
			}
		}
	}
	//plateau[i][j]
 
	return legalMove;	
}

Voilà, donc une fois que l'on a tous les déplacements possible, on en déduit UnmakeMove normalement...
Et donc une fois ces déplacements trouvé on trouve grâce à la fonction Evaluate() le meilleur choix à faire...
Ai-je bien compris...?

[fearyourself]

Oui, c'est une solution.

Ce que t'es en train de faire comme programme n'est pas évident. Visiblement, tu apprends (sinon tu ne posterais pas ici ).

Je te conseille donc de programmer en 3 grandes étapes:

- Elaborer un algorithme, sans parler de programmation ni même réflechir à l'implémentation sous-jacente.

Cette partie peut-être vague ou très détaillée, cela dépend...

- Réfléchir à la traduction algo-langage, cela est plus facile si l'algorithme est bien pensé et relativement détaillé. Un algorithme trop détaillé risque d'utiliser des concepts qui ne sont pas fait pour le langage...

- Implémenter vraiment le programme...


Toi tu fusionnes les trois. Bien que tu y arriveras sûrement, tu vas droit à l'erreur de conception...

Je conseille donc de faire un pas en arrière, te dire que t'es dans le forum Algorithme et de montrer des algorithmes sans code C! Cela peut sembler être une perte de temps au début, mais sans algorithme et allant directement au code, on perd généralement plus de temps...

Jc

[davcha]

Et donc une fois ces déplacements trouvé on trouve grâce à la fonction Evaluate() le meilleur choix à faire...
Ai-je bien compris...?

Evaluate sert à donner une note à un déplacement donné.

Si tu vires tout le concept du minmax pour ne garder que Evaluate : un minmax de profondeur 0 (ou 1 selon les implémentations), alors ton algorithme va effectuer chaque coup possible de la situation de départ et donner une note à chacune des situations d'arrivée.

Exemple :
Tu es dans une position où tu as 5 coups possibles, tu fais :

Code :

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

1
2
3
4
5
for(i=0;i<5;i++){
  faire_le_coup(i);
  notes[i] = evaluer();
  defaire_le_coup(i);
}

Tu te retrouves avec un tableau de notes.
Une note représente la qualité d'une situation, mais comme les situations notées découlent d'un coup (ou d'une série de coups), ça revient à associer chaque note à chaque coup menant à la situation notée.

Ensuite, le minmax te permet d'aller voir "plus loin" ce qui va se passer.
Exemple :
Tu as une série de 5 notes, et la meilleure note est la note i=2 (le 3e coup donc). Mais une fois le 3e coup effectué, tu te rends compte que tous les coups suivants que tu peux faire à partir de la nouvelle situation sont tout à fait merdiques, finalement ça veut dire que le 3e coup n'était pas le meilleur.
Donc, on fait une recherche sur plus d'un demi-coup.



Pour la fonction Evaluer en elle-même, il faut te poser la question "qu'est-ce qui va me faire gagner (ou faire perdre l'adversaire) ?". Aux échecs, le premier joueur qui ne peut pas jouer a perdu, il faut donc :
- soit maximiser le nombre de coups légaux de l'IA
- soit minimiser le nombre de coups légaux de son adversaire.

[Sivrît]

Le Min-Max n'étant pas un algo trivial, tu as effectivement intéret à avoir les idées claire sur son fonctionnement.

Evaluate() est ce que l'on appelle une heuristique, c'est à dire une recette expérimentalle qui aide à jouer. Pour Othello on peut en première approche faire (nombre de pions à soi - nombre de pions adverses). Plus l'heuristique reflette fidèlement la valeur d'une position, la proximité de la victoire, et meilleure elle est (et plus compliquée généralement aussi).

On pourrait se limiter à jouer en maximisant l'heuristique que j'ai proposé (ce que fait un joueur débutant... disons comme moi ) mais ça ne marche pas très bien car cette heuristique ne prend pas en compte l'évolution future du jeu. Pour ça on a le Min-Max ! C'est lui qui introduit la vision à long terme.

Sur le plan théorique, on considère l'arbre des mouvements possibles (tronqué à une profondeur donné). On utilise l'heuristique pour chiffrer les feuilles, donc Evaluate() founie la base du raisonnement. Ensuite, pour chaque étage on remonte les valeurs en alternant minimums (l'adversaire, lors de ses tours, est supposé jouer intelligemment, c'est à dire en minimisant l'heuristique) et des maximums (tant qu'a faire on va la maximiser à nos tours ). Quand on arrive en haut il ne reste qu'à choisir ce qui semble le meilleur coup, le moins pire : Le min-max sert à trouver le coup qui laisse à l'adversaire les moins bonnes alternatives.

Après, il est possible de parcourrir l'arbre (virtuel) en profondeur sans le construire, comme le fait le code que tu as cité (c'est un peu mieux pour la pauvre RAM). Plus simple et plus rapide somme toute. Par contre la difficulté est de pouvoir remonter, ie défaire les coups.

En effet pour Othello UnmakeMove n'est pas une évidence. Le plus simple à coder me semble de faire une copie du jeu, d'y appliquer le coup et de passer la copie à l'appel récursif.

Plus rapide ce serait de garder les changements dùs à un coup dans une liste (ou équivalent), genre (attention, pseudo C !) :

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
19
20
21
 
int Max(int depth)      // Au tour des BLANCS de jouer
{
    int best = -INFINITY;
 
    if (depth <= 0)
        return Evaluate();
 
    ListeCoups listeCoupsPossibles = GenerateLegalMoves(BLANCS);  // <-- Les coups possibles dépendent du camp qui joue !
    while ( ! listeCoupsPossibles.estVide()) {
        Coup coup = listeCoupsPossibles.suivant();
        ListeChangements listeChangements = MakeNextMove(coup);
 
        val = Min(depth - 1);
        if (val > best)
            best = val;
 
        UnmakeMove(listeChangements);
    }
    return best;
}

[Miksimus]

OK.

Merci tous les trois pour vos enrichissantes réponses...

Je vais donc m'ateler à developper un peu plus un algorithme puis ensuite à basculer en C.
Je reviens écrire dès que j'ai avancé.


Merci encore...