Rhooo, j'avais pas vu ce topic...
Je vais tenter tout de suite, j'avais vu le tuto (le titre seulement) sur le SDZ mais je savais pas que c'était un début d'IA
A tout à l'heure !
EDIT : Bon je galère
Voici comment je vois la chose :
Je lance ma fonction IAPlay(); Elle récupère les cellules vides, et pour toutes les cellules vides, lance la fonction IASimulation();
IASimulation(), pour toutes les cellules vides restantes, lance HumanSimulation(); puis vérifie si le coup à jouer est le max.
HumanSimulation(), pour toutes les cellules vides restantes, lance IASimulation(); puis vérifie si le coup à jouer est le min.
Ensuite, lorsque la profondeur est nulle, j'évalue la plateau, et retourne le meilleur coup à jouer
Ai-je compris le principe ? Parce que je me perds dans toutes ces petites fonctions d'IA
Oui, le principe c'est ça.
Par contre, te fait pas chier avec la fonction d'évaluation, va jusqu'au bout de ton arbre et renvoie les valeurs que si tu as gagné, l'IA a gagné ou match nul. C'est plus simple.
Voici ce que j'ai fait, je comprends pas vraiment comment tout cela fonctionne
int IAplay(int *board, int deepth){
int *emptyBoard = malloc(sizeof(int) * deepth),
i,
tmp,
tmpi,
best = -INF_MAX;
// Pour toutes les cellules vides
for(i = 0; i < deepth; i++){
getEmptyCells(board, emptyBoard);
tmp = IASimulation(board, deepth);
if(tmp > best){
best = tmp;
tmpi = emptyBoard[i];
}
}
free(emptyBoard);
return tmpi;
}
int IASimulation(int *board, int deepth){
if(deepth == 0)
return evalBoard(board);
int i,
tmp,
max = -INF_MAX;
for(i = 0; i < deepth; i++){
if(board[i] == EMPTY){
board[i] = P2;
tmp = HumanSimulation(board, (deepth - 1));
if(tmp > max){
max = tmp;
}
board[i] = EMPTY;
}
}
return max;
}
int HumanSimulation(int *board, int deepth){
if(deepth == 0)
return evalBoard(board);
int i,
tmp,
min = INF_MAX;
for(i = 0; i < deepth; i++){
if(board[i] == EMPTY){
board[i] = P1;
tmp = IASimulation(board, (deepth - 1));
if(tmp < min){
min = tmp;
}
board[i] = EMPTY;
}
}
return min;
}
int evalBoard(int *board){
int i,
pions = 0;
Coord c;
for(i = 0; i < CELL_X * CELL_Y; i++)
pions++;
for(i = 0; i < CELL_X * CELL_Y; i++){
c.x = i % CELL_X;
c.y = i / CELL_X;
if(hasWin(board, c, P1))
return INF_MAX - pions;
if(hasWin(board, c, P2))
return pions - INF_MAX;
}
return EMPTY;
}
J'ai fait des test avec printf et je ne rentre jamais dans la fonction evalBoard, ce qui me semble super pas logique étant donnée que je fais bien mes (deepth - 1)
Ce qui fait que tmp de la fonction IAPlay() vaut toujours 1000 ou -1000 et donc l'IA remplit la grille dans l'ordre croissant des choses... De plus, arrivé au milieu de la grille à peu près, tmpi n'est même pas réévalué donc vaut 132454534 ou 31651689 (enfin, l'ancienne valeur quoi ) et donc, SegFault
Un peu d'aide sur la conception, pas forcément une correction du code sera la bienvenue
Quel profondeur utilises-tu.
Pour un morpion 3x3, si tu met une profondeur > 9, c'est un peu normal, que tu n'atteignes pas 0.
Il faut lancer la fonction evalBoard si
-la profondeur a atteint 0 ou
-si la grille est remplie.
Pour un morpion, tu peux oublier la profondeur, je pense.
Par contre, tu dois à chaque appel tester si le coup est gagnant.
// Récupère les coordonnées de la cellule de l'IA
Coord getIACell(int *board, int nb){
// On copie le plateau
int _board[CELL_X * CELL_Y] = {0},
i;
Coord c;
copyBoard(board, _board);
// Maintenant, qu'on a copié notre tableau, il faut choisir le meilleur coup...
i = IAplay(_board, nb);
c.x = i % CELL_X;
c.y = i / CELL_X;
return c;
//return getRandomCell(board, nb);
}
currentCell = getIACell(board, turn--));
// Turn correspond au nombre de tour qu'il reste à jouer ou au nombre de case vide...
// Déclaration :
int turn = CELL_X * CELL_Y;
Bien entendu, turn diminue aussi lorsque le joueur joue
tu dois à chaque appel tester si le coup est gagnant.
A quoi te sert getEmptyCells ?
Par contre, le but de la profondeur c'est de limiter la recherche de l'arbre, là tu vas explorer tout ton arbre quoi qu'il arrive.
tu dois à chaque appel tester si le coup est gagnant.
A chaque appel de quoi ? IASimulation et HumanSimulation ?
Citation : Pouet_forever
A quoi te sert getEmptyCells ?
Par contre, le but de la profondeur c'est de limiter la recherche de l'arbre, là tu vas explorer tout ton arbre quoi qu'il arrive.
getEmptyCells me retourne la liste des cases vides, ainsi, cela m'évite de faire à chaque fois de faire tout le plateau depuis le début (même avec les cases remplies) mais j'ai du mal à l'utiliser correctement
Je crois (je dis bien je crois) que je viens de comprendre un truc. Il ne faudrait pas mieux que je fasse :
int IASimulation(int *board, int deepth, int *emptyCells){
if(deepth == 0)
return evalBoard(board);
int i,
tmp,
max = -INF_MAX;
for(i = 0; i < deepth; i++){
board[emptyCells[i]] = P2;
getEmptyCells(board, emptyCells);
tmp = HumanSimulation(board, (deepth - 1), emptyCells);
if(tmp > max){
max = tmp;
}
board[emptyCells[i]] = EMPTY;
}
return max;
}
Je vais tester, je vous dis de suite, j'éditerai
EDIT :
Bon, c'est déjà un début, je peux atteindre la fin du plateau (à savoir faire match null )
Voici le code :
#include "include.h"
int IAplay(int *board, int deepth){
int *emptyBoard = malloc(sizeof(int) * deepth),
i,
tmp,
tmpi,
best = -INF_MAX;
// Pour tous les coups restants
for(i = 0; i < deepth; i++){
// Initialisation du tableau des cellules vides
getEmptyCells(board, emptyBoard);
tmp = IASimulation(board, deepth, emptyBoard);
if(tmp > best){
best = tmp;
tmpi = emptyBoard[i];
}
}
free(emptyBoard);
return tmpi;
}
int IASimulation(int *board, int deepth, int *emptyCells){
if(deepth == 0)
return evalBoard(board);
int i,
tmp,
max = -INF_MAX;
for(i = 0; i < deepth; i++){
// On simule le coup pour la 1ere cellule vide trouvée
board[emptyCells[i]] = P2;
// Réinitialisation du tableau de cellules vides
getEmptyCells(board, emptyCells);
tmp = HumanSimulation(board, (deepth - 1), emptyCells);
if(tmp > max){
max = tmp;
}
// Et on la revide (Pour le prochain test complet)
board[emptyCells[i]] = EMPTY;
}
return max;
}
int HumanSimulation(int *board, int deepth, int *emptyCells){
if(deepth == 0)
return evalBoard(board);
int i,
tmp,
min = INF_MAX;
for(i = 0; i < deepth; i++){
// On simule le coup pour la 1ere cellule vide trouvée
board[emptyCells[i]] = P1;
// Réinitialisation du tableau de cellules vides
getEmptyCells(board, emptyCells);
tmp = IASimulation(board, (deepth - 1), emptyCells);
if(tmp < min){
min = tmp;
}
// Et on la revide (Pour le prochain test complet)
board[emptyCells[i]] = EMPTY;
}
return min;
}
int evalBoard(int *board){
int i,
pions = 0;
Coord c;
for(i = 0; i < CELL_X * CELL_Y; i++)
pions++;
for(i = 0; i < CELL_X * CELL_Y; i++){
c.x = i % CELL_X;
c.y = i / CELL_X;
if(hasWin(board, c, P1))
return INF_MAX - pions;
if(hasWin(board, c, P2))
return pions - INF_MAX;
}
return EMPTY;
}
Par contre, je ne vois pas du tout où appeler evalBoard
A chaque coup que tu fais, il faut que tu testes si le pion qui a été posé est gagnant.
Si le pion est gagnant, il faut que tu retournes le maximum ou le minimum en fonction du joueur qui joue.
Je pense que tu te fais trop chier avec ton getEmptyCells, essaye plutôt de parcourir ta grille normalement. Ou, si tu veux vraiment utiliser cette fonction, utilise une pile (ou une liste chaînée, mais plus lourd à gérer).
Merci pour vos conseils et votre temps mais là, je crois qu'il y a un sérieux problème...
Voici le code :
#include "include.h"
// On prend en considération que l'IA
// va toujours au bout de l'arbre
// Donc deepth = nombre de cases vides
// On verra l'amélioration ensuite
int IAplay(int *board, int deepth){
int i,
tmp,
tmpi,
best = -INF_MAX;
for(i =0; i < CELL_X * CELL_Y; i++){
printf("%d", board[i]);
if((i + 1) % CELL_X == 0)
printf("\n");
}
for(i =0; i < CELL_X * CELL_Y; i++){
printf("%d : ", i);
if(board[i] == EMPTY){
//printf("\n\nTour %d\n", i);
tmp = IASimulation(board, deepth);
printf("tmp = %d\n", tmp);
if(tmp > best){
tmp = best;
tmpi = i;
}
} else {
printf("board[%d] is not empty => %d\n", i, board[i]);
}
}
printf("La cellule à jouer est %d\n", tmpi);
return tmpi;
}
int IASimulation(int *board, int deepth){
if(deepth == 0)
return evalBoard(board, P2);
else {
int i = 0,
tmp,
winner,
max = -INF_MAX;
for(i = 0; i < CELL_X * CELL_Y; i++){
if(board[i] == EMPTY){
board[i] = P2;
if((winner = evalBoard(board, P2)) != EMPTY)
return winner;
tmp = HumanSimulation(board, (deepth - 1));
if(tmp > max){
max = tmp;
}
board[i] = EMPTY;
printf("board[%d] a été réinitialisé à %d\n", i, board[i]);
}
}
return max;
}
}
int HumanSimulation(int *board, int deepth){
if(deepth == 0)
return evalBoard(board, P1);
else {
int i,
tmp,
winner,
min = INF_MAX;
for(i = 0; i < CELL_X * CELL_Y; i++){
if(board[i] == EMPTY){
board[i] = P1;
if((winner = evalBoard(board, P1)) != 0 )
return winner;
tmp = IASimulation(board, (deepth - 1));
if(tmp < min){
min = tmp;
}
board[i] = EMPTY;
printf("board[%d] a été réinitialisé à %d\n", i, board[i]);
}
}
return min;
}
}
int evalBoard(int *board, int player){
int i,
pions = 0;
Coord c;
for(i = 0; i < CELL_X * CELL_Y; i++)
if(board[i] != EMPTY)
pions++;
for(i = 0; i < CELL_X * CELL_Y; i++)
if(board[i] != EMPTY){
c.x = i % CELL_X;
c.y = i / CELL_X;
if(hasWin(board, c, board[i])){
printf("hasWin returns %d pour %d(%d-%d)\n", board[i] == P1 ? INF_MAX - pions : -INF_MAX + pions, i, c.x, c.y);
return player == P1 ? INF_MAX - pions : pions - INF_MAX;
}
}
return EMPTY;
}
Et un résultat : (2 étant l'IA, 1 moi et 0 une cellule vide)
Citation : zMorp2
000
000
100
0 : board[8] a été réinitialisé à 0
board[7] a été réinitialisé à 0
hasWin returns -992 pour 0(0-0)
board[5] a été réinitialisé à 0
hasWin returns -992 pour 0(0-0)
board[4] a été réinitialisé à 0
hasWin returns -992 pour 2(2-0)
board[3] a été réinitialisé à 0
hasWin returns 992 pour 1(1-0)
board[2] a été réinitialisé à 0
hasWin returns 992 pour 1(1-0)
board[1] a été réinitialisé à 0
hasWin returns 992 pour 2(2-0)
board[0] a été réinitialisé à 0
hasWin returns 992 pour 2(2-0)
tmp = -992
1 : board[1] is not empty => 2
2 : board[2] is not empty => 1
3 : board[3] is not empty => 2
4 : board[4] is not empty => 1
5 : board[5] is not empty => 2
6 : board[6] is not empty => 1
7 : board[7] is not empty => 1
8 : board[8] is not empty => 2
La cellule à jouer est 0
201
000
100
0 : board[0] is not empty => 2
1 : hasWin returns -992 pour 1(1-0)
board[5] a été réinitialisé à 0
hasWin returns -992 pour 1(1-0)
board[4] a été réinitialisé à 0
hasWin returns 991 pour 2(2-0)
board[5] a été réinitialisé à 0
board[3] a été réinitialisé à 0
hasWin returns 992 pour 2(2-0)
board[1] a été réinitialisé à 0
hasWin returns 992 pour 2(2-0)
tmp = -992
2 : board[2] is not empty => 1
3 : board[3] is not empty => 2
4 : board[4] is not empty => 1
5 : board[5] is not empty => 1
6 : board[6] is not empty => 1
7 : board[7] is not empty => 2
8 : board[8] is not empty => 1
La cellule à jouer est 1
221
010
100
Je ne comprends pas pourquoi mon tableau board n'est pas réinitialisé correctement lorsqu'il faut passer au 2ème teste
EDIT : INF_MAX vaut 1000
Merci GurneyH, c'est déjà un début, mais cela ne fonctionne vraiment toujours pas...
Je vais tenter d'implémenter la correction de Pouet_forever et comprendre ce qui cloche car l'IA remplit la grille dans l'ordre croissant de i
Voici ma réponse, un petit peu longtemps après. J'étais pas mal débordé par différents projets, mais j'avais très envie de participer. Si vous pouvez commenter mon code, malgré la date, je vous en remercierai grandement!
game.h :
#ifndef GAME_H
#define GAME_H
#define W 3
#define H 3
void startGame(int isH[2]);
void playH(int turn, int grid[W][H]);
int playB(int turn, int grid[W][H]);
int IA(int player, int turn, int grid[W][H], int profondeur, int *L, int *C);
void printGrid(int grid[W][H]);
int hasWin(int grid[W][H], int turn);
int game(void);
#endif
game.c :
#include <stdio.h>
#include <stdlib.h>
#include "game.h"
#define IAMAX 2000
#define IAMIN -1000
#define IANUL 0
#define PROFMAX 10000
void startGame(int isH[2]){
do{
printf("Tappe 1 pour que le joueur 1 soit humain, 0 pour un ordinateur");
scanf("%d", &isH[0]);
}while((unsigned)isH[0] > 1);
do{
printf("Tappe 1 pour que le joueur 2 soit humain, 0 pour un ordinateur");
scanf("%d", &isH[1]);
}while((unsigned)isH[1] > 1);
}
int isEmpty(int box){
if(box == 0){
return 1;
}
else{
return 0;
}
}
void emptyCase(int *box){
*box = 0;
}
int isFull(int grid[W][H]){
int i, j;
for(i = 0; i < W; i++){
for(j = 0; j < H; j++){
if(isEmpty(grid[i][j])){
return 0;
}
}
}
return 1;
}
void playH(int turn, int grid[W][H]){
int i, j, ok = 0;
do{
printf("Rentre la ligne de la case\n");
scanf("%d", &i);
printf("Rentre la colonne de la case\n");
scanf("%d", &j);
if(grid[i][j] != 0 || (unsigned)j >= H || (unsigned)i >= W){
printf("Choix invalide\n");
}
else{
ok = 1;
grid[i][j] = turn + 1;
}
}while(!ok);
}
int playB(int turn, int grid[W][H]){
int i, j;
IA(turn, turn, grid, 100, &i, &j);
if(!isEmpty(grid[i][j])){
printf("Erreur d'algo\n");
return EXIT_FAILURE;
}
else{
grid[i][j] = turn + 1;
}
return 0;
}
int IA(int player, int turn, int grid[W][H], int profondeur, int *L, int *C){
int i, j, iM = 0, jM = 0;
int maxT, max = IAMIN;
int gridT[W][H];
int t1, t2;
if(profondeur == 0){
printf("On touche le fond\n");
return IANUL;
}
for(i = 0; i < W; i++){
for(j = 0; j < H; j++){
gridT[i][j] = grid[i][j];
}
}
for(i = 0; i < W; i++){
for(j = 0; j < H; j++){
if(isFull(gridT)){
return IANUL;
}
if(isEmpty(gridT[i][j])){
gridT[i][j] = turn + 1;
if(hasWin(gridT, player)){
return IAMAX + profondeur - PROFMAX;
}
if(hasWin(gridT, (player + 1)%2)){
return IAMIN + profondeur - PROFMAX;
}
maxT = IA(player, (turn + 1)%2, gridT, profondeur -1, &t1, &t2);
emptyCase(&gridT[i][j]);
if(max < maxT){
max = maxT;
iM = i;
jM = j;
}
}
}
}
*L = iM;
*C = jM;
return max;
}
void printGrid(int grid[W][H]){
int i, j;
for(i = 0; i < W; i++){
for(j = 0; j < H; j++){
printf("%c|", " ox"[grid[i][j]]);
}
printf("\n");
}
}
int hasWin(int grid[W][H], int turn){
int result, i, j;
result = 1;
for(i = 0; i < W; i++){
if(grid[i][i] != turn +1){
result = 0;
}
}
if(result) return 1;
result = 1;
for(i = 0; i < H; i++){
if(grid[H-1-i][i] != turn +1){
result = 0;
}
}
if(result) return 1;
for(i = 0; i < W; i++){
result = 1;
for(j = 0; j < H; j++){
if(grid[i][j] != turn +1){
result = 0;
}
}
if(result) return 1;
}
for(i = 0; i < W; i++){
result = 1;
for(j = 0; j < H; j++){
if(grid[j][i] != turn +1){
result = 0;
}
}
if(result) return 1;
}
return 0;
}
int game(void){
int isHuman[2], win = 0, cont = 1;
int turn = 0;
int grid[W][H] = {{0}};
startGame(isHuman);
while(cont){
if(isHuman[turn]){
playH(turn, grid);
}
else{
if(playB(turn, grid) == EXIT_FAILURE){
return EXIT_FAILURE;
}
}
printGrid(grid);
if(hasWin(grid, turn)){
cont = 0;
win = 1;
}
if(isFull(grid)){
cont = 0;
}
else{
turn += 1;
turn %= 2;
}
}
if(win){
printf("Victoire du jouer %d!", turn + 1);
}
else{
printf("Match nul!");
}
return 0;
}
J'ai essayé de séparer pas mal les fonctions. Je me sers d'assertions pour ne pas avoir à ajouter des variables en folie. Le programme n'est pas "secure", si il faudrait que je vide le buffer pour ça. Mais j'ai un peu la flemme, ce n'était pas mon but dans l'exercice.
Voici une trace d'exécution :
Tappe 1 pour que le joueur 1 soit humain, 0 pour un ordinateur0
Tappe 1 pour que le joueur 2 soit humain, 0 pour un ordinateur0
o| | |
| | |
| | |
o|x| |
| | |
| | |
o|x|o|
| | |
| | |
o|x|o|
x| | |
| | |
o|x|o|
x| |o|
| | |
o|x|o|
x| |o|
| |x|
o|x|o|
x|o|o|
| |x|
o|x|o|
x|o|o|
x| |x|
o|x|o|
x|o|o|
x|o|x|
Match nul!
Déjà, merci de ta participation.
Sans rentrer dans ton code, ya quelque chose qui ne va pas. Si tu joues une case dans le coin, la case à jouer juste après sera la case du milieu.
Tu as inversé les lignes et les colonnes dans ton programme (rien de bien méchant).
Dans ta fonction startGame tu pourrais utiliser une boucle.
Tu utilises souvent turn + 1, mais tu ne fais pas toujours de modulo, c'est voulu ? tu ne risques pas d'avoir une valeur que tu ne veux pas ?
Comme tu n'utilises pas ta profondeur, tu peux enlever ces lignes là :
if(profondeur == 0){
printf("On touche le fond\n");
return IANUL;
}
Pourquoi faire une copie de ton tableau ? Tu peux simplement travailler sur le même tableau.
Tu t'es trompé sur les valeurs que tu renvoies :
Tu renvoies les valeurs inverses de celles que tu devrais renvoyer (PROFMAX >> IAMAX > IAMIN).
Pour le premier cas, tu devrais renvoyer IAMAX-profondeur et dans le deuxième cas IAMIN+profondeur.
Je me suis pas trop attardé à commenter ton code, j'ai surtout regardé l'IA.
Je trouve ton code simple et propre, j'aime bien.
Encore une fois, merci de ta participation !
Bon courage. Je pense que pour faire fonctionner ton algo tu n'as que quelques modifications (mineures) à faire.
Tu utilises souvent turn + 1, mais tu ne fais pas toujours de modulo, c'est voulu ? tu ne risques pas d'avoir une valeur que tu ne veux pas ?
En fait, turn vaut soit 0, soit 1. Joueur 1 vaut 1, Joueur 2 vaut 2, vide vaut 0. Ainsi, turn + 1 indique le numéro (et donc la valeur dans la grille) du joueur. Donc +1%2 pour changer de tour, comme dans l'AI (j'en reparle plus tard), et +1 pour indiquer le joueur.
Citation : Pouet_forever
Comme tu n'utilises pas ta profondeur, tu peux enlever ces lignes là :
if(profondeur == 0){
printf("On touche le fond\n");
return IANUL;
}
Pourquoi faire une copie de ton tableau ? Tu peux simplement travailler sur le même tableau.
Pour la profondeur, je vais sûrement l'utiliser plus tard. Donc autant la laisser. Le "on touche le fond", c'est surtout de la vérification d'algo. Le tableau est une erreur de code. Je m'en suis rendu compte tôt, mais j'avais envie d'un algo fonctionnel, donc j'ai eu la flemme de modifier tout de suite.
Tu renvoies les valeurs inverses de celles que tu devrais renvoyer (PROFMAX >> IAMAX > IAMIN).
Pour le premier cas, tu devrais renvoyer IAMAX-profondeur et dans le deuxième cas IAMIN+profondeur.
En fait non, je ne me suis pas trompé.
int IA(int player, int turn, int grid[W][H], int profondeur, int *L, int *C){
Comme on le voit, il y a deux valeur : player et turn. Player permet de voir pour qui est l'algorithme. Ainsi, quand player+1 %2 indique l'autre joueur. C'est pour marquer l'alternance des coups dans la récursivité, en sachant à qui profite les coups. Player n'est jamais modifié, comme tu peux le voir à la ligne 119.
Après, j'ai quelques valeurs à modifier, pour obtenir un code plus fonctionnel au niveau du poids des coups. En fait, j'ai bien compris le système de poids (comment initialiser max, comment le modifier etc...) que récemment, du coup c'est encore du domaine de l'innovation ^^".
Citation : Pouet_forever
Je me suis pas trop attardé à commenter ton code, j'ai surtout regardé l'IA.
Je trouve ton code simple et propre, j'aime bien.
Encore une fois, merci de ta participation !
Bon courage. Je pense que pour faire fonctionner ton algo tu n'as que quelques modifications (mineures) à faire.
Et encore une fois de rien! C'est très agréable. Et merci pour les compliments, ça me touche beaucoup.
Une fois un algo stable, c'est parti pour la SDL =)
Ton histoire de 'turn' est un peu ambigu, tu pourrais faire une fonction histoire de bien montrer pourquoi tu fais ça.
J'ai vu que player n'était pas modifié, mais je maintiens que les valeurs que tu renvoies sont fausses. De plus, tu as oublié une partie de l'algo en fait, ton algo doit être un min/max et tu ne fais que le max : if(max<maxT)
C'est bien d'avoir fait la console avant, au moins tu ne te focalises pas sur l'affichage mais sur l'aglo.
Bon courage !
J'ai un changé complètement pour l'IA, histoire d'avoir un truc plus clair. Pour vérifier mes assertions entre turn et player, j'ai fait trois fonctions :
turn vaut soit 0, soit 1
player vaut soit 1, soit 2
changeTurn(turn -> turn), getPlayer(turn -> player), getOtherPlayer(player -> player).
Ces fonctions vérifient que les arguments sont bien des player ou des turns.
Ça permet d'enlever un peu de "magie" du code.
Sinon, j'ai fait une fonction IAmax, qui appelle une autre fonction IAmin, sur le concept du minmax. Très différente de l'ancienne, plus claire, plus intuitive.
J'utilise aussi un "doubleBreak", qui me permet de sortir d'une double boucle. De même, j'ai rajouté une struct coordonnées pour simplifier le code.
Il faut choisir la difficulté (entre 1 et l'infini : 0 fait planter). Je compte rajouter des unions histoire de permettre de faire des bots de différentes puissances. Mais pas tout de suite, là j'ai piscine
Voici le nouveau code :
game.c :
#include <stdio.h>
#include <stdlib.h>
#include "game.h"
#define IAMAX 100
#define IAMIN -100
#define IANUL 0
#define INF 1000000
#define DIFF 2
void startGame(int isH[2]){
do{
printf("Tappe 1 pour que le joueur 1 soit humain, 0 pour un ordinateur");
scanf("%d", &isH[0]);
}while((unsigned)isH[0] > 1);
do{
printf("Tappe 1 pour que le joueur 2 soit humain, 0 pour un ordinateur");
scanf("%d", &isH[1]);
}while((unsigned)isH[1] > 1);
}
int isEmpty(int box){
if(box == 0){
return 1;
}
else{
return 0;
}
}
void emptyCase(int *box){
*box = 0;
}
int getOtherPlayer(int player){
if(player <1 || player > 2){
printf("Bad use of getOtherPlayer : player = %d\n", player);
return EXIT_FAILURE;
}
else{
return player % 2 + 1;
}
}
int getPlayer(int turn){
if((unsigned) turn > 1){
printf("Bad use of getPlayer : turn = %d\n", turn);
return EXIT_FAILURE;
}
else{
return turn + 1;
}
}
int changeTurn(int turn){
return (turn + 1) %2;
}
int isFull(int grid[W][H]){
int i, j;
for(i = 0; i < W; i++){
for(j = 0; j < H; j++){
if(isEmpty(grid[i][j])){
return 0;
}
}
}
return 1;
}
void playH(int player, int grid[W][H]){
int i, j, ok = 0;
do{
printf("Rentre la ligne de la case\n");
scanf("%d", &i);
printf("Rentre la colonne de la ligne\n");
scanf("%d", &j);
if(!((unsigned) i < H && (unsigned) j < W && isEmpty(grid[i][j]))){
int c;
while((c = getchar()) != '\n' && c != EOF);
printf("Choix invalide\n");
}
else{
ok = 1;
grid[i][j] = player;
}
}while(!ok);
}
int playB(int turn, int grid[W][H], int diff){
coord ij;
IAmax(turn, grid, diff, &ij);
if(!isEmpty(grid[ij.x][ij.y])){
printf("Erreur d'algo\n");
return EXIT_FAILURE;
}
else{
grid[ij.x][ij.y] = getPlayer(turn);
}
return 0;
}
void chooseDiff(int *diff){
printf("Choose difficulty (1..Inf)");
scanf("%d", diff);
}
int IAmax(int turn, int grid[W][H], int deepth, coord *c){
int max = -INF, maxT;
int doubleBreak = 0;
coord ij, t;
if(deepth == 0){
return IANUL;
}
if(isFull(grid)){
return IANUL;
}
for(ij.x = 0; ij.x < W; ij.x++){
for(ij.y = 0; ij.y < H; ij.y++){
if(isEmpty(grid[ij.x][ij.y])){
grid[ij.x][ij.y] = getPlayer(turn);
if(isFull(grid)){
max = IANUL;
doubleBreak = 1;
}
if(hasWin(grid, getPlayer(turn))){
max = IAMAX + deepth;
doubleBreak = 1;
}
else{
maxT = IAmin(changeTurn(turn), grid, deepth - 1, &t);
if(maxT > max){
c->x = ij.x;
c->y = ij.y;
max = maxT;
}
}
emptyCase(&grid[ij.x][ij.y]);
}
if(doubleBreak){
c->x = ij.x;
c->y = ij.y;
break;
}
}
if(doubleBreak) break;
}
return max;
}
int IAmin(int turn, int grid[W][H], int deepth, coord *c){
int min = INF, minT;
int doubleBreak = 0;
coord ij, t;
if(deepth == 0){
return IANUL;
}
if(isFull(grid)){
return IANUL;
}
for(ij.x = 0; ij.x < W; ij.x++){
for(ij.y = 0; ij.y < H; ij.y++){
if(isEmpty(grid[ij.x][ij.y])){
grid[ij.x][ij.y] = getPlayer(turn);
if(isFull(grid)){
min = IANUL;
doubleBreak = 1;
}
if(hasWin(grid, getPlayer(turn))){
min =IAMIN - deepth;
doubleBreak = 1;
}
else{
minT = IAmax(changeTurn(turn), grid, deepth - 1, &t);
if(minT < min){
c->x = ij.x;
c->y = ij.y;
min = minT;
}
}
emptyCase(&grid[ij.x][ij.y]);
}
if(doubleBreak){
c->x = ij.x;
c->y = ij.y;
break;
}
}
if(doubleBreak) break;
}
return min;
}
void printGrid(int grid[W][H]){
int i, j;
for(i = 0; i < W; i++){
for(j = 0; j < H; j++){
printf("%c|", " ox"[grid[i][j]]);
}
printf("\n");
}
}
int hasWin(int grid[W][H], int player){
int result, i, j;
result = 1;
for(i = 0; i < W; i++){
if(grid[i][i] != player){
result = 0;
}
}
if(result) return 1;
result = 1;
for(i = 0; i < H; i++){
if(grid[H-1-i][i] != player){
result = 0;
}
}
if(result) return 1;
for(i = 0; i < W; i++){
result = 1;
for(j = 0; j < H; j++){
if(grid[i][j] != player){
result = 0;
}
}
if(result) return 1;
}
for(i = 0; i < W; i++){
result = 1;
for(j = 0; j < H; j++){
if(grid[j][i] != player){
result = 0;
}
}
if(result) return 1;
}
return 0;
}
int game(void){
int isHuman[2], win = 0, cont = 1;
int turn = 0, diff;
int grid[W][H] = {{0}};
startGame(isHuman);
chooseDiff(&diff);
while(cont){
printf("Au tour du joueur %d!\n", getPlayer(turn));
if(isHuman[turn]){
playH(getPlayer(turn), grid);
}
else{
if(playB(turn, grid, diff) == EXIT_FAILURE){
return EXIT_FAILURE;
}
}
printGrid(grid);
if(hasWin(grid, getPlayer(turn))){
cont = 0;
win = 1;
}
if(isFull(grid)){
cont = 0;
}
else{
turn = changeTurn(turn);
}
}
if(win){
printf("Victoire du joueur %d!", getPlayer(turn));
}
else{
printf("Match nul!");
}
return 0;
}
game.h :
#ifndef GAME_H
#define GAME_H
#define W 3
#define H 3
typedef struct coord{
int x;
int y;
}coord;
void startGame(int isH[2]);
int isEmpty(int box);
void emptyCase(int *box);
int getOtherPlayer(int player);
int getPlayer(int turn);
int changeTurn(int turn);
int isFull(int grid[W][H]);
void playH(int player, int grid[W][H]);
int playB(int turn, int grid[W][H], int diff);
void chooseDiff(int *diff);
int IAmax(int turn, int grid[W][H], int deepth, coord *c);
int IAmin(int turn, int grid[W][H], int deepth, coord *c);
void printGrid(int grid[W][H]);
int hasWin(int grid[W][H], int player);
int game(void);
#endif
J'ai fait quelques tests. En dessous de 3, l'IA est nulle. La 6 semble imbattable. Pourquoi pas une IA avec gestion du stress : pouvant rater des coups ^^".
Merci beaucoup d'animer cette section avec des exercices comme ça, c'est vraiment fun.
A première vue ça a l'air correct (je n'ai pas compilé le code).
Mais tu n'étais pas obligé de faire 2 fonctions, tu pouvais rester sur 1 seule fonction mais gérer les 2 cas dans cette même fonction.
Par contre, ta gestion de la profondeur n'est pas correcte, il faut que, dès que tu atteins profondeur==0, renvoyer une évaluation de ta grille, là tu gères ce cas comme un match nul.
Si tu veux, tu peux améliorer ton IA avec le négamax et l'alpha/beta, et pourquoi pas si tu veux, d'autres techniques que je n'ai pas présentées ici pour gérer une grille de taille supérieure à 3x3 et une IA pas trop longue.
En gros, la différence avec l'algo IAmax et IAmin, est que je calcule le coefficient "coefTurn" au dessus, qui indique si le joueur à qui est le tour est le joueur qui veut faire le maximum de points (si on se retrouve dans un noeud max ou noeud min).
Ensuite, j'applique ce coef à tous les return, sauf le dernier.
Le but du negamax est justement de supprimer ce coefficient.
Ce que tu as fait n'est pas un negamax.
Il faut que tes résultats soient symétriques par rapport à 0 (ce qui est le cas chez toi) et il faut que tu récupères l'inverse de ce que tu récupères (pas très clair là...). Ta fonction doit faire beaucoup moins de lignes.
× 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.
🍊 - Étudiant - Codeur en C | Zeste de Savoir apprenez avec une communauté | Articles - ♡ Copying is an act of love.