NegaMax ne fonctionne pas comme prévu

Question

J'ai un problème avec la mise en œuvre d'un simple NegaMax dans mes échecs programm.

Selon plusieurs sites web negamax devrait ressembler ceci dans mon code:

int Position::negaMax(int curr_depth, int depth) {
    cd = curr_depth-1;
    if (curr_depth==depth) return evaluate();

    int max = -500000;

    calc_moves(true);
    doBackup(cd);
    for (int i=0;i<mvSize[cd];i++) {
        move_figure(mvD[cd][i][0],mvD[cd][i][1],mvD[cd][i][2],mvI[cd][i][0],mvI[cd][i][1]);    
        int score = -negaMax(curr_depth+1,depth);
        cd--; undoMove(cd);

        if (curr_depth==1)
            cout << "Move: " << getMoveString(i) << ", Score: " << score << endl;        

        if (score>max)
            max=score;
   }
   return max;
}

Mais avec ce code j'obtiens ce résultat:

Move: a2a3, Score: 0
Move: a2a4, Score: 0
Move: b2b3, Score: 0
Move: b2b4, Score: 0
Move: c2c3, Score: 0
Move: c2c4, Score: 0
Move: d2d3, Score: 0
Move: d2d4, Score: 0
Move: e2e3, Score: 0
Move: e2e4, Score: 0
Move: f2f3, Score: 0
Move: f2f4, Score: 0
Move: g2g3, Score: 0
Move: g2g4, Score: 0
Move: h2h3, Score: 0
Move: h2h4, Score: 0
Move: b1a3, Score: 0
Move: b1c3, Score: 0
Move: g1h3, Score: 0
Move: g1f3, Score: 0
score: 0

Qui peut ne pas être juste, si je negaMax pour ply3 à partir de la position de départ.

Si je supprime le signe moins devant de la fonction récursive appel, je reçois un plus meilleur résultat.Mais à mon avis ça ne peut pas être de droite, parce que sans le signe moins dans le code ci-dessus, j'ai seulement de maximiser le score pour un joueur, mais pas pour les deux.

Move: a2a3, Score: 0
Move: a2a4, Score: 30
Move: b2b3, Score: 0
Move: b2b4, Score: 30
Move: c2c3, Score: 0
Move: c2c4, Score: 30
Move: d2d3, Score: 295
Move: d2d4, Score: 295
Move: e2e3, Score: 295
Move: e2e4, Score: 295
Move: f2f3, Score: 0
Move: f2f4, Score: 30
Move: g2g3, Score: 0
Move: g2g4, Score: 30
Move: h2h3, Score: 0
Move: h2h4, Score: 30
Move: b1a3, Score: 30
Move: b1c3, Score: 30
Move: g1h3, Score: 30
Move: g1f3, Score: 30
score: 295

J'ai essayé de mettre en œuvre les différentes versions de MinMax, NegaMax et AlphaBeta.Mais je reçois toujours un score de 0.Je serais très reconnaissant pour tous les indicateurs.

Answer 1

Le véritable squelette de negamax semble être correctement mis en œuvre.(Cependant, je suis plus habitué à voir une seule profondeur variable passée à la fonction récursive qui est soustrait chaque pli - et renvoie le score évalué lorsqu'il est égal à 0).Mais il est difficile de diagnostiquer votre problème comme un outsider en raison de la grande dépendance sur d'autres codes.

Plutôt que de la pêche pour vous, je pense qu'il serait mieux pour vous enseigner comment pêcher. Je suggère de passer du temps à construire une routine que les sorties de la structure de l'arbre et le score cumulé visuellement en quelque sorte.Il semble que vous avez déjà les blocs de construction d'une telle chose, aussi.Il peut être de temps à le faire au départ, mais dans le long terme aidera grandement avec le débogage - et croyez-moi, avec un moteur d'échecs, le chalutage par le biais de cet arbre sera une malheureusement fréquent de la réalité, surtout lorsque vous implémentez les plus obscurs se déplace comme en-passant - ceux-ci peuvent causer toutes sortes de problèmes à l'intérieur de l'arbre (j'y ai été).

Essayez de sortir quelque chose comme ceci:

<move-white ---->
    <move-black ----><eval score>
    <move-black ----><eval score>
    <move-black ----><eval score>
    <best black score>
<move-white ---->
    <move-black ----><eval score>
    <move-black ----><eval score>
    <move-black ----><eval score>
    <move-black ----><eval score>
    <move-black ----><eval score>
    <move-black ----><eval score>
    <best black score>
<move-white ---->
    <move-black ----><eval score>
    <move-black ----><eval score>
    <best black score>
<best white score>

...où ---- indique le déplacer.

Évidemment, cela va être beaucoup plus grand et plus profond, mais au moins vous pouvez voir ce qui se passe d'une manière plus humaine de manière conviviale.J'espère qu'il va vous aider avec d'autres problèmes dans le long terme, aussi.La configuration d'un bon système de débogage avec un moteur d'échecs est essentiel, que vous allez probablement trouver.