Iterative deepening question

[Luis Babboni]

Hi.

Actually I understood the more common way used to search is iterative deepening (ID)
If I understood right, ID do a search to deep 1 using alphabeta, later a search to deep 2 using alpha beta and so on.
One of the advantage of the ID seems to be the possibilitie to use the previous deep search to decide the order of the moves in wich start the actual deep search.

I understood correctly till here?

If I understood right, my question is that using alpha beta for previous deep, you will do not have the complete tree to determine wich line es better to start actual deep search.
I could start for the best line in the previous deep, but how to use the second best line in previous deep to start search in actual deep if I´m not sure that this second best line was found in previous deep?

Being the complete tree till previous deep of around the 10% of the total tree till actual deep, I could evaluate all moves till previous deep instead of just what alpha beta needs.... but in this case, could be doing fast the ordering of all those moves?
And I´m not sure that the complete tree for previous deep is just 10% of the alpha beta tree till actual deep.

Thanks and sorry for the stupid questions or nonsense I could made

[bob]

Hi.

Actually I understood the more common way used to search is iterative deepening (ID)
If I understood right, ID do a search to deep 1 using alphabeta, later a search to deep 2 using alpha beta and so on.
One of the advantage of the ID seems to be the possibilitie to use the previous deep search to decide the order of the moves in wich start the actual deep search.

I understood correctly till here?

yes... In fact that is the primary reason for using iterative deepening, it is faster to go 1, 2, ..., n than to just start at n. Plus you have an easier way to deal with running out of time.

If I understood right, my question is that using alpha beta for previous deep, you will do not have the complete tree to determine wich line es better to start actual deep search.
I could start for the best line in the previous deep, but how to use the second best line in previous deep to start search in actual deep if I´m not sure that this second best line was found in previous deep?

Being the complete tree till previous deep of around the 10% of the total tree till actual deep, I could evaluate all moves till previous deep instead of just what alpha beta needs.... but in this case, could be doing fast the ordering of all those moves?
And I´m not sure that the complete tree for previous deep is just 10% of the alpha beta tree till actual deep.

Thanks and sorry for the stupid questions or nonsense I could made

You don't need the "second best." At iteration N+1 all you need to do is search the best move from iteration N first (this means the best move at ply=1, best move at ply=2, ..., best move at ply=N-1) first. For the very last ply you likely won't have a best move, but you have all the earlier plies ordered correctly.

All alpha/beta needs is the best (or a good) move ordered first. The second, third, etc moves are irrelevant as to the order they are searched.

[Luis Babboni]

Thanks bob!

Good news!

But still some doubts.

1st:
You said "...the best move at ply=1, best move at ply=2, ..., best move at ply=N-1..."
For ply N what I need is not just the best move at ply N-1?
Cause the best move for ply k<N fall not necesarily into the same line that the best for ply N. I agree that you need best move for ply 2 to start search ply 3, but later you will do not need best move for ply 2 anymore..... or I´m wrong?

2nd:
I understood that the second best move could be useful cause I read a lot of times that is better to search some kind of moves first like promotions, captures etc.... and I understood the ID allow you to, instead of look first for that´s kind of moves, use the second best move for ply N-1; following by the 3rd best move for ply N-1; etc.
You suggest to look first for best move of ply N-1 following by promotions; captures; etc?
Or what I´m understanding wrongly?

[AlvaroBegue]

English nitpick: You have "questions", not "doubts" (aunque en español sean "dudas").

1: You just need to remember the best move from the previous iteration.

2: The second move matters only if the first move turns out not to be the best. So this matters a lot less than the first move, and Bob was simplifying when he said it doesn't matter.

I use a very simple method: Keep a list of moves from iteration to iteration, and whenever a new best move is found, move it to the top of the list.

Code: Select all

Move search_root(Board &board) {
  Move moves[256];
  int n_moves = board.generate_moves(moves);
  
  for (int depth = 1; enough_time_for_another_iteration(); ++depth) {
    int best_score = -Infinity;
    for &#40;int i = 0; i < n_moves; ++i&#41; &#123;
      board.make_move&#40;moves&#91;i&#93;);
      int value = -negamax&#40;board, -Infinity, -best_score, depth - 1&#41;;
      board.undo_move&#40;);
      if &#40;value > best_score&#41; &#123;
        best_score = value;
        std&#58;&#58;rotate&#40;moves, moves + i, moves + i + 1&#41;; // <-- This does the magic!
      &#125;
    &#125;
  &#125;
  
  return moves&#91;0&#93;;
&#125;

[Luis Babboni]

Gracias Álvaro!

Sigo con questions!

And how to know wich is the second best move of ply N-1?

I try to make my question in different way helping my poor english with an image:



My question is:
How to decide from wich Ply4 node continue after end with nodes into the oval?
If I know wich is the second best node in Ply4, is easy to choice it to continue.... but I´m afraid I haven´t it.... so I must decide between nodes into the rectangle using heuristic choice like promotions first following by captures; etc?
Or simply use the DFS algorithm and continue with lefter node into the rectangle?

I think my question could be so obviously for all you so that´s why I can´t make you understand me.... plus my bad english

Or may be the thing is worst.... you understood me and what happens is that I do not understood your answers!

[stegemma]

English nitpick: You have "questions", not "doubts" (aunque en español sean "dudas").

1: You just need to remember the best move from the previous iteration.

2: The second move matters only if the first move turns out not to be the best. So this matters a lot less than the first move, and Bob was simplifying when he said it doesn't matter.

I use a very simple method: Keep a list of moves from iteration to iteration, and whenever a new best move is found, move it to the top of the list.

Code: Select all

Move search_root(Board &board) {
  Move moves[256];
  int n_moves = board.generate_moves(moves);
  
  for (int depth = 1; enough_time_for_another_iteration(); ++depth) {
    int best_score = -Infinity;
    for &#40;int i = 0; i < n_moves; ++i&#41; &#123;
      board.make_move&#40;moves&#91;i&#93;);
      int value = -negamax&#40;board, -Infinity, -best_score, depth - 1&#41;;
      board.undo_move&#40;);
      if &#40;value > best_score&#41; &#123;
        best_score = value;
        std&#58;&#58;rotate&#40;moves, moves + i, moves + i + 1&#41;; // <-- This does the magic!
      &#125;
    &#125;
  &#125;
  
  return moves&#91;0&#93;;
&#125;

Maybe would be enough to sort moves after the end of the for(i) loop.

[stegemma]

You apply iterative deepening only on the root node (ply N). If you apply ID to intermediate nodes, it is called "internal iterative deepening", i think. I used that method but it was slower than teh simple one, with ID at the root.

[Luis Babboni]

You apply iterative deepening only on the root node (ply N). If you apply ID to intermediate nodes, it is called "internal iterative deepening", i think. I used that method but it was slower than teh simple one, with ID at the root.

Thanks Stefano, but I do not understand you.

Wich is the root node?
In my image.... is best node of ply 4?
I think ID as an aplication on the tree, not on the node....
May be there is something in the basic I´m missunderstanding

[Luis Babboni]

Mmmmm....
here it seems to say exactly what you said Stefano:
https://chessprogramming.wikispaces.com ... +Deepening
...
And I do not understood it for the moment.
So please excuse me, it seems I need more reading yet.

[stegemma]

Mmmmm....
here it seems to say exactly what you said Stefano:
https://chessprogramming.wikispaces.com ... +Deepening
...
And I do not understood it for the moment.
So please excuse me, it seems I need more reading yet.

No problem, I try to explain. The root node is the top of the tree, in your drawing; it is the position where you start thinking. At the root you apply ID, calling alphabeta for any move. In alphabeta itself you don't do ID, simply you sort moves based on the expected value. In fact, you should have two similar loops:

- one for the moves at the root (with ID)
- one for moves in deeper nodes (in alphabeta)

PS: "Babboni" looks like an italian surname, it isn't?