storing pv during search

Discussion of chess software programming and technical issues.

Moderator: Ras

ericlangedijk
Posts: 53
Joined: Thu Aug 08, 2013 5:13 pm

storing pv during search

Post by ericlangedijk »

In the recursive AlphaBeta algorithm I have to store the PV.
In the following code <moves> is in stack memory.
How can I best store the PV line at the place marked <STORE_PV>?
Can I get it from the stack?

Code: Select all

function tsearch.alphabeta(depth: integer; alpha, beta: tscore): tscore;
var
  moves: tmovelist;
  ms: pmovestack;
  u: tstateinfo;
  value: tscore;
  m: tmove;
  valid: integer;
label
  exitpoint;
begin
  if depth <= 0 then begin
    result := quiet(alpha, beta);
    if board.tomove = black then
      result := -result;
    exit;
  end;

  inc(searchdepth);
  valid := 0;
  board.genmoves(@moves);
  ms := @moves[0];

  while getnextmove(m) do begin
    board.makemove(m, u);
    inc(valid);
    value := -alphabeta(depth - 1, -beta, -alpha);
    board.unmakemove(m);

    if value >= beta then begin
      result := beta;
      goto exitpoint;
    end;

    if value > alpha then begin
      alpha := value;
      if atroot then begin
        bestmove := m;
        bestscore := alpha;
        STORE_PV()
      end;
    end;
    inc(ms);
  end;

  if valid = 0 then begin
    if board.isincheck then begin
      result := -mate + searchdepth - 1;
    end
    else
      result := drawscore();
  end
  else
    result := alpha;

  exitpoint:
    dec(searchdepth);
end;
Henk
Posts: 7251
Joined: Mon May 27, 2013 10:31 am

Re: storing pv during search

Post by Henk »

pv.Add(bestMove);
if (bestChild != null)
pv.AddRange(bestChild);

pv is an extra parameter for search.

protected virtual int Search(int depth, int lb, int ub, out MoveBase mvFound, List<MoveBase> pv, bool isPV)

In the recursive call I use

score = -Search(depth - 100, -ub, -lb, out mv2, child, isPV);
User avatar
hgm
Posts: 28464
Joined: Fri Mar 10, 2006 10:06 am
Location: Amsterdam
Full name: H G Muller

Re: storing pv during search

Post by hgm »

See my post in the active thread on tri-angular array.