Transposition Tables

Discussion of chess software programming and technical issues.

Moderators: hgm, Rebel, chrisw

bob
Posts: 20943
Joined: Mon Feb 27, 2006 7:30 pm
Location: Birmingham, AL

Re: Transposition Tables

Post by bob »

Uri Blass wrote:
bob wrote:
hgm wrote:You keep bringing up hash hits. This has nothing whatsoever to do with hash hits.

Imagine this is an engine _without_ any hash tables.

If there is a mate-in-4 from the root (7 ply) _no_ other branch from the root will be longer than 5 ply. Even if the requested depth at the root is 49. No hash tables. No hash hits. No hash prunings. Just plain alpha-beta + ID, with the best move of the previous iteration searched first.
Sorry, in that case you are wrong. If I do a 20 ply search, even after finding a mate in 5, most branches are going to 20 plies. The only ones that won't are the ones that end in a forced mate themselves, or that end in a forced draw. Otherwise there is no way to do a cutoff until you go down to the tip and work your way back up.

Remember. "depth first". So without hash tables, what you are saying will never happen. If it wasn't a depth-first approach, you would have a point, but depth-first behaves exactly as I explained. If you want to try to explain an example, I'll be glad to join in and explain what happens...
This is simply not correct.

If you find a forced mate in 5 you only need to remember the fact that you found mate in 5 to tell you that searching lines of more than 7 plies are useless because they cannot be shorter mate than mate in 5.

You simply decide about rules when not to search based on alpha beta and the ply of the search(you can have rules to change alpha and beta in case that they are mate score based on the ply of the search and when they are mate score you will simply have alpha>=beta and cutoff when the ply is too big).

Uri
Fine, then it isn't alpha/beta searching. This is a "depth-first" search paradigm. If you want to change that, that's ok. But then it isn't a depth-first search strategy because within the classic minimax/alpha-beta search, All scores are backed up from the tips. I suppose you could make such a test if you want to waste the time and branches, because how many positions would that apply in, compared to the 99.99999999% of the positions where there is no forced mate at all.

So if we are going to talk about non-standard "almost alpha/beta" that is OK. In that case I would always revert to the idea "make the usual/common case fastest". This isn't that either.
User avatar
hgm
Posts: 27870
Joined: Fri Mar 10, 2006 10:06 am
Location: Amsterdam
Full name: H G Muller

Re: Transposition Tables

Post by hgm »

bob wrote:Here is why moves go beyond the depth needed to find the mate.

If you find a mate in 3 from the root, you find that the side on move is mated at ply=6. No arguments there. But you have to realize that almost no branches end in mate scores. And for _every_ branch that does not reach a forced mate, you _must_ search all the way to the tip to get a score that will cause cutoffs as you back up the tree since you have found a forced mate already. But if you are doing a 20 ply search, and find a single mate in 3 from the root, all the rest of the root braches are going to go all the way to ply=20 and there is absolutely no way to prevent that since we are using a depth-first search algorithm. Since in the absence of a mate score on a path, no score is produced until you reach remaining-depth = 0 and call the q-search and ultimately the evaluation procedure.
Seems you haven't understood a word from what was written above.

