Partage

zMorp - 2ème partie

Créer une IA

1 2 >>

2 janvier 2011 à 22:08:25

Mois: Janvier
Sujet: Boucles, manipulation de tableaux, pointeurs et récursivité

zMorp - 2ème partie

Maintenant que nous avons fait notre morpion en mode 2 joueurs, nous allons créer une petite intelligence artificielle, dite IA, afin de nous permettre de jouer seul contre l'ordinateur.
Je vais décomposer ça en 2 étapes :

1 - IA à coup de if :
Sûrement la plus simple à mettre en oeuvre, il vous suffit de faire une IA et d'essayer d'imaginer tous les coups possibles et de jouer au bon endroit en fonction de ça. On se limitera au morpion 3x3 pour cette option, à moins que vous n'ayez envie de faire quelques milliers de if. :-°

2 - IA avec un algorithme plus avancé :
*) Sûrement l'IA le plus adapté à un morpion, j'ai nommé l'algorithme min/max. Bien que son nom soit simple, son implémentation n'est pas des plus faciles pour un débutant. L'algorithme min/max est basé sur la récursivité, je vous conseille donc, avant de vous y attaquer, d'être un minimum à l'aise avec la récursivité.
Vous pouvez faire une simplification negamax sur votre algorithme min/max afin d'avoir des valeurs positives et négatives en fonction du noeud. Je vous le conseille, c'est plus pratique.

*) Une fois l'algorithme min/max fait, vous pouvez l'améliorer pour éviter de parcourir tout votre arbre, ce qui permet de gagner en temps. Pour un morpion 3x3, pas grande incidence, par contre pour un morpion de grande taille ou un jeu d'échecs par exemple, ça a tout son intérêt.

Je ne vous donne pas d'explications, ni de tutos, je vous laisse chercher par vous même. On trouve plein de tutos sur internet. Simplement, je vous demanderais une chose, et j'y tiens particulièrement : ne pompez pas le code trouvé sur d'autres sites !!! Ca n'apportera rien à l'exercice, et vous ça ne vous apportera rien non plus. Faites en sorte que vous code gère des parties de morpion non pas en 3x3, mais en NxN avec M pions à aligner.

Faites un code qui ne gère que le mode 1 joueur pour éviter de vous embêter à faire un menu de choix. Gardez le mode 1 joueur, mais mettez le 'en veille' (macros, conditions, etc.).

Si vous avez des questions, surtout n'hésitez pas à poser votre question ici.

Pour le code, je peux vous fournir un code, mais il vaut mieux que le code vienne de vous, c'est plus simple que de se plonger dans le code de quelqu'un d'autre.

Bon courage !

Loadware

8 janvier 2011 à 23:55:37

Peut-on poster le code d'un morpion réalisé en console avec PDCurses et qui ne gére que le mode 1 joueur ?

Pouet_forever

8 janvier 2011 à 23:58:21

Oui, rien ne l'interdit.

Il me semble que PDcurses est pour windows et ncurses pour toutes les plateformes. PDcurses est compatible ncurses ? si ce n'est pas le cas, tu peux essayer d'enlever la partie qui n'est pas compatible ncurse.

Loadware

9 janvier 2011 à 0:22:30

PDCurses est une version portable de ncurses tout simplement.

Voilà mon code :

main.c

#include <time.h>
#include <stdio.h>
#include <stdlib.h>
#include <curses.h>
#include "morpion.h"

int main(void)
{
    int continuer = 1, jouer = 1, boucle = 1;//booléens
    int nbrA = 0, grille[9] = {0}, choix = 0;
    const int min = 0, max = 8;
    
    srand(time(NULL));
    
    initscr();

    start_color();
    init_pair(1, CLR_JAUNE, COLOR_BLACK);
    init_pair(2, CLR_BLANC, COLOR_BLACK);
    init_pair(3, CLR_BLEU, COLOR_BLACK);
    init_pair(4, CLR_VERT, COLOR_BLACK);
    init_pair(5, CLR_ROUGE, COLOR_BLACK);
    init_pair(6, CLR_CYAN, COLOR_BLACK);
    init_pair(7, CLR_VIOLET, COLOR_BLACK);

    curs_set(0);
    noecho();

    morpion_chargerGrille();

    jouer = (rand() % 2);//le joueur commence 1 fois sur 2.

    while(continuer)
    {
        while(jouer)
        {
            attron(COLOR_PAIR(4));
            mvaddstr(17, 0, "Quelle case ?");
            attroff(COLOR_PAIR(4));

            refresh();

            choix = getch();//récupération de la touche appuyée

            if(choix >= '1' && choix <= '9' && grille[choix - '1'] == 0)//si on choisit entre 1 et 9
            {
                grille[choix - '1'] = 1;//la case est cochée pour le joueur 1
                jouer = 0;
            }
            else if(choix == 27)//si on choisit Echap
            {
                attron(COLOR_PAIR(1));
                mvaddstr(17, 0, "Fin de la partie...");
                attroff(COLOR_PAIR(1));

                continuer = 0;
                jouer = 0;
            }
        }

        jouer = 1;

        if(continuer)//on coche la case choisie
            morpion_cocherCase(grille);
            
        //on test si le joueur gagne
        if((grille[0] == 1 && grille[1] == 1 && grille[2] == 1) || (grille[3] == 1 && grille[4] == 1 && grille[5] == 1) || (grille[6] == 1 && grille[7] == 1 && grille[8] == 1) || (grille[0] == 1 && grille[3] == 1 && grille[6] == 1) || (grille[1] == 1 && grille[4] == 1 && grille[7] == 1) || (grille[2] == 1 && grille[5] == 1 && grille[8] == 1) || (grille[0] == 1 && grille[4] == 1 && grille[8] == 1) || (grille[2] == 1 && grille[4] == 1 && grille[6] == 1))
        {
            attron(COLOR_PAIR(4));
            mvaddstr(17, 0, "Vous avez gagné !");
            attroff(COLOR_PAIR(4));

            continuer = 0;
        }

        //S'il n'y a pas égalité, on lance l'IA
        if(continuer && !((grille[0] != 0 && grille[1] != 0 && grille[2] != 0 && grille[3] != 0 && grille[4] != 0 && grille[5] != 0 && grille[6] != 0 && grille[7] != 0 && grille[8] != 0)))
        {
            if(grille[0] == 0 && ((grille[1] == 2 && grille[2] == 2) || (grille[3] == 2 && grille[6] == 2) || (grille[4] == 2 && grille[8] == 2)))
                grille[0] = 2;
            else if(grille[1] == 0 && ((grille[0] == 2 && grille[2] == 2) || (grille[4] == 2 && grille[7] == 2)))
                grille[1] = 2;
            else if(grille[2] == 0 && ((grille[0] == 2 && grille[1] == 2) || (grille[5] == 2 && grille[8] == 2) || (grille[4] == 2 && grille[6] == 2)))
                grille[2] = 2;
            else if(grille[3] == 0 && ((grille[0] == 2 && grille[6] == 2) || (grille[4] == 2 && grille[5] == 2)))
                grille[3] = 2;
            else if(grille[4] == 0 && ((grille[0] == 2 && grille[8] == 2) || (grille[1] == 2 && grille[7] == 2) || (grille[2] == 2 && grille[6] == 2) || (grille[3] == 2 && grille[5] == 2)))
                grille[4] = 2;
            else if(grille[5] == 0 && ((grille[2] == 2 && grille[8] == 2) || (grille[3] == 2 && grille[4] == 2)))
                grille[5] = 2;
            else if(grille[6] == 0 && ((grille[7] == 2 && grille[8] == 2) || (grille[4] == 2 && grille[2] == 2) || (grille[3] == 2 && grille[0] == 2)))
                grille[6] = 2;
            else if(grille[7] == 0 && ((grille[4] == 2 && grille[1] == 2) || (grille[6] == 2 && grille[8] == 2)))
                grille[7] = 2;
            else if(grille[8] == 0 && ((grille[7] == 2 && grille[6] == 2) || (grille[2] == 2 && grille[5] == 2) || (grille[4] == 2 && grille[0] == 2)))
                grille[8] = 2;
            else if(grille[0] == 0 && ((grille[1] == 1 && grille[2] == 1) || (grille[3] == 1 && grille[6] == 1) || (grille[4] == 1 && grille[8] == 1)))
                grille[0] = 2;
            else if(grille[1] == 0 && ((grille[0] == 1 && grille[2] == 1) || (grille[4] == 1 && grille[7] == 1)))
                grille[1] = 2;
            else if(grille[2] == 0 && ((grille[0] == 1 && grille[1] == 1) || (grille[5] == 1 && grille[8] == 1) || (grille[4] == 1 && grille[6] == 1)))
                grille[2] = 2;
            else if(grille[3] == 0 && ((grille[0] == 1 && grille[6] == 1) || (grille[4] == 1 && grille[5] == 1)))
                grille[3] = 2;
            else if(grille[4] == 0 && ((grille[0] == 1 && grille[8] == 1) || (grille[1] == 1 && grille[7] == 1) || (grille[2] == 1 && grille[6] == 1) || (grille[3] == 1 && grille[5] == 1)))
                grille[4] = 2;
            else if(grille[5] == 0 && ((grille[2] == 1 && grille[8] == 1) || (grille[3] == 1 && grille[4] == 1)))
                grille[5] = 2;
            else if(grille[6] == 0 && ((grille[7] == 1 && grille[8] == 1) || (grille[4] == 1 && grille[2] == 1) || (grille[3] == 1 && grille[0] == 1)))
                grille[6] = 2;
            else if(grille[7] == 0 && ((grille[4] == 1 && grille[1] == 1) || (grille[6] == 1 && grille[8] == 1)))
                grille[7] = 2;
            else if(grille[8] == 0 && ((grille[7] == 1 && grille[6] == 1) || (grille[2] == 1 && grille[5] == 1) || (grille[4] == 1 && grille[0] == 1)))
                grille[8] = 2;
            else//si aucunes combinaisons est possible, l'IA choisie une case aléatoirement
            {
                while(boucle)
                {
                    if(grille[nbrA = (rand() % (max - min + 1)) + min] == 0)
                        boucle = 0;
                }

                grille[nbrA] = 2;
                boucle = 1;
            }

            morpion_cocherCase(grille);//on coche la case de l'IA
        }
        
        //on test si l'IA a gagnée ou s'il y a égalité
        if(continuer && ((grille[0] == 2 && grille[1] == 2 && grille[2] == 2) || (grille[3] == 2 && grille[4] == 2 && grille[5] == 2) || (grille[6] == 2 && grille[7] == 2 && grille[8] == 2) || (grille[0] == 2 && grille[3] == 2 && grille[6] == 2) || (grille[1] == 2 && grille[4] == 2 && grille[7] == 2) || (grille[2] == 2 && grille[5] == 2 && grille[8] == 2) || (grille[0] == 2 && grille[4] == 2 && grille[8] == 2) || (grille[2] == 2 && grille[4] == 2 && grille[6] == 2)))
        {
            attron(COLOR_PAIR(5));
            mvaddstr(17, 0, "L'ordinateur a gagné !");
            attroff(COLOR_PAIR(5));

            continuer = 0;
        }
        else if(continuer && (grille[0] != 0 && grille[1] != 0 && grille[2] != 0 && grille[3] != 0 && grille[4] != 0 && grille[5] != 0 && grille[6] != 0 && grille[7] != 0 && grille[8] != 0))
        {
            attron(COLOR_PAIR(7));
            mvaddstr(17, 0, "             ");
            mvaddstr(17, 0, "Egalité !");
            attroff(COLOR_PAIR(7));

            continuer = 0;
        }
    }

    refresh();
    
    getch();//fin du jeu

    endwin();
    
    return 0;
}

