Wann sucht Alpha-Beta mit Speicher-Return-Cutoff-Werten?

Question

Ich habe eine Alpha-Beta-Suche mit Transpositionstabelle implementiert.

Habe ich hier die richtigen Ideen zum Speichern von Cutoffs in der Tabelle?

Spezifisch, ist mein Schema für die Rückgabe der Cutoffs, wenn ein Tabellentreffer auftritt, korrekt? (Und ebenso, sie zu speichern.) Meine Implementierung scheint mit this one zu widersprechen, aber es scheint mir intuitiv richtig.

Auch speichert mein Algorithmus nie einen Eintrag mit der At_most-Flag. Wann sollte ich diese Einträge speichern?

Hier ist meine (vereinfacht) Code demonstriert die wichtigsten Ideen:

int ab(board *b, int alpha, int beta, int ply) { 
    evaluation *stored = tt_get(b); 
    if (entryExists(stored) && stored->depth >= ply) { 
     if (stored->type == at_least) { // lower-bound 
      if (stored->score >= beta) return beta; 
     } else if (stored->type == at_most) { // upper bound 
      if (stored->score <= alpha) return alpha; 
     } else { // exact 
      if (stored->score >= beta) return beta; // respect fail-hard cutoff 
      if (stored->score < alpha) return alpha; // alpha cutoff 
      return stored->score; 
     } 
    } 

    if (ply == 0) return quiesce(b, alpha, beta, ply); 

    int num_children = 0; 
    move chosen_move = no_move; 
    move *moves = board_moves(b, &num_children); 

    int localbest = NEG_INFINITY; 
    for (int i = 0; i < num_children; i++) { 
     apply(b, moves[i]); 
     int score = -ab(b, -beta, -alpha, ply - 1); 
     unapply(b, moves[i]); 
     if (score >= beta) { 
      tt_put(b, (evaluation){moves[i], score, at_least, ply}); 
      return beta; // fail-hard 
     } 
     if (score >= localbest) { 
      localbest = score; 
      chosen_move = moves[i]; 
      if (score > alpha) alpha = score; 
     } 
    } 
    tt_put(b, (evaluation){chosen_move, alpha, exact, ply}); 
    return alpha; 
} 

Answer 1

Meine Implementierung mit diesem

Der Code für die Umsetzung Tabelle nachschlagen scheint Recht zu widersprechen scheint, mich. Es entspricht in etwa dem auf wikipedia.

// Code on Wikipedia rewritten using your notation/variable names 
if (entryExists(stored) && stored->depth >= ply) 
{ 
    if (stored->type == at_least) 
    alpha = max(alpha, stored->score); 
    else if (stored->type == at_most) 
    beta = min(beta, stored->score); 
    else if (stored->type == exact) 
    return stored->score; 

    if (alpha >= beta) 
    return stored->score; 
} 

, die auf entspricht (das Rückschlag if (alpha >= beta) wurde innerhalb eines jeden Knotentyp bewegt):

if (entryExists(stored) && stored->depth >= ply) 
{ 
    if (stored->type == at_least) 
    { 
    alpha = max(alpha, stored->score); 
    if (alpha >= beta) return stored->score; 
    } 
    else if (stored->type == at_most) 
    { 
    beta = min(beta, stored->score); 
    if (alpha >= beta) return stored->score; 
    } 
    else if (stored->type == exact) 
    return stored->score; 
} 

und dies kann in geändert werden:

if (entryExists(stored) && stored->depth >= ply) 
{ 
    if (stored->type == at_least) 
    { 
    // if (max(alpha, stored->score) >= beta) ... 
    if (stored->score >= beta) return stored->score; 
    } 
    else if (stored->type == at_most) 
    { 
    // if (min(beta, stored->score) <= alpha) ... 
    if (stored->score <= alpha) return stored->score; 
    } 
    else if (stored->type == exact) 
    return stored->score; 
} 

Der verbleibende Unterschied ist, dass Wikipedia verwendet eine fail-soft Optimierung, während Ihr Code das klassische Alpha-Beta-Beschneiden ist (fail-hard). Fail-Soft ist eine kleine Verbesserung, ändert aber nicht die Schlüsselpunkte der Algorithmen.

---

mein Algorithmus speichert nie einen Eintrag mit der at_most Flagge. Wann sollte ich diese Einträge speichern?

Es gibt einen Fehler beim Speichern des Knotentyps exact/at_most. Hier können Sie gehen davon aus, dass der Knoten immer vom Typ ist exact:

tt_put(b, (evaluation){chosen_move, alpha, exact, ply}); 

tatsächlich kann es ein at_most Knoten sein:

if (alpha <= initial_alpha) 
{ 
    // Here we haven't a best move. 
    tt_put(b, (evaluation){no_move, initial_alpha, at_most, ply}); 
} 
else 
    tt_put(b, (evaluation){chosen_move, alpha, exact, ply});