Starting with Hash Tables.

[Luis Babboni]

Mmmm, now I´m not sure I understand the idea for hash tables, but at least suggested me an idea about how to take advantage of transpositions.
I´ll try to explain it and please say me how right or wrong I´m am.

Starting from this position:

k in E8
K in E1
P in E2
White turn to move.

After 3 plies, I count 210 possible sequences of moves but just 130 possible end positions.
If i have a list of positions my engine are analyzing, each time after a move it found a position just analyzed, it directly could jump to next move without need to continue more depth from there.
This way, in this particular case, it is needed to analyze just 62% (130/210) of the moves I need to analyze without that list.

Any comment that can help me?

Thanks!

[Sven]

Mmmm, now I´m not sure I understand the idea for hash tables, but at least suggested me an idea about how to take advantage of transpositions.
I´ll try to explain it and please say me how right or wrong I´m am.

Starting from this position:

k in E8
K in E1
P in E2
White turn to move.

After 3 plies, I count 210 possible sequences of moves but just 130 possible end positions.
If i have a list of positions my engine are analyzing, each time after a move it found a position just analyzed, it directly could jump to next move without need to continue more depth from there.
This way, in this particular case, it is needed to analyze just 62% (130/210) of the moves I need to analyze without that list.

Any comment that can help me?

Thanks!

The basic idea of a transposition table (TT) is close to what you have written above. You save work by avoiding to repeat an identical tree search. In your example, when doing a 6-ply search from the given position (and while ignoring alpha-beta for a moment!) there would be 210 nodes after 3 plies which would need to be searched another 3 plies deep. 130 of them would actually be searched and for the other 80 you would take the score from the TT since the same position had already been reached through a different move sequence (e.g. 1. e3 Ke7 2. Kf2 and 1. Kf2 Ke7 2. e3 lead to the same position).