morpion.c

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <curses.h>
#include "morpion.h"

//cette fonction sert à initialiser l'affichage du titre et de la grille
void morpion_chargerGrille(void)
{
    int i = 0, j = 0;

    clear();

    attron(COLOR_PAIR(1));
    mvaddch(0, 2, B_D);
    mvaddch(0, 10, B_G);
    mvaddch(1, 2, H_B);
    mvaddch(1, 10, H_B);
    mvaddch(2, 2, H_D);
    mvaddch(2, 10, H_G);

    for(i = 0 ; i < strlen("Morpion") ; i++)
    {
        mvaddch(0, i + 3, G_D);
        mvaddch(2, i + 3, G_D);
    }

    mvaddstr(1, 3, "Morpion");
    attroff(COLOR_PAIR(1));

    attron(COLOR_PAIR(2));

    for(i = 3 ; i <= 15 ; i += 4)
    {
        for(j = 1 ; j <= 9 ; j += 4)
        {
            mvaddch(i, j, G_D);
            mvaddch(i, j + 1, G_D);
            mvaddch(i, j + 2, G_D);
        }
    }

    for(i = 4 ; i <= 12 ; i += 4)
    {
        for(j = 0 ; j <= 12 ; j += 4)
        {
            mvaddch(i, j, H_B);
            mvaddch(i + 1, j, H_B);
            mvaddch(i + 2, j, H_B);
        }
    }

    mvaddch(3, 0, B_D);
    mvaddch(3, 4, G_D_B);
    mvaddch(3, 8, G_D_B);
    mvaddch(3, 12, B_G);

    for(i = 7 ; i <= 11 ; i += 4)
    {
        mvaddch(i, 0, H_B_D);
        mvaddch(i, 4, H_B_G_D);
        mvaddch(i, 8, H_B_G_D);
        mvaddch(i, 12, H_B_G);
    }

    mvaddch(15, 0, H_D);
    mvaddch(15, 4, G_D_H);
    mvaddch(15, 8, G_D_H);
    mvaddch(15, 12, H_G);
    attroff(COLOR_PAIR(2));

    attron(COLOR_PAIR(6));
    mvaddch(12, 1, '1');
    mvaddch(12, 5, '2');
    mvaddch(12, 9, '3');
    mvaddch(8, 1, '4');
    mvaddch(8, 5, '5');
    mvaddch(8, 9, '6');
    mvaddch(4, 1, '7');
    mvaddch(4, 5, '8');
    mvaddch(4, 9, '9');
    attroff(COLOR_PAIR(6));

    refresh();
}

//cette fonction sert à cocher toute la grille en fonction du tableau grille[]
void morpion_cocherCase(int *grille)
{
    int i = 0, j = 0, k = 0;

    for(i = 13 ; i >= 5 ; i -= 4)
    {
        for(j = 2 ; j <= 10 ; j += 4)
        {
            if(grille[k] == 1)//si la case est au joueur 1
            {
                attron(COLOR_PAIR(4));
                mvaddch(i, j, 'X');
                attroff(COLOR_PAIR(4));
            }
            else if(grille[k] == 2)//si la case est à l'IA
            {
                attron(COLOR_PAIR(5));
                mvaddch(i, j, 'O');
                attroff(COLOR_PAIR(5));
            }

            k++;
        }
    }

    refresh();
}

morpion.h

#ifndef MORPION
#define MORPION

#define CLR_BLEU            9
#define CLR_VERT            10
#define CLR_CYAN            11
#define CLR_ROUGE           12
#define CLR_VIOLET          13
#define CLR_JAUNE           14
#define CLR_BLANC           15

