Récursion et gestion de mé moire

Bonjour,

J'ai entrepris d'écrire un programme de jeu d'Echecs. Je suis venu à bout,
non sans mal, des préliminaires imposés: définition des règles de
déplacement des pièces, interface graphique pour les déplacer,
enregistrement écrit des coups joués et déplacement dans la partie par des
boutons avant / arrière.

J'en suis maintenant au vif du sujet, à savoir la recherche du meilleur coup
au moyen de l'algorithme MinMax avec coupures alpha-beta.
La difficulté vient de ce que cet algorithme est récursif. Voici sa
structure.

"pos" décrit l'échiquier sur 84 octets." minDepth" est la profondeur en
demi-coups à laquelle on limite la recherche. "alpha" est une limite
inférieure du score et "beta" une limite supérieure. Au fil de itérations,
la fourchette alpha beta se rétrécit:

-(int) minMax:(LBPosition)pos minDepth:(int)minDepth alpha:(int)A
beta:(int)B
{
.......
str = [self setMovesString:pos]; // mouvements possibles: a1a2/b1b2/....
moves = [str componentsSeparatedByString:@"/"]; //NSArray coups autorisés
......
for (i=0; i<[moves count] ;i++)
{
......
moveStr = [moves objectAtIndex:i];
nextPos = [self doMove:moveStr atPos:pos]; //nouvel échiquier
alpha = A > alphaPos ? A : alphaPos; //alpha = Max(A, alphaPos)
/**********************************************************************/
//Ici intervient la récursion
moveScore = [self minMax:nextPos minDepth:minDepth alpha:alpha beta:B];

/**********************************************************************/
if (alphaPos < moveScore) //alphaPos = Max (alphaPos, moveScore);
alphaPos = moveScore;

if (alphaPos >= B)
return alphaPos; //coupure beta;
}
return alphaPos;
}

(Cet extrait ne comporte que la partie Max. La partie Min est symétrique et
concerne les coups de l'adversaire.)

Comme une position donne lieu en moyenne à 30 coups possibles, la récursion
est intense. une exploration totale sur une profondeur 4 donnerait lieu à
810 000 appel de MinMax. La coupure alpha-beta limite de 5/6 fois ce nombre,
mais je suis parvenu à 76000 appels sur une profondeur 4, en 4 minutes 38''

Le problème que je rencontre alors est que quand je devrais reprendre la
main, j'obtiens la roulette arc-en-ciel si longtemps que je suis obligé de
forcer le Quit...

Je me suis livré à un examen via ObjectAlloc qui donne ceci:

-Au départ, programme initialisé: Global allocation Total, Current = 1.9 Mo
-Pendant la recherche du premier coup blanc 1.Cc3, trouvé en 3 sec. et <
2000 appels de MinMax (Hors ObjectAlloc), Global allocation Total, Current
atteint 17 Mo puis revient à sa valeur initiale.
-Pendant la recherche de la réponse noire 1...c7-c6 (bizarre comme
ouverture... trouvé en 12" et < 6000 appels) Global allocation Total,
Current atteint 64 Mo puis revient à 5,3 Mo (Memory leakage possible...)

Si j'extrapole vers la situation où le programme trouve une bonne réfutation
à une menace de mat en 2 coups en 4' 38" et 76000 appels de MinMax , cela
donne 800Mo d'allocation courante! (Pour les initiés, il s'agit du Mat de
Legal, où les Blancs offrent leur Dame pour faire ensuite Mat en deux coups.
Normal que le programme aie pris son temps avant de renoncer au cadeau)

J'ai installé un pool d'autoRelease, mais c'est complètement inopérant. Si
je comprends bien ça doit être normal, puisqu'on ne sort pas de l'EventLoop
tant que la récursion est en cours.

Merci à qui a eu la patience de me lire, et plus encore à qui pourrait
m'indiquer la bonne méthode pour gérer proprement les désallocations.
Mes premiers résultats sont encourageants et ça m'ennuie d'être bloqué par
ce problème.

Louis Balourdet