Strange. It seems to me it was spelled out in excruciating detail.
So, every iteration you search takes longer and longer, and there's no solution to that within the alpha/beta framework.
Well, so alpha-beta sucks. Better do it the way I do it, then... :lol: :lol: :lol:
With all of that, I don't follow any of your reasoning since the tree doesn't miraculously get truncated at ply=6 for all branches, just because you found a mate in 3 on the first branch.
Well, my tree does. As I said, miraculously. The beta cutoffs see to that, as soon as the search realizes that the worst possible score (-INF) is already high enough to make the opponent avoid this branch.
Note also that even the first move which is a forced mate is going to have _many_ branches that must be searched to ply=20 as well, because any branch that doesn't end in a forced mate or draw can't get a score unless it is backed up from the tips. That's why I do not understand your original statement...
Of course branches do get scores without reaching the tips. It is quite common to give them artificial fail-low scores, as soon as it is clear that the score at the tip can never be high enough. This is called futility pruning. My engines don't engage in such futile searches as searching for a mate in a negative number of moves. I consider that as evidence of the superiority of my (trivially simple) scheme over strict minimax (which would not even prefer a mate-in-2 over a mate-in-8 without that silly kludge of path-dependent mate scores).
Being "pruned 2 plies earlier" does not mean they don't get searched to full depth however. You _must_ back up non-mate scores from the tips. Not from magic scores created at interior nodes. Because then you are not doing alpha/beta at all...
Ah, so now it finally begines to dawn on you that to do better than alpha-beta, one might perhaps need to do something different from alpha-beta? :roll:
The above explanation is simply wrong, as it appears you beleve that now suddenly no search branch goes beyond ply=6 when doing a 20 ply search. And that absolutely does not work that way..
Nothing wrong. The tip of the branch (node without children) is at ply=3. (A mate-in-3 only goes to ply=5, btw.)
The only question is, "what" do you get for free. You certainly can't get a tree where no branches extend beyond 6 plies...
Yes I can. The algorithm I described does exactly that.
bob
Posts: 20943
Joined: Mon Feb 27, 2006 7:30 pm
Location: Birmingham, AL

Re: Transposition Tables

Post by bob »

hgm wrote:
bob wrote:Here is why moves go beyond the depth needed to find the mate.

If you find a mate in 3 from the root, you find that the side on move is mated at ply=6. No arguments there. But you have to realize that almost no branches end in mate scores. And for _every_ branch that does not reach a forced mate, you _must_ search all the way to the tip to get a score that will cause cutoffs as you back up the tree since you have found a forced mate already. But if you are doing a 20 ply search, and find a single mate in 3 from the root, all the rest of the root braches are going to go all the way to ply=20 and there is absolutely no way to prevent that since we are using a depth-first search algorithm. Since in the absence of a mate score on a path, no score is produced until you reach remaining-depth = 0 and call the q-search and ultimately the evaluation procedure.
Seems you haven't understood a word from what was written above.

Strange. It seems to me it was spelled out in excruciating detail.