#define G_D                 0x2500
#define H_B                 0x2502
#define B_D                 0x250C
#define B_G                 0x2510
#define H_D                 0x2514
#define H_G                 0x2518
#define H_B_D               0x251C
#define H_B_G               0x2524
#define G_D_B               0x252C
#define G_D_H               0x2534
#define H_B_G_D             0x253C
//ces defines permettent d'initialiser les couleurs et l'affichage de la grille

void morpion_chargerGrille(void);
void morpion_cocherCase(int *grille);

#endif

Pouet_forever

9 janvier 2011 à 0:41:03

J'ai beau faire tout mon possible, mais les fonctions de conio.h j'arrive pas à les remplacer. :-°

J'ai beau mettre getch de ncurses, ça fonctionne pas pour autant.

Je commenterai ton code sur la partie autre que ncurses, je ne connais pas. :-°

GurneyH

9 janvier 2011 à 1:01:31

pdcurses est le pendant portable de ncurses.

Très peu de différences à l'usage entre les 2 lib.

Citation : Pouet_Forever

J'ai beau faire tout mon possible, mais les fonctions de conio.h j'arrive pas à les remplacer.

Pourquoi parles-tu de conio? o_O

Zeste de Savoir, le site qui en a dans le citron !

Loadware

9 janvier 2011 à 1:12:06

@GurneyH : Pouet_forever parle de conio car j'utilise _getch(); dans mon morpion.

GurneyH

9 janvier 2011 à 1:16:38

tu utilises bien pdcurses?

Zeste de Savoir, le site qui en a dans le citron !

Loadware

9 janvier 2011 à 14:24:37

@GurneyH : Oui j'utilise PDCurses mais uniquement pour les fonctions d'affichages, la gestion des touches est réalisée avec conio.

GurneyH

9 janvier 2011 à 14:41:48

Citation : Loadware

@GurneyH : Oui j'utilise PDCurses mais uniquement pour les fonctions d'affichages, la gestion des touches est réalisée avec conio.

C'est dommage, pdcurses permet cette gestion.

Zeste de Savoir, le site qui en a dans le citron !

Loadware

9 janvier 2011 à 15:29:33

Je le sais mais ce code est en réalité imbriqué dans un projet beaucoup plus gros où la gestion des touches ne peut pas être partout réalisé à l'aide de pdcurses.

Edit : Après avoir bien cherché dans la doc de PDCurses j'ai réussi à me passer de conio pour la gestion des touches dans mon gros projet, donc j'ai édité mon code avec le morpion

crushing

9 janvier 2011 à 21:17:48

Voilà j'ai modifié mon code que j'ai poster dans la partie 1 suivant ce que m'a dis Pouet (je le remercie d'ailleurs) et ce que je savais faire.
J'ai fait mon IA à grand coups de if, c'est la première que je fais, c'est déjà pas si mal

#include <stdlib.h>
#include <stdio.h>
#include <time.h>

#if defined ( __APPLE__ )
# include <unistd.h>
#elif defined ( linux )
# include <unistd.h>
#else
# include <windows.h>
#endif

void textcolor(int couleurDuTexte,int couleurDeFond);
void afficher(int table[]);
int caseVide(int enter, int table[]);
int win(int tableau[]);
int ia(int table[], int coups);
void initTable(int table[]);

enum{VIDE = 0, CROIX = 1, ROND = 2};

void textcolor(int couleurDuTexte,int couleurDeFond) // fonction d'affichage de couleurs
{
#if defined ( __APPLE__ )
	// Je ne sais pas faire sous apple
	return;
#elif defined ( linux )
	if(couleurTexte==15)couleurTexte=37;
	else if(couleurTexte==2)couleurTexte=32;
	else couleurTexte=31;
	printf("\033[%sm",couleurTexte);
#else
	HANDLE H=GetStdHandle(STD_OUTPUT_HANDLE);
	SetConsoleTextAttribute(H,couleurDeFond*16+couleurDuTexte);
#endif
}

void afficher(int table[]) // Affiche la progression de la grille de morpion
{
	int i = 0, j = 0;
	for(i=0;i<3;i++)
	{
		for(j=0;j<3;j++)
		{
			if(table[i*3+j]==VIDE)
			{
				textcolor(15,0); // Blanc
				printf("%d ",i*3+j+1);
			}
			else if(table[i*3+j]==CROIX)
			{
				textcolor(2,0); // Vert
				printf("X ");
			}
			else if(table[i*3+j]==ROND)
			{
				textcolor(4,0); // Rouge
				printf("O ");
			}
		}
		printf("\n");
	}
	textcolor(15,0);
	printf("\n");
}

int caseVide(int enter, int table[]) // Test une case vide
{
	if((enter>=1&&enter<=9) && table[enter-1]==VIDE)
		return 1;
	else
		return 0;
}

int win(int tableau[]) // Test une victoire
{
    if ((tableau[0] == tableau[1] && tableau[0] == tableau[2] && tableau[2] != VIDE)||
            (tableau[3] == tableau[4] && tableau[3] == tableau[5] && tableau[5] != VIDE)||
            (tableau[6] == tableau[7] && tableau[6] == tableau[8] && tableau[8] != VIDE)||
            (tableau[0] == tableau[3] && tableau[0] == tableau[6] && tableau[6] != VIDE)||
            (tableau[1] == tableau[4] && tableau[1] == tableau[7] && tableau[7] != VIDE)||
            (tableau[2] == tableau[5] && tableau[2] == tableau[8] && tableau[8] != VIDE)||
            (tableau[0] == tableau[4] && tableau[0] == tableau[8] && tableau[8] != VIDE)||
            (tableau[2] == tableau[4] && tableau[2] == tableau[6] && tableau[6] != VIDE))
			return 1;
	return 0;
}

