Re: [computer-go] Mega transposition table
On Fri, Jan 19, 2007 at 10:46:07AM -0500, Don Dailey wrote: On Fri, 2007-01-19 at 12:00 -0200, Mark Boon wrote: What ticked me off with the cuckoo method is apparently it can loop and a rehash is needed. Ouch, that better not happen very often! The whole point is that this cost is extremely tiny when amortized over the run time of the whole algorithm. In other words, the analysis of how efficient the algorithm considers this time. So the answer is that it is indeed a rare occurrence - a fraction of a percent of your run time. That also means that you have to keep enough data in each node to recalculate the hash keys from, for example the board position etc. Maybe it would be enough to keep the zobrist hash of the position, and use different bits of it for the hash key, or a different modulus, or something. -H -- Heikki Levanto In Murphy We Turst heikki (at) lsd (dot) dk ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
Re: [computer-go] Mega transposition table
UCT could help to tiddy up the transposition table Erik van der Werf's thesis was mainly about transposition table replacement algorihtms, IIRC. My personal summary: it is very hard to be more clever (at replacement) than always replace when hitting an occupied slot. (this is very similar to beating a LRU-replacement-sheme for disk-blocks; but totally different ;-) after a degree of confidence is gained. This could I think, this is exactly what the transposition table's purpose is: Avoid doing the same computations over and over. If you avoid them by some other means, the hash-nodes will be replaced anyway, eventually. No sweat. HTH, AvK ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
Re: [computer-go] Mega transposition table
On 1/19/07, A van Kessel [EMAIL PROTECTED] wrote: Erik van der Werf's thesis was mainly about transposition table replacement algorihtms, IIRC. No it wasn't. I think you're confusing me with Dennis Breuker. see: http://www.xs4all.nl/~breukerd/thesis/index.html I have some knowledge on transposition tables, and have even done some experiments along the lines as suggested by the original poster, but it was definitely not the main topic of my thesis (which btw can be found at http://erikvanderwerf.tengen.nl/pubdown/thesis_erikvanderwerf.ps.gz). My personal summary: it is very hard to be more clever (at replacement) than always replace when hitting an occupied slot. Yes, new does quite well under most circumstances. However, something like TwoBig should be easy to implement with UCT. An interesting question may be how to efficiently free memory from entries that become irrelevant in the continuation of a game (after the actual moves made have ruled out portions of the full game-graph), but this is probably not an issue in the context of the original poster's question. Erik ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
Re: [computer-go] Mega transposition table
interesting question may be how to efficiently free memory from entries that become irrelevant in the continuation of a game (after the actual moves made have ruled out portions of the full game-graph), but this is probably not an issue in the context of the original poster's question. Thats what I tried to said on my first post. After, sufficient simulations, there are a lot of transposition tables (ie, board configurations) that its well known to be useless moves. UCT can be used to decide which transposition tables delete from the mega database. Saving huge space and perhaps, making this idea feasible. Edu __ Preguntá. Respondé. Descubrí. Todo lo que querías saber, y lo que ni imaginabas, está en Yahoo! Respuestas (Beta). ¡Probalo ya! http://www.yahoo.com.ar/respuestas ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
Re: [computer-go] Mega transposition table
I'm talking about a transposition table storing win/played values (MC interested values.). If this ratio becomes tooo low (ex, win ratio below 1% with 10 games confidence), you can be sure you can delete all the game tree after this move. All the transposition tables following this move. I will look in detail your links later in my home. Manu thanks, Eduardo --- A van Kessel [EMAIL PROTECTED] escribió: UCT could help to tiddy up the transposition table Erik van der Werf's thesis was mainly about transposition table replacement algorihtms, IIRC. My personal summary: it is very hard to be more clever (at replacement) than always replace when hitting an occupied slot. (this is very similar to beating a LRU-replacement-sheme for disk-blocks; but totally different ;-) after a degree of confidence is gained. This could I think, this is exactly what the transposition table's purpose is: Avoid doing the same computations over and over. If you avoid them by some other means, the hash-nodes will be replaced anyway, eventually. No sweat. HTH, AvK ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/ __ Preguntá. Respondé. Descubrí. Todo lo que querías saber, y lo que ni imaginabas, está en Yahoo! Respuestas (Beta). ¡Probalo ya! http://www.yahoo.com.ar/respuestas ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
Re: [computer-go] Mega transposition table
On 1/19/07, Eduardo Sabbatella [EMAIL PROTECTED] wrote: interesting question may be how to efficiently free memory from entries that become irrelevant in the continuation of a game (after the actual moves made have ruled out portions of the full game-graph), but this is probably not an issue in the context of the original poster's question. Thats what I tried to said on my first post. After, sufficient simulations, there are a lot of transposition tables (ie, board configurations) that its well known to be useless moves. Sure, but here I was also talking about high quality parts of the game graph which nevertheless become irrelevant (in the continuation of a game) after a specific opening has been played. Erik ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
Re: [computer-go] Mega transposition table
I believe that clustering algorithm is algorithm is both more practical and elegant, than two big, and other multilevel schemes. - It uses memory in more efficient manner effecting in reduction of collision rate. - It allows for more than 2 entries on the same hash before loosing the information I would also would like to point that there is a new (2001) clever method of hashing i.e. Cuckoo Hashing that has the potential of replacing all other methods. If one is really serious about hash performance then there is this 2006-hot article: http://www.cwi.nl/themes/ins1/publications/docs/ZuHeBo:DAMON:06.pdf Hope this helps :) Łukasz On 1/19/07, Erik van der Werf [EMAIL PROTECTED] wrote: On 1/19/07, A van Kessel [EMAIL PROTECTED] wrote: Erik van der Werf's thesis was mainly about transposition table replacement algorihtms, IIRC. No it wasn't. I think you're confusing me with Dennis Breuker. see: http://www.xs4all.nl/~breukerd/thesis/index.html I have some knowledge on transposition tables, and have even done some experiments along the lines as suggested by the original poster, but it was definitely not the main topic of my thesis (which btw can be found at http://erikvanderwerf.tengen.nl/pubdown/thesis_erikvanderwerf.ps.gz). My personal summary: it is very hard to be more clever (at replacement) than always replace when hitting an occupied slot. Yes, new does quite well under most circumstances. However, something like TwoBig should be easy to implement with UCT. An interesting question may be how to efficiently free memory from entries that become irrelevant in the continuation of a game (after the actual moves made have ruled out portions of the full game-graph), but this is probably not an issue in the context of the original poster's question. Erik ___ 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] Mega transposition table
Take a look at http://en.wikipedia.org/wiki/Cuckoo_hashing also. Lukasz On 1/19/07, Eduardo Sabbatella [EMAIL PROTECTED] wrote: Right now my two main concerns are about: 1) feasability, perhaps even prunning with UCT for storing usefull games, no more than 5 ply can be stored on nowadays memory constraints. 2) techniques for prunning gametree on big databases of game configurations. This thing by itself its a quite big topic. About the hash method in your email, I have just print out the paper and I will read it on my commuting back home. I can't say much about hashing techniques specially needed in this situation. I was planning to use Berkeley DB or something. Is it too bad? o_O Many thanks, Eduardo --- £ukasz Lew [EMAIL PROTECTED] escribió: I believe that clustering algorithm is algorithm is both more practical and elegant, than two big, and other multilevel schemes. - It uses memory in more efficient manner effecting in reduction of collision rate. - It allows for more than 2 entries on the same hash before loosing the information I would also would like to point that there is a new (2001) clever method of hashing i.e. Cuckoo Hashing that has the potential of replacing all other methods. If one is really serious about hash performance then there is this 2006-hot article: http://www.cwi.nl/themes/ins1/publications/docs/ZuHeBo:DAMON:06.pdf Hope this helps :) £ukasz On 1/19/07, Erik van der Werf [EMAIL PROTECTED] wrote: On 1/19/07, A van Kessel [EMAIL PROTECTED] wrote: Erik van der Werf's thesis was mainly about transposition table replacement algorihtms, IIRC. No it wasn't. I think you're confusing me with Dennis Breuker. see: http://www.xs4all.nl/~breukerd/thesis/index.html I have some knowledge on transposition tables, and have even done some experiments along the lines as suggested by the original poster, but it was definitely not the main topic of my thesis (which btw can be found at http://erikvanderwerf.tengen.nl/pubdown/thesis_erikvanderwerf.ps.gz). My personal summary: it is very hard to be more clever (at replacement) than always replace when hitting an occupied slot. Yes, new does quite well under most circumstances. However, something like TwoBig should be easy to implement with UCT. An interesting question may be how to efficiently free memory from entries that become irrelevant in the continuation of a game (after the actual moves made have ruled out portions of the full game-graph), but this is probably not an issue in the context of the original poster's question. Erik ___ 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/ __ Preguntá. Respondé. Descubrí. Todo lo que querías saber, y lo que ni imaginabas, está en Yahoo! Respuestas (Beta). ¡Probalo ya! http://www.yahoo.com.ar/respuestas ___ 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] Mega transposition table
I have just understood the algorithm. Quite interesting, the collision prob decreases in the power of two on every step. Nice. Also quite new, I like to see new, basic and simple algorithms. Not common this days. Thanks! --- £ukasz Lew [EMAIL PROTECTED] escribió: Take a look at http://en.wikipedia.org/wiki/Cuckoo_hashing also. Lukasz On 1/19/07, Eduardo Sabbatella [EMAIL PROTECTED] wrote: Right now my two main concerns are about: 1) feasability, perhaps even prunning with UCT for storing usefull games, no more than 5 ply can be stored on nowadays memory constraints. 2) techniques for prunning gametree on big databases of game configurations. This thing by itself its a quite big topic. About the hash method in your email, I have just print out the paper and I will read it on my commuting back home. I can't say much about hashing techniques specially needed in this situation. I was planning to use Berkeley DB or something. Is it too bad? o_O Many thanks, Eduardo --- £ukasz Lew [EMAIL PROTECTED] escribió: I believe that clustering algorithm is algorithm is both more practical and elegant, than two big, and other multilevel schemes. - It uses memory in more efficient manner effecting in reduction of collision rate. - It allows for more than 2 entries on the same hash before loosing the information I would also would like to point that there is a new (2001) clever method of hashing i.e. Cuckoo Hashing that has the potential of replacing all other methods. If one is really serious about hash performance then there is this 2006-hot article: http://www.cwi.nl/themes/ins1/publications/docs/ZuHeBo:DAMON:06.pdf Hope this helps :) £ukasz On 1/19/07, Erik van der Werf [EMAIL PROTECTED] wrote: On 1/19/07, A van Kessel [EMAIL PROTECTED] wrote: Erik van der Werf's thesis was mainly about transposition table replacement algorihtms, IIRC. No it wasn't. I think you're confusing me with Dennis Breuker. see: http://www.xs4all.nl/~breukerd/thesis/index.html I have some knowledge on transposition tables, and have even done some experiments along the lines as suggested by the original poster, but it was definitely not the main topic of my thesis (which btw can be found at http://erikvanderwerf.tengen.nl/pubdown/thesis_erikvanderwerf.ps.gz). My personal summary: it is very hard to be more clever (at replacement) than always replace when hitting an occupied slot. Yes, new does quite well under most circumstances. However, something like TwoBig should be easy to implement with UCT. An interesting question may be how to efficiently free memory from entries that become irrelevant in the continuation of a game (after the actual moves made have ruled out portions of the full game-graph), but this is probably not an issue in the context of the original poster's question. Erik ___ 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/ __ Preguntá. Respondé. Descubrí. Todo lo que querías saber, y lo que ni imaginabas, está en Yahoo! Respuestas (Beta). ¡Probalo ya! http://www.yahoo.com.ar/respuestas ___ 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/ __ Preguntá. Respondé. Descubrí. Todo lo que querías saber, y lo que ni imaginabas, está en Yahoo! Respuestas (Beta). ¡Probalo ya! http://www.yahoo.com.ar/respuestas ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
Re: [computer-go] Mega transposition table
This seems to be only a small variation of hashing methods I was taught at university in the 80s. The method I always used was simply putting the new value and key in the place of the old one, with one simple addition. In case the spot is filled it would look at the next 'n' spots until it found an empty one (or one with the same key of course). If not, simply replace the old values with the new. But I must say for me the transposition lookup was not a critical piece in terms of performance because evaluations were so many orders of magnitude more expensive. So I used n=10 for a dramatically better usage of the available space in the table. I did no real research in terms of table-use, speed and number of collisions as a function of 'n'. What ticked me off with the cuckoo method is apparently it can loop and a rehash is needed. Ouch, that better not happen very often! Mark On 19-jan-07, at 11:00, Łukasz Lew wrote: Take a look at http://en.wikipedia.org/wiki/Cuckoo_hashing also. Lukasz On 1/19/07, Eduardo Sabbatella [EMAIL PROTECTED] wrote: Right now my two main concerns are about: 1) feasability, perhaps even prunning with UCT for storing usefull games, no more than 5 ply can be stored on nowadays memory constraints. 2) techniques for prunning gametree on big databases of game configurations. This thing by itself its a quite big topic. About the hash method in your email, I have just print out the paper and I will read it on my commuting back home. I can't say much about hashing techniques specially needed in this situation. I was planning to use Berkeley DB or something. Is it too bad? o_O Many thanks, Eduardo --- £ukasz Lew [EMAIL PROTECTED] escribió: I believe that clustering algorithm is algorithm is both more practical and elegant, than two big, and other multilevel schemes. - It uses memory in more efficient manner effecting in reduction of collision rate. - It allows for more than 2 entries on the same hash before loosing the information I would also would like to point that there is a new (2001) clever method of hashing i.e. Cuckoo Hashing that has the potential of replacing all other methods. If one is really serious about hash performance then there is this 2006-hot article: http://www.cwi.nl/themes/ins1/publications/docs/ZuHeBo:DAMON:06.pdf Hope this helps :) £ukasz On 1/19/07, Erik van der Werf [EMAIL PROTECTED] wrote: On 1/19/07, A van Kessel [EMAIL PROTECTED] wrote: Erik van der Werf's thesis was mainly about transposition table replacement algorihtms, IIRC. No it wasn't. I think you're confusing me with Dennis Breuker. see: http://www.xs4all.nl/~breukerd/thesis/index.html I have some knowledge on transposition tables, and have even done some experiments along the lines as suggested by the original poster, but it was definitely not the main topic of my thesis (which btw can be found at http://erikvanderwerf.tengen.nl/pubdown/thesis_erikvanderwerf.ps.gz). My personal summary: it is very hard to be more clever (at replacement) than always replace when hitting an occupied slot. Yes, new does quite well under most circumstances. However, something like TwoBig should be easy to implement with UCT. An interesting question may be how to efficiently free memory from entries that become irrelevant in the continuation of a game (after the actual moves made have ruled out portions of the full game-graph), but this is probably not an issue in the context of the original poster's question. Erik ___ 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/ __ Preguntá. Respondé. Descubrí. Todo lo que querías saber, y lo que ni imaginabas, está en Yahoo! Respuestas (Beta). ¡Probalo ya! http://www.yahoo.com.ar/respuestas ___ 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] Mega transposition table
On Fri, 2007-01-19 at 07:17 -0300, Eduardo Sabbatella wrote: Hello, Did someone try to store the transposition tables of the first n plys in order to reutilise them? This is probably a good idea. Since the tree in UCT is deep and narrow, you should probably not reset it between moves, but just prune away the ancestor nodes as you go. You can also expand it when your opponent is thinking, it would pay off pretty good if the computer favors the move the opponent actually plays. - Don I mean, at least the first 5 or 10 plys. We are talking about a lot of GB. UCT could help to tiddy up the transposition table after a degree of confidence is gained. This could save a lof of space and could be the key to make this feasible. Too weird? Eduardo ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
Re: [computer-go] Mega transposition table
On Fri, 2007-01-19 at 12:00 -0200, Mark Boon wrote: What ticked me off with the cuckoo method is apparently it can loop and a rehash is needed. Ouch, that better not happen very often! The whole point is that this cost is extremely tiny when amortized over the run time of the whole algorithm. In other words, the analysis of how efficient the algorithm considers this time. So the answer is that it is indeed a rare occurrence - a fraction of a percent of your run time. When it does happen, you would get a little pause - you probably wouldn't notice it. Some applications cannot deal with pauses such as action games where you cannot just stop the action for even a half a second to rebuild a hash table. In those cases you have to use something different. - Don ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
Re: [computer-go] Mega transposition table
On Fri, 2007-01-19 at 11:33 +, Eduardo Sabbatella wrote: If this ratio becomes tooo low (ex, win ratio below 1% with 10 games confidence), you can be sure you can delete all the game tree after this move. All the transposition tables following this move. I think you can win, but please note that the weak moves have very small tree's, so you have to clean up a LOT of them.And you ARE throwing out information that UCT will eventually reconstitute. - Don ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
Re: [computer-go] Mega transposition table
On Fri, 2007-01-19 at 11:45 +0100, A van Kessel wrote: My personal summary: it is very hard to be more clever (at replacement) than always replace when hitting an occupied slot. (this is very similar to beating a LRU-replacement-sheme for disk-blocks; but totally different ;-) You can improvement substantially on this, but of course it's better to allocate a bigger table if you can. With transposition tables in chess or go you have a replacement scheme that is careful to not overwrite better entries. It does make a good bit of difference how you implement this. - Don ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
Re: [computer-go] Mega transposition table
I see your point. I was thinking that after X simulations, transposition table could be made 'persistent'. Not before that. So this will avoid a lot of 'garbage', not so 'useful' board states. I have to think a lot about it. But I suposse as my transposition table implementation, it should have different node sizes (4 moves, 8, 16 or full board.) Some precalc data (at least the number of moves in this state as, as its usefull for UCT). How to avoid to recalculate discarted data? Perhaps its all about choosing wisely what to discard and when to store permanently. --- Don Dailey [EMAIL PROTECTED] escribió: On Fri, 2007-01-19 at 11:33 +, Eduardo Sabbatella wrote: If this ratio becomes tooo low (ex, win ratio below 1% with 10 games confidence), you can be sure you can delete all the game tree after this move. All the transposition tables following this move. I think you can win, but please note that the weak moves have very small tree's, so you have to clean up a LOT of them.And you ARE throwing out information that UCT will eventually reconstitute. - Don ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/ __ Preguntá. Respondé. Descubrí. Todo lo que querías saber, y lo que ni imaginabas, está en Yahoo! Respuestas (Beta). ¡Probalo ya! http://www.yahoo.com.ar/respuestas ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
Re: [computer-go] Mega transposition table
Sorry, I didn't understand the big table but It sounds promissing. I don't understand how do you access to different variations ... it seems like a merge-sort array but not sure. --- Don Dailey [EMAIL PROTECTED] escribió: I'm not sure it matters, because as I reported earlier you can delay node expansion with hardly any effect on the strength, and I'm requiring 100 hits before expansion. Pruning out moves from the tree WILL weaken the program - the question is how much? There is a tradeoff of course. What I am doing is pre-allocating the memory, my program does not need to malloc or free it. I start at zero, and have a global counter that tells me which entry to use next. I use 100 hits so I don't run out of entries for quite a while. To free this memory I just reset this global pointer to zero. The children of a node are listed in memory sequentially, I don't have to store separate pointer to each of them, I just have a first child pointer (index) and a count of the number of children. So when I open up a new node I find all the legal moves and use the next N available slots to place them. This is wasteful, but it's dirt simple and very fast. Even with only 256 MB of memory I have plenty for a pretty long search. - Don On Fri, 2007-01-19 at 13:09 -0300, Eduardo Sabbatella wrote: I see your point. I was thinking that after X simulations, transposition table could be made 'persistent'. Not before that. So this will avoid a lot of 'garbage', not so 'useful' board states. I have to think a lot about it. But I suposse as my transposition table implementation, it should have different node sizes (4 moves, 8, 16 or full board.) Some precalc data (at least the number of moves in this state as, as its usefull for UCT). How to avoid to recalculate discarted data? Perhaps its all about choosing wisely what to discard and when to store permanently. --- Don Dailey [EMAIL PROTECTED] escribió: On Fri, 2007-01-19 at 11:33 +, Eduardo Sabbatella wrote: If this ratio becomes tooo low (ex, win ratio below 1% with 10 games confidence), you can be sure you can delete all the game tree after this move. All the transposition tables following this move. I think you can win, but please note that the weak moves have very small tree's, so you have to clean up a LOT of them.And you ARE throwing out information that UCT will eventually reconstitute. - Don ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/ __ Preguntá. Respondé. Descubrí. Todo lo que querías saber, y lo que ni imaginabas, está en Yahoo! Respuestas (Beta). ¡Probalo ya! http://www.yahoo.com.ar/respuestas ___ 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/ __ Preguntá. Respondé. Descubrí. Todo lo que querías saber, y lo que ni imaginabas, está en Yahoo! Respuestas (Beta). ¡Probalo ya! http://www.yahoo.com.ar/respuestas ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
Re: [computer-go] Mega transposition table
On Fri, 2007-01-19 at 16:51 +, Eduardo Sabbatella wrote: Sorry, I didn't understand the big table but It sounds promissing. I don't understand how do you access to different variations ... it seems like a merge-sort array but not sure. It forms a tree in memory, but it's just a huge array of nodes. Each node has this: move - the move played from parent to get us here visits - number of times this node visited score - number of wins from this node first_child- index of node of first child child_count- number of legal moves from this position. (the move and child_count are 16 bits, everything else 32 bits, total structure size = 32 + 32 + 32 + 16 + 16 bits. = 128 bits. ) if child_count == 0 the node has not yet been expanded. If first child is stored at index 1300, for example and there are 10 children, then 1300 - first child 1301 - second child 1302 - third child etc. first_child is actually a pointer in my implementation, but to make this explanation clearer you can think of it as an index into the global array. In the example the pointer addresses array location 1300 .. in c - (node_t *) child = (big_array[1300]); - Don ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
Re: [computer-go] Mega transposition table
Are there more experimental results coming? Have you tried going higher than 100 yet? How much memory do you need at 100 during the course of a 30 minute game? On 1/19/07, Don Dailey [EMAIL PROTECTED] wrote: I'm not sure it matters, because as I reported earlier you can delay node expansion with hardly any effect on the strength, and I'm requiring 100 hits before expansion. Pruning out moves from the tree WILL weaken the program - the question is how much? There is a tradeoff of course. What I am doing is pre-allocating the memory, my program does not need to malloc or free it. I start at zero, and have a global counter that tells me which entry to use next. I use 100 hits so I don't run out of entries for quite a while. To free this memory I just reset this global pointer to zero. The children of a node are listed in memory sequentially, I don't have to store separate pointer to each of them, I just have a first child pointer (index) and a count of the number of children. So when I open up a new node I find all the legal moves and use the next N available slots to place them. This is wasteful, but it's dirt simple and very fast. Even with only 256 MB of memory I have plenty for a pretty long search. - Don On Fri, 2007-01-19 at 13:09 -0300, Eduardo Sabbatella wrote: I see your point. I was thinking that after X simulations, transposition table could be made 'persistent'. Not before that. So this will avoid a lot of 'garbage', not so 'useful' board states. I have to think a lot about it. But I suposse as my transposition table implementation, it should have different node sizes (4 moves, 8, 16 or full board.) Some precalc data (at least the number of moves in this state as, as its usefull for UCT). How to avoid to recalculate discarted data? Perhaps its all about choosing wisely what to discard and when to store permanently. --- Don Dailey [EMAIL PROTECTED] escribió: On Fri, 2007-01-19 at 11:33 +, Eduardo Sabbatella wrote: If this ratio becomes tooo low (ex, win ratio below 1% with 10 games confidence), you can be sure you can delete all the game tree after this move. All the transposition tables following this move. I think you can win, but please note that the weak moves have very small tree's, so you have to clean up a LOT of them.And you ARE throwing out information that UCT will eventually reconstitute. - Don ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/ __ Preguntá. Respondé. Descubrí. Todo lo que querías saber, y lo que ni imaginabas, está en Yahoo! Respuestas (Beta). ¡Probalo ya! http://www.yahoo.com.ar/respuestas ___ 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] Mega transposition table
On Fri, 2007-01-19 at 12:46 -0500, Chris Fant wrote: Are there more experimental results coming? Have you tried going higher than 100 yet? How much memory do you need at 100 during the course of a 30 minute game? I don't have the computing resources to test everything I would like to. But 100 seems safe and I can spend up to about 10 minutes on just one move before the table is exhausted. My table is 4 million nodes which is 67,108,864 bytes since each entry is 128 bits. If I got desperate, I could use a scheme where I don't store all the children, and when I need to expand I could move them to the end of the list and mark the previous slots as free. But then I'm starting to get into serious memory management, I don't know if I could do any better than malloc and free. - Don ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
Re: [computer-go] Mega transposition table
On 1/19/07, Mark Boon [EMAIL PROTECTED] wrote: This seems to be only a small variation of hashing methods I was taught at university in the 80s. The method I always used was simply putting the new value and key in the place of the old one, with one simple addition. In case the spot is filled it would look at the next 'n' spots until it found an empty one (or one with the same key of course). If not, simply replace the old values with the new. But I must say for me the transposition lookup was not a critical piece in terms of performance because evaluations were so many orders of magnitude more expensive. So I used n=10 for a dramatically better usage of the available space in the table. I did no real research in terms of table-use, speed and number of collisions as a function of 'n'. This is what I meant by clustering. It's most simple. I use cluster_size = 4. In some applications I have a performance bottleneck here. What ticked me off with the cuckoo method is apparently it can loop and a rehash is needed. Ouch, that better not happen very often! Mark On 19-jan-07, at 11:00, Łukasz Lew wrote: Take a look at http://en.wikipedia.org/wiki/Cuckoo_hashing also. Lukasz On 1/19/07, Eduardo Sabbatella [EMAIL PROTECTED] wrote: Right now my two main concerns are about: 1) feasability, perhaps even prunning with UCT for storing usefull games, no more than 5 ply can be stored on nowadays memory constraints. 2) techniques for prunning gametree on big databases of game configurations. This thing by itself its a quite big topic. About the hash method in your email, I have just print out the paper and I will read it on my commuting back home. I can't say much about hashing techniques specially needed in this situation. I was planning to use Berkeley DB or something. Is it too bad? o_O Many thanks, Eduardo --- £ukasz Lew [EMAIL PROTECTED] escribió: I believe that clustering algorithm is algorithm is both more practical and elegant, than two big, and other multilevel schemes. - It uses memory in more efficient manner effecting in reduction of collision rate. - It allows for more than 2 entries on the same hash before loosing the information I would also would like to point that there is a new (2001) clever method of hashing i.e. Cuckoo Hashing that has the potential of replacing all other methods. If one is really serious about hash performance then there is this 2006-hot article: http://www.cwi.nl/themes/ins1/publications/docs/ZuHeBo:DAMON:06.pdf Hope this helps :) £ukasz On 1/19/07, Erik van der Werf [EMAIL PROTECTED] wrote: On 1/19/07, A van Kessel [EMAIL PROTECTED] wrote: Erik van der Werf's thesis was mainly about transposition table replacement algorihtms, IIRC. No it wasn't. I think you're confusing me with Dennis Breuker. see: http://www.xs4all.nl/~breukerd/thesis/index.html I have some knowledge on transposition tables, and have even done some experiments along the lines as suggested by the original poster, but it was definitely not the main topic of my thesis (which btw can be found at http://erikvanderwerf.tengen.nl/pubdown/thesis_erikvanderwerf.ps.gz). My personal summary: it is very hard to be more clever (at replacement) than always replace when hitting an occupied slot. Yes, new does quite well under most circumstances. However, something like TwoBig should be easy to implement with UCT. An interesting question may be how to efficiently free memory from entries that become irrelevant in the continuation of a game (after the actual moves made have ruled out portions of the full game-graph), but this is probably not an issue in the context of the original poster's question. Erik ___ 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/ __ Preguntá. Respondé. Descubrí. Todo lo que querías saber, y lo que ni imaginabas, está en Yahoo! Respuestas (Beta). ¡Probalo ya! http://www.yahoo.com.ar/respuestas ___ 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
Re: [computer-go] Mega transposition table
This is a very good design in my opinion. I was about to ask why you used an index instead of a pointer until I saw that you were using a pointer actually. Using global data like this highlights one of the ways that C++ can blow away Java's requirement that everything must be allocated on the heap. On 1/19/07, Don Dailey [EMAIL PROTECTED] wrote: On Fri, 2007-01-19 at 16:51 +, Eduardo Sabbatella wrote: Sorry, I didn't understand the big table but It sounds promissing. I don't understand how do you access to different variations ... it seems like a merge-sort array but not sure. It forms a tree in memory, but it's just a huge array of nodes. Each node has this: move - the move played from parent to get us here visits - number of times this node visited score - number of wins from this node first_child- index of node of first child child_count- number of legal moves from this position. (the move and child_count are 16 bits, everything else 32 bits, total structure size = 32 + 32 + 32 + 16 + 16 bits. = 128 bits. ) if child_count == 0 the node has not yet been expanded. If first child is stored at index 1300, for example and there are 10 children, then 1300 - first child 1301 - second child 1302 - third child etc. first_child is actually a pointer in my implementation, but to make this explanation clearer you can think of it as an index into the global array. In the example the pointer addresses array location 1300 .. in c - (node_t *) child = (big_array[1300]); - Don ___ 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] Mega transposition table
Don, You wrote: Does it matter?... While I am not totally up-to-date on C++ compiler optimizers, it seems like locality of reference compiler optimizations might be influenced if you were to specify allocation on the stack as opposed to the heap. And aren't stack based values much more likely to end up in registers and in CPU cache than heap based references and values? Perhaps all of these kinds of evaluations are rendered ineffective with more modern day CPUs and C++/C compilers. From what I have been following in the Java JVMs, these prove to be VERY important in the way they choose to optimize execution paths and data flows. Just figured that it would matter in C++/C in a similar way. Jim Don Dailey wrote: On Fri, 2007-01-19 at 17:19 -0600, Jim O'Flaherty, Jr. wrote: Don, So could you elaborate on where you are allocating space for big_array in your code snippet below? Does it matter? I just declare it as a global but I will probably eventually just place it on the heap via malloc - with a command line argument to set the size. - Don ___ 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/
