Re: [computer-go] Re: Big board. Temperature
Physics temperature is a macroscopic description (global) of the underlying (un)-stability, so it comes to mind very quickly :) Unfortunately the term temperature used in Computer Game theory is misleading for physicists. CGT-temperature = value of the best move in go, this has very little relation do with a global description of unstability. (I propose to ban the term temperature from CGT, and replace it by value, unless someone can explain the link with temperature in physics, and shows some identical properties ;-) Le jeudi 1 mars 2007 08:27, Darren Cook a écrit : Just trying to understand what you guys are talking about... I realize it is a rather small picture, but do the terminal positions of 19x19 games between very strong players show more fractal qualities (or some other physics thing) than between, say, 15 kyu amateurs? Yes. Pro games are near a limit of (un)-stability. It seems one see the kind of physics he knows better (D.Doshay sees magnetic transition, D.Hillis percolation and spin glass, i see fluid dynamics and solidification ...) The common denominator is a critical state, with sudden change in properties, from a nearly homogeneous state. - Beginners are under critical - Pro near critical - (Quasi) Random players above critical. Or, from another angle, how do you imagine a very large board would look in a game between two very strong players? And would it be any different for 15 kyu players? For sure. On 19x19 one can estimate players strenght by seeing a position. 15 kyu is ugly ;) (overconcentrated, hyperstatic, not mixed, very little Work of stones/groups, ...) Alain ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
Re: [computer-go] Re: Big board. Temperature
alain Baeckeroot wrote: (I propose to ban the term temperature from CGT, and replace it by value, unless someone can explain the link with temperature in physics, and shows some identical properties ;-) While I bet most of us dislike the term, it seems to express an inherent concept. Renaming temperature to value will lose that. I know that when I first came across the term temperature, I had to look up what it meant and then learned something. If it was value, I never would have. ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
[computer-go] MC - Estimating a moves true probability of winning
Hello Jason I think what you are trying to do can be done more easily. A. You have a Bernoulli random variable whose result is 0 or 1 following an unknown probability p. (Excuse me for explaining obvious things, this is for anyone who reads it.) You want to estimate p from a random sample. The estimator of p computed from the sample is usually called p-hat (a ^ char on a p) Of course, the same board position produces 0 or 1 with the same probability p. B. You cont the number of wins. Therefore, you have a random variable which follows a BINOMIAL (n, p) being n the sample size. C. To compare if a move is better than another, you have to compare _confidence intervals_. I.e. the interval in which p (the unknown probability) lies computed from your observed p-hat, n and a desired confidence level, say 95%. These intervals can be computed with methods you can find searching for Confidence Interval for a Binomial Proportion. The most used are Wilson and Agresti-Coull intervals. These intervals include continuity correction as you mention in your post. Other ways of comparing proportions are: The difference between proportions, the relative risk and the odds ratio to name a few. My Bible for this is a book called Categorical Data Analysis from Alan Agresti published by Wiley Sons. To use these results, you must make some assumption about the underlying distribution of a move's probability of winning. That's the good news. You don't. There is no need to understand what complex mechanism produces p. Only that: same position == same p. *Do not* expect a sound statistical analysis to tell you the best move, unless it is very obvious, n is immense or your confidence level is extremely low. But, if you are lucky, it will tell you what moves are clearly bad and can be safely (= with a given confidence) pruned out. Computing distributions is not as hard as it may seem because you can interpolate from a LUT with reasonable precision. Anyway, even if I have the statistical skills to do that, I personally am not doing things that well because I believe computing time is more productive doing more simulations than quality control. I may be wrong. Jacques. ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
Re: [computer-go] Re: Big board. Temperature
it is a rather small picture, but do the terminal positions of 19x19 games between very strong players show more fractal qualities (or some other physics thing) than between, say, 15 kyu amateurs? Yes. Pro games are near a limit of (un)-stability. ... - Beginners are under critical - Pro near critical - (Quasi) Random players above critical. It'd be an interesting experiment to see if you can train a neural network to be shown a large set of final positions (*) from each of A: pro, B: 10-15kyu, and C: random player, and be able to categorize them correctly. My guess would've been that A and B look very similar, but unfortunately I don't have the time to investigate currently. Darren *: To avoid a bias due to pros recognizing and resigning lost games earlier, it'd have to be games that were actually scored and the size of the win was no more than around 4 pts. ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
Re: [computer-go] Re: Big board. Temperature
Le jeudi 1 mars 2007 11:51, Jason House a écrit : alain Baeckeroot wrote: (I propose to ban the term temperature from CGT, and replace it by value, unless someone can explain the link with temperature in physics, and shows some identical properties ;-) While I bet most of us dislike the term, it seems to express an inherent concept. OK. Do you have some good link which clearly explain CGT temperature ? Nowhere i find something explaining why it is a good name, in the sense it is alike what all physicists call temperature (= more or less global average of underlying agitation*density). Renaming temperature to value will lose that. I know that when I first came across the term temperature, I had to look up what it meant and then learned something. If it was value, I never would have. I read some papers about thermography in go, and in this papers it was much more clear if i replace temperature with value. Some clever temperature stuff sounds trivial if you replace it by the word value. Like saying winning strategy = play the highest temperature point. Also except in small yose, it is hard to have a thermometer, about as hard as a valuemeter ;-) I agree that using value could also be misleading, but it seems much better name than temperature. maybe cgtemperate, or cvalue ? Cheers Alain ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
Re: [computer-go] Re: Big board. Temperature
*: To avoid a bias due to pros recognizing and resigning lost games earlier, it'd have to be games that were actually scored and the size of the win was no more than around 4 pts. i don't think that i've ever seen a 15kyu game that was that close. s. Finding fabulous fares is fun. Let Yahoo! FareChase search your favorite travel sites to find flight and hotel bargains. http://farechase.yahoo.com/promo-generic-14795097 ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
Re: [computer-go] Re: Big board. Temperature
In message [EMAIL PROTECTED], alain Baeckeroot [EMAIL PROTECTED] writes Physics temperature is a macroscopic description (global) of the underlying (un)-stability, so it comes to mind very quickly :) Unfortunately the term temperature used in Computer Game theory is misleading for physicists. CGT-temperature = value of the best move in go, this has very little relation do with a global description of unstability. (I propose to ban the term temperature from CGT, and replace it by value, unless someone can explain the link with temperature in physics, and shows some identical properties ;-) This would be confusing. A position in CGT has a value and a temperature. If you really want to use some other word for temperature, don't choose a word that already has a different meaning in the same context. By the way - I thought CGT stood for Combinatorial Game Theory. Nick -- Nick Wedd[EMAIL PROTECTED] ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
Re: [computer-go] Re: Big board. Temperature
-BEGIN PGP SIGNED MESSAGE- Hash: SHA1 steve uurtamo wrote: *: To avoid a bias due to pros recognizing and resigning lost games earlier, it'd have to be games that were actually scored and the size of the win was no more than around 4 pts. i don't think that i've ever seen a 15kyu game that was that close. s. I play them all the time. Obviously you can find SOME, even if they are rare ; ) -BEGIN PGP SIGNATURE- Version: GnuPG v1.4.6 (GNU/Linux) iD8DBQFF5tOq6THm0ATXcbwRAuMyAJ9MNmSZ9Bngf27nDFCInIe0i1IH1ACgqrnY 2Di7z9wnFH8SpaIaEypRB/U= =rnBI -END PGP SIGNATURE- ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
Re: [computer-go] Re: Big board. Temperature
Nowhere i find something explaining why it is a good name, in the sense it is alike what all physicists call temperature (= more or less global average of underlying agitation*density). you'll probably be happier just noting that it's an appropriation of the word 'temperature' in use in a different field in a different context. if physicists had invented CGT, they might have used a different word, but they didn't, because they were busy ... doing physics. s. Now that's room service! Choose from over 150,000 hotels in 45,000 destinations on Yahoo! Travel to find your fit. http://farechase.yahoo.com/promo-generic-14795097 ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
Re: [computer-go] Re: Big board. Temperature
Le jeudi 1 mars 2007 12:36, Nick Wedd a écrit : [EMAIL PROTECTED] writes (I propose to ban the term temperature from CGT, and replace it by value, unless someone can explain the link with temperature in physics, and shows some identical properties ;-) This would be confusing. A position in CGT has a value and a temperature. If you really want to use some other word for temperature, don't choose a word that already has a different meaning in the same context. Ah, this shows how much i misunderstood what i have read on the topic :-( By the way - I thought CGT stood for Combinatorial Game Theory. Yes, it was big brain lag. Alain ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
Re: [computer-go] Re: Big board
I think it would make the most sense to make the measurements at the stage of the game where a human expert would find it easiest to distinguish them by looking at the board (After the first 30 moves?) Waiting till the end probably isn't ideal, although it was a perfectly good place to start. There might be some other physics thing but fractal dimension is out for 19x19. If I want to measure the fractal dimension of a 512x512 board, I make a measurement, reduce the x and y dimensions by a factor of 2, and repeat until done. Then I try to fit a curve to the 8 or so resulting points: not great, but doable. If I start with 19x19, I wind up trying to fit a curve to a couple of points: garbage. Or maybe there's some clever way to make a 19x19 game effectively bigger by looking at the sequence of moves and measure the fractal dimension of that. Dave Hillis -Original Message- From: [EMAIL PROTECTED] To: computer-go@computer-go.org Sent: Thu, 1 Mar 2007 3:27 AM Subject: Re: [computer-go] Re: Big board Chris Fant opened a door by demonstrating how easy it is to generate a decent sized image from a go game using fast playout games. ... ... But there's not a lot to be done with a 19x19 grid. ... And I agree with you that the middle image is getting close to a proper fractal but not yet there. Just trying to understand what you guys are talking about... I realize it is a rather small picture, but do the terminal positions of 19x19 games between very strong players show more fractal qualities (or some other physics thing) than between, say, 15 kyu amateurs? Or, from another angle, how do you imagine a very large board would look in a game between two very strong players? And would it be any different for 15 kyu players? Darren ___ 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] GTPv3
Hi, There are some issues that are not so well defined in GTP v2. Maybe GTP v3 should be released to avoid too much legacy later? 1. The most important thing is controller - engine architecture. There are situations that engine would like to have the control. For instance When he want to send commands to GUI to draw something while he is working. In gogui this is solved by using stderr to send those commands, but: - stderr is not network transparent - syntax is not standardized - there is no confirmation about success / failure for those commands. 2. The second thing is that there are many variables in the engine (komi, board size, time, etc). Developers tend to have more of them to control various parameters of the engine. End users could like to have some control over strength of the algorithm, etc. 3. If GTP would supports chats, KGS would probably implement it. 4. Opponent identification. 5. Interrupt. Users do not always want to wait until the program finish work. GoGui uses comment #interrupt to do it, but this is a hack. (this is somewhat related to 1.) 6. Position setup. I had conversation with Marcus about setup in GoGui. And we concluded that there should be a separate command for that. Would You like to have those issues solved? I hope we can get somewhere. :) Best Regards, Łukasz ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
Re: [computer-go] GTPv3
Hi Łukasz, Maybe something could be borrowed from UCI, the universal chess interface. It is a really well designed protocol that serves the same purpose as GTP does for go, but it's for chess. It's about at the same point GTP is, most chess programs support it and interfaces are available for it. http://www.uciengines.de/UCI_Protocol/uci_protocol.html I'm not suggesting we switch protocols, but perhaps we could take a look at UCI and borrow some of it's better features for an updated GTP. Now, it's about time someone posts that we should be on the GTP list :-) - Don On Thu, 2007-03-01 at 13:22 +0100, Łukasz Lew wrote: Hi, There are some issues that are not so well defined in GTP v2. Maybe GTP v3 should be released to avoid too much legacy later? 1. The most important thing is controller - engine architecture. There are situations that engine would like to have the control. For instance When he want to send commands to GUI to draw something while he is working. In gogui this is solved by using stderr to send those commands, but: - stderr is not network transparent - syntax is not standardized - there is no confirmation about success / failure for those commands. 2. The second thing is that there are many variables in the engine (komi, board size, time, etc). Developers tend to have more of them to control various parameters of the engine. End users could like to have some control over strength of the algorithm, etc. 3. If GTP would supports chats, KGS would probably implement it. 4. Opponent identification. 5. Interrupt. Users do not always want to wait until the program finish work. GoGui uses comment #interrupt to do it, but this is a hack. (this is somewhat related to 1.) 6. Position setup. I had conversation with Marcus about setup in GoGui. And we concluded that there should be a separate command for that. Would You like to have those issues solved? I hope we can get somewhere. :) Best Regards, Łukasz ___ 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] GTPv3
On Thu March 1 2007 05:22, Łukasz Lew wrote: The most important thing is controller - engine architecture. There are situations that engine would like to have the control. For these requests come up once in a while, but IMO the clear separation between who is the controller and the engine is a big advantage of GTP. It makes both the implementation of engines and controllers much easier. Can you do simple, single-threaded controller scripts with UCI? Is it used for as many use cases as GTP is, ranging from regression testing to any kind of automated experiments with Go engines? The Go server protocols are designed for humans and asynchronous sending of messages between them at any time, but does it make sense for a computer engine to allow it to start chatting, whenever it feels like it? I think that GTP should not be extended in a way that makes the implementation of engines or controllers more complicated. In gogui this is solved by using stderr to send those commands, but: - stderr is not network transparent Remi Coulom convinced me that it is more convenient for the engine to write to standard error and he was right. Typically the GTP interface is only one of several interfaces to lower level Go engine code and you don't want to make lower level code aware of this. One idea I had in mind to address this was to allow the engine to send comment lines before the actual response. Then you could tunnel the standard error output through a network connection in these comment lines, maybe starting with a special keyword. It would need only a minor modification to existing controllers to ignore all text before the response. Alternatively, one could extend the tools GtpServer and NetGtp in the GoGui package to internally transmit standard error text in such a way, that would be transparent for the engine and controller on different hosts. 6. Position setup. I had conversation with Marcus about setup in GoGui. And we concluded that there should be a separate command for that. The coming version 1.0 of GoGui will support a setup command. It is a simplified version of a suggestion I made a while ago to the GTP list and uses a syntax like: gogui-setup b A1 b B2 w C3 Originally I had an undoable setup command in mind to incrementally follow setup stones in SGF trees, but it is much easier for engine programmers to handle only full position setup on empty boards, so GoGui will follow the SGF properties incrementally and translate setup nodes into clear_board / gogui-setup sequences. - Markus ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
Re: [computer-go] GTPv3
The coming version 1.0 of GoGui will support a setup command. It is a simplified version of a suggestion I made a while ago to the GTP list and uses a syntax like: gogui-setup b A1 b B2 w C3 I would like to suggest using the command setup_sequence instead to miror the play_sequence command which was introduced by GoGui (I believe).___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
Re: [computer-go] GTPv3
On Thursday 01 March 2007, Phil G wrote: I would like to suggest using the command setup_sequence instead to miror the play_sequence command which was introduced by GoGui (I believe). I finally followed the GTP (draft) standard and used a prefix separated by a hyphen for non-standard extension commands, so play_sequence became gogui-play_sequence. setup_sequence wouldn't be a good name, because the setup stones are not a sequence, you can specify them in any order. There will also be a second command gogui-setup_player for setting the color to play, but support for that is optional, since it is not strictly necessary that the engine is informed about the color to play. The genmove and play commands are sent with a color argument anyway. If an engine does not support gogui-setup, setup stones will be sent as moves as previously. - Markus ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
Re: [computer-go] MC - Estimating a moves true probability of winning
I respond to various items below. Sections of the original e-mail that I'm not responding to were completely deleted. Jacques Basaldúa wrote: Hello Jason I think what you are trying to do can be done more easily. I guess the key question is what am I trying to do?. In UCT, the next move to simulate is chosen based off of an estimated probability of winning. Correcting bias in that estimate should lead to better sampling. If one abruptly stops all simulations and picks the best move based on this estimated probability, I think this may give the optimal answer... choosing the move with the highest expectation of winning the game. It's important to note that with a peaked distribution of moves' probabilities of winning, the estimated probability of winning will rise slowly. That means that moves with only a few simulations will never be chosen over moves with (a good win rate and) a lot of simulations. C. To compare if a move is better than another, you have to compare _confidence intervals_. I.e. the interval in which p (the unknown probability) lies computed from your observed p-hat, n and a desired confidence level, say 95%. These intervals can be computed with methods you can find searching for Confidence Interval for a Binomial Proportion. The most used are Wilson and Agresti-Coull intervals. These intervals include continuity correction as you mention in your post. Other ways of comparing proportions are: The difference between proportions, the relative risk and the odds ratio to name a few. My Bible for this is a book called Categorical Data Analysis from Alan Agresti published by Wiley Sons. With lots and lots of simulations, this could lead to a prediction such as move a is better than move b with 95% confidence. If a bot wants to prove with high confidence that the move that it has selected is better than all others, I suspect it may have to do lots and lots of simulations and would be impractical. I think that was the same point you made later in your e-mail. I welcome someone proving us wrong ;) An alternate but related approach is move a is better than move b with a p-value of xx%. Of course, I'm also not too sure on how to use that result. To use these results, you must make some assumption about the underlying distribution of a move's probability of winning. That's the good news. You don't. There is no need to understand what complex mechanism produces p. Only that: same position == same p. If you take a good look at your tests, they will make very specific null hypothesis which in effect make at least some assumption about the underlying distributions (or try to wash away all effects with the central limit theorem). *Do not* expect a sound statistical analysis to tell you the best move, unless it is very obvious, n is immense or your confidence level is extremely low. But, if you are lucky, it will tell you what moves are clearly bad and can be safely (= with a given confidence) pruned out. I agree with that. ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
