Unclear pruning

[metax]

I just found the following line in https://chessprogramming.wikispaces.com/Pruning:

Returning Alpha
likely at expected All-Nodes:

* after trying width[ply] moves in Shannon Type-B programs, return alpha

What does that mean? What is width[ply], and is the idea good in your opinion?

[Harald]

I just found the following line in https://chessprogramming.wikispaces.com/Pruning:

Returning Alpha
likely at expected All-Nodes:

* after trying width[ply] moves in Shannon Type-B programs, return alpha

What does that mean? What is width[ply], and is the idea good in your opinion?

Let me guess:

We are at an all node. That means
- we do not expect to find a move with a score >= beta.
- we try all moves in case we are wrong and lucky.

Shannon B means a selective searching algorithm. We assume the
move order is very good.

alpha is during the search and at each position the best score we could
get so far. If there is a move better than alpha then alpha is set to
the move's score in the position where this happens.

width[ply] may be a constant for all plies or a function of plies. Perhaps
width[0] = 20; width[1] = 19; ...; width[15] = 5; ...; width[250] = 5;

Now when we are at an all node position somewhere ply deep in the search tree
and there are M possible moves to try and width[ply] = W and W < M,
then we only try the first W moves in that position. All remaining moves
are not tried. Not even with a reduced depth. They are pruned.
That is ok as long as we believe that the remaining moves have an even
less probability for a good score >= beta.

I don't think this idea is good. It is too static and independent of the
position. It does not look how far alpha is away from beta or if the first
moves are captures or if we are in check or how big is W/M or ...
Pruning is a hard decision compared to depth reduction.

There is a related and better alternative with a similar idea.
Look for late move reductions LMR. That typically deals with all the
critical points and seems to be very effective in many programs.

Harald

[Gerd Isenberg]

I just found the following line in https://chessprogramming.wikispaces.com/Pruning:

Returning Alpha
likely at expected All-Nodes:

* after trying width[ply] moves in Shannon Type-B programs, return alpha

What does that mean? What is width[ply], and is the idea good in your opinion?

Yes, Shannon type B programs until the 70ties or so used to have width per ply, see Kotok-McCarthy-Program {4, 3, 2, 2, 1, 1, 1, 1, 0, 0} or Mac Hack IV with {15, 15, 9, 9, 7, ...}. Chess 3.6 was also Shannon type B, until Chess 4 performed the paradigm shift.

[bob]

I just found the following line in https://chessprogramming.wikispaces.com/Pruning:

Returning Alpha
likely at expected All-Nodes:

* after trying width[ply] moves in Shannon Type-B programs, return alpha

What does that mean? What is width[ply], and is the idea good in your opinion?

Width[ply] was an idea from Greenblatt's program. You choose some number of moves to search normally. If there are more moves than this, you can prune the remainder. The bigger a value in width[ply] is, the less you prune. Normally values for shallow plys are big, values for deep plies are small. I don't know if anyone uses something like this today.