Algo Negamax

Programming Topics (Computer Chess) and technical aspects as test techniques, book building, program tuning etc

Moderator: Andres Valverde

Algo Negamax

Postby MortyMars » 05 Jun 2022, 17:55

Hello everyone :D ,

This is my first post on the forum, from France...
I took over a project of a chess game with AI (like negamax) in Objective C for macOS.
I'm at a version I'm quite satisfied with (at my humble level of coder), with a number of nice features implemented.
However, since the beginning of the project, I've been struggling with a poor AI engine in terms of move quality (and response time, but that's not the point), because despite my poor level I always win against the computer and that's obviously not normal ;-)
I obviously scoured the net for the best negamax algorithms and did a lot of different tests on my code, without any convincing performance improvement.
I am convinced that my problem comes from a bad adequacy between the Negamax method itself, the implementation of its call, and the evaluation method which participates for much to make the good choices.
For the most curious, I attach my code below (sorry for the comments in French...)
Negamax method :
Code: Select all
   //*************************************************************************************************************
   // 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
                  alpha:(int)alpha
                   beta:(int)beta   {
     
      Side otherSide = (side == sideWhite) ? sideBlack : sideWhite;
     
      /* Test assurant la sortie de la boucle de l'appel récursif (cf. plus bas)
      Si on a atteint la profondeur définie ou si le camp adv est Mat ou Pat, alors on sort */
      if (depth <= 0 || [self PossibleMovesForSide:otherSide board:board].count == 0)
      {
         int eval = [self EvalBoardForSide:side board:board] ;
         /*NSLog(@"\n\t\t\t NegaFS : Depth= %d (NB_MOVE_AHEAD= %d) - Coup %@= ?? - Old éval= ?? New éval= %d",
                              depth, NUMBER_MOVES_AHEAD, (otherSide == 1)? @"Noirs":@"Blancs",eval); */
         return eval;
         //return (side == sideBlack)? eval:-eval; // TEST !?
      }
     
      // sinon on descend dans l'arbre des coups successifs par appel récursif
      else
      {
         // nbLoop ++; NSLog(@"\n Coups examinés    = %d",nbLoop);
         //int best = -INT_MAX;
         // 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 PUIS 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 >= alpha) {
               /*NSLog(@"\n\t\t\t NegaFS : Depth= %d (NB_MOVE_AHEAD= %d) - Coup %@= %@ - Old éval= %d - New éval= %d ",
                                    depth, NUMBER_MOVES_AHEAD, (otherSide == 1)? @"Noirs":@"Blancs",moveEnCours,alpha,score); */
               
               alpha = score;           // dans Négamax on cherche toujours la valeur Max (pas comme en minimax)
               
               /* si les bornes de la fenêtre se croisent --> ÉLAGAGE BETA !! */
               if (alpha >= beta) {
                  nbElag ++; //NSLog(@"\n\t\t\t NegaFS : Branches élaguées = %d", nbElag);
                  break;
               }
               
            } // Fin de if score
         } // Fin de for chaque move possible
         
         //NSLog(@"\n\t\t NegaFS : Meilleure évaluation retournée par Negamax = %d",alpha);
         return alpha;
         
      } /* Fin de else (profondeur non atteinte) */
   } /* Fin de méthode 'NegamaxFS' */


