Answers.Body: <p>You're over-complicating it to the extent it doesn't make sense. You don't change the size of used RAM by &quot;clearing&quot; an entry. Clearing an entry means zeroing or changing the value to something meaningless, not un-allocating RAM. I suggest reading how arrays work as your first step to understanding transposition tables.</p>
  
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2024-01-03T10:25:06.267Z
Answers.Text: I’m not sure I agree with you. 1. Deleting an entry object certainly can and does free up memory, even if the object was in an array. 2. Why would I ever want to set an entry to 0 or meaningless? 3. My Transposition Table is a Python dict so your comment on arrays isn’t very relevant. 4. TT by nature benefit from hash-able keys, so I’m not sure why one would ever want to use an array.
Answers.UserDisplayName: EdwardK
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2024-01-04T08:04:53.677Z
Answers.Text: It appears you have the mind and desire to engineer properly so I suggest eventually moving to another language like C/C++, because trying to do this in Python is like punching sand. Python is a very high-level language that hides what's going on underneath for simplicity. Your python dict is an array underneath. So are hash tables and any other contiguous allocation of ram. In most (all?) interpreted languages like python, a dictionary of objects is an array of 64-bit unsigned integers containing the address of each object located randomly in ram. cont....
Answers.UserDisplayName: Keith Downes
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2024-01-04T08:15:51.507Z
Answers.Text: Deleting a class frees the ram, but it doesn't free the 64-bit integer in the array. An array of classes is lunacy because of this. In a language like C++, we can hold the TT info itself where the reference information would be. You can do this too in Python, but only for native types like integers and floats (doesn't python use only floats underneath?) Anyway, hope this clears up some of your confusion. There's a lot more going on than what python leads you to believe.
Answers.UserDisplayName: Keith Downes
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2024-01-04T17:58:09.700Z
Answers.Text: I agree lower level languages are much better, I'm just using Python for fun. However re: the memory management, although the hashtable is an array of addresses, deleting an object replaces the hashtable index with a dummy entry so yes the ram is not inherently freed, but these indices can store new addresses or be released when the hashtable auto resizes (at least there's one benefit of Python). Ultimately storing fewer objects reduces memory overhead without sacrificing hits which was my goal, but appreciate you adding context and sharing the C++ implementation, explains the misunderstanding
Answers.UserDisplayName: EdwardK
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2024-01-02T09:45:20.103Z
Answers.LastActivityDate: 2024-01-02T09:45:20.103Z
Answers.UserDisplayName: Keith Downes
Answers.Body: <p>I do believe I have come up with an ugly but (hopefully) complete solution to your problem though. What you have to do is keep track of the first irreversible move in every line that happens in search and propagate it downwards to all descendent nodes (as an argument in search or through some global variable), then store that in the TT for those descendent nodes, on top of storing the number of irreversible moves.</p>
  <p>When you clear the TT of all the irrelevant positions, you can clear out all of the positions that don't have both the same number of irreversible moves and the same specific irreversible move made.</p>
  <p>ONE MINUTE LATER...</p>
  <p>After thinking, I just realized that this alone will allow still-valid positions to be removed; after one irreversible move is made, once another is played the stored move in your TT will be the old one instead of the current one and won't match up. This means you'll actually have to store <em>all</em> the irreversible moves in the TT from the ancestor line for every position then pop them off the stack at every iteration (unmanageable for higher depths), or somehow update the move in TT entries during future searches where the position is encountered again.</p>
  <p>Of those two options, the first is more viable but I feel that this entire idea may not be worth enough in performance to justify actually further muddying up your code.</p>
  
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2024-01-03T10:39:18.063Z
Answers.Text: Yes I believe your approach with some tinkering would allow us to minimize the number of entries stored to the fullest extent but certainly would not be worth the overhead (in both performance and development! Lol). Considering the search depth, I think the difference between this optimization and a simple counter would not be nearly as significant as the initial implementation. Although it would be interesting if nothing else to see this idea explored fully. Cheers
Answers.UserDisplayName: EdwardK
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2023-12-21T02:22:35.303Z
Answers.LastActivityDate: 2023-12-21T02:28:15.657Z
Answers.LastEditDate: 2023-12-21T02:28:15.657Z
Answers.UserDisplayName: Hank's back rank
Body: <p>What do most engines use as an eviction policy for their transposition tables? I have read plenty about replacement strategies for collisions or overflow, but not as much about actively reducing table size.</p>
  <p>My engine stores the number of irreversible moves made so far, namely pawn moves, captures, and castles, and purges all entries from the table that have fewer, meaning they can no longer be reached from the current board state. Even in positions where there are no pawn pushes or captures for an extended period, the chance of hits goes up significantly so the table always hovers around the same size, depending on depth.</p>
  <p>The memory footprint is drastically reduced and performance impact is negligible. Collisions go from rare to effectively non-existant. Am I overcomplicating it and the benefits are not worth the added complexity? I'm curious to know if any other engines implement this technique or what eviction strategy they use, if any.</p>
  