You are correct. It never occurred to me that one would make a basic change to alpha/beta that hurts everywhere but when dealing with mates (probably doesn't hurt a lot, but every branch is bad and every bit of code that gets executed at every node is bad when it is ineffective at most).

I now understand that you use the bounds to lop off the search. I think it is pointless, but that's up to you and your program. Exactly how often does that happen in a real game? Very few games end in checkmate when I play other computers or GM players.


So, every iteration you search takes longer and longer, and there's no solution to that within the alpha/beta framework.
Well, so alpha-beta sucks. Better do it the way I do it, then... :lol: :lol: :lol:

Perhaps alpha/beta is not best in finding forced mates. But it is certainly best for overall searching, and putting extra test conditions to lop the search off when it hardly ever happens is not a great idea IMHO. Again, "make the common case fastest" not some special-case where you find a mate, which is a very uncommon condition.
With all of that, I don't follow any of your reasoning since the tree doesn't miraculously get truncated at ply=6 for all branches, just because you found a mate in 3 on the first branch.
Well, my tree does. As I said, miraculously. The beta cutoffs see to that, as soon as the search realizes that the worst possible score (-INF) is already high enough to make the opponent avoid this branch.
Note also that even the first move which is a forced mate is going to have _many_ branches that must be searched to ply=20 as well, because any branch that doesn't end in a forced mate or draw can't get a score unless it is backed up from the tips. That's why I do not understand your original statement...
Of course branches do get scores without reaching the tips. It is quite common to give them artificial fail-low scores, as soon as it is clear that the score at the tip can never be high enough. This is called futility pruning.
That is _never_ applied anywhere but near the tips. Saving a couple of plies and the q-search nodes needed as well. But not lopping off 15 plies out of a 20 ply search.

My engines don't engage in such futile searches as searching for a mate in a negative number of moves. I consider that as evidence of the superiority of my (trivially simple) scheme over strict minimax (which would not even prefer a mate-in-2 over a mate-in-8 without that silly kludge of path-dependent mate scores).
Again, "make the common case fastest." I can absolutely guarantee you that mate scores are not "the common case". If you want to waste the time to do that, feel free... I'd much rather search extra stuff when I have found a forced win, rather than doing extra work in all the cases where I don't have a forced win. Again, mates are rare in real chess. Most games end in resignation far before that point arrives.

Being "pruned 2 plies earlier" does not mean they don't get searched to full depth however. You _must_ back up non-mate scores from the tips. Not from magic scores created at interior nodes. Because then you are not doing alpha/beta at all...
Ah, so now it finally begines to dawn on you that to do better than alpha-beta, one might perhaps need to do something different from alpha-beta? :roll:

No, it began to dawn on me that you had introduced an inefficiency in real alpha/beta that has a very definite cost, to handle a case that hardly ever occurs and when it does occur it is not that important to stop early.
The above explanation is simply wrong, as it appears you beleve that now suddenly no search branch goes beyond ply=6 when doing a 20 ply search. And that absolutely does not work that way..
Nothing wrong. The tip of the branch (node without children) is at ply=3. (A mate-in-3 only goes to ply=5, btw.)
How do you find out you have a mate? I have to get to ply 6, and find no legal moves + notice I am in check. That's far more efficient than checking for mate after each move is played at ply 5.

The only question is, "what" do you get for free. You certainly can't get a tree where no branches extend beyond 6 plies...
Yes I can. The algorithm I described does exactly that.
Yep... and is a search algorithm nobody else is using, because we all trust alpha/beta and want to make it as efficient as possible. This is adding some sort of non-depth-first process into a depth-first algorithm. If you like it, more power to you. I don't consider it worthwhile at all...
User avatar
hgm
Posts: 27870
Joined: Fri Mar 10, 2006 10:06 am
Location: Amsterdam
Full name: H G Muller

Re: Transposition Tables

Post by hgm »

bob wrote:You are correct. It never occurred to me that one would make a basic change to alpha/beta that hurts everywhere but when dealing with mates (probably doesn't hurt a lot, but every branch is bad and every bit of code that gets executed at every node is bad when it is ineffective at most).
So why bother to react, if you have not the slightest idea what people are talking about, and can only argue from yuor own irrelevant pre-concptions and prejudices? What do you want to prove? That you are unable to understand pseudo-code?
I now understand that you use the bounds to lop off the search.
Better late than never. As it was in the first line I wrote about this subject some 50 postings ago...
I think it is pointless, but that's up to you and your program. Exactly how often does that happen in a real game? Very few games end in checkmate when I play other computers or GM players.
Well, you won't be able to beat uMax without one, for starters... :lol: :lol: :lol:
Perhaps alpha/beta is not best in finding forced mates. But it is certainly best for overall searching, and putting extra test conditions to lop the search off when it hardly ever happens is not a great idea IMHO. Again, "make the common case fastest" not some special-case where you find a mate, which is a very uncommon condition.
As I wrote, it is a completely free side effect of the way I implemented the delayed-loss bonus. Things that take absolutely zero time I generally consider fast. But knowing how you like to search 20 ply deeper to find a mate-in-1, I don't expect you to agree. You probably would be willing to spend a man year on how to speed that up. :lol: :lol: :lol:
That is _never_ applied anywhere but near the tips. Saving a couple of plies and the q-search nodes needed as well. But not lopping off 15 plies out of a 20 ply search.
Nevertheless is is hard refutation of your claims that one has to search to the tips. One might say that your statements fail low here. That in your opinion they fail low only by a little amount, is quite irrelevant. :wink:

Again, "make the common case fastest." I can absolutely guarantee you that mate scores are not "the common case". If you want to waste the time to do that, feel free... I'd much rather search extra stuff when I have found a forced win, rather than doing extra work in all the cases where I don't have a forced win. Again, mates are rare in real chess. Most games end in resignation far before that point arrives.
As I pointed out, it takes zero time. Fast enough for me.
No, it began to dawn on me that you had introduced an inefficiency in real alpha/beta that has a very definite cost, to handle a case that hardly ever occurs and when it does occur it is not that important to stop early.
Well, that is great progress, that you finally now start to understand the first of the 5000 lines that I posted on this subject since then. Unfortunately I don't expect to live to the age of 150, so the line that says 'zero time' probably will remain beyond your grasp forever.
How do you find out you have a mate? I have to get to ply 6, and find no legal moves + notice I am in check. That's far more efficient than checking for mate after each move is played at ply 5.
The pseudo-legal King moves that might be generated never make it to the MakeMove stage. A SEE on them removes them from the move list. When in-check Imost people don't do pseudo-legal move generation. So in my definition ply=6 is not reached. I only count moves that are actually made. Similar in QS nodes: A QS node that returns the Eval score after concluding that it has no legal captures, is a tip.
Yep... and is a search algorithm nobody else is using, because we all trust alpha/beta and want to make it as efficient as possible. This is adding some sort of non-depth-first process into a depth-first algorithm. If you like it, more power to you. I don't consider it worthwhile at all...
Well, no one would have really expected that. But that wouldn't stop me from recommending it to other people.
Uri Blass
Posts: 10413
Joined: Thu Mar 09, 2006 12:37 am
Location: Tel-Aviv Israel

Re: Transposition Tables

Post by Uri Blass »

hgm wrote:
bob wrote:You are correct. It never occurred to me that one would make a basic change to alpha/beta that hurts everywhere but when dealing with mates (probably doesn't hurt a lot, but every branch is bad and every bit of code that gets executed at every node is bad when it is ineffective at most).
So why bother to react, if you have not the slightest idea what people are talking about, and can only argue from yuor own irrelevant pre-concptions and prejudices? What do you want to prove? That you are unable to understand pseudo-code?
I now understand that you use the bounds to lop off the search.
Better late than never. As it was in the first line I wrote about this subject some 50 postings ago...
I think it is pointless, but that's up to you and your program. Exactly how often does that happen in a real game? Very few games end in checkmate when I play other computers or GM players.
Well, you won't be able to beat uMax without one, for starters... :lol: :lol: :lol:
Perhaps alpha/beta is not best in finding forced mates. But it is certainly best for overall searching, and putting extra test conditions to lop the search off when it hardly ever happens is not a great idea IMHO. Again, "make the common case fastest" not some special-case where you find a mate, which is a very uncommon condition.
As I wrote, it is a completely free side effect of the way I implemented the delayed-loss bonus. Things that take absolutely zero time I generally consider fast. But knowing how you like to search 20 ply deeper to find a mate-in-1, I don't expect you to agree. You probably would be willing to spend a man year on how to speed that up. :lol: :lol: :lol:
That is _never_ applied anywhere but near the tips. Saving a couple of plies and the q-search nodes needed as well. But not lopping off 15 plies out of a 20 ply search.
Nevertheless is is hard refutation of your claims that one has to search to the tips. One might say that your statements fail low here. That in your opinion they fail low only by a little amount, is quite irrelevant. :wink:

Again, "make the common case fastest." I can absolutely guarantee you that mate scores are not "the common case". If you want to waste the time to do that, feel free... I'd much rather search extra stuff when I have found a forced win, rather than doing extra work in all the cases where I don't have a forced win. Again, mates are rare in real chess. Most games end in resignation far before that point arrives.
As I pointed out, it takes zero time. Fast enough for me.
No, it began to dawn on me that you had introduced an inefficiency in real alpha/beta that has a very definite cost, to handle a case that hardly ever occurs and when it does occur it is not that important to stop early.
Well, that is great progress, that you finally now start to understand the first of the 5000 lines that I posted on this subject since then. Unfortunately I don't expect to live to the age of 150, so the line that says 'zero time' probably will remain beyond your grasp forever.
How do you find out you have a mate? I have to get to ply 6, and find no legal moves + notice I am in check. That's far more efficient than checking for mate after each move is played at ply 5.
The pseudo-legal King moves that might be generated never make it to the MakeMove stage. A SEE on them removes them from the move list. When in-check Imost people don't do pseudo-legal move generation. So in my definition ply=6 is not reached. I only count moves that are actually made. Similar in QS nodes: A QS node that returns the Eval score after concluding that it has no legal captures, is a tip.
Yep... and is a search algorithm nobody else is using, because we all trust alpha/beta and want to make it as efficient as possible. This is adding some sort of non-depth-first process into a depth-first algorithm. If you like it, more power to you. I don't consider it worthwhile at all...
Well, no one would have really expected that. But that wouldn't stop me from recommending it to other people.

I think that it is better to be more polite.
The fact that Bob did not understand is because he made some wrong assumption that alpha beta as he understands it is used.

I did not consider your ideas as not alpha-beta but definition is of course not something that I want to argue about.

When we talk about time I guess that for bob even something that take very small time is not zero time.

If you change alpha and beta during the search then it take time.
This time is very small and may do your program only 0.1% slower but it is not 0.

Uri
User avatar
hgm
Posts: 27870
Joined: Fri Mar 10, 2006 10:06 am
Location: Amsterdam
Full name: H G Muller

Re: Transposition Tables

Post by hgm »

Uri Blass wrote:When we talk about time I guess that for bob even something that take very small time is not zero time.

If you change alpha and beta during the search then it take time.
This time is very small and may do your program only 0.1% slower but it is not 0.
I have to change alpha and beta anyway, to adjust the window for the delayed-loss bonus.

So when I say that the cutting off of all branches at the mate depth takes zero time, I really mean zero time, and not a little. And zero code as well. It is just a matter of choosing the CHECKMATED score cleverly compared to -INFINITY.
bob
Posts: 20943
Joined: Mon Feb 27, 2006 7:30 pm
Location: Birmingham, AL

Re: Transposition Tables

Post by bob »

hgm wrote:
bob wrote:You are correct. It never occurred to me that one would make a basic change to alpha/beta that hurts everywhere but when dealing with mates (probably doesn't hurt a lot, but every branch is bad and every bit of code that gets executed at every node is bad when it is ineffective at most).
So why bother to react, if you have not the slightest idea what people are talking about, and can only argue from yuor own irrelevant pre-concptions and prejudices? What do you want to prove? That you are unable to understand pseudo-code?
Perhaps that I am unable to stand a lot of gibberish thrown in. Alpha/Beta is a well-known algorithm. With no "stop the search just because a value is outside the window" exceptions thrown in. So, perhaps I am guilty of thinking about the algorithm I thought we all used, and am guilty of that.

However, the idea is still defective from a performance perspective, which is why nobody does it.

I now understand that you use the bounds to lop off the search.
Better late than never. As it was in the first line I wrote about this subject some 50 postings ago...
I think it is pointless, but that's up to you and your program. Exactly how often does that happen in a real game? Very few games end in checkmate when I play other computers or GM players.
Well, you won't be able to beat uMax without one, for starters... :lol: :lol: :lol:
I don't worry about my opponent's sloppy programming. If you can't find a good way to handle resigning and offering/accepting draws, that's your issue. I handle those cases just fine, and I do so because I don't like to aggravate GM players by playing to mate in dead lost positions and such... Perhaps we have different goals overall?



Perhaps alpha/beta is not best in finding forced mates. But it is certainly best for overall searching, and putting extra test conditions to lop the search off when it hardly ever happens is not a great idea IMHO. Again, "make the common case fastest" not some special-case where you find a mate, which is a very uncommon condition.
As I wrote, it is a completely free side effect of the way I implemented the delayed-loss bonus. Things that take absolutely zero time I generally consider fast. But knowing how you like to search 20 ply deeper to find a mate-in-1, I don't expect you to agree. You probably would be willing to spend a man year on how to speed that up. :lol: :lol: :lol:
In the pseudo-code you posted, you have an extra conditional statement to bail out before doing the recursive call to search(). That is not "zero cost" by any measure.

That is _never_ applied anywhere but near the tips. Saving a couple of plies and the q-search nodes needed as well. But not lopping off 15 plies out of a 20 ply search.
Nevertheless is is hard refutation of your claims that one has to search to the tips. One might say that your statements fail low here. That in your opinion they fail low only by a little amount, is quite irrelevant. :wink:
Most people, when they discuss such, call it "alpha/beta with futility pruning". Then there is no ambiguity. Ditto for alpha/beta with null-move which is another variant...

Again, "make the common case fastest." I can absolutely guarantee you that mate scores are not "the common case". If you want to waste the time to do that, feel free... I'd much rather search extra stuff when I have found a forced win, rather than doing extra work in all the cases where I don't have a forced win. Again, mates are rare in real chess. Most games end in resignation far before that point arrives.
As I pointed out, it takes zero time. Fast enough for me.
Then is the code you posted earlier wrong? You had this line twice:

if (eval >= beta) go to cutoff
eval = search()
if (eval >= beta) go to cutoff

That is not "zero cost". And for a case that is very rarely happening at that...



No, it began to dawn on me that you had introduced an inefficiency in real alpha/beta that has a very definite cost, to handle a case that hardly ever occurs and when it does occur it is not that important to stop early.
Well, that is great progress, that you finally now start to understand the first of the 5000 lines that I posted on this subject since then. Unfortunately I don't expect to live to the age of 150, so the line that says 'zero time' probably will remain beyond your grasp forever.
Since it is obviously false, I suppose it will. No computation you do is "zero cost" if you do more than what is required without the "change".

Clearly the second IF is not free.

How do you find out you have a mate? I have to get to ply 6, and find no legal moves + notice I am in check. That's far more efficient than checking for mate after each move is played at ply 5.
The pseudo-legal King moves that might be generated never make it to the MakeMove stage. A SEE on them removes them from the move list. When in-check Imost people don't do pseudo-legal move generation. So in my definition ply=6 is not reached. I only count moves that are actually made. Similar in QS nodes: A QS node that returns the Eval score after concluding that it has no legal captures, is a tip.
I had a "check evasion generator" in the earliest version of Crafty. But that is not done until ply=6. Why would I be generating moves for my opponent when I am on move in ply=5? Makes no sense to me. I generate legal moves, of which there are none, and when I try to find/make the first move, I discover there are none and since I am in check, I conclude this side is mated. All at ply=6, not 5...

Yep... and is a search algorithm nobody else is using, because we all trust alpha/beta and want to make it as efficient as possible. This is adding some sort of non-depth-first process into a depth-first algorithm. If you like it, more power to you. I don't consider it worthwhile at all...
Well, no one would have really expected that. But that wouldn't stop me from recommending it to other people.
bob
Posts: 20943
Joined: Mon Feb 27, 2006 7:30 pm
Location: Birmingham, AL

Re: Transposition Tables

Post by bob »

hgm wrote:
Uri Blass wrote:When we talk about time I guess that for bob even something that take very small time is not zero time.

If you change alpha and beta during the search then it take time.
This time is very small and may do your program only 0.1% slower but it is not 0.
I have to change alpha and beta anyway, to adjust the window for the delayed-loss bonus.

So when I say that the cutting off of all branches at the mate depth takes zero time, I really mean zero time, and not a little. And zero code as well. It is just a matter of choosing the CHECKMATED score cleverly compared to -INFINITY.
Two points...

(1) you are doing something inefficient at _every_ ply in the tree. So saying it takes zero time when doing it for the mate case is just a tad disingenuous. at a minimum. It just means you are doing something unnecessary _everywhere_ so there is no extra cost (to you only) when you do it in a place where it might actually help in a rare case only.

(2) the conditional test to avoid calling search is absolutely not free either. So in reality your zero cost, means my search approach has a negative cost in this area. And a negative cost is better than a zero cost, if you want to go that far out on a limb to try to make a case.

If you think that mucking with the bounds is a good approach, go for it. It is certainly not the "optimal" approach, although many different approaches will actually work. I still suspect hashing issues any time you muck with a bound, unless you muck with the bound you store in the table as well, because otherwise you have path-dependent information in the bounds that doesn't match the non-path-dependent hash signature you use for looking things up.

but do it however you want.
User avatar
hgm
Posts: 27870
Joined: Fri Mar 10, 2006 10:06 am
Location: Amsterdam
Full name: H G Muller

Re: Transposition Tables

Post by hgm »

bob wrote:Perhaps that I am unable to stand a lot of gibberish thrown in. Alpha/Beta is a well-known algorithm. With no "stop the search just because a value is outside the window" exceptions thrown in. So, perhaps I am guilty of thinking about the algorithm I thought we all used, and am guilty of that.
Indeed. And the request is not to do that, as it is not helpful. If person A proposes something new to person B, and you have no idea what they are proposing, and you don't like to find out, DO NOT go off like a broken record to repeat what you think everyone is using.
However, the idea is still defective from a performance perspective, which is why nobody does it.
Knowing that you usually don't have the slightest idea what you are talking about, when talking about other people's algorithms, it should be abundantly clear that that statement is worth zilch.
I don't worry about my opponent's sloppy programming. If you can't find a good way to handle resigning and offering/accepting draws, that's your issue. I handle those cases just fine, and I do so because I don't like to aggravate GM players by playing to mate in dead lost positions and such... Perhaps we have different goals overall?
I have a very good way to handle resigning: never do it at all. Never in the history of Chess one point has been earned by resigning. :lol:
In the pseudo-code you posted, you have an extra conditional statement to bail out before doing the recursive call to search(). That is not "zero cost" by any measure.
See below.
Most people, when they discuss such, call it "alpha/beta with futility pruning". Then there is no ambiguity. Ditto for alpha/beta with null-move which is another variant...
Your point being exactly what? Have I called it anything different? Have I indeed called it anything at all? Have I ever claimed that it was even alpha-beta? The only thing I have done is post 3 lines of pseudo-code and adviced Colin to use that in stead of the silly 100000-ply stuff for hash probing and storing.

That being said, I think you have an extremely narrow-minded interpretation of the meaning of 'alpha-beta'. The original meaning of alpha-beta pruning is a pruning technique that prunes branches whose score can no longer have any effect on the score of the root. That does NOT limit it to minimax. And it certainly does not limit it to fixed-depth minimax.
Then is the code you posted earlier wrong? You had this line twice:

if (eval >= beta) go to cutoff
eval = search()
if (eval >= beta) go to cutoff

That is not "zero cost". And for a case that is very rarely happening at that...
Well, I don't know how you do it, of course, but I prefer to take the stand-pat cutoff before having searched any moves, if Eval >= Beta. As searching captures usually give rise to more than 1 branch that ends in an evaluation, plus a lot of other worke (Make/UnMake, capture generation). So indeed, I think it saves time to compare Eval to Beta before searching the first move. I was under the impression that his was also quite standard. Ors should I call it alpha-beta plus QS then? :roll:
Since it is obviously false, I suppose it will. No computation you do is "zero cost" if you do more than what is required without the "change".

Clearly the second IF is not free.
the second IF actually saves a lot of unnecessary move generations in QS.
I had a "check evasion generator" in the earliest version of Crafty. But that is not done until ply=6. Why would I be generating moves for my opponent when I am on move in ply=5? Makes no sense to me. I generate legal moves, of which there are none, and when I try to find/make the first move, I discover there are none and since I am in check, I conclude this side is mated. All at ply=6, not 5...
We might simply starting the count differently? With me the root is ply=0, so with mate-in-3 the first move of the mating side would bring you from ply=0 to ply=1, the third move to ply=5. So on ply=5 the side that has the move is checkmated, has no legal moves and is in check.

So which moves for the opponent would you want me to generate at ply=5? That makes no sens to me either.
Uri Blass
Posts: 10413
Joined: Thu Mar 09, 2006 12:37 am
Location: Tel-Aviv Israel

Re: Transposition Tables

Post by Uri Blass »

Only one note:
Many people use ideas that are defective from a performance perspective
so claiming that this is a reason that nobody does it is not correct.


Here is one example:
The idea to have a move generator that include bishop underpromotions is defective from a performance perspective but most programmers do it.

I also do it because performance is not the only target that I consider.

Uri