Calling via a Best Shot Research Method:
Code: Select all
   //***************************************************************************************************
   // 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, le joueur -lui- se débrouille tout seul, pour l'instant ...
   +(Move *)BestMoveForSide:(Side)side
                      board:(ChessBoard *)board
   {
      /* Détermination du jeu de tous les moves possibles pour 'side' */
      NSSet *movesPossibles = [self PossibleMovesForSide:side board:board];
      /* PRÉREQUIS : TESTER SI SIDE EST MAT OU PAT À CE STADE, CAR SI LE CAS PAS LA PEINE D'ALLER PLUS LOIN... */
      if (movesPossibles.count == 0) [self NotifiePatMatDesSide:side onBoard:board];
      /* Sinon on poursuit en cherchant le meilleur move possible pour 'side'... */
      else
      {
         int bestScore  = -INT_MAX;
         Move *bestMove = nil;
         Side otherSide = (side == sideWhite)? sideBlack:sideWhite;
         /* Pour chacun des coups possibles pour la couleur considérée...
         Si par exemple NUMBER_MOVES_AHEAD est 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];
               
               /* TEST AJOUTÉ CAR SI LE MOVE MET L'ADV. MAT ALORS C'EST LE BEST MOVE QU'IL NOUS FAUT !
               (À ce stade on ne se contente pas d'un Pat, que l'on ne recherche jamais pour l'adversaire,
               il faut donc vérifier les 2 conditions : d'impossibilité de 'move' et de mise en échec)
               TODO : Le if initial a été scindé en 2 pour réduire le nbre de tests et donc de méthodes
               appelées, MAIS VOIR LAQUELLE DES 2 (PossibleMoveFS ou TestEchecRoiSide) EST LA MOINS LOURDE
               AFIN DE LA METTRE EN TETE DE TEST */
               if ([self PossibleMovesForSide:otherSide  board:newBoard].count == 0) {
                  if ([self TestEchecRoiSide:otherSide inBoard:newBoard]) {
                        bestMove = moveEnCours;
                        return bestMove;
                  }
               } // FIN DE TEST AJOUTÉ
               
               /* Appel initial à 'NegaMaxFS' avec les paramètres par défaut : pour 'side', dans une copie du board
               (car les moves sont virtuels), à la profondeur de recherche max, et avec la fenêtre alpha bêta max */
               int negaMax = +[self NegamaxForSide:side
                                             board:newBoard
                                             depth:NUMBER_MOVES_AHEAD
                                             alpha:-INT_MAX
                                              beta:INT_MAX];
               if (negaMax > bestScore || !bestMove) {
                  bestScore = negaMax;
                  bestMove = moveEnCours;
                  NSLog(@"\n\t BMFS : Un meilleur choix intermédiaire est trouvé pour les %@ : Score = %d et Move = %@",
                        (side == 1)? @"Noirs" : @"Blancs", bestScore, bestMove);
               } // Fin de if
            } // Fin de for
         
         /* NSLog de contrôle, potentiellement désactivable */
         NSLog(@"\n BMFS : Choix définitif validé pour les %@ : Score attendu = %d et Move retenu = %@",
               (side == 1)? @"Noirs" : @"Blancs", bestScore, bestMove);
         return bestMove;
      } // Fin de else
     
      //return 0;
      return Nil; // Valeur de retour à laquelle on n'accède jamais, mais plus raccord avec un type Move attendu
   } /* Fin de Méthode 'BestMoveForSide */