int ia(int table[], int coups) // L'IA
{
	int i;
	if(coups==8)
		for(i=0;i<9;i++)
			if(table[i]==VIDE)
				return i;
	if(coups==1&&table[4]==VIDE)return 4;
	else if(coups==1&&table[4]!=VIDE)return 0;

	// L'IA tente de gagner sur ce coups
		// Test lignes
	else if(table[6]==ROND&&table[7]==ROND&&table[8]==VIDE)return 8; // 3
	else if(table[6]==ROND&&table[8]==ROND&&table[7]==VIDE)return 7; // 3
	else if(table[7]==ROND&&table[8]==ROND&&table[6]==VIDE)return 6; // 3
	else if(table[3]==ROND&&table[4]==ROND&&table[5]==VIDE)return 5; // 2
	else if(table[3]==ROND&&table[5]==ROND&&table[4]==VIDE)return 4; // 2
	else if(table[4]==ROND&&table[5]==ROND&&table[3]==VIDE)return 3; // 2
	else if(table[0]==ROND&&table[1]==ROND&&table[2]==VIDE)return 2; // 1
	else if(table[0]==ROND&&table[2]==ROND&&table[1]==VIDE)return 1; // 1
	else if(table[1]==ROND&&table[2]==ROND&&table[0]==VIDE)return 0; // 1

		// Test colonnes
	else if(table[2]==ROND&&table[5]==ROND&&table[8]==VIDE)return 8; // 3
	else if(table[1]==ROND&&table[4]==ROND&&table[7]==VIDE)return 7; // 3
	else if(table[0]==ROND&&table[3]==ROND&&table[6]==VIDE)return 6; // 3
	else if(table[2]==ROND&&table[8]==ROND&&table[5]==VIDE)return 5; // 2
	else if(table[1]==ROND&&table[7]==ROND&&table[4]==VIDE)return 4; // 2
	else if(table[0]==ROND&&table[6]==ROND&&table[3]==VIDE)return 3; // 2
	else if(table[5]==ROND&&table[8]==ROND&&table[2]==VIDE)return 2; // 1
	else if(table[4]==ROND&&table[7]==ROND&&table[1]==VIDE)return 1; // 1
	else if(table[3]==ROND&&table[6]==ROND&&table[0]==VIDE)return 0; // 1

		// Test diagonales
	else if(table[0]==ROND&&table[4]==ROND&&table[8]==VIDE)return 8; // 3
	else if(table[2]==ROND&&table[4]==ROND&&table[6]==VIDE)return 6; // 3
	else if(table[0]==ROND&&table[8]==ROND&&table[4]==VIDE)return 4; // 2
	else if(table[2]==ROND&&table[6]==ROND&&table[4]==VIDE)return 4; // 2
	else if(table[4]==ROND&&table[6]==ROND&&table[2]==VIDE)return 2; // 2
	else if(table[4]==ROND&&table[8]==ROND&&table[0]==VIDE)return 0; // 2

	// L'IA regarde si le joueur peux gagner
		// Test lignes
	else if(table[6]==CROIX&&table[7]==CROIX&&table[8]==VIDE)return 8; // 3
	else if(table[6]==CROIX&&table[8]==CROIX&&table[7]==VIDE)return 7; // 3
	else if(table[7]==CROIX&&table[8]==CROIX&&table[6]==VIDE)return 6; // 3
	else if(table[3]==CROIX&&table[4]==CROIX&&table[5]==VIDE)return 5; // 2
	else if(table[3]==CROIX&&table[5]==CROIX&&table[4]==VIDE)return 4; // 2
	else if(table[4]==CROIX&&table[5]==CROIX&&table[3]==VIDE)return 3; // 2
	else if(table[0]==CROIX&&table[1]==CROIX&&table[2]==VIDE)return 2; // 1
	else if(table[0]==CROIX&&table[2]==CROIX&&table[1]==VIDE)return 1; // 1
	else if(table[1]==CROIX&&table[2]==CROIX&&table[0]==VIDE)return 0; // 1

		// Test colonnes
	else if(table[2]==CROIX&&table[5]==CROIX&&table[8]==VIDE)return 8; // 3
	else if(table[1]==CROIX&&table[4]==CROIX&&table[7]==VIDE)return 7; // 3
	else if(table[0]==CROIX&&table[3]==CROIX&&table[6]==VIDE)return 6; // 3
	else if(table[2]==CROIX&&table[8]==CROIX&&table[5]==VIDE)return 5; // 2
	else if(table[1]==CROIX&&table[7]==CROIX&&table[4]==VIDE)return 4; // 2
	else if(table[0]==CROIX&&table[6]==CROIX&&table[3]==VIDE)return 3; // 2
	else if(table[5]==CROIX&&table[8]==CROIX&&table[2]==VIDE)return 2; // 1
	else if(table[4]==CROIX&&table[7]==CROIX&&table[1]==VIDE)return 1; // 1
	else if(table[3]==CROIX&&table[6]==CROIX&&table[0]==VIDE)return 0; // 1

		// Test diagonales
	else if(table[0]==CROIX&&table[4]==CROIX&&table[8]==VIDE)return 8; // 3
	else if(table[2]==CROIX&&table[4]==CROIX&&table[6]==VIDE)return 6; // 3
	else if(table[0]==CROIX&&table[8]==CROIX&&table[4]==VIDE)return 4; // 2
	else if(table[2]==CROIX&&table[6]==CROIX&&table[4]==VIDE)return 4; // 2
	else if(table[4]==CROIX&&table[6]==CROIX&&table[2]==VIDE)return 2; // 2
	else if(table[4]==CROIX&&table[8]==CROIX&&table[0]==VIDE)return 0; // 2

	// L'IA joue autre part
	do
	{
		i = rand() % 8;
	}while(table[i]!=VIDE);
	return i;
}

void initTable(int table[]) // Initialise le tableau int[9]
{
	int i;
	for(i = 0;i < 9;i++)
		table[i] = VIDE;
}

void main(void)
{
	int table[9] = {0};
	int game = 1;
	int player = 1, numCase = 0, coups = 0,forIA = 0, play = 1, choix = 0;
	char caract = 'C';


	printf("---------------------------------------\n");
	printf("----------- By Crushing ---------------\n");
	printf("---------------------------------------\n\n");
	printf("Bienvenue dans le jeu du morpion !\n\n");
	printf("Les cases avec des '.' sont vide\nEntrez le numero de la case pour y mettre votre signe\nLes numeros sont :\n");
	afficher(table);

	while(caract!='Y'&&caract!='N') // 1 ou 2 joueurs
	{
		printf("\nVoulez-vous jouez a 1 joueur (Y/N) : ");
		caract = fgetc(stdin);
		caract = toupper(caract);
	}
	if(caract=='Y')forIA=1;
	caract = ' ';

	printf("\nLe joueur 1 commence\n");

	while(play)
	{
		initTable(table);
	while(game)
	{
		while(!choix)
		{
		if(player==1)
		{
			textcolor(2,0); // Vert 
			printf("Joueur 1");
			textcolor(15,0); // Blanc
			printf("veuillez entrer le numero de la case : ");
			textcolor(2,0); // Vert 
			scanf("%d", &numCase);
			textcolor(15,0); // Blanc
		}
		else
		{
			textcolor(4,0); // Rouge
			printf("Joueur 2");
			textcolor(15,0); // Blanc
			printf("veuillez entrer le numero de la case : ");
			textcolor(4,0); // Rouge
			if(forIA==1) // Si l'IA joue
			{
				numCase=ia(table,coups)+1;
				printf("%d\n",numCase);
			}
			else // Sinon un autre joueur joue
				scanf("%d", &numCase);
			textcolor(15,0); // Blanc
		}
		if(!caseVide(numCase, table))
			printf("Erreur dans la case entrer\n");
		else choix=1;
		}
			coups++;
			table[numCase-1]=player;
			afficher(table);
			if(win(table)) // Gagné ?
			{
				game=0;
				printf("\nLe joueur %d a gagner, bravo a lui !\n\n", player);
			}
			else if(coups==9) // Match nul ?
			{
				game=0;
				printf("Quel dommage ! Un match nul entre nos 2 joueurs !\n\n");
			}
			else // Sinon changement de joueur
			{
				if(player==1)player=2;
				else player=1;
				choix = 0;
			}
	}
	while(caract!='Y'&&caract!='N')
	{
		printf("Voulez-vous faire une autre partie ? (Y/N) : ");
		caract = fgetc(stdin);
		caract = toupper(caract);
	}
	if(caract=='Y')
		game = 1;
	else
		play = 0;
	}

	while(getchar() != '\n');

	return 0;
}

Pouet_forever

10 janvier 2011 à 22:32:17

Loadware >
Bon... j'arrive à compiler + lancer ton programme sans soucis, mais j'ai rien d'affiché dans ma console.

Tu pourrais créer plus de fonctions
J'ai pas pu tester ton IA, mais pour rendre ton code plus lisible, tu pourrais passer à la ligne après chaque parenthèses ou || qu'il y a après chaque parenthèse.

Défaut principal, ça manque cruellement de fonctions.

crushing >
Sous Apple, c'est les mêmes commandes que sous linux (à quelques commandes près).

Tu pourrais faire plus de fonctions

A vous 2 :
J'ai pas pu (ou voulu) tester vos codes, mais vous pouvez maintenant essayer de réfléchir à une IA plus intelligente.

L'algorithme min/max ! Par contre, limitez vous à un tableau de 3x3.

Si vous avez des questions, n'hésitez pas à poster ici, on est là pour vous répondre !

Merci de votre participation !

crushing

12 janvier 2011 à 17:50:56

Excuse-moi Pouet, mais je ne vois pas trop quelles genres de fonctions tu voudrais que je rajoute :euh:

.
Sinon merci pour apple, je vais corriger...

Loadware

12 janvier 2011 à 18:11:41

Citation : Pouet_forever

Défaut principal, ça manque cruellement de fonctions.

