Transposition Tables

[hgm]

This whole idea that a single conditional jump would 'wreck performance' is of course so silly that it it is a shameful display that Bob even dares to hide behind it, as an excuse for not reading the posts he reacts to. We are talking here about a single if per move generation. he move generation will obviously takes a thousand times longer. And that from a person who has repeatedly stated here that he does not care about the efficiency of his move genrator, as generating moves is only about 10% of the search time. And now something that might take 0.1% of that time (had it not been needed for QS anyway) would suddenly wreck performance to an extent that no one would use this?

I never have heard such a feeble and laughable excuse in my life. Not even when I was in Kindergarten.

[bob]

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.

Again, different goals. I want GM players to play my program. They won't if it drags draws out forever or plays every game to mate. This has been well-documented in the past in discussions with GM players when they talk about playing computers on chess servers. If you don't care about such games, fine. I do, however, in that I am trying to do something reasonably similar to what humans do when they play the game, including "having class and showing manners". It is something worth trying (hint).

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.

It isn't "silly". It works in a _very_ straightforward way, it makes looking at tree dumps much easier since bounds don't vary depending on the ply.. It is known to work correctly with hashing, something yours has not convinced me of yet. Etc. You have a _very_ strange definition of "silly". It would seem you mean "anything that works quite simply and provably correctly is silly". Because this is provably correct and it is definitely simple.

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.

Now we are in the twilight. Alpha/beta _is_ minimax, but with backward pruning included. No idea what on earth the above means. It is absolutely defined in the domain of minimax, which is depth-first.

Jeez, if we don't have a common and accepted vocabulary, no wonder it is so hard to communicate. I use the normal computer science definition of the above myself. One which you can find in _any_ AI book.

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.

Again, a vocabulary problem. "stand pat" is the option you have in the quiescence search. But nowhere else. And this doesn't seem to be talking about the q-search at all unless you have switched the subject.

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?

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.

We are talking about the first (unnecessary) if...

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.

The first move made is made at ply=1, the second move made is at ply=2. I have not seen anyone number them any differently than that...

So which moves for the opponent would you want me to generate at ply=5? That makes no sens to me either.

I don't want you to generate any opponent moves at ply=5. plies 1,3,5 are computer-on-move. But a mate in 3 delivers mate at ply=5, but I need to get to ply=6 to see that the opponent has no legal moves...

Are we again talking apples and oranges???

[bob]

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

How can it be "defective" when it implements a rule of chess that is clearly defined? There are positions where a bishop under-promotion is the only move that wins or draws. They are rare, but they are not non-existent.

I can't think of _anyone_ that uses an idea that is both defective from a performance point of view _and_ offers nothing from a practical point of view either... I have seen more than my fair share of "bizarre" alpha/beta implementations over the past 40 years or so, and this particular approach falls right into the same bin, IMHO. The idea may work perfectly. I personally believe that it is flawed with respect to hash hits. And it clearly is a confusing issue when debugging by printing trees...

But several of the bizarre implementations I have seen did work, so if this one does, more power to him. But I would not suggest that someone try something that is considerably "out there" with respect to clarity and debugging. I don't like the idea of mucking the bounds at all...

[hgm]

Again, different goals. I want GM players to play my program. They won't if it drags draws out forever or plays every game to mate. This has been well-documented in the past in discussions with GM players when they talk about playing computers on chess servers. If you don't care about such games, fine. I do, however, in that I am trying to do something reasonably similar to what humans do when they play the game, including "having class and showing manners". It is something worth trying (hint).

All side-tracking. You brought the issue of resigning up, and if you knew your goal to be different from mine you also knew that this was irrelevant. If you don't think your engine needs to be capable to perform a decent checkmate, because the opponents are all GM and thus will have the class and manners to resign before the actual mate, you are badly mistaken. As soon as they even get a whiff of the fact that your engine might not be able to win KQK, they will play on in such lost positions laughing themselves silly about those stupid computers.

It isn't "silly". It works in a _very_ straightforward way, it makes looking at tree dumps much easier since bounds don't vary depending on the ply.. It is known to work correctly with hashing, something yours has not convinced me of yet. Etc. You have a _very_ strange definition of "silly". It would seem you mean "anything that works quite simply and provably correctly is silly". Because this is provably correct and it is definitely simple.

That is a very unsound inference. Just because one thing that works modarately simply and provably correct is silly, anything else sharing those properties should be silly as well?

Besides, I do not consider it straightforward at all, as you store different values in the hash table than what you return as search scores. This mucking with hash scores I don't like, and indeed leads to frequent errors for people first implementing hash tables. And what makes it truly silly, of course, it that it only works for mates. So that if the engine gets into a KQKR ending, it might be showing the same indecisive behavior of preferring to capture the Rook in 2 moves rather than in 1 move, because it can see that on the QxR the bare K can make a step towards the center, and thus wants to keep that move over the horizon by only playing QxR on the last ply of the search. Thus postponing the conversion forever or until the 50-move rule finally convinces it that a capture is needed. That is what I call silly.

Now we are in the twilight. Alpha/beta _is_ minimax, but with backward pruning included. No idea what on earth the above means.

It means what it says. Alpha-beta is a pruning technique that can be applied to a wide variety of search types, including, but not limited to minimax.

It is absolutely defined in the domain of minimax, which is depth-first.

More nonsense. Minimax is defined as an abstract prescription for propagating leave scores towards the root. It says _nothing_ about any temporal aspects of this. Depth-first is a prescription to walk a tree sequentially. I would not call retrograde analysis as used for EGTB building 'depth first', but it is undeniably minimax.

Jeez, if we don't have a common and accepted vocabulary, no wonder it is so hard to communicate. I use the normal computer science definition of the above myself. One which you can find in _any_ AI book.

This is why I clearly and concisely define every every term I use, and mostly avoid using any term whatsoever, but give pseudo-code in stead. But alas, to little avail...

Again, a vocabulary problem. "stand pat" is the option you have in the quiescence search. But nowhere else. And this doesn't seem to be talking about the q-search at all unless you have switched the subject.

Well, I guess it is more a problem of you being incapable of understanding pseudo-code. Otherwise you would have noticed that the pseudo-code where you saw that allegedly unnecessary if-statement was for a Search() implementation that did both main search and QS, and thus needed a test for stand-pat cutoff...

Clearly the second IF is not free.

the second IF actually saves a lot of unnecessary move generations in QS.

We are talking about the first (unnecessary) if...

Hmm, must be something wrong with my eyes, then...

The first move made is made at ply=1, the second move made is at ply=2. I have not seen anyone number them any differently than that...

Well, you have seen now. But you Americans also seem to count floors funny, so I can imagine what makes you do it that way.

I could not care less how we count, as long as it is noted (as was explicitly stated) that in all the examples I gave he root is ply=0, i.e. before making any plies. If you rather call a mate-in-3 if it happens at ply=6, then of course all the other branches would be cut at ply=4 in your terminology.

I don't want you to generate any opponent moves at ply=5. plies 1,3,5 are computer-on-move. But a mate in 3 delivers mate at ply=5, but I need to get to ply=6 to see that the opponent has no legal moves...

Are we again talking apples and oranges???

Like I said, just confusion through counting differently.

[hgm]

How can it be "defective" when it implements a rule of chess that is clearly defined? There are positions where a bishop under-promotion is the only move that wins or draws. They are rare, but they are not non-existent.

"Defective from a performance point of view" means that you would score better by not implementing the feature, and take your loss (e.g. by printing 'resign') in the situation where you would have needed the feature. Because the speedup of the search by not implementing the feature would bring you more Elo than the occasional loss when you needed it would have gained you.

For under-promotions this is not quite the case, but under conditions where not only the speed, but also the size is important, under-promotion is truly defective: these rules offer resigning as a fully legal alternative.

If the rules of Chess clearly define it or not, is immaterial.

[Uri Blass]

1)Note that the good engines have no problem to force mate.
They sometime may spend a lot of time on mate in 1 but this is not something that change the result of the game.

2)preferring to capture the Rook in 2 moves rather than in 1 move is not a practical problem based on my experience even without delayed bonus.

If it happens it certainly does not happen often otherwise I could see it in games of movei that even does not store mates correctly and may report mate in 8 when the shortest mate is mate in 10 thanks to wrong handling of it in the hash but it does not prevent movei to win the game.

I plan to fix the problem of wrong mate scores but I do not find it as something that changes the result and if it changes the results it probably happens in less than 1 out of 100 games.

3)Movei has no problem of spending long time on mate in 1 because after having finishing an iteration with mate score it does not start another iteration.

You can claim that in theory it may lead to not finding mate because it always is going to play a move that leads to mate in 7 instead of mate in 6
until it has no mate without repetition that it evaluates as draw but practically it never happened in my experience.

Uri

[Uri Blass]

How can it be "defective" when it implements a rule of chess that is clearly defined? There are positions where a bishop under-promotion is the only move that wins or draws. They are rare, but they are not non-existent.

"Defective from a performance point of view" means that you would score better by not implementing the feature, and take your loss (e.g. by printing 'resign') in the situation where you would have needed the feature. Because the speedup of the search by not implementing the feature would bring you more Elo than the occasional loss when you needed it would have gained you.

For under-promotions this is not quite the case, but under conditions where not only the speed, but also the size is important, under-promotion is truly defective: these rules offer resigning as a fully legal alternative.

If the rules of Chess clearly define it or not, is immaterial.

I think that I can score better by having move generator that does not consider bishop underpromotions.

If we think only about performance than the speed up by not implementing underpromotions to bishop is probably more important than one game out of million when underpromotion to bishop may help you to get a better result.

Uri

[hgm]

This might even be true for Rook under-promotions.

[nczempin]

I think that I can score better by having move generator that does not consider bishop underpromotions.

If we think only about performance than the speed up by not implementing underpromotions to bishop is probably more important than one game out of million when underpromotion to bishop may help you to get a better result.

Uri

Not generating sub-promotions in the search doesn't preclude you from allowing them as a legal move. I consider legality checking of made moves as the domain of the interface (as in the code that impliments UCI or WB), not the engine itself.

So perhaps even for uMax it would be "legal" (cost of 0 characters) to keep them out of the move generation, but allow it to be a legal move (without resigning).

[hgm]

Just to give an example of alpha-beta pruning in a non-minimax context:

Suppose the score propagation in a game tree is defined as:

Code: Select all

Search(N) = 0.95*max_moves(-Search(N-1)) + 0.05*Eval()     (N>0)
Search(0) = QS() = max( Eval(), 0.95*max_capts(-QS()) + 0.05*Eval() ),

where max_moves(x) and max_capts(x) means the maximum of the quantity x after moving, taken over the set of all moves or captures, respectively, and the maximum over an empty set is defined as -INFINITY, as usual. Note that when we replace the 0.05 by 0, and the 0.95 to 1, this would degenerate into common minimax.

Pseudo-code to efficiently compute Search(N) would then be:

Code: Select all

Search(Depth, Alpha, Beta)
{    int NewAlpha, NewBeta, Score, CurEval = Eval();

    if&#40;Depth <= 0&#41; Alpha = CurEval; // stand pat
    if&#40;BestScore >= Beta&#41; return Beta; // stand-pat cutoff

    NewAlpha = &#40;Alpha - 0.05*CurEval&#41;/0.95;
    NewBeta = &#40;Beta - 0.05*CurEval&#41;/0.95;

    if&#40;Depth > 0&#41; GENERATE_MOVES; else GENERATE_CAPTURES;

    for&#40;ALL_MOVES&#41;
    &#123;
        Make&#40;);
        // Ask for a Score value that is EXACT between NewAlpa and NewBeta
        Score = -Search&#40;Depth-1, -NewBeta, -NewAlpha&#41;;
        UnMake&#40;);

        Score = 0.95*Score + 0.05*CurEval; // score propagation rule
        // After this, Score will be EXACT if it is between Alpha and Beta

        if&#40;Score > Alpha&#41; 
        &#123;   Alpha = Score;
            if&#40;Alpha >= Beta&#41; return Beta;
        &#125;
    &#125;

    return&#40;Alpha&#41;;
&#125;

Apart from the fact that the original score in this game is not determined through strict minimaxing (e.g. different paths to the same final position can have different scores), the pruning of irrelevant branches is so much identical to alpha-beta pruning in a minimax tree, that I don't see what would ever be gained by _not_ calling this alpha-beta pruning.