Re: Re[2]: [computer-go] use for Monte Carlo on 19X19?
On Tue, 2007-11-06 at 16:30 +0100, Lars Schäfers wrote: By the way: a 9x9 CGOS server using japanese rules... I have a dream.. ;) What formal and automatable Japanese ruleset are you proposing? A computer implementation would also lend credibility. -Jeff ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
Re: [computer-go] use for Monte Carlo on 19X19?
By the way: a 9x9 CGOS server using japanese rules... I have a dream.. ;) Lars Hi Lars, I don't want to get too philosophical here and start another rules debate so I'll start by saying that I'm not that interested in rules as such. It's way more interesting to me to focus on playing strength. Japanese rules is a fairly large diversion from this in my opinion. When I designed CGOS I didn't want to get involved with the complexities of Japanese scoring because the real motivation for CGOS was to encourage the development of strong playing Go programs.I wanted it to be as easy as possible to get started in this, not just for the program developers, but also for myself.How do you score Japanese games correctly in an automated way in the face of program disputes? There was a lot of discussion about this at one point - one of them being to let gnugo score the games. But of course it involves more protocol to the server such as dead stone agreement and such.Nothing that isn't possible, but it makes things way more complicated for everybody.For a server like CGOS it's a heavy price to pay. As Nick Wedd observed, it's very difficult to get all the program authors to get the software correct for any kind of protocol.Of course if I were to do it, I would simply set up the rules and the protocol and I would not be forgiving of program error (it would be up to the programmer to get it right or risk losing games.) It's already like that on CGOS. Some programs don't do positions super ko correctly and they sometimes lose games. I get a report every month or two about this, claiming CGOS doesn't know how to handle Ko properly but in every case the complainant was wrong.I can easily imagine what it would be like with Japanese rules. I would be getting hammered with sincere pleads to check the code because they are sure it's wrong. I chased down every case of the KO bug, I never ignored the complainant just because I knew they would be wrong but I wanted to give them the satisfaction that I checked it out with an open mind (ok, I admit my mind wasn't open - I knew they were wrong but I still always did the homework to set their mind at ease.) Since you have a dream - I will tell you my dream. I wish there was a single set of standardized rules that everyone in the world honored. These rules would promote the game by being as simple as possible so that beginners would understand it.Japanese rules have almost certainly hurt the game in Western cultures. I believe this because I almost didn't discover the game due to these rules - you simply cannot understand Japanese rules without already being good at the game. With Chinese rules, you can learn the rules quickly. Having said all of that, I'm very interested in Japanese scoring from an engineering point of view. I think it would interesting challenge and a lot of fun making my own program able to handle them properly. Of course this is a requirement for a serious commercial program. I have a un-serious commercial palm program that does not know Japanese and it's a requested feature, although not heavily requested. I acknowledge that Japanese rules are popular and here to stay.I would really get interested if I had a strong program and I was in the polishing phase of program development, where you provide a fancy GUI and lots of cool features. Even then, it's a lot of work because there is not such thing as one set of Japanese rules, there are many variations. In fact it would be interesting to enumerate those variations, such as ko, komi, handicap system (should there be compensation), suicide, time-control and so on. There is surely a sensei page on this. - Don DD AnchorMan uses that in KGS mode - it will pass quite early sometimes and DD mark dead stones based on the territory statistics you are talking DD about. DD So I assume the play-outs are chinese and the move selection is the same DD as our bots except you won't move into an intersection that is owned by DD either player? DD How reliable is that?I had to be pretty conservative in AnchorMan DD about using that, it would fail to defend territory unless I made the DD threshold for ownership pretty high. DD - Don DD Lars wrote: I had build an Monte-Carlo GO-Engine (GOMonCy) wich uses the Japanese scoring system. It reached a win rate against GnuGO 3.6 level 10 of stable 50%-52%. I used territorry-statistics about the Monte-Carlo outcomes. You get a probability for every field telling you who is the owner. It works quite good, but I thougt that nearly everyone is using such statistics, isnt't it? Using a threshold to decide that a field belongs to a player you can also handle seki situations. Of course, if it is losing, the engin will break the seki situation an continue losing.. Am Montag, den 05.11.2007, 16:54 -0800 schrieb [EMAIL PROTECTED]:
Re[4]: [computer-go] use for Monte Carlo on 19X19?
Hello Jeff, as far as I know there don't exist any formal and automatable japanese ruleset. I would propose the GnuGO scoring as a referee. Perhaps it's possible to ask the two bots which stones they think are dead or in seki. If they don't agree GnuGO will decide who had won. This would perhaps be an advantage for GnuGO playing on CGOS but show me a 9x9 game where you wouldn't agree with the scoring, I think such cases are really rare. Lars Tuesday, November 6, 2007, 6:08:20 PM, you wrote: JN On Tue, 2007-11-06 at 16:30 +0100, Lars Schäfers wrote: By the way: a 9x9 CGOS server using japanese rules... I have a dream.. ;) JN What formal and automatable Japanese ruleset are you proposing? A JN computer implementation would also lend credibility. JN -Jeff JN ___ JN computer-go mailing list JN computer-go@computer-go.org JN 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] use for Monte Carlo on 19X19?
Lars, If I do anything to CGOS it would be handicap games. But I think your suggestion is sensible for Japanese scoring.GnuGo won't score perfectly every time, but I understand it is rarely incorrect. Does anyone have statistics on how well GnuGo scores professional 19x19 games? - Don Lars Schäfers wrote: Hello Jeff, as far as I know there don't exist any formal and automatable japanese ruleset. I would propose the GnuGO scoring as a referee. Perhaps it's possible to ask the two bots which stones they think are dead or in seki. If they don't agree GnuGO will decide who had won. This would perhaps be an advantage for GnuGO playing on CGOS but show me a 9x9 game where you wouldn't agree with the scoring, I think such cases are really rare. Lars Tuesday, November 6, 2007, 6:08:20 PM, you wrote: JN On Tue, 2007-11-06 at 16:30 +0100, Lars Schäfers wrote: By the way: a 9x9 CGOS server using japanese rules... I have a dream.. ;) JN What formal and automatable Japanese ruleset are you proposing? A JN computer implementation would also lend credibility. JN -Jeff JN ___ JN computer-go mailing list JN computer-go@computer-go.org JN 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] FW: Microsoft Research Lectures: Akihiro Kishimoto, Future University-Hakodate
Akihiro has kindly agreed for us to film his talk and make it available. I should be able to put it online somewhere - I will let you know when this is done. Best, David From: [EMAIL PROTECTED] [mailto:[EMAIL PROTECTED] On Behalf Of Adrian Petrescu Sent: 05 November 2007 18:14 To: [EMAIL PROTECTED]; computer-go Subject: Re: [computer-go] FW: Microsoft Research Lectures: Akihiro Kishimoto, Future University-Hakodate As a public lectures, do these things get recorded and posted online anywhere, Google Techtalk-style? This looks like a really interesting talk, but I live nowhere near where this is being held. Is there any way at all? Thanks for bringing this to our attention at any rate :) On 11/5/07, Jack [EMAIL PROTECTED] wrote: This may be of interest JL -Original Message- From: Sarah Nightingale (Interaction Recruitment PLC) [mailto:[EMAIL PROTECTED] Sent: 05 November 2007 17:25 To: Jack Lang Subject: Microsoft Research Lectures: Akihiro Kishimoto, Future University-Hakodate MICROSOFT RESEARCH LECTURE This is a PUBLIC lecture TITLE: Developing the Best Life and Death Solver in Go SPEAKER: Akihiro Kishimoto INSTITUTION: Future University-Hakodate HOST: David Stern DATE: 13 November 2007 TIME: 15:00 - 16:00 MEETING ROOM: Lecture-room small(50 seats) ADDRESS: Microsoft Research Ltd, 7 J J Thomson Avenue (Off Madingley Road), Cambridge Computer Go is one of the ultimate challenges for games research. Despite of a lot of efforts for building state of the art programs, Go is still resistant to current AI techniques, even for solving subproblems such as Life and Death, or tsume-Go. This talk presents the techniques behind TsumeGo Explorer, a high-performance tsume-Go solver. TsumeGo Explorer uses df-pn(r), a new search algorithm that improves the depth-first proof-number search algorithm. The program also contains domain-dependent enhancements. In empirical tests, TsumeGo Explorer out performs GoTools, which has been the undisputedly best tsume-Go solver for the last 15 years. --- You are currently subscribed to msrclectures as: [EMAIL PROTECTED] To unsubscribe send a blank email to [EMAIL PROTECTED] m Please see our Privacy Statement: http://research.microsoft.com/msrsupp/privacy.htm ___ 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] FW: Microsoft Research Lectures: Akihiro Kishimoto, Future University-Hakodate
Great work Dave! Look forward to seeing it. -Josh On 11/6/07, David Stern [EMAIL PROTECTED] wrote: Akihiro has kindly agreed for us to film his talk and make it available. I should be able to put it online somewhere – I will let you know when this is done. Best, David From: [EMAIL PROTECTED] [mailto:[EMAIL PROTECTED] On Behalf Of Adrian Petrescu Sent: 05 November 2007 18:14 To: [EMAIL PROTECTED]; computer-go Subject: Re: [computer-go] FW: Microsoft Research Lectures: Akihiro Kishimoto, Future University-Hakodate As a public lectures, do these things get recorded and posted online anywhere, Google Techtalk-style? This looks like a really interesting talk, but I live nowhere near where this is being held. Is there any way at all? Thanks for bringing this to our attention at any rate :) On 11/5/07, Jack [EMAIL PROTECTED] wrote: This may be of interest JL -Original Message- From: Sarah Nightingale (Interaction Recruitment PLC) [mailto:[EMAIL PROTECTED] Sent: 05 November 2007 17:25 To: Jack Lang Subject: Microsoft Research Lectures: Akihiro Kishimoto, Future University-Hakodate MICROSOFT RESEARCH LECTURE This is a PUBLIC lecture TITLE: Developing the Best Life and Death Solver in Go SPEAKER: Akihiro Kishimoto INSTITUTION: Future University-Hakodate HOST: David Stern DATE: 13 November 2007 TIME: 15:00 - 16:00 MEETING ROOM: Lecture-room small(50 seats) ADDRESS: Microsoft Research Ltd, 7 J J Thomson Avenue (Off Madingley Road), Cambridge Computer Go is one of the ultimate challenges for games research. Despite of a lot of efforts for building state of the art programs, Go is still resistant to current AI techniques, even for solving subproblems such as Life and Death, or tsume-Go. This talk presents the techniques behind TsumeGo Explorer, a high-performance tsume-Go solver. TsumeGo Explorer uses df-pn(r), a new search algorithm that improves the depth-first proof-number search algorithm. The program also contains domain-dependent enhancements. In empirical tests, TsumeGo Explorer out performs GoTools, which has been the undisputedly best tsume-Go solver for the last 15 years. --- You are currently subscribed to msrclectures as: [EMAIL PROTECTED] To unsubscribe send a blank email to [EMAIL PROTECTED] m Please see our Privacy Statement: http://research.microsoft.com/msrsupp/privacy.htm ___ 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] use for Monte Carlo on 19X19?
Don Dailey wrote: Lars, If I do anything to CGOS it would be handicap games. But I think your suggestion is sensible for Japanese scoring.GnuGo won't score perfectly every time, but I understand it is rarely incorrect. Does anyone have statistics on how well GnuGo scores professional 19x19 games? That depends on how difficult you make the problem. I have used Dave Dyer's test set of 623 scored professional 19x19 games, see http://www.andromeda.com/people/ddyer/go/scoring-games.html for information. As can be seen in the example on that page, those game records generally leave out all dame moves and even some moves required to finalize territories when it's clear how many points will be obtained there. Worse still, final endgame kos are frequently left out since it's assumed to be obvious who will win them. With this in mind, the results for GNU Go 3.7.11 are 534 (85.7%) correctly scored, 79 (12.7%) off by one point, 5 off by 2 points, 2 off by 3 points, and 1 each off by 12, 34, and 38 points. But mind you, GNU Go is trained on those games. It would certainly do worse on unseen games of a similar difficulty. On the other hand, if the game records are complete up to and including dame filling, I would expect the error rate to be less than 1%, possibly much better. /Gunnar ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
Re: [computer-go] use for Monte Carlo on 19X19?
On Tue, 2007-11-06 at 16:55 -0500, Don Dailey wrote: Hi Jeff, Yes, I agree with your points.Well behaved on CGOS means that your bot will resign as soon as it knows it's losing. I think when a bot should resign is a matter of personal preference. I myself prefer to see games played out if it's somewhat close or very near the end. If there's a handful of moves left what's the point of resigning? But against humans it should technically be the same, but isn't.When playing against humans a bot needs to be able to mark dead groups. I have the same feelings whether it's a bot vs bot game or bot vs human. As for marking dead stones, obviously a bot needs to be able to against humans, and I never suggested otherwise. My only point is that you don't need territory scoring rules for this. -Jeff ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
Re: [computer-go] use for Monte Carlo on 19X19?
On Nov 6, 2007 4:34 PM, Don Dailey [EMAIL PROTECTED] wrote: Territory scoring doesn't make the game end any sooner, it just penalizes you for not doing so. Right. In close games, the decision to pass is non-trivial. If protecting against an invasion causes a loss, then the invasion must be left open. This type of behavior is human-like. The only real exception is that weak humans like me don't count perfectly and exhibit this behavior in more cases than they should. If I'm ahead 40 points, I protect everything. But I refrained for 2 reasons: 1. It makes everything more confusing and complicated. 2. There is a better way. Actually, I agree with you that the better way is the better way for the community as a whole. Similar to an occasional slow/fast tournament on KGS, I think some experimentation with territory scoring has some benefit. This style of behavior is pleasing to people, and I think some testing of it could be helpful. Many people prefer to end games the human lost gracefully rather than be forced to resign through long endgame. I think having a way to generate a lot of games to test this style of behavior is helpful. I really care little about the rules, except that it provides a mechanism to encourage the human-like behavior that I want my bot to exhibit. I mostly consider this discussion to be theoretical. I doubt anyone would implement this and put up a temporary server to play around with this behavior. All I'm really trying to say is that if someone did do it, I'd be happy to participate. My ultimate goals are slightly different than create the strongest bot. I aim to make a bot that's fun to play and to add features to. Being the strongest would be a bonus ;) ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
Re: [computer-go] use for Monte Carlo on 19X19?
Hi Jeff, Yes, I agree with your points.Well behaved on CGOS means that your bot will resign as soon as it knows it's losing. But against humans it should technically be the same, but isn't.When playing against humans a bot needs to be able to mark dead groups. In my opinion time control should be Fischer clock - so much time for the whole game plus some number of seconds per move. I like small increments and large main times - but it's a matter of taste and as you say, it's up to the player how quickly he plays no matter what the time control is.With Fischer time control you can express time controls very flexibly. Increment of zero is like sudden death. - Don Jeff Nowakowski wrote: I apologize in advance to list members that are sick of this topic, but if people keep on bringing up these fallacious arguments, I'm going to keep on responding to them. On Tue, 2007-11-06 at 16:09 -0500, Jason House wrote: Having run a dumb bot on KGS in the past, I became sensitive to user needs... 1. A bot that stubbornly plays 50 useless moves in endgame is highly annoying... especially with sudden death time limits. Resigning a lost game helps, but so would territory scoring with proper dead stone marking. You don't need territory scoring rules for this. I run a copy of MoGo on KGS. It uses Chinese rules and does a good job of passing once the opponent has passed. It also marks dead stones correctly. If you put your program on KGS then this is pretty much required if you want repeat players and want to avoid people escaping from games. 2. Byo yomi or canadian time are very popular, but a computer can't take full advantage of byo yomi or canadian time in endgame without frustrating the opponent. When a game is nearly over, the bot should not ponder for 19 out of 20 seconds of byo yomi to play an obvious move. Again, this has nothing to do with the rules, and I'll again use MoGo as an example. It plays a very fast endgame. How you code your bot to use time is up to you and not dependent on the rules. Your arguments are for well behaved bots on KGS against human players, which is not the point at all of CGOS. I encourage people to make their bots well behaved for KGS tournaments and for play against KGS humans, but that's up to individual authors and is not dependent on the ruleset. -Jeff ___ 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] use for Monte Carlo on 19X19?
Ok, this is my last post on this topic for a while, promise. On Tue, 2007-11-06 at 17:21 -0500, Jason House wrote: I think having a way to generate a lot of games to test this style of behavior is helpful. I really care little about the rules, except that it provides a mechanism to encourage the human-like behavior that I want my bot to exhibit. This behavior is not dependent on the rules! Even if your monte carlo bot uses territory scoring, it will still play useless moves if it is losing. If you want more human-like behavior, you'll still have to make your program know when to pass under either ruleset. I see no benefit in putting up a territory-based CGOS server that you couldn't have gotten from local experimentation with GnuGo. -Jeff ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
Re: [computer-go] use for Monte Carlo on 19X19?
Hi Jason, A few comments. Area scoring is what CGOS does, Territory scoring is Japanese. Territory scoring doesn't make the game end any sooner, it just penalizes you for not doing so. I like the concept of not playing the game out to the bitter end but you can't stop players from doing this if they want to. I have considered implementing something like this in CGOS so that bots could stop playing early as an option. Would require a negotiation phase to make sure both sides agree on dead stones and so on. But I refrained for 2 reasons: 1. It makes everything more confusing and complicated. 2. There is a better way. In my opinion, since it's clear you can't force anyone to pass unless they want to, then there is no good solution based on agreement protocols that require the cooperation of both bots. However, since any solution is optional, there is a solution that does not require the cooperation of the other bot. I'll call it the resign protocol. If you are interested in playing nice and not dragging out the game - then you can resign if you are losing. If you are not losing there is nothing you can do to shorten the game if the opponent is not willing. In other words, if he won't resign, he probably won't pass either. It's far easier to resign than work out a pass/pass/negotiate phase. So to me this is really the most elegant solution. - Don Jason House wrote: Personally, I'm ignorant on the subtle nature of Japanese rules. I look it as territory scoring instead of area scoring. Area scoring has the nice side effect that people can and should stop playing a game once all territory is decided. Having run a dumb bot on KGS in the past, I became sensitive to user needs... 1. A bot that stubbornly plays 50 useless moves in endgame is highly annoying... especially with sudden death time limits. Resigning a lost game helps, but so would territory scoring with proper dead stone marking. 2. Byo yomi or canadian time are very popular, but a computer can't take full advantage of byo yomi or canadian time in endgame without frustrating the opponent. When a game is nearly over, the bot should not ponder for 19 out of 20 seconds of byo yomi to play an obvious move. My usual method to solve #1 is to put up an approximate and hope I don't piss off too many people while testing. #2 is usually pretty easy to solve by adding a max time per move that decreases as the game length gets longer. On Nov 6, 2007 3:45 PM, Jeff Nowakowski [EMAIL PROTECTED] mailto:[EMAIL PROTECTED] wrote: On Tue, 2007-11-06 at 18:27 +0100, Lars Schäfers wrote: Hello Jeff, as far as I know there don't exist any formal and automatable japanese ruleset. I would propose the GnuGO scoring as a referee. I don't see what is gained by converting CGOS to Japanese rules. You lose the ability for programs to play out disputes and instead depend on a 6k computer program (typical KGS rank for GnuGO) to resolve disputes. It's also a needless complication for bot authors that aren't concerned about Japanese rules. If you want to implement Japanese rules for your program, great. This discussion has been had many times on this list. What's the new compelling argument for having it again? -Jeff ___ computer-go mailing list computer-go@computer-go.org mailto:computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/ ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/ ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
[computer-go] Re: use for Monte Carlo on 19X19?
the idea is: identify at least one stone from every unconditionally living and every unconditionally dead group on the board, and report them as dead or alive. It can be done very fast, but the problem is that in a typical endgame board under Japanese rules, the number of unconditionally alive stones is zero. ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
[computer-go] Re: use for Monte Carlo on 19X19?
the idea is: identify at least one stone from every unconditionally living and every unconditionally dead group on the board, and report them as dead or alive. It can be done very fast, but the problem is that in a typical endgame board under Japanese rules, the number of unconditionally alive stones is zero. ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
Re: [computer-go] use for Monte Carlo on 19X19?
Lars Schäfers wrote: I would propose the GnuGO scoring as a referee. Perhaps it's possible to ask the two bots which stones they think are dead or in seki. If they don't agree GnuGO will decide who had won. This would perhaps be an advantage for GnuGO playing on CGOS but show me a 9x9 game where you wouldn't agree with the scoring, I think such cases are really rare. I am using GnuGo scoring in my tournaments. But GnuGo 3.7.10 mostly doesn´t score seki correctly, has this been revised for v3.7.11 ...?! So the reliability of GnuGo´s scoring depends on the programs playing stile because some programs tend to look for living in seki more often than others. A rough estimation for my 9x9 tournament: between 1% and 5% of the 9x9 games are not scored correctly by GnuGo 3.7.10 but the side to win is correct in 99,9% of the games. Stefan ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
[computer-go] Re: use for Monte Carlo on 19X19?
At 05:22 PM 11/6/2007, Ray Tayek wrote: At 03:50 PM 11/6/2007, you wrote: ... in a typical endgame board under Japanese rules, the number of unconditionally alive stones is zero. maybe for pro games. for amatuer 1-kyu to 10-kyu games, i suspect that after about 1/2 of the moves in the entire game have been made, enough groups are a few stones away from being benson alive that it would be worthwhile to find these. The whole problem is to determine what ought to be considered dead. Finding a group that needs a few more stones to be completely alive doesn't help at all, because you have to do a full board search to find out if those moves could actually be made. A strategy that starts by anchoring the determination in unconditionally alive groups starts with nothing. ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
[computer-go] Re: use for Monte Carlo on 19X19?
At 05:22 PM 11/6/2007, Ray Tayek wrote: At 03:50 PM 11/6/2007, you wrote: ... in a typical endgame board under Japanese rules, the number of unconditionally alive stones is zero. maybe for pro games. for amatuer 1-kyu to 10-kyu games, i suspect that after about 1/2 of the moves in the entire game have been made, enough groups are a few stones away from being benson alive that it would be worthwhile to find these. The whole problem is to determine what ought to be considered dead. Finding a group that needs a few more stones to be completely alive doesn't help at all, because you have to do a full board search to find out if those moves could actually be made. A strategy that starts by anchoring the determination in unconditionally alive groups starts with nothing. ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
[computer-go] [OT] All-integer scalable distribution algorithm.
Folks... First, let me say how much pleasure my reading of this list has given me. I love that folks are out there cranking on this problem. Truly, it's one of the great problems. I have a rather strange request. I am a statistical idiot, in both senses of 'statistical'. After scrolling through a half-dozen stat tutorials online, I find myself completely unable to grasp how I'd get the effect I want even if I wanted to use floats, which I don't. As you will soon be aware, I don't even have the language to figure out how to describe my problem. Seeing as how there are so many MC algorithm workers on the list, I thought I'd turn to you for some guidance. The essence of my idea is that I want a psuedo-random algorithm which takes as a parameter a 'degree-of-randomness' value. Something along these lines: int choose( int range, int degree-of-randomness) Returns an integer in [0-range] distributed depending on the value of degree-of-randomness. At degree-of-randomness 100, I want the distribution to be uniform. At degree-of-randomness 0, I want the distribution to be -- I don't even know what to call this -- half-of-a-normal-distribution with the steepness proportionately related to degree-of-randomness. Am I making *any* sense? If so, you may need some sort of psychiatric help, or alternatively, you could do me the favor of explaining how to ask for what I want or even how to actually get it. :) Cheers, and thanks, Hill ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
[computer-go] Re: randomness
Am I making *any* sense? If so, you may need some sort of psychiatric help, or alternatively, you could do me the favor of explaining how to ask for what I want or even how to actually get it. :) Most computer applications use uniform randomness, but it sounds like what you want is normally distributed randomness, with mean = 50 and variance to be specified. Changing the variance changes the slope of the curve and in effect, the degree to which is is bunched near the mean. Given that computer random numbers are uniform, you need to transform them into normally distributed numbers. Try this: http://www.taygeta.com/random/gaussian.html I didn't fully parse it, but it looks like a reasonable source. ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
Re: [computer-go] [OT] All-integer scalable distribution algorithm.
It sounds like you're frustrated, so here's a few lines of C code
that'll do about what you describe. Note that the use of large values
for the standard deviation will make the code go very slow from
repetitive looping. The divide by 10 is to make it not be too slow with
a degree of randomness of 100. randn returns a normally distributed
random number.
float standard_deviation = degree_of_randomness/10;
double r;
do{
r = abs(randn(seed))*standard_deviation;
}while (r = (range+1))
return floor(r);
1. Get a random, normally distributed, variable
(using your favorite API to do that)
2. If it's negative, make it positive
Use your favorite function for generating a normally distributed random
variable. If it's negative, make it positive.
Multiply it by some
On Tue, 2007-11-06 at 22:03 -0500, Mike Hill wrote:
Folks...
First, let me say how much pleasure my reading of this list has given
me. I love that folks are out there cranking on this problem. Truly,
it's one of the great problems.
I have a rather strange request. I am a statistical idiot, in both
senses of 'statistical'. After scrolling through a half-dozen stat
tutorials online, I find myself completely unable to grasp how I'd get
the effect I want even if I wanted to use floats, which I don't. As you
will soon be aware, I don't even have the language to figure out how to
describe my problem. Seeing as how there are so many MC algorithm
workers on the list, I thought I'd turn to you for some guidance.
The essence of my idea is that I want a psuedo-random algorithm which
takes as a parameter a 'degree-of-randomness' value. Something along
these lines:
int choose( int range, int degree-of-randomness)
Returns an integer in [0-range] distributed depending on the value of
degree-of-randomness. At degree-of-randomness 100, I want the
distribution to be uniform. At degree-of-randomness 0, I want the
distribution to be -- I don't even know what to call this --
half-of-a-normal-distribution with the steepness proportionately
related to degree-of-randomness.
Am I making *any* sense? If so, you may need some sort of psychiatric
help, or alternatively, you could do me the favor of explaining how to
ask for what I want or even how to actually get it. :)
Cheers, and thanks,
Hill
___
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] [OT] All-integer scalable distribution algorithm.
On Tue, 6 Nov 2007, Mike Hill wrote: int choose( int range, int degree-of-randomness) Returns an integer in [0-range] distributed depending on the value of degree-of-randomness. At degree-of-randomness 100, I want the distribution to be uniform. At degree-of-randomness 0, I want the distribution to be -- I don't even know what to call this -- half-of-a-normal-distribution with the steepness proportionately related to degree-of-randomness. This seems not so much the degree of randomness as the skew. Because a normal distribution has an infinite continuous range, I don't think that's what you want. You say half a normal; is something like a geometric distribution close enough? You might check it out, at least it's discrete. But when I have a problem like this, I tend to use what I think of as the weight, bisect algorithm. See if this solves your problem. Basically, skew can go from 0 to infinity, and the higher it is, the steeper the skew and the less likely you are to choose 0, the more likely you are to choose size-1. [begin python code] from bisect import bisect from random import random def draw(weights): sigma = 0.0 ps = [] for p in weights: sigma += p ps.append(sigma) return (ps,random()*sigma) def choose(size, skew): ''' skew=0 gives uniform distribution skew=1 gives linear, skew = 2 quadratic, and so on. ''' weights = [i**skew for i in range(size)] return draw(weights) [end python code] HTH, Tom ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
Re: [computer-go] [OT] All-integer scalable distribution algorithm.
At 07:03 PM 11/6/2007, you wrote: ... Returns an integer in [0-range] distributed depending on the value of degree-of-randomness. At degree-of-randomness 100, I want the distribution to be uniform. At degree-of-randomness 0, I want the distribution to be -- I don't even know what to call this -- half-of-a-normal-distribution with the steepness proportionately related to degree-of-randomness. maybe a normal (gaussian) with the standard deviation (sigma) proportional to the degree of randomness. but clip the tails. see the graphs of the normal density function: http://en.wikipedia.org/wiki/Normal_distribution. a larger variance will get you a flatter curve that will approach a uniform distribution. --- vice-chair http://ocjug.org/ ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