Method of evaluation of a board :
Code: Select all
   //*************************************************************************************************************
   // Méthode de classe MCN
   // 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 evalBoardRetournee = 0;
      evalBoard = 0;
     
      /* ÉVALUATION MATÉRIELLE - On balaye chaque case de l'échiquier considéré, pour obtenir une valeur globale
      totalisant la valeur de chacune des pièces encore présentes. À noter que la valeur relative des pièces
      (au Roi près) 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 Invalide:                  break;   // si pas de pièce, pas de valeur ajoutée
                  case Pion:    value = 100;      break;   // s'il y a un Pion : +100
                  case Cava:    value = 300;      break;   // +300 pour un Cavalier
                  case Fou:     value = 300;      break;   // +300 pour un Fou
                  case Tour:    value = 500;      break;   // +500 pour une Tour
                  case Dame:    value = 900;      break;   // +900 pour la Dame
                  case Roi:     value = 100000;   break;   // +100 000 pour le Roi !!!!
                  /* Bien que le Roi ne puisse être capturé -ce qu'ignorent complètement la présente méthode
                  d'évaluation, le moteur de l'IA, ainsi que la méthode gérant le déplacement des pièces- il est
                  important de lui accorder une forte valeur afin d'inciter l'IA à choisir, par appat du gain,
                  un coup qui permettrait de le capturer si c'était effectivement possible... */
               }
               
               /* Si la pièce est Blanche sa valeur s'ajoute au total, sinon elle est déduite
               (par conv. une éval pos indique un avantage aux Blancs et une éval nég un avantage aux Noirs) */
               evalBoard  += value * ((piece.side == sideWhite)? 1 : -1);   // INCRÉMENT VALEUR AFFICHÉE
               
            } /* Fin de if piece*/
         } /* Fin de for y */
      } /* fin de for x */
     
      /* PRISE EN COMPTE DE LA MISE EN ÉCHEC ET MAT
      NB : La prise en compte de la mise en échec, implémentée un temps dans l'éval, a été abandonnée car
      elle perturbait le choix du coup quand il s'opposait à une prise potentielle de pièce, pour un bénéfice
      (la mise en échec) qui n'est finalement que temporaire sans garantir un avantage stratégique futur */
      //Side otherSide = (side == sideWhite)? sideBlack:sideWhite;
     
      if ([self TestEchecRoiSide:sideBlack inBoard:board]) {
         if ([self PossibleMovesForSide:sideBlack board:board].count == 0) {
            evalBoard += +100000; /* Valeur positive car situation favorisant les Blancs */
         }
      }
      else if ([self TestEchecRoiSide:sideWhite inBoard:board]) {
         if ([self PossibleMovesForSide:sideWhite board:board].count == 0) {      // IA est Mat
            evalBoard += -100000; /* Valeur négative car situation favorisant les Noirs */
         }
      }
      /* FIN DE PRISE EN COMPTE DE LA MISE EN ÉCHEC ET MAT  */
     
      /* PRISE EN CPTE DES PIONS EN AVANT-DERNIÈRE RANGÉE : +900 ACCORDÉS COMME S'ILS ÉTAIENT DÉJÀ PROMUS DAMES
      Échiquier orienté avec les Blancs en bas */
      if (sideJoueur == sideWhite) {
         for (int x = 0; x < 8; x ++) {
            Piece *pionB = board->pieceCase[x][6];  // Pion Blanc en rangée 6
            if ((pionB.type == Pion) && (pionB.side == sideWhite)) {
               evalBoard += 900; /* Valeur positive car situation favorisant les Blancs */
            }
            Piece *pionN = board->pieceCase[x][1];  // Pion Noir en rangée 1
            if ((pionN.type == Pion) && (pionN.side == sideBlack)) {
               evalBoard += -900; /* Valeur négative car situation favorisant les Noirs */
            }
         }
      }
      /* Échiquier orienté avec les Noirs en bas */
      if (sideJoueur == sideBlack) {
         for (int x = 0; x < 8; x ++) {
            Piece *pionB = board->pieceCase[x][1];  // Pion Blanc en rangée 1
            if ((pionB.type == Pion) && (pionB.side == sideWhite)){
               evalBoard += 900 ; /* Valeur positive car situation favorisant les Blancs */
            }
            Piece *pionN = board->pieceCase[x][6];  // Pion Noir en rangée 6
            if ((pionN.type == Pion) && (pionN.side == sideBlack)){
               evalBoard += -900; /* Valeur négative car situation favorisant les Noirs */
            }
         }
      }
      /* FIN DE PRISE EN COMPTE DES PIONS ARRIVÉS SUR LEUR AVANT DERNIÈRE RANGÉE */

      /* Mise en forme du 'lblEvalBoard' de l'interface, avec un '+' ajouté aux valeurs positives */
      if (evalBoard > 0)
            monMCNControleur.lblEvalBoard.cell.title = [NSString stringWithFormat:@"Éval : +%d", evalBoard];
      else  monMCNControleur.lblEvalBoard.cell.title = [NSString stringWithFormat:@"Éval : %d",  evalBoard];
     
     
      /* Ultime traitement pour satisfaire le principe d'inverser l'évaluation quand c'est aux Noirs de jouer,
      imposé par le fonctionnement de l'algorithme Negamax */
      //if (side == sideWhite) evalBoard = -evalBoard;
      if (sideIA == sideWhite) evalBoard = evalBoard;
      else if (sideIA == sideBlack) evalBoard = -evalBoard;
      return evalBoard;
     
   } /* Fin de Méthode 'EvalBoardForSide' */


Unless of course there are obvious and gross errors, I'm not asking for my code to be corrected because of the time it could take.
But I would be interested in your similar experience ideally in Objective C of course, or in another language that I could transpose to my case (C, C++,...), the important thing being mainly that I can examine a functional code as a whole (Negamax, call, and evaluation method)
Thank you in advance for the leads you could give me.
Thank you in advance for any suggestions you may have. Sincerely.
MortyMars
 
Posts: 7
Joined: 05 Jun 2022, 17:06
Location: Fleury / France

Re: Algo Negamax

Postby H.G.Muller » 07 Jun 2022, 16:17

That it is objective C is a bigger problem than the French. :wink:

But a glance at your code gives me the impression that you don't have a Quiescence Search: as soon as d <= 0 you return eval. Even when the opponent of the side on move has a hanging Queen. This is enough to explain very poor play: the AI's goal will become to grab the most valuable piece in the last move of its allotted depth, usually with the Queen (because that is the most mobile, and can reach pieces other pieces cannot), while the intended victim is usually protected (but the recapture is too deep to see). And it will be willing or even eager to make sacrifices of less valuable pieces along the way, because taking these will keep the opponent busy.

It is essential that you consider some captures at d<=0. At the very least the capture of the piece that just moved.
User avatar
H.G.Muller
 
Posts: 3389
Joined: 16 Nov 2005, 12:02
Location: Diemen, NL

Re: Algo Negamax

Postby MortyMars » 08 Jun 2022, 00:45

Thanks H.G. for your feedback :)

Concerning Objective C I'm often told, but I'm stubborn about this language which I find elegant ;)

More seriously, it's true that I don't particularly bother with the case where depth=0, but I was just following (with probably too much confidence) what most pseudo code for this kind of algorithm proposes.
I must admit that this is the first time I've heard of quiescence search...
I'll try to see how to integrate it into my code and I'll come back for news
Sincerely
MortyMars
 
Posts: 7
Joined: 05 Jun 2022, 17:06
Location: Fleury / France

Re: Algo Negamax

Postby H.G.Muller » 08 Jun 2022, 09:19

The easiest way to do this would be not to make the evaluation and the searching of moves an if-then-else (based on d<=0), but leave the evaluation in the if-then, and search through the moves unconditionally. You would only return the evaluation score if it is above beta, and otherwise increase alpha to the evaluation score (if it is not already higher), before continuing with the loop over moves.

In that move loop you should then (when d<=0) ignore all moves that do not capture something. (In fact you could already ignore them if they do not capture enough to raise the evaluation above alpha.) Or you could be even more restrictive, and ignore all moves that do not go to the destination square of the previous ply.

Beware, though, that the order in which moves are searched is very important in the alpha-beta algorithm. In particular searching all captures in QS just in any order can easily lead to 'search explosion'. The way to prevent that is to search the capture of the most-valuable opponent piece first.
User avatar
H.G.Muller
 
Posts: 3389
Joined: 16 Nov 2005, 12:02
Location: Diemen, NL

Re: Algo Negamax

Postby MortyMars » 08 Jun 2022, 19:44

Hello H.G.

Without wishing to be abusive or to take the easy way out, what could it give in terms of code?
What do I have to change in my Negamax?
Thanks
Sincerely
MortyMars
 
Posts: 7
Joined: 05 Jun 2022, 17:06
Location: Fleury / France

Re: Algo Negamax

Postby H.G.Muller » 09 Jun 2022, 11:02

This is a bit tricky, since I have no experience with Objective C. But it should be something like:

