Re: [computer-go] UCT tree pruning
Nice to hear that :) 2009/6/5 Michael Williams michaelwilliam...@gmail.com: Łukasz Lew wrote: On Wed, Jun 3, 2009 at 00:56, Michael Williams michaelwilliam...@gmail.com wrote: Two things: Firstly, I'm storing (only in RAM) the precalculated Winrate and InvSqrtVisits and keeping them updated. So my UCT formula went from Wins / Visits + sqrt(lnParentVisits / Visits) to WinRate + sqrtLnParentVisits * InvSqrtVisits; This has a memory cost, but I don't care so much about RAM since I can send the nodes to disk. And the second thing is to store in the parent node a reference to what is likely the UCT-best child node. If the parent has been visited 100*boardspaces times, I will go directly to the likely-best child with probability 2047/2048. Anytime a proper UCT loop occurs, the likely-best reference is updated (about 90% of the time there is no change, so I think it's safe). This is quite similar to epsilon trick described here: http://www.mimuw.edu.pl/~lew/files/epsilon_trick.pdf in short when you calculate best UCT child you visit it max(best.visit_count * epsilon, 1) times with epsilon = 0.05 for instance It works well both for new and old nodes, but you have to keep the counter of visits. The soft way would be to recalculate best child with probability min(1, 1/(best.visit_count*epsilon)). Both variants of ET can give you some guarantees about the way the tree is explored. Łukasz I switched to this method. Thanks, Lukasz. ___ 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] UCT tree pruning
Łukasz Lew wrote: On Wed, Jun 3, 2009 at 00:56, Michael Williams michaelwilliam...@gmail.com wrote: Two things: Firstly, I'm storing (only in RAM) the precalculated Winrate and InvSqrtVisits and keeping them updated. So my UCT formula went from Wins / Visits + sqrt(lnParentVisits / Visits) to WinRate + sqrtLnParentVisits * InvSqrtVisits; This has a memory cost, but I don't care so much about RAM since I can send the nodes to disk. And the second thing is to store in the parent node a reference to what is likely the UCT-best child node. If the parent has been visited 100*boardspaces times, I will go directly to the likely-best child with probability 2047/2048. Anytime a proper UCT loop occurs, the likely-best reference is updated (about 90% of the time there is no change, so I think it's safe). This is quite similar to epsilon trick described here: http://www.mimuw.edu.pl/~lew/files/epsilon_trick.pdf in short when you calculate best UCT child you visit it max(best.visit_count * epsilon, 1) times with epsilon = 0.05 for instance It works well both for new and old nodes, but you have to keep the counter of visits. The soft way would be to recalculate best child with probability min(1, 1/(best.visit_count*epsilon)). Both variants of ET can give you some guarantees about the way the tree is explored. Łukasz I switched to this method. Thanks, Lukasz. ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
Re: [computer-go] UCT tree pruning
Update: After concentrating on tightening the UCT loop, I've optimized myself back into needing the SDD :/ But now I should be able to get to 20B nodes in just one day. (still only doing 7x7 Go) Michael Williams wrote: Yes, when memory is full, I save and free all leaf nodes (which is the vast majority). Nodes are loaded as needed. Don Dailey wrote: On Mon, Jun 1, 2009 at 4:57 PM, Michael Williams michaelwilliam...@gmail.com mailto:michaelwilliam...@gmail.com wrote: I've optimized my disk access to the point where I'm mostly CPU limited now, even when using a standard hard disk instead of an SSD. I can now create trees of up to about 30 billion nodes, which would take about a week. The simulation rate is continuously going down because so much time is spent in UCT loops in the huge tree. That's impressive. Are you doing things which move parts of the tree onto the disk and back when needed? I'm curious about the details! - Don Don Dailey wrote: On Mon, Jun 1, 2009 at 11:22 AM, Isaac Deutsch i...@gmx.ch mailto:i...@gmx.ch mailto:i...@gmx.ch mailto:i...@gmx.ch wrote: Well, I'll take that over crashing with an out-of-memory error. :) Still, pruning seems better to me and has the same effect. ;p But is it better? I think it's not so obvious without thorough testing. Pruning throw away information that is lost forever and may need to be recalculated. Requiring more simulations does not throw out results, but results in some inefficiencies. So it's not clear to me which is better - it may even be that it depends on how much you push it. I am just guessing but I would guess that pruning is better in the short term, worse in the longer term. Imagine a search at a corespondence level, where the computer thinks for 24 hours. Which method is best there? Could you use hard disk or SSD? Using some kind of caching system, where you relegate the oldest unvisited nodes to the hard dirve. It may be that nodes you might normally prune are unlikely to get used again but if they do you still have the data.This is no good unless you can guarantee that the disk is used very infrequently - but with SSD it may be more practical. - Don -- Nur bis 31.05.: GMX FreeDSL Komplettanschluss mit DSL 6.000 Flatrate und Telefonanschluss nur 17,95 Euro/mtl.!* http://portal.gmx.net/de/go/dsl02 ___ computer-go mailing list computer-go@computer-go.org mailto:computer-go@computer-go.org mailto:computer-go@computer-go.org mailto:computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/ ___ computer-go mailing list computer-go@computer-go.org mailto:computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/ ___ computer-go mailing list computer-go@computer-go.org mailto: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] UCT tree pruning
I mean SSD. Michael Williams wrote: Update: After concentrating on tightening the UCT loop, I've optimized myself back into needing the SDD :/ But now I should be able to get to 20B nodes in just one day. (still only doing 7x7 Go) Michael Williams wrote: Yes, when memory is full, I save and free all leaf nodes (which is the vast majority). Nodes are loaded as needed. Don Dailey wrote: On Mon, Jun 1, 2009 at 4:57 PM, Michael Williams michaelwilliam...@gmail.com mailto:michaelwilliam...@gmail.com wrote: I've optimized my disk access to the point where I'm mostly CPU limited now, even when using a standard hard disk instead of an SSD. I can now create trees of up to about 30 billion nodes, which would take about a week. The simulation rate is continuously going down because so much time is spent in UCT loops in the huge tree. That's impressive. Are you doing things which move parts of the tree onto the disk and back when needed? I'm curious about the details! - Don Don Dailey wrote: On Mon, Jun 1, 2009 at 11:22 AM, Isaac Deutsch i...@gmx.ch mailto:i...@gmx.ch mailto:i...@gmx.ch mailto:i...@gmx.ch wrote: Well, I'll take that over crashing with an out-of-memory error. :) Still, pruning seems better to me and has the same effect. ;p But is it better? I think it's not so obvious without thorough testing. Pruning throw away information that is lost forever and may need to be recalculated. Requiring more simulations does not throw out results, but results in some inefficiencies. So it's not clear to me which is better - it may even be that it depends on how much you push it. I am just guessing but I would guess that pruning is better in the short term, worse in the longer term. Imagine a search at a corespondence level, where the computer thinks for 24 hours. Which method is best there? Could you use hard disk or SSD? Using some kind of caching system, where you relegate the oldest unvisited nodes to the hard dirve. It may be that nodes you might normally prune are unlikely to get used again but if they do you still have the data.This is no good unless you can guarantee that the disk is used very infrequently - but with SSD it may be more practical. - Don -- Nur bis 31.05.: GMX FreeDSL Komplettanschluss mit DSL 6.000 Flatrate und Telefonanschluss nur 17,95 Euro/mtl.!* http://portal.gmx.net/de/go/dsl02 ___ computer-go mailing list computer-go@computer-go.org mailto:computer-go@computer-go.org mailto:computer-go@computer-go.org mailto:computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/ ___ computer-go mailing list computer-go@computer-go.org mailto:computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/ ___ computer-go mailing list computer-go@computer-go.org mailto: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] UCT tree pruning
That sounds like a good optimization. What did you do? Sent from my iPhone On Jun 2, 2009, at 3:16 PM, Michael Williams michaelwilliam...@gmail.com wrote: Update: After concentrating on tightening the UCT loop, I've optimized myself back into needing the SDD :/ But now I should be able to get to 20B nodes in just one day. (still only doing 7x7 Go) Michael Williams wrote: Yes, when memory is full, I save and free all leaf nodes (which is the vast majority). Nodes are loaded as needed. Don Dailey wrote: On Mon, Jun 1, 2009 at 4:57 PM, Michael Williams michaelwilliam...@gmail.com mailto:michaelwilliam...@gmail.com wrote: I've optimized my disk access to the point where I'm mostly CPU limited now, even when using a standard hard disk instead of an SSD. I can now create trees of up to about 30 billion nodes, which would take about a week. The simulation rate is continuously going down because so much time is spent in UCT loops in the huge tree. That's impressive. Are you doing things which move parts of the tree onto the disk and back when needed? I'm curious about the details! - Don Don Dailey wrote: On Mon, Jun 1, 2009 at 11:22 AM, Isaac Deutsch i...@gmx.ch mailto:i...@gmx.ch mailto:i...@gmx.ch mailto:i...@gmx.ch wrote: Well, I'll take that over crashing with an out-of- memory error. :) Still, pruning seems better to me and has the same effect. ;p But is it better? I think it's not so obvious without thorough testing. Pruning throw away information that is lost forever and may need to be recalculated. Requiring more simulations does not throw out results, but results in some inefficiencies. So it's not clear to me which is better - it may even be that it depends on how much you push it. I am just guessing but I would guess that pruning is better in the short term, worse in the longer term. Imagine a search at a corespondence level, where the computer thinks for 24 hours. Which method is best there? Could you use hard disk or SSD? Using some kind of caching system, where you relegate the oldest unvisited nodes to the hard dirve. It may be that nodes you might normally prune are unlikely to get used again but if they do you still have the data.This is no good unless you can guarantee that the disk is used very infrequently - but with SSD it may be more practical. - Don -- Nur bis 31.05.: GMX FreeDSL Komplettanschluss mit DSL 6.000 Flatrate und Telefonanschluss nur 17,95 Euro/mtl.!* http://portal.gmx.net/de/go/dsl02 ___ computer-go mailing list computer-go@computer-go.org mailto:computer-go@computer-go.org mailto:computer-go@computer-go.org mailto:computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/ --- --- -- ___ computer-go mailing list computer-go@computer-go.org mailto:computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/ ___ computer-go mailing list computer-go@computer-go.org mailto: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] UCT tree pruning
Two things: Firstly, I'm storing (only in RAM) the precalculated Winrate and InvSqrtVisits and keeping them updated. So my UCT formula went from Wins / Visits + sqrt(lnParentVisits / Visits) to WinRate + sqrtLnParentVisits * InvSqrtVisits; This has a memory cost, but I don't care so much about RAM since I can send the nodes to disk. And the second thing is to store in the parent node a reference to what is likely the UCT-best child node. If the parent has been visited 100*boardspaces times, I will go directly to the likely-best child with probability 2047/2048. Anytime a proper UCT loop occurs, the likely-best reference is updated (about 90% of the time there is no change, so I think it's safe). Jason House wrote: That sounds like a good optimization. What did you do? Sent from my iPhone On Jun 2, 2009, at 3:16 PM, Michael Williams michaelwilliam...@gmail.com wrote: Update: After concentrating on tightening the UCT loop, I've optimized myself back into needing the SDD :/ But now I should be able to get to 20B nodes in just one day. (still only doing 7x7 Go) Michael Williams wrote: Yes, when memory is full, I save and free all leaf nodes (which is the vast majority). Nodes are loaded as needed. Don Dailey wrote: On Mon, Jun 1, 2009 at 4:57 PM, Michael Williams michaelwilliam...@gmail.com mailto:michaelwilliam...@gmail.com wrote: I've optimized my disk access to the point where I'm mostly CPU limited now, even when using a standard hard disk instead of an SSD. I can now create trees of up to about 30 billion nodes, which would take about a week. The simulation rate is continuously going down because so much time is spent in UCT loops in the huge tree. That's impressive. Are you doing things which move parts of the tree onto the disk and back when needed? I'm curious about the details! - Don Don Dailey wrote: On Mon, Jun 1, 2009 at 11:22 AM, Isaac Deutsch i...@gmx.ch mailto:i...@gmx.ch mailto:i...@gmx.ch mailto:i...@gmx.ch wrote: Well, I'll take that over crashing with an out-of-memory error. :) Still, pruning seems better to me and has the same effect. ;p But is it better? I think it's not so obvious without thorough testing. Pruning throw away information that is lost forever and may need to be recalculated. Requiring more simulations does not throw out results, but results in some inefficiencies. So it's not clear to me which is better - it may even be that it depends on how much you push it. I am just guessing but I would guess that pruning is better in the short term, worse in the longer term. Imagine a search at a corespondence level, where the computer thinks for 24 hours. Which method is best there? Could you use hard disk or SSD? Using some kind of caching system, where you relegate the oldest unvisited nodes to the hard dirve. It may be that nodes you might normally prune are unlikely to get used again but if they do you still have the data.This is no good unless you can guarantee that the disk is used very infrequently - but with SSD it may be more practical. - Don -- Nur bis 31.05.: GMX FreeDSL Komplettanschluss mit DSL 6.000 Flatrate und Telefonanschluss nur 17,95 Euro/mtl.!* http://portal.gmx.net/de/go/dsl02 ___ computer-go mailing list computer-go@computer-go.org mailto:computer-go@computer-go.org mailto:computer-go@computer-go.org mailto:computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/ ___ computer-go mailing list computer-go@computer-go.org mailto:computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/ ___ computer-go mailing list computer-go@computer-go.org mailto: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/ ___ computer-go
Re: [computer-go] UCT tree pruning
On Wed, Jun 3, 2009 at 00:56, Michael Williams michaelwilliam...@gmail.com wrote: Two things: Firstly, I'm storing (only in RAM) the precalculated Winrate and InvSqrtVisits and keeping them updated. So my UCT formula went from Wins / Visits + sqrt(lnParentVisits / Visits) to WinRate + sqrtLnParentVisits * InvSqrtVisits; This has a memory cost, but I don't care so much about RAM since I can send the nodes to disk. And the second thing is to store in the parent node a reference to what is likely the UCT-best child node. If the parent has been visited 100*boardspaces times, I will go directly to the likely-best child with probability 2047/2048. Anytime a proper UCT loop occurs, the likely-best reference is updated (about 90% of the time there is no change, so I think it's safe). This is quite similar to epsilon trick described here: http://www.mimuw.edu.pl/~lew/files/epsilon_trick.pdf in short when you calculate best UCT child you visit it max(best.visit_count * epsilon, 1) times with epsilon = 0.05 for instance It works well both for new and old nodes, but you have to keep the counter of visits. The soft way would be to recalculate best child with probability min(1, 1/(best.visit_count*epsilon)). Both variants of ET can give you some guarantees about the way the tree is explored. Łukasz Jason House wrote: That sounds like a good optimization. What did you do? Sent from my iPhone On Jun 2, 2009, at 3:16 PM, Michael Williams michaelwilliam...@gmail.com wrote: Update: After concentrating on tightening the UCT loop, I've optimized myself back into needing the SDD :/ But now I should be able to get to 20B nodes in just one day. (still only doing 7x7 Go) Michael Williams wrote: Yes, when memory is full, I save and free all leaf nodes (which is the vast majority). Nodes are loaded as needed. Don Dailey wrote: On Mon, Jun 1, 2009 at 4:57 PM, Michael Williams michaelwilliam...@gmail.com mailto:michaelwilliam...@gmail.com wrote: I've optimized my disk access to the point where I'm mostly CPU limited now, even when using a standard hard disk instead of an SSD. I can now create trees of up to about 30 billion nodes, which would take about a week. The simulation rate is continuously going down because so much time is spent in UCT loops in the huge tree. That's impressive. Are you doing things which move parts of the tree onto the disk and back when needed? I'm curious about the details! - Don Don Dailey wrote: On Mon, Jun 1, 2009 at 11:22 AM, Isaac Deutsch i...@gmx.ch mailto:i...@gmx.ch mailto:i...@gmx.ch mailto:i...@gmx.ch wrote: Well, I'll take that over crashing with an out-of-memory error. :) Still, pruning seems better to me and has the same effect. ;p But is it better? I think it's not so obvious without thorough testing. Pruning throw away information that is lost forever and may need to be recalculated. Requiring more simulations does not throw out results, but results in some inefficiencies. So it's not clear to me which is better - it may even be that it depends on how much you push it. I am just guessing but I would guess that pruning is better in the short term, worse in the longer term. Imagine a search at a corespondence level, where the computer thinks for 24 hours. Which method is best there? Could you use hard disk or SSD? Using some kind of caching system, where you relegate the oldest unvisited nodes to the hard dirve. It may be that nodes you might normally prune are unlikely to get used again but if they do you still have the data. This is no good unless you can guarantee that the disk is used very infrequently - but with SSD it may be more practical. - Don -- Nur bis 31.05.: GMX FreeDSL Komplettanschluss mit DSL 6.000 Flatrate und Telefonanschluss nur 17,95 Euro/mtl.!* http://portal.gmx.net/de/go/dsl02 ___ computer-go mailing list computer...@computer-go.org mailto:computer-go@computer-go.org mailto:computer-go@computer-go.org mailto:computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/ ___ computer-go mailing list computer-go@computer-go.org mailto:computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/ ___ computer-go mailing list computer-go@computer-go.org mailto:computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
Re: [computer-go] UCT tree pruning
On Jun 2, 2009, at 6:56 PM, Michael Williams michaelwilliam...@gmail.com wrote: Two things: Firstly, I'm storing (only in RAM) the precalculated Winrate and InvSqrtVisits and keeping them updated. So my UCT formula went from Wins / Visits + sqrt(lnParentVisits / Visits) to WinRate + sqrtLnParentVisits * InvSqrtVisits; Which equations do you use for the incremental updates? Or do you just recompute the values? This has a memory cost, but I don't care so much about RAM since I can send the nodes to disk. And the second thing is to store in the parent node a reference to what is likely the UCT-best child node. If the parent has been visited 100*boardspaces times, I will go directly to the likely-best child with probability 2047/2048. Anytime a proper UCT loop occurs, the likely-best reference is updated (about 90% of the time there is no change, so I think it's safe). What is a proper UCT loop? Jason House wrote: That sounds like a good optimization. What did you do? Sent from my iPhone On Jun 2, 2009, at 3:16 PM, Michael Williams michaelwilliam...@gmail.com wrote: Update: After concentrating on tightening the UCT loop, I've optimized myself back into needing the SDD :/ But now I should be able to get to 20B nodes in just one day. (still only doing 7x7 Go) Michael Williams wrote: Yes, when memory is full, I save and free all leaf nodes (which is the vast majority). Nodes are loaded as needed. Don Dailey wrote: On Mon, Jun 1, 2009 at 4:57 PM, Michael Williams michaelwilliam...@gmail.com mailto:michaelwilliam...@gmail.com wrote: I've optimized my disk access to the point where I'm mostly CPU limited now, even when using a standard hard disk instead of an SSD. I can now create trees of up to about 30 billion nodes, which would take about a week. The simulation rate is continuously going down because so much time is spent in UCT loops in the huge tree. That's impressive. Are you doing things which move parts of the tree onto the disk and back when needed? I'm curious about the details! - Don Don Dailey wrote: On Mon, Jun 1, 2009 at 11:22 AM, Isaac Deutsch i...@gmx.ch mailto:i...@gmx.ch mailto:i...@gmx.ch mailto:i...@gmx.ch wrote: Well, I'll take that over crashing with an out-of- memory error. :) Still, pruning seems better to me and has the same effect. ;p But is it better? I think it's not so obvious without thorough testing. Pruning throw away information that is lost forever and may need to be recalculated. Requiring more simulations does not throw out results, but results in some inefficiencies. So it's not clear to me which is better - it may even be that it depends on how much you push it. I am just guessing but I would guess that pruning is better in the short term, worse in the longer term. Imagine a search at a corespondence level, where the computer thinks for 24 hours. Which method is best there? Could you use hard disk or SSD? Using some kind of caching system, where you relegate the oldest unvisited nodes to the hard dirve. It may be that nodes you might normally prune are unlikely to get used again but if they do you still have the data.This is no good unless you can guarantee that the disk is used very infrequently - but with SSD it may be more practical. - Don -- Nur bis 31.05.: GMX FreeDSL Komplettanschluss mit DSL 6.000 Flatrate und Telefonanschluss nur 17,95 Euro/mtl.!* http://portal.gmx.net/de/go/dsl02 ___ computer-go mailing list computer-go@computer-go.org mailto:computer-go@computer-go.org mailto:computer-go@computer-go.org mailto:computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/ --- --- -- ___ computer-go mailing list computer-go@computer-go.org mailto:computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/ ___ computer-go mailing list computer-go@computer-go.org mailto: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] UCT tree pruning
Jason House wrote: On Jun 2, 2009, at 6:56 PM, Michael Williams michaelwilliam...@gmail.com wrote: Two things: Firstly, I'm storing (only in RAM) the precalculated Winrate and InvSqrtVisits and keeping them updated. So my UCT formula went from Wins / Visits + sqrt(lnParentVisits / Visits) to WinRate + sqrtLnParentVisits * InvSqrtVisits; Which equations do you use for the incremental updates? Or do you just recompute the values? It's not incremental. WinRate = Wins / Visits; InvSqrtVisits = 1 / sqrt(Visits); This has a memory cost, but I don't care so much about RAM since I can send the nodes to disk. And the second thing is to store in the parent node a reference to what is likely the UCT-best child node. If the parent has been visited 100*boardspaces times, I will go directly to the likely-best child with probability 2047/2048. Anytime a proper UCT loop occurs, the likely-best reference is updated (about 90% of the time there is no change, so I think it's safe). What is a proper UCT loop? By that I meant finding the the child that maximizes the UCT formula. Jason House wrote: That sounds like a good optimization. What did you do? Sent from my iPhone On Jun 2, 2009, at 3:16 PM, Michael Williams michaelwilliam...@gmail.com wrote: Update: After concentrating on tightening the UCT loop, I've optimized myself back into needing the SDD :/ But now I should be able to get to 20B nodes in just one day. (still only doing 7x7 Go) Michael Williams wrote: Yes, when memory is full, I save and free all leaf nodes (which is the vast majority). Nodes are loaded as needed. Don Dailey wrote: On Mon, Jun 1, 2009 at 4:57 PM, Michael Williams michaelwilliam...@gmail.com mailto:michaelwilliam...@gmail.com wrote: I've optimized my disk access to the point where I'm mostly CPU limited now, even when using a standard hard disk instead of an SSD. I can now create trees of up to about 30 billion nodes, which would take about a week. The simulation rate is continuously going down because so much time is spent in UCT loops in the huge tree. That's impressive. Are you doing things which move parts of the tree onto the disk and back when needed? I'm curious about the details! - Don Don Dailey wrote: On Mon, Jun 1, 2009 at 11:22 AM, Isaac Deutsch i...@gmx.ch mailto:i...@gmx.ch mailto:i...@gmx.ch mailto:i...@gmx.ch wrote: Well, I'll take that over crashing with an out-of-memory error. :) Still, pruning seems better to me and has the same effect. ;p But is it better? I think it's not so obvious without thorough testing. Pruning throw away information that is lost forever and may need to be recalculated. Requiring more simulations does not throw out results, but results in some inefficiencies. So it's not clear to me which is better - it may even be that it depends on how much you push it. I am just guessing but I would guess that pruning is better in the short term, worse in the longer term. Imagine a search at a corespondence level, where the computer thinks for 24 hours. Which method is best there? Could you use hard disk or SSD? Using some kind of caching system, where you relegate the oldest unvisited nodes to the hard dirve. It may be that nodes you might normally prune are unlikely to get used again but if they do you still have the data.This is no good unless you can guarantee that the disk is used very infrequently - but with SSD it may be more practical. - Don -- Nur bis 31.05.: GMX FreeDSL Komplettanschluss mit DSL 6.000 Flatrate und Telefonanschluss nur 17,95 Euro/mtl.!* http://portal.gmx.net/de/go/dsl02 ___ computer-go mailing list computer-go@computer-go.org mailto:computer-go@computer-go.org mailto:computer-go@computer-go.org mailto:computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/ ___ computer-go mailing list computer-go@computer-go.org mailto:computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/ ___ computer-go mailing list computer-go@computer-go.org mailto: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] UCT tree pruning
In dimwit we simply increase the number of visits to a node before it is added to the UCT tree, to slow down its growth. I wasn't too happy about how selective the tree got with a long time to think, but it's unclear if this particular hack had anything to do with that. Álvaro. On Mon, Jun 1, 2009 at 4:54 AM, Isaac Deutsch i...@gmx.ch wrote: Hi. I've been thinking about pondering, and the way the tree has to be built to support pondering. Because with pondering, the thinking time for a move can be very big theoretically, I would like to handle automatic pruning of the tree to avoid running out of memory. Right now I have a fixed size pool of nodes, and I simply stop the tree from growing when I see that all nodes are used. However I'm afraid this could hurt the performance when thinking times are very long. This brings me to my question: When I see that I'm running out of memory, which leaves/subtrees of the UCT tree should be pruned? -Prune moves with a low winrate and a low variance. This would favor nodes near the root, and often lots of memory would be freed this way. However, one has to be careful not to prune potentially good moves. -Prune leaf nodes with little visits that are old. This would have a small impact on the UCT search but the memory freed is very little, meaning I would have to do a lot of pruning. Another approach would be of course to just let the tree grow indefinitely and hope that it will not use too much memory, but I'm not sure it would work well in all situations. What do you do in your programs? Have you tested other approaches? Do you think hard pruning is bad in general? Regards, -ibd -- Nur bis 31.05.: GMX FreeDSL Komplettanschluss mit DSL 6.000 Flatrate und Telefonanschluss nur 17,95 Euro/mtl.!* http://portal.gmx.net/de/go/dsl02 ___ 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] UCT tree pruning
In dimwit we simply increase the number of visits to a node before it is added to the UCT tree, to slow down its growth. I wasn't too happy about how selective the tree got with a long time to think, but it's unclear if this particular hack had anything to do with that. Álvaro. I already do this - a node is expanded if it has 4 visits. Still, I worry about not being able to prune the tree. Are you suggesting that it is unlikely that I will run into memory problems? Isaac -- Nur bis 31.05.: GMX FreeDSL Komplettanschluss mit DSL 6.000 Flatrate und Telefonanschluss nur 17,95 Euro/mtl.!* http://portal.gmx.net/de/go/dsl02 ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
Re: [computer-go] UCT tree pruning
On Mon, Jun 1, 2009 at 9:38 AM, Isaac Deutsch i...@gmx.ch wrote: In dimwit we simply increase the number of visits to a node before it is added to the UCT tree, to slow down its growth. I wasn't too happy about how selective the tree got with a long time to think, but it's unclear if this particular hack had anything to do with that. Álvaro. I already do this - a node is expanded if it has 4 visits. Still, I worry about not being able to prune the tree. Are you suggesting that it is unlikely that I will run into memory problems? No. We use a threshold that is a function of how large the tree already is. It starts at 5 and then we increase it as the tree grows larger. I think the exact formula scaled with something like the log(tree_size)^2, but I would have to check when I get home. Álvaro. Isaac -- Nur bis 31.05.: GMX FreeDSL Komplettanschluss mit DSL 6.000 Flatrate und Telefonanschluss nur 17,95 Euro/mtl.!* http://portal.gmx.net/de/go/dsl02 ___ 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] UCT tree pruning
No. We use a threshold that is a function of how large the tree already is. It starts at 5 and then we increase it as the tree grows larger. I think the exact formula scaled with something like the log(tree_size)^2, but I would have to check when I get home. Álvaro. Ah, now I understand. I'm not sure if I like the idea because the tree is very much shaped based on the initial estimated values. Do you think it is not a problem that the tree might struggle to converge to the best move once it has explored a long line that doesn't work? Greetings, Isaac -- Nur bis 31.05.: GMX FreeDSL Komplettanschluss mit DSL 6.000 Flatrate und Telefonanschluss nur 17,95 Euro/mtl.!* http://portal.gmx.net/de/go/dsl02 ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
Re: [computer-go] UCT tree pruning
On Mon, Jun 1, 2009 at 10:10 AM, Isaac Deutsch i...@gmx.ch wrote: No. We use a threshold that is a function of how large the tree already is. It starts at 5 and then we increase it as the tree grows larger. I think the exact formula scaled with something like the log(tree_size)^2, but I would have to check when I get home. Álvaro. Ah, now I understand. I'm not sure if I like the idea because the tree is very much shaped based on the initial estimated values. Do you think it is not a problem that the tree might struggle to converge to the best move once it has explored a long line that doesn't work? Well, I'll take that over crashing with an out-of-memory error. :) ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
Re: [computer-go] UCT tree pruning
Well, I'll take that over crashing with an out-of-memory error. :) Still, pruning seems better to me and has the same effect. ;p -- Nur bis 31.05.: GMX FreeDSL Komplettanschluss mit DSL 6.000 Flatrate und Telefonanschluss nur 17,95 Euro/mtl.!* http://portal.gmx.net/de/go/dsl02 ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
Re: [computer-go] UCT tree pruning
Valkyria simply do not expand the tree when it runs out of unused nodes. That would be the most simple thing to prevent crashing. Then one could consider pruning the tree in order to be able to expand the tree even deeper. -Magnus Quoting Isaac Deutsch i...@gmx.ch: Well, I'll take that over crashing with an out-of-memory error. :) Still, pruning seems better to me and has the same effect. ;p -- Nur bis 31.05.: GMX FreeDSL Komplettanschluss mit DSL 6.000 Flatrate und Telefonanschluss nur 17,95 Euro/mtl.!* http://portal.gmx.net/de/go/dsl02 ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/ -- Magnus Persson Berlin, Germany ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
Re: [computer-go] UCT tree pruning
On Mon, Jun 1, 2009 at 11:22 AM, Isaac Deutsch i...@gmx.ch wrote: Well, I'll take that over crashing with an out-of-memory error. :) Still, pruning seems better to me and has the same effect. ;p But is it better? I think it's not so obvious without thorough testing. Pruning throw away information that is lost forever and may need to be recalculated. Requiring more simulations does not throw out results, but results in some inefficiencies. So it's not clear to me which is better - it may even be that it depends on how much you push it. I am just guessing but I would guess that pruning is better in the short term, worse in the longer term. Imagine a search at a corespondence level, where the computer thinks for 24 hours. Which method is best there? Could you use hard disk or SSD? Using some kind of caching system, where you relegate the oldest unvisited nodes to the hard dirve. It may be that nodes you might normally prune are unlikely to get used again but if they do you still have the data.This is no good unless you can guarantee that the disk is used very infrequently - but with SSD it may be more practical. - Don -- Nur bis 31.05.: GMX FreeDSL Komplettanschluss mit DSL 6.000 Flatrate und Telefonanschluss nur 17,95 Euro/mtl.!* http://portal.gmx.net/de/go/dsl02 ___ 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] UCT tree pruning
It seems that it would be better to always expand after one visit, and prune nodes with less than N visits, than to only expand after N visits. I expand after every visit and prune nodes with few visits when I need to. Davdi -Original Message- From: computer-go-boun...@computer-go.org [mailto:computer-go- boun...@computer-go.org] On Behalf Of Isaac Deutsch Sent: Monday, June 01, 2009 9:23 AM To: computer-go Subject: Re: [computer-go] UCT tree pruning But is it better? I think it's not so obvious without thorough testing. - Don OK. It seems difficult to find a good rule to prune moves/nodes. I just had an additional idea. You could make the treshold for expanding a node a function of the tree size AND the depth the node is at in the tree. This could somewhat counterbalance the effect of the tree becoming very selective. Do you think that might work? -ibd -- Nur bis 31.05.: GMX FreeDSL Komplettanschluss mit DSL 6.000 Flatrate und Telefonanschluss nur 17,95 Euro/mtl.!* http://portal.gmx.net/de/go/dsl02 ___ 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] UCT tree pruning
I've optimized my disk access to the point where I'm mostly CPU limited now, even when using a standard hard disk instead of an SSD. I can now create trees of up to about 30 billion nodes, which would take about a week. The simulation rate is continuously going down because so much time is spent in UCT loops in the huge tree. Don Dailey wrote: On Mon, Jun 1, 2009 at 11:22 AM, Isaac Deutsch i...@gmx.ch mailto:i...@gmx.ch wrote: Well, I'll take that over crashing with an out-of-memory error. :) Still, pruning seems better to me and has the same effect. ;p But is it better? I think it's not so obvious without thorough testing. Pruning throw away information that is lost forever and may need to be recalculated. Requiring more simulations does not throw out results, but results in some inefficiencies. So it's not clear to me which is better - it may even be that it depends on how much you push it. I am just guessing but I would guess that pruning is better in the short term, worse in the longer term. Imagine a search at a corespondence level, where the computer thinks for 24 hours. Which method is best there? Could you use hard disk or SSD? Using some kind of caching system, where you relegate the oldest unvisited nodes to the hard dirve. It may be that nodes you might normally prune are unlikely to get used again but if they do you still have the data.This is no good unless you can guarantee that the disk is used very infrequently - but with SSD it may be more practical. - Don -- Nur bis 31.05.: GMX FreeDSL Komplettanschluss mit DSL 6.000 Flatrate und Telefonanschluss nur 17,95 Euro/mtl.!* http://portal.gmx.net/de/go/dsl02 ___ computer-go mailing list computer-go@computer-go.org mailto: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] UCT tree pruning
On Mon, Jun 1, 2009 at 4:57 PM, Michael Williams michaelwilliam...@gmail.com wrote: I've optimized my disk access to the point where I'm mostly CPU limited now, even when using a standard hard disk instead of an SSD. I can now create trees of up to about 30 billion nodes, which would take about a week. The simulation rate is continuously going down because so much time is spent in UCT loops in the huge tree. That's impressive. Are you doing things which move parts of the tree onto the disk and back when needed? I'm curious about the details! - Don Don Dailey wrote: On Mon, Jun 1, 2009 at 11:22 AM, Isaac Deutsch i...@gmx.ch mailto: i...@gmx.ch wrote: Well, I'll take that over crashing with an out-of-memory error. :) Still, pruning seems better to me and has the same effect. ;p But is it better? I think it's not so obvious without thorough testing. Pruning throw away information that is lost forever and may need to be recalculated. Requiring more simulations does not throw out results, but results in some inefficiencies. So it's not clear to me which is better - it may even be that it depends on how much you push it. I am just guessing but I would guess that pruning is better in the short term, worse in the longer term. Imagine a search at a corespondence level, where the computer thinks for 24 hours. Which method is best there? Could you use hard disk or SSD? Using some kind of caching system, where you relegate the oldest unvisited nodes to the hard dirve. It may be that nodes you might normally prune are unlikely to get used again but if they do you still have the data.This is no good unless you can guarantee that the disk is used very infrequently - but with SSD it may be more practical. - Don -- Nur bis 31.05.: GMX FreeDSL Komplettanschluss mit DSL 6.000 Flatrate und Telefonanschluss nur 17,95 Euro/mtl.!* http://portal.gmx.net/de/go/dsl02 ___ computer-go mailing list computer-go@computer-go.org mailto: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] UCT tree pruning
Yes, when memory is full, I save and free all leaf nodes (which is the vast majority). Nodes are loaded as needed. Don Dailey wrote: On Mon, Jun 1, 2009 at 4:57 PM, Michael Williams michaelwilliam...@gmail.com mailto:michaelwilliam...@gmail.com wrote: I've optimized my disk access to the point where I'm mostly CPU limited now, even when using a standard hard disk instead of an SSD. I can now create trees of up to about 30 billion nodes, which would take about a week. The simulation rate is continuously going down because so much time is spent in UCT loops in the huge tree. That's impressive. Are you doing things which move parts of the tree onto the disk and back when needed? I'm curious about the details! - Don Don Dailey wrote: On Mon, Jun 1, 2009 at 11:22 AM, Isaac Deutsch i...@gmx.ch mailto:i...@gmx.ch mailto:i...@gmx.ch mailto:i...@gmx.ch wrote: Well, I'll take that over crashing with an out-of-memory error. :) Still, pruning seems better to me and has the same effect. ;p But is it better? I think it's not so obvious without thorough testing. Pruning throw away information that is lost forever and may need to be recalculated. Requiring more simulations does not throw out results, but results in some inefficiencies. So it's not clear to me which is better - it may even be that it depends on how much you push it. I am just guessing but I would guess that pruning is better in the short term, worse in the longer term. Imagine a search at a corespondence level, where the computer thinks for 24 hours. Which method is best there? Could you use hard disk or SSD? Using some kind of caching system, where you relegate the oldest unvisited nodes to the hard dirve. It may be that nodes you might normally prune are unlikely to get used again but if they do you still have the data.This is no good unless you can guarantee that the disk is used very infrequently - but with SSD it may be more practical. - Don -- Nur bis 31.05.: GMX FreeDSL Komplettanschluss mit DSL 6.000 Flatrate und Telefonanschluss nur 17,95 Euro/mtl.!* http://portal.gmx.net/de/go/dsl02 ___ computer-go mailing list computer-go@computer-go.org mailto:computer-go@computer-go.org mailto:computer-go@computer-go.org mailto:computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/ ___ computer-go mailing list computer-go@computer-go.org mailto:computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/ ___ computer-go mailing list computer-go@computer-go.org mailto: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/