Je ne vois pas vraiment où en rajouter, le code me semble suffisamment simple comme ça.
Quand à coder une IA plus puissante, faut voir si je suis motivé

darkipod

12 janvier 2011 à 18:16:13

bonjour
pour l'IA la méthode min/max il s'agit bien de cela ?
si c'est ça j'ai pas le .u sorti des ronces! :-°

Loadware

12 janvier 2011 à 18:50:21

Il y a un tuto là dessus sur le SdZ

Pouet_forever

12 janvier 2011 à 19:25:53

Vous voulez que je vous fasse une explication sur le minimax ?
Si vous faites un min/max, limitez-vous à un plateau de 3x3. Après si vous avez réussi et que vous n'avez pas eu trop de problèmes, je vous aiguillerai sur d'autres algos.

Bah, pour les fonctions, ya moyen de faire de multiples fonctions. C'est surtout pour l'évolution du jeu, si vous voulez rajouter/enlever des choses, changer l'interface, etc. vous n'aurez qu'à changer la fonction.

darkipod

12 janvier 2011 à 20:41:28

Le tuto je l'avais repere sur le sdz
mais vu mon niveau et le temps que je peux y consacrer il y a un fosse
je réfléchis a un IA très basique........

Pouet_forever

15 janvier 2011 à 17:01:29

Comme ya pas grand monde, je vais essayer d'expliquer. :-°

L'algorithme min/max

Je vais passer tous les détails d'application de cet algo aux jeux (jeux à somme nulle, etc.) vous le trouverez sur le net.

Pour faire simple, le but de cet algorithme est de jouer toutes les positions possibles et de jouer la position qui a reçu le meilleur score. C'est-à-dire, la position qui avantage le plus l'ordinateur et qui désavantage le plus le joueur. Si l'ordinateur est en position de faiblesse (2 pions adverse alignés) on jouera ce coup.

Pourquoi min/max ?

Comme dit précédemment, le but de l'ordinateur est de jouer le coup qui a reçu le meilleur score, donc il va jouer le coup 'max'.
On va considérer que le joueur est très intelligent, et jouera toujours lui aussi le meilleur score (en son avantage bien sûr). Donc, par rapport à l'IA, il jouera le coup qui aura le score le moins bon, donc il va jouer le coup 'min'.

Exemple pour le coup 'max' :

Image utilisateur

Pour le coup 'min', c'est l'inverse. On simulera que c'est le joueur qui a joué (pareil, tous les coups possible) et on prendra le minimum (ce qui met l'ordinateur le plus en défaut). Dans l'exemple du dessus, pour un coup min, on aurait gardé le coup qui a eu le score -12.

Nous connaissons maintenant les 2 types de coup. Maintenant, ce qu'il faut c'est faire jouer alternativement IA et humain.
Pour ça on ferait 2 fonctions, une qui joue pour l'IA et qui prend le coup 'max' qui a le meilleur score et une fonction qui joue l'humain et qui prend le coup 'min' qui a le score le moins bon. Ces 2 fonctions s'appellent mutuellement (récursivement). Ce qui nous ferait :

Fonction MAX (IA qui joue) :