Code: Select all
   //*************************************************************************************************************
   // 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
                  alpha:(int)alpha
                   beta:(int)beta   {
     
      Side otherSide = (side == sideWhite) ? sideBlack : sideWhite;
     
      /* Test assurant la sortie de la boucle de l'appel récursif (cf. plus bas)
      Si on a atteint la profondeur définie ou si le camp adv est Mat ou Pat, alors on sort */
      if (depth <= 0 || [self PossibleMovesForSide:otherSide board:board].count == 0)
      {
         int eval = [self EvalBoardForSide:side board:board] ;
         /*NSLog(@"\n\t\t\t NegaFS : Depth= %d (NB_MOVE_AHEAD= %d) - Coup %@= ?? - Old éval= ?? New éval= %d",
                              depth, NUMBER_MOVES_AHEAD, (otherSide == 1)? @"Noirs":@"Blancs",eval); */
         if(eval >= beta) // <-------------------------------------- only return when eval gives a beta cutoff
         return eval;
         if(eval > alpha) alpha = eval; // <------------------------- accept eval as the (expected) score of non-capture moves
         //return (side == sideBlack)? eval:-eval; // TEST !?
      }
     
      // sinon on descend dans l'arbre des coups successifs par appel récursif
//      else <---------------------------------------------------- This 'else' must be removed


In the loop over moves you would have to skip the non-captures:

Code: Select all
         for (Move *moveEnCours in [self PossibleMovesForSide:otherSide board:board])
         {
            if(depth <= 0 && !IsCapture(moveEnCourse)) continue; // <----------- Skip non-captures in QS
            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 PUIS 1


How the function IsCapture() would figure out whether moveEnCourse is a capture or not you will have to figure out yourself.

And, like I said, the order in which the for-loop presents the PossibleMovesForSide can have a huge effect on the efficiency of the search.
User avatar
H.G.Muller
 
Posts: 3389
Joined: 16 Nov 2005, 12:02
Location: Diemen, NL

Re: Algo Negamax

Postby MortyMars » 09 Jun 2022, 23:50

Thanks H.G. :D
It's much clearer with your suggested code change.
As far as determining whether the move being considered is a catch or not, I think I should be able to do that without too much trouble 8-)
However, as for the order in which the possible moves are examined, I admit that this is beyond my control : I'll rely on my luck :wink:
I'm putting all this in my code and I'll give news.
Thanks again !
MortyMars
 
Posts: 7
Joined: 05 Jun 2022, 17:06
Location: Fleury / France

Re: Algo Negamax

Postby H.G.Muller » 10 Jun 2022, 08:39

The problem with relying on luck is that you have to be lucky for every move of the game in order to finish it. As long as you do not control the order in which the moves (in particular the captures) are searched, it is advisable to to restrict the moves that are searched when depth <= 0 to the captures of the piece moved in the previous ply. (Which you would then have to pass as an additional parameter to NegamaxForSide.)

A QS searching all captures can potentially search very deep before a position without captures results. Especially when there are Queens on a crowded board. Queens are so mobile that they can gobble up many pieces, and there is no limitation on how far negative 'depth' can go. So an 'all-capture search' can easily add an extra 10 or even 20 ply to the search when both Queens go onto such a 'plunder raid', usually in billions of different ways. While capturing the opponent's Queen rather than continuing your own plunder raid would have put an immediate and profitable stop to it. But once your Queen has entered the opponent's camp it usually has a wide choice for what to capture next, so statistically it is much more likely that one of these captures will be searched rather than capturing the opponent Queen.

When you restrict the search to recaptures to the same square, the search will hardly ever need more than 3 extra ply before all pieces attacking the square have been traded. And, more importantly, at any point of the exchange the choice will be limited to just 2 or 3 pieces.
User avatar
H.G.Muller
 
Posts: 3389
Joined: 16 Nov 2005, 12:02
Location: Diemen, NL

Re: Algo Negamax

Postby MortyMars » 11 Jun 2022, 00:49

Hello H.G. :D

Regarding your penultimate post, I have implemented your code proposal.
Unfortunately, the new exit condition of the recursive loop (depth <=0) seems to be sufficiently disturbed that the recursion is done in an almost infinite loop: during several tests (board of beginning of game or of middle of game) I was each time obliged to interrupt the execution because I reached depth values exceeding -6000... :shock:
Needless to say, my computer was all fans on
So I decided to cut the cake by adding to the refactored code an additional test that causes an output with a simple return of 'eval' as soon as 'depth <=-1' (I tested larger values but it's unplayable in terms of response time)
I discovered in passing that the AI was not making the right choices for it in terms of score :x
I need to fix this problem of reversing or not reversing the score when it's Black's turn to play... Any ideas on this subject?

Concerning your last post, I agree with you, but without knowing where I'm really going, I'll have to dig into these tracks and implement them (after fixing the AI choice bug)...

Thank you again
Sincerely
MortyMars
 
Posts: 7
Joined: 05 Jun 2022, 17:06
Location: Fleury / France

Re: Algo Negamax

Postby H.G.Muller » 11 Jun 2022, 11:42

A depth of -6000 should be impossible; if you only search captures when depth <=0 you should go at the very worst to -31, after which only a single piece is left on the board, and thus nothing to capture. If you already stop before capturing a King you can at worst go to depth = -30.

So it seems the code you wrote for identifying a move as a capture is not working as it should.
User avatar
H.G.Muller
 
Posts: 3389
Joined: 16 Nov 2005, 12:02
Location: Diemen, NL

Re: Algo Negamax

Postby MortyMars » 11 Jun 2022, 22:51

Yes, it does make sense :o
Thank you for this undeniable observation :wink:
I am therefore reviewing my Method for determining whether there is a capture or not...
Sincerely :)
MortyMars
 
Posts: 7
Joined: 05 Jun 2022, 17:06
Location: Fleury / France

Re: Algo Negamax

Postby MortyMars » 12 Jun 2022, 21:37

Hello H.G. :)

I have revised my test to highlight a move with capture.
It was buggy but it works now, and I don't get the erratic behaviour I used to get.
The results are rather encouraging in terms of the performance of the algorithm (better relevance), even if there are obviously still some nice improvements to be found.

