Re: [Computer-go] Using 9x9 policy on 13x13 and 19x19
Perfect, thank you. I was wondering about doing this with a fully-convolutional architecture, and it looks like that is what you are doing! On Thu, Mar 1, 2018 at 2:21 PM, Hiroshi Yamashita wrote: > Hi Imran, > > I have only changed input shape. > On Caffe, > > from 9x9 > input_dim: 1 > input_dim: 50 > input_dim: 9 > input_dim: 9 > > to 19x19 > input_dim: 1 > input_dim: 50 > input_dim: 19 > input_dim: 19 > > This is available on fully convolutional. > http://computer-go.org/pipermail/computer-go/2015-December/008324.html > > Caffe's prototxt is > http://www.yss-aya.com/20180302using9x9_19x19.tar.gz > > Thanks, > Hiroshi Yamashita > > > On 2018/03/02 0:35, Imran Hendley wrote: > >> Hi Hiroshi, >> >> Are you using zero-padding to allow input shapes to match for all board >> sizes? >> >> Thanks, >> Imran >> >> ___ > Computer-go mailing list > Computer-go@computer-go.org > http://computer-go.org/mailman/listinfo/computer-go > ___ Computer-go mailing list Computer-go@computer-go.org http://computer-go.org/mailman/listinfo/computer-go
Re: [Computer-go] Using 9x9 policy on 13x13 and 19x19
Hi Hiroshi, Are you using zero-padding to allow input shapes to match for all board sizes? Thanks, Imran On Thu, Mar 1, 2018 at 12:06 AM, Cornelius wrote: > Hi Sighris, > > i have always thought that creating algorithms for arbitrary large go > boards should enlighten us in regards to playing on smaller go boards. > > A humans performance doesn't differ that much on differently sized large > go boards and it scales pretty well. For example one would find it > rather easy to evaluate large dragons or ladders. The currently used > neural algorithms (NNs) do not perform well in this regard. > > Maybe some form of RNN could be integrated into the evaluation. > > > BR, > Cornelius > > > Am 24.02.2018 um 08:23 schrieb Sighris: > > I'm curious, does anybody have any interest in programs for 23x23 (or > > larger) Go boards? > > > > BR, > > Sighris > > > > > > On Fri, Feb 23, 2018 at 8:58 AM, Erik van der Werf < > erikvanderw...@gmail.com > >> wrote: > > > >> In the old days I trained separate move predictors on 9x9 games and on > >> 19x19 games. In my case, the ones trained on 19x19 games beat the ones > >> trained on 9x9 games also on the 9x9 board. Perhaps it was just because > of > >> was having better data from 19x19, but I thought it was interesting to > see > >> that the 19x19 predictor generalized well to smaller boards. > >> > >> I suppose the result you see can easily be explained; the big board > policy > >> learns about large scale and small scale fights, while the small board > >> policy doesn't know anything about large scale fights. > >> > >> BR, > >> Erik > >> > >> > >> On Fri, Feb 23, 2018 at 5:11 PM, Hiroshi Yamashita > >> wrote: > >> > >>> Hi, > >>> > >>> Using 19x19 policy on 9x9 and 13x13 is effective. > >>> But opposite is? > >>> I made 9x9 policy from Aya's 10k playout/move selfplay. > >>> > >>> Using 9x9 policy on 13x13 and 19x19 > >>> 19x19 DCNNAyaF128from9x91799 > >>> 13x13 DCNNAyaF128from9x91900 > >>> 9x9 DCNN_AyaF128a558x12290 > >>> > >>> Using 19x19 policy on 9x9 and 13x13 > >>> 19x19 DCNN_AyaF128a523x12345 > >>> 13x13 DCNNAya795F128a5232354 > >>> 9x9 DCNN_AyaF128a523x12179 > >>> > >>> 19x19 policy is similar strength on 13x13 and 166 Elo weaker on 9x9. > >>> 9x9 policy is 390 Elo weaker on 13x13, and 491 Elo weaker on 19x19. > >>> It seems smaller board is more useless than bigger board... > >>> > >>> Note: > >>> All programs select maximum policy without search. > >>> All programs use opening book. > >>> 19x19 policy is Filter128, Layer 12, without Batch Normalization. > >>> 9x9 policy is Filter128, Layer 11, without Batch Normalization. > >>> 19x19 policy is made from pro 78000 games, GoGoD. > >>> 9x9 policy is made from 10k/move. It is CGOS 2892(Aya797c_p1v1_10k). > >>> Ratings are BayesElo. > >>> > >>> Thanks, > >>> Hiroshi Yamashita > >>> > >>> ___ > >>> Computer-go mailing list > >> > >> > >> ___ > >> Computer-go mailing list > > > > > > > > ___ > > Computer-go mailing list > > Computer-go@computer-go.org > > http://computer-go.org/mailman/listinfo/computer-go > > > > ___ > Computer-go mailing list > Computer-go@computer-go.org > http://computer-go.org/mailman/listinfo/computer-go > ___ Computer-go mailing list Computer-go@computer-go.org http://computer-go.org/mailman/listinfo/computer-go
[Computer-go] Does AlphaZero use a 20-block or 40-block resnet?
The AlphaGo Zero paper tests 20 and 40 block resnet architectures (among others), and in the AlphaZero paper AlphaZero Go plays against the 20-block AlphaGo Zero, but I cannot find any mention of which architecture AlphaZero is using! I'm assuming they are using either the 20 or 40 block resnets - Does anyone know which? ___ Computer-go mailing list Computer-go@computer-go.org http://computer-go.org/mailman/listinfo/computer-go
[Computer-go] What happens if you only feed the current board position to AGZ?
AlphaGo Zero's Neural Network takes a 19x19x17 input representing the current and 15 previous board positons, and the side to play. What if you were to only give it the current board position and side to play, and you handled all illegal ko moves only in the tree? So obviously the network cannot distinguish between two identical positions one where there is an illegal ko move and one where there is not. But after running MCTS long enough and expanding the tree AGZ should understand what is going on, right? Does this just make it require more time to find the best move, or is it somehow fundamentally broken? The only thing I can think of is that ko threats might sometimes linger for a very long time, so maybe this is a big problem, but my understanding of Go is limited. For comparison, the original AlphaGo used a feature plane of ones and zeros to indicate legal and illegal moves. ___ Computer-go mailing list Computer-go@computer-go.org http://computer-go.org/mailman/listinfo/computer-go
Re: [Computer-go] AlphaGo Zero self-play temperature
Great, thanks guys! On Tue, Nov 7, 2017 at 1:51 PM, Gian-Carlo Pascutto wrote: > On 7/11/2017 19:07, Imran Hendley wrote: > > Am I understanding this correctly? > > Yes. > > It's possible they had in-betweens or experimented with variations at > some point, then settled on the simplest case. You can vary the > randomness if you define it as a softmax with varying temperature, > that's harder if you only define the policy as select best or select > proportionally. > > -- > GCP > ___ > Computer-go mailing list > Computer-go@computer-go.org > http://computer-go.org/mailman/listinfo/computer-go > ___ Computer-go mailing list Computer-go@computer-go.org http://computer-go.org/mailman/listinfo/computer-go
[Computer-go] AlphaGo Zero self-play temperature
Hi, I might be having trouble understanding the self-play policy for AlphaGo Zero. Can someone let me know if I'm on the right track here? The paper states: In each position s, an MCTS search is executed, guided by the neural network f_θ . The MCTS search outputs probabilities π of playing each move. This wasn't clear at first since MCTS outputs wins and visits, but later the paper explains further: MCTS may be viewed as a self-play algorithm that, given neural network parameters θ and a root position s, computes a vector of search probabilities recommending moves to play, π = α_θ(s), proportional to the exponentiated visit count for each move, π_a ∝ N(s, a)^(1/τ) , where τ is a temperature parameter. So this makes sense, but when I looked for the schedule for decaying the temperature all I found was the following in the Self-play section of Methods: For the first 30 moves of each game, the temperature is set to τ = 1; this selects moves proportionally to their visit count in MCTS, and ensures a diverse set of positions are encountered. For the remainder of the game, an infinitesimal temperature is used, τ→0. This sounds like they are sampling proportional to visits for the first 30 moves since τ = 1 makes the exponent go away, and after that they are playing the move with the most visits, since the probability of the move with the most visits goes to 1 and the probability of all other moves goes to zero in the expression π(a | s_0) = N(s_0 , a)^(1/τ) / ∑ b N(s_0 , b)^(1/τ) as τ goes to 0 from the right. Am I understanding this correctly? I am confused because it seems a little convoluted to define this simple policy in terms of a temperature. When they mentioned temperature I was expecting something that slowly decays over time rather than only taking two trivial values. Thanks! ___ Computer-go mailing list Computer-go@computer-go.org http://computer-go.org/mailman/listinfo/computer-go
Re: [computer-go] Re: mogo beats pro!
> > I flipped memory and time there. If pspace-complete is not in p, then it > will be a big problem trying to solve it without infinite time. That doesn't > seem like an ideal situation for solving it. > You only need an infinite amount of time for undecidable problems. np-complete, pspace, exptime, etc. are just intractable. I think we are more interested in how long before we can achieve superhuman play though, since perfect play seems impossible based on what we know about computation, the limitations of the physical world etc. I want to say 7-10 years, but it's really hard to predict when the necessary algorithmic advances will come. At worst we will just have to wait until robots take over the world in 20 years. ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
Re: [computer-go] Re: mogo beats pro!
> go is worse than np-complete, it's pspace-complete. > > s. > I thought it was even worse than that ;) ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
Re: [computer-go] CGOS 19x19 up and running
Hi, Are the old game archives still available anywhere, or will they be in future? I am missing May, June, and July, and I was meaning to download them. Have I missed my chance? On Sun, Aug 3, 2008 at 11:09 AM, Don Dailey <[EMAIL PROTECTED]> wrote: > Ok, > > I have 19x19 up and running. Instructions are basically the same as > for 13x13, the only thing changing about the web pages and so on in the > urls's is the directory /19x19/ instead of /13x13/ and the port for > the client is 6819. > > I will update the main web page to reflect the changes and provide links > later. > > - Don > > > ___ > computer-go mailing list > computer-go@computer-go.org > http://www.computer-go.org/mailman/listinfo/computer-go/ > ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
Re: [computer-go] A small optimization for scoring random playouts
On Dec 19, 2007 5:55 PM, <[EMAIL PROTECTED]> wrote: > Depending on your rule set, you might not want to use stones captured. > Oh wow, thanks for the tip. I guess that's what happens when you learn the rules of go the same day you start writing your program. And I take back everything I yelled at GNU Go when it didn't count the captured stones in its area score. ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
[computer-go] A small optimization for scoring random playouts
I'm not sure if everyone does this already, but I realized that at the end of a random playout there are no territories bigger than one intersection, so you don't really need to call your area score method in most cases. Let D = blackStonesOnBoard - whiteStonesOnBoard + whiteStonesCaptured - blackStonesCaptured - komi. If abs(D) > K for some small threshold K (I use size/2 = 4 for a 9x9 board, but you can use size if you want to be super safe) then D>0 means black wins, white wins otherwise. The only problem is when D is close to 0, since the real area score also counts each eye as one point and this is not reflected in D. So depending on how many eyes each side has, the result might go one way or another. We can either keep track of the number of eyes and update D accordingly, or we can just call the area score method for these borderline cases. If we do the latter we are still saving a lot of time in most cases if we choose K small enough. This gave me a nice speedup of 10% or so if I remember correctly. ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
Re: [computer-go] random numbers with functional languages
On Dec 19, 2007 11:25 AM, Don Dailey <[EMAIL PROTECTED]> wrote:
>
> Imran Hendley wrote:
> > A sorry about that. Glad to hear you fixed the problem. What was your
> > solution?
> >
> > It seems you mentioned the "global list" approach in your email which
> > I missed too. Why did you think this was an ugly approach? I just put
> > my random array in a Singleton object (call it
> > MyRandomNumberGenerator) which internally stores the next index and
> > has a method for getting the next random number. So I just replace all
> > my calls to Random.getNextInt() with
> > MyRandomNumberGenerator.getNextInt(). Actually I can see how a lot of
> > people would still call this ugly... But it's just a lookup so I think
> > it will beat any other solution that involves generating a new random
> > number by a reasonable margin.
> You are spending time before the game to save time during the game - a
> good principle in general but you do have a few issues:
>
> 1. How does this affect cache? (probably not much but you have to
> consider it.)
> 2. Can you get enough numbers to last a complete game?
>
> If this is so slow, then there would be a long delay each time you
> generate a new set of random numbers and I really think you should do
> this between games. I wonder how long the delay is?
>
> If the delay is unduly long (it must be, otherwise you wouldn't have to
> do this) then an alternative is to change a fraction of the numbers
> between games:
>
> // code to randomly change 1000 values:
>
> for (i=0; i<1000; i++) {
>ix = randomInt( RANDOM_ARRAY_SIZE );
>randArray[ ix ] = newRandomNumber();
> }
>
> In other words, pick a few array locations at random and change their
> value.
>
> This will prevent any serious cycles with long testing sequences.
>
> You could also perform such a routine between moves. You only need to
> change a few so change as many as you can in a fraction of a second.
>
> - Don
>
Don,
I probably go through my entire array 5 times per second during a UCT
search. So far I have been relying on the hope that I do not come back to
the beginning of my array at exactly the same position in a random playout
which would cause a bad cycle. If I come back at a different position then I
will not start replaying the same set of playouts in the search of that
particular game position, and I will also play a different sequence of moves
in this run through the array because I will "reject" different numbers I
get because they correspond to illegal board positions but didn't last time
through the array and vice versa.
I think the chance of a bad cycle is very small. I just did some more
analysis of this just now and it got a little complicated, so I'll leave it
out. However, I do think making a bad cycle impossible is important. Your
idea of reinitializing some random positions in the array looks really good.
Unfortunately there is no way I can do this each time through the array for
any meaningful portion of the whole array...since just resetting my index to
0 when I get to the end is pretty expensive in terms of average cost, and if
I'm going through the array a few times a second I can't do much more than
that each time. What do you think of resetting my index to a random position
between 0 and some small n every time to make the probability of getting
stuck in a cycle forever go to zero, and then finding some free time to
reset the numbers like right after playing a move and before starting to
ponder for example?
And about the cache...I've never really thought about it. How do think the
cache would be affected? I don't really know much about cache's to be
honest. Are you saying that the numbers in my array would get stored in the
cache? Is this good or bad?
Imran
___
computer-go mailing list
computer-go@computer-go.org
http://www.computer-go.org/mailman/listinfo/computer-go/
Re: [computer-go] random numbers with functional languages
A sorry about that. Glad to hear you fixed the problem. What was your solution? It seems you mentioned the "global list" approach in your email which I missed too. Why did you think this was an ugly approach? I just put my random array in a Singleton object (call it MyRandomNumberGenerator) which internally stores the next index and has a method for getting the next random number. So I just replace all my calls to Random.getNextInt() with MyRandomNumberGenerator.getNextInt(). Actually I can see how a lot of people would still call this ugly... But it's just a lookup so I think it will beat any other solution that involves generating a new random number by a reasonable margin. On Dec 19, 2007 5:15 AM, Berk Ozbozkurt <[EMAIL PROTECTED]> wrote: > That was not the problem, as the source code is available and it doesn't > call system libraries at all. I was initializing with known seed in my > tests anyway. > > Thanks though, in the process of composing a reply demonstrating the > problem, I found a partial solution. Now random number generation takes > 3% of running time, compared to 60% of older version and ~1% of a > hypothetical ideal solution. > > Berk. > > Stuart A. Yeates wrote: > > Probably the reason that it is so slow is that it's aiming for a > > cryptographically random number sequence. These are usually derived > > ultimately from kernel timings (often via /dev/random on linux > > systems) and it can take a while to establish a degree of confidence > > in the randomness of these bits. > > > > If you want a sequence of numbers that is very unlikely to repeat but > > that doesn't have to be cryptographically random, standard practice is > > to initialise the random number generator with the current time > > (usually a long expressed in milliseconds). This naturally fails if > > you ever create more than one sequence per millisecond. > > > > cheers > > stuart > > > > > > On 19/12/2007, Berk Ozbozkurt <[EMAIL PROTECTED]> wrote: > > > >> Hi, > >> > >> I'm currently writing a UCT based go program in Clean to see if it is > >> feasible to write one in a functional language. This is my first > attempt > >> at functional languages, and I'm having trouble with random numbers. > >> > >> A mersenne twister module is available for Clean. Once initialized it > is > >> reasonably fast to extract a new random number from the generator. > >> However, it is about a hundred times slower to initialize it with a new > >> random seed. Therefore my first attempt at generating random numbers by > >> storing seeds at tree nodes and creating a new random list and a new > >> seed each time random numbers are required for mc evaluation is very > >> slow. The alternative seems to be passing around an index to a global > >> random list, which is both ugly and complicated. Is there another way? > >> > > ___ > 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] random numbers with functional languages
A couple of things I did: I edited the Mersenne Twister code I'm using to get it's seed from the system time in nanoseconds rather than in miliseconds to fix the problem of wanting to generate more than one random number in a millisecond. Instead of generating a new random number every time I want to pick a move in a random playout, I fill a large circular array with random numbers when my go program launches (before it is actually playing a game) and I have a method that just gets the next number out of the array instead of generating a new random number in real time. Actually I have a different array for each possible board size, since I need a random integer from a different range for each. Sure the array repeats after 500,000 numbers or however many you use, but this is not a big deal when your playouts are only 100 moves long each - and it is unlikely to start repeating from the same position. This approach was much faster than generating random numbers on the fly. On Dec 19, 2007 3:51 AM, Stuart A. Yeates <[EMAIL PROTECTED]> wrote: > Probably the reason that it is so slow is that it's aiming for a > cryptographically random number sequence. These are usually derived > ultimately from kernel timings (often via /dev/random on linux > systems) and it can take a while to establish a degree of confidence > in the randomness of these bits. > > If you want a sequence of numbers that is very unlikely to repeat but > that doesn't have to be cryptographically random, standard practice is > to initialise the random number generator with the current time > (usually a long expressed in milliseconds). This naturally fails if > you ever create more than one sequence per millisecond. > > cheers > stuart > > > On 19/12/2007, Berk Ozbozkurt <[EMAIL PROTECTED]> wrote: > > Hi, > > > > I'm currently writing a UCT based go program in Clean to see if it is > > feasible to write one in a functional language. This is my first attempt > > at functional languages, and I'm having trouble with random numbers. > > > > A mersenne twister module is available for Clean. Once initialized it is > > reasonably fast to extract a new random number from the generator. > > However, it is about a hundred times slower to initialize it with a new > > random seed. Therefore my first attempt at generating random numbers by > > storing seeds at tree nodes and creating a new random list and a new > > seed each time random numbers are required for mc evaluation is very > > slow. The alternative seems to be passing around an index to a global > > random list, which is both ugly and complicated. Is there another way? > > ___ > > 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] Speed of generating random playouts
On Nov 16, 2007 6:38 PM, Chris Fant <[EMAIL PROTECTED]> wrote: > > > > Neat. Was the 15-bit version for 81 values or 361? At the risk of > > > > putting my foot in my mouth, I don't think there exist 361 15-bit > > > > numbers that satisfy minimum requirements (if the floating-point > > > > average of any four code values is a code value, then the four code > > > > values are identical). > > > > > > It was 361 values. So either you are wrong or I have a bug. I > > > probably have a bug. Here's the list. If it violates the rules, > > > please let me know. > > > > Yep, I think I had a bug. I just removed an optimization that I > > thought was valid and now I'm getting smaller lists. So I guess it > > was not valid. Let me see how small I can get the numbers without > > that optimization... > > > > Turns out that wasn't the problem. The actual bug was quite > laughable. I won't get into it. But I should have been more > thorough. Now that it's fixed, yeah, you can't do much with 15 bits. > Best I can do now is 30 bits (for 361 values): Shouldn't we be taking John's advice and only looking for 19 values? He said we can have a separate sum for x and y coordinates. ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
Re: [computer-go] Speed of generating random playouts
> For every string, you can keep track of this sum incrementally.
> When the string establishes a new adjacency to an empty point i,
> you add code[i] into the sum.
OK that's what I thought before then I got really confused. And nums
is just U_all_i code[i], right?
> > if sum a_i <= 4, and sum (a_i * n_i) is in {1,2,3,4} * nums,
> > then only one a_i is nonzero.
So a_i could be 2 and sum(a_i * n_i) could be in 4*nums (for example)
and this would mean that we are in atari? We are not only interested
in whether sum(a_i * n_i) is in sum(a_i) * nums?
___
computer-go mailing list
computer-go@computer-go.org
http://www.computer-go.org/mailman/listinfo/computer-go/
Re: [computer-go] Speed of generating random playouts
On Nov 14, 2007 3:19 PM, John Tromp <[EMAIL PROTECTED]> wrote:
> On Nov 14, 2007 2:00 PM, John Tromp <[EMAIL PROTECTED]> wrote:
>
> > My solution doesn't make use of that, and satisfies the stronger property:
>
> > 0 <= a_i <= 4 and sum a_i * n_i is in 1*nums union 2*nums union 3*nums
> > union 4*nums
> > => only one a_i is nonzero.
>
> that was not quite correct. it should say:
>
> let a_i be the number of adjacencies to a liberty at point i.
>
> if sum a_i <= 4, and sum (a_i * n_i) is in {1,2,3,4} * nums,
> then only one a_i is nonzero.
I'm really lost now. a_i is the number of stones we have adjacent to a
liberty at intersection i? Do we need to know the location of our
liberties to update sum a_i? How is this easier than just remembering
the locations of all real liberties you saw? How do we know that the
stones around i are from the same group? What are the n_i in
sum(a_i*n_i)? is {1,2,3,4}*nums supposed to be a cartesian product of
two sets? Is this related to what you said about encoding x and y
separately?
___
computer-go mailing list
computer-go@computer-go.org
http://www.computer-go.org/mailman/listinfo/computer-go/
Re: [computer-go] Speed of generating random playouts
On Nov 13, 2007 4:05 PM, Jason House <[EMAIL PROTECTED]> wrote: > > > > On Nov 13, 2007 3:57 PM, Petr Baudis <[EMAIL PROTECTED]> wrote: > > > > On Tue, Nov 13, 2007 at 03:32:03PM -0500, John Tromp wrote: > > > On Nov 13, 2007 2:48 PM, Petr Baudis <[EMAIL PROTECTED]> wrote: > > > > > > > I'm now somewhat torn. The speedup from using pseudo-liberty counts > > > > could be huge, estimating from my profiling. On the other hand, it > would > > > > be very useful to still be able to quickly check if a group is in > atari > > > > - it looks like if atari stones would get special attention during the > > > > random games, that could make the bot a lot stronger. > > > > > > > > Is there any known way to get the best of the both worlds? :-) > > > > > > Yes, you can generalize pseudoliberties by extending them > > > with another field, such that if the (summed) pseudoliberty field > > > is between 1 and 4, then the other (summed) field will tell you if all > these > > > are coming from a single true liberty. > > > > Wow, that's great idea! I was trying to think along these lines but > > realized the implementation only after reading what you wrote. > > > > I guess you mean something in the spirit of: > > > >group.xyzzy = 0 > > > >add_liberty(group, coord) > >group.xyzzy += as_int(coord) > > > >remove_liberty(group, coord) > >group.xyzzy -= as_int(coord) > > > >in_atari(group) > >group.pseudlibs <= 4 && is_liberty(group, as_coord( > group.xyzzy)) > > You're right, that would work. > > PS: I think that last one should be: > group.pseudlibs <= 4 && is_liberty(group, > as_coord(group.xyzzy/group.pseudlibs)) I definitely understand the idea now, and it looks very good. However this implementation could break: Say we have pseudoliberties at intersections: 99,100,101. We sum those up to get 300, divide by the number of pseudoliberties - 3, get back 100, check to see if 100 is a liberty, and since it is we conclude that we have one liberty at intersection 100 that we counted three times, and hence our string is in atari. ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
Re: [computer-go] Speed of generating random playouts
On Nov 13, 2007 3:30 PM, Jason House <[EMAIL PROTECTED]> wrote: > > > > On Nov 13, 2007 3:13 PM, Imran Hendley <[EMAIL PROTECTED]> wrote: > > Looking at my code I first check if the number of pseudoliberties is > > less than or equal to 2 (this is necessary but not sufficent for a > > string to be in atari given the way I compute pseudoliberties), which > > is very fast (it just involves a lookup because I have already > > computed pseudoliberties for all strings when the last move was made). > > If this is true I then do a slower check to see if the string in > > question is actually in atari. This gets the best of both worlds > > because most strings (ones with more than two pseudoliberties) are > > ruled out very quickly and only a few are looked at with the slower > > routine that uses real liberties to check for atari. > > > I'm curious how you do that. The simpler problems can fit in 3x3 patterns > such as 5-7 stones forming a "C", or 8 stones forming an "O". There can be > larger, more pathological cases such as an E or butterfly shapes that can > have disparate stones counting liberties more than two times. I was afraid someone would ask that! I forgot to emphasize that I do not calculate pseudoliberties in the standard way (I use something a little more complicated to address the kinds of problems you mentioned), and that the "2" in if pseudoliberties <= 2 would most likely be a different number for someone else, but now I guess I will have to go back over my code and see if what I'm doing is actually correct. I remember thinking about this problem and spending a lot of time on it, but it was so long ago that I can't remember how it ended up working in the end, so I'll try to get back to you soon. ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
Re: [computer-go] Speed of generating random playouts
> I'm now somewhat torn. The speedup from using pseudo-liberty counts > could be huge, estimating from my profiling. On the other hand, it would > be very useful to still be able to quickly check if a group is in atari > - it looks like if atari stones would get special attention during the > random games, that could make the bot a lot stronger. > > Is there any known way to get the best of the both worlds? :-) Looking at my code I first check if the number of pseudoliberties is less than or equal to 2 (this is necessary but not sufficent for a string to be in atari given the way I compute pseudoliberties), which is very fast (it just involves a lookup because I have already computed pseudoliberties for all strings when the last move was made). If this is true I then do a slower check to see if the string in question is actually in atari. This gets the best of both worlds because most strings (ones with more than two pseudoliberties) are ruled out very quickly and only a few are looked at with the slower routine that uses real liberties to check for atari. ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
Re: [computer-go] Speed of generating random playouts
Sorry I did not have time to look at your code, but here a few quick hints:
1) Before any optimization make sure that your code works 100%
correctly. This means testing extensively and writing tests that you
can use as you start optimizing to make sure nothing breaks in the
process. You might get into big trouble if there is a bug you find
after doing lots of optimizations.
2) Learn how to profile your code. I don't work in C so unfortunately
I can't give you specific directions. But this is always the first
step in optimizing a large project. When you can see exactly where
your bottlenecks are it is 100 times easier and more efficient to
optimize. Without profiling you might find yourself spending a week on
an optimization that ends up giving you only 1% speedup.
The main optimization for me was squeezing every little bit out of
random number generation. This meant using a third party random number
generator in java (because the built in one is slow and also not
really pseudorandom anyway) and using various other tricks...
3) Think very carefully about data structures and algorithms at a high
level. I tried to simplify my board structure and my structure for
representing strings as much as possible and this also generated a lot
of speedup. As the last poster mentioned, if you are picking a random
intersection and rejecting the ones that are occupied until you have
filled the board this will take a lot longer than mainting a list of
empty intersections and only sampling from these. More specifically,
only sampling from empty intersections will take O(n) to fill the
board, while sampling with replacement and rejecting occupied
intersections will take O(nlogn) which is actually pretty bad since a
lot of time is spent deciding where to play as it is.
I hope that helps!
On Nov 12, 2007 2:45 PM, Heikki Levanto <[EMAIL PROTECTED]> wrote:
> On Mon, Nov 12, 2007 at 06:10:21PM +0100, Petr Baudis wrote:
> > Sorry, it's http://repo.or.cz/w/zzgo.git
>
> I've had a quick look at it, and have already two comments:
>
> 1) You seem to use struct {x,y} for coordinates all the way. I think using a
> single int is usually faster. I was involved with GNU Go when we made that
> change, and it did make sense. Gives some speed, but costs a bit of work, and
> some readability.
>
> 2) It looks like your montecarlo algorithm tries to pick random points and
> discards those that are not empty or legal to play in. It ought to be faster
> to make a list of legal points in advance (or at least empty ones), and pick
> from that list. This list can be maintained incrementally during the MC
> simulation.
>
>
> Still, I like your style, and may yet decide to take advantage of your
> library instead of LibEGO at least in some of my experiments.
>
> - Heikki
>
> --
> Heikki Levanto "In Murphy We Turst" heikki (at) lsd (dot) dk
>
> ___
>
> computer-go mailing list
> computer-go@computer-go.org
> http://www.computer-go.org/mailman/listinfo/computer-go/
>
___
computer-go mailing list
computer-go@computer-go.org
http://www.computer-go.org/mailman/listinfo/computer-go/
[computer-go] Video of Sylvain Gelly talk at NIPS
Hi All, I have been reading this list for a while, but I haven't really posted yet. However, I found a link to a video of Sylvain's Gelly's Mogo talk at NIPS which I think a lot of you would be interested in watching. There are also some other talks on UCT and related topics that are easy to find on the same site. There is also a talk about "Discounted UCB" which Yamato was asking about a few months ago when he found the slides to the talk. Here is the link: http://videolectures.net/otee06_gelly_umc/ ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
