Iterative deepening

Quote:

Original post by alvaro One would keep the moves at the root sorted, at least so the best move found so far is always the first one. Then you simply return the first move, regardless of whether the depth-6 search was completed or not. Does that answer your question?

Quote:

Original post by crypto_rsa Quote: Original post by alvaro One would keep the moves at the root sorted, at least so the best move found so far is always the first one. Then you simply return the first move, regardless of whether the depth-6 search was completed or not. Does that answer your question? Well, it sorts the moves at the beginning of each iteration based on the results stored in a transposition table (which are likely to come from the last completed iteration), but the order based on deeper results may be different.

Quote:

Yes, the best move from depth-5 search is the first one but that does not guarantee it will be the best one in depth-6 search as well.

Move think(Position P) {  vector<Move> moves = generate_moves(P);  for(int depth=1; enough_time_left(); ++depth) {    double best_score = -infinity;    for(unsigned i=0; i<moves.size(); ++i) {      double score = alphabeta(apply_move(P, moves), -infinity, -best_score, depth-1);      if(search_interrupted_because_of_timeout())        break;      if(score>best_score) {        score = best_score;        // Move the new best move to the beginning of the list        std::rotate(moves.begin(), moves.begin()+i, moves.begin()+i+1);      }    }  }    return moves[0];}

Quote:

Original post by alvaro Quote: Original post by crypto_rsa Quote: Original post by alvaro One would keep the moves at the root sorted, at least so the best move found so far is always the first one. Then you simply return the first move, regardless of whether the depth-6 search was completed or not. Does that answer your question? Well, it sorts the moves at the beginning of each iteration based on the results stored in a transposition table (which are likely to come from the last completed iteration), but the order based on deeper results may be different. Typically you wouldn't use the transposition table for this. I'll post some pseudo-code below.

Quote:

Quote: Yes, the best move from depth-5 search is the first one but that does not guarantee it will be the best one in depth-6 search as well. Of course not. The point is that it is safe to interrupt depth 6 at any point, and you will get a move that is no worse than the move that was best at depth 5. If you don't get the same move as you got in depth 5, it's because the new move has a better score in depth 6. Here's some pseudo-code (of the C++ variety): Move think(Position P) { vector<Move> moves = generate_moves(P); for(int depth=1; enough_time_left(); ++depth) { double best_score = -infinity; for(unsigned i=0; i<moves.size(); ++i) { double score = alphabeta(apply_move(P, moves), -infinity, -best_score, depth-1); if(search_interrupted_because_of_timeout()) break; if(score>best_score) { score = best_score; // Move the new best move to the beginning of the list std::rotate(moves.begin(), moves.begin()+i, moves.begin()+i+1); } } } return moves[0];}

Quote:

Original post by crypto_rsa I use the TT for storing evaluations (and thus sorting the move list) in the whole game tree, not just at the root node.

Quote:

The point is that it is safe to interrupt depth 6 at any point, and you will get a move that is no worse than the move that was best at depth 5. If you don't get the same move as you got in depth 5, it's because the new move has a better score in depth 6. Here's some pseudo-code (of the C++ variety): Move think(Position P) { vector<Move> moves = generate_moves(P); for(int depth=1; enough_time_left(); ++depth) { double best_score = -infinity; for(unsigned i=0; i<moves.size(); ++i) { double score = alphabeta(apply_move(P, moves), -infinity, -best_score, depth-1); if(search_interrupted_because_of_timeout()) break; if(score>best_score) { score = best_score; // Move the new best move to the beginning of the list std::rotate(moves.begin(), moves.begin()+i, moves.begin()+i+1); } } } return moves[0];}

Quote:

Original post by crypto_rsa One more thing. You seem to be using the best result from the previous iteration as the lower bound in the next iteration. Is this safe? I think the evaluation function would have to be monotone or something. You can get e. g. evaluation 150 for depth 3 (for move A), then you sort the moves, next you begin searching to depth 4 but the correct (best) evaluation for this depth is 100 (move B). When using 150 as the lower bound, you won't discover move B as being the best one. Or am I wrong?

Quote:

Original post by alvaro Quote: Original post by crypto_rsa One more thing. You seem to be using the best result from the previous iteration as the lower bound in the next iteration. Is this safe? I think the evaluation function would have to be monotone or something. You can get e. g. evaluation 150 for depth 3 (for move A), then you sort the moves, next you begin searching to depth 4 but the correct (best) evaluation for this depth is 100 (move B). When using 150 as the lower bound, you won't discover move B as being the best one. Or am I wrong? You didn't read my pseudo-code correctly. best_score is initialized to -infinity every time we start searching a new depth.