Newbie needs help: the TT breaks my PV scheme

[Harald Johnsen]

To store the PV i use a triangular array (like in TSCP) , wich is updated every time negamax() or quiesce() return a score bigger than alpha.
The TT has 10 million entries and uses an always replace strategy.
Do i need a new PV scheme? Could anyone give me some advice?
Thanks

You are perhaps forgetting to update your pv when you do a cuttoff (perhaps the last move is not updated or the lenght is not computed correctly).
A simple test is to not do cuttoff inside the PV. It's not needed and it's easier to debug you search and your eval.

HJ.

[P. Villanueva]

Well, first off, that name has already been used for a private engine. Sorry.

Ouch! I didn't know it!

There are a few issues though. First, you always need to store a move at the root. Most people use a separate function for the root (though it's probably not that important for you right now), and I don't think anyone probes the hash in the root position. If you do decide to probe the hash in the root position, at least take the hash move and put it as the best move. It doesn't matter if you know the score for the position if you don't know what move to play!

You're right. A single line of code avoiding hash probes on the root node and there are no more illegal moves.

One quick question: when you get an EXACT TT hit, do you stuff the current PV moves into the PV and back that up along with the TT score? That is an easy thing to forget, once you are used to your q-search backing up the PV as a normal part of what it does. But when you get an EXACT TT hit, you stop the search immediately and you have to manually save the moves in the current path to create a "short PV". Short, because it does not show the entire line leading to the score, just the PV that leads to the TT hit but nothing beyond...

I forgot to do that. I shouldn't miss that point.

Thanks everybody for the answers. The problem is now solved.

[bob]

Did you read my whole post?? Specifically this part:

I bring it up also because it elegantly solves the problem that Bob brought up. When the fifty move counter gets close to fifty, he runs through the hash table and invalidates old entries. Here's a better way to do this:

Code: Select all

if (fifty_count < 80) /* I.e. less than 40 reversible moves */
    path_hashkey = hashkey; /* No change, we can just accept cutoffs regardless of path */
else
    path_hashkey = hashkey ^ some_constant; /* If we are getting close to 50, then only accept cutoffs from newer searches, BUT, still use the hash move */

You can take this even further, and make the last line:

Code: Select all

path_hashkey = hashkey ^ some_constant[fifty_count - 80];

So that when the fifty move count is big, we only accept searches with the exact same fifty count.

The _only_ place this has any effect is when the fifty move counter gets big, which is the same place where you blindly invalidate the whole hash table.

As I said, I do not "blindly invalidate the whole table". The primary use for hash entries is to carry move ordering information around, and that _never_ gets invalidated. I have a flag that says "best move is good, score is invalid" which I use about 10 moves in front of the 50 move rule barrier.

But you were also proposing to use this elsewhere as well for 3-fold repetitions and that is something that sounds like a bad idea, without having tested it of course...

[Zach Wegner]

As I said, I do not "blindly invalidate the whole table". The primary use for hash entries is to carry move ordering information around, and that _never_ gets invalidated. I have a flag that says "best move is good, score is invalid" which I use about 10 moves in front of the 50 move rule barrier.

Please Bob, read it again. What I propose as a solution to your problem allows you to use the hash table for move ordering everywhere, but, when the fifty move counter gets big and starts to be a problem, only allow cutoffs from entries where the fifty move counter was the same. Which makes your approach look pretty blind in comparison, as well as inefficient because of having to run through the entire hash table...

But you were also proposing to use this elsewhere as well for 3-fold repetitions and that is something that sounds like a bad idea, without having tested it of course...

That is one implementation of it. I know that it hurts overall, I tested it. I thought at least that it was an interesting idea. The only reason I brought it up at all was to help you specifically by showing you a better way to solve your problem.

I know now not to bother anymore. Sorry for wasting your time Bob...

[bob]

As I said, I do not "blindly invalidate the whole table". The primary use for hash entries is to carry move ordering information around, and that _never_ gets invalidated. I have a flag that says "best move is good, score is invalid" which I use about 10 moves in front of the 50 move rule barrier.

Please Bob, read it again. What I propose as a solution to your problem allows you to use the hash table for move ordering everywhere, but, when the fifty move counter gets big and starts to be a problem, only allow cutoffs from entries where the fifty move counter was the same. Which makes your approach look pretty blind in comparison, as well as inefficient because of having to run through the entire hash table...

OK, let me try once more. I understood what you wrote. You are proposing to maintain a second "signature" that is path-based rather than position-based. OK. It isn't free to do this as it is done _everywhere_ in the tree, thru the entire game. It has some sort of cost.

I run thru the hash table once, after the 50-move rule counter passes the 40-move threshold. That has a cost, but it is only incurred on those very rare occasions where a 50-move draw is an issue. My approach has zero affect for 99% of the games, 99% of the moves within each of those games.

That was my point. There is a cost incurred in your approach. If you further try to use it to handle repetitions, there is a much larger cost involved, because that is not confined to positions near a 50-move draw.

As I mentioned, I don't worry about repetition issues anyway, and am not seeing any issues at all since I count all 2-fold repetitions as draws inside the search anyway. 50-move rule draws are an issue and my approach has prevented me from stumbling into 50-move draws blindly, although one could argue that Crafty might well "commit" to a path that leads to a 50-move draw, well before move 40, because the hash table entries concealed the draw score since they had not yet been cleared. I've not seen that happen in testing, although I only looked at this when I was specifically looking at bogus draw issues in a version of Crafty last year...

I would speculate that my overhead is far less than what you are proposing with the new signature overhead that is incurred everywhere.

But you were also proposing to use this elsewhere as well for 3-fold repetitions and that is something that sounds like a bad idea, without having tested it of course...

That is one implementation of it. I know that it hurts overall, I tested it. I thought at least that it was an interesting idea. The only reason I brought it up at all was to help you specifically by showing you a better way to solve your problem.

I know now not to bother anymore. Sorry for wasting your time Bob...

I'm not sure why the attitude has to pop up here. You proposed an idea. I don't agree with it. That is grounds to cop an attitude? It is doubtful that I will agree with everything anyone says. Does everyone then cop an attitude about it? You didn't agree with my assessment... did I cop an attitude as a result?

I don't think your proposed solution is a reasonable approach. End of story unless you find a better way to convince me, or change things so that the issues I mentioned become insignificant. But I'm not going to get snotty if you don't agree with me, you are certainly free to test anything you want, good or bad. I've tried more than my share of bad ideas I have come up with, and I suspect I will come up with more that are bad in the future.

It is possible to have discussions, and disagreements, without sarcasm and attitude however. But only if you _want_ to in the first place.

[Zach Wegner]

OK, let me try once more. I understood what you wrote. You are proposing to maintain a second "signature" that is path-based rather than position-based. OK. It isn't free to do this as it is done _everywhere_ in the tree, thru the entire game. It has some sort of cost.

I run thru the hash table once, after the 50-move rule counter passes the 40-move threshold. That has a cost, but it is only incurred on those very rare occasions where a 50-move draw is an issue. My approach has zero affect for 99% of the games, 99% of the moves within each of those games.

That was my point. There is a cost incurred in your approach. If you further try to use it to handle repetitions, there is a much larger cost involved, because that is not confined to positions near a 50-move draw.

As I mentioned, I don't worry about repetition issues anyway, and am not seeing any issues at all since I count all 2-fold repetitions as draws inside the search anyway. 50-move rule draws are an issue and my approach has prevented me from stumbling into 50-move draws blindly, although one could argue that Crafty might well "commit" to a path that leads to a 50-move draw, well before move 40, because the hash table entries concealed the draw score since they had not yet been cleared. I've not seen that happen in testing, although I only looked at this when I was specifically looking at bogus draw issues in a version of Crafty last year...

I would speculate that my overhead is far less than what you are proposing with the new signature overhead that is incurred everywhere.

OK, I think we are getting somewhere here. The important thing that I was trying to tell you is that you don't have to give up the transpositions in the rest of the tree, it is possible to only worry about the 50 move rule. Specifically, the cost of my approach is non-zero, but it is constant throughout the game. This is the only code you need to add:
Inside make_move:

Code: Select all

if (fifty_count < 80)
    path_hashkey = hashkey;
else
    path_hashkey = hashkey ^ some_constant[fifty_count - 80];

...with an equivalent restoration in unmake.

In hash_store:

Code: Select all

hash_entry->hashkey = (hashkey & low_order_bits) | (path_hashkey & high_order_bits);

In hash_probe:

Code: Select all

if ((hash_entry->hashkey & low_order_bits) == (hashkey & low_order_bits))
{
    hash_move = hash_entry->move;
    /* This will only fail when the fifty move count gets high: */
    if ((hash_entry->hashkey & high_order_bits) == (path_hashkey & high_order_bits))
    {
        accept_cutoffs();
    }
}

So yes, the cost is nonzero. But it is a very small linear cost, and doesn't depend on the size of the hash table. You'd maybe lose 1% in NPS, if that even. The important thing is that you can accept cutoffs more intelligently in the late endgame. For instance, if the fifty move counter at the root is 30, and you search 20 plies deep, there will be many hash entries that will be affected by the fifty move rule. You would accept these for cutoffs, as long as the counter at the root is less than 40, whereas my method would only accept them up to the tenth ply, where after it would require hash entries to match the fifty move counter in addition to the position. Additionally, once the fifty counter at the root had reached 40, you would not accept cutoffs from any entry in the hash table, even though many of them are still valid.

It probably won't make a difference, especially considering how little the 50 move draw ever comes up. But I thought you might want to try it out...

I'm not sure why the attitude has to pop up here. You proposed an idea. I don't agree with it. That is grounds to cop an attitude? It is doubtful that I will agree with everything anyone says. Does everyone then cop an attitude about it? You didn't agree with my assessment... did I cop an attitude as a result?

I don't think your proposed solution is a reasonable approach. End of story unless you find a better way to convince me, or change things so that the issues I mentioned become insignificant. But I'm not going to get snotty if you don't agree with me, you are certainly free to test anything you want, good or bad. I've tried more than my share of bad ideas I have come up with, and I suspect I will come up with more that are bad in the future.

It is possible to have discussions, and disagreements, without sarcasm and attitude however. But only if you _want_ to in the first place.

I'm sorry if I come off as rude. I don't really mean it. I know that it's a bad idea to store path information, but it sounded nice when I thought of it. The idea didn't work out though, and I planned to just not say anything about it, like many other ideas that I have had (some of them good...). But I thought it might help you. It's fine if you don't like it, but you were only arguing against an idea that I already knew was bad, not the one that I was trying to propose to you. It didn't seem like you were listening to me at all.

I've just been frustrated with computer chess in general lately. I work so hard, and try to contribute _something_, but everybody just wants to argue about meaningless implementation details. Nobody cares about new ideas anymore, they just care about ELO. More people flock to test the latest stupid Toga fork than to take the time to look at a new engine. The one testing group that has touched my engine in the month that it has been released had a horribly incorrect setup (which could have been solved by looking at the readme), which caused it to lose every game as black. They didn't even notice, and I got no reply when I told them about it. The rating is still there.

Sorry to rant to you, but the past few weeks have been making me seriously considering giving up CC for good...

[bob]

OK, let me try once more. I understood what you wrote. You are proposing to maintain a second "signature" that is path-based rather than position-based. OK. It isn't free to do this as it is done _everywhere_ in the tree, thru the entire game. It has some sort of cost.

I run thru the hash table once, after the 50-move rule counter passes the 40-move threshold. That has a cost, but it is only incurred on those very rare occasions where a 50-move draw is an issue. My approach has zero affect for 99% of the games, 99% of the moves within each of those games.

That was my point. There is a cost incurred in your approach. If you further try to use it to handle repetitions, there is a much larger cost involved, because that is not confined to positions near a 50-move draw.

As I mentioned, I don't worry about repetition issues anyway, and am not seeing any issues at all since I count all 2-fold repetitions as draws inside the search anyway. 50-move rule draws are an issue and my approach has prevented me from stumbling into 50-move draws blindly, although one could argue that Crafty might well "commit" to a path that leads to a 50-move draw, well before move 40, because the hash table entries concealed the draw score since they had not yet been cleared. I've not seen that happen in testing, although I only looked at this when I was specifically looking at bogus draw issues in a version of Crafty last year...

I would speculate that my overhead is far less than what you are proposing with the new signature overhead that is incurred everywhere.

OK, I think we are getting somewhere here. The important thing that I was trying to tell you is that you don't have to give up the transpositions in the rest of the tree, it is possible to only worry about the 50 move rule. Specifically, the cost of my approach is non-zero, but it is constant throughout the game. This is the only code you need to add:
Inside make_move:

Code: Select all

if (fifty_count < 80)
    path_hashkey = hashkey;
else
    path_hashkey = hashkey ^ some_constant[fifty_count - 80];

...with an equivalent restoration in unmake.

I don't believe that is enough. You are simply tying it to the 50 move counter at the time you store the position. You really need the _path_ encoded, not just the 50 move counter. Just because the position here is N moves from 50 moves doesn't say a lot about other similar positions at the same 50 move counter, because the paths _prior_ to the key position could be different and have earlier (or later) draws.

There was a dissertation published on this topic and how to fix it, but the cost is simply unbearable...

I will have to think about it a bit, but my first impression is that basing the secondary signature solely on the 50 move counter is not enough... It is certainly better than doing nothing. Whether it is better than invalidating the scores from previous searches (not previous iterations) is another question. And I suspect it still suffers from insufficient information to avoid all such draws by the 50 move rule.


[quote[]\\]

In hash_store:

Code: Select all

hash_entry->hashkey = (hashkey & low_order_bits) | (path_hashkey & high_order_bits);

In hash_probe:

Code: Select all

if ((hash_entry->hashkey & low_order_bits) == (hashkey & low_order_bits))
{
    hash_move = hash_entry->move;
    /* This will only fail when the fifty move count gets high: */
    if ((hash_entry->hashkey & high_order_bits) == (path_hashkey & high_order_bits))
    {
        accept_cutoffs();
    }
}

So yes, the cost is nonzero. But it is a very small linear cost, and doesn't depend on the size of the hash table. You'd maybe lose 1% in NPS, if that even. The important thing is that you can accept cutoffs more intelligently in the late endgame. For instance, if the fifty move counter at the root is 30, and you search 20 plies deep, there will be many hash entries that will be affected by the fifty move rule. You would accept these for cutoffs, as long as the counter at the root is less than 40, whereas my method would only accept them up to the tenth ply, where after it would require hash entries to match the fifty move counter in addition to the position. Additionally, once the fifty counter at the root had reached 40, you would not accept cutoffs from any entry in the hash table, even though many of them are still valid.

It probably won't make a difference, especially considering how little the 50 move draw ever comes up. But I thought you might want to try it out...

I'm not sure why the attitude has to pop up here. You proposed an idea. I don't agree with it. That is grounds to cop an attitude? It is doubtful that I will agree with everything anyone says. Does everyone then cop an attitude about it? You didn't agree with my assessment... did I cop an attitude as a result?

I don't think your proposed solution is a reasonable approach. End of story unless you find a better way to convince me, or change things so that the issues I mentioned become insignificant. But I'm not going to get snotty if you don't agree with me, you are certainly free to test anything you want, good or bad. I've tried more than my share of bad ideas I have come up with, and I suspect I will come up with more that are bad in the future.

It is possible to have discussions, and disagreements, without sarcasm and attitude however. But only if you _want_ to in the first place.

I'm sorry if I come off as rude. I don't really mean it. I know that it's a bad idea to store path information, but it sounded nice when I thought of it. The idea didn't work out though, and I planned to just not say anything about it, like many other ideas that I have had (some of them good...). But I thought it might help you. It's fine if you don't like it, but you were only arguing against an idea that I already knew was bad, not the one that I was trying to propose to you. It didn't seem like you were listening to me at all.

I've just been frustrated with computer chess in general lately. I work so hard, and try to contribute _something_, but everybody just wants to argue about meaningless implementation details. Nobody cares about new ideas anymore, they just care about ELO. More people flock to test the latest stupid Toga fork than to take the time to look at a new engine. The one testing group that has touched my engine in the month that it has been released had a horribly incorrect setup (which could have been solved by looking at the readme), which caused it to lose every game as black. They didn't even notice, and I got no reply when I told them about it. The rating is still there.

Sorry to rant to you, but the past few weeks have been making me seriously considering giving up CC for good...[/quote]

It will continue to have its ups and downs. Hopefully more ups, but only over the long term. Short-term can be ugly at times. Certainly not ugly enough to quit over however. Takes time to make progress...

[Zach Wegner]

I don't believe that is enough. You are simply tying it to the 50 move counter at the time you store the position. You really need the _path_ encoded, not just the 50 move counter. Just because the position here is N moves from 50 moves doesn't say a lot about other similar positions at the same 50 move counter, because the paths _prior_ to the key position could be different and have earlier (or later) draws.

There was a dissertation published on this topic and how to fix it, but the cost is simply unbearable...

I will have to think about it a bit, but my first impression is that basing the secondary signature solely on the 50 move counter is not enough... It is certainly better than doing nothing. Whether it is better than invalidating the scores from previous searches (not previous iterations) is another question. And I suspect it still suffers from insufficient information to avoid all such draws by the 50 move rule.

Why wouldn't it be enough? You already know that the position itself matches. If the fifty move counter is the same, why does the path that got there matter? It will still be a draw in the same number of moves.

The technique isn't perfect. It solves the 50 move counter to the same extent as your method, but it utilizes more information from the hash table. You could make it perfect with respect to fifty move draws by modifying the path component for every different value of the fifty counter, but that would kill efficiency everywhere else.

This technique is also very flexible. For instance, you can make the path component only different for every difference of 10 in the fifty move counter, which is the equivalent of clearing the hash table every 10 moves. Or you could make it the same for the first twenty moves, then the next ten, five, and so on. You can include as much or as little information as you like.

It will continue to have its ups and downs. Hopefully more ups, but only over the long term. Short-term can be ugly at times. Certainly not ugly enough to quit over however. Takes time to make progress...

Thanks, that's definitely true. I've gone on plenty of breaks, but I keep getting sucked back in. Right now it's very hard to take a break, I'm just not satisfied yet with what I have. I need to at the very least finish DTS. Thanks for listening to me though. There are some genuinely good people in CC...

[bob]

I don't believe that is enough. You are simply tying it to the 50 move counter at the time you store the position. You really need the _path_ encoded, not just the 50 move counter. Just because the position here is N moves from 50 moves doesn't say a lot about other similar positions at the same 50 move counter, because the paths _prior_ to the key position could be different and have earlier (or later) draws.

There was a dissertation published on this topic and how to fix it, but the cost is simply unbearable...

I will have to think about it a bit, but my first impression is that basing the secondary signature solely on the 50 move counter is not enough... It is certainly better than doing nothing. Whether it is better than invalidating the scores from previous searches (not previous iterations) is another question. And I suspect it still suffers from insufficient information to avoid all such draws by the 50 move rule.

Why wouldn't it be enough? You already know that the position itself matches. If the fifty move counter is the same, why does the path that got there matter? It will still be a draw in the same number of moves.

This is a "path issue". Not just a "distance to 50 moves from the current position" issue. the same position can be reached from two different paths that still have the same "distance to 50 moves" value. But two different paths mean different potential repetition circumstances.

In looking back thru some summaries I have when I was doing all the draw testing last year, the 50-move-rule was rarely an issue. Repetitions were _way_ more problematic, particularly when I was not counting 2-fold as a draw as I do now...

I would also hate to deal with the case where one path stores(position P(n) where P is the position, n is the exact 50-move counter) and another path reaches position P(q) (same position, different 50-move value but q > n) and I can't use the hash entry to recognize that they are essentially identical since the second way just took a more direct path to the same position rather than going down a path that was unnecessarily longer.

The technique isn't perfect. It solves the 50 move counter to the same extent as your method, but it utilizes more information from the hash table. You could make it perfect with respect to fifty move draws by modifying the path component for every different value of the fifty counter, but that would kill efficiency everywhere else.

This technique is also very flexible. For instance, you can make the path component only different for every difference of 10 in the fifty move counter, which is the equivalent of clearing the hash table every 10 moves. Or you could make it the same for the first twenty moves, then the next ten, five, and so on. You can include as much or as little information as you like.

No argument so long as you realize this is not a "final solution" which requires a true path hashing component. I believe that a good solution requires multiple pieces of information. Normal hash signature and search result. signature with full path information and remaining 50-move count, so that this could be used to overrule the actual score/bound if desired. I still suspect I would be tempted to ignore anything with a moves-to-50 value of 10 or greater, until I see a position where I need to avoid the 50-move counter farther back in the tree than that. I suspect such is possible, but I generally see 50 move cases in simple endings where a lot of checks are not available (rook endings are pretty rare 50 move cases but are ones where lots of checks could perhaps force a 50-move draw starting before the counter reaches 40 maybe...)

But in any case, I am not sure that just knowing the distance to 50 for a position is enough as it might hide critical information, whereas actual path information would solve it, although again I am not sure whether a path hash would be enough as opposed to the actual path itself...

However, this is not causing me to draw won endings or lose drawn endings at present, so it isn't worth a lot of effort since it isn't much of a problem. Repetitions are more serious, and _much_ more difficult to deal with

It will continue to have its ups and downs. Hopefully more ups, but only over the long term. Short-term can be ugly at times. Certainly not ugly enough to quit over however. Takes time to make progress...

Thanks, that's definitely true. I've gone on plenty of breaks, but I keep getting sucked back in. Right now it's very hard to take a break, I'm just not satisfied yet with what I have. I need to at the very least finish DTS. Thanks for listening to me though. There are some genuinely good people in CC...

In thinking about this a bit, I wonder if storing the 50-move counter would not be just as effective and at least provide a "hint" that things might not be what they seem to be. Then you could compare current 50 move counter to hash 50-move counter and use that to choose whether to use the entry or not via comparison for >= or <= or even a specific margin, rather than just knowing "not the same" or "same"...

[Zach Wegner]

In thinking about this a bit, I wonder if storing the 50-move counter would not be just as effective and at least provide a "hint" that things might not be what they seem to be. Then you could compare current 50 move counter to hash 50-move counter and use that to choose whether to use the entry or not via comparison for >= or <= or even a specific margin, rather than just knowing "not the same" or "same"...

Think about it again. My method can do mostly this, but without the computation overhead on probing. All you do is store the same hashkey for a range of fifty move values. What my method can't do, though, is compare the counters with an acceptable margin. You have to have hard bounds across which the counters cannot be considered equal.

It is quite possible to store the fifty move counter instead; it's basically the same idea. The reason I use a Zobrist key is to maximize information: I take the space for storing the path hashkey out of the normal hashkey. So I XOR in the regular hashkey to the path hashkey so that I get more bits to match against. And before you say anything, I know that collisions don't really matter.