By Lothar Jung
Date 2021-09-17 17:34
Edited 2021-09-17 17:38
Upvotes 1
/*
* SEARCH.C
* Tom Kerrigan's Simple Chess Program (TSCP)
*
* Copyright 1997 Tom Kerrigan
*/
#include <stdio.h>
#include <string.h>
#include "defs.h"
#include "data.h"
#include "protos.h"
/* see the beginning of think() */
#include <setjmp.h>
jmp_buf env;
BOOL stop_search;
/* think() calls search() iteratively. Search statistics
are printed depending on the value of output:
0 = no output
1 = normal output
2 = xboard format output */
void think(int output)
{
int i, j, x;
/* try the opening book first */
pv[0][0].u = book_move();
if (pv[0][0].u != -1)
return;
/* some code that lets us longjmp back here and return
from think() when our time is up */
stop_search = FALSE;
setjmp(env);
if (stop_search) {
/* make sure to take back the line we were searching */
while (ply)
takeback();
return;
}
start_time = get_ms();
stop_time = start_time + max_time;
ply = 0;
nodes = 0;
memset(pv, 0, sizeof(pv));
memset(history, 0, sizeof(history));
if (output == 1)
printf("ply nodes score pv\n");
for (i = 1; i <= max_depth; ++i) {
follow_pv = TRUE;
x = search(-10000, 10000, i);
if (output == 1)
printf("%3d %9d %5d ", i, nodes, x);
else if (output == 2)
printf("%d %d %d %d",
i, x, (get_ms() - start_time) / 10, nodes);
if (output) {
for (j = 0; j < pv_length[0]; ++j)
printf(" %s", move_str(pv[0][j].b));
printf("\n");
fflush(stdout);
}
if (x > 9000 || x < -9000)
break;
}
}
/* search() does just that, in negamax fashion */
int search(int alpha, int beta, int depth)
{
int i, j, x;
BOOL c, f;
/* we're as deep as we want to be; call quiesce() to get
a reasonable score and return it. */
if (!depth)
return quiesce(alpha,beta);
++nodes;
/* do some housekeeping every 1024 nodes */
if ((nodes & 1023) == 0)
checkup();
pv_length[ply] = ply;
/* if this isn't the root of the search tree (where we have
to pick a move and can't simply return 0) then check to
see if the position is a repeat. if so, we can assume that
this line is a draw and return 0. */
if (ply && reps())
return 0;
/* are we too deep? */
if (ply >= MAX_PLY - 1)
return eval();
if (hply >= HIST_STACK - 1)
return eval();
/* are we in check? if so, we want to search deeper */
c = in_check(side);
if (c)
++depth;
gen();
if (follow_pv) /* are we following the PV? */
sort_pv();
f = FALSE;
/* loop through the moves */
for (i = first_move[ply]; i < first_move[ply + 1]; ++i) {
sort(i);
if (!makemove(gen_dat.m.b))
continue;
f = TRUE;
x = -search(-beta, -alpha, depth - 1);
takeback();
if (x > alpha) {
/* this move caused a cutoff, so increase the history
value so it gets ordered high next time we can
search it */
history[(int)gen_dat.m.b.from][(int)gen_dat.m.b.to] += depth;
if (x >= beta)
return beta;
alpha = x;
/* update the PV */
pv[ply][ply] = gen_dat.m;
for (j = ply + 1; j < pv_length[ply + 1]; ++j)
pv[ply][j] = pv[ply + 1][j];
pv_length[ply] = pv_length[ply + 1];
}
}
/* no legal moves? then we're in checkmate or stalemate */
if (!f) {
if (c)
return -10000 + ply;
else
return 0;
}
/* fifty move draw rule */
if (fifty >= 100)
return 0;
return alpha;
}
/* quiesce() is a recursive minimax search function with
alpha-beta cutoffs. In other words, negamax. It basically
only searches capture sequences and allows the evaluation
function to cut the search off (and set alpha). The idea
is to find a position where there isn't a lot going on
so the static evaluation function will work. */
int quiesce(int alpha,int beta)
{
int i, j, x;
++nodes;
/* do some housekeeping every 1024 nodes */
if ((nodes & 1023) == 0)
checkup();
pv_length[ply] = ply;
/* are we too deep? */
if (ply >= MAX_PLY - 1)
return eval();
if (hply >= HIST_STACK - 1)
return eval();
/* check with the evaluation function */
x = eval();
if (x >= beta)
return beta;
if (x > alpha)
alpha = x;
gen_caps();
if (follow_pv) /* are we following the PV? */
sort_pv();
/* loop through the moves */
for (i = first_move[ply]; i < first_move[ply + 1]; ++i) {
sort(i);
if (!makemove(gen_dat.m.b))
continue;
x = -quiesce(-beta, -alpha);
takeback();
if (x > alpha) {
if (x >= beta)
return beta;
alpha = x;
/* update the PV */
pv[ply][ply] = gen_dat.m;
for (j = ply + 1; j < pv_length[ply + 1]; ++j)
pv[ply][j] = pv[ply + 1][j];
pv_length[ply] = pv_length[ply + 1];
}
}
return alpha;
}
/* reps() returns the number of times the current position
has been repeated. It compares the current value of hash
to previous values. */
int reps()
{
int i;
int r = 0;
for (i = hply - fifty; i < hply; ++i)
if (hist_dat.hash == hash)
++r;
return r;
}
/* sort_pv() is called when the search function is following
the PV (Principal Variation). It looks through the current
ply's move list to see if the PV move is there. If so,
it adds 10,000,000 to the move's score so it's played first
by the search function. If not, follow_pv remains FALSE and
search() stops calling sort_pv(). */
void sort_pv()
{
int i;
follow_pv = FALSE;
for(i = first_move[ply]; i < first_move[ply + 1]; ++i)
if (gen_dat.m.u == pv[0][ply].u) {
follow_pv = TRUE;
gen_dat.score += 10000000;
return;
}
}
/* sort() searches the current ply's move list from 'from'
to the end to find the move with the highest score. Then it
swaps that move and the 'from' move so the move with the
highest score gets searched next, and hopefully produces
a cutoff. */
void sort(int from)
{
int i;
int bs; /* best score */
int bi; /* best i */
gen_t g;
bs = -1;
bi = from;
for (i = from; i < first_move[ply + 1]; ++i)
if (gen_dat.score > bs) {
bs = gen_dat.score;
bi = i;
}
g = gen_dat[from];
gen_dat[from] = gen_dat[bi];
gen_dat[bi] = g;
}
/* checkup() is called once in a while during the search. */
void checkup()
{
/* is the engine's time up? if so, longjmp back to the
beginning of think() */
if (get_ms() >= stop_time) {
stop_search = TRUE;
longjmp(env, 0);
}
}
By Lothar Jung
Date 2021-09-23 10:28
Edited 2021-09-23 10:33
Upvotes 1
By Lothar Jung
Date 2021-09-23 13:42
Edited 2021-09-23 13:49
Upvotes 1
Im Kontext der Schachprogrammierung ist Pruning eine wichtige Technik zur Optimierung des Suchprozesses nach dem besten Zug. Schach ist ein Spiel mit einer enormen Anzahl von möglichen Zügen und Spielverläufen, und es ist oft nicht praktikabel (oder sogar unmöglich), jeden einzelnen Zug und jedes einzelne Szenario zu betrachten. Pruning-Techniken werden verwendet, um die Anzahl der zu analysierenden Spielverläufe zu reduzieren und somit die Effizienz des Schachprogramms zu steigern.
Eines der bekanntesten Pruning-Verfahren in der Schachprogrammierung ist die Alpha-Beta-Pruning-Technik. Diese Technik ist eine Erweiterung des Minimax-Algorithmus, der in Spielbäumen verwendet wird, um den besten Zug zu bestimmen. Alpha-Beta-Pruning verbessert die Effizienz des Minimax-Algorithmus, indem es bestimmte Zweige des Spielbaums abbricht (oder "beschneidet"), wenn festgestellt wird, dass sie nicht zum besten möglichen Ergebnis führen werden. Dies reduziert die Anzahl der zu analysierenden Knoten und ermöglicht es dem Programm, tiefer in den Spielbaum zu schauen, ohne zusätzlichen Rechenaufwand.
Andere Pruning-Techniken, die in Schachprogrammen verwendet werden, sind zum Beispiel Null Move Pruning und Late Move Reductions. Null Move Pruning geht davon aus, dass ein guter Zug dem Gegner schaden wird und daher ist es unnötig, Züge zu prüfen, bei denen der Gegner ungestört bleibt. Late Move Reductions hingegen reduzieren die Suchtiefe für Züge, die als unwahrscheinlich angesehen werden.
Zusammenfassend lässt sich sagen, dass Pruning in der Schachprogrammierung dazu dient, die Anzahl der zu analysierenden Züge und Spielverläufe zu reduzieren, um die Effizienz und Geschwindigkeit des Programms zu verbessern. Es ist eine entscheidende Technik, um ein leistungsfähiges Schachprogramm zu entwickeln.
Die Alpha-Beta-Suche ist eine effiziente Suchmethode, die häufig in Schachprogrammen verwendet wird, um den Suchbaum zu durchsuchen und den besten Zug zu finden. Hier ist eine anschauliche Beschreibung, wie die Alpha-Beta-Suche in einem Schachprogramm funktionieren kann:
Stell dir vor, du spielst Schach gegen einen Computer. Jeder Zug, den du machst, eröffnet eine Vielzahl von Möglichkeiten, die der Computer erkunden kann. Die Alpha-Beta-Suche hilft dem Computer dabei, den Suchraum effizient einzuschränken und nur die vielversprechendsten Pfade zu untersuchen.
Die Suche beginnt in der aktuellen Spielsituation, in der der Computer an der Reihe ist. Der Computer betrachtet zuerst seinen eigenen Zug und bewertet die Position basierend auf verschiedenen Faktoren wie Materialvorteil, Positionierung der Figuren und möglichen Angriffen.
Nun beginnt die eigentliche Alpha-Beta-Suche. Der Computer betrachtet einen Zug, den er machen könnte, und simuliert dann, wie das Spiel fortgesetzt werden würde. Er berücksichtigt auch deine möglichen Züge als Gegenspieler. Um dies zu tun, wird ein Suchbaum aufgebaut, der alle möglichen Züge und ihre Auswirkungen darstellt.
Der Computer beginnt, den Suchbaum rekursiv zu durchsuchen. Er wählt einen Zug aus und bewertet die resultierende Position. Dabei verwendet er eine Bewertungsfunktion, die die Stärke der Position abschätzt. Je höher der Wert, desto besser die Position für den Computer.
Während der Suche verwendet der Computer zwei Werte, die als Alpha und Beta bezeichnet werden, um den Suchraum weiter einzuschränken. Alpha repräsentiert den bisher besten Zug für den Computer, während Beta den besten Zug für den Gegner darstellt.
Der Computer durchläuft nun die möglichen Züge in der aktuellen Position. Wenn er einen Zug gefunden hat, der besser ist als der bisherige Alpha-Wert, aktualisiert er Alpha. Wenn er jedoch feststellt, dass der Gegner einen Zug machen kann, der schlechter ist als der aktuelle Beta-Wert, bricht er die Suche in diesem Ast ab, da der Gegner diesen Zug ohnehin nicht wählen würde.
Dieses ständige Aktualisieren von Alpha und Beta erlaubt es dem Computer, den Suchraum effizient einzuschränken, da er unwichtige Zweige des Suchbaums überspringen kann.
Die Alpha-Beta-Suche durchsucht den Suchbaum schrittweise und bewertet die Positionen, bis sie eine vordefinierte Suchtiefe erreicht oder einen Endzustand des Spiels erreicht hat. Sobald die Suche abgeschlossen ist, wählt der Computer den besten Zug aus, der zu der besten Position führt, die er gefunden hat.
Auf diese Weise hilft die Alpha-Beta-Suche dem Computer, den riesigen Suchraum des Schachspiels effizient zu durchsuchen und gute Züge zu finden, ohne alle möglichen Kombinationen von Zügen bis zum Ende des Spiels zu überprüfen.
Powered by mwForum 2.29.3 © 1999-2014 Markus Wichitill
CSS-Shop