But that is only one aspect of using a TT. The other, more important aspect is that you also store the best move that was found when searching a position. Say you have completed your 6-ply search and start the next iteration, now searching 7 plies deep. You will now visit again those 210 "ply 3 from root" positions (ok: in fact much less with alpha-beta but as I said, let's ignore that here) and want to obtain search results for searching another 4 plies from there. Here you can't just take the TT score and return, since that was found by searching only 3 plies deep from each of those 210 positions (you record the search depth in the TT together with the score). But you can take the "best move" stored in the TT entry as well and use it for move ordering: try that move first, even prior to winning captures, since it is very likely that it is a strong move. The observation is that the strength improvement from using the TT move for move ordering is huge, usually more than the "transposition" aspect of saving duplicate work.

[Luis Babboni]

...
But that is only one aspect of using a TT. The other, more important aspect is that you also store the best move that was found when searching a position. Say you have completed your 6-ply search and start the next iteration, now searching 7 plies deep. You will now visit again those 210 "ply 3 from root" positions (ok: in fact much less with alpha-beta but as I said, let's ignore that here) and want to obtain search results for searching another 4 plies from there. Here you can't just take the TT score and return, since that was found by searching only 3 plies deep from each of those 210 positions (you record the search depth in the TT together with the score). But you can take the "best move" stored in the TT entry as well and use it for move ordering: try that move first, even prior to winning captures, since it is very likely that it is a strong move. The observation is that the strength improvement from using the TT move for move ordering is huge, usually more than the "transposition" aspect of saving duplicate work.

Mmmm, sorry, I do not not understand.
One aspect of iterative deepening, as far as I understood, is that the time needed to study plies 1 to n-1 are far less than time needed to study ply n. So not sure what you tried to say me (please be sure I´m not understood cause my poor knowledge and poor english, not cause other reason) but the only place where I could gain time is in depth n search. I´m wrong?
And about how to gain time in depth n search, actually my engine start by best move found in ply n-1, that´s was the idea of iterative deepening I understand. I do not need any table for this.

What idea I´m missing?

Mmmm, you mean use the best move at each depth of depth n search or something like this?

[Robert Pope]

Mmmm, sorry, I do not not understand.
...
And about how to gain time in depth n search, actually my engine start by best move found in ply n-1, that´s was the idea of iterative deepening I understand. I do not need any table for this.

What idea I´m missing?

Mmmm, you mean use the best move at each depth of depth n search or something like this?

That gives you the best move at the first ply.

Hash table also gives you the opponent's best reply, etc., so that potentially, you already know the best move at each branch of the tree, and you will get far more cutoffs because you search these first as well.

[Sven]

...
But that is only one aspect of using a TT. The other, more important aspect is that you also store the best move that was found when searching a position. Say you have completed your 6-ply search and start the next iteration, now searching 7 plies deep. You will now visit again those 210 "ply 3 from root" positions (ok: in fact much less with alpha-beta but as I said, let's ignore that here) and want to obtain search results for searching another 4 plies from there. Here you can't just take the TT score and return, since that was found by searching only 3 plies deep from each of those 210 positions (you record the search depth in the TT together with the score). But you can take the "best move" stored in the TT entry as well and use it for move ordering: try that move first, even prior to winning captures, since it is very likely that it is a strong move. The observation is that the strength improvement from using the TT move for move ordering is huge, usually more than the "transposition" aspect of saving duplicate work.

Mmmm, sorry, I do not not understand.
One aspect of iterative deepening, as far as I understood, is that the time needed to study plies 1 to n-1 are far less than time needed to study ply n. So not sure what you tried to say me (please be sure I´m not understood cause my poor knowledge and poor english, not cause other reason) but the only place where I could gain time is in depth n search. I´m wrong?
And about how to gain time in depth n search, actually my engine start by best move found in ply n-1, that´s was the idea of iterative deepening I understand. I do not need any table for this.

What idea I´m missing?

Mmmm, you mean use the best move at each depth of depth n search or something like this?

You misunderstood what I meant by "you store the best move that was found when searching a position". I was not talking about the best move at the root node only. I meant that you always store the best move in the hash table, for each position during search. Iterative deepening starts to really become effective that way, since without it you still do a lot of useless work that can be avoided by better move ordering. You store the move before returning control to the parent node. A typical hash table entry of a chess engine contains most or all of the following information:

- the hash key itself, or at least a part of it (to make sure that the entry actually belongs to the given position and not to a different one which has the same lower N bits that are used as table index),
- the score,
- the type of the score (exact score, lower bound, or upper bound),
- the draft, or remaining depth, to which the position was searched,
- the best move,
- and often some other information that can be useful for the replacement strategy.

So if there was a best move available when storing information in the TT then it can be used especially for move ordering during the next iteration.

[Luis Babboni]

Thanks guys, I become to understand better.

[Luis Babboni]

More questions:

1-For sure after each pawn move or capture, the previous hash tables are useless and in this cases you could forgot it and restart it again.
Or the usual way to use it is directly clear or overwrite it after each move?

2-How many bytes is logical to use for each position and the corresponding asociated values?

I hope I do not ask a nosense.

[hgm]

If you are lucky the hash table contains the entire tree. Also the part of the tree after the Pawn move or capture. So if you make such a move in the root, it is not the entire hash table that becomes useless. In fact the sub-trees of many other moves could still remain usefull, because they did that same Pawn push or capture on a later ply, and you can still transpose into these lines.

But it is gin 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.

[Luis Babboni]

Yeap, of course you are right. I make mistakes with the ideas. If a pawn is moved in ply 2, the subtree that have this pawn move as root is still usefull.

What about how many bytes for each entrie in the TT?

Another thing too much important in wich I did not thought before... when I have the number that identifies the actual position.... the time consumming searching if the same number is or not into the TT, forbide it use as I think the things right now. I need to read more about it!
Mmmm, I think the number identifies the position, must give you too its place in the TT if you do not want to waste ages trying to find it.

[Luis Babboni]

I´m Reading this!:
http://mediocrechess.blogspot.com.ar/20 ... ables.html
More questions later.

Note: so intrigued about why is a .com.ar (argentine) website!!