For information the new Negamax is the following (without comments):
Code: Select all
   //***************************************************************************************************
   // Méthode de classe - Implémentation de l'algo 'Negamax' ('Minimax' compact) avec élagage alpha-bêta
   // L'appel initial à 'NegaMax' se fait dans 'BestMoveForSide'. Les appels suivants se font par récursi-
   // vité dans le coeur de 'NegaMax' avec des param adaptés à l'alternance IA/Joueur des coups examinés.
   // Une touche de 'Quiescence Search' (QS) est ajouté au code pour une meilleure efficacité de l'algo...
   +(int)NegamaxForSide:(Side)side
                  board:(ChessBoard *)board
                  depth:(int)depth
                  alpha:(int)alpha
                   beta:(int)beta   {
     
      Side otherSide = (side == sideWhite) ? sideBlack : sideWhite;
      int eval = [self EvalBoardForSide:side board:board] ;

      if ([self PossibleMovesForSide:otherSide board:board].count == 0) return eval;
      if (depth <= 0)
      {
         if (eval >= beta) return eval;
         if (eval > alpha) alpha = eval;
         NSLog(@"\nQuiescence Search (QS) en depth : %d",depth);
      }
     
      for (Move *moveEnCours in [self PossibleMovesForSide:otherSide board:board])
      {
         BOOL capture = NO;
         int typePiece  = [board pieceAtPos:moveEnCours.dest].type;
         Side sidePiece = [board pieceAtPos:moveEnCours.dest].side;
         if (typePiece != Invalide) {
            if (sidePiece == otherSide) {
               capture = YES;
               NSLog(@"Pièce potentiellement prise : type (1 à 6) = %d side (Black 1 - White 2) %d",
                     typePiece, sidePiece);
            }
         }
         if(depth <= 0 && !capture) {
            NSLog(@"\n Move : %@ abandonné car sans capture Next Move !!", moveEnCours);
            continue;
         }
         
         ChessBoard *newBoard = board.copy;
         [newBoard PerformMove:moveEnCours];
         
         int score = -[self NegamaxForSide:otherSide 
                                     board:newBoard
                                     depth:depth - 1 
                                     alpha:-beta     
                                      beta:-alpha];   
         if (score >= alpha) {
            alpha = score;
            if (alpha >= beta) {
               nbElag ++;
               NSLog(@"\n\t\t\t NegaFS : Branches élaguées = %d", nbElag);
               break;
            }
         }
      }
      return alpha;
   }



