// Minimax.m // chess // // Created by Andrew Wang on 15/07/2013. // Copyright (c) 2013 Andrew Wang. All rights reserved. #import "Minimax.h" #import "ChessBoard.h" #import "Move.h" #import "Pos.h" #import "RuleBook.h" #define NUMBER_MOVES_AHEAD 3 // Constante qui définit sur combien de tours à venir l'algorithme fera ses simulations // De base cette constante est fixée à 3 @implementation Minimax //************************************************************************************************************* // Méthode de classe // La méthode est générique mais elle n'est réellement appelée que par l'IA pour trouver son meilleur coup // (nous, on se débrouille tout seuls ;-) pour l'instant...) +(Move *)BestMoveForSide:(Side)side board:(ChessBoard *)board { NSSet *movesPossibles = [self PossibleMovesForSide:side board:board]; if (movesPossibles.count == 0) [self NotifiePatMatDesSide:side onBoard:board]; else { int bestScore = -INFINITY; // version ORIGINALE, conforme au BestPseudoCode Move *bestMove = nil; // Pour chacun des coups possibles pour la couleur considérée... // NUMBER_MOVES_AHEAD étant fixé à 3, l'algo fera une simul sur les 3 prochains tours : d'abord pour // l'IA (ici dans BestMFSide), puis pour le Joueur et l'IA à nouveau (dans l'appel récursif de NegaMax) for (Move *moveEnCours in movesPossibles) { ChessBoard *newBoard = board.copy; // On travaille sur une copie du board courant [newBoard PerformMove:moveEnCours]; // On invoque negaMax par une autre racine negaMax faisant appel au negaMax proprement dit // avec la profondeur de recherche par défaut. int minMax = [self NegamaxForSide:side // la VO est +[self negamaxForSide, confirmée par BestPseudoCode board:newBoard depth:NUMBER_MOVES_AHEAD alpha:-INFINITY beta:INFINITY]; if (minMax > bestScore || !bestMove) { //NSLog(@"\nUn bon coup IA est %@ avec un minMax de %d",moveEnCours,minMax); bestScore = minMax; bestMove = moveEnCours; } // Fin de if } // Fin de for int eval = [self EvalBoardForSide:side board:board]; NSLog(@"\nLe 'bestMove' IA est %@ avec une 'eval' courante de %d, \net un 'bestScore' attendu de %d", [MCNmoveToStr Modif00EnA1:bestMove surBoard:board],eval,bestScore); return bestMove; } // Fin de else return 0; } //************************************************************************************************************* // Méthode de classe - Implémentation de l'algorithme 'Negamax' ('Minimax' compact) avec élagage alpha-bêta // L'appel initial à 'NegaMax' se fait dans 'BestMoveForSide' avec les param. par défaut. Les appels suivants se font // par récursivité dans le coeur de 'NegaMax' avec des param. adaptés à l'alternance IA/Joueur des coups examinés. +(int)NegamaxForSide:(Side)side board:(ChessBoard *)board depth:(int)depth // la méthode est appelée par bestMoveForSide, avec depth fixée à 3 (*) alpha:(int)alpha // alpha fixé à -INFINITY beta:(int)beta // bêta fixé à INFINITY { // depth <= 0 ? --> Test assurant la sortie de la boucle de l'appel récursif (cf. plus bas) if (depth <= 0) { int eval = [self EvalBoardForSide:side board:board] ; /* stringDebugging = [stringDebugging stringByAppendingString:[NSString stringWithFormat: @"%ld \t\tDEPTH= %d \tEVAL retourné à SCORE= %d \n", numDebugLine,depth, eval]]; numDebugLine = numDebugLine + 1; */ //return [self EvalBoardForSide:side board:board]; return eval; } // sinon on descend dans l'arbre des coups successifs par appel récursif else { int best = -INFINITY; // selon BestPseudoCode (la VO était +INFINITY) Side otherSide = (side == sideWhite) ? sideBlack : sideWhite; // Pour chaque coup possible de chacun des 3 tours à venir ==> for (Move *moveEnCours in [self PossibleMovesForSide:otherSide board:board]) { ChessBoard *newBoard = board.copy; [newBoard PerformMove:moveEnCours]; // ==> on simule son exécution, pour évaluer chaque board résultant // Appel récursif permettant de poursuivre la simul pour les tours de profondeur (depth) 2 et 1 int score = -[self NegamaxForSide:otherSide // couleur permutée à chaque appel board:newBoard depth:depth - 1 // 'depth' passe de 3 (*) à 2, à 1, puis à 0 alpha:-beta // alpha et bêta sont croisés à chaque nouvel appel car ce beta:-alpha]; // qui est Max pour l'IA matche avec ce qui est Min pour le Joueur // LA SUITE N'EST EXÉCUTÉE QUE QUAND SCORE EST ÉVALUÉ (càd qd 'depth'=0) CE QUI NOUS FAIT SORTIR DE NEGAMAX if (score > best) { best = score; // dans Négamax on cherche tjs la valeur Max (pas d'alternance comme en minimax) if (best > alpha) { alpha = best; // on referme la fenêtre de [-INFINITY ; +INFINITY] à [best ; +INFINITY] if (alpha >= beta) { // les bornes de la fenêtre se croisent --> ÉLAGAGE !! /* stringDebugging = [stringDebugging stringByAppendingString:[NSString stringWithFormat: @"%ld \t\tDEPTH= %d \tAprès élagage BEST retourné à SCORE= %d \tALPHA= %d \tBÊTA= %d\n", numDebugLine,depth, best, alpha, beta]]; numDebugLine = numDebugLine + 1; */ return best;} } // Fin de if best } // Fin de if score } // Fin de for chaque move possible /* stringDebugging = [stringDebugging stringByAppendingString:[NSString stringWithFormat: @"%ld \t\tDEPTH= %d \tBEST retourné à SCORE= %d \tALPHA= %d \tBÊTA= %d\n", numDebugLine,depth, best, alpha, beta]]; numDebugLine = numDebugLine + 1; */ return best; // Ligne ORIGINALE conforme au BEST PSEUDO CODE NEGAMAX } // Fin de else (profondeur non atteinte) } // Fin de méthode //************************************************************************************************************* // Méthode de classe // ex méthode 'scoreForSide' renommée pour une meilleure compréhension du but de la méthode // et pour éviter la confusion entre la variable 'score' de 'negamax' +(int)EvalBoardForSide:(Side)side board:(ChessBoard *)board { int evalBoard = 0; evalBoardAffichee = 0; // On balaye chaque case de l'échiquier considéré, et donner une valeur globale totalisant la valeur de // chacune des pièces encore présentes. La note accordée à un échiquier ne tient donc compte que de la // présence ou non des pièces de chacun des cotés, et en aucun cas des positions stratégiques et des // menaces potentielles... Même si ça parait un peu décevant, c'est une éval basique recevable. // A noter que la valeur relative des pièces est celle communément attribuée par la sphère échiquéenne for (int x = 0; x < 8; x++) // balayage des abcisses { for (int y = 0; y < 8; y++) // balayage des ordonnées { Piece *piece = [board piece_colX:x rangY:y]; if (piece) { int value = 0; switch (piece.type) { case Piece_Invalide: break; // si pas de pièce, pas de valeur ajoutée case Piece_Pion: value = 100; break; // s'il y a un Pion : +100 case Piece_Cavalier: value = 300; break; // +300 pour un Cavalier case Piece_Fou: value = 300; break; // +300 pour un Fou case Piece_Tour: value = 500; break; // +500 pour une Tour case Piece_Dame: value = 900; break; // +900 pour la Dame case Piece_Roi: value = 100000; break; // REVOIR INTÉRET D'INTÉGRER LE ROI AU CALCUL !? } // Si la pièce est de la couleur visée par l'appel de la méthode, alors la valeur s'ajoute, // sinon elle est déduite evalBoard += value * ((piece.side == side) ? 1 : -1); // eval ORIGINALE evalBoardAffichee += value * ((piece.side == sideWhite) ? 1 : -1); // eval pour affichage // Le mode de calcul d'evalBoard inverse le signe du résultat global selon la couleur en cours, // ce qui est cohérent avec la nécessité d'inverser cette valeur, imposée par l'algo Négamax // quand c'est aux Noirs de jouer... // TODO - VÉRIFIER QUE LE SIGNE PORTÉ PAR L'ÉVALUATION INFLUENCE CORRECTEMENT L'IA DANS // SON CHOIX DU MEILLEUR COUP POUR ELLE, QUELLE QUE SOIT LA COULEUR QU'ELLE JOUE } } } // Mise à jour du 'lblEvalBoard' de l'interface if (evalBoardAffichee > 0) monMCNControleur.lblEvalBoard.cell.title = [NSString stringWithFormat:@"+%d", evalBoardAffichee]; else monMCNControleur.lblEvalBoard.cell.title = [NSString stringWithFormat:@"%d", evalBoardAffichee]; return evalBoard; // Ligne ORIGINALE } // Fin de Méthode 'EvalBoardForSide' //************************************************************************************************************* // Méthode de classe 'PossibleMoveForSide' // Détermine tous les 'moves' possibles d'un 'side', à partir de l'ensemble des positions possibles de toutes // les pièces de cette couleur présentes sur le 'board' // MCN - AJOUT D'UNE VÉRIFICATION SYSTÉMATIQUE SI POSITION D'ÉCHEC GÉNÉRÉE AVANT VALIDATION ET AJOUT D'UN MOVE +(NSSet *)PossibleMovesForSide:(Side)side board:(ChessBoard *)board { NSMutableSet *moves = [[NSMutableSet alloc] init]; //Pos *posRoiSide; for (int x = 0; x < 8; x++) { for (int y = 0; y < 8; y++) { Pos *pos = [Pos posWithX:x y:y]; Piece *piece = [board piece_colX:x rangY:y]; if (piece) { if (piece.side == side) { NSSet *PosAcceptees = [RuleBook PosAccepteesForPiece:piece atPos:pos inBoard:board]; for (Pos *possibleDest in PosAcceptees) { Move *move = [[Move alloc] initWithStart:pos dest:possibleDest]; // Il faut réaliser le move (dans une copie du board) pour pouvoir contrôler l'absence de pos d'échec ChessBoard *newBoard = board.copy; [newBoard PerformMove:move]; /* Test désactivé car repris désormais dans 'PosAccepteesForPiece' // MCN - VÉRIFICATION SI UNE POSITION D'ÉCHEC EST GÉNÉRÉE PAR LE MOVE ---------------------------- if (![self TestEchecRoiSide:side inBoard:newBoard]) { [moves addObject:move]; // LE MOVE EST VALIDÉ ET AJOUTÉ SI PAS DE POS D'ÉCHEC GÉNÉRÉE } // --------------------------------------------------------------------------------------------- */ [moves addObject:move]; // Retour de lka ligne d'origine } // fin de for } // fin de if piece.side } // fin de if piece } // fin de for y } // fin de for x return moves; } // Fin de 'PossibleMoveForSide' AVEC CONTROLE SYSTÉMATIQUE DE POSITION D'ÉCHEC //************************************************************************************************************* // MCN - Méthode de Classe (inspirée de 'PossibleMoveForSide') // Détection des positions d'Échec et d'Échec et Mat en faveur du coté 'Side' // La méthode vise à déterminer tous les 'move' possibles coté 'side' d'un 'board' et à examiner si à chaque // destination de chacun de ces 'move' on trouve le Roi adverse, auquel cas cela signifie qu'il est en échec. // De par sa lourdeur comparée à sa version lite 'TestEchecRoiSide', cette méthode est à réserver aux besoins // d'affichage de la chaine de description complète de l'échec car ici on recherche les pos d'échec multiples // et le mat potentiel et on gère les messages d'alerte correspondant // TODO - Voir cependant s'il n'y a pas de dégraissage de code à faire +(NSString *)TestEchecFavSide:(Side)side board:(ChessBoard *)board { NSString *strEchec = @""; checkCount = 0; Side otherSide = (side == sideWhite)? sideBlack:sideWhite; // On s'arrête sur chaque case du 'board' courant, on regarde si on y trouve une pièce, et si cette pièce // est de couleur 'side'... Si oui, pour chacune de ses destinations possibles... for (int x = 0; x < 8; x++) { for (int y = 0; y < 8; y++) { Pos *pos = [Pos posWithX:x y:y]; Piece *piece = [board piece_colX:x rangY:y]; if (piece) { if (piece.side == side) { NSSet *PosAcceptees = [RuleBook PosAccepteesForPiece:piece atPos:pos inBoard:board]; for (Pos *possibleDest in PosAcceptees) { Move *moveSide = [[Move alloc] initWithStart:pos dest:possibleDest]; // DÉTECTION MISE EN ÉCHEC ...on regarde si sur chacune de ces cases destination il y a une // pièce de la couleur opposée dont le type est Roi... Si oui, il y a Echec Piece *pieceAdv = [board piece_colX:moveSide.dest.x rangY:moveSide.dest.y]; if (pieceAdv.type == Piece_Roi) { if (pieceAdv.side == otherSide) { strEchec = @"Echec"; checkCount = checkCount + 1; // incrémentation de checkCount NSLog(@"\ncheckCount = %d",checkCount); } // fin if } // fin if } // fin for } // fin if } // fin if } // fin for } // Sortie du for /* Il est nécessaire de parcourir la boucle de détection d'ÉCHEC ci-avant jusqu'au bout sans en sortir à la première détection, ceci afin de pouvoir comptabiliser les échecs multiples. On peut ensuite afficher une boite de dialogue signifiant l'ÉCHEC quand il est effectivement avéré. */ if ( [strEchec isEqual:@"Echec"] ) // On continue uniquement si le Roi est effectivement en échec { // Boite de dialogue NSString *msgTitre; NSString *msgInfo; if (sideCourant == sideWhite) { msgTitre = @"Le Roi NOIR est en position d'Échec !"; msgInfo = @"Confirmez pour poursuivre la partie..."; } else { msgTitre = @"Le Roi BLANC est en position d'Échec !"; msgInfo = @"Confirmez pour poursuivre la partie..."; } NSAlert *alertEchec = [[NSAlert alloc] init]; [alertEchec addButtonWithTitle:@"OK"]; [alertEchec setMessageText:msgTitre]; [alertEchec setInformativeText:msgInfo]; [alertEchec setAlertStyle:NSAlertStyleInformational]; // Récupération du choix fait par le joueur NSModalResponse boutonChoisi = [alertEchec runModal]; if (boutonChoisi == NSAlertFirstButtonReturn) { return strEchec; // Echec confirmé, on peut sortir de la boucle } } // fin if return strEchec; } // fin méthode TestEchecFavSide // ************************************************************************************************************* // MCN - Méthode de Classe // Version "lite" de 'TestEchecFavSide' (renvoyant une chaine décrivant la situation vis-à-vis de l'échec) // visant quant à elle à répondre RAPIDEMENT à la question de savoir si le Roi est en échec, en se moquant d'être // capable de dire si l'échec est simple ou double et si le mat est confirmé... // NOTER que la question posée, et donc la réponse apportée, par les deux méthodes en question sont inverses // Cette méthode est adaptée (c'est sa raison d'être) pour valider ou non un MovePossible.... // Elle n'est appelée que dans 'PossibleMoveForSide' et dans 'NotifiePatMatDesSide' +(BOOL)TestEchecRoiSide:(Side)side inBoard:(ChessBoard *)board { BOOL sideEstEnEchec = NO; //NSMutableSet *movesSideAdv = [[NSMutableSet alloc] init]; Side otherSide = (side == sideWhite)? sideBlack:sideWhite; // On parcourt chaque case du 'board' courant, à la recherche des pièces adverses (càd 'otherSide) // et pour chacune d'elle on vérifie chacune de ses destinations possibles>> for (int x = 0; x < 8; x++) { for (int y = 0; y < 8; y++) { Pos *pos = [Pos posWithX:x y:y]; Piece *pieceAdv = [board piece_colX:x rangY:y]; if (pieceAdv) { if (pieceAdv.side == otherSide) { NSSet *PosAcceptees = [RuleBook PosAccepteesForPiece:pieceAdv atPos:pos inBoard:board]; for (Pos *possibleDest in PosAcceptees) { Move *moveSideAdv = [[Move alloc] initWithStart:pos dest:possibleDest]; //[movesSideAdv addObject:moveSideAdv]; // DÉTECTION MISE EN ÉCHEC >>et sur chacune de ces cases destinations on regarde si on trouve // notre Roi, auquel cas nous sommes en situation d'Échec :-( Piece *piece = [board piece_colX:moveSideAdv.dest.x rangY:moveSideAdv.dest.y]; if (piece.type == Piece_Roi) { if (piece.side == side) { sideEstEnEchec = YES; //NSLog(@"\nLes %@ SONT Échec",(side==1)?@"Noirs":@"Blancs"); return sideEstEnEchec; } // fin if } // fin if //else {sideEstEnEchec = NO; NSLog(@"\nLes %@ NE SONT PAS Échec",(side==1)?@"Noirs":@"Blancs");} } // fin for } // fin if } } // fin for } // Sortie du for return sideEstEnEchec; } // Fin de Méthode 'TestEchecRoiSide' //*************************************************************************************************** // MCN - Méthode de gestion du Pat et du Mat - CETTE MÉTHODE NE DOIT ÊTRE APPELÉE QU'APRÈS QU'UN TEST // SUR 'PossibleMovesForSide' AIT RÉVÉLÉ QUE LE JEU DE MOVES EST VIDE, CAR C'EST BIEN CE TEST QUI // CARACTÉRISE UNE SITUATION DE MAT OU DE PAT, LA PRÉSENTE MÉTHODE NE FAIT QUE LA TRAITER... +(void)NotifiePatMatDesSide:(Side)side onBoard:(ChessBoard*)board { // MAT - Par définition, si on est ici c'est que 'side' n'a plus de move possible... // ...et si en plus 'side' est Échec sur le board actuel, c'est que 'side' est Mat if ([self TestEchecRoiSide:side inBoard:board]) { // Traitement des chaines : liste des coups et messages NSString *msgTitre; NSString *msgInfo; // Suppression des caractères vides en fin de chaine 'stringCoupsPartie' tant qu'il y en a while ([stringCoupsPartie characterAtIndex:(stringCoupsPartie.length-1)] == ' ') { // range : à partir du char à l'indice 0 et sur une longueur de len-1 pour supp le dernier char stringCoupsPartie = [stringCoupsPartie substringWithRange:NSMakeRange(0,stringCoupsPartie.length-1)]; } // Suppression des caractères '+' en fin de chaine tant qu'il y en a while ([stringCoupsPartie characterAtIndex:(stringCoupsPartie.length-1)] == '+') { stringCoupsPartie = [stringCoupsPartie substringWithRange:NSMakeRange(0,stringCoupsPartie.length-1)]; } // Boite de dialogue if (side == sideBlack) { msgTitre = @"Les NOIRS sont Mat !"; msgInfo = @"Partie terminée, Les BLANCS gagnent !"; // Mise à jour de la liste des coups et du contrôle 'txtView' // on ajoute un '#' pour signifier mat, puis 1-0 pour "les Blancs gagnent" stringCoupsPartie = [stringCoupsPartie stringByAppendingString:@"#\n\t1-0"]; [monMCNControleur MaJtxtCoups]; } else if (side == sideWhite) { msgTitre = @"Les BLANCS sont Mat !"; msgInfo = @"Partie terminée, Les NOIRS gagnent !"; // Mise à jour de la liste des coups et du contrôle 'txtView' // on ajoute un '#' pour signifier mat, puis 0-1 pour "les Noirs gagnent" stringCoupsPartie = [stringCoupsPartie stringByAppendingString:@"#\n\t0-1"]; [monMCNControleur MaJtxtCoups]; } // Affichage de la boite de dialogue NSAlert *alertMat = [[NSAlert alloc] init]; [alertMat addButtonWithTitle:@"OK"]; [alertMat setMessageText:msgTitre]; [alertMat setInformativeText:msgInfo]; [alertMat setAlertStyle:NSAlertStyleInformational]; // Attente 'OK' par le joueur NSModalResponse boutonChoisi = [alertMat runModal]; if (boutonChoisi == NSAlertFirstButtonReturn) { stopMatOuPat = true; } } // fin if de niv 1 // PAT - Mais si au contraire il n'y a pas situation d'échec, c'est que 'side' est simplement Pat else { // Si pas de move possible mais pas de situation d'Échec alors 'Pat' // Mise à jour de la liste des coups et du contrôle 'textView' stringCoupsPartie = [stringCoupsPartie stringByAppendingString:@"\n\t1/2-1/2"]; [monMCNControleur MaJtxtCoups]; NSString *msgTitre; NSString *msgInfo; if (side == sideBlack) { msgTitre = @"Les NOIRS sont Pat !"; msgInfo = @"Le Roi Noir est Pat, la partie est déclarée nulle !"; } else if (side == sideWhite) { msgTitre = @"Les BLANCS sont Pat !"; msgInfo = @"Le Roi Blanc est Pat, la partie est déclarée nulle !"; } // Affichage boite de dialogue NSAlert *alertPat = [[NSAlert alloc] init]; [alertPat addButtonWithTitle:@"OK"]; [alertPat setMessageText:msgTitre]; [alertPat setInformativeText:msgInfo]; [alertPat setAlertStyle:NSAlertStyleInformational]; // Récupération du choix fait par le joueur NSModalResponse boutonChoisi = [alertPat runModal]; if (boutonChoisi == NSAlertFirstButtonReturn) { stopMatOuPat = true; } } // fin else de niv 1 } // Fin de Méthode 'NotifiePatMatDesSide' @end