Not logged inCSS-Forum
Forum CSS-Online Help Search Login
CSS-Shop Impressum Datenschutz
Up Topic Hauptforen / Schachprogrammierung / Alpha Beta Suche
- - 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);
  }
}
Parent - - By Lothar Jung Date 2021-09-23 10:28 Edited 2021-09-23 10:33 Upvotes 1
Parent - By Lothar Jung Date 2021-11-10 13:17 Upvotes 1
Hier der Wikipedia Beitrag zum Pruning:

https://de.wikipedia.org/wiki/Pruning?wprov=sfti1
- By Lothar Jung Date 2021-09-23 13:42 Edited 2021-09-23 13:49 Upvotes 1
Hier eine sehr gute Veröffentlichung „APPLYING-ALPHA-BETA-ALGORITHM-IN-A-CHESS-ENGINE“:

https://www.researchgate.net/publication/319390201_APPLYING_ALPHA-BETA_ALGORITHM_IN_A_CHESS_ENGINE/fulltext/59a7804ba6fdcc61fcfbde3d/APPLYING-ALPHA-BETA-ALGORITHM-IN-A-CHESS-ENGINE.pdf?origin=publication_detail

Hier eine weitere Veröffentlichung mit Pseudo-Code Beispielen „Alpha-Beta with Sibling Prediction Pruning in Chess“:

https://homepages.cwi.nl/~paulk/theses/Carolus.pdf
- By Lothar Jung Date 2021-12-07 22:10 Upvotes 1
Hier ein guter Artikel von Thomas Zipproth:

https://computerschach.de/Files/2000/Suchet,%20so%20werdet%20ihr%20finden.pdf

Exponentielles Wachstum des Suchbaums.
Up Topic Hauptforen / Schachprogrammierung / Alpha Beta Suche

Powered by mwForum 2.29.3 © 1999-2014 Markus Wichitill