Re: [computer-go] Hash tables
On Jul 6, 2009, at 10:09 PM, Peter Drake wrote: I suppose I could also include first child / next sibling pointers. I wouldn't actually use them when performing playouts, but they would greatly speed up the mark phase of marking and sweeping. Hmm. That would work for a tree, but this is a DAG. Consider this situation: A / \ B C \ / \ D E (For simplicity, ignore the fact that an actual transposition must be at least three moves long.) Here D can be reached from either B or C, but E can only be reached from C (perhaps due to ko). With first-child/next-sibling pointers, that might look like this: A | B-C |/ D-E If we then actually move to B and try to keep the tree, we'll end up keeping E, even though it's really an unreachable node. That's probably acceptable: we can keep a few unreachable nodes, as long as we keep all of the real ones. There might be another problem, though. Suppose, from the situation above, I add F and G as children of B: A | B-C | \ F-G-D-E Later, I discover that F is also a child of C. I look through C's apparent children (D and E) and discover that F is not among them. How do I add F to the list of C's children without some serious list traversal (and surgery)? Perhaps a better solution is for each node to point to a linked list of its children. The nodes in these lists (allocated from a pool at load time, naturally) would each point to a search tree node and the next list node. Peter Drake http://www.lclark.edu/~drake/ ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
Re: [computer-go] Hash tables
On Thu, Jul 2, 2009 at 7:20 PM, Peter Drake dr...@lclark.edu wrote: Okay, so I've finally built a transposition table. There is a big pool of nodes, allocated at startup. To find a node, I: 1) Play the move on the board and get the new Zobrist hash (incorporating the simple ko point and color to play). 2) Take this modulo the length of the table (currently 128K nodes) to find the first place to probe. I assume you mean exactly 131072, a power of two? Then modulo is a bit masking operation. The classic algorithm is to use a prime number table size, and I think this idea of using a power of 2 table size and bit masking was started in the old days when division was horribly expensive. Just about every game program I'm aware of using the power of two table size with a simple mask to calculated the first address to use. 3) Linearly probe (i.e., try the next location, then the next one, etc.) until either I find a node with the correct Zobrist hash or hit the limit on the number of probes (1024 seems to work okay). 4) In situations where I'm trying to allocate a node, if I didn't find one that matched, I overwrite the first old node I encountered. An old node is one that wasn't touched on the previous turn (as indicated by a timestamp). If I didn't find an old node, the allocation fails. This is the best way I think.It's silly to traverse the whole table and clear it before each move if you can spare a few extra bits. Even 2 or 3 bits for this timestamp is enough. Of course that is the only downside, you do need a few extra bits and you want to keep the records as small as reasonably possible. You have the added advantage that you can still use nodes from previous searches - but of course you would update the time stamp whenever you did this. This works all right, but I'm bothered by the tension between a low probe limit (speeding up unsuccessful searches) and a high one (making more complete use of the table). Also, the table tends to fill up. Questions for others: a) Are you using this timestamp trick, or are you traversing your DAG to mark which nodes are still relevant every time you accept a (real, non-playout) move? I realize that almost none of the nodes touched last turn are still relevant, but traversing the entire table seems expensive. In Lazarus I did not use a transposition table, just a tree of nodes. However I did go to some trouble between moves to do something, I forgot what it was exactly. But I remember the principal idea was to save important parts of the tree from one search to the next one. Also I did not use standard garbage collection, I created a pool of nodes and managed this myself, no memory allocations, no free() b) Is there some clever way to abandon an unsuccessful search earlier? In a hash table that wasn't full or close to it, I'd go until I found a null (i.e., a node that had never been used, as opposed to a node that is old or marked for deletion). Unfortunately, Orego fills up the table of 128k nodes in a matter of seconds. c) Is there some useful way of rehashing to get rid of the old nodes? Unfortunately, I can't fit a second copy of the table in memory... I'll be looking forward to the response as I don't know how others do this. But I know the good programs all have some kind of scheme to reuse nodes that are not proving to be particularly relevant to the current search. - Don Thanks, Peter Drake http://www.lclark.edu/~drake/ http://www.lclark.edu/%7Edrake/ ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/ ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
Re: [computer-go] Hash tables
Considering that memory keeps getting cheaper, would it make sense to dynamically choose how much space to use? Nowadays most new computer purchasers start with 2 GB, and go up from there. Terry McIntyre terrymcint...@yahoo.com “We hang the petty thieves and appoint the great ones to public office.” -- Aesop From: David Fotland fotl...@smart-games.com To: computer-go computer-go@computer-go.org Sent: Sunday, July 5, 2009 9:05:45 PM Subject: RE: [computer-go] Hash tables The hash table contains a linked list of nodes with the same hash index. Your description is pretty close, but I don't remember the exact details. Yes, I keep around some nodes for while, but eventually old nodes go into the past and can be recovered. I actually have fewer total nodes than you do. The commercial version allocates 30K nodes per CPU core. The version in the world championship had much more, but the commercial version can't be that greedy for memory. David I give up when there are no nodes that area available to be overwritten. I'm still a little confused. First, does the hash table contains pointers into a node pool, or do you use the node pool as the hash table? Second, how and when do you determine which nodes (if any) are available for overwriting, without doing some sort of traversal? Is the following a correct summary of what you do when it's time to create a new node? Go to the one node that would be used for this Zobrist hash. If the same hash is stored there, use the existing node. If not, either overwrite this node (if this node is available for overwriting) or not create a new node (otherwise). Also, what exactly is the criterion for overwriting? You said nodes that have few visits or are old. Is this just (visits visitThreshold) || (depthFromBeginningOfGame currentGameTurn)? Doesn't depthFromBeginningOfGame cause you to keep around nodes that are outside the still-relevant branch of the tree (i.e., the branch descending from the current root), almost all of which are irrelevant? If the search is long enough, there are no nodes that can be recovered, and the UCT tree stops growing. I keep searching when there are no reusable nodes. ...because this improves the quality of information in the nodes you were able to create. That makes sense. Thanks, Peter Drake http://www.lclark.edu/~drake/ ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/ ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/ ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
Re: [computer-go] Hash tables
The problem with making it dynamic with respect to how much memory is available is that this does not play well with other software. Since modern operating systems are designed for multiple processes, you don't want the amount allocated to be a function of which program got loaded first. Can you imagine testing 2 GO programs designed this way? The first program which happened to get loaded would suck up all the memory.Or even if it grabbed half the memory, the other program might also grab half of what was left.This would give an unfair advantage to one program over the other based solely on which got loaded first. What makes the most sense is to have a modest default size, but make the amount of memory used user configurable. If you take the point of view that the end user isn't smart enough to make those decisions, you might set it to be some modest fraction of the size of the TOTAL memory installed in the computer, but I think this is still dicey. With these caveats explained to the end user, you could have a special mode they have to activate, which causes the program to allocate as much as possible with the understanding that this mode is for dedicated play - it assumes the computer is not being used for anything else. - Don 2009/7/6 terry mcintyre terrymcint...@yahoo.com Considering that memory keeps getting cheaper, would it make sense to dynamically choose how much space to use? Nowadays most new computer purchasers start with 2 GB, and go up from there. Terry McIntyre terrymcint...@yahoo.com “We hang the petty thieves and appoint the great ones to public office.” -- Aesop -- *From:* David Fotland fotl...@smart-games.com *To:* computer-go computer-go@computer-go.org *Sent:* Sunday, July 5, 2009 9:05:45 PM *Subject:* RE: [computer-go] Hash tables The hash table contains a linked list of nodes with the same hash index. Your description is pretty close, but I don't remember the exact details. Yes, I keep around some nodes for while, but eventually old nodes go into the past and can be recovered. I actually have fewer total nodes than you do. The commercial version allocates 30K nodes per CPU core. The version in the world championship had much more, but the commercial version can't be that greedy for memory. David I give up when there are no nodes that area available to be overwritten. I'm still a little confused. First, does the hash table contains pointers into a node pool, or do you use the node pool as the hash table? Second, how and when do you determine which nodes (if any) are available for overwriting, without doing some sort of traversal? Is the following a correct summary of what you do when it's time to create a new node? Go to the one node that would be used for this Zobrist hash. If the same hash is stored there, use the existing node. If not, either overwrite this node (if this node is available for overwriting) or not create a new node (otherwise). Also, what exactly is the criterion for overwriting? You said nodes that have few visits or are old. Is this just (visits visitThreshold) || (depthFromBeginningOfGame currentGameTurn)? Doesn't depthFromBeginningOfGame cause you to keep around nodes that are outside the still-relevant branch of the tree (i.e., the branch descending from the current root), almost all of which are irrelevant? If the search is long enough, there are no nodes that can be recovered, and the UCT tree stops growing. I keep searching when there are no reusable nodes. ...because this improves the quality of information in the nodes you were able to create. That makes sense. Thanks, Peter Drake http://www.lclark.edu/~drake/ http://www.lclark.edu/%7Edrake/ ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/ ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/ ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/ ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
Re: [computer-go] Hash tables
Okay, I've almost got it. I'm also looking into implementing a transposition table. Some things are still unclear to me. If you're hashing by chaining, you presumably go to the appropriate slot in the table, then traverse the (short) linked list of nodes hanging from that slot. If the node you want isn't present, though, you have to find another node you can overwrite, presumably from another chain in the hash table. How do you find such a node without a lengthy search? Peter Drake http://www.lclark.edu/~drake/ Firstly, I don't understand the problem you describe: If the node you want isn't present, though, you have to find another node you can overwrite, presumably from another chain in the hash table. Are you referring to a node that was inserted, then overwritten, and now you need it again? Secondly, to find a node that has to be overwritten, do you have a criteria that always finds the node the least probable to be used again, or can it also return that there aren't any nodes in this chain that should be overwritten? The first one would always limit the search to a single chain, without looking at other chains in the hash table, wouldn't it? Isaac ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
Re: [computer-go] Hash tables
On Jul 6, 2009, at 9:26 AM, Isaac Deutsch wrote: If you're hashing by chaining, you presumably go to the appropriate slot in the table, then traverse the (short) linked list of nodes hanging from that slot. If the node you want isn't present, though, you have to find another node you can overwrite, presumably from another chain in the hash table. How do you find such a node without a lengthy search? Firstly, I don't understand the problem you describe: If the node you want isn't present, though, you have to find another node you can overwrite, presumably from another chain in the hash table. Are you referring to a node that was inserted, then overwritten, and now you need it again? No, I'm referring to a node that was inserted and is no longer relevant. For example, if my tree is A B C D E (that is, B and D are children of the root, C is the child of B, etc.), then I move to B, the remaining tree is: B C The nodes A, D, and E are no longer relevant, because they can no longer be reached. The challenge is to make these available for reuse (overwriting) without traversing all of memory. Secondly, to find a node that has to be overwritten, do you have a criteria that always finds the node the least probable to be used again, or can it also return that there aren't any nodes in this chain that should be overwritten? The first one would always limit the search to a single chain, without looking at other chains in the hash table, wouldn't it? I wasn't aiming for that level of sophistication; just hoping to reuse nodes that are no longer in the tree (dag) because they're along roads not taken. Peter Drake http://www.lclark.edu/~drake/ ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
Re: [computer-go] Hash tables
Well, there is one slight catch... Nodes do not contain pointers to their children. To find the node after making a move, I make the move on the board, then use the Zobrist hash of the new board as a key to search for the child node in the hash table. So traversing the tree would involve re-playing all of the moves from the root. Worse, in the interest of speed, my play code (modeled on LibEGO) doesn't support undoing. To do a recursive traversal like this, I therefore have to perform a board copy every time I backtrack. On the other hand, I think I could get away with only traversing the part of the tree that is still relevant (probably a small fraction of the nodes in use), then traversing the set of nodes linearly to rebuild the free list. In other words, I would perform a mark-and- sweep garbage collection. Peter Drake http://www.lclark.edu/~drake/ On Jul 6, 2009, at 8:02 PM, Michael Williams wrote: If you are talking about 128k nodes, I don't think traversing them will take very long. ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
Re: [computer-go] Hash tables
I thought you had really heavy nodes? Like 1k bytes or so? But no 8 byte pointers to children? Peter Drake wrote: Well, there is one slight catch... Nodes do not contain pointers to their children. To find the node after making a move, I make the move on the board, then use the Zobrist hash of the new board as a key to search for the child node in the hash table. So traversing the tree would involve re-playing all of the moves from the root. Worse, in the interest of speed, my play code (modeled on LibEGO) doesn't support undoing. To do a recursive traversal like this, I therefore have to perform a board copy every time I backtrack. On the other hand, I think I could get away with only traversing the part of the tree that is still relevant (probably a small fraction of the nodes in use), then traversing the set of nodes linearly to rebuild the free list. In other words, I would perform a mark-and-sweep garbage collection. Peter Drake http://www.lclark.edu/~drake/ On Jul 6, 2009, at 8:02 PM, Michael Williams wrote: If you are talking about 128k nodes, I don't think traversing them will take very long. ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/ ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
Re: [computer-go] Hash tables
Correct. Following David Fotland's suggestion, each node contains arrays of the run and win counts of its (potential) children. This way, searching the children of a node does not cause a cache miss. When using RAVE (on which I'm still working), I also need arrays for RAVE runs and counts through each child. These are all Java chars (effectively 16-bit unsigned ints). On 9x9, that's 81 * 2 * 4 = 648 bytes. Some other info pushes this up to around 1k. I suppose I could also include first child / next sibling pointers. I wouldn't actually use them when performing playouts, but they would greatly speed up the mark phase of marking and sweeping. Yes, I think this would be an improvement. Thanks! Peter Drake http://www.lclark.edu/~drake/ On Jul 6, 2009, at 8:15 PM, Michael Williams wrote: I thought you had really heavy nodes? Like 1k bytes or so? But no 8 byte pointers to children? Peter Drake wrote: Well, there is one slight catch... Nodes do not contain pointers to their children. To find the node after making a move, I make the move on the board, then use the Zobrist hash of the new board as a key to search for the child node in the hash table. So traversing the tree would involve re-playing all of the moves from the root. Worse, in the interest of speed, my play code (modeled on LibEGO) doesn't support undoing. To do a recursive traversal like this, I therefore have to perform a board copy every time I backtrack. On the other hand, I think I could get away with only traversing the part of the tree that is still relevant (probably a small fraction of the nodes in use), then traversing the set of nodes linearly to rebuild the free list. In other words, I would perform a mark-and-sweep garbage collection. Peter Drake http://www.lclark.edu/~drake/ On Jul 6, 2009, at 8:02 PM, Michael Williams wrote: If you are talking about 128k nodes, I don't think traversing them will take very long. ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/ ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/ ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
[computer-go] Hash tables
Okay, so I've finally built a transposition table. There is a big pool of nodes, allocated at startup. To find a node, I: 1) Play the move on the board and get the new Zobrist hash (incorporating the simple ko point and color to play). 2) Take this modulo the length of the table (currently 128K nodes) to find the first place to probe. 3) Linearly probe (i.e., try the next location, then the next one, etc.) until either I find a node with the correct Zobrist hash or hit the limit on the number of probes (1024 seems to work okay). 4) In situations where I'm trying to allocate a node, if I didn't find one that matched, I overwrite the first old node I encountered. An old node is one that wasn't touched on the previous turn (as indicated by a timestamp). If I didn't find an old node, the allocation fails. This works all right, but I'm bothered by the tension between a low probe limit (speeding up unsuccessful searches) and a high one (making more complete use of the table). Also, the table tends to fill up. Questions for others: a) Are you using this timestamp trick, or are you traversing your DAG to mark which nodes are still relevant every time you accept a (real, non-playout) move? I realize that almost none of the nodes touched last turn are still relevant, but traversing the entire table seems expensive. b) Is there some clever way to abandon an unsuccessful search earlier? In a hash table that wasn't full or close to it, I'd go until I found a null (i.e., a node that had never been used, as opposed to a node that is old or marked for deletion). Unfortunately, Orego fills up the table of 128k nodes in a matter of seconds. c) Is there some useful way of rehashing to get rid of the old nodes? Unfortunately, I can't fit a second copy of the table in memory... Thanks, Peter Drake http://www.lclark.edu/~drake/ ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
RE: [computer-go] Hash tables
a) I don't use timestamps. I don't have a DAG. I just reuse nodes that have few visits or are old (I keep the depth from root in each node). b) By unsuccessful search, I assume you mean the linear search in the probe. I don't do a probe search, so I can't help you there. I have a strong aversion to doing big linear searches in performance-sensitive code :) How big are your nodes? If you have 2 GB, they are about 15 KB each. That seems a little large. David -Original Message- From: computer-go-boun...@computer-go.org [mailto:computer-go- boun...@computer-go.org] On Behalf Of Peter Drake Sent: Thursday, July 02, 2009 4:21 PM To: Computer Go Subject: [computer-go] Hash tables Okay, so I've finally built a transposition table. There is a big pool of nodes, allocated at startup. To find a node, I: 1) Play the move on the board and get the new Zobrist hash (incorporating the simple ko point and color to play). 2) Take this modulo the length of the table (currently 128K nodes) to find the first place to probe. 3) Linearly probe (i.e., try the next location, then the next one, etc.) until either I find a node with the correct Zobrist hash or hit the limit on the number of probes (1024 seems to work okay). 4) In situations where I'm trying to allocate a node, if I didn't find one that matched, I overwrite the first old node I encountered. An old node is one that wasn't touched on the previous turn (as indicated by a timestamp). If I didn't find an old node, the allocation fails. This works all right, but I'm bothered by the tension between a low probe limit (speeding up unsuccessful searches) and a high one (making more complete use of the table). Also, the table tends to fill up. Questions for others: a) Are you using this timestamp trick, or are you traversing your DAG to mark which nodes are still relevant every time you accept a (real, non-playout) move? I realize that almost none of the nodes touched last turn are still relevant, but traversing the entire table seems expensive. b) Is there some clever way to abandon an unsuccessful search earlier? In a hash table that wasn't full or close to it, I'd go until I found a null (i.e., a node that had never been used, as opposed to a node that is old or marked for deletion). Unfortunately, Orego fills up the table of 128k nodes in a matter of seconds. c) Is there some useful way of rehashing to get rid of the old nodes? Unfortunately, I can't fit a second copy of the table in memory... Thanks, Peter Drake http://www.lclark.edu/~drake/ ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/ ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
Re: [computer-go] Hash tables
On Jul 5, 2009, at 6:01 PM, David Fotland wrote: a) I don't use timestamps. I don't have a DAG. I just reuse nodes that have few visits or are old (I keep the depth from root in each node). Do you save the tree between turns? If so, how do you adjust the depth from the root when a real move is played and one of the children of the old root becomes the new root? Similarly, do you clear out all of the nodes, so they don't look like they have many visits? ...or does root mean the beginning of the game? b) By unsuccessful search, I assume you mean the linear search in the probe. I don't do a probe search, so I can't help you there. I have a strong aversion to doing big linear searches in performance-sensitive code :) I share the same aversion. Do you simply give up if the node indicated by (zobristHash % tableSize) cannot be overwritten? How big are your nodes? If you have 2 GB, they are about 15 KB each. That seems a little large. The machine in question has 1 GB, and I believe the nodes are around 1K (for 9x9). That does imply that I should be able to fit around a million of them in there, but the machine thrashes when I go from 128K to 256K nodes. Peter Drake http://www.lclark.edu/~drake/ ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
RE: [computer-go] Hash tables
Yes, I save the search state from move to move. I don't save the tree, since I don't have a DAG. I keep the depth from the start of the game, not the start of the search. I give up when there are no nodes that area available to be overwritten. If the search is long enough, there are no nodes that can be recovered, and the UCT tree stops growing. I keep searching when there are no reusable nodes. David -Original Message- From: computer-go-boun...@computer-go.org [mailto:computer-go- boun...@computer-go.org] On Behalf Of Peter Drake Sent: Sunday, July 05, 2009 7:08 PM To: computer-go Subject: Re: [computer-go] Hash tables On Jul 5, 2009, at 6:01 PM, David Fotland wrote: a) I don't use timestamps. I don't have a DAG. I just reuse nodes that have few visits or are old (I keep the depth from root in each node). Do you save the tree between turns? If so, how do you adjust the depth from the root when a real move is played and one of the children of the old root becomes the new root? Similarly, do you clear out all of the nodes, so they don't look like they have many visits? ...or does root mean the beginning of the game? b) By unsuccessful search, I assume you mean the linear search in the probe. I don't do a probe search, so I can't help you there. I have a strong aversion to doing big linear searches in performance-sensitive code :) I share the same aversion. Do you simply give up if the node indicated by (zobristHash % tableSize) cannot be overwritten? How big are your nodes? If you have 2 GB, they are about 15 KB each. That seems a little large. The machine in question has 1 GB, and I believe the nodes are around 1K (for 9x9). That does imply that I should be able to fit around a million of them in there, but the machine thrashes when I go from 128K to 256K nodes. Peter Drake http://www.lclark.edu/~drake/ ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/ ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
Re: [computer-go] Hash tables
On Jul 5, 2009, at 7:21 PM, David Fotland wrote: Yes, I save the search state from move to move. I don't save the tree, since I don't have a DAG. I keep the depth from the start of the game, not the start of the search. Got it. I give up when there are no nodes that area available to be overwritten. I'm still a little confused. First, does the hash table contains pointers into a node pool, or do you use the node pool as the hash table? Second, how and when do you determine which nodes (if any) are available for overwriting, without doing some sort of traversal? Is the following a correct summary of what you do when it's time to create a new node? Go to the one node that would be used for this Zobrist hash. If the same hash is stored there, use the existing node. If not, either overwrite this node (if this node is available for overwriting) or not create a new node (otherwise). Also, what exactly is the criterion for overwriting? You said nodes that have few visits or are old. Is this just (visits visitThreshold) || (depthFromBeginningOfGame currentGameTurn)? Doesn't depthFromBeginningOfGame cause you to keep around nodes that are outside the still-relevant branch of the tree (i.e., the branch descending from the current root), almost all of which are irrelevant? If the search is long enough, there are no nodes that can be recovered, and the UCT tree stops growing. I keep searching when there are no reusable nodes. ...because this improves the quality of information in the nodes you were able to create. That makes sense. Thanks, Peter Drake http://www.lclark.edu/~drake/ ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
RE: [computer-go] Hash tables
The hash table contains a linked list of nodes with the same hash index. Your description is pretty close, but I don't remember the exact details. Yes, I keep around some nodes for while, but eventually old nodes go into the past and can be recovered. I actually have fewer total nodes than you do. The commercial version allocates 30K nodes per CPU core. The version in the world championship had much more, but the commercial version can't be that greedy for memory. David I give up when there are no nodes that area available to be overwritten. I'm still a little confused. First, does the hash table contains pointers into a node pool, or do you use the node pool as the hash table? Second, how and when do you determine which nodes (if any) are available for overwriting, without doing some sort of traversal? Is the following a correct summary of what you do when it's time to create a new node? Go to the one node that would be used for this Zobrist hash. If the same hash is stored there, use the existing node. If not, either overwrite this node (if this node is available for overwriting) or not create a new node (otherwise). Also, what exactly is the criterion for overwriting? You said nodes that have few visits or are old. Is this just (visits visitThreshold) || (depthFromBeginningOfGame currentGameTurn)? Doesn't depthFromBeginningOfGame cause you to keep around nodes that are outside the still-relevant branch of the tree (i.e., the branch descending from the current root), almost all of which are irrelevant? If the search is long enough, there are no nodes that can be recovered, and the UCT tree stops growing. I keep searching when there are no reusable nodes. ...because this improves the quality of information in the nodes you were able to create. That makes sense. Thanks, Peter Drake http://www.lclark.edu/~drake/ ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/ ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
Re: [computer-go] Hash tables
On Jul 5, 2009, at 9:05 PM, David Fotland wrote: The hash table contains a linked list of nodes with the same hash index. Okay, I've almost got it. If you're hashing by chaining, you presumably go to the appropriate slot in the table, then traverse the (short) linked list of nodes hanging from that slot. If the node you want isn't present, though, you have to find another node you can overwrite, presumably from another chain in the hash table. How do you find such a node without a lengthy search? I actually have fewer total nodes than you do. The commercial version allocates 30K nodes per CPU core. The version in the world championship had much more, but the commercial version can't be that greedy for memory. That's reassuring. Peter Drake http://www.lclark.edu/~drake/ ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
RE: [computer-go] Hash tables
Between moves, I find the nodes that can be recycled and put them on a free list. If the free list is empty I do a very short search, then give up. David -Original Message- From: computer-go-boun...@computer-go.org [mailto:computer-go- boun...@computer-go.org] On Behalf Of Peter Drake Sent: Sunday, July 05, 2009 9:42 PM To: computer-go Subject: Re: [computer-go] Hash tables On Jul 5, 2009, at 9:05 PM, David Fotland wrote: The hash table contains a linked list of nodes with the same hash index. Okay, I've almost got it. If you're hashing by chaining, you presumably go to the appropriate slot in the table, then traverse the (short) linked list of nodes hanging from that slot. If the node you want isn't present, though, you have to find another node you can overwrite, presumably from another chain in the hash table. How do you find such a node without a lengthy search? I actually have fewer total nodes than you do. The commercial version allocates 30K nodes per CPU core. The version in the world championship had much more, but the commercial version can't be that greedy for memory. That's reassuring. Peter Drake http://www.lclark.edu/~drake/ ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/ ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
Re: [computer-go] Hash tables
Aha, got it! Thanks. Peter Drake http://www.lclark.edu/~drake/ On Jul 5, 2009, at 10:17 PM, David Fotland wrote: Between moves, I find the nodes that can be recycled and put them on a free list. If the free list is empty I do a very short search, then give up. David -Original Message- From: computer-go-boun...@computer-go.org [mailto:computer-go- boun...@computer-go.org] On Behalf Of Peter Drake Sent: Sunday, July 05, 2009 9:42 PM To: computer-go Subject: Re: [computer-go] Hash tables On Jul 5, 2009, at 9:05 PM, David Fotland wrote: The hash table contains a linked list of nodes with the same hash index. Okay, I've almost got it. If you're hashing by chaining, you presumably go to the appropriate slot in the table, then traverse the (short) linked list of nodes hanging from that slot. If the node you want isn't present, though, you have to find another node you can overwrite, presumably from another chain in the hash table. How do you find such a node without a lengthy search? I actually have fewer total nodes than you do. The commercial version allocates 30K nodes per CPU core. The version in the world championship had much more, but the commercial version can't be that greedy for memory. That's reassuring. Peter Drake http://www.lclark.edu/~drake/ ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/ ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/ ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