Comments.ContentLicense: CC BY-SA 4.0
Comments.CreationDate: 2023-12-13T14:57:54.580Z
Comments.Text: I'm not completely clear on what your question is, but it is basically standard for any engines with a TT to completely clear the transposition table after any irreversible move is made in the actual game. I'm pretty sure I haven't heard of storing the number of irreversible moves in the entries, since it's just faster to do what I said earlier.
Comments.UserDisplayName: Hank's back rank
Comments.ContentLicense: CC BY-SA 4.0
Comments.CreationDate: 2023-12-14T03:30:48.890Z
Comments.Text: So is that counter used for determining what action to take in the event of a collision? Or what do you mean by purging entries? Normally, the transposition is implemented in fixed sized arrays, so the memory footprint doesn't change based on the number of entries that are saved. I don't think engines usually spend time actively removing entries from the table outside of collisions.
Comments.UserDisplayName: Nelson O
Comments.ContentLicense: CC BY-SA 4.0
Comments.CreationDate: 2023-12-18T18:59:42.647Z
Comments.Text: @NelsonO The counter is used to keep track of which entries we can remove from the TT. I know most engines set a predetermined size and have replacement strategies for collisions when nearing full, but I assume that means some relevant entries could be replaced. If we use the fact that pawns can't move backwards and captures can't be undone, we can use that value to remove the entries we know 100% it will never be hit again
Comments.UserDisplayName: EdwardK
Comments.ContentLicense: CC BY-SA 4.0
Comments.CreationDate: 2023-12-18T19:02:24.917Z
Comments.Text: @Hank'sbackrank even after some irreversible move is made, there will still be some relevant entries in the TT though, so storing the value with the entry allows for selective clearing. Also clearing the table only occurs after the move is sent so the overhead is not as relevant. And my question is how do competitve engines perform TT clearing because the solution I came up with was on the fly, I'm curious if there is a more clever approach or if they have concluded it's not worth the complexity
Comments.UserDisplayName: EdwardK
Comments.ContentLicense: CC BY-SA 4.0
Comments.CreationDate: 2023-12-18T21:10:22.290Z
Comments.Text: Just a note, if you are only clearing entries with fewer irreversible moves than the current position, you will not be clearing other positions resulting from all the other different irreversible sister moves that were searched, or even positions resulting from  another branch irreversible moves from the past. Please clarify if I'm misunderstanding, since that seems like a large waste of TT space.
Comments.UserDisplayName: Hank's back rank
Comments.ContentLicense: CC BY-SA 4.0
Comments.CreationDate: 2023-12-20T20:18:16.063Z
Comments.Text: @Hank'sbackrank that's a great point! I had a similar thought, which is what made me wonder if there were optimizations out there. I concluded that with a fixed depth search, the # of positions resulting from separate move branches with similar # of irreversible moves will never branch out uncontrollably. Since only positions reachable from the current board are searched, those irrelevant positions won't be explored further and will eventually be pruned as the game progresses. The memory profile supported this, as the TT always hovered around 100k +/- 20k entries when searching 4 plies deep.
Comments.UserDisplayName: EdwardK
Comments.ContentLicense: CC BY-SA 4.0
Comments.CreationDate: 2023-12-21T02:13:01.477Z
Comments.Text: I would like to point out that a depth of 4 plies is very shallow and doesn't really allow you to accumulate that many deeper junk positions, so the issue may become more pronounced at higher depths.
Comments.UserDisplayName: Hank's back rank
Comments.ContentLicense: CC BY-SA 4.0
Comments.CreationDate: 2024-01-03T10:41:26.177Z
Comments.Text: Agreed, that note was to highlight how even as the game progressed (more total positions evaluated), the TT size never fluctuated too much.
Comments.UserDisplayName: EdwardK
Tags: <engines><programming><computer-chess><transpositions>
Title: Transposition Table eviction policy
ThreadText: # Transposition Table eviction policy
  
  (Asked by: username_0 on 2023-12-13)
  
  What do most engines use as an eviction policy for their transposition tables? I have read plenty about replacement strategies for collisions or overflow, but not as much about actively reducing table size.
  
  My engine stores the number of irreversible moves made so far, namely pawn moves, captures, and castles, and purges all entries from the table that have fewer, meaning they can no longer be reached from the current board state. Even in positions where there are no pawn pushes or captures for an extended period, the chance of hits goes up significantly so the table always hovers around the same size, depending on depth.
  
  The memory footprint is drastically reduced and performance impact is negligible. Collisions go from rare to effectively non-existant. Am I overcomplicating it and the benefits are not worth the added complexity? I'm curious to know if any other engines implement this technique or what eviction strategy they use, if any.
  
  **Tags:** engines, programming, computer-chess, transpositions
  
  > **Comments:**
  > **username_1**: I'm not completely clear on what your question is, but it is basically standard for any engines with a TT to completely clear the transposition table after any irreversible move is made in the actual game. I'm pretty sure I haven't heard of storing the number of irreversible moves in the entries, since it's just faster to do what I said earlier.  
  > **username_2**: So is that counter used for determining what action to take in the event of a collision? Or what do you mean by purging entries? Normally, the transposition is implemented in fixed sized arrays, so the memory footprint doesn't change based on the number of entries that are saved. I don't think engines usually spend time actively removing entries from the table outside of collisions.  
  > **username_0**: @NelsonO The counter is used to keep track of which entries we can remove from the TT. I know most engines set a predetermined size and have replacement strategies for collisions when nearing full, but I assume that means some relevant entries could be replaced. If we use the fact that pawns can't move backwards and captures can't be undone, we can use that value to remove the entries we know 100% it will never be hit again  
  > **username_0**: @Hank'sbackrank even after some irreversible move is made, there will still be some relevant entries in the TT though, so storing the value with the entry allows for selective clearing. Also clearing the table only occurs after the move is sent so the overhead is not as relevant. And my question is how do competitve engines perform TT clearing because the solution I came up with was on the fly, I'm curious if there is a more clever approach or if they have concluded it's not worth the complexity  
  > **username_1**: Just a note, if you are only clearing entries with fewer irreversible moves than the current position, you will not be clearing other positions resulting from all the other different irreversible sister moves that were searched, or even positions resulting from  another branch irreversible moves from the past. Please clarify if I'm misunderstanding, since that seems like a large waste of TT space.  
  > **username_0**: @Hank'sbackrank that's a great point! I had a similar thought, which is what made me wonder if there were optimizations out there. I concluded that with a fixed depth search, the # of positions resulting from separate move branches with similar # of irreversible moves will never branch out uncontrollably. Since only positions reachable from the current board are searched, those irrelevant positions won't be explored further and will eventually be pruned as the game progresses. The memory profile supported this, as the TT always hovered around 100k +/- 20k entries when searching 4 plies deep.  
  > **username_1**: I would like to point out that a depth of 4 plies is very shallow and doesn't really allow you to accumulate that many deeper junk positions, so the issue may become more pronounced at higher depths.  
  > **username_0**: Agreed, that note was to highlight how even as the game progressed (more total positions evaluated), the TT size never fluctuated too much.  
  
  ---
  
  ## 2 answers
  
  ### Answer by username_3 on 2024-01-02. Score: 2
  
  You're over-complicating it to the extent it doesn't make sense. You don't change the size of used RAM by "clearing" an entry. Clearing an entry means zeroing or changing the value to something meaningless, not un-allocating RAM. I suggest reading how arrays work as your first step to understanding transposition tables.
  
  > **Comments:**
  > **username_0**: I’m not sure I agree with you. 1. Deleting an entry object certainly can and does free up memory, even if the object was in an array. 2. Why would I ever want to set an entry to 0 or meaningless? 3. My Transposition Table is a Python dict so your comment on arrays isn’t very relevant. 4. TT by nature benefit from hash-able keys, so I’m not sure why one would ever want to use an array.  
  > **username_3**: It appears you have the mind and desire to engineer properly so I suggest eventually moving to another language like C/C++, because trying to do this in Python is like punching sand. Python is a very high-level language that hides what's going on underneath for simplicity. Your python dict is an array underneath. So are hash tables and any other contiguous allocation of ram. In most (all?) interpreted languages like python, a dictionary of objects is an array of 64-bit unsigned integers containing the address of each object located randomly in ram. cont....  
  > **username_3**: Deleting a class frees the ram, but it doesn't free the 64-bit integer in the array. An array of classes is lunacy because of this. In a language like C++, we can hold the TT info itself where the reference information would be. You can do this too in Python, but only for native types like integers and floats (doesn't python use only floats underneath?) Anyway, hope this clears up some of your confusion. There's a lot more going on than what python leads you to believe.  
  > **username_0**: I agree lower level languages are much better, I'm just using Python for fun. However re: the memory management, although the hashtable is an array of addresses, deleting an object replaces the hashtable index with a dummy entry so yes the ram is not inherently freed, but these indices can store new addresses or be released when the hashtable auto resizes (at least there's one benefit of Python). Ultimately storing fewer objects reduces memory overhead without sacrificing hits which was my goal, but appreciate you adding context and sharing the C++ implementation, explains the misunderstanding  
  
  ---
  
  ### Answer by username_1 on 2023-12-21. Score: 1
  
  I do believe I have come up with an ugly but (hopefully) complete solution to your problem though. What you have to do is keep track of the first irreversible move in every line that happens in search and propagate it downwards to all descendent nodes (as an argument in search or through some global variable), then store that in the TT for those descendent nodes, on top of storing the number of irreversible moves.
  
  When you clear the TT of all the irrelevant positions, you can clear out all of the positions that don't have both the same number of irreversible moves and the same specific irreversible move made.
  
  ONE MINUTE LATER...
  
  After thinking, I just realized that this alone will allow still-valid positions to be removed; after one irreversible move is made, once another is played the stored move in your TT will be the old one instead of the current one and won't match up. This means you'll actually have to store *all* the irreversible moves in the TT from the ancestor line for every position then pop them off the stack at every iteration (unmanageable for higher depths), or somehow update the move in TT entries during future searches where the position is encountered again.
  
  Of those two options, the first is more viable but I feel that this entire idea may not be worth enough in performance to justify actually further muddying up your code.
  
  > **Comments:**
  > **username_0**: Yes I believe your approach with some tinkering would allow us to minimize the number of entries stored to the fullest extent but certainly would not be worth the overhead (in both performance and development! Lol). Considering the search depth, I think the difference between this optimization and a simple counter would not be nearly as significant as the initial implementation. Although it would be interesting if nothing else to see this idea explored fully. Cheers  
  
  ---
  
  