Forum
CSS-Shop
## 1. Didaktisches Alpha-Beta wie aus einem Lehrbuch
```c
static int negamax(Position *position, int depth, int alpha, int beta)
{
MoveList moves = generate_legal_moves(position);
if (moves.count == 0)
return matt_oder_patt(position);
if (depth == 0)
return evaluate(position);
int best = -INF;
for (size_t i = 0; i < moves.count; ++i) {
Undo undo;
make_move(position, moves, &undo);
int score = -negamax(position, depth - 1,
-beta, -alpha);
unmake_move(position, moves, &undo);
if (score > best)
best = score;
if (score > alpha)
alpha = score;
if (alpha >= beta)
break; /* Beta-Cutoff */
}
return best;
}
```
Die Hauptschleife ist leicht erkennbar:
1. nächsten legalen Zug nehmen,
2. Zug ausführen,
3. rekursiv suchen,
4. Zug zurücknehmen,
5. besten Wert und `alpha` aktualisieren,
6. bei `alpha >= beta` die übrigen Züge abschneiden.
Das Minuszeichen vor dem rekursiven Aufruf entsteht durch Negamax: Nach
jedem Zug wechselt die Seite, aus deren Sicht die Bewertung gelesen wird.
## 2. Entsprechender Kern der Glasgow-Suche
Die wirkliche Portierung befindet sich in
`rom_search_run_fixed_node()` in `engine/src/rom_search.c`. Der folgende
Ausschnitt ist gekürzt, behält aber die Struktur und die Namen der echten
Hilfsfunktionen bei:
```c
/* Ersten priorisierten Kandidaten erzeugen und ausführen. */
glasgow_rom_search_prepare_first_descend(..., &first);
child_position = first.child_position;
child_local_2 = first.descend.recurse_local_2;
child_frame_0 = first.descend.recurse_d6;
child_source = first.descend.move.source;
child_encoded_destination = first.descend.move.encoded_destination;
/* Das ist die eigentliche Hauptschleife über die Kandidaten. */
for (; {
uint16_t recursive_d0;
uint16_t recursive_a0;
++runtime->result->edges;
/* Entspricht dem rekursiven negamax()-Aufruf. */
rom_search_run_fixed_node(runtime,
&child_position,
child_local_2,
child_frame_0,
&recursive_d0,
&recursive_a0);
/*
* Zug zurücknehmen, Seite zurückdrehen, Rückgabewert negieren,
* mit dem bisherigen Wert vergleichen und gegebenenfalls PV ändern.
*/
glasgow_rom_search_finish_child_return(
&(GlasgowRomSearchChildReturnContext) {
.ram = runtime->context->ram,
.recursive_d0 = recursive_d0,
.recursive_a0 = recursive_a0,
.parent_local_12 = parent_local_12,
.parent_local_24 = parent_local_24,
.parent_d6 = parent_d6,
},
&child_return);
if (child_return.score.retry_generation) {
/* Glasgow kann die selektive Zugerzeugung erneut anstoßen. */
rom_search_retry_root_candidate(..., &next);
child_position = next.child_position;
continue;
}
if (child_return.finish.outcome ==
GLASGOW_ROM_SEARCH_CANDIDATE_FINISH_LEAF) {
/* Dieser Knoten ist abgeschlossen: Wert an den Vater zurückgeben. */
*d0 = child_return.finish.local_4;
*a0 = child_return.finish.local_6;
return true;
}
/* Nächsten zugelassenen und priorisierten Zug holen und ausführen. */
glasgow_rom_search_prepare_next_descend(..., &next);
if (!next.child_ready) {
*d0 = next.pop.local_4;
*a0 = next.pop.local_6;
return true;
}
child_position = next.child_position;
child_local_2 = next.descend.recurse_local_2;
child_frame_0 = next.descend.recurse_d6;
child_source = next.descend.move.source;
child_encoded_destination = next.descend.move.encoded_destination;
}
```
Der entscheidende Wertvergleich steckt in
`glasgow_rom_search_score_return()`:
```c
existing_score =
((uint16_t)ram[f076] << 5) + ram[f076 + 1];
candidate_score =
((uint16_t)(uint8_t)d3 << 5) + (uint8_t)d4;
if (existing_score >= candidate_score) {
/* Der neue Zug verbessert die bisherige Schranke nicht. */
cleanup_required = true;
} else {
/* Neuer Bestwert; außerdem wird die Hauptvariante aktualisiert. */
ram[f076] = (uint8_t)d3;
ram[f076 + 1] = (uint8_t)d4;
update_principal_variation();
}
```Powered by mwForum 2.29.3 © 1999-2014 Markus Wichitill