I also reworked my evaluation function, which I have great difficulty in stabilizing the code for a satisfactory AI behavior:
Code: Select all
   //***************************************************************************************************
   // Méthode de classe MCN
   // 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 evalRetour = 0;  /* Valeur retournée pour l'algorithme Negamax */
      evalBoard = 0;       /* Valeur affichée respectant la convention   */
     
      /* ÉVALUATION MATÉRIELLE - On balaye chaque case de l'échiquier considéré, pour obtenir une valeur
      globale totalisant la valeur de chacune des pièces encore présentes. À noter que la valeur relative
      des pièces (au Roi près) 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 Invalide:                  break;   // si pas de pièce, pas de valeur ajoutée
                  case Pion:    value = 100;      break;   // s'il y a un Pion : +100
                  case Cava:    value = 300;      break;   // +300 pour un Cavalier
                  case Fou:     value = 300;      break;   // +300 pour un Fou
                  case Tour:    value = 500;      break;   // +500 pour une Tour
                  case Dame:    value = 900;      break;   // +900 pour la Dame
                  case Roi:     value = 100000;   break;   // +100 000 pour le Roi !!!!
                  /* Bien que le Roi ne puisse être capturé -ce qu'ignorent complètement la présente méthode
                  d'évaluation, le moteur de l'IA, ainsi que la méthode gérant le déplacement des pièces- il
                  est important de lui accorder une forte valeur afin d'inciter l'IA à choisir, par appat du
                  gain, un coup qui permettrait de le capturer si c'était effectivement possible... */
               }
               
               /* Si la pièce est Blanche sa valeur s'ajoute au total, sinon elle est déduite
               (par conv. une éval + indique un avantage aux Blancs et une éval - un avantage aux Noirs) */
               evalBoard  += value * ((piece.side == sideWhite)? 1 : -1);   // INCRÉMENT VALEUR AFFICHÉE
               evalRetour += value * ((piece.side == sideIA)? 1 : -1);
               
            } /* Fin de if piece*/
         } /* Fin de for y */
      } /* fin de for x */
     
      /* PRISE EN COMPTE DE LA MISE EN ÉCHEC ET MAT
      NB : La prise en compte de la mise en échec, implémentée un temps dans l'éval, a été abandonnée car
      elle perturbait le choix du coup quand il s'opposait à une prise potentielle de pièce, pour un bénéfice
      (la mise en échec) qui n'est finalement que temporaire sans garantir un avantage stratégique futur */
      //Side otherSide = (side == sideWhite)? sideBlack:sideWhite;
     
      /* Si les Noirs sont Mat */
      if ([self TestEchecRoiSide:sideBlack inBoard:board]) {
         if ([self PossibleMovesForSide:sideBlack board:board].count == 0) {
            evalBoard += +100000; /* Valeur positive car situation favorisant les Blancs */
            evalRetour += +100000 * ((sideIA == sideWhite)? 1 : -1);
         }
      }
      /* Si les Blancs sont Mat */
      else if ([self TestEchecRoiSide:sideWhite inBoard:board]) {
         if ([self PossibleMovesForSide:sideWhite board:board].count == 0) {
            evalBoard += -100000; /* Valeur négative car situation favorisant les Noirs */
            evalRetour += +100000 * ((sideIA == sideBlack)? 1 : -1);
         }
      }
      /* FIN DE PRISE EN COMPTE DE LA MISE EN ÉCHEC ET MAT  */
     
      /* PRISE EN CPTE DES PIONS EN AVANT-DERNIÈRE RANGÉE : +900 ACCORDÉS COMME SI DÉJÀ PROMUS EN DAMES
      Échiquier orienté avec les Blancs en bas */
      if (sideJoueur == sideWhite) {
         for (int x = 0; x < 8; x ++) {
            Piece *pionB = board->pieceCase[x][6];  // Pion Blanc en rangée 6
            if ((pionB.type == Pion) && (pionB.side == sideWhite)) {
               evalBoard  += +900; /* Valeur positive car situation favorisant les Blancs */
               evalRetour += +900 * ((sideIA == sideWhite)? 1 : -1);
            }
            Piece *pionN = board->pieceCase[x][1];  // Pion Noir en rangée 1
            if ((pionN.type == Pion) && (pionN.side == sideBlack)) {
               evalBoard  += -900; /* Valeur négative car situation favorisant les Noirs */
               evalRetour += +900 * ((sideIA == sideBlack)? 1 : -1);
            }
         }
      }
      /* Échiquier orienté avec les Noirs en bas */
      if (sideJoueur == sideBlack) {
         for (int x = 0; x < 8; x ++) {
            Piece *pionB = board->pieceCase[x][1];  // Pion Blanc en rangée 1
            if ((pionB.type == Pion) && (pionB.side == sideWhite)){
               evalBoard  += +900 ; /* Valeur positive car situation favorisant les Blancs */
               evalRetour += +900 * ((sideIA == sideWhite)? 1 : -1);
            }
            Piece *pionN = board->pieceCase[x][6];  // Pion Noir en rangée 6
            if ((pionN.type == Pion) && (pionN.side == sideBlack)){
               evalBoard  += -900; /* Valeur négative car situation favorisant les Noirs */
               evalRetour += +900 * ((sideIA == sideBlack)? 1 : -1);
            }
         }
      }
      /* FIN DE PRISE EN COMPTE DES PIONS ARRIVÉS SUR LEUR AVANT DERNIÈRE RANGÉE */

      /* Mise en forme du 'lblEvalBoard' de l'interface, avec un '+' ajouté aux valeurs positives */
      if (evalBoard > 0)
            monMCNControleur.lblEvalBoard.cell.title = [NSString stringWithFormat:@"Éval : +%d", evalBoard];
      else  monMCNControleur.lblEvalBoard.cell.title = [NSString stringWithFormat:@"Éval : %d",  evalBoard];
     
      return evalRetour;
   }


I'll try to make it (the AI) a better player than me, who is a schoolboy ;)
Sincerely
MortyMars
 
Posts: 7
Joined: 05 Jun 2022, 17:06
Location: Fleury / France


Return to Programming and Technical Discussions

Who is online

Users browsing this forum: No registered users and 4 guests