'max' en cours initialise au minimum (voire l'infini)

Pour toutes les cases jouable
  On joue le coup
    On appelle la fonction MIN pour que l'humain joue
    On regarde si ce que la fonction MIN a retourné est plus grand que le 'max' en cours
       Si c'est le cas, on garde le nouveau 'max'
  On supprime le coup  
Fin pour

On retourne le 'max' trouvé

Fonction MIN (humain qui joue) :

'min' en cours initialise au maxium (voire l'infini)

Pour toutes les cases jouable
  On joue le coup
    On appelle la fonction MAX pour que l'IA joue
    On regarde si ce que la fonction MAX a retourné est plus petit que le 'min' en cours
       Si c'est le cas, on garde le nouveau 'min'
  On supprime le coup  
Fin pour

On retourne le 'min' trouvé

Il manque quelque chose dans nos fonctions. Si vous avez remarqué, on joue toutes les cases possibles, mais on ne regarde jamais si quelqu'un a gagné ou match nul. Après avoir joué le coup, il faut regarder ça !
Par exemple, s'il y a match nul on retourne 0, si l'IA a gagné on retourne le maximum et si l'humain a gagné on retourne le minimum (ces nombres doivent être assez grand pour ne pas influencer la fonction d'évaluation présentée plus bas).

Jusque là, tout va bien, mais il serait pas mal de nous dire que c'est mieux de gagner en 3 coups que de gagner en 9...
Pour ça, on va simplement, au lieux de retourner minimum et maximum, retourner minimum+nombre_de_coups ou maximum-nombre_de_coups.`
Pourquoi min+nbr de coups et pas - ? -> Tout simplement, que si c'est l'humain qui gagne, on renvoie la valeur à un coup 'max' qui prendra le maxium. Donc minimum+nbr de coups sera supérieur à minimum.

C'est l'inverse pour le maximum.

(point de passage (checkpoint !) -> Vous pouvez vous arrêter là et faire tout ce qui est dit plus haut, une fois que ce sera fait, vous pourrez continuer. Rien d'obligatoire, mais je pense que c'est plus simple pour une première approche)

Jusque là, on explorait absolument tous les coups, ce qui rend votre IA absolument imbattable. :lol:

Pour donner une difficulté à l'IA, on va simplement 'couper' volontairement le nombre de coups joués. Par exemple, sur un morpion 3x3 on peut jouer maximum 9 coups. Pour donner de la difficulté (ou de la facilité, ça dépend dans quel sens vous vous mettez

), on stoppera la recherche à 3 coups par exemple (mode très simple, l'IA regarde uniquement le coup d'après). Pour 5 coups (mode simple) l'IA regardera 2 coups après. Pour 7 coups (difficile) l'IA regardera 7 coups. Et pour 9 coups (mode très difficile) l'IA regardera absolument tous les coups possibles.
On va appeler ça 'profondeur'.
On appelle nos fonctions 'min' et 'max' à chaque fois avec profondeur-1. Si la profondeur est égale à 0, on stoppe là et on évalue le plateau puis on retourne la valeur de l'évaluation.

Pour l'évaluation, il faut voir combien il y a de pions adverse alignés, combien de pions ami alignés histoire de dire 'c'est bien parti pour moi' ou 'je vais perdre, il faut que je joue là'.
Par exemple, pour évaluer une grille 3x3, on pourrais dire :

--> Pour toutes les lignes, toutes les colonnes et toutes les diagonales :
- S'il n'y a aucun pion sur le plateau, on ajoute 0
- S'il y a 1 pion IA, on ajoute 1
- S'il y a 1 pion humain, on ajoute -1
- S'il y a 2 pions IA, on ajoute 3
- S'il y a 2 pions humain, on ajoute -3
--> On retourne le score

Voilà, c'est à peu près tout pour le minimax.

J'ai volontairement laissé quelques flous, mais si vous voulez, je peux éclaircir ça.

Loadware

15 janvier 2011 à 17:24:38

Merci Pouet_forever pour ces précisions sur l'algo min-max mais quand je vois la quantité de code pour l'IA d'un morpion dans ce tuto, je me dis que mon IA à coup de if est bien plus courte pour un résultat équivalent au final.

GurneyH

15 janvier 2011 à 22:40:25

Citation : Loadware

Merci Pouet_forever pour ces précisions sur l'algo min-max mais quand je vois la quantité de code pour l'IA d'un morpion dans ce tuto, je me dis que mon IA à coup de if est bien plus courte pour un résultat équivalent au final.

Et tu as raison.
Sauf que, essayes d'étendre ta solution à une grille 4x4 ou +, tu vas rapidement comprendre...

L'algo min/max présenté par pouet est très limité, en revanche il donne les bases pour attaquer autre chose.
Après, il faut savoir ce qu'on veut! Perso, moi une IA à coup de if, ça ne me satisfait pas et j'assaye de faire mieux.
Mais, chacun son truc!

Zeste de Savoir, le site qui en a dans le citron !

darkipod

16 janvier 2011 à 13:42:30

Merci pour ton résume Pouet sur le sujet.
Cependant pour ma part le mettre en forme sur cet exo me parait complique.
Je bloque sur le fait par exemple comment fabriquer l 'arbre et qu'est que je mets comme valeur en bas de la pyramide?
Et la récursivité .............c'est pas non plus mon fort!
Pour que je puisse commencer mon algo peut tu me donner une piste?
Merci

Pouet_forever

16 janvier 2011 à 21:27:23

Loadware> Pour un morpion 3x3, ouais, qu'est-ce que tu feras pour un morpion 10x10 ? Je te dis pas le nombre de cas à gérer. :-°

Un jeu d'échecs ? un reversi ? et j'en passe, je pense que tes if sont largés. :-°

Le but de cet exo, c'est plus une introduction à l'IA.

darkipod >
En fait, l'arbre se fait de lui même.

Il suffit d'appeler au fur et à mesure tes fonctions min et max.

La valeur en bas de la pyramide, c'est l'évaluation de ton plateau, ce que j'ai montré plus haut. Pour la partie simple, on se limitera à dire :
Pour ça, on va simplement, au lieux de retourner minimum et maximum, retourner minimum+nombre_de_coups ou maximum-nombre_de_coups.

Je pense que j'ai visé un peu haut pour cet exo, le mois prochain on reviendra sur des choses plus simple... :-°

darkipod

20 janvier 2011 à 17:54:28

bonjour,
j'essaye de comprendre comment faire voici ou j'en suis

                                        
depart de la grille , etat vierge personne a joué                                        
1        2        3                        
4        5        6                        
7        8        9                        
                                        
joueur humain joue                                        
                                        
1        2        3                        
4        X        6                        
7        8        9                        
                                        
au tour de l'ordi : IA.                                         
on compte le nombre de case occupées :                                        
ici 1 case humain                                        score=-1
IA joue                                        
                                        
1        2        O                        
4        X        6                        
7        8        9                        
                                        
joueur humain joue                                        
                                        
1        2        O                        
4        X        6                        
7        8        X                        
                                        
au tour de l'ordi : IA.                                         
on compte le nombre de case occupées :                                        
ici 2 case humain et 1 case pour IA                                        score =-3+1=-2
IA joue il devrait la position 0                                        
                                        
O        2        O                        
4        X        6                        
7        8        X                        
                                        
joueur humain joue                                        
                                        
O        2        O                        
4        X        6                        
7        X        X                        
                                        
on compte le nombre de case occupées :                                        
ici 3 cases humain et 2 cases pour IA                                        score =?
IA joue  la position  2                                         
                                        
O        O        O                        
4        X        6                        
7        X        X                        
                                        
IA gagne car il a trois pions alignés                                        
                                        
Bon à partir de cela mes questions sont :                                        
au troisième tour score vaut combien ?                                        
par rapport à l'arbre que tu as donné, quels sont les valeurs que l'on a en bas de la pyramide ?

bref j ai pas compris grand chose, une piste pour que je puisse commencer
merci

Pouet_forever

20 janvier 2011 à 18:39:14

C'est pas vraiment ça.

Le but c'est de jouer tous les coups possibles, et dès que quelqu'un a gagné ou match nul on 'remonte' la valeur.

IA simule le coup
X..
...
...

Puis on simule que l'humain joue
XO.  X.O  X..  X..  X..  X..  X..  X..
...  ...  O..  .O.  ..O  ...  ...  ...
...  ...  ...  ...  ...  O..  .O.  ..O

A chaque simulation de jeu de l'humain, on simule que l'IA joue.
Pour la première simulation (celle de gauche juste au dessus) ça donnerai ça
XOX  XO.  XO.  XO.  XO.  XO.  XO.
...  X..  .X.  ..X  ...  ...  ... 
...  ...  ...  ...  X..  .X.  ..X

Etc. jusqu'à ce que la grille soit pleine ou que quelqu'un gagne.
Puis on renvoie la valeur.

Une fois qu'on a testé tous les coups valides, on joue coup qui a eu le
meilleur score.

GurneyH

21 janvier 2011 à 9:02:10

Histoire de participer.
Une IA basique, avec alpha-beta(negamax peut être testé aussi).
C'est totalement inefficace, l'ordinateur jour toujours de manière identique, mais bon...:D

#include <stdio.h>
#include <stdlib.h>
#include <time.h>


#define W           4           /* Largeur de la grille         */
#define H           4           /* Hauteur de la grille         */
#define N           3           /* Nombre de pions à aligner    */

#define DEPTH       9
#define INFINI      1000
typedef struct
{
    int grid[W * H];
    int crtPlayer;
    int count;
} Board;

/* I/O --------------------------------------------------------------------------------- */
void clear(void)
{
    int c;
    while((c = getchar()) != '\n' && c != EOF)
        ;
}



/* Une autre partie ? */
int IO_ask(void)
{
    char c;

    for(;;)
    {
        int ret;
        printf("Une autre partie (o/n) ? ");
        ret = scanf("%c", &c);
        clear();
        if(ret != 1)
            puts("Saisie invalide !");
        else
        {
            if( c == 'O' || c == 'o')
                return 0;
            else if(c == 'N' || c == 'n')
                return 1;
        }
    }
}


void IO_displayMsg(char const *msg)
{
    printf("%s", msg);
}



/* Retourne la case choisie par le joueur courant */
int IO_getChoice(Board *p)
{
    int row, col;

    /* On boucle tant qu'on a pas une saisie jugée valide */
    for(;;)
    {
        int ret;

        printf("Joueur %d (ligne colonne) -> ", p->crtPlayer);
        ret = scanf("%d %d", &row, &col);
        clear();
        if(ret != 2)
            puts("Saisie invalide !");
        else
        {
            if((unsigned)--row >= H || (unsigned)--col >= W)
                puts("Ligne ou colonne incorrecte");
            else if(p->grid[row * W + col])
                puts("Case occupée");
            else
                return row * W + col;
        }
    }
}



/* Affiche une ligne de - aux bonnes dimensions */
void separator(void)
{
    int i;
    for (i = 0; i < W; i++)
        printf(" -");
    puts("");
}



/* Affiche la grille */
void Grid_display(int *grid)
{
    int i, j;
    for(i = 0; i < H; i++)
    {
        separator();

        for(j = 0; j < W; j++)
        {
            printf("|");
            putchar(" OX"[grid[i * W + j]]);
        }
        puts("|");
    }
    separator();
}


/* IA ----------------------------------------------------------------------- */
/* Teste une direction en partant d'une cellule donnée */
int lower_check(int *grid, int cell, int ii, int ij)
{
    int i = cell / W;
    int j = cell % W;
    int count = 0;

    while((unsigned)i < H && (unsigned)j < W)
    {
        if(grid[i * W + j] == grid[cell])
        {
            count++;
            i += ii;
            j += ij;
        }
        else
            break;  /* On est tombé sur un pion adverse, on sort */
    }

    return count - 1;
}


/* Testes toutes les directions à partir d'une case donnée.
 * Retourne le gagnant s'il existe, 0 sinon.
 */
int check(Board *p, int cell)
{
    /* Directions */
    static int a_inc[4][2] = {{1, 0}, {0, 1}, {1, 1}, {1, -1}};
    int i;

    for(i = 0; i < 4; i++)
    {
        int ii = a_inc[i][0];   /* Direction sur l'axe H */
        int ij = a_inc[i][1];   /* Direction sur l'axe W */
        int count = 1;          /* On compte le pion qui vient d'être placé */

        count += lower_check(p->grid, cell, ii, ij);
        count += lower_check(p->grid, cell, -ii, -ij);

        /* Si on a aligné N pions la partie est terminée. */
        if(count >= N)
            return p->grid[cell];

    }
    return 0;
}





int IA_alphabeta(Board *b, int p, int *p_cell, int depth, int alpha, int beta)
{
    if(b->count == W * H)
        return 0;
    else
    {
        int tmpCell;
        int i;

        for(i = 0; i < W * H; i++)
        {
            if(!b->grid[i])
            {
                b->grid[i] = p;
                b->count++;
                if(check(b, i) == p)
                {
                    *p_cell = i;
                    alpha = 1;
                }
                else
                {
                    int score = -IA_alphabeta(b, 3 - p, &tmpCell, depth - 1, alpha, beta);
                    if(score >= alpha)
                    {
                        alpha = score;
                        *p_cell = i;
                    }
                }
                b->grid[i] = 0;
                b->count--;

                if(alpha >= beta || alpha == 1)
                    return alpha;
            }
        }
        return alpha;
    }
}


int IA_negamax(Board *b, int p, int *p_cell, int depth)
{
    if(b->count == W * H)
        return 0;
    else
    {
        int tmpCell;
        int bestScore = -INFINI;
        int i;

        for(i = 0; i < W * H; i++)
        {
            if(!b->grid[i])
            {
                b->grid[i] = p;
                b->count++;
                if(check(b, i) == p)
                {
                    *p_cell = i;
                    bestScore = 1;
                }
                else
                {
                    int score = -IA_negamax(b, 3 - p, &tmpCell, depth - 1);
                    if(score >= bestScore)
                    {
                        bestScore = score;
                        *p_cell = i;
                    }
                }
                b->grid[i] = 0;
                b->count--;
            }
        }
        return bestScore;
    }
}


int IA_getChoice(Board *board)
{
    int ret;

    /*IA_negamax(board, board->crtPlayer, &ret, DEPTH);*/
    IA_alphabeta(board, board->crtPlayer, &ret, DEPTH, -INFINI, INFINI);
    return ret;
}



/* JEU ---------------------------------------------------------------------- */


void initBoard(Board *p)
{
    int i;
    for(i = 0; i < W * H; i++)
        p->grid[i] = 0;

    p->crtPlayer = rand() % 2 + 1;
    p->count = 0;
}





/* Boucle principale */
void play(void)
{
    char buf[BUFSIZ];
    Board board;

    initBoard(&board);
    sprintf(buf, "Le joueur %d commence!\n", board.crtPlayer);
    IO_displayMsg(buf);
    while(board.count++ < W * H)
    {
        int cell;
        Grid_display(board.grid);
        if(board.crtPlayer == 1)
            cell = IO_getChoice(&board);
        else
            cell = IA_getChoice(&board);
        board.grid[cell] = board.crtPlayer;
        if (check(&board, cell))
            break;  /* Il y a un gagnant ! */

        board.crtPlayer = 3 - board.crtPlayer;
    }


    /* Fin de partie */
    Grid_display(board.grid);
    if(board.count < W * H)
        sprintf(buf, "Le joueur %d gagne !\n", board.crtPlayer);
    else
        sprintf(buf, "Match Nul !");
    IO_displayMsg(buf);
}

/* ---------------------------------------------------------------------------*/
int main(void)
{
    int done = 0;

    srand(time(NULL));
    do
    {
        play();
        done = IO_ask();
    }
    while(!done);

    return EXIT_SUCCESS;
}

Zeste de Savoir, le site qui en a dans le citron !

Pouet_forever

21 janvier 2011 à 19:08:15

Il doit te manquer un petit quelque chose quand même. L'IA c'est les X et il commence à jouer :

Joueur 1 (ligne colonne) -> 4 3
 - - - -
|X|X|O| |
 - - - -
|O|O|X| |
 - - - -
|X| | | |
 - - - -
| | |O| |
 - - - -
 - - - -
|X|X|O| |
 - - - -
|O|O|X| |
 - - - -
|X|X| | |
 - - - -
| | |O| |
 - - - -

Il aurait dû jouer le coup gagnant. :-°

Ton appel récursif alpha beta est faux aussi. En faisant comme ça, ta valeur beta ne changera jamais alors que tu changes constamment de noeud. Tu aurais dû appeler ta fonction comme ça (les 2 derniers paramètres) :

int score = -IA_alphabeta(b, 3 - p, &tmpCell, depth - 1, -beta, -alpha);

Dans ton if, tu testes le joueur courant et tu donnes une valeur fixe, mais le joueur courant peut être soit l'humain soit l'IA, donc il faudrait mettre une valeur différente si c'est l'IA qui gagne ou l'humain (pareil pour le negamax).

if(check(b, i) == p)
        {
          *p_cell = i;
          alpha = 1;
        }

</span></span>
Tu n'utilises pas ta profondeur, ça permettrait d'éviter des branches. :-°

Merci pour ta participation, je commençais à désespérer. :lol:

GurneyH

21 janvier 2011 à 20:08:14

Je vais revoir ma copie, alors.

edit:
et oui, j'ai bien inverser l'ordre de alpha et beta dans les paramètres. :honte:

edit2:
effectivement, je n'utilise pas depth.

J'ai certainement codé trop vite.

Zeste de Savoir, le site qui en a dans le citron !

Pouet_forever

30 janvier 2011 à 13:22:47

zMorp - 2ème partie - Correction

Le plus dur dans cet exercice était d'arriver à visualiser l'arbre. Une fois que vous avez réussi à visualiser l'arbre, rien de compliqué si vous connaissez la récursivité.

La solution donne le minimax, le négamax et l'alphabeta en négamax, vous avez juste la directive en début de fichier à changer :

#include <ctype.h>
#include <ctype.h>
#include <stdio.h>
#include <stdlib.h>
#include <time.h>

enum {
  TAB_H = 3,              /* Hauteur  */
  TAB_W = 3,              /* Largeur  */
  TAB_T = TAB_H * TAB_W,  /* Nbre total de cases      */
  NBR_P = 3               /* Nbre de pions à aligner  */
};

#define MINIMAX
/* #define NEGAMAX */
/* #define ALPHABETA */

enum {
  IA_DIFF = 99,           /* Profondeur -> difficulté de l'IA       */
  IA_MAX  = 10000,        /* Valeur maximale de l'IA                */
  IA_MID  = 0,            /* Valeur 'centrale' (match nul) de l'IA  */
  IA_MIN  = -IA_MAX,      /* Valeur minimale de l'IA                */
  INF     = IA_MAX * 2,   /* Valeur infinie de l'IA                 */
  NOE_MAX = 1,            /* Noeud 'max' de l'IA                    */
  NOE_MIN = 2             /* Noeud 'min' de l'IA                    */
};

enum {
  VIDE  = 0,
  J1    = 1,
  J2    = 2,
  JIA   = J1    /* Modifier cette variable pour le joueur IA */
};

typedef struct Coord_ {
  int x;
  int y;
} Coord;

void viderStdin(void) {
  int c;
  while ((c = getchar()) != '\n' && c != EOF)
    ;
}

int testerCoup(int * tab, Coord * c) {
  if (c->x < 0 || c->x >= TAB_W || c->y < 0 || c->y >= TAB_H ||
      tab[c->y * TAB_W + c->x] != VIDE)
    return 0;
  else
    return 1;
}

int jouerCoup(int * tab, Coord * c, int joueur) {
  tab[c->y * TAB_W + c->x] = joueur;
  return 0;
}

int delCoup(int * tab, Coord * c) {
  tab[c->y * TAB_W + c->x] = VIDE;
  return 0;
}

void affiche(int * tab) {
  char * s = ".XO";
  int i;
  
  for (i = 0; i < TAB_T; i++) {
    if (i && i % TAB_H == 0)
      puts("");
    putchar(s[tab[i]]);
  }
  puts("");
}

int compterDir(int * tab, Coord * c, int x, int y, int joueur) {
  int cnt, i, j;
  
  cnt = 0;
  i = c->x + x;
  j = c->y + y;
  while (i >= 0 && i < TAB_W && j >= 0 && j < TAB_H &&
         tab[j * TAB_W + i] == joueur) {
    cnt++;
    j += y;
    i += x;
  }
  
  return cnt;
}

int estCoupGagnant(int * tab, Coord * c, int joueur) {
  Coord dir[4] = {
    { 0, 1 }, { 1,  0 },
    { 1, 1 }, { 1, -1 }
  };
  int cnt, i;
  
  for (i = 0; i < 4; i++) {
    cnt =  compterDir(tab, c, dir[i].x,  dir[i].y,  joueur);
    cnt += compterDir(tab, c, -dir[i].x, -dir[i].y, joueur);
    if (cnt + 1 >= NBR_P)
      return 1;
  }
  
  return 0;
}

int estGagnant(int ret, int joueur, int pce) {
  if (ret)
    printf("Joueur %d gagne !\n", joueur);
  else if (pce >= TAB_T)
    printf("Match nul !\n");
  else
    return 0;
  return 1;
}

int alphaBeta(int * tab, Coord * c, int joueur, int pce,
              int prof, int alpha, int beta) {
  Coord ij;
  
  if (pce >= TAB_T)
    return IA_MID;
  
  for (ij.y = 0; ij.y < TAB_H; ij.y++) {
    for (ij.x = 0; ij.x < TAB_W; ij.x++) {
      if (testerCoup(tab, &ij)) {
        int tmp;
        
        jouerCoup(tab, &ij, joueur);
        
        if (estCoupGagnant(tab, &ij, joueur))
          tmp = (IA_MAX - (pce + 1));
        else
          tmp = -alphaBeta(tab, c, 3 - joueur, pce + 1, prof - 1,
                           -beta, -alpha);
        delCoup(tab, &ij);
        
        if (tmp >= beta)
          return beta;
        if (tmp > alpha) {
          if (prof == IA_DIFF)
            *c = ij;
          alpha = tmp;
        }
      }
    }
  }
  
  return alpha;
}


int negamax(int * tab, Coord * c, int joueur, int pce, int prof) {
  Coord ij;
  int best = -INF;
  
  if (pce >= TAB_T)
    return IA_MID;
  
  for (ij.y = 0; ij.y < TAB_H; ij.y++) {
    for (ij.x = 0; ij.x < TAB_W; ij.x++) {
      if (testerCoup(tab, &ij)) {
        int tmp;
        
        jouerCoup(tab, &ij, joueur);
        
        if (estCoupGagnant(tab, &ij, joueur))
          tmp = IA_MAX - (pce + 1);
        else
          tmp = -negamax(tab, c, 3 - joueur, pce + 1, prof - 1);
        delCoup(tab, &ij);
        
        if (tmp > best) {
          if (prof == IA_DIFF)
            *c = ij;
          best = tmp;
        }
      }
    }
  }
  
  return best;
}

int minimax(int * tab, Coord * c, int joueur, int pce, int prof, int noeud) {
  Coord ij;
  int best;
  
  /* Si la grille est vide, on renvoie 'match nul' */
  if (pce >= TAB_T)
    return IA_MID;
  
  /* Initialisation des variables en fonction du noeud */
  if (noeud == NOE_MAX)
    best = -INF;
  else
    best = INF;
  
  for (ij.y = 0; ij.y < TAB_H; ij.y++) {
    for (ij.x = 0; ij.x < TAB_W; ij.x++) {
      if (testerCoup(tab, &ij)) {
        int tmp;
        
        jouerCoup(tab, &ij, joueur);
        
        /* Noeud max */
        /* Pour un noeud max, on récupère le coup qui a eu le meilleur score */
        if (noeud == NOE_MAX) {
          /* Si on a gagné, pas besoin de continuer, on donne la valeur MAX  */
          if (estCoupGagnant(tab, &ij, joueur))
            tmp = IA_MAX - (pce + 1);
          /* Sinon, on appelle récursivement la fonction avec le noeud opposé */
          else
            tmp = minimax(tab, c, 3 - joueur, pce + 1, prof - 1, NOE_MIN);
          
          /* Si le coup à jouer est meilleur, on le garde */
          if (tmp > best) {
            /* Si on est au 1er coup, on le garde */
            if (prof == IA_DIFF)
              *c = ij;
            best = tmp;
          }
        }
        /* Noeud min */
        /* Même chose que le noeud max, mais on garde le coup minimum */
        else {
          if (estCoupGagnant(tab, &ij, joueur))
            tmp = IA_MIN + (pce + 1);
          else
            tmp = minimax(tab, c, 3 - joueur, pce + 1, prof - 1, NOE_MAX);
          
          if (tmp < best)
            best = tmp;
        }
        
        delCoup(tab, &ij);
      }
    }
  }
  
  return best;
}

int saisieIA(int * tab, Coord * c, int joueur, int pce) {
#ifdef MINIMAX
  minimax(tab, c, joueur, pce, IA_DIFF, NOE_MAX);
#elif defined NEGAMAX
  negamax(tab, c, joueur, pce, IA_DIFF);
#elif defined ALPHABETA
  alphaBeta(tab, c, joueur, pce, IA_DIFF, -INF, INF);
#endif
  return 0;
}

int saisieCoord(int * tab, Coord * c) {
  
  do {
    printf("Entrez les coordonees (x y) : ");
    scanf("%d%d", &c->x, &c->y);
    viderStdin();
    c->x--;
    c->y--;
  } while (!testerCoup(tab, c));
  
  return 0;
}

void jouer(int joueur) {
  int tab[TAB_T] = { 0 };
  int done, pce, ret;
  Coord c;
  
  printf("Joueur %d commence !\n\n", joueur);
  affiche(tab);
  
  pce = 0;
  done = 0;
  while (!done) {
    if (joueur == JIA) {
      printf("IA joue :\n");
      saisieIA(tab, &c, joueur, pce);
    }
    else {
      saisieCoord(tab, &c);
    }
    jouerCoup(tab, &c, joueur);
    pce++;
    ret = estCoupGagnant(tab, &c, joueur);
    done = estGagnant(ret, joueur, pce);
    affiche(tab);
    joueur = 3 - joueur;
  }
}

int rejouer(void) {
  int c;
  
  do {
    printf("Voulez-vous rejouer (o)ui/(n)on ? ");
    c = getchar();
    viderStdin();
    c = toupper(c);
  } while (c != 'N' && c != 'O');
  return c == 'O';
}

int init(void) {
  srand(time(NULL));
  return 0;
}

int main(void) {
  int joueur;
  init();
  
  joueur = rand() % 2 + 1;
  do {
    jouer(joueur);
    joueur = 3 - joueur;
  } while (rejouer());
  
  return EXIT_SUCCESS;
}

Je n'ai pas fait de fonction d'évaluation, on explore l'arbre en entier.

Edit: Rajout de commentaires.

1 2 >>

zMorp - 2ème partie

× Après avoir cliqué sur "Répondre" vous serez invité à vous connecter pour que votre message soit publié.

× Attention, ce sujet est très ancien. Le déterrer n'est pas forcément approprié. Nous te conseillons de créer un nouveau sujet pour poser ta question.

zMorp - 2ème partie

Créer une IA

zMorp - 2ème partie

main.c

morpion.c

morpion.h

L'algorithme min/max

zMorp - 2ème partie - Correction

zMorp - 2ème partie

Supprimer

Modérer

Signaler le message aux modérateurs