Is this trivially obvious?

Discussion of chess software programming and technical issues.

Moderator: Ras

Chan Rasjid
Posts: 588
Joined: Thu Mar 09, 2006 4:47 pm
Location: Singapore

Re: Is this trivially obvious?

Post by Chan Rasjid »

hgm wrote:If there is a mate in N ply, you will see it with certainty when you search N ply(fixed depth). Searching deeper cannot bring any faster mate in view. And searching less deep will with equal certainty not make you see any mate in N. Not only that you cannot force it: when you do not search N ply, you will not find a single node in your tree that has a mate-in-N-ply score.

The score of mate nodes is coupled hard to the tree level where you find them.
It seems my OP did not state the conditions clearly; but it does seem a dumb question.

I'll think about this dumb thing.

Thanks,
Rasjid.
User avatar
Desperado
Posts: 879
Joined: Mon Dec 15, 2008 11:45 am

Re: Is this trivially obvious?

Post by Desperado »

Chan Rasjid wrote:
hgm wrote:Are you talking now about fixed-depth full-width searches? Because then it is trivially obvious. And if it is not fixed-depth, but can use extensions, then it is obviously not true, so there would be nothing to prove.
Say yes, fixed-depth full-width searches with no extensions. Why is it trivially obvious.

Rasjid.
if you think of a minimax tree, that means you visit _every_ node.
now, if you find a mateScore which is a forced mate it will be passed back
to the root with guarantee to be the shortest mate possible.

AlphaBeta guarantees to get the same score as minimax, because only
branches(scores) are pruned that cannot be forced anyway.

So the conclusion is that if you find a mate in N at ply X, you have to find
at X+1,x+2,x+n... the same mate in N (fix depth search,no selectivity: which is basically a minimax result of a balanced tree, related to length of paths)
Chan Rasjid
Posts: 588
Joined: Thu Mar 09, 2006 4:47 pm
Location: Singapore

Re: Is this trivially obvious?

Post by Chan Rasjid »

Desperado wrote:
Chan Rasjid wrote:
hgm wrote:Are you talking now about fixed-depth full-width searches? Because then it is trivially obvious. And if it is not fixed-depth, but can use extensions, then it is obviously not true, so there would be nothing to prove.
Say yes, fixed-depth full-width searches with no extensions. Why is it trivially obvious.

Rasjid.
if you think of a minimax tree, that means you visit _every_ node.
now, if you find a mateScore which is a forced mate it will be passed back
to the root with guarantee to be the shortest mate possible.

AlphaBeta guarantees to get the same score as minimax, because only
branches(scores) are pruned that cannot be forced anyway.

So the conclusion is that if you find a mate in N at ply X, you have to find
at X+1,x+2,x+n... the same mate in N (fix depth search,no selectivity: which is basically a minimax result of a balanced tree, related to length of paths)
I think this is about it, a minimax explanation.

Thanks,
Rasjid.