Number of moves displayed are from cuted or uncuted tree?

[Luis Babboni]

Sorry if my question has no sense cause I missunderstood something, I´m completely new in this.

As far as I understood, for searching for the best move, yo do not need to search all moves using minimax, you could use alphabeta, that is a kind of cut over the "minimax tree", and just search over it.
So, as far as I understood, you need to store just the "alphabeta tree" that is smaller than the "minimax tree".

And my question if I understood right is:
The number of moves studied that engines use to show to the GUI, are the moves the "minimax tree" have or the moves the "alphabeta tree" has?
I think are the "minimax tree" moves, but not sure.... in fact, as I said, I´m not sure if I am understanding the matter or not.

Thanks.

[Aleks Peshkov]

There is no way to know exact minimax and even alpha-beta tree size. Engines show numbers of nodes (positions) that they actually visited during search. This number is typically much smaller then equivalent alpha-beta tree.

[Luis Babboni]

Thanks Aleks!!

[Michael Sherwin]

Also you say 'store the tree'. Whole trees are not stored during alpha/beta searching. Only the current branch/path is stored in a 'last in first out' type stack.

[Luis Babboni]

Also you say 'store the tree'. Whole trees are not stored during alpha/beta searching. Only the current branch/path is stored in a 'last in first out' type stack.

Mmm... that´s was still beyond my knowledge.... but as preview.... that´s means you do not need to have tons of bytes for store moves with its scores before decide wich to choice?

Thanks Michael!

[zullil]

Also you say 'store the tree'. Whole trees are not stored during alpha/beta searching. Only the current branch/path is stored in a 'last in first out' type stack.

Mmm... that´s was still beyond my knowledge.... but as preview.... that´s means you do not need to have tons of bytes for store moves with its scores before decide wich to choice?

Thanks Michael!

Right. Basically, you "walk" through the tree, and simply keep track of alpha and beta values. These values tell you how good the current position is, and also allow you to modify your walk, by telling you which sections of the tree you can safely ignore (prune). Of course, you can keep track of more info if you wish.

[Luis Babboni]

I thought a little more about it (I´m still in te moves generator but may be can help me to understood what follow to choice a better way to do the previous things).

Is this then the way you must do?:

-Decide how many time you will give to the next move as maximum.
-Calculate aproximately how many deepth levels/numebr of nodes you could evaluate in this time in agree with your know of your engine speed.
-If you do not find nothing too important, stop at the level you calculate before and before change to next path, store actual path just if is better than any previous one, if not you dicard it cause you will not need to continue this path in this move search evaluation (you could store it anyway to use it in any next move, but is another story).
-If you found something very important before the time you calculated is reached, you could stop searching.
-If the time you cacluated is reached and you are not ina very interesting point, you must stop search. If your evaluation of the speed of your engine is accurate, you could not be as far of the numbers of studied nodes/leves you calculated before.

[hgm]

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.

[Luis Babboni]

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?

[Luis Babboni]

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...