Number of moves displayed are from cuted or uncuted tree?

[zullil]

Not really. It is difficult to predict in advance how long a search of a certain depth will take. You can easily be wrong by a factor 1000 or more.

So what engines do is just increase the depth in steps of 1 ply, starting with a 1-ply search, then a 2-ply search etc. When time runs out, you can then abort the search in progress (usually meaning it doesn't produce anything you can use), and play the move of the last search that you were able to finish. If you wantto do it a bit smarter, you can refrain from starting searches that you will almost certainly not be able to finish. E.g. if you have 15 sec/move, and doing all searches upto 11 ply took you 13 sec, it seems unrealistic the 12-ply search, which would be next, could be done in under 2 sec. So you could better just play the move the 11-ply search came up with, and save the 2 sec for some later move.

Mmmm.... now I do not understood then...

To increase the depth I must have all previous tree stored... or I´m wrong?

There is no reason to "store" the tree. Your move generator determines all the edges from a node, and your make/unmake lets you move along edges. No need to maintain storage of a global tree structure.

[bob]

Not really. It is difficult to predict in advance how long a search of a certain depth will take. You can easily be wrong by a factor 1000 or more.

So what engines do is just increase the depth in steps of 1 ply, starting with a 1-ply search, then a 2-ply search etc. When time runs out, you can then abort the search in progress (usually meaning it doesn't produce anything you can use), and play the move of the last search that you were able to finish. If you wantto do it a bit smarter, you can refrain from starting searches that you will almost certainly not be able to finish. E.g. if you have 15 sec/move, and doing all searches upto 11 ply took you 13 sec, it seems unrealistic the 12-ply search, which would be next, could be done in under 2 sec. So you could better just play the move the 11-ply search came up with, and save the 2 sec for some later move.

Mmmm.... now I do not understood then...

To increase the depth I must have all previous tree stored... or I´m wrong?

There is no reason to "store" the tree. Your move generator determines all the edges from a node, and your make/unmake lets you move along edges. No need to maintain storage of a global tree structure.

You DO sort of store the tree. That's what the transposition/refutation table is all about. Without that, iterated search would be much less effective than it is today.

[hgm]

Mmm..... if the time takes to generate the moves is insignificant compared with evaluation time, you could build all the tree again evaluating now just the new ply .... but I do not think is the case...

Actually this is usually the case, when you have a non-trivial evaluation. If you have a transposition table that is nice, and it saves you some time. But it isn't really essential. You can already get a quite reasonable engine when the only thing you remember from a previous iteration is the PV branch.

Normally each subsequent iteration lasts 3-4 times longer than the previous one. So regenerating the part of the tree that you walked before is only 25% of the search (as opposed to evaluation) time. Even if the previous iteration would not help speeding up the next one at all (because you do not use any information from it) it would be helpful to do it, just as an 'insurance': it means you have a pretty good move to play when you cannot finish the next iteration. And it costs you only ~25% of the available time to take that insurance. While if you don't take it, you will several times during a game get in a situation where you will either forfeit on time (because your iteration will finish only after your time is up) or have to abort the iteration and play a random move. (Basically meaning that you will lose every game, no matter how strong your engine plays when it can finish its search.) Of course anything that you could learn from the previous iteration, which would help accelerating the next one, could be profited from.

Micro-Max 1.6 does iterative deepening without learning anything from the previous iteration, other than how long it took.

[Sven]

Mmm..... if the time takes to generate the moves is insignificant compared with evaluation time, you could build all the tree again evaluating now just the new ply .... but I do not think is the case...

A typical implementation of tree search works "almost" like this: you maintain one board object and initialize it appropriately (to the initial chess position, or a position given externally e.g. by an FEN string). Then you walk through the tree of positions by
a) generating all legal moves at the current position and ordering them in a "clever" way,
b) looping over all of these moves by
- making each one (thus modifying the board),
- calling the search recursively,
- unmaking the move (modifying the board back), and
- comparing the score returned from recursion to the best score found so far, since you need to keep track of the best score and (at least at the root) the best move.

Recursion terminates at a given search depth where, instead of generating all moves again, you either return the result of your static evaluation function (the most simple approach) or the result of a quiescence search (the better approach where only captures are searched until no interesting capture is left, then static eval is returned).

Most programs also do "iterative deepening" starting with a search depth of 1, then 2, 3 and so on until time is up, while always starting to search the principle variation of the previous iteration first. As already pointed out by Bob, this will become even more effective when adding a transposition table, but even without it you get the advantage of using the available time much better than you would do by "guessing" in advance how deep you might be able to search, and then doing a very incomplete search most of the time (or not searching deep enough).

Recursion uses the normal system stack. There the current search path from the root node to the current node is stored along with scoring information and the whole move list of each node on that path. So searching 10 plies deep requires storage for the board plus 10 move lists plus 10 moves + some integers etc., not much more (when considering requirements of the search itself).

In the beginning I wrote "almost" since many important details are left out, of course. You will find out later. The algorithm sketched above is basically Minimax, or Negamax in its enhanced form. Actually AlphaBeta is used by almost all chess programs since more than 40 years, reducing the overall tree size roughly from N^depth to N^(depth/2) in the best case of perfect move ordering. You can read a lot about all of that in the section about search in the Chess Programming Wiki, just search for Depth-First Search. Start reading there before you try advanced stuff like transposition tables.

[Luis Babboni]

Thanks guys! I´m reading you