out of time in PVS

Discussion of chess software programming and technical issues.

Moderators: hgm, Harvey Williamson, bob

Forum rules
This textbox is used to restore diagrams posted with the [d] tag before the upgrade.
AxolotlFever
Posts: 50
Joined: Sun Nov 11, 2018 8:26 pm
Location: Germany
Full name: Louis Mackenzie-Smith
Contact:

out of time in PVS

Post by AxolotlFever » Thu Dec 13, 2018 11:38 am

Hi all,

My engine is currently single-threaded, and does ok when I search to some fixed depth, or when I wait for a complete Iterative Deepening search to complete. However, if I try to interrupt my search in the middle of a PVS, then my program starts returning completely crazy moves, and it becomes terrible.

Have you implemented something to interrupt your search in the middle of PVS? If so, what do you return? Do you return eval? Alpha? Drop into Qsearch?

Thanks kindly in advance,
Louis

User avatar
Guenther
Posts: 3012
Joined: Wed Oct 01, 2008 4:33 am
Location: Regensburg, Germany
Full name: Guenther Simon
Contact:

Re: out of time in PVS

Post by Guenther » Thu Dec 13, 2018 11:54 am

AxolotlFever wrote:
Thu Dec 13, 2018 11:38 am
Hi all,

My engine is currently single-threaded, and does ok when I search to some fixed depth, or when I wait for a complete Iterative Deepening search to complete. However, if I try to interrupt my search in the middle of a PVS, then my program starts returning completely crazy moves, and it becomes terrible.

Have you implemented something to interrupt your search in the middle of PVS? If so, what do you return? Do you return eval? Alpha? Drop into Qsearch?

Thanks kindly in advance,
Louis
This thread gives some advice for this
http://talkchess.com/forum3/viewtopic.p ... +iteration
Current foe list count : [92]
http://rwbc-chess.de/chronology.htm

AxolotlFever
Posts: 50
Joined: Sun Nov 11, 2018 8:26 pm
Location: Germany
Full name: Louis Mackenzie-Smith
Contact:

Re: out of time in PVS

Post by AxolotlFever » Thu Dec 13, 2018 12:01 pm

Hi there Guether,

Thansk very much for this link, it is very useful!

Kind regs,
Louis

Henk
Posts: 5797
Joined: Mon May 27, 2013 8:31 am

Re: out of time in PVS

Post by Henk » Thu Dec 13, 2018 12:13 pm

Easiest but inefficient is just clear the line and use previous line which did finish.

[if you do iterative deepening and are researching move from previous iteration first, you can do some optimizations on (ply) depth = 0 for on ply depth = 0 each move searched gives added value. But at this moment doing position analysis with my engine fails so I might have a similar bug]

Ras
Posts: 1140
Joined: Tue Aug 30, 2016 6:19 pm
Contact:

Re: out of time in PVS

Post by Ras » Thu Dec 13, 2018 4:39 pm

You can add something like this in the loop that iterates over the moves in your search recursion:

Code: Select all

if (time_is_up != TM_NO_TIMEOUT)
    return a;

    if (t > a)
    {
        a = t;
        *best_move_index = i;
        
    ...
That makes sure that in case of timeout, no nonsense moves can raise alpha. In your main iterative deepening move, you check whether you get any move at all. This may fail if the timeout occured during the search of the first root move. In this case, you take the line from the depth iteration before. Otherwise, at least the first move has been searched, and you can take the PV. This relies on moving the best move to the top of the root list after every iteration.
Rasmus Althoff
https://www.ct800.net

elcabesa
Posts: 806
Joined: Sun May 23, 2010 11:32 am
Contact:

Re: out of time in PVS

Post by elcabesa » Thu Dec 13, 2018 6:28 pm

One usually stop the PVS search and use the result of the previous finished iterative deepening result.
Remember that after you decide to stop the search you have also to stop saving killers, sving info to transposition tables and so on.

AlvaroBegue
Posts: 919
Joined: Tue Mar 09, 2010 2:46 pm
Location: New York
Full name: Álvaro Begué (RuyDos)

Re: out of time in PVS

Post by AlvaroBegue » Thu Dec 13, 2018 7:39 pm

Here's what I do: Whenever I find a move that becomes the best move at the root, I move it to the top of the list. At the end, I just return the top move. This handles aborted searches very naturally.

Code: Select all

Move search_root(Board const &board) {
  std::vector<Move> moves = board.generate_moves();
  
  try {
    for (int depth = 1; !out_of_time(); ++depth) {
      int alpha = -Infinity;
      for (size_t i = 0; i < moves.size(); ++i) {
        // Here you do the usual make_move, PVS search, yadda, yadda, yadda
        if (score > alpha) {
          alpha = score;
          std::rotate(moves, moves + i, moves + i + 1); // Move the best move to the top of the list
          // print some info about the best move and PV
        }
      }
    }
  }
  catch (...) {
    // I use an exception from the middle of the search if I run out of time or the GUI asks me to stop, and I catch it here
  }
  
  return moves[0]; // No matter how we got out of the loop, this is the best move we've found so far.
}


RubiChess
Posts: 105
Joined: Fri Mar 30, 2018 5:20 am

Re: out of time in PVS

Post by RubiChess » Fri Dec 14, 2018 6:31 pm

I return alpha immediately without storing to TT.
This should just throw away all unfinished searches.

Andreas

Sven
Posts: 3822
Joined: Thu May 15, 2008 7:57 pm
Location: Berlin, Germany
Full name: Sven Schüle
Contact:

Re: out of time in PVS

Post by Sven » Sat Dec 15, 2018 12:15 am

RubiChess wrote:
Fri Dec 14, 2018 6:31 pm
I return alpha immediately without storing to TT.
This should just throw away all unfinished searches.
Do you also use a flag indicating that the search is being stopped? If you don't then just returning alpha on detecting a timeout might be wrong since the direct parent node negates the score and performs a beta cutoff but then the parent's parent just continues with the next move after noticing that its current move has been refuted.
Sven Schüle (engine author: Jumbo, KnockOut, Surprise)

RubiChess
Posts: 105
Joined: Fri Mar 30, 2018 5:20 am

Re: out of time in PVS

Post by RubiChess » Sat Dec 15, 2018 6:56 am

Sven wrote:
Sat Dec 15, 2018 12:15 am
RubiChess wrote:
Fri Dec 14, 2018 6:31 pm
I return alpha immediately without storing to TT.
This should just throw away all unfinished searches.
Do you also use a flag indicating that the search is being stopped? If you don't then just returning alpha on detecting a timeout might be wrong since the direct parent node negates the score and performs a beta cutoff but then the parent's parent just continues with the next move after noticing that its current move has been refuted.
Yes, I have a global flag "IMMEDIATESTOP" that lets every parent node just return its alpha.

Post Reply