Re: [computer-go] Re: Implications of a CPU vs Memory trend on MCTS
I concur with Don; for the early moves, this is likely to be helpful. On a 19x19 board, the first ten or fifteen moves of a pro game often follow fairly well-known patterns, but it's not enough to simply memorize the patterns; there is deep knowledge which explains why one 3,4 point is better than the other, or why a particular joseki matches the overall position, and another is a failure. Building up a tree over time which knows something about the various choices might be helpful. Terry McIntyre terrymcint...@yahoo.com On general principles, when we are looking for a solution of a social problem, we must expect to reach conclusions quite opposed to the usual opinions on the subject; otherwise it would be no problem. We must expect to have to attack, not what is commonly regarded as objectionable, but what is commonly regarded as entirely proper and normal. – John Beverley Robinson, 1897 ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
Re: [computer-go] Re: Implications of a CPU vs Memory trend on MCTS
Sparks are flying, but I don't think that either of you are onto the exact truth. Don: do you play Go the same way you play chess? I don't think I do. The opening, in computer terms, for me only gets to move 20 if there is a long Joseki involved. It happens too often that somebody tries something before that. (Disclaimer: I only ever made it to 3 dan, and don't play actively - strong players may think differently). Last time I talked to a pro, many years ago now, about a relatively innocent opening (Chinese opening, a pattern consisting of 5 moves), I found a very open mind about each of the moves, and huge flexibility to deal with deviations. I am pretty convinced that there is not currently a good answer to playing well in the opening and early middle game and 19x19. I just don't think anyone has come up with one. MCTS looks like a blind man wandering the desert (I agree on this point), but on other hand a pure opening book will limit the program. I am hoping that people keep a goal of beating the *strongest* human players in mind, rather than chasing 200 ELO here and there. It seems easy to tune programs that plateau at a particular kyu or dan level. In that respect I commend the authors of the papers on Monte Carlo go on their reservations about hand-crafted patterns in playouts. They, the patterns, do have a tendency to remind me of kyu player tactics (always respond to atari, always pull a stone out of atari...). Pure statistical measures (criticality, David Silver's approach), etc, sound *much* more exciting to me, as they don't constrain strength scalability - I hope to see many more. Christian Don Dailey wrote: On Tue, May 12, 2009 at 8:17 PM, Dave Dyer dd...@real-me.net mailto:dd...@real-me.net wrote: If I use persistent storage and do that search again in another game, I can start exactly where I left off and generate 50,000 more nodes. It will be the same as if I did 100,000 nodes instead of 50,000 nodes.Or put another way, it will be the same as if I spent 20 seconds on this move instead of 10 seconds. Sure, but except for openings you'll never reach the same position position in another game unless the players are deliberately copying their play. I think you still miss the point. I don't expect this to help on move 20, only for the early positions you have seen before. When I play chess, I play the first few moves almost instantly, without making a blunder. I can do this because I have studied those positions and know them thoroughly. It's not because I memorized them, even though I have.As soon as I get to positions I am less familiar with, I slow down to a crawl, because now I have to try to figure them out over the board. Of course my knowledge of the opening helps some, even when I'm out of the book I have a good sense of how to proceed. With GO, a computer can do the same. It's almost ridiculous to search the opening position from scratch, as it we are a totally moron and have never see that position before. There is no reason not to study it and remember what we learned about it.There is no reason not to apply this to as many moves as possible in the opening, even if it's only a very few. I don't understand why this is not immediately obvious to you. What I suggest is superior to just memorizing what moves to play, you can actually save the tree and in a sense it's like a program actually understands the position, not just play by rote. If it's a position you already searched, you will have at least a little head start no matter what the opponent plays.Even if the opponent surprises you, you will have a piece of the tree intact and the next time this same situation happens, you will now have some serious analysis already pre-computed. With 19x19 this is probably not a huge ELO booster, but there is certainly nothing unsound about it either. And it may not be as bad as you think because the computer will tend to be deterministic about which moves it plays which by itself drastically lowers the branching factor. If it fails to play the same in a position it has already seen, that is not a bad thing either, it indicates that it found a move it likes better, perhaps discovering that something was wrong with the previous choice. That's exactly what you hope it does. Consider move 20 (for example). If you saved every move 20 node you ever encountered, how often do you think you'd encounter a duplicate from a different game, such that you can either avoid an evaluation, or improve your knowledge of that position by studying it a bit more. I contend it is a vanishingly small percentage. I don't believe you want to save the tree beyond the point where you are in a position you have never seen for the very reason you state. It's very unlikely that you will still be a part of the tree you have
Re: [computer-go] Re: Implications of a CPU vs Memory trend on MCTS
On Wed, May 13, 2009 at 2:34 AM, Christian Nentwich christ...@modeltwozero.com wrote: Sparks are flying, but I don't think that either of you are onto the exact truth. Don: do you play Go the same way you play chess? I don't think I do. The opening, in computer terms, for me only gets to move 20 if there is a long Joseki involved. It happens too often that somebody tries something before that. (Disclaimer: I only ever made it to 3 dan, and don't play actively - strong players may think differently). Last time I talked to a pro, many years ago now, about a relatively innocent opening (Chinese opening, a pattern consisting of 5 moves), I found a very open mind about each of the moves, and huge flexibility to deal with deviations. I'm only advocating an approach where you remember what you were thinking last.This is not inflexible, it is just the opposite. A strict opening book is inflexible.With this memory approach, you might find that what you think is good today, does not look so good tomorrow. If there is any lack of open-mindedness on the part of the program, the fault lies with the move selection algorithm, not the idea. In fact this is far more human-like than simply wiping your memory of each game after you play it. It's my feeling that on 19x19 this is not worth much of anything - certainly not the enormous disk space it would cost. It's not because of any inherent unsoundness of the idea, but just the fact that you are only going to be able to maintain a limited memory of just the first very few moves. There is no doubt you will be able able to play those very few moves much better, but it's not clear if some kind of joseki is better. I am pretty convinced that there is not currently a good answer to playing well in the opening and early middle game and 19x19. I just don't think anyone has come up with one. MCTS looks like a blind man wandering the desert (I agree on this point), but on other hand a pure opening book will limit the program. I am hoping that people keep a goal of beating the *strongest* human players in mind, rather than chasing 200 ELO here and there. It seems easy to tune programs that plateau at a particular kyu or dan level. I think this much is clear. Even on small boards the program benefits from some kind of opening book. In that respect I commend the authors of the papers on Monte Carlo go on their reservations about hand-crafted patterns in playouts. They, the patterns, do have a tendency to remind me of kyu player tactics (always respond to atari, always pull a stone out of atari...). Pure statistical measures (criticality, David Silver's approach), etc, sound *much* more exciting to me, as they don't constrain strength scalability - I hope to see many more. Christian Don Dailey wrote: On Tue, May 12, 2009 at 8:17 PM, Dave Dyer dd...@real-me.net mailto: dd...@real-me.net wrote: If I use persistent storage and do that search again in another game, I can start exactly where I left off and generate 50,000 more nodes. It will be the same as if I did 100,000 nodes instead of 50,000 nodes.Or put another way, it will be the same as if I spent 20 seconds on this move instead of 10 seconds. Sure, but except for openings you'll never reach the same position position in another game unless the players are deliberately copying their play. I think you still miss the point. I don't expect this to help on move 20, only for the early positions you have seen before. When I play chess, I play the first few moves almost instantly, without making a blunder. I can do this because I have studied those positions and know them thoroughly. It's not because I memorized them, even though I have.As soon as I get to positions I am less familiar with, I slow down to a crawl, because now I have to try to figure them out over the board. Of course my knowledge of the opening helps some, even when I'm out of the book I have a good sense of how to proceed. With GO, a computer can do the same. It's almost ridiculous to search the opening position from scratch, as it we are a totally moron and have never see that position before. There is no reason not to study it and remember what we learned about it.There is no reason not to apply this to as many moves as possible in the opening, even if it's only a very few. I don't understand why this is not immediately obvious to you. What I suggest is superior to just memorizing what moves to play, you can actually save the tree and in a sense it's like a program actually understands the position, not just play by rote. If it's a position you already searched, you will have at least a little head start no matter what the opponent plays.Even if the opponent surprises you, you will have a piece of the tree intact and the next time this same situation happens, you will now have some serious
Re: [computer-go] Re: Implications of a CPU vs Memory trend on MCTS
On Wed, May 13, 2009 at 2:44 AM, Magnus Persson magnus.pers...@phmp.sewrote: Some quick comments: I did store the search tree with early versions of Valkyria, but then I gave it up. Problems: 1) Searching deeper did not seem to overcome inherent fuseki weaknesses 2) The memory cost became too high Yes, the memory cost is high. When I started talking about this, I knew that it would involve a lot of space. And you have to stop when you run out of disk space and probably even memory space. In point 1, I think it's clear that program play very weak on the first few moves, so even at super high levels it's difficult to overcome this. Advantage: 1) Playing fast in the opening saves time. This is very good on small boards. Currently, I am thinking of doing something similar to a normal opening book but with winrate statistics from played games that are updated online. The idea is to bias search towards known good moves, but avoid: 1) Memory costs 2) The problem of overfitting weak and strong opponents if only the most played moves are stored and no search is done in the positions found in the opening book. Sounds like a reasonable approach to me. The principle is to try to benefit somehow from past experiences and your idea attempts to do that. -Magnus ___ 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] Re: Implications of a CPU vs Memory trend on MCTS
I'm a bit late reading this thread and the discussion seems to have veered from the original topic a bit. As to the CPU vs. memory discussion, it's not so clear-cut to me that CPU speeds are improving faster than memory. Twenty years ago you had CPUs in the 4-8Mhz range and around 1Mb of memory. Today both are about 1000 times higher. CPU speeds are not necessarily only represented by hertz of course, but both CPU and memory seemed to have progressed with roughly the same speed. The thing is, they don't progress evenly. So maybe at the moment CPUs are going a bit faster than memory. But this could be temporary, not necessarily a sustainable trend. Also, CPU speeds of a single processor has stalled for a few years now. Using multiple CPUs or cores you get easy doubles by going to two and four. But it also gets more and more expensive. And doubling the CPUs doesn't double the power really. A bit over ten years ago we made a tsume-go program using PN search. There we also had problems keeping the tree in memory, so we designed a tree-structure that would automatically swap part of the tree out to disk. But after that there was a period that this code seemed to have become superfluous, as memory suddenly became abundant. If we now have a memory shortage with respect to CPU power it's quite possible this is something cyclical. Mark ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
Re: [computer-go] Re: Implications of a CPU vs Memory trend on MCTS
Plus, they are both made out of the same stuff so one would expect them to scale at about the same rate. Mark Boon wrote: I'm a bit late reading this thread and the discussion seems to have veered from the original topic a bit. As to the CPU vs. memory discussion, it's not so clear-cut to me that CPU speeds are improving faster than memory. Twenty years ago you had CPUs in the 4-8Mhz range and around 1Mb of memory. Today both are about 1000 times higher. CPU speeds are not necessarily only represented by hertz of course, but both CPU and memory seemed to have progressed with roughly the same speed. The thing is, they don't progress evenly. So maybe at the moment CPUs are going a bit faster than memory. But this could be temporary, not necessarily a sustainable trend. Also, CPU speeds of a single processor has stalled for a few years now. Using multiple CPUs or cores you get easy doubles by going to two and four. But it also gets more and more expensive. And doubling the CPUs doesn't double the power really. A bit over ten years ago we made a tsume-go program using PN search. There we also had problems keeping the tree in memory, so we designed a tree-structure that would automatically swap part of the tree out to disk. But after that there was a period that this code seemed to have become superfluous, as memory suddenly became abundant. If we now have a memory shortage with respect to CPU power it's quite possible this is something cyclical. Mark ___ 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: Implications of a CPU vs Memory trend on MCTS
Storing an opening book for the first 10 moves requires 331477745148242200 nodes. Even with some reduction for symmetry, I don't see that much memory becoming available anytime soon, and you still have to evaluate them somehow. Actually storing a tree, except for extremely limited special cases, is not even conceptually possible, and doesn't save much time. Consider that if you store the tree you saw at the previous move, by the time you get to use the stored tree 99% of it is useless because your opponent chose his move. ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
Re: [computer-go] Re: Implications of a CPU vs Memory trend on MCTS
Where does your 99% figure come from? Dave Dyer wrote: Storing an opening book for the first 10 moves requires 331477745148242200 nodes. Even with some reduction for symmetry, I don't see that much memory becoming available anytime soon, and you still have to evaluate them somehow. Actually storing a tree, except for extremely limited special cases, is not even conceptually possible, and doesn't save much time. Consider that if you store the tree you saw at the previous move, by the time you get to use the stored tree 99% of it is useless because your opponent chose his move. ___ 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: Implications of a CPU vs Memory trend on MCTS
At 02:13 PM 5/12/2009, Michael Williams wrote: Where does your 99% figure come from? 1/361 1% by endgame there are still easily 100 empty spaces on the board. ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
[computer-go] Re: Implications of a CPU vs Memory trend on MCTS
At 02:13 PM 5/12/2009, Michael Williams wrote: Where does your 99% figure come from? 1/361 1% by endgame there are still easily 100 empty spaces on the board. ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
Re: [computer-go] Re: Implications of a CPU vs Memory trend on MCTS
You have made the assumption that the move that your opponent selected was on average explored equally as much as all of the other moves. That seems a bit pessimistic. One would expect that the opponent selected a strong move and one would also expect that your tree explored that strong move more than it did other moves. I'm not saying keeping the tree is a huge benefit. I'm just saying that I don't think your 99% number is fair. Dave Dyer wrote: At 02:13 PM 5/12/2009, Michael Williams wrote: Where does your 99% figure come from? 1/361 1% by endgame there are still easily 100 empty spaces on the board. ___ 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] Re: Implications of a CPU vs Memory trend on MCTS
In the opening, among reasonably clueful players, the branching factor is much closer to 10 than to 361. Terry McIntyre terrymcint...@yahoo.com On general principles, when we are looking for a solution of a social problem, we must expect to reach conclusions quite opposed to the usual opinions on the subject; otherwise it would be no problem. We must expect to have to attack, not what is commonly regarded as objectionable, but what is commonly regarded as entirely proper and normal. – John Beverley Robinson, 1897 From: Michael Williams michaelwilliam...@gmail.com Subject: Re: [computer-go] Re: Implications of a CPU vs Memory trend on MCTS You have made the assumption that the move that your opponent selected was on average explored equally as much as all of the other moves. That seems a bit pessimistic. One would expect that the opponent selected a strong move and one would also expect that your tree explored that strong move more than it did other moves. I'm not saying keeping the tree is a huge benefit. I'm just saying that I don't think your 99% number is fair. Dave Dyer wrote: At 02:13 PM 5/12/2009, Michael Williams wrote: Where does your 99% figure come from? 1/361 1% by endgame there are still easily 100 empty spaces on the board. ___ 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] Re: Implications of a CPU vs Memory trend on MCTS
I don't think you have any understanding of what I'm suggesting. You don't actually store the whole tree, you store whatever part of it is generated by the program and that is an infinitesimal subset.I have noticed that many times you tend to think in purely theoretical terms when it was completely out of context and I think you are doing it again. So basically you can only store nodes at the rate the computer can generate them while doing heaving playouts.Since monte carlo tree's are pruned in very severe ways, in practice you cannot even come close to storing the entire tree even to a very modest depth.In theory MC probably would, after a few million years, grow a complete tree to some pretty good depth while discovering a complete solution. The storage cost is probably still prohibitive, as you can probably store only a few thousand moves worth of nodes on a large disk. You will constantly grow nodes and presumably for a book learning system you will stop storing nodes beyond some modest move number. If you look carefully at what MC search does, you will notice that the tree almost looks like a beam search. There is no significant depth for the vast majority of lines. If you don't know that, you have not been paying much attention to the discussion on MCTS. As has been mentioned, there may be ways to stretch this. The most obvious, other than direct compression, is to design your tree search to be heavy on CPU time whenever a reasonable compromise is possible and a decision must be made. For instance if you have a choice between doing super heavy playouts or looking at twice the number of nodes, and it's pretty much all the same, then choose the heavy playouts.If you can do 10 playouts instead of one and get almost as good results, then do that. In general emphasize the quality of the nodes over quantity whenever it's a reasaonble decision. - Don On Tue, May 12, 2009 at 5:10 PM, Dave Dyer dd...@real-me.net wrote: Storing an opening book for the first 10 moves requires 331477745148242200 nodes. Even with some reduction for symmetry, I don't see that much memory becoming available anytime soon, and you still have to evaluate them somehow. Actually storing a tree, except for extremely limited special cases, is not even conceptually possible, and doesn't save much time. Consider that if you store the tree you saw at the previous move, by the time you get to use the stored tree 99% of it is useless because your opponent chose his move. ___ 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] Re: Implications of a CPU vs Memory trend on MCTS
And for MCTS it is much lower than 10. 2009/5/12 terry mcintyre terrymcint...@yahoo.com In the opening, among reasonably clueful players, the branching factor is much closer to 10 than to 361. Terry McIntyre terrymcint...@yahoo.com On general principles, when we are looking for a solution of a social problem, we must expect to reach conclusions quite opposed to the usual opinions on the subject; otherwise it would be no problem. We must expect to have to attack, not what is commonly regarded as objectionable, but what is commonly regarded as entirely proper and normal. – John Beverley Robinson, 1897 -- *From:* Michael Williams michaelwilliam...@gmail.com ** *Subject:* Re: [computer-go] Re: Implications of a CPU vs Memory trend on MCTS You have made the assumption that the move that your opponent selected was on average explored equally as much as all of the other moves. That seems a bit pessimistic. One would expect that the opponent selected a strong move and one would also expect that your tree explored that strong move more than it did other moves. I'm not saying keeping the tree is a huge benefit. I'm just saying that I don't think your 99% number is fair. Dave Dyer wrote: At 02:13 PM 5/12/2009, Michael Williams wrote: Where does your 99% figure come from? 1/361 1% by endgame there are still easily 100 empty spaces on the board. ___ 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] Re: Implications of a CPU vs Memory trend on MCTS
On Tue, May 12, 2009 at 6:05 PM, Don Dailey dailey@gmail.com wrote: And for MCTS it is much lower than 10. 2009/5/12 terry mcintyre terrymcint...@yahoo.com In the opening, among reasonably clueful players, the branching factor is much closer to 10 than to 361. I assume Dave Dyer does not understand alpha beta pruning either, or he would not assume the branching factor is 361.But the pruning we are doing is far more severe than even alpha/beta pruning.(In a theoretical sense this is not true because a proper MCTS eventually would have to explore the tree in alpha/beta fashion to provide a proof.)In practical MC programs the effective BF is extremely low. - Don Terry McIntyre terrymcint...@yahoo.com On general principles, when we are looking for a solution of a social problem, we must expect to reach conclusions quite opposed to the usual opinions on the subject; otherwise it would be no problem. We must expect to have to attack, not what is commonly regarded as objectionable, but what is commonly regarded as entirely proper and normal. – John Beverley Robinson, 1897 -- *From:* Michael Williams michaelwilliam...@gmail.com ** *Subject:* Re: [computer-go] Re: Implications of a CPU vs Memory trend on MCTS You have made the assumption that the move that your opponent selected was on average explored equally as much as all of the other moves. That seems a bit pessimistic. One would expect that the opponent selected a strong move and one would also expect that your tree explored that strong move more than it did other moves. I'm not saying keeping the tree is a huge benefit. I'm just saying that I don't think your 99% number is fair. Dave Dyer wrote: At 02:13 PM 5/12/2009, Michael Williams wrote: Where does your 99% figure come from? 1/361 1% by endgame there are still easily 100 empty spaces on the board. ___ 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] Re: Implications of a CPU vs Memory trend on MCTS
It's possible for the tree to become too narrow. On a 9x9 board, you might be able to say that there are only one or two playable moves, but on 19x19, I doubt that any pro would claim that the options are that narrow, even accounting for symmetry, It's common to hear that some pros play A, some B, some C or D in this situation. Moderately strong amateurs play one of these other options, which are mistakes because ... An opening book could benefit from knowing how to respond to the options considered by both pros and strong amateurs. As for weaker players like me, we tend to be somewhat more creative, you'll just have to work it out on the fly. I think an efficient opening book would be organized on principles similar to huffman encoding: it would devote space to high-probability branches, and less to the weird stuff - but enough memory might be retained to eventually observe Gee, opponent X does this a lot, and I have discovered a good refutation Y. Terry McIntyre terrymcint...@yahoo.com On general principles, when we are looking for a solution of a social problem, we must expect to reach conclusions quite opposed to the usual opinions on the subject; otherwise it would be no problem. We must expect to have to attack, not what is commonly regarded as objectionable, but what is commonly regarded as entirely proper and normal. But as Don says, this needs to be integrated with the basic search algorithm to scale well. I recently tried a few games against Leela, where the first 8 opening plays were predetermined ( a mini chinese opening ). This is not the usual style of Leela. I find that I can win either side of the same position. When Leela and I start with an empty board, I have a harder time of it; Leela's style is not mine. – John Beverley Robinson, 1897 From: Don Dailey dailey@gmail.com To: computer-go computer-go@computer-go.org Sent: Tuesday, May 12, 2009 3:14:55 PM Subject: Re: [computer-go] Re: Implications of a CPU vs Memory trend on MCTS On Tue, May 12, 2009 at 6:05 PM, Don Dailey dailey@gmail.com wrote: And for MCTS it is much lower than 10. 2009/5/12 terry mcintyre terrymcint...@yahoo.com In the opening, among reasonably clueful players, the branching factor is much closer to 10 than to 361. I assume Dave Dyer does not understand alpha beta pruning either, or he would not assume the branching factor is 361.But the pruning we are doing is far more severe than even alpha/beta pruning.(In a theoretical sense this is not true because a proper MCTS eventually would have to explore the tree in alpha/beta fashion to provide a proof.)In practical MC programs the effective BF is extremely low. - Don Terry McIntyre terrymcint...@yahoo.com On general principles, when we are looking for a solution of a social problem, we must expect to reach conclusions quite opposed to the usual opinions on the subject; otherwise it would be no problem. We must expect to have to attack, not what is commonly regarded as objectionable, but what is commonly regarded as entirely proper and normal. – John Beverley Robinson, 1897 From: Michael Williams michaelwilliam...@gmail.com Subject: Re: [computer-go] Re: Implications of a CPU vs Memory trend on MCTS You have made the assumption that the move that your opponent selected was on average explored equally as much as all of the other moves. That seems a bit pessimistic. One would expect that the opponent selected a strong move and one would also expect that your tree explored that strong move more than it did other moves. I'm not saying keeping the tree is a huge benefit. I'm just saying that I don't think your 99% number is fair. Dave Dyer wrote: At 02:13 PM 5/12/2009, Michael Williams wrote: Where does your 99% figure come from? 1/361 1% by endgame there are still easily 100 empty spaces on the board. ___ 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/
[computer-go] Re: Implications of a CPU vs Memory trend on MCTS
An essential feature of monte carlo is that it's search space is random and extremely sparse, so consequently opportunity to re-use nodes is also extremely sparse. On the other hand, if the search close to the root is not sparse, my previous arguments about the number of nodes and the number of them that will continue to be useful still apply. ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
Re: [personal] Re: [computer-go] Re: Implications of a CPU vs Memory trend on MCTS
I assume Dave Dyer does not understand alpha beta pruning either, or he would not assume the branching factor is 361. The branch at the root is about (361-move number) - you have to consider all top level moves. A/B only kicks in by lowering the average branching factor at lower levels. If you're trying to save and reuse trees to reduce work, alpha beta makes most of the saved nodes useless for anything outside the principle variation. This is precisely because the nodes were mostly not fully explored, and all you know (from the previous evaluation) is that this node is better or worse than some other, now-irrelevant branch. I did a lot of work trying to reuse trees for iterative deepening of alpha-beta searches. It required a lot of bookkeeping and a lot of memory, and it didn't turn out to be a good strategy even for small searches where the memory was essentially cost free. I suppose it's possible there's something fundamentally different here, but you ought to think carefully before investing in terrabyte memories. ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
Re: [computer-go] Re: Implications of a CPU vs Memory trend on MCTS
On Tue, May 12, 2009 at 6:33 PM, Dave Dyer dd...@real-me.net wrote: An essential feature of monte carlo is that it's search space is random and extremely sparse, so consequently opportunity to re-use nodes is also extremely sparse. That depends. Monte Carlo only expands node it considered promising and it's very focused on only expanding those nodes. At some point however, it does accumulate nodes that are worthless in the sense that (for the most part) it is very unlikely to visit again. But it may spend some time deciding that and it's information you don't really want to discard if you can avoid it. On the other hand, if the search close to the root is not sparse, my previous arguments about the number of nodes and the number of them that will continue to be useful still apply. I think we are talking about 2 different things. Tell me if I am correct, but I think you are trying to say that storing the tree won't help in most positions, because after even a very few moves you will get no utility out of this.If that's what you mean, then I agree.But that's not what I'm saying. Let's say I do a 10 second search and generate 50,000 nodes. I've generated 50,000 nodes that are all useful in accord with the MCTS algorithm I'm using. If I use persistent storage and do that search again in another game, I can start exactly where I left off and generate 50,000 more nodes. It will be the same as if I did 100,000 nodes instead of 50,000 nodes.Or put another way, it will be the same as if I spent 20 seconds on this move instead of 10 seconds. NONE of these nodes can be considered not useful and I think you are way off based to think that. They were generated by a search and we consider MCTS pretty useful, and a good MCTS is pretty effective about not generating a lot of not useful moves.What I'm saying is that we may not have to simply throw this hard earned information away. Will this help much on 19x19?I think it might a little. If you persistently save the tree, you will tend to play the same moves - which means you will get good utility out of this and may fairly quickly have accumulated a lot of saved search effort - even if for only a few of the first move choices. Is this better than a human generated book? No, but that doesn't matter. Even In 9x9 it seems like you need a human book, even in 7x7 it seems to be the case. But I opened this discussion specific about automated book generation. - 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: [personal] Re: [computer-go] Re: Implications of a CPU vs Memory trend on MCTS
On Tue, May 12, 2009 at 6:47 PM, Dave Dyer dd...@real-me.net wrote: I assume Dave Dyer does not understand alpha beta pruning either, or he would not assume the branching factor is 361. The branch at the root is about (361-move number) - you have to consider all top level moves. A/B only kicks in by lowering the average branching factor at lower levels. If you're trying to save and reuse trees to reduce work, alpha beta makes most of the saved nodes useless for anything outside the principle variation. This is precisely because the nodes were mostly not fully explored, and all you know (from the previous evaluation) is that this node is better or worse than some other, now-irrelevant branch. But then MCTS is invalid. The point is that you do spend time learning that these nodes are not relevant, so you might as well try to remember that. If you are playing a game of chess and fall for a trap, do you consider it silly to try to remember this for the next game? - Don I did a lot of work trying to reuse trees for iterative deepening of alpha-beta searches. It required a lot of bookkeeping and a lot of memory, and it didn't turn out to be a good strategy even for small searches where the memory was essentially cost free. I suppose it's possible there's something fundamentally different here, but you ought to think carefully before investing in terrabyte memories. ___ 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: Implications of a CPU vs Memory trend on MCTS
If I use persistent storage and do that search again in another game, I can start exactly where I left off and generate 50,000 more nodes. It will be the same as if I did 100,000 nodes instead of 50,000 nodes.Or put another way, it will be the same as if I spent 20 seconds on this move instead of 10 seconds. Sure, but except for openings you'll never reach the same position position in another game unless the players are deliberately copying their play. Consider move 20 (for example). If you saved every move 20 node you ever encountered, how often do you think you'd encounter a duplicate from a different game, such that you can either avoid an evaluation, or improve your knowledge of that position by studying it a bit more. I contend it is a vanishingly small percentage. -- ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
[computer-go] Re: Implications of a CPU vs Memory trend on MCTS
But then MCTS is invalid. The point is that you do spend time learning that these nodes are not relevant, so you might as well try to remember that. It is invalid. It's just a heuristic that is working within the current domain. If you are playing a game of chess and fall for a trap, do you consider it silly to try to remember this for the next game? The point is that if your opponent wanders into a space you did not consider, you still have to know how to respond. What clever humans recognize as the same trap is actually just one of zillions of similar positions that will be flooding your database of known positions. ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
Re: [computer-go] Re: Implications of a CPU vs Memory trend on MCTS
more nodes. It will be the same as if I did 100,000 nodes instead of 50,000 nodes.Or put another way, it will be the same as if I spent 20 seconds on this move instead of 10 seconds. ... Consider move 20 (for example). If you saved every move 20 node you ever encountered, how often do you think you'd encounter a... Hi Dave, You are right that by move 20 you are unlikely to get a repeated game. But by having that information in the tree, the decision made at move 5 is more accurate. Basically what Don's suggestion means is for the first few moves of the game (while you are playing a game that has been seen before) it is as if your program is playing on hardware that is N times quicker (where N is the number of times this position has been seen before). I think a UCT tree seeded with a large pro/strong-player game library would be useful, and is basically the same idea. It would encourage the computer to play well-known fuseki/joseki (without having to work them out from first principles) while still having the UCT tree behind it. Meaning that the level of play would not suddenly drop when the opponent leaves your opening library, and meaning it would not suddenly find itself in a situation that it does not understand. Darren -- Darren Cook, Software Researcher/Developer http://dcook.org/mlsn/ (English-Japanese-German-Chinese-Arabic open source dictionary/semantic network) http://dcook.org/work/ (About me and my work) http://dcook.org/blogs.html (My blogs and articles) ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
Re: [computer-go] Re: Implications of a CPU vs Memory trend on MCTS
On Tue, May 12, 2009 at 8:17 PM, Dave Dyer dd...@real-me.net wrote: If I use persistent storage and do that search again in another game, I can start exactly where I left off and generate 50,000 more nodes. It will be the same as if I did 100,000 nodes instead of 50,000 nodes.Or put another way, it will be the same as if I spent 20 seconds on this move instead of 10 seconds. Sure, but except for openings you'll never reach the same position position in another game unless the players are deliberately copying their play. I think you still miss the point. I don't expect this to help on move 20, only for the early positions you have seen before. When I play chess, I play the first few moves almost instantly, without making a blunder. I can do this because I have studied those positions and know them thoroughly. It's not because I memorized them, even though I have.As soon as I get to positions I am less familiar with, I slow down to a crawl, because now I have to try to figure them out over the board. Of course my knowledge of the opening helps some, even when I'm out of the book I have a good sense of how to proceed. With GO, a computer can do the same. It's almost ridiculous to search the opening position from scratch, as it we are a totally moron and have never see that position before. There is no reason not to study it and remember what we learned about it.There is no reason not to apply this to as many moves as possible in the opening, even if it's only a very few. I don't understand why this is not immediately obvious to you. What I suggest is superior to just memorizing what moves to play, you can actually save the tree and in a sense it's like a program actually understands the position, not just play by rote. If it's a position you already searched, you will have at least a little head start no matter what the opponent plays.Even if the opponent surprises you, you will have a piece of the tree intact and the next time this same situation happens, you will now have some serious analysis already pre-computed. With 19x19 this is probably not a huge ELO booster, but there is certainly nothing unsound about it either. And it may not be as bad as you think because the computer will tend to be deterministic about which moves it plays which by itself drastically lowers the branching factor. If it fails to play the same in a position it has already seen, that is not a bad thing either, it indicates that it found a move it likes better, perhaps discovering that something was wrong with the previous choice. That's exactly what you hope it does. Consider move 20 (for example). If you saved every move 20 node you ever encountered, how often do you think you'd encounter a duplicate from a different game, such that you can either avoid an evaluation, or improve your knowledge of that position by studying it a bit more. I contend it is a vanishingly small percentage. I don't believe you want to save the tree beyond the point where you are in a position you have never seen for the very reason you state. It's very unlikely that you will still be a part of the tree you have visited before. I thought I already conceded that point? Didn't I already say that this is an idea for the first few moves? But this idea will save you time that can be spend in later moves, so it can actaully benefit the moves you make later in the game. But more importantly it can prevent you from being in a losing position by move 20 from a bad move choice on move 5. - 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/
