Re: [computer-go] Random weighted patterns
This code should work with r -= weights[i++] in the loop body, and comes down
to a linear search through
cumulative sum of the weights. If the weights will be static for a number of
selections, you can store the
cumulative weights in an array and use binary search for selecting the move.
So setting up the table is O(n),
but selecting moves based on those weights is O(log n).
If the weights are constantly being updated, there's a tradeoff between Peter's
code and the tree-based approach:
Peter's code is O(1) for updating weights and O(n) for selections, while the
tree-based approach is O(log n) for updates
and selections.
[You can get practically quicker selection using Peter's code if you keep the
weights sorted in decreasing order, but then updates
become O(n) worst-case (probably O(1) amortized, though).]
Steve
On Thu, 16 Jul 2009, Don Dailey wrote:
In the loop i is always zero. I think your code is wrong.
You probably meant to loop over all the weights (or I should say on average
half the weights), and this code is slow if there are a lot of weights.
2009/7/16 Peter Drake dr...@lclark.edu
I must be missing something. Isn't the obvious trick:
int r = random(sum of weights);
int i = 0;
while (r weights[i]) {
r -= weights[i];
}
return i;
This way, you only have to generate one random number.
Peter Drake
http://www.lclark.edu/~drake/
On Jul 15, 2009, at 8:55 PM, Zach Wegner wrote:
On Wed, Jul 15, 2009 at 10:37 PM, David Fotlandfotl...@smart-games.com
wrote:
So many complex ideas :) Why not just multiply the weight of each
pattern
by a random number and pick the biggest result?
David
That involves generating N random numbers and then doing N-1
comparisons. The n-ary tree has only 1 random number and log N
comparisons, but has to be
incrementally updated (log N adds).
Also, I don't think the distribution is the same. Imagine two moves a
and b, with weights 2 and 1. The probabilities should be a=2/3 b=1/3,
but if you select two random numbers in a finite range, there's only a
1/4 chance that the second number is more than twice the first, which
is needed for b to be selected. I could be wrong here though.
Zach
___
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/
--
Steve Kroon | Computer Science Division, Stellenbosch University
(084) 458 8062 (Cell) | (086) 655 4386 (Fax) | kroonrs (Skype)
http://www.cs.sun.ac.za/~kroon | kr...@sun.ac.za___
computer-go mailing list
computer-go@computer-go.org
http://www.computer-go.org/mailman/listinfo/computer-go/
[computer-go] Random weighted patterns
If you want to take many samples from a fixed, or infrequently changing, distribution, you can do it in O(1) time per sample, with O(n) initial setup costs. This is quite clever and goes by the name of alias method. See http://cg.scs.carleton.ca/~luc/rnbookindex.html, page 107-111 For weighted patterns, the row sum method by Rémi is probably hard to beat. It was discussed here a while ago. Martin ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
Re: [computer-go] gtp which version to implement?
Thanks all for the input. --- On Wed, 7/15/09, Don Dailey dailey@gmail.com wrote: From: Don Dailey dailey@gmail.com Subject: Re: [computer-go] gtp which version to implement? To: computer-go computer-go@computer-go.org Date: Wednesday, July 15, 2009, 9:39 AM On Wed, Jul 15, 2009 at 9:41 AM, Carter Cheng carter_ch...@yahoo.com wrote: Where can I find information on these bridging protocols or are libraries provided for this (to the 9x9 19x19 servers)? The CGOS protocol is pretty easy to decode from the cgos client script which is written in TCL. Even if you don't know tcl you can learn the protocol easily from the script. However, there is no need to know the CGOS protocol if your engine speaks GTP. GTP is designed to be a universal protocol for GO engines - if your engine knows GTP it should be able to use all kinds of tool including GOGUI, a nice user interface for GO programs. The cgos client program speaks to the server in it's language and to your program using GTP. See how simple life can be? The CGOS protocol is about to change just slightly as I will be soon upgrading the server, but an updated client will be provided so that will require no change on your part. (And the old CGOS prototol will still work but with some restrictions.) - Don --- On Wed, 7/15/09, Hellwig Geisse hellwig.gei...@mni.fh-giessen.de wrote: From: Hellwig Geisse hellwig.gei...@mni.fh-giessen.de Subject: Re: [computer-go] gtp which version to implement? To: computer-go computer-go@computer-go.org Date: Wednesday, July 15, 2009, 2:44 AM On Wed, 2009-07-15 at 11:24 +0200, Urban Hafner wrote: Carter Cheng wrote: Thanks everyone for the help thus far. I have been looking at the GTP protocol page and I am curious which version of the protocol I should try to implement if I want to communicate with the servers. Should I be looking at the GTP 2.0 draft version? You should implement (part of) the draft. It's widely used nowadays. I'm not sure if there's any server out there that uses the old version. Just to be clear on this point: GTP is not a server protocol, but a protocol between a controller and an engine. If you want the engine to connect to a server, there is still a bridge needed, which communicates with the engine through GTP and with the server through whatever protocol the server is speaking. Hellwig ___ 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/ -Inline Attachment Follows- ___ 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 weighted patterns
Thanks! I had never seen the alias method before and it is quite ingenious! - George On Thu, Jul 16, 2009 at 3:04 AM, Martin Muellermmuel...@cs.ualberta.ca wrote: If you want to take many samples from a fixed, or infrequently changing, distribution, you can do it in O(1) time per sample, with O(n) initial setup costs. This is quite clever and goes by the name of alias method. See http://cg.scs.carleton.ca/~luc/rnbookindex.html, page 107-111 For weighted patterns, the row sum method by Rémi is probably hard to beat. It was discussed here a while ago. Martin ___ 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] Slightly OT: Sound in CGoban
I've recently been getting an odd distorted buzzing with every sound played by CGoban3, the KGS client. This doesn't happen with other applications, so I don't think it's a hardware or driver problem. Has anyone else encountered this? Peter Drake http://www.lclark.edu/~drake/ ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
Re: [computer-go] Slightly OT: Sound in CGoban
Le 16/07/2009 à 22:28, Peter Drake a écrit : I've recently been getting an odd distorted buzzing with every sound played by CGoban3, the KGS client. This doesn't happen with other applications, so I don't think it's a hardware or driver problem. Has anyone else encountered this? Peter Drake http://www.lclark.edu/~drake/ you should mailto:ad...@gokgs.com to report this. btw, if you can advocate fo a public bug tracker it would be a great improvement for the community :) Alain. ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
[computer-go] Dead stones at end of game
I was looking at this game that Orego played against a human on KGS recently: Orego-Zanarkand.sgf Description: Binary data I note that Orego'sdeadstonesaremarkedasdead,butZanarkand'sarenot.DoesKgsGtpdefertothehumanwhentherearedisputesaboutdeadstones? Is that the most likely explanation?(Whatifthereisadisputebetweenprograms?)Oregolosesevenifallofthedeadstonesareremoved,butI'mabitdismayedthatOregopassed.(Zanarkandpassedfirst.)IbelieveOregoreasoned,"IfIpass,thegameends,andifallstonesontheboardarealive,Iwin!"I'llhavetolookintothis... Peter Drakehttp://www.lclark.edu/~drake/ ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
Re: [computer-go] Dead stones at end of game
IIRC, the user can do whatever they want in a free game. Only rated games require the bot to agree with the scoring Sent from my iPhone On Jul 16, 2009, at 6:18 PM, Peter Drake dr...@lclark.edu wrote: I was looking at this game that Orego played against a human on KGS recently: Orego-Zanarkand.sgf I note that Orego's dead stones are marked as dead, but Zanarkand's are not. Does KgsGtp defer to the human when there are disputes about dead stones? Is that the most likely explanation? (What if there is a dispute between programs?) Orego loses even if all of the dead stones are removed, but I'm a bit dismayed that Orego passed. (Zanarkand passed first.) I believe Orego reasoned, If I pass, the game ends, and if all stones on the board are alive, I win! I'll have to look into this... Peter Drake http://www.lclark.edu/~drake/ ___ 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] Slightly OT: Sound in CGoban
There are some relevant discussions in the computer go forum at http://www.godiscussions.com -Original Message- From: Alain Baeckeroot alain.baecker...@laposte.net To: computer-go computer-go@computer-go.org Sent: Thu, Jul 16, 2009 5:08 pm Subject: Re: [computer-go] Slightly OT: Sound in CGoban Le 16/07/2009 à 22:28, Peter Drake a écrit : I've recently been getting an odd distorted buzzing with every sound played by CGoban3, the KGS client. This doesn't happen with other applications, so I don't think it's a hardware or driver problem. Has anyone else encountered this? Peter Drake http://www.lclark.edu/~drake/ you should mailto:ad...@gokgs.com to report this. tw, if you can advocate fo a public bug tracker it would be a great mprovement for the community :) Alain. __ omputer-go mailing list omputer...@computer-go.org ttp://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] Dead stones at end of game
On KGS, either player may mark stones as dead. If you disagree, you toggle the state of the stones. The game ends when both players click done -- you should do this only when you are entirely satisfied with the score. I don't know how the human interface maps to the API seen by the program. Terry McIntyre terrymcint...@yahoo.com “We hang the petty thieves and appoint the great ones to public office.” -- Aesop From: Jason House jason.james.ho...@gmail.com To: computer-go computer-go@computer-go.org Sent: Thursday, July 16, 2009 3:27:28 PM Subject: Re: [computer-go] Dead stones at end of game IIRC, the user can do whatever they want in a free game. Only rated games require the bot to agree with the scoring Sent from my iPhone On Jul 16, 2009, at 6:18 PM, Peter Drake dr...@lclark.edu wrote: I was looking at this game that Orego played against a human on KGS recently: Orego-Zanarkand.sgf I note that Orego's dead stones are marked as dead, but Zanarkand's are not. Does KgsGtp defer to the human when there are disputes about dead stones? Is that the most likely explanation? (What if there is a dispute between programs?) Orego loses even if all of the dead stones are removed, but I'm a bit dismayed that Orego passed. (Zanarkand passed first.) I believe Orego reasoned, If I pass, the game ends, and if all stones on the board are alive, I win! I'll have to look into this... Peter Drake http://www.lclark.edu/~drake/ ___ 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/
