,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.
