Re: [computer-go] Re: Scaling monte carlo up to 19x19
Nick Apperson wrote: > There are certain times when this technique is highly useful. ... > imagine a board with two walls down the middle bordering on each other I agree. We have to divide the board to create strong programs! But division is a very complicated subject. In the isolated areas UCT can be a very strong tool. But if you divide the board using a ruler, just like Africa was divided some time ago, you only create more problems. Division has to be done with great understanding of the position and using natural and foreseeable borders. Jacques. ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
Re: [computer-go] Re: Scaling monte carlo up to 19x19
On Wed, 2007-01-31 at 04:00 -0800, Dave Dyer wrote: > > > >Of course, everything depends on how you can deal with the boarders - how > >about some monte-carlo-simulations over the possible boarder-configurations? > > My thought is that one thing you could easily get from the rollouts > is a good estimate of the status of each string of stones currently > on the board, and the eventual owner of each empty space. Monte Carlo is quite good at this - and Botnoid uses this information to modify it's move choices to a certain extent and it gives it a pretty good boost in strength. I think you have to do more than just partitioning, you might have to assign the stones on the borders of the partition some status such as "never die" or something.A string that straddles a partition may have only 1 liberty in the other partition so perhaps just allowing simple captures outside your partition would be a big improvement. I think this is worth pursuing - but it's going to very tricky getting it right. - Don > In the zone logic, stones adjacent to the border would count the border > as friendly or unfriendly based on the best estimate of that status. > > ___ > 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: Scaling monte carlo up to 19x19
> >Of course, everything depends on how you can deal with the boarders - how >about some monte-carlo-simulations over the possible boarder-configurations? My thought is that one thing you could easily get from the rollouts is a good estimate of the status of each string of stones currently on the board, and the eventual owner of each empty space. In the zone logic, stones adjacent to the border would count the border as friendly or unfriendly based on the best estimate of that status. ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
Re: [computer-go] Re: Scaling monte carlo up to 19x19
Funny thing, I also just thought about this as a friend of mine had an idea similiar to Dave's. I guess it might be a good idea to make your zone-partitioning (or zone-merging, when you start from 1x1-boards) dependant of the current board configuration. That is, some clever algorithm (probably another kind of MC) might judge the "interdependencies" over the board graph and decide what is better dealt with together and what might be looked at alone. Of course, everything depends on how you can deal with the boarders - how about some monte-carlo-simulations over the possible boarder-configurations? ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
Re: [computer-go] Re: Scaling monte carlo up to 19x19
I'm working now in a similar idea. As yours, it will play only in one zone using MC. It will start on 7x7 sub-boards but they will grow once they become full of stones. I will normalize the sub-board results using its area. It will help me to compare the different sub-boards. Once all the sub-boards get evaluated, it will play in the sub-board with less winning moves (first the urgent, then the important). But the main idea is the same as yours: scale breaking the board down. 2007/1/30, Dave Dyer <[EMAIL PROTECTED]>: Here's an idea for scaling up, which should result in "only" factor of 10 slower speed. To scale from 9x9 to 19x19, subdivide the board into four, overlapping 10x10 boards. Run a standard 9x9 monte carlo up to the 90% full stage on each of the four boards, then run a full board monte on the whole board remaining. Treat the ovelapping stripes as edges in a slightly more sophisticated way than usual, becuase you might be connecting to liberties by playing in the stripe. To avoid artifacts caused by the location of the overlaps: the number of zones, and the location of the stripes, is also subject to randomization. It might be interesting to try this on a 9x9 board using a 5x5 zone to begin with. ___ 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: Scaling monte carlo up to 19x19
I believe this to be a good idea, but I couldn't get around some minor problems. Essentially, because the local searches are coupled to one another, it ends up exploding as you consider this coupling (scaling to larger regions). You then have to trade accuracy or have more computing power than I have access to... There are cases though where you can find local solutions that are independent in some sense from the rest of the board and the program I am working on now does that. I'm sure someone smarter than me will be able to figure out a better way though. There are certain times when this technique is highly useful. For a simple example, imagine a board with two walls down the middle bordering on each other. In some sense, as long as both those walls live, there are 2 subgames taking place. This type of situation is where I see your approach as being the most useful. Just my thoughts. - Nick On 1/30/07, Weston Markham <[EMAIL PROTECTED]> wrote: I have an idea in the back of my mind that is an extreme version of this: Divide the board into 361 separate local searches, then use information from these to guide a global search. The local searches would be done on the full board, but would only search for strategies that will capture or defend individual intersections. I suspect that this first phase could potentially benefit from parallelization for a significant portion of the game. Eventually this parallelism will break down because there will only be a limited number of local battles, and the eventual status of points that are in the same chain will almost always be the same. Any practical program would need to deal with this gracefully, of course, rather than duplicate its effort many times. Also, I only have a vague idea of how to take advantage of the information gained from the local searches, when performing the global search. Weston On 1/30/07, Dave Dyer <[EMAIL PROTECTED]> wrote: > The idea isn't more than lightly toasted (less than half baked), but > the kernal is turn the full board search into set of searches on > much smaller boards, using the overlapping strips as boundary > conditions, then do some unifying final step to pick the 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: Scaling monte carlo up to 19x19
> The idea isn't more than lightly toasted (less than half baked), but > the kernal is turn the full board search into set of searches on > much smaller boards, using the overlapping strips as boundary > conditions, then do some unifying final step to pick the move. how would it handle the following situation: the best move is to start a ladder in the upper-left quadrant of the board and there is a ladder-breaker in the bottom-right quadrant of the board. this won't look like a good move in any single quadrant search. it'll look good for a full-board search, but only if you look deep enough to see the ladder breaker come into play. s. The fish are biting. Get more visitors on your site using Yahoo! Search Marketing. http://searchmarketing.yahoo.com/arp/sponsoredsearch_v2.php ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
Re: [computer-go] Re: Scaling monte carlo up to 19x19
I have an idea in the back of my mind that is an extreme version of this: Divide the board into 361 separate local searches, then use information from these to guide a global search. The local searches would be done on the full board, but would only search for strategies that will capture or defend individual intersections. I suspect that this first phase could potentially benefit from parallelization for a significant portion of the game. Eventually this parallelism will break down because there will only be a limited number of local battles, and the eventual status of points that are in the same chain will almost always be the same. Any practical program would need to deal with this gracefully, of course, rather than duplicate its effort many times. Also, I only have a vague idea of how to take advantage of the information gained from the local searches, when performing the global search. Weston On 1/30/07, Dave Dyer <[EMAIL PROTECTED]> wrote: The idea isn't more than lightly toasted (less than half baked), but the kernal is turn the full board search into set of searches on much smaller boards, using the overlapping strips as boundary conditions, then do some unifying final step to pick the move. ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
[computer-go] Re: Scaling monte carlo up to 19x19
At 02:59 PM 1/30/2007, [EMAIL PROTECTED] wrote: > I'm having difficulty picturing this, so I'll start with the most basic > questions. > >Do you mean Monte Carlo by itself or Monte Carlo combined with tree search >(e.g. UCT)? > The idea isn't more than lightly toasted (less than half baked), but the kernal is turn the full board search into set of searches on much smaller boards, using the overlapping strips as boundary conditions, then do some unifying final step to pick the move. >Do you mean partition the larger board for the course of each playout >(randomizing zones from one to the next) or in some other sense? I imagine you'd want to randomizing the set of zones in the course of the search. ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
Re: [computer-go] Re: Scaling monte carlo up to 19x19
I'm having difficulty picturing this, so I'll start with the most basic questions. Do you mean Monte Carlo by itself or Monte Carlo combined with tree search (e.g. UCT)? Do you mean partition the larger board for the course of each playout (randomizing zones from one to the next) or in some other sense? - Dave Hillis -Original Message- From: [EMAIL PROTECTED] To: computer-go@computer-go.org; computer-go@computer-go.org Sent: Tue, 30 Jan 2007 3:00 PM Subject: [computer-go] Re: Scaling monte carlo up to 19x19 Here's an idea for scaling up, which should result in "only" factor of 10 slower speed. To scale from 9x9 to 19x19, subdivide the board into four, overlapping 10x10 boards. Run a standard 9x9 monte carlo up to the 90% full stage on each of the four boards, then run a full board monte on the whole board remaining. Treat the ovelapping stripes as edges in a slightly more sophisticated way than usual, becuase you might be connecting to liberties by playing in the stripe. To avoid artifacts caused by the location of the overlaps: the number of zones, and the location of the stripes, is also subject to randomization. It might be interesting to try this on a 9x9 board using a 5x5 zone to begin with. ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/ Check Out the new free AIM(R) Mail -- 2 GB of storage and industry-leading spam and email virus protection. ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
[computer-go] Re: Scaling monte carlo up to 19x19
Here's an idea for scaling up, which should result in "only" factor of 10 slower speed. To scale from 9x9 to 19x19, subdivide the board into four, overlapping 10x10 boards. Run a standard 9x9 monte carlo up to the 90% full stage on each of the four boards, then run a full board monte on the whole board remaining. Treat the ovelapping stripes as edges in a slightly more sophisticated way than usual, becuase you might be connecting to liberties by playing in the stripe. To avoid artifacts caused by the location of the overlaps: the number of zones, and the location of the stripes, is also subject to randomization. It might be interesting to try this on a 9x9 board using a 5x5 zone to begin with. ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
