Negamax non funziona come previsto

Question

Ho un problema con l'implementazione di un semplice Negamax nel mio programma di scacchi.

Secondo diversi siti Web, Negamax dovrebbe apparire come segue nel mio codice:

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;
}

Ma con questo codice ottengo questo output:

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

Non può essere giusto, se negAmax per Ply3 dalla posizione di partenza.

Se rimuovo il segno meno davanti alla chiamata di funzione ricorsiva, ottengo un risultato più migliore. Ma a mio avviso che non può essere giusto, perché senza il segno meno nel codice sopra, massimizzo il punteggio solo per un giocatore, ma non per entrambi.

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

Ho provato a implementare diverse versioni di Minmax, Negamax e Alphabeta. Ma ricevo sempre un punteggio di 0. Sarei molto grato per qualsiasi suggerimento.

Answer 1

Lo scheletro effettivo di Negamax sembra essere implementato correttamente. (Tuttavia, sono più abituato a vedere una singola variabile di profondità passata alla funzione ricorsiva che viene sottratta ogni ply e restituisce il punteggio valutato quando è uguale a 0). Ma è difficile diagnosticare il tuo problema come estraneo a causa della grande dipendenza dall'altro codice.

Piuttosto che pescare per te, sento che sarebbe meglio insegnarti come pescare. Suggerirei di passare un po 'di tempo per costruire una routine che produce visivamente la struttura dell'albero e il punteggio cumulativo. Sembra che tu abbia già anche i mattoni di una cosa del genere. Potrebbe richiedere molto tempo farlo inizialmente, ma a lungo termine aiuterà molto con il debug - e credimi, con un motore a scacchi, a strascico attraverso questo albero sarà una realtà purtroppo frequente, specialmente quando implementerai mosse più oscure come EN -Passant - Questi possono causare tutti i tipi di problemi all'interno dell'albero (ci sono stato).

Prova a produrre qualcosa del genere:

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

...dove ---- indica la mossa.

Ovviamente questo sarà molto più grande e più profondo, ma almeno puoi vedere cosa sta succedendo in modo più amichevole. Spero che ti aiuti anche con altri problemi a lungo termine. La creazione di un buon sistema di debug con un motore a scacchi è vitale, come probabilmente troverai.