Botvinnik Markov revisited

[jwes]

There are only two types of pruning in the alpha/beta framework. The first is called "backward pruning" and is the basic alpha/beta pruning mechanism. The second is forward pruning, where you generate a set of moves, and then say "these will be searched and these are going to be tossed out." IE the shannon type-B strategy.

What would you call pruning where you search some move sufficiently to decide it is a stupid move rather than a sacrifice and then mark it so that on future iterations you do not search it again?

That's the kind of pruning I am talking about, a move that is permanently marked as "never play". But it's STILL called forward pruning.

I would also call it a bad idea. Do any programs do this?

You can never be sure that a move that looks really bad actually is a very good move and a scalable program should never say never, although it's correct to give them much less consideration. But on a future iteration it should be possible to discover anything.

If the score is perfect, of course this does not apply because we need not search perfect moves, such as moves that reference an endgame database or simple ending that can be marked as a draw.

I think that sometimes you can be sure a move is bad, particularly in endgames.
Consider this position. How many ply do you need to analyze before you are sure a6 is a bad move? A human would never even consider this move.
[d]6k1/p4ppp/1p6/1P6/P7/8/6PP/6K1 b - - 0 1

[Dann Corbit]

There are only two types of pruning in the alpha/beta framework. The first is called "backward pruning" and is the basic alpha/beta pruning mechanism. The second is forward pruning, where you generate a set of moves, and then say "these will be searched and these are going to be tossed out." IE the shannon type-B strategy.

What would you call pruning where you search some move sufficiently to decide it is a stupid move rather than a sacrifice and then mark it so that on future iterations you do not search it again?

That's the kind of pruning I am talking about, a move that is permanently marked as "never play". But it's STILL called forward pruning.

I would also call it a bad idea. Do any programs do this?

You can never be sure that a move that looks really bad actually is a very good move and a scalable program should never say never, although it's correct to give them much less consideration. But on a future iteration it should be possible to discover anything.

If the score is perfect, of course this does not apply because we need not search perfect moves, such as moves that reference an endgame database or simple ending that can be marked as a draw.

I think that sometimes you can be sure a move is bad, particularly in endgames.
Consider this position. How many ply do you need to analyze before you are sure a6 is a bad move? A human would never even consider this move.
[d]6k1/p4ppp/1p6/1P6/P7/8/6PP/6K1 b - - 0 1

I guess that by "unstoppable passed pawn" evaluation rule, most programs will find it in one ply.

[jwes]

There are only two types of pruning in the alpha/beta framework. The first is called "backward pruning" and is the basic alpha/beta pruning mechanism. The second is forward pruning, where you generate a set of moves, and then say "these will be searched and these are going to be tossed out." IE the shannon type-B strategy.

What would you call pruning where you search some move sufficiently to decide it is a stupid move rather than a sacrifice and then mark it so that on future iterations you do not search it again?

That's the kind of pruning I am talking about, a move that is permanently marked as "never play". But it's STILL called forward pruning.

I would also call it a bad idea. Do any programs do this?

You can never be sure that a move that looks really bad actually is a very good move and a scalable program should never say never, although it's correct to give them much less consideration. But on a future iteration it should be possible to discover anything.

If the score is perfect, of course this does not apply because we need not search perfect moves, such as moves that reference an endgame database or simple ending that can be marked as a draw.

I think that sometimes you can be sure a move is bad, particularly in endgames.
Consider this position. How many ply do you need to analyze before you are sure a6 is a bad move? A human would never even consider this move.
[d]6k1/p4ppp/1p6/1P6/P7/8/6PP/6K1 b - - 0 1

I guess that by "unstoppable passed pawn" evaluation rule, most programs will find it in one ply.

I meant a bad enough move that you will prune it.

[Don]

There are only two types of pruning in the alpha/beta framework. The first is called "backward pruning" and is the basic alpha/beta pruning mechanism. The second is forward pruning, where you generate a set of moves, and then say "these will be searched and these are going to be tossed out." IE the shannon type-B strategy.

What would you call pruning where you search some move sufficiently to decide it is a stupid move rather than a sacrifice and then mark it so that on future iterations you do not search it again?

That's the kind of pruning I am talking about, a move that is permanently marked as "never play". But it's STILL called forward pruning.

I would also call it a bad idea. Do any programs do this?

You can never be sure that a move that looks really bad actually is a very good move and a scalable program should never say never, although it's correct to give them much less consideration. But on a future iteration it should be possible to discover anything.

If the score is perfect, of course this does not apply because we need not search perfect moves, such as moves that reference an endgame database or simple ending that can be marked as a draw.

I think that sometimes you can be sure a move is bad, particularly in endgames.
Consider this position. How many ply do you need to analyze before you are sure a6 is a bad move? A human would never even consider this move.

I'm not sure we are talking about the same thing.

What I'm talking about is hard core pruning without any additional consideration ever - in a practical chess playing program.

Yes, you can construct positions like this where it's obvious that a6 is wrong, but I don't believe you can actually put this into a heuristic that can be applied to a chess program with 100 percent accuracy. If you can, then please tell me what it is?

What rule that is 100% correct will also tell you not to play a6 in this position?

I think if you try to produce such a rule, you will understand what I am saying.

[d]6k1/p4ppp/1p6/1P6/P7/8/6PP/6K1 b - - 0 1

[Dann Corbit]

There are only two types of pruning in the alpha/beta framework. The first is called "backward pruning" and is the basic alpha/beta pruning mechanism. The second is forward pruning, where you generate a set of moves, and then say "these will be searched and these are going to be tossed out." IE the shannon type-B strategy.

What would you call pruning where you search some move sufficiently to decide it is a stupid move rather than a sacrifice and then mark it so that on future iterations you do not search it again?

That's the kind of pruning I am talking about, a move that is permanently marked as "never play". But it's STILL called forward pruning.

I would also call it a bad idea. Do any programs do this?

You can never be sure that a move that looks really bad actually is a very good move and a scalable program should never say never, although it's correct to give them much less consideration. But on a future iteration it should be possible to discover anything.

If the score is perfect, of course this does not apply because we need not search perfect moves, such as moves that reference an endgame database or simple ending that can be marked as a draw.

I think that sometimes you can be sure a move is bad, particularly in endgames.
Consider this position. How many ply do you need to analyze before you are sure a6 is a bad move? A human would never even consider this move.

I'm not sure we are talking about the same thing.

What I'm talking about is hard core pruning without any additional consideration ever - in a practical chess playing program.

Yes, you can construct positions like this where it's obvious that a6 is wrong, but I don't believe you can actually put this into a heuristic that can be applied to a chess program with 100 percent accuracy. If you can, then please tell me what it is?

What rule that is 100% correct will also tell you not to play a6 in this position?

I think if you try to produce such a rule, you will understand what I am saying.

[d]6k1/p4ppp/1p6/1P6/P7/8/6PP/6K1 b - - 0 1

It is possible to do this if you have a precalculation engine that computes based upon board configurations and bitmaps.

For instance, in this configuration, it will know (having precalculated) that the pawn race is lost. Therefore, the move is known a-priori as lost.

This is done by a program generator that performs incremental evaluations as a function of chessmen remaining on the board and has precomputed pawn race distances etc. already calculated.

For every combination of chessmen, there is a different move generator. Of course, this is impossibly tedious. That is why a function generator program is needed.

So, for instance, if the generated program list consumes 10 GB of source code it matters little because you did not have to write it -- you only had to write the function that writes the functions. (Of course, you are thinking about spilling the instruction cache by switching all these functions. But the functions change somewhat slowly over time because a program will not instantly go from 32 chessmen down to 4).

[jwes]

There are only two types of pruning in the alpha/beta framework. The first is called "backward pruning" and is the basic alpha/beta pruning mechanism. The second is forward pruning, where you generate a set of moves, and then say "these will be searched and these are going to be tossed out." IE the shannon type-B strategy.

What would you call pruning where you search some move sufficiently to decide it is a stupid move rather than a sacrifice and then mark it so that on future iterations you do not search it again?

That's the kind of pruning I am talking about, a move that is permanently marked as "never play". But it's STILL called forward pruning.

I would also call it a bad idea. Do any programs do this?

You can never be sure that a move that looks really bad actually is a very good move and a scalable program should never say never, although it's correct to give them much less consideration. But on a future iteration it should be possible to discover anything.

If the score is perfect, of course this does not apply because we need not search perfect moves, such as moves that reference an endgame database or simple ending that can be marked as a draw.

I think that sometimes you can be sure a move is bad, particularly in endgames.
Consider this position. How many ply do you need to analyze before you are sure a6 is a bad move? A human would never even consider this move.

I'm not sure we are talking about the same thing.

What I'm talking about is hard core pruning without any additional consideration ever - in a practical chess playing program.

Yes, you can construct positions like this where it's obvious that a6 is wrong, but I don't believe you can actually put this into a heuristic that can be applied to a chess program with 100 percent accuracy. If you can, then please tell me what it is?

What rule that is 100% correct will also tell you not to play a6 in this position?

I think if you try to produce such a rule, you will understand what I am saying.

How about this? In a Q+pawns vs pawns endgame, if the side with only pawns has no pawn past the 5th rank, a 3 ply search is enough to determine if the position is completely won or only probably won.

[Uri Blass]

There are only two types of pruning in the alpha/beta framework. The first is called "backward pruning" and is the basic alpha/beta pruning mechanism. The second is forward pruning, where you generate a set of moves, and then say "these will be searched and these are going to be tossed out." IE the shannon type-B strategy.

What would you call pruning where you search some move sufficiently to decide it is a stupid move rather than a sacrifice and then mark it so that on future iterations you do not search it again?

That's the kind of pruning I am talking about, a move that is permanently marked as "never play". But it's STILL called forward pruning.

I would also call it a bad idea. Do any programs do this?

You can never be sure that a move that looks really bad actually is a very good move and a scalable program should never say never, although it's correct to give them much less consideration. But on a future iteration it should be possible to discover anything.

If the score is perfect, of course this does not apply because we need not search perfect moves, such as moves that reference an endgame database or simple ending that can be marked as a draw.

I think that sometimes you can be sure a move is bad, particularly in endgames.
Consider this position. How many ply do you need to analyze before you are sure a6 is a bad move? A human would never even consider this move.

I'm not sure we are talking about the same thing.

What I'm talking about is hard core pruning without any additional consideration ever - in a practical chess playing program.

Yes, you can construct positions like this where it's obvious that a6 is wrong, but I don't believe you can actually put this into a heuristic that can be applied to a chess program with 100 percent accuracy. If you can, then please tell me what it is?

What rule that is 100% correct will also tell you not to play a6 in this position?

I think if you try to produce such a rule, you will understand what I am saying.

[d]6k1/p4ppp/1p6/1P6/P7/8/6PP/6K1 b - - 0 1

I can suggest the following rule(it may be improved but I think that it is practically 100% correct):

In pawn endgames
A move that allows the opponent to get an unstoppable pawns in the 6th rank or in the 7th rank
when the most advanced pawn of the opponent needs at least 3 more moves for promotion is a losing move(I do not care about the case that it is the best losing move).

unstoppable pawn in this definition means that the opponent king cannot get to the square of the pawn in the next move and the pawn path is not blocked by the friendly king.

Uri

[Uri Blass]

There are only two types of pruning in the alpha/beta framework. The first is called "backward pruning" and is the basic alpha/beta pruning mechanism. The second is forward pruning, where you generate a set of moves, and then say "these will be searched and these are going to be tossed out." IE the shannon type-B strategy.

What would you call pruning where you search some move sufficiently to decide it is a stupid move rather than a sacrifice and then mark it so that on future iterations you do not search it again?

That's the kind of pruning I am talking about, a move that is permanently marked as "never play". But it's STILL called forward pruning.

I would also call it a bad idea. Do any programs do this?

You can never be sure that a move that looks really bad actually is a very good move and a scalable program should never say never, although it's correct to give them much less consideration. But on a future iteration it should be possible to discover anything.

If the score is perfect, of course this does not apply because we need not search perfect moves, such as moves that reference an endgame database or simple ending that can be marked as a draw.

I think that sometimes you can be sure a move is bad, particularly in endgames.
Consider this position. How many ply do you need to analyze before you are sure a6 is a bad move? A human would never even consider this move.

I'm not sure we are talking about the same thing.

What I'm talking about is hard core pruning without any additional consideration ever - in a practical chess playing program.

Yes, you can construct positions like this where it's obvious that a6 is wrong, but I don't believe you can actually put this into a heuristic that can be applied to a chess program with 100 percent accuracy. If you can, then please tell me what it is?

What rule that is 100% correct will also tell you not to play a6 in this position?

I think if you try to produce such a rule, you will understand what I am saying.

[d]6k1/p4ppp/1p6/1P6/P7/8/6PP/6K1 b - - 0 1

It is possible to do this if you have a precalculation engine that computes based upon board configurations and bitmaps.

For instance, in this configuration, it will know (having precalculated) that the pawn race is lost. Therefore, the move is known a-priori as lost.

This is done by a program generator that performs incremental evaluations as a function of chessmen remaining on the board and has precomputed pawn race distances etc. already calculated.

For every combination of chessmen, there is a different move generator. Of course, this is impossibly tedious. That is why a function generator program is needed.

So, for instance, if the generated program list consumes 10 GB of source code it matters little because you did not have to write it -- you only had to write the function that writes the functions. (Of course, you are thinking about spilling the instruction cache by switching all these functions. But the functions change somewhat slowly over time because a program will not instantly go from 32 chessmen down to 4).

You need to be careful here.
Pawn race is lost does not mean that the game is lost because it is possible to get a draw in KQ vs KP endgame when the pawn is in the 7th rank.

Uri

[zamar]

How about this? In a Q+pawns vs pawns endgame, if the side with only pawns has no pawn past the 5th rank, a 3 ply search is enough to determine if the position is completely won or only probably won.

The usefulness of such rules is highly questionable because usually search of any modern chess engine is a kind of self-adjusting.

Let's assume that position you describe is to be searched with depth = 20, side with queen to move. In stockfish it might go like this:

Null move pawn move
queen move king move
null move king move
null move razoring

So instead of performing usual 20 ply search we just performed 7 ply search which cost is around 0.1% of the usual search.

Null move, futility pruning and razoring are your friends. They already do the dirty job for you in many many cases.

[Don]

How about this? In a Q+pawns vs pawns endgame, if the side with only pawns has no pawn past the 5th rank, a 3 ply search is enough to determine if the position is completely won or only probably won.

I don't think a 3 ply search is nearly enough to say with any kind of reasonable certainty.

Basicallly what you are saying is that if you are more than a queen up for 3 ply just assume you are winning.

I'm not saying that is a horrible rule, but it's clearly imperfect because there could be dangerous pawns that the 3 ply search cannot see.

Basically what I claim is a reasonable scalable solution is to reduce heaviliy if you are have a great deal of confidence that you have a won position. In other words, why do a 3 ply search? Make it based on the depth where you do more than 3 ply if your remaining depth is quite large, but you are still severely reducing based on high confidence.