Starting with Hash Tables.

[Luis Babboni]

As always, thanks Sven for your time and help no matter you think I doing it the wrong way.

But I see it like this:

I want to join two cities that have a forest in middle.
I start from one of them and I do not know exactly where is the other, just that is on the other side of the forest.
I decided to first make a narrow way cutting plants with my knife no matter in how tortuous way I do it. Once I´ll arrive to the other city (I think now I´m 80% near than when started) i´ll know better wich is the best path to join them and just then I´ll start an asphalt road. I think is better idea than start with the asphalt before even know the direction to point.


PS1: I could be wrong but this is the way I see it!
PS2: yes, the debugging is a nightmare.
PS3: actually your are guiding me about the direction I must point, in the future you will guide me about how to do the asphalt.
PS4: I think the fact that you know right where are the other city, is what not allow you to understad my point of view and see my way as a waste of time. You could not imagine how lost I am!

[Luis Babboni]

What about with 3rd repetitions?

As far as I understand, at least in my way to do it, the number that represents a position do not have information about how many times this position was reached. Actually I use it for this in fact, but not store that information in it.

I mean, if in a search I found a position that is repeated three times, I give score=0 (tie) to this position/parth because I do my 3rd repetition rule test before evaluate the position.

My question is what about if I found that position again but now in a circumstances that is not the 3rd time I reach it?
What you suggest me as first TT attempt, to directly not store that position to not give it a wrong evaluation for example?
Or to evaluate it no matter is a 3rd repetition the first time I found it and store in the TT that score?

Thanks.

[hgm]

This is a problem that everyone ignores, because any solution conceived so far is far worse than the problem itself.

[Sven]

What about with 3rd repetitions?

As far as I understand, at least in my way to do it, the number that represents a position do not have information about how many times this position was reached. Actually I use it for this in fact, but not store that information in it.

I mean, if in a search I found a position that is repeated three times, I give score=0 (tie) to this position/parth because I do my 3rd repetition rule test before evaluate the position.

My question is what about if I found that position again but now in a circumstances that is not the 3rd time I reach it?
What you suggest me as first TT attempt, to directly not store that position to not give it a wrong evaluation for example?
Or to evaluate it no matter is a 3rd repetition the first time I found it and store in the TT that score?

Thanks.

There is no perfect solution for this well-known problem. As you have stated correctly, evaluating a position as a draw due to repetition (3rd occurrence of the same position) is path-dependent. As far as I remember, some authors do not store draw scores in the TT at all. Others ignore the problem completely, based on the observation that usually there is no serious problem since the first repetition (second occurrence) of a position during search can already be evaluated as a draw (this is a known and correct simplification valid for tree search, not at the game-playing level of course).

[Luis Babboni]

Thanks guys!

[Luis Babboni]

...
- the draft, or remaining depth, to which the position was searched,
...

Wich is here the usual way to consider this?
I´m asking about how to deal with extensions.
Suppouse I searching till depth 8 but I found a branch extended 2 plies more to depth 10.

How I stored the "draft" of a position found at depth 5?
a) as 3 cause 8-5=3 or b) as 5 cause 10-5=5.

How I stored the "draft" of a position found at depth 9?
a) as -1 cause 8-9=-1 or b) as 1 cause 10-9=1.

I bet for options a) but will like some comments about it.

Thanks!

[Sven]

...
- the draft, or remaining depth, to which the position was searched,
...

Wich is here the usual way to consider this?
I´m asking about how to deal with extensions.
Suppouse I searching till depth 8 but I found a branch extended 2 plies more to depth 10.

How I stored the "draft" of a position found at depth 5?
a) as 3 cause 8-5=3 or b) as 5 cause 10-5=5.

How I stored the "draft" of a position found at depth 9?
a) as -1 cause 8-9=-1 or b) as 1 cause 10-9=1.

I bet for options a) but will like some comments about it.

Thanks!

You always store the draft that your search function got as "remaining depth" parameter for that position, even if some lines of the subtree were extended.

So there is no fixed answer to both of your examples since it depends on the depth at which the extensions occurred. But you don't need to think about it at all, my first sentence is sufficient for you. I'll just explain why this is true. In the following explanation I'll assume you are in iteration 8, i.e. the nominal max depth is 8.

1) If you are at ply 5 from root and there was no extension yet on the path from root to current node then you search this node with a remaining depth of 8-5=3. Even if that subtree will have some lines extended (e.g. check extension), the nominal depth is 3, so before returning from this node you store the position with a draft of 3.

2) If you are at ply 5 from root and there were already extensions of two plies on the path from root to current node then you search this node with a remaining depth of 8+2-5=5, so at the end you will store the position with draft=5.

3) If you are at ply 9 from root then there must have been at least an extension of 1 ply. Apart from that I can't tell you anything new about this case.

[Luis Babboni]

Thanks Sven, I think I understood you!

[Luis Babboni]

...
But it is in general true that part of the positions in the table become unreachable by a move in the root. Then, if you are not doing analysis (in which you also take back moves) but are playing a game, these are useless.

People handle this by including an 'age field' in the TT entire. E.g. you can increment a counter for each search you start from the root, and store that in any entry you successfully access (probe hit or write). Then when you hit upon entries with an age field much lower than the current search number, they are likely to be useless, and you can preferentially overwrite those.

Nevertheless after near each new engine version it becomes less significative, I still use random in the order of studying moves. This allows the engine to not start always in the same way even no having any openbook.
This is making choicing by random the number ID of each piece and the number ID of each movement of each piece. At equal move ordering level, I allways start from piece of low number ID and lower move ID out of all of that move ordering level, but them are not always the same. I take a new random values each time is Soberango turn to move.

1st point: if I want to use TT entries from previous turns (hgm saids: "...when you hit upon entries with an age field much lower than the current search number, they are likely to be useless..." ) not just "lower", I need to not use that random at least till a pawn move or a capture, when all TT entries become useless.
I´m correct? I mean, kept the previous turns TT entries is important part of have TTs, I´m right? Not just the actual searching results stored in TT are important?

EDIT: I think I have a not too much time consuming way to kept random and previous turn TT entries but the questions are still important for me.

2nd point: about that "much lower" I thought in a way to define how much is much enough to know a TT entrie is useless without no doubts. I just need two bytes for age entry, one for pawns positions and other for number of pieces. Is this limit too high? How much is "much lower" a good parameter?

Thanks!

[Sven]

...
But it is in general true that part of the positions in the table become unreachable by a move in the root. Then, if you are not doing analysis (in which you also take back moves) but are playing a game, these are useless.

People handle this by including an 'age field' in the TT entire. E.g. you can increment a counter for each search you start from the root, and store that in any entry you successfully access (probe hit or write). Then when you hit upon entries with an age field much lower than the current search number, they are likely to be useless, and you can preferentially overwrite those.

Nevertheless after near each new engine version it becomes less significative, I still use random in the order of studying moves. This allows the engine to not start always in the same way even no having any openbook.
This is making choicing by random the number ID of each piece and the number ID of each movement of each piece. At equal move ordering level, I allways start from piece of low number ID and lower move ID out of all of that move ordering level, but them are not always the same. I take a new random values each time is Soberango turn to move.

1st point: if I want to use TT entries from previous turns (hgm saids: "...when you hit upon entries with an age field much lower than the current search number, they are likely to be useless..." ) not just "lower", I need to not use that random at least till a pawn move or a capture, when all TT entries become useless.
I´m correct? I mean, kept the previous turns TT entries is important part of have TTs, I´m right? Not just the actual searching results stored in TT are important?

EDIT: I think I have a not too much time consuming way to kept random and previous turn TT entries but the questions are still important for me.

2nd point: about that "much lower" I thought in a way to define how much is much enough to know a TT entrie is useless without no doubts. I just need two bytes for age entry, one for pawns positions and other for number of pieces. Is this limit too high? How much is "much lower" a good parameter?

Thanks!

You simply keep all TT entries unless they are overwritten. If your TT has just one entry per index then you have no choice, you always overwrite. With more than one entry per index (typical is four) you define a replacement strategy for the case that all entries for the given index are in use (otherwise you use one of the free entries for that index). Only at that point, i.e. for the replacement strategy, the "age" becomes relevant.

As I already told you in the past, I still suggest that you drop your "random" implementation on the move ordering level. You gain
1) reproducible behaviour of your search (important for debugging) and
2) better performance (since a random component in move ordering will often have a negative impact on tree size).
Avoiding to always repeat the same opening moves is only important if you play many games against the same opponent. Different opponents will usually play different opening moves at some point in time. Playing many games against the same opponent is the typical scenario when you test your own engine by playing many games with short time control. There you should use a more or less large set of starting positions, otherwise you would get misleading results. So even here you don't really need a random component in your search.