Re: [computer-go] Re: Open source real time Go server
sorry, i should have been more clear. an SE can't be any smarter than a computer player, because it could otherwise easily simulate a computer player, as described. would it be slower? yes, by a constant factor that is bounded by the boardsize. this simulation could be completely paralellized, however, so if anyone thinks that i'm wrong, they should build such an SE, and we can easily put together enough boxes to beat all existing computer players. i point this out because a pet peeve of mine is people who complain about the SE and don't realize that it's equivalently difficult, if not *more* difficult, than building a computer player. s. On Tue, Jan 19, 2010 at 12:20 AM, Michael Williams michaelwilliam...@gmail.com wrote: Your point is obvious but that's a horrible proof since there are usually more than one legal moves from which to chose (that means it takes more time). steve uurtamo wrote: As for other things we'd like to see improved, we could build a list. My pet peeve is the KGS score estimator, which is often wildly wrong. an SE can't be any smarter than a computer player that runs in the amount of time that you're willing to wait for the SE to calculate*. so don't expect much. ever. recall that the SE runs locally in your client. s. * proof: if it were, then it would make a better computer player by just evaluating its score estimate at all legal board points and choosing the maximum at each move. ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/ ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/ ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
Re: [computer-go] Re: Open source real time Go server
As for other things we'd like to see improved, we could build a list. My pet peeve is the KGS score estimator, which is often wildly wrong. an SE can't be any smarter than a computer player that runs in the amount of time that you're willing to wait for the SE to calculate*. so don't expect much. ever. recall that the SE runs locally in your client. s. * proof: if it were, then it would make a better computer player by just evaluating its score estimate at all legal board points and choosing the maximum at each move. ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
Re: [computer-go] Optimizing combinations of flags
That doesn't seem to directly support deriving information from random trials. For computer go tuning, would you play multiple games with each parameter set in order to get a meaningful figure? That seems likely to be less efficient than treating it as a bandit problem. you'd decide how many experiments you wanted to run, take a stab at what you thought the interactions between parameters were (i.e. independent between #2 and #3, and no worse than quadratic between #1 and #4), generate an optimal design, run enough experiments at each setting of the parameters (as specified by the design) to keep error low, then fit the specified model with the resulting data. the way to consider the model is that you want to model winrate versus (whomever -- self-play, on kgs, whatever you want), and you have some idea about interactions between parameters (i think that this cutoff is only appropriate between these two ranges, and have reason to believe has only a very weak interaction with this other parameter, whereas these 12 parameters might all be related in some horrible quadratic way), but you don't want to blindly run thousands of random tests. you'd rather run thousands of tests that were specifically designed to maximize the amount of information that you can get about the model that you're trying to fit. alternatively, it does sphere packing over the direct product of open or closed (but bounded) intervals and discrete sets, so you can get a set of points that is slightly better than a random set of experiments (i.e. guaranteed to cover the space well). s. ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
Re: [computer-go] Optimizing combinations of flags
sorry to self-reply, but: alternatively, it does sphere packing over the direct product of open or closed (but bounded) intervals and discrete sets, so you can get a set of points that is slightly better than a random set of experiments (i.e. guaranteed to cover the space well). arguably it is not slightly better, but much, much better. especially when the dimensionality (number of parameters) is high. s. ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
Re: [computer-go] Optimizing combinations of flags
the way to do all of this exactly is with experimental design. to design experiments correctly that handle inter-term interactions of moderate degree, this tool is quite useful: http://www2.research.att.com/~njas/gosset/index.html s. ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
Re: [computer-go] Re: Hahn system tournament and MC bots
maybe divided by ten? s. On Mon, Nov 23, 2009 at 5:50 AM, Robert Jasiek jas...@snafu.de wrote: Ingo Althöfer wrote: I would have found a completely continuous result system more natural, for instance giving +40.5 points for each win with 40.5 or more giving -40.5 points for each loss with 40.5 or more The most natural score-dependent Go variant(!) would be the game result x for the score x, with resignation being not available and using some scoring method that has +-361 as its extreme scores. -- robert jasiek ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/ ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
Re: [computer-go] Re: Hahn system tournament and MC bots
i'm just thinking that approximating the 10 stones on the board == 1 stone of handicap phenomenon might be a nice way to keep track of score in a tournament. i realize that it's not terribly accurate, but it would give a number that's easier to parse. dividing by 10 for everyone wouldn't change the overall result, so it wouldn't punish anyone, right? s. On Mon, Nov 23, 2009 at 9:03 AM, Robert Jasiek jas...@snafu.de wrote: steve uurtamo wrote: maybe divided by ten? To punish programs or me for the ability of killing 70 stones dragons? -- robert jasiek ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/ ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
Re: [computer-go] Re: Hahn system tournament and MC bots
:) my point was that simply totaling total won by points after each game is over, or totalling total won by points divided by ten after each game should produce the same rank order of results, therefore not punishing anyone. my comment that one handicap difference in strength, in an even game, roughly equates to 10 game stones at the end of the game, was perhaps too distracting as a rationale (perhaps because it is only empirically true at the kyu level?). the idea that i like about keeping track of number of points won or lost by is that not only could you find the winner, but you could find how absolutely dominant, on average, they were against their opponents. if the variance was low, we might expect to see, say, a less than 20 stone average advantage in points. normalizing by dividing by 10 just scales this down to something chunkier. s. On Mon, Nov 23, 2009 at 9:53 AM, Robert Jasiek jas...@snafu.de wrote: steve uurtamo wrote: dividing by 10 for everyone wouldn't change the overall result First you describe something like handicap steps, then you describe something different (a mere division by 10). Therefore so it wouldn't punish anyone, right? ...this question cannot be answered. -- robert jasiek ___ 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: [SPAM] Re: [computer-go] Joseki Book
you could always take a joseki dictionary and build the trees by hand, if you feel that you're strong enough to work out the most common variations for the most common opening situations. s. 2009/11/9 Olivier Teytaud teyt...@lri.fr: There is a paper about that in http://hal.inria.fr/inria-00369783/en/ and Tristan Cazenave published something around that also. (these two works are about the automatic building of opening book in self-play) See also the references in the PDF above. Best regards, Olivier Only papers I can recall are from seventies (assuming you mean academic papers) from Wilcoxx. I may have electrical copies. Not sure though. I managed to find some of them from ACM site. That paper described position based approach where each and every stage was stored into datastructure, kinda like huge pattern matching library. Was called lenses if I remember correctly. More common way is store joseki moves as a tree. Biggest issue is always hos key in all those variations. Petri 2009/11/9 Jessica Mullins jmull...@lclark.edu Hi, I am wondering what is the best way to build a Joseki Book? I am a student at Lewis Clark College and am working with Professor Peter Drake to build a Joseki Book for the program Orego.sed aproach i.e each state of joske Right now I am extracting moves from professor players and saving those into a database. Then if during game play a position is contained in the database, play the response move like the professional. I am just wondering what other people have done to build a Joseki Book, or if anyone knows of any papers that might be helpful. Thank you, Jessica Mullins Lewis Clark College '10 ___ 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/ -- = Olivier Teytaud (TAO-inria) olivier.teyt...@inria.fr Tel (33)169154231 / Fax (33)169156586 Equipe TAO (Inria-Futurs), LRI, UMR 8623(CNRS - Universite Paris-Sud), bat 490 Universite Paris-Sud 91405 Orsay Cedex France (one of the 56.5 % of french who did not vote for Sarkozy in 2007) ___ 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] Neural networks
these things have definitions, folks. everything isn't everything else. s. On Tue, Nov 3, 2009 at 7:43 AM, Willemien wilem...@googlemail.com wrote: I disagree with the point that MCTS is a neural network, In my opinion (and i maybe completely off target) One of the essences of neural networks is that the program changes/learns from the games it has played. . MCTS doesn't have that result, the improvement is only in-game The program doesn't learn not to make the same mistake anymore, by MCTS the mistake is hopefully avoided. if MTCS is a neyural network than alpha beta would also qualify. but i may be wrong it is just an opening for a discussion in which we all can learn 2009/11/2 Daniel Burgos dbur...@gmail.com: Well, at its esence a computer is an universal Turing Machine. If you organize the program as a neural network or as a MC algorithm is just cosmetics. You can see the circuits of your computer as neurons simulating a Von Neumann architecture that is simulating a neural network or a MC or whatever. An may be your whatever is simulating another thing. 2009/11/2 Álvaro Begué alvaro.be...@gmail.com On Sun, Nov 1, 2009 at 7:50 PM, Aldric Giacomoni ald...@trevoke.net wrote: Álvaro Begué wrote: 2009/10/31 compgo...@aol.com: Present day MC Go programs are neural networks. The playout is the trainng process. What? ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/ Go programs using the Monte-Carlo algorithms are neural networks. The actual fact of playing games is what trains them to play better. ... I'm pretty sure that's what it means, anyway. Except they don't fit any definition of neural network that I've been able to find. For starters, they don't have neurons. ___ 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/ ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
Re: [computer-go] CUDA implementation of the per-intersection GPGPU approach
Since AMAF values are so helpful, perhaps one can let go of the idea of sequential play following the rules of go, and basically play moves in parallel on all empty intersection. Compute new state (do captures) and repeat a fixed number of times and evaluate. two thoughts: i) how do you determine color to play for each thread? ii) if i) becomes unsynchronized with the rules of go, you're basically exploring random boards instead of boards that are related to the game that you're interested in. the board should rapidly converge to something that retains no information about the initial state of the board (assuming that the initial board has stones on it). s. ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
Re: [computer-go] Dynamic komi at high handicaps
zen wins many more of its even games with no handicap than it does with even, say, an even 2 stone handicap as either black or white. i haven't compiled numbers for it (i'm not zen's maintainer), but i watched it happen over the course of about 50 games one day. it was pretty consistently worse with any kind of handicap on the board, the more handicap the worse. fix the handicap problem and it would likely rise a stone in strength. s. On Wed, Aug 19, 2009 at 12:15 PM, Jeff Nowakowskij...@dilacero.org wrote: On Wed, Aug 19, 2009 at 07:27:00AM -0700, terry mcintyre wrote: Consider the game when computer is black, with 7 stones against a very strong human opponent. Computer thinks every move is a winning move; it plays randomly; a half-point win is as good as a 70-point win. Didn't this game actually happen? Didn't MoGo *beat* a pro with 7 stones? Did it play randomly? Don't the monte carlo bots frequently win as White when giving handicap stones on KGS? I think we need some real statistical evidence that this problem is even worth talking about, aside from stylistic issues. I'm not the first to say this, but I think it bears repeating. -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] Re: Dynamic komi in commercial programs
i think that the rationale behind variable komi is intuitive: good players can handicap one another more effectively with komi than with handicap stones, because it's more fine-grained. this is likely what is leading to the idea that computers playing handicap games could use this to their advantage. there's something like an exact tradeoff between stones and komi, although i don't know the function and it'd be interesting to find. s. ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
Re: [computer-go] Experimentation
something i've played with a little bit: only look at algorithms with the following property: * they every so often update an in-memory score for each board position. you can then run a timing loop around this and just make the highest-scoring valid move the play. you can use a signal handler to dump the list at any time. s. 2009/7/7 terry mcintyre terrymcint...@yahoo.com: Digesting Don's remarks, it seems that a reasonable method would start with equal numbers of simulations. It could then proceed to try various optimizations, and compare algorithms which use equal time. It makes perfect sense for the ultimate goal to be better performance using the same time or less, but it might be easier to progress stepwise - first tweak the top-level design, then tweak the performance - in order to separate out the different inputs to the experiment. Terry McIntyre terrymcint...@yahoo.com “We hang the petty thieves and appoint the great ones to public office.” -- Aesop ___ 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] Complicated seki with Ko
zen builds sekis, and occasionally wins games that way. s. On Tue, Jun 30, 2009 at 1:25 PM, Jason Housejason.james.ho...@gmail.com wrote: Is it possible to explicitly use a monospace font? I can't read your board positions. I haven't heard of any handling of seki in playouts except for Remi's CrazyStone. I don't think he's ever given specifics on how he did it. Maybe he'll respond to your e-mail? Sent from my iPhone On Jun 26, 2009, at 1:37 PM, Brian Sheppard sheppar...@aol.com wrote: Here is a position that exposed some bugs in Pebbles. Maybe it will help you. 1 2 3 4 5 6 7 8 9 A - O - O X - - X - B - X O - O X - O O C - O O - O - X O - D X X X O O O O O O E - O X X X O X O O F - - O X O X X X X G - - X X O O X X - H - O X O - O O X X J - O X O O - X - X X to play. X is already doomed in this position. The bottom O group is in a seki with the X group at right. O cannot play J6 self-atari. X cannot fill in J8 and then play J6, and after X J6, O captures and X cannot recapture. So it will be dual life. Because the top of the board is O's, O have more than half the board, even without komi. The playouts have to handle certain issues well in order to find that. The first point is to filter out plays that make self-atari on large groups. This will cause the rest of the board to fill up until only the seki remains. The the playout will be in a position like the following: 1 2 3 4 5 6 7 8 9 A - O - O O - O O - B O - O - O O - O O C - O O - O - O O - D X X X O O O O O O E - X X X X O X O O F X X - X O X X X X G X - X X O O X X - H X X X O - O O X X J X - X O O - X - X X to play. Pebbles does not detect superko in playouts, so this position will loop forever with J6/J8/J7/pass. In Pebbles, infinite games were scored as draws. I changed that to give the win to O on the basis of its preponderance of material. (No doubt that will bite me at some point.) Even if we detect the superko repetition, it seems to me that we are only getting the right answer by accident. For instance, if X plays J6 then after J8/J7 there is no move for X, so X has self-ataried himself. Another possibility if to see that X's J6 is atari and also self-atari, so X can look for the approach move. In this case X would play J8 instead of J6 which avoids the ko. Then the seki is obvious. How do other programs handle this case? ___ 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] Ko in light playouts
what happens with the following? rank the moves as normal, ignoring ko. choose the highest ranked legal move at the end. (i.e. only check for ko-legality when choosing the final move) s. On Mon, Jun 15, 2009 at 4:45 PM, Heikki Levantohei...@lsd.dk wrote: I am slowly getting my little bot to do very light playouts. I came to think about detecting ko. Is it even necessary in a simple playout? During the earlier stages of the game, the playouts have no idea of wanting to recapture the ko, of ko threats, or anything else. Only in the endgame can we run into problems, when everything else is filled up, and the only points left are in a ko fight. At that point the playout moves are fast, repeating the same position all over again, until a limit to the number of moves puts a stop to it all. I suppose that in the end the right thing is to do the right thing, and detect at least a simple ko properly and according to the rules. But I thought I'd ask if people are trying alternative tricks? - Heikki P.S. My progress is awfully slow, as I work full time with other things, and have several hobbies cometing for my spare time. Still, I am making slow progress, and at some point I get my halfgo playing on cgos. Very badly, to begin with... It is a simple program, written in C, using bitmaps for the board images. I just wanted to see how far I could take that approach. Now it seems to be a good foundation for my next experiments, which I will have to do before discussing them here. -- 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/
Re: [computer-go] MCTS, 19x19, hitting a wall?
But here is someting interesting: In the case of computer chess it has been estimated that the progress in software has been roughly the same as the progress in hardware. Modern chess programs are truly amazing, and not just a result of faster hardware. There is no reason to think that this won't be true of computer go. This makes me wonder... so how slow (and RAM starved) of a computer could you use and still get grandmaster level chess play? In other words, how far back could we go in time if we had today's software and expect a computer to play chess as well as humans? s. ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
Re: [computer-go] MCTS, 19x19, hitting a wall?
To conclude, it appears that 500 MHz (embedded: poor cache performance) with little memory for transposition tables is the lowest you can go, while still staying at grandmaster level. that's quite impressive. some kind of pipelining is involved? are they 32bit? s. ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
Re: [computer-go] bots and handicaps (Re: New CGOS)
The handicap system is imperfect anyway, it's almost a coincidence that it works as well as it does. okay, this sounds like chess bias. the handicap system *defines* the difference in skill levels in go. it's a coincidence that something like ELO can match fairly well to stones. not the other way around. the fact that chess doesn't have a fine-grained way to handicap a game, in fact, the fact that most games don't, doesn't mean that it's hard to deal with. my guess is that any go playing program that doesn't depend upon an opening book for a lot of its strength is going to adapt just fine. experiments between players of different CGOS-measured strengths could find this out for sure -- time for another set of experiments? i'll donate some cpu time. if it helps to encourage the authors, just keep in mind that winning with handicap is extremely convincing evidence to regular go players that one player is much stronger than another. plus, it takes exponentially fewer games to determine that difference. with a logarithmic (in range of handicap, say, +/-6 stones) number of games you could get a very accurate view of the strength difference between two players. say, take best of 2 out of 3 at each test level and do binary search. some go clubs just keep track of the relative difference in stone strength between pairs of players, requiring, say, a 3-win streak by one player to adjust the handicap by a single stone. alternatively, you can (somewhat cheesily) map ELO to handicap and vice-versa for a limited range of ELO and handicap. s. ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
Re: [computer-go] Congratulations to Steenvreter!
contests are never hindered by weak opponents, in my opinion. the more the merrier the better of course! s. 2009/6/1 dhillism...@netscape.net: One factor is that there seems to be a narrow range between too few entrants and too many. For any given contest, the potential pool includes an elite few who have a chance at first place and maybe a couple who have a new or newly improved bot. There is a larger group, back in the pack, whose last breakthrough was a while ago. For many of us in that last group, it would be easy enough to enter, but hard to know if that would help or hinder. - Dave Hillis -Original Message- From: David Doshay ddos...@mac.com To: computer-go computer-go@computer-go.org Sent: Mon, 1 Jun 2009 5:32 pm Subject: Re: [computer-go] Congratulations to Steenvreter! SlugGo has not been participating because we had made no progress. I hope to have something by the end of summer. Cheers, David On 1, Jun 2009, at 1:39 PM, Nick Wedd wrote: would like to know what I might do to attract more entrants. ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/ Wanna slim down for summer? Go to America Takes it Off to learn how. ___ 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] Implications of a CPU vs Memory trend on MCTS
increasing memory is more expensive than increasing cpu speed at this point. there was an addressing issue with 32bit machines, but that shouldn't be too much of an issue anymore. most people want to pay less than or equal to the price of their last machine whenever they buy one, though, so companies oblige them -- companies have to change something, though, so they make new cpus. i agree that ram is the more useful thing to have access to, but it's just hideously expensive to have lots and lots of high speed ram available to the cpu. if you need some extra ram, feel free to use your graphics card's ram. most modern graphics cards have way more ram than you might think. there aren't many technologies that work cheaper than ram that are within an order of magnitude or two of the speed of ram. so you're pretty much stuck. one nice thing about your compression idea is that fast cpu means that you can afford to spend more time fiddling with compression and decompression. if the size of any object is really an issue, here's what i'd suggest -- * look at the structure of your objects during actual games and try to figure out where self-similarity lies. * actually copy the memory objects to disk and bzip them and see how much compression you get. if it's not much, it's a big waste of time to even think about it. * think, hard, about how much extra ram you'd need to be happy and content, and how much extra gameplay you'd get out of having that extra ram. if doubling your ram would only effect a 10% advantage, is it worth the effort? * turn the problem around and ask yourself what you'd do if you had, say, a terabyte of ram. such machines exist, but that isn't that important. how would you write your code differently if you had that much ram, and would it instantly mean that your program would be immensely stronger? if not, then ram isn't the main issue. if you can figure out how to use that much ram to guarantee a much stronger player, then maybe someone will loan you one to play with. even if they don't, it's an important exercise, especially if it turns out that: * perhaps your structures are so self-similar that you can get radical levels of compression easily. there are some very cheesy ways to do this. you can use zlib on structures that haven't been accessed in awhile or which you expect not to be accessed for awhile. you'll need to fully decompress them to access anything inside of them, though, so it might make sense to set up your compression hierarchically according to how you wander through your structure. this is very tricky stuff that entirely depends upon what access patterns you're using through your structure, and how it's built. enjoy serializing and unserializing your objects. basically, if you want to have high-speed random access to nearly random data, you have to use ram. change any two of these variables and you can probably hog some of the cpu to give you a hand. s. ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
Re: [computer-go] Implications of a CPU vs Memory trend on MCTS
is the ssd fast enough to be practical? s. On Tue, May 12, 2009 at 12:41 PM, Michael Williams michaelwilliam...@gmail.com wrote: Don Dailey wrote: On Tue, May 12, 2009 at 12:16 PM, Michael Williams michaelwilliam...@gmail.com mailto:michaelwilliam...@gmail.com wrote: I have a trick ;) I am currently creating MCTS trees of over a billion nodes on my 4GB machine. Ok, I'll bite. What is your solution? I use an SSD. There are many details, of course. But it's still in the works and I'm still making lots of changes and adjustments. I seem to be able to solve (there are lots of definitions) 6x6 Go in that when I use a komi of 3.5, it is unable to find a winning line for white and when I use 4.5, it is unable to find a winning line for black. ___ 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] Implications of a CPU vs Memory trend on MCTS
cool, that's what i was wondering -- that you'd have to treat it as something inbetween ram and a HD. thanks, s. On Tue, May 12, 2009 at 12:48 PM, Michael Williams michaelwilliam...@gmail.com wrote: It depends on how you use it and how much you pay for it. If you get a high-end Intel SSD, you can treat it however you like. But I can't afford that. I got a cheap SSD and so I had shape my algorithm around which kind of disk operations it likes and which ones it doesn't. steve uurtamo wrote: is the ssd fast enough to be practical? s. On Tue, May 12, 2009 at 12:41 PM, Michael Williams michaelwilliam...@gmail.com wrote: Don Dailey wrote: On Tue, May 12, 2009 at 12:16 PM, Michael Williams michaelwilliam...@gmail.com mailto:michaelwilliam...@gmail.com wrote: I have a trick ;) I am currently creating MCTS trees of over a billion nodes on my 4GB machine. Ok, I'll bite. What is your solution? I use an SSD. There are many details, of course. But it's still in the works and I'm still making lots of changes and adjustments. I seem to be able to solve (there are lots of definitions) 6x6 Go in that when I use a komi of 3.5, it is unable to find a winning line for white and when I use 4.5, it is unable to find a winning line for black. ___ 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/ ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
Re: [computer-go] Monte-Carlo Simulation Balancing
also, i'm not sure that a lot of most amateurs' moves are very good. the spectrum of bad moves is wide, it's just that it takes someone many stones stronger to severely punish small differences between good and nearly-good moves. among players of relatively similar strength, these differences will go unnoticed and unpunished. s. 2009/4/28 Don Dailey dailey@gmail.com: A simplistic model that helps explain this is golf. On a single hole, even a casual golfer has a realistic chance of out-golfing Tiger Woods. Tiger occasionally shoots a 1 over par on some hole and even weak amateurs occasionally par or even birdie a hole. It's not going to happen a lot, but it's not ridiculous either. Years ago I taught a player how to golf, and on his third time out with me, he hit a hole in one on a short par 3. If Tiger Woods had been playing with us, he would have lost that hole to this beginner. But in a 9 hole match, the odds go down enormously - for all practical purposes there is no chance. I kind of think of GO like that, even though it's a pretty simplistic model. Each move is like a hole of golf, it can be a good shot or a bad one. With GO, however, probably a LOT of your moves are just as good as the moves of a good player. But it's the ones that fall short, that kill you. Go on a big board is like 18 holes of golf compared to just 1 or 2 holes of golf. The better player is far more likely to win the 18 hole match than the 1 hole match. - Don On Tue, Apr 28, 2009 at 1:53 PM, Ivan Dubois dubois_i...@yahoo.fr wrote: I noticed that, in general, changes in the playout policy have a much bigger impact on larger boards than on smaller boards. Rémi I think rating differences are emplified on larger boards. This is easy to see if you think about it this way : Somehow a 19x19 board is like 4 9x9 boards. Let us define a new game that I would call 4-Go where instead of playing one game, you play simultenously 4 games and determine the winner by calculating the sum of the scores of the four games. Certainly rating differences would be bigger with 4-go than with go (given the same two players). This explains why rating differences are bigger on 19x19 than 9x9. Ivan ___ 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] Could be that nobody is playing?
it would slowly grow in (measured) strength over time. s. 2009/4/20 terry mcintyre terrymcint...@yahoo.com: From: Jason House jason.james.ho...@gmail.com CGOS requires us to use new names on the server each time we change our bots. It computes the strength using all games (heavilly biased with the results of the first 100 games) Hypothetically speaking, if a bot were to actually learn from experience, how would CGOS deal with that? ___ 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] COGS bug in Ko detection?
it's simply too easy to write the code to check for this on the server side for it to be a bug. :) s. 2009/4/13 Don Dailey dailey@gmail.com: Hi Brain, I get a superko bug report or two almost every month since CGOS has been running (2 or 3 years?) It's usually due to a misunderstanding of which specific superko rule CGOS uses. CGOS uses positional superko. I'm quite sure there is no bug here. There are OTHER bugs in the server, but not superko! - Don On Mon, 2009-04-13 at 09:32 -0400, Brian Sheppard wrote: Black is flagged for an illegal Ko at the end of game 738921 on CGOS. Black played H1, which looks legal to me. Server bug? Scanning through the log today, I found a similar situation in game 738998. The setup is that two stones in the corner are captured by playing 1 stone. Recapture of the capturing stone is declared a Ko. There was no SuperKo repetition involved in either game. Best, Brian ___ 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] Fast ways to evaluate program strength.
otherwise pair-go wouldn't be as funny to watch. s. On Tue, Apr 7, 2009 at 8:05 PM, Michael Williams michaelwilliam...@gmail.com wrote: Łukasz Lew wrote: I would like to rephrase my question: Let's measure prediction of pro moves of a whole engine while modifying heavy playouts / MCTS in the engine. How well might it work? Probably not well. Because what matters is not how often you play strong moves, but how often you avoid blunders. ___ 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] Rules for remote play at the Computer Olympiad
Moreover, this is a really complicated issue. There has been some extensive statistical work on human cheating in chess done by Ken Regan at the University at Buffalo. However, this relies heavily upon the fact that computers dominate human play by a wide margin. The same is not the case in go. s. On Sat, Apr 4, 2009 at 1:56 AM, Robert Jasiek jas...@snafu.de wrote: Vincent Diepeveen wrote: If a program under no circumstance can reproduce a specific move and that for several occasions, then that's very clear proof of course. [...] Statistics prove everything here. No. Rather it proves that the program cheats OR that the methods of detecting cheating are improper. One always must have a logfile Good. -- robert jasiek ___ 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] time measurement
if it really mattered, remote participants could use a phone to connect -- it's not like these are very high-volume transmissions, and the latency, while high, is still an unimportant fraction of total time. on the plus side, the latency is exact. on the minus side, it's a pretty expensive phone call. :) s. On Tue, Feb 3, 2009 at 12:03 PM, terry mcintyre terrymcint...@yahoo.com wrote: I would not want to discourage remote players - some systems are designed to take advantage of large supercomputers which are not very portable. However, remote players need to accept the trade-off. They get to avoid the trouble of packing up and shipping a trailer full of computer gear to the other side of the world. The downside is that network lag happens. As others have mentioned, client-side timing can be gamed by the simple expedient of pulling the plug to the modem; I can think of a few ways to manipulate iptables which would have similar effects. I hope that tournament organizers do their best to provide a decent connection. Remote participants need to do likewise. ___ 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] time measurement
a slightly simpler protocol: you let me put a machine on your local network that i control, and you agree to do an ntp-like service with it. s. ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
Re: [computer-go] Re: Hardware limits
my biased $0.02: i don't think that the point is to call it even. someone's got to win, and everyone else has to come in = 2nd place. moreover, pretending as if this is the kind of contest that can be won with money (or hardware) alone is just sour grapes. one way to make this a contest about algorithms would be to require everyone's code to run on identical hardware under the identical operating system. how much fun would that be? not very much at all. imagine that you're used to being able to fit a very frequently-accessed table entirely in ram. in fact, many of your other data structures and code flow are built around the fact that it fits entirely in ram on your box. then imagine that the contest hardware has less ram and that you get to spend 90% of your thinking time watching the machine swap, or rewrite all of your code. no thanks. sure, this is the opposite of the problem that is being described -- instead of it being a sad story for the guy who has tiny hardware, it's a sad story for the guy who has access to better hardware. in neither case is it a really sad story, however. it's just that arbitrary limits always cause problems for somebody. the *only* time where hardware could really become an issue is if everyone competing is using algorithms all of which scale at roughly the same rate, all of which parallelize at roughly the same rate, etc. talk about a boring contest! this isn't an asymptotic problem requiring an algorithmic solution. this is a fixed-size board requiring a best of show answer. whoever gets there, however they get there, deserves to win, as long as the machines are choosing their own moves. s. ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
Re: [computer-go] Re: GCP on ICGA Events 2009 in Pamplona
i think you might be estimating this incorrectly. s. On Sat, Jan 10, 2009 at 9:00 AM, Gian-Carlo Pascutto g...@sjeng.org wrote: Ingo Althöfer wrote: What prevents you from freezing in your chess activities for the next few months and hobbying full (free) time on computer go. The amount of chess players compared to the amount of go players. -- GCP ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/ ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
Re: [computer-go] Re: Hardware limits
also, it's quite surprising how few watts the human brain uses. s. ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
Re: [computer-go] 3-4-5 rule
that's with or manhattan distance 2 as well? how about 3 or 4? s. On Mon, Dec 29, 2008 at 7:42 PM, Don Dailey dailey@gmail.com wrote: After 842 games with 19x19 go the version with the 3-4-5 line rule is scoring about 55% I thought it might do better, I think the rule is reasonably sound - but 55% is pretty respectable for such an easy change and it hardly slows down the search at all. Rank Name Elo+- games score oppo. draws 1 d2p 2037 12 12 842 55% 20000% 2 base 2000 12 12 842 45% 20370% ___ 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] Value of rule
don, this rule is very intuitive for a 19x19 board even if you include the 5th line. for a 9x9, i'm not so sure. s. On Sun, Dec 21, 2008 at 3:55 PM, Don Dailey dailey@gmail.com wrote: As previously mentioned, I have been testing the rule which says move only to the 3rd and 4th lines unless something is nearby.In this case, the rule is 3-5 lines. I started with 200 playouts, because I'm also interested in how this rule affects play at various depths. Here is the 200 playout results: Rank Name Elo+- games score oppo. draws 1 d2p 204188 5803 53% 20210% 2 d2r 202988 5803 50% 20290% 3 d3r 200988 5810 50% 20080% 4 d3p 200788 5805 49% 20160% 5 base 200088 5803 48% 20130% Here is a key: base - no rule d2 - distance 2 (must be = 2, otherwise move only to 3-5 lines) d3 - distance 3 r - only applied to root move selection. p - applied in playouts AND root move selection. So d2p - is the version with distance 2 applied in playouts and root. From the above ELO chart, the idea look pretty good. Distance 2 seems to be superior to distance 3 and the best version takes it all the way through the playouts. The other test uses 2000 playouts. The results is not so rosy and could be due to statistical noise. But at least the same idea tested strongest, but only by 17 ELO. 17 ELO gives you a win expectancy of a little over 52% using ELO's formula. Rank Name Elo+- games score oppo. draws 1 d2p 2017 12 12 2190 52% 20010% 2 d3r 2004 12 12 2196 49% 20080% 3 base 2000 12 12 2193 49% 20040% 4 d2r 1999 12 12 2191 50% 19980% 5 d3p 1993 12 12 2190 49% 20010% Conclusion: At low playouts, it works well. At high playouts, it's difficult to say if it helps or not. The evidence is slightly in favor of using it, especially since it does not show much of a slowdown. I'm now measuring approximately 3% slowdown for doing this in the playouts. I have a feeling this would work significantly better on larger boards, so I will try 11x11 next. 11 x 11 is the best board size for go :-) - 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] MC Opening stage
the thing about within manhattan distance (small) of other stones type heuristics is that they seem to leave out the possibility of tenuki. s. On Thu, Dec 11, 2008 at 5:27 AM, Thomas Lavergne [EMAIL PROTECTED] wrote: I've not tryed it for the moment due to lack of time for computer go, but I've thinked about an opening heuristic thta from a go player point of view seems acceptable : - For the first play, restrict to intersection at a manhatan distance of 2 from the corner hoshi (4-4 points) (and tengen if you want ot allow a more cosmic style) - Next restrict to a manhatan distance of 2 from : - Corner hoshi - Side hoshi if at there is a stone in at least one of the corners and manhatan distance of 3 from stones already on board As the game progress, increase theses distance progressively. Probably something like add 1 to each every five moves. Play on the first line are forbidden until mid-game, unless there is a stone in manhatan distance of 2. You can stop using early, for example at play 15 or 20, or wait to the time were there is no restriction due to the ever increasing number of stone and distance restriction. This cover most of professional games, and seems for me sufficiently conservative. Other policies can reduce more the search tree, but from my point of view they can prune too much the search tree. Tom On Thu, Dec 11, 2008 at 08:29:40AM +0900, Darren Cook wrote: Most of those 55 distinct moves are rarely used in the opening. I once heard a simple rule which seems to cover just about everything interesting: consider only moves which are on the 3rd and 4th lines, and/or within a manhattan distance of n, for some small n, of some other stone already on the board. Wandering off the opening theme a bit, but the book, Oriental Strategy in a Nutshell, by Bruce and Sue Wilcox has numerous rules of thumb of this nature. It will probably appeal to the people on this list more than the wishy-washy play here because it feels good style of most traditional go books. The rules might be useful in MC heavy playouts. Going back to the topic, for 19x19 at least, I would suggest make an opening book from pro and strong amateur games. Only start using MCTS once you leave the book. Using MCTS on the first move is like trying to use a precision screwdriver to hammer in a three-inch nail: your tool will break before you get any worthwhile results. Darren -- Darren Cook, Software Researcher/Developer http://dcook.org/mlsn/ (English-Japanese-German-Chinese-Arabic open source dictionary/semantic network) http://dcook.org/work/ (About me and my work) http://dcook.org/blogs.html (My blogs and articles) ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/ -- Thomas LavergneEntia non sunt multiplicanda praeter necessitatem. (Guillaume d'Ockham) [EMAIL PROTECTED]http://oniros.org ___ 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] MC Opening stage
and there are nontrivial arguments concerning points way out near the center. s. On Wed, Dec 10, 2008 at 3:39 PM, terry mcintyre [EMAIL PROTECTED] wrote: From: tony tang [EMAIL PROTECTED] Back to the original question - accounting for symmetry, there 55 distinct opening moves on a 19x19 board. Are there a noted collection of these opening moves? if so could you direct me to the material? cheers Do you mean the 55 distinct opening moves? Divide a 19x19 grid along the two diagonals, and the vertical and horizontal midlines; you have eight identical pie slices. The number of points in any triangular slice is the sum of 1,2,3..10 - or 55. The slices share points along the common edges. Most of those 55 distinct moves are rarely used in the opening. I once heard a simple rule which seems to cover just about everything interesting: consider only moves which are on the 3rd and 4th lines, and/or within a manhattan distance of n, for some small n, of some other stone already on the board. If memory serves, David Fotland mentioned this at the Portland Congress. Some players favor opening moves on the fifth line, however. ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/ ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
Re: [computer-go] Re: hex robot
don, i agree, although i will point out one of C's biggest flaws, which happens (conveniently for the sake of this argument) to be its least important one for game programming: string handling sucks if i never have to handle a string, i'll choose C without question. when i need to handle strings, i choose C with major reservations. s. On Thu, Nov 27, 2008 at 11:55 AM, Don Dailey [EMAIL PROTECTED] wrote: On Thu, 2008-11-27 at 13:03 -0200, Mark Boon wrote: You say you're going to try to make a prototype first and then when it shows promise, move to a more flexible language like Java. What language are you intending to use? It seems the wrong way around to me. Develop the prototype in a flexible language and when it seems to work, move it to a specific langauge that can leverage some specific CPU features. Seems to make much more sense to me. This is clearly the conventional wisdom, but I think it's a mistake for an ultimately high performance game program, even for an initial prototype. The supposed benefit is freedom to experiment and nail down your algorithm, but I think this is a myth. I know that sounds like blasphemy, but when I've tried this before I discovered that even though C/C++ is pretty gnarly, it has at least 3 major advantages that might not matter for many other things, but is very important for games: 1. It's about as fast as you will get. 2. It is superbly flexible. 3. It is not a memory hog. To summarize my experiences, these wonderful high level languages are full of limitations and you spent more time pulling your hair out to work around them. Even the speed limitation is more of an issue that you think, if you make heavy use of testing. If you don't make heavy use of testing, you don't know what you are doing anyway. For instance, let's say you are experimenting with an algorithm. At some point you must test that algorithm to see if it's better than what you were doing, or to compare it with something else. You must play a large number of games to measure superiority, unless it is overwhelming. Most changes won't be overwhelming and even if it is you still need a lot of games to know how overwhelming it is. With a slower language this is correspondingly a slower process, negating much of the supposed high level language advantage. I spend more time waiting on tests than programming, even in C. Someone says, but if you have a large bank of workstations ...Well if you do, it doesn't change the fact that you are wasting them. An author for a strong playing engine for any game will be able to utilize as much power as you give him for testing. If I had 100 workstations I still would not use Ruby (a joy to program in and one of my favorites) because what a stupid waste of resources it would be to make those 100 workstations perform like only 2 or 3 workstations. When developing the simple reference bot, and experimenting with ideas to make it play better with fewer simulations, guess what? I am performance bound - I cannot test ideas fast enough and this would be worse with a high level language. A word about Java, which will probably produce some anger because I know some of us here love Java. I have never seen a top level, non-trivial game playing program in Java. I don't think you could build a strong chess program in Java. Probably more due to memory issues than performance - but I think for a top chess program performance would be an issue too. Yes, it's possible to write some programs in Java that are almost as fast as C, but probably not a chess program.You really need system level programming type of flexibility that C provides, not high level abstractions that the processor doesn't care about, and the compiler cannot optimize away. An ad-hoc poll: What is the strongest Java playing program on CGOS? I can't see building a very strong MCTS GO program in Java, because even in C, the tree does not fit in memory. My little reference bot can be done in Java however. The performance loss is modest and memory isn't an issue. But the code is clearly larger. Perhaps because I'm not a Java expert, it seems to take more code to do the same thing in Java. All kinds of scaffolding required to use the standard data structures.Much more typing. System.out.printf() is just one example. Seems like a little thing and I'm nitpicking - I see some value in this kind of anal-ism for big projects especially, but it's pretty annoying. I cannot see an ease of use difference between Java and C but I can imagine with large projects Java has some advantages.With it's strong typing Java seems almost as low level to me as C. To summarize, I have found over the years that just plain CPU/MEMORY performance is the primary barrier not just to program strength, but development time. You must measure development time 2 ways. One is how many man hours are
Re: [computer-go] On Don Dailey's first chess program
commercial software was freely available on BBSes when i was a small child, and very, very many people had modems. no internet access, but modems and local BBSes. s. On Sat, Nov 22, 2008 at 10:13 AM, Matthew Woodcraft [EMAIL PROTECTED] wrote: Don Dailey wrote: A few years later I was pointed to a site where I could download that and just about any commercial chess program.We are talking several decades ago, I didn't bookmark the site or use it myself and I have no idea if it's still there. It seems to me that only a very small number of people would have been in a position to download anything, several decades ago. What kind of 'site' was it, anyway? Doubtless not a web site! -M- ___ 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] One-sided 2-inch Rules
for small k, this should give a massive advantage to black. the additional requirement that white place a stone within the smallest cityblock distance of the last stone whenever he has no valid move within distance k of black's last move is an even more substantial advantage for black. i'm thinking that black can set up situations that cause white to make bad shape. if not, it's an unimportant rule, but otherwise it's a big advantage to black. just my $0.02. s. On Tue, Nov 18, 2008 at 5:20 PM, Ingo Althöfer [EMAIL PROTECTED] wrote: Hello, one of the basic problems of go newbies is their tendency to place the next stone near to the latest stone of the opponent. Sometimes this is called the 2-inch heuristic of beginners. What do you think about a formalized variant of Go with one-sided distance-k rule? Let k be some natural number. The normal rules of Go hold, except for one thing: When possible, White has to place his next stone within distance k (in city-block metric) of the latest stone of Black. If there is no feasible move of this type the stone has to be placed within the smallest possible city-block distance of the latest stone of Black. White may pass at any time. Example: On 19x19 board k=36 would mean no restriction at all.) * What should be fair values of komi(k) or fair numbers of handicap stones? * Main question: How strong would MCTS-based programs be in this variant(s)? * Would computers be stronger than humans for certain values of k? Ingo. -- Ist Ihr Browser Vista-kompatibel? Jetzt die neuesten Browser-Versionen downloaden: http://www.gmx.net/de/go/browser ___ 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] simple MC reference bot and specification
sorry to be pedantic, but: 13. Chinese scoring. s. On Sat, Oct 11, 2008 at 9:11 AM, Don Dailey [EMAIL PROTECTED] wrote: On Sat, 2008-10-11 at 13:33 +0100, Claus Reinke wrote: I have a rough idea of what that might be. And I suspect that keeping this de facto standard implicit has been hiding some actual differences in what different people think that standard is. Some of my questions arise from trying to pin down where and why different authors have different ideas of what the standard is. If there has been some explicit standardisation since those papers were published, I'd be interested in a pointer to that standard and its rationale. I'm going to publish a real simple java reference program and some docs to go with it and a program to test it for black box conformance. (Actually, it will test 2 or more and compare them.) I would like to get someone who writes better than I do to write up the standard in less casual language but it goes something like this: 1. A complete game playing program so it can also be tested in real games. 2. Play uniformly random moves except to 1 pt eyes and avoiding simple ko. When a move is otherwise not possible, pass. 3. Playout ends after 2 consecutive pass moves (1 for each side.) 4. 1 pt eye is an empty point surrounded by friendly stones for the side to move. Additionally, we have 2 cases. If the stone is NOT on any edge (where the corner is an edge) there must be no more than one diagonal enemy stone.If the point in question is on the edge, there must be NO diagonal enemy stones. 5. In the playouts, statistics are taken on moves played during the playouts. If the move is played FIRST (during the playout) by the side to move it is one data point and the win loss record is maintained. 6. The move with the highest statistical win rate is the one selected for move in the actual game. 7. In the case of moves with even scores a random selection is made. 8. Pass move are never selected as the final move to play unless no other non-eye filling move is possible. 9. Random number generator is unspecified - your program should simply pass the black box test and as a further optional test your program should score close to 50% against other properly implemented programs. 10. Suicide not allowed in the playouts or in games it plays. 11. When selecting moves to play in the actual game (not playouts) superko is checked and forbidden. 12. If a move has NO STATS taken (which is highly unlikely unless you do very few playouts) it is ignored for move selection. Did I miss anything? I would like to get feedback and agreement on this. Please note - a few GTP commands will be added in order to instrument any conforming programs. Haven't figured those out yet, but it will be designed so that it can report number of nodes, number of playouts, average score of playouts, etc. So the tester may set up some position and a ko, and ask for statistics based on the number of specified playouts. - 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] Congratulations to David Fotland!
The fault tolerance is not a serious problem, even being tolerant against false result reporting isn't too bad with a decent error-correcting coding scheme for handing out the work. The networking issue is somewhat more serious. Not the actual network delay, but the mechanism that the boinc client software uses to process work requests and the interval at which people typically send back their results is such that you'd be unlikely to get a single work request back until after you needed it. This could work for very long-length (24h-ish) games, however, if that's the only boinc project that the remote machines were participating in. s. On Thu, Oct 2, 2008 at 3:43 PM, David Doshay [EMAIL PROTECTED] wrote: Yes, various kinds of off-line (not in-game) processing could be done. But nothing in a real-time game. Cheers, David On 2, Oct 2008, at 10:48 AM, terry mcintyre wrote: An @home network might be better for things such as creating opening books, testing algorithms, etc. ___ 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] Congratulations to David Fotland!
sure, this would work much better, and is easy to implement (diameter is log(# nodes) if you set it up as an expander!). but writing it from scratch is a bit of a burden. i may have a project like this next semester for my networking class, if so, we can tack the rest onto it if anyone's interested, over the summer, perhaps. s. On Thu, Oct 2, 2008 at 5:19 PM, Zach Wegner [EMAIL PROTECTED] wrote: On Thu, Oct 2, 2008 at 3:48 PM, steve uurtamo [EMAIL PROTECTED] wrote: The networking issue is somewhat more serious. Not the actual network delay, but the mechanism that the boinc client software uses to process work requests and the interval at which people typically send back their results is such that you'd be unlikely to get a single work request back until after you needed it. This makes the assumption that boinc is used, or at least that one central server is used. I've thought a lot about this issue, and I think one central server would be too inefficient. I would use a distributed network, and let each computer just connect with a small number of others, creating something more like a web than a tree. This could be optimized for ping time as well--arrange the nodes in the web so that they talk most with those close to them. ___ 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] Analysis of 6x6 Go
even-sized boards have the disability that there's no tengen. i think that this makes mirror go functional until fairly late in the game. s. ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
Re: [computer-go] Re: sgf format for non-quadratic board sizes?
every point having 4 liberties would seem to make the opening much more about influence. my guess is that it's an easier game. (but that's just wild speculation). s. On Fri, Sep 19, 2008 at 2:30 PM, David Doshay [EMAIL PROTECTED] wrote: First move is easy, but depending upon ratio of diameter to length of torus, ladders can get complicated. Cheers, David On 19, Sep 2008, at 10:48 AM, Álvaro Begué wrote: On Fri, Sep 19, 2008 at 1:29 PM, Don Dailey [EMAIL PROTECTED] wrote: Would go on a torus be interesting? There are not corners or edges, the sides of the board simply wrap around. - Don Yes, it's probably similar in spirit to regular go, except everything feels like the center of the board. It would also make the first move easy. :) Álvaro. On Fri, 2008-09-19 at 09:52 -0700, Ross Werner wrote: Urban Hafner wrote: Ah, right. I thought you were talking about implementing this feature for your own program. Personally I don't know of any program that supports rectangular boards. There was a recent thread on GoDiscussions about this topic: http://www.godiscussions.com/forum/showthread.php?t=6960 Not much information there, but maybe enough to be useful. ~ Ross ___ 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/ ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/ ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
Re: [computer-go] Re: OT: Teaching Go (was Re: Disputes under Japanese rules)
i've read suggestions along the lines of teaching capture go first. this should get a lot of the life-and-death intuition under the belt (plus should help learn counting liberties). s. On Thu, Sep 18, 2008 at 3:15 PM, Jeff Nowakowski [EMAIL PROTECTED] wrote: On Thu, 2008-09-18 at 11:12 -0700, Peter Drake wrote: Eventually, sure -- but I'd like them to have a few games under their belts before I bring up the issue of different versions of the rules. Ok, then play some 9x9 games with area scoring rules as Dave Devos suggested. I was making the same suggestion. Don't hit them with both rules at the same time, but make sure to choose the right set to start with! I may just follow Kim and Jeong's pedagogical lead and let the students experiment with pieces of the rules before trying to play a complete game. It's ok to teach unconditional life or simple life and death first, but once you get beyond that you need to be able to end and score the game, and beginners just can't do that easily with territory scoring and an agreement phase. I tried to learn with Kim's Learn to Play Go, and I was absolutely confused and frustrated when it came to end game scoring. The computer scientist's instinct is to lay down a terse and elegant set of rules and then deal with the consequences of those rules, but perhaps that is a bad thing when teaching. You need foundations to build on. One foundation is life and death; however, life and death is just a simple consequence of the capturing rule. The other foundation is the score at the end of the game. Having an easy way to score let's the beginner experiment with what is alive and what is dead, what is true territory that cannot be invaded. An informal agreement phase with rules that punish a player for trying to play it out is a detriment. Nobody is advocating that you give noobs Tromp-Taylor and letting them figure it out. Just don't give them territory rules with dead-stone agreement as a first 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] Disputes under Japanese rules
I've asked this question of a couple of people and got different answers, so I thought I'd check here. to get a different set of different answers. :) Suppose, under Japanese rules, I throw a (hopeless) stone into your territory. I keep passing until you've actually removed it (playing four stones inside your own territory, thus losing a net three points). If you try to pass as well, I stubbornly insist that the stone is alive, thus restarting the game. stones on the board aren't counted unless they're dead. your hopeless one stone has neither two eyes nor is a seki, so i can ignore it and we will remove it from my territory after the game is over. in fact, after you place it there, i will pass, unless you've actually caused me some danger by placing it there, in which case i will respond (and the net effect will be that we will each have placed a stone inside my territory, not affecting the outcome of the score so far). if, after we've both passed, you suggest that this clearly dead stone is in fact alive, and that all of its surrounded territory should be counted as yours, i'll point out that it doesn't surround any territory and isn't a seki, so is dead. the stones on the board that are alive dont count toward points in japanese rules, just the territory, so it matters not how many stones are on the board or if you've placed a stone inside my territory, simply that we agree on the life and death status of stones inside what we both agree *is* our territory. right? so imagine instead that you have three dead stones inside my territory and place a fourth, surrounding one point of territory, and i pass, and you place a fifth and create some intensely important ko or seki opportunity for yourself. well, then perhaps i shouldn't have passed. i was being greedy, or cocky, by taking those 3 free points, but after that, i should have been more careful. when i was first learning how to play, i would occasionally drop a stone into my opponent's territory thinking that it counted for something (that i could build life in the hopeless chasm of my opponent's territory). he'd pass. i'd drop another in. he'd pass again. basically, until he responded, i was making moves that didn't provide a real threat to him. it was only after a bit of gentle advice that i realized that i was both giving him free points and annoying the crap out of him. even an opponent who doesn't understand the concept of two eyes or seki could be persuaded according to the official procedure, which i've never seen anyone need to use in practice. if the putative opponent actually doesn't understand two eyes or seki, playing out on a separate board might be a good way to educate them without ruining the stones-in-play and creating a situation that is well-nigh impossible to undo without convincing your opponent that you're doing something sneaky to the score. of course, you could bore them to tears by writing each move down in the on-the-board after-game sequence so that they could be undone, one at a time, after life or death had been established. superko and bent four in the corner actually do require someone explaining why this is a rule, same as explaining why ko is a rule. ko because it makes the game more fun. superko because of the same thing as ko only over a longer timeframe. bent four because it's a totally crappy situation that is hard to resolve otherwise. in the case of malicious intent, a much simpler option, which i have seen exercised, is for the stronger opponent to resign and watch or start a game with someone else. it's about having fun, after all. s. ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
Re: [computer-go] Congratulations to Leela and to Many Faces!
without vast captures of territory, someone will either violate the superko rule or make an illegal move before lots of time passes. s. On Tue, Sep 16, 2008 at 10:24 AM, Jeff Nowakowski [EMAIL PROTECTED] wrote: On Tue, 2008-09-16 at 10:10 -0400, Don Dailey wrote: It's a shame Fischer Timing is not available. A small Fischer increment of 1 or 2 seconds would do the job nicely. It doesn't solve the problem of two programs that don't pass. You can't keep to a fixed schedule if you keep on allowing just a few seconds more ad nauseum. -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] Bobby Fischer
i thought that story was about lasker. s. On Thu, Sep 11, 2008 at 9:43 AM, Magnus Persson [EMAIL PROTECTED] wrote: I know a 4-Dan player who told a story that goes something like this: He and his friends who were all very strong chess players at the time, discovered the rules of go and played a bunch of games against each other until they thought they mastered it. Later they met a player who gave them a 9-stone handicap and beat them easily. They were shocked and told him he must be a master player but he just replied: No I am just a beginner. -Magnus Quoting Mark Boon [EMAIL PROTECTED]: On Thu, Sep 11, 2008 at 8:53 AM, Adrian Grajdeanu [EMAIL PROTECTED] wrote: I read that story in a book, just after Bobby Fisher's death. Don't remember all details, save that he was astonished he got beaten. Adrian Hehe. After I learned the game (from a book, playing with my father who brought a set from Japan for my birthday) I was also astonished to be beaten by the first other person I met that knew the game. And he gave me 9 stones handicap! But rather than putting me off it made me even more intrigued by the game. Now I know this person was probably not even 15 kyu. Mark ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/ -- Magnus Persson Berlin, Germany ___ 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] Kaori-Crazystone
1d (amateur) is a kind of holy grail for amateurs, because it separates fairly serious players from people just messing around, so seeing a program at that level on a 19x19 board at reasonable (non-blitz) time controls is quite impressive. 1p is generally stronger than all but a small handful of amateurs, so can be thought of as =7d (amateur). beating a 1p in a zero-handicap game would be a really, really big deal for a computer player. $1M prize was well-considered, from that point of view. i think that the insurance value of such a proposition is still pretty low. s. On Thu, Sep 4, 2008 at 11:38 AM, Don Dailey [EMAIL PROTECTED] wrote: It's difficult for me to understand this due to different ranking systems and pro ratings vs amateur ratings. I see here listed as a 4 dan player on this page: http://www.nihonkiin.or.jp/player/htm/ki000343.htm Is that 4 dan pro? My understanding is something like this: kyu player are casual players (or weak tournament players) low dan players are something like advanced amateurs or experts and weak masters in chess. Pro's are like super high dan players and there is not very much difference between ranks compared to regular dan players. I have heard that a 1d professional will beat a 9d professional with 3 or 4 stones. So a 1d pro is something like a 7 or 8d+ amateur? Is this all roughly correct? So I assume that Aoba Kaori is a 4d professional? That would relate to something in the ballpark of 9 or 10d amateur if there were such a thing. And with 8 stones handicap, this implies that CrazyStone did what a 2d+ would have done, or it is weaker than 2d but got lucky. So it's performance rating for that one game is lower bounded at around 1 or 2 dan. Since it won the game we could pick 2 dan as a better lower bound guess although since it won we do not have a reasonable upper bound guess on it's performance except our own credulity. Does what I said make any sense? I am not a go player and I'm not very comfortable with this guesswork. In chess, if you beat a player I am used to thinking in terms of setting a performance rating of around 400 ELO higher for that one game. I know this is not precise, but I also think of 400 ELO subtracted from the player you beat as a kind of estimated lower bound on your strength. If you beat a 2500 ELO chess player, it's a relatively safe bet that you are at least 2100 ELO in strength although technically there is a chance you could lose to anybody, even a random move generator. I know this isn't precise language, but how many ranks would give us around 90 - 95% confidence of superiority?If I beat a 5 dan player, could you say that it's very likely I am at least 3 dan in strength? I'm thinking that if we estimate Aoba at 10d amateur and CrazyStone wins with 8 stone handicap, it is roughly equivalent to beating a 2d player without handicap and that we can subtract 2 stones to say that with pretty high confidence CrazyStone is playing at least 1 kyu (but that's it's much more likely Crazy Stone is stronger than this - after all it performed in this one game at least as well as 2d player.) - Don On Thu, 2008-09-04 at 16:28 +0200, Rémi Coulom wrote: terry mcintyre wrote: Congratulations! Thanks. I'm dying for details! What was the time limit? The organizers asked that the program should play at a constant time (30 second) per move. The sgf file contains time stamps (you can see the time with gogui, for instance). I don't know what was her time control, but she apparently played at the same pace as the program. Did the game end on time or by resignation at move 179? She resigned. The pro was Aoba Kaori, yes? Yes. The only other information I have about the match are these pages in Japanese: https://secure1.gakkai-web.net/gakkai/fit/program/html/event/event.html#6 http://www.ipsj.or.jp/10jigyo/fit/fit2008/events.html#1-4-1 I hope the organizers can send me some photos tomorrow. Then I will set up a web page and tell the list. Rémi ___ 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] Kaori-Crazystone
in fact, if you made a betting game out of it, and formed a pool that would go to anyone willing to take the challenge, i think that you'd find that the ratio of dollars against to dollars for would be a fairly accurate depiction of the strength increase over time. the ratio would likely lag behind the reality, but with money involved, people might tend to think more carefully about the situation. i think that people have set up such market indicators for all kinds of things just to see how accurately they predict reality. s. On Thu, Sep 4, 2008 at 12:38 PM, steve uurtamo [EMAIL PROTECTED] wrote: 1d (amateur) is a kind of holy grail for amateurs, because it separates fairly serious players from people just messing around, so seeing a program at that level on a 19x19 board at reasonable (non-blitz) time controls is quite impressive. 1p is generally stronger than all but a small handful of amateurs, so can be thought of as =7d (amateur). beating a 1p in a zero-handicap game would be a really, really big deal for a computer player. $1M prize was well-considered, from that point of view. i think that the insurance value of such a proposition is still pretty low. s. On Thu, Sep 4, 2008 at 11:38 AM, Don Dailey [EMAIL PROTECTED] wrote: It's difficult for me to understand this due to different ranking systems and pro ratings vs amateur ratings. I see here listed as a 4 dan player on this page: http://www.nihonkiin.or.jp/player/htm/ki000343.htm Is that 4 dan pro? My understanding is something like this: kyu player are casual players (or weak tournament players) low dan players are something like advanced amateurs or experts and weak masters in chess. Pro's are like super high dan players and there is not very much difference between ranks compared to regular dan players. I have heard that a 1d professional will beat a 9d professional with 3 or 4 stones. So a 1d pro is something like a 7 or 8d+ amateur? Is this all roughly correct? So I assume that Aoba Kaori is a 4d professional? That would relate to something in the ballpark of 9 or 10d amateur if there were such a thing. And with 8 stones handicap, this implies that CrazyStone did what a 2d+ would have done, or it is weaker than 2d but got lucky. So it's performance rating for that one game is lower bounded at around 1 or 2 dan. Since it won the game we could pick 2 dan as a better lower bound guess although since it won we do not have a reasonable upper bound guess on it's performance except our own credulity. Does what I said make any sense? I am not a go player and I'm not very comfortable with this guesswork. In chess, if you beat a player I am used to thinking in terms of setting a performance rating of around 400 ELO higher for that one game. I know this is not precise, but I also think of 400 ELO subtracted from the player you beat as a kind of estimated lower bound on your strength. If you beat a 2500 ELO chess player, it's a relatively safe bet that you are at least 2100 ELO in strength although technically there is a chance you could lose to anybody, even a random move generator. I know this isn't precise language, but how many ranks would give us around 90 - 95% confidence of superiority?If I beat a 5 dan player, could you say that it's very likely I am at least 3 dan in strength? I'm thinking that if we estimate Aoba at 10d amateur and CrazyStone wins with 8 stone handicap, it is roughly equivalent to beating a 2d player without handicap and that we can subtract 2 stones to say that with pretty high confidence CrazyStone is playing at least 1 kyu (but that's it's much more likely Crazy Stone is stronger than this - after all it performed in this one game at least as well as 2d player.) - Don On Thu, 2008-09-04 at 16:28 +0200, Rémi Coulom wrote: terry mcintyre wrote: Congratulations! Thanks. I'm dying for details! What was the time limit? The organizers asked that the program should play at a constant time (30 second) per move. The sgf file contains time stamps (you can see the time with gogui, for instance). I don't know what was her time control, but she apparently played at the same pace as the program. Did the game end on time or by resignation at move 179? She resigned. The pro was Aoba Kaori, yes? Yes. The only other information I have about the match are these pages in Japanese: https://secure1.gakkai-web.net/gakkai/fit/program/html/event/event.html#6 http://www.ipsj.or.jp/10jigyo/fit/fit2008/events.html#1-4-1 I hope the organizers can send me some photos tomorrow. Then I will set up a web page and tell the list. Rémi ___ 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
Re: [computer-go] yet a mogo vs human game
you could use HMMs as long as you didn't mind retraining (and thus starting your ratings system over from scratch) every time you added or subtracted a new player. it'd be relatively fast in any case. s. On Thu, Aug 28, 2008 at 11:44 AM, Rémi Coulom [EMAIL PROTECTED] wrote: This was my post about multi-dimensional Elo: http://www.mail-archive.com/computer-go@computer-go.org/msg06267.html I have not tried it since that time. Rémi ___ 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] yet a mogo vs human game
this approach would also severely limit the number of players that could be involved in the rating system, since it would require manipulating an 2*(N choose 2) matrix, where N is the number of players involved. s. On Thu, Aug 28, 2008 at 12:35 PM, steve uurtamo [EMAIL PROTECTED] wrote: you could use HMMs as long as you didn't mind retraining (and thus starting your ratings system over from scratch) every time you added or subtracted a new player. it'd be relatively fast in any case. s. On Thu, Aug 28, 2008 at 11:44 AM, Rémi Coulom [EMAIL PROTECTED] wrote: This was my post about multi-dimensional Elo: http://www.mail-archive.com/computer-go@computer-go.org/msg06267.html I have not tried it since that time. Rémi ___ 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] yet a mogo vs human game
out of curiosity, can you estimate the largest number of opponents that all played each other a reasonable number of times? (i.e. what's the largest subset of opponents and number of games that you can choose so that everyone started playing everyone else in the subset without anyone leaving for good)? i've got some HMM code lying around and could generate the full matrix of win probabilities from such a dataset. this would answer the question, just how intransitively do these players play against one another. s. On Thu, Aug 28, 2008 at 12:37 PM, Don Dailey [EMAIL PROTECTED] wrote: If you ever want to try, I can give you the data for cgos in compact form that you can experiment with (one line per game - 2 names and 1 result + date) or you can simply extract them from the archived games. - Don On Thu, 2008-08-28 at 17:44 +0200, Rémi Coulom wrote: This was my post about multi-dimensional Elo: http://www.mail-archive.com/computer-go@computer-go.org/msg06267.html I have not tried it since that time. Rémi ___ 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] What was the specific design of the Mogo version which beat the pro...
And what language/platform is Mogo written in; C/C++, Java, Assembly, PHP, etc.? This made coffee spray out of my nose (PHP). I think that C is most likely, based upon how they parallelized it. Did you read the list posting that mentioned (briefly) how they scaled it up? s. ___ 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!
this is interesting! perhaps i misunderstand the setup of the experiment -- what is the unit of measure for the delay, or how is delay being implemented? the FIFO queue is doing what, and where is the delay being introduced? thanks, s. On Wed, Aug 13, 2008 at 9:20 AM, Hideki Kato [EMAIL PROTECTED] wrote: Magnus Persson: [EMAIL PROTECTED]: Quoting Don Dailey [EMAIL PROTECTED]: Yes, UCT is easier to use with multiple CPU's because with additional processors alpha-beta programs do wasted work, unless you are talking about theoretical programs with perfect move ordering, which you aren't. Nice that all is clear about alpha-beta programs. But... does not UCT with additional processors waste a lot of simulations because what would be the optimal path through the search tree depends on the threads that have not finished yet? Yes, UCT does. From my recent experiments with a delay line (a fixed size FIFO queue) between a UCTsearcher and an MC simulator with RAVE against GNU Go 3.7.11 level 0 on 9x9 (single thread): delay #po winsgames winning rateELO 1 sigma of wr 0 1,000 721 2,000 36.05% -99.6 1.07% 1 1,000 721 2,000 36.05% -99.6 1.07% 2 1,000 690 2,000 34.50% -111.4 1.06% 3 1,000 663 2,000 33.15% -121.8 1.05% 5 1,000 642 2,000 32.10% -130.1 1.04% 10 1,000 522 2,000 26.10% -180.8 0.98% 20 1,000 412 2,000 20.60% -234.4 0.90% 50 1,000 82 2,000 4.10% -547.6 0.44% Hideki Some people reported that more processors helps a lot on large boards, whereas on smaller one there is not much gain. -Magnus ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/ -- [EMAIL PROTECTED] (Kato) ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/ ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
Re: [computer-go] Re: What's happening at the European Go Congress?
what happens when the opponent deviates from joseki? knowing how to punish joseki mistakes can be very, very tricky. also knowing which joseki to use where is very, very sophisticated. the wrong joseki can be worse globally than a non-joseki move. s. On 8/12/08, Ian Osgood [EMAIL PROTECTED] wrote: On Aug 12, 2008, at 5:25 AM, Don Dailey wrote: On Tue, 2008-08-12 at 08:43 +0200, Gian-Carlo Pascutto wrote: I don't like opening books. They are a liability when the rest of the program is still improving so quickly. I had one that worked effectively, but had to be redone if the program improved substantially, so it was a program. I essentially deep-search each new position encountered. So each game played presented a new book position to learn which I did off-line. It even had variety - I didn't want it too predictable so I deep searched N times, and used the moves in the same ratio they were chosen. Usually only 1 or 2 moves get played. This is a different kind of opening book than I'm thinking of. You are both talking about cached computation, whereas I consider an opening book as codified theory and wisdom gained over the entire history of the game (semeais and joseki). How could adding established semeai and joseki patterns (probably for early move selection and bias) to a program make it weaker? If anything, the global view of full-board MCTS has the potential to make better use of semeai and joseki patterns than the classical shallow-search programs. Self-learned books were also abandoned in chess. Hand tuned books are labor intensive, often requiring a separate team member to create them, but the best chess programs all have them. Ian ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/ ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
Re: [computer-go] Re: Strength of Monte-Carlo w/ UCT...
erm. you guys seem to be arguing for the sake of arguing, without a clear or precise definition of what you're even arguing about. there is a mathematical proof that go, for any fixed sized board, can be completely solved. there is a mathematical proof that given a fixed komi and fixed number of handicap stones, every game is either a forcible win or loss or draw for a particular one of the two players. we don't know this function yet, so we don't know if there's advantage for white or black or not, but it's guaranteed to exist. is proven to exist. there is a mathematical proof that current algorithms can solve go. it makes no sense to ask if there is a mathematical proof of anything related to humans. the two are simply incommensurate. the mathematical proofs are simply about whether a computer with a lot of memory and a lot of free time can win or force draws in every game of go against any player. and it turns out that this is true. whether or not computers can beat humans at go on a 19x19 board in a reasonable amount of time is unrelated to mathematics. * computers are getting better and better at go. most people on this mailing list are mainly interested in helping (*) to happen. s. On Sun, Aug 10, 2008 at 11:46 PM, Denis fidaali [EMAIL PROTECTED] wrote: Hi there. I do agree with your point Robert Waite. I have yet seen no such paper as one that would prove that there is such thing as scalability based on any mathematical proofs. So all your points at criticizing the mathematical certainty of the scalability, is probably 100% right. There is no such things as mathematical certainty there. It can be modelized easily, as you already did : what if the the evaluation function is giving on purpose wrong data. How would one mathematically prove that it doesn't ? You would at a minimum have to know WHAT the evaluation function ACTUALLY exactly is ... In fact all the evidences that we have gathered about the scalability may rather been surprising to some persons : why in hell does all that works so well ? But, it's a proven fact that it does indeed works well so far. So that it seems perfectly natural to speak such phrases as there are evidences that given the hardware we got in twenty years, human will be beaten by current algorithms. I don't see how those evidences can be qualified with the term mathematical, but they are here (hiding among us !). Now if someone has the feeling that maybe there is a roadblock, it has to be considered for what it is : a personal intuition. What is this intuitions precisely based on ? Why are you trying to share it with us in the first place. For myself, i believe that what you are trying to do, is to begin to analyses all the data the community has gathered so far, trying to understand why indeed it worked so well that it even beaten out a pro with a 9 stones handicap and with as few as 1.7 million evaluations/second (running on some 800 hundreds cores). To the point that the pro felt he had no chances of wining at all with that much of a handicap. Your are trying to understand this, and are probably right on track for that goal. The term mathematical is very valuable to you, and you'll find it that it has a much wider use (on this list) than what you would like it to. But now, mathematics as proven to be of little use in the context of go programming lately. It's more of a physician world. You make up a (mathematical) model. You test it again reality via experimentations. You then get empirical certitudes that the model is indeed correct. There is no way of mathematically proving that light speed would still be constant if i chose to dance naked on the champs-Elysée some day. You'll definitely find no paper on that. Yet to speak of it as mathematically certain, is probably not as wrong as it sound. But as it is, i'm playing the devil advocates here. I'm totally agreeing with you. I found your way to fight irrationnality very interesting indeed. It's been very refreshing. - Robert Waite has wrote : I would really like to see what paper you are referring to. Do you mean Bandit based Monte-Carlo Planning? Please post the name of the paper which you are referring to. I do not think that the empirical evidence is overwhelming that it is scalable in a practical way for the problem of beating a human. Now the topic has moved to scalable to beat a human and I disagree with the interpretation of the data. We are both interpreting data. Your data doesn't count as a theory.. where you reduced my theory to one that has no data. We are both interpreting the same data. Diminishing returns was just an example of something that could be a roadblock. I was questioning how this necessarily scales to humans. It seems more data is needed from MC-programs vs. humans to make a rigorous theory of scalability. So far.. the only scalability
Re: [computer-go] Re: Strength of Monte-Carlo w/ UCT...
You mentioned three proofs relating to go... could you post the links to the papers? the first two statements are consequences of the following: all two-person, finite, zero-sum games have solutions. * for a more precise statement, see john von neumann's 1928 paper: Von Neumann, J: Zur theorie der gesellschaftsspiele Math. Annalen. 100 (1928) 295-320 and the definitions of the terms used in the statement (*). or perhaps more helpfully, a modern treatment on the subject of game theory. the third statement is true simply because the minimax algorithm exists. i am not claiming that any of this has anything to do with the actual problem of beating a human. i am not making this claim because i also make the claim that beating humans at go is pretty much unrelated to the mathematics in these proofs. I didn't ask for a mathematical proof saying if a computer can beat a human. I asked in a roundabout way if this algorithm (or any known algorithm) has a proven complexity that is somehow tractable or useful to beat humans. Just by throwing human in does not mean you are out of the realms of math. What about statistics? The object of many statistical models is a group of people. So please don't say it makes no sense to ask about mathematical proofs of anything related to humans. A mathematical proof can have a result that affects humans. If it was proven tomorrow that there is a set of algorithms that can solve the game in poly time.. we could draw relevant conclusions with regards to beating a human being. Relating humans to math does not destroy the accuracy of the relation. algorithms do not have complexities, problems do. algorithms may have asymptotic runtimes, but even this isn't always true. poly time doesn't mean tractable. just like exptime doesn't mean intractable. there's a coefficient in front of the polynomial (or exponential function) that can radically affect the real-world tractability of the problem. another thing is that complexity classes are used to describe problems like, find me an algorithm that can solve the game of go for *any* sized board. in this sense, go is quite difficult. however, nobody on this list is seriously hoping to write a program to solve go for any sized board and hoping that it will succeed on a 19x19 board. what they are doing is trying to engineer very good programs to beat humans on a 19x19 board. whether or not computers can beat humans at go on a 19x19 board in a reasonable amount of time is unrelated to mathematics. Why? Let's say you can prove that the game is solvable so that black wins. Let's say that you can prove that it is solvable in linear time. You can then infer that we could build a machine to play the solved game and beat a human unconditionally. Why can't you use the math here to make a statement about beating humans? what if the linear function is this one: time = 10^10^10^10^10^10^10 * (size of board) that doesn't imply tractability, but it is still linear. the problem that i mentioned earlier: how much effort is required to completely solve the game of go for _any_ given boardsize is known not to be linear. it's known not to be polynomial. the problem of solve the game of go for a 19x19 board is known to be a *constant*. since there are only a finite number of legal board situations, there are only a finite number of legal games. enumerating all of these takes a constant amount of time. storing these takes a constant amount of space. this is not useful to make good programs for playing go, however. the thing is, all of the talk of asymptotics that you seem to be referring to are perfectly useful to prove things about arbitrary games on arbitrary sized boards, but when you have a fixed-size board, what matters is much more an issue of engineering a fixed problem. s. ___ 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] Some cgos 19x19 suggestions
one more thing -- you may want to keep anchors from playing one another. at least, i seem to recall that i saw two anchors playing one another. it can't (by definition) affect anyone's ratings, so... probably pointless for them to do so, right? s. On Sun, Aug 10, 2008 at 11:27 AM, Don Dailey [EMAIL PROTECTED] wrote: On Sun, 2008-08-10 at 14:15 -0400, Don Dailey wrote: I will also modify the server so that losses by anchors don't count. Woops, what I mean is losses on TIME won't count. They will still count if the opponent loses but not if the anchor loses. - 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] mogo beats pro!
your calculation is for mogo to beat kim, according to kim and the mogo team's estimates. i think that a better thing to measure would be for a computer program to be able to regularly beat amateurs of any rank without handicap. i.e. to effectively be at the pro level. for one thing, this is easier to measure, and for another, it relies much less on mogo staying the same, kim being correct, or some other professional being much better against computer players, for instance. it just requires some machine connected to KGS to be able to attain, say, 9d, and keep it for a month or so. s. ___ 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!
again, not true. there are an infinite number of complexity classes beyond P that do not require infinite space or infinite time. exptime would just take exponential time instead of polynomial time, and pspace would just be able to reuse its available polynomial space (and thus use at worst exponential time). there are no problems that would take infinite time or infinite space. there are problems that cannot be solved no matter how much space or time you give a computer, but that's a different matter altogether, and go isn't one of those problems. s. On Fri, Aug 8, 2008 at 6:53 PM, Robert Waite [EMAIL PROTECTED] wrote: Besides... solving a pspace-complete problem would require infinite memory... isn't that correct? nope. 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. ___ 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] Some cgos 19x19 suggestions
david, is mfgo-12-0805-2c really over 400 ELO better than mfgo-11, as cgos seems to suggest? or is mfgo11 still rising up into place? thanks, s. On Sun, Aug 10, 2008 at 8:51 AM, David Fotland [EMAIL PROTECTED] wrote: First, thank you very much, Don, for giving us a reliable 19x19 server. Please consider increasing the time a program stays on the list until it ages off. I guess you drop programs from the ratings page after some time that depends on the number of games they have played. Since 19x19 games take 4 times longs, it seems you should allow four times as much time to age off the list, for the same number of games. I like seeing the top program's results a little longer. It would be nice if a program can get into position more quickly. Since the games take longer, it can take several days to climb up from the initial 1200 to 2000, especially if there is an early loos. Does it make sense to set the initial k value a little higher, or to set the initial rating to 1500 instead of 1200? -David ___ 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] mogo beats pro!
I still have this theory that when the level of the program is in the high-dan reaches, it can take proper advantage of an opening book. Alas, it may be a few years before enough processoring power is routinely available to test this hypothesis. I know that we duffers can always ruin a perfectly good joseki just as soon as we leave the memorized sequence. why would this be the case? and where would the book come from? my thinking is that unless mogo created the book itself, playing games like these, against opponents like these, at time controls like this one, then it couldn't possibly be helpful. and even then it might not be helpful. s. - Original Message From: Darren Cook [EMAIL PROTECTED] I do have to ask -- if 1.7 million playouts per second and an hour of playing time are required to reach this level, ... Can Olivier give us more details. A few questions that come to mind: how many playouts per *move* was it using in each of the opening, middle game and endgame? Was it using a fuseki book, and how many moves did the game stay in that book? And once it was out of the book was it all UCT (*) search, or were there any joseki libraries, etc.? I'd also be interested to hear how inefficient the cluster was (e.g. 1000 CPUs won't be doing 1000 times the number of playouts, there must be some overhead). Darren *: Sorry, I've forgotten the new term we are supposed to use. ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/ ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
Re: [computer-go] Re: mogo beats pro!
not something he would necessarily do in a professional tournament. perhaps true. money is a great motivating force, even small amounts of money (as don has pointed out in the past). s. On Fri, Aug 8, 2008 at 7:57 AM, Robert Waite [EMAIL PROTECTED] wrote: Yeah.. the misclick question is another fuzzy point. There was a lot of debate in the actual game about what was happening... but there is the difficulty of having weak players and strong players commenting. The only person who really knew what was happening and the direction of play is Mr. Kim. I hope that information becomes available as there are many stakeholders hoping that the results of this game provide hope for a computer crushing human opponents : ) I have a feeling that the devs are going to put out more information.. if anyone here finds solid information in the coming weeks.. please post it here so it is easier to find. What I would really hope for is someone who has a channel to Mr. Kim. This event received some coverage in AGA eJournal and certainly some here.. but to me this was a huge victory where the implications of the game did not come out until the victory. I feel that if this had occured in Japan or Korea... there would be general newspaper articles about the whole match... and there would have been dedicated reporters at the event. It would be really nice to have an interview with Mr. Kim to give stakeholders as much information as possible. I am sure that the Mogo devs are getting feedback from him... it would be nice for people in general to have Mr. Kim's take. The speed with which he played as well as the idea that he was laughing and clapping would indicate that he perhaps was testing the game and did not consider this a Showdown. Perhaps he was very surprised with its strength compared to other software he has played and was testing various aspects with his play... not something he would necessarily do in a professional tournament. This is all conjecture since we do not have a solid record yet of what Mr. Kim thought. My feelings are that even if Kim gave it his all... the overall result would have been the same: a computer got extremely strong very quickly.. and this indicates that researchers are on the right track. I am sure he is busy.. and he may even give Korean interviews about what happened... but if anyone finds information about Mr. Kims perspective of the game... I think it would be of great interest to the computer go community. ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/ ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
Re: [computer-go] Re: mogo beats pro!
okay, thanks, david. s. On Fri, Aug 8, 2008 at 8:08 AM, David Fotland [EMAIL PROTECTED] wrote: The supercomputer nodes did not have shared memory. Mogo uses shared memory within a node, but between nodes it uses MPI message passing. The supercomputer has low latency connections between nodes, and the Mogo team has said that the strength scales better on systems with this kind of interconnect than on clusters just using Ethernet. There is an issue with latency because the statistics in the important nodes of the UCT tree are shared frequently. Sharing idle time on computers on the internet would be interesting for postal games, but won't scale up in performance like Mogo on this supercomputer. David -Original Message- From: [EMAIL PROTECTED] [mailto:computer-go- [EMAIL PROTECTED] On Behalf Of steve uurtamo Sent: Friday, August 08, 2008 2:45 AM To: computer-go Subject: Re: [computer-go] Re: mogo beats pro! hm. this makes me think back to something. did this supercomputer have all of its ram shared by all processors? or could it be emulated by a large enough number of machines given individual jobs, given that combining the results of those jobs isn't too complicated? if so, i think that this would be ripe for BOINC -- at these time controls, there's no issue with latency, and there are clever ways to deal with people dropping off of the grid or giving intentionally bad information. and who wouldn't want to donate idle computer time to a project that was, say, sitting on KGS and kicking the crap out of decent players? lots of people sit on KGS and just simply watch. why not have those idle lurking watchers participate in the game as well, with their copious unused cycles? s. On Fri, Aug 8, 2008 at 2:12 AM, Darren Cook [EMAIL PROTECTED] wrote: Yes, MoGo gained much more from the longer time setting than Mr. Kim did. Note that Mr. Kim used very little of his time in the one-hour game. He said after the match that using more time would not have helped him. I imagine that is typical as white in a handicap game; you play solid, good shape moves and wait for black to do something wrong. (I.e. strong players can play a dozen simultaneous high-handicap games as easily as they can play one high-handicap game.) Darren ___ 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/ ___ 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!
don, thanks for your thoughtful comments. 9 handicap is still a real game, in the sense that the handicapping isn't arbitrary -- it definitely measures some skill difference. i think that even a match of 3 games would give quite a bit more information, although i thought that Mr. Kim had said that 9 stones would be too much regardless (or suggested as much). when janice kim won against a (13 stone?) computer handicap, that was showmanship, but a good highwater mark at the time. it'd be great if mogo, with hardware like this, or even a drastically reduced hardware set, could compete often enough to get an official ranking according to, say, the european go federation. but people are unlikely to want to risk rating points against computers, i'd think. i think that the suggestion that the mogo team with this hardware could beat a 1dan amateur regularly without handicap isn't really in question, but it'd still be worth seeing in practice. (and i wonder, as i'm sure a lot of the other scaling geeks here are, about just how much cluster you'd need in order to perform at that (1d-ish) level). although there's nothing magical about 1d versus 2d or 1k, the dan barrier still has an allure for many people, because it's just so difficult to attain for many amateurs. s. On 8/8/08, Don Dailey [EMAIL PROTECTED] wrote: I think events like this are great. They generate interest and excitement and are great fun. But they have very little scientific value. They are wide open for speculation, non-objective analysis, etc. Often strong players fail to take matches like this seriously because they are exhibitions with nothing particular at stake. I don't know if this was the case or not but I know it is happens. Also, it seems silly to me to find super strong players only to heavily handicap them. What's with that? I know of course why, nobody cares about an exhibition match with an ordinary player an thus it has value. But it really underscores the nature of this kind of exhibition, not really a significant scientific experiment. No serious conclusions are possible.It's also rather silly to rank moves and not performance in general over many games. Such and such a move was a 5 dan move, this other move was a kyu level move, etc. This is a sound bite to make people happy but isn't very quantifiable. Nevertheless, I have high praise that such an event took place, it's always super-cool to be able to utilize such a powerful machine and this was a good excuse to do so. I am left relatively confused about the outcome however. Someone gave a computer a bunch of stones and it was able to beat a strong player. Is that supposed to be exciting? I think I would simply be embarrassed that it was believed that so many stones were necessary to even the match. (Of course compared to a few years ago, this is an impressive victory for a computer go program, although only a single data point.) I hope I don't come across as being critical, I think this was a great idea and such matches should be arranged whenever possible. I just get a little embarrassed when too much significance is made of it. - Don On Fri, 2008-08-08 at 10:13 -0400, Robert Waite wrote: I was in the KGS room for a couple of hours before the match and a couple after. I was very surprised by the result as many were. There still is a lack of clear information about the event. For example, when Kim said that the computer plays at maybe 2 or 3 dan... does he mean professional or amateur pro? The supercomputer itself is unclear... some had said it would be 3000+ cores... for the game they said 800 processors. Some said it was indeed 3000+ cores.. because each processor was 4 core. But I never found a clear answer on this. The records of discussion are in MogoTitan's sgf records.. but the discussions in the computer go room and perhaps private rooms are not recorded (at least that I know of). If someone did give this information, it was very easy to lose track of when 500 people were observing the match. Tonight I am probably going to go through the records to see if any more information can be gleaned. One person who seemed to be in the room with Kim said that he was laughing and clapping at some of the computer's moves. One person in this list, but not the AGA eJournal, mentioned that Kim used about 11 minutes time.. where the computer used around 50. This was surprising to me... Kim is reported to say that he felt having extra time would not have helped. To me... this seems a little odd. He may have used it as a tactic to give the computer less thinking time (if Mogo was indeed thinking during Kim's turn). He also might have done this to show that the computer is quite a bit weaker than him. It is really hard to tell what really happened without a good report on the event. AGA eJournal
Re: [computer-go] Re: mogo beats pro!
well, in opposition to the p neq np problem, this is a fixed boardsize. it's an engineering, optimization, and special-purpose algorithm issue at this point. no need for any solution to work for all boardsizes in some measurable, scalable way. s. On 8/8/08, Robert Waite [EMAIL PROTECTED] wrote: I might come off as being strongly opinionated on the topic.. but I have been of the opinion for a while that maybe playing go is a problem that can't be solved by computers. I kinda want p != np and for us to be confined by mathematics (sorry).The general taunt from my side is that A computer can only beat a weak amateur or A computer is easily beaten by an amateur child. This record clearly will make those taunts change. It certainly affected my opinion of the strength of statistical analysis. ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/ ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
Re: [computer-go] Re: mogo beats pro!
go is worse than np-complete, it's pspace-complete. s. On 8/8/08, Robert Waite [EMAIL PROTECTED] wrote: well, in opposition to the p neq np problem, this is a fixed boardsize. it's an engineering, optimization, and special-purpose algorithm issue at this point. no need for any solution to work for all boardsizes in some measurable, scalable way. I don't necessarily think that go is np-complete... but the board does not have to be infinite to be intractable. I mean.. let's say that 19x19 go or some other game has 3^361 possible positions. That seems to be bigger than the number of available matter we have to construct memory. It seems like there would be a set of algorithms that will be able to beat the strongest human players of go. But it is not certain that there aren't certain limits to what we can calculate with computers. This is why the whole p != np is interesting. There are many common algorithmic problems that might not have a polynomial run time solution. Go has many angles of attack... but how about eye shapes... how many possible 4 stone connected eye shapes are there? Its like tetris.. there are 5 unique shapes. But so far... no one has found an efficient algorithm that will tell you how many unique shapes for N connected stones. I think they have only calculated to N=28. This isn't really an NP type problem as it is not a decision problem... but it could well be intractable. It is possible that as time goes on... computer go (or any computer) will run into certain problems that cannot be solved on a traditional computer. ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/ ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
Re: [computer-go] Re: mogo beats pro!
Besides... solving a pspace-complete problem would require infinite memory... isn't that correct? nope. s. ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
Re: [computer-go] CGOS server boardsize
this would work best for a static board evaluator. a bot that retains state would likely be best served by using ram to retain state for a single game. s. On Fri, Aug 1, 2008 at 1:51 PM, Don Dailey [EMAIL PROTECTED] wrote: How about rotating board sizes? Each round changes the board size. Just an idea. One time long ago I considered making a server where there were no time controls. You just played at whatever pace you choose. The server would try to keep your bot busy playing many different games simultaneously. Whenever your move is complete, the server hands you a new position to compute which likely would be from some other game. Slower bots of course play less games. Scheduling for this is an interesting problem, especially if avoiding mismatches is a priority. - Don On Fri, 2008-08-01 at 13:09 -0700, Christoph Birk wrote: On Fri, 1 Aug 2008, [EMAIL PROTECTED] wrote: Something that has worked well in other games would be to change the third CGOS every month. Each month, the parameters would be announced and the CGOS started empty except for the anchor(s). At the end of the month, the bot at the top?would be?the winner. That would allow us to experiment with novel settings like 11x11 boards or 20 seconds per game that might be interesting for a short while but maybe not for long. It can be a way of keeping things fresh and leveling the playing field a little. It also would need a lot more maintenance ... IMHO there would not much to be learned from (eg) 11x11. I think of CGOS as a testing arena, not a monthly tournament to find the best program at some arbitrary setting. Christoph ___ 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] What Do You Need Most?
the $500K/year to hire an expert team of programmers to incorporate everyone's source code into an open-source framework is pretty wasteful. just let people dig through the code on their own. it'd be good enough, and save $500K/year. there's no real reason to give out the hardware, either, unless you want to encourage people to spend their time each year developing tinier and tinier high-powered wireless devices for cheating. all they need is access to an equivalent machine (say, ssh access) during the year to test and write speed optimizations. also, after this ran for a few years and started to get very competitive, it'd be difficult to convince people to give away their source code every year for the chance to win $100K/year. one reason is that commercial exploitation of their code would begin to be worth more as the strength improved significantly. another way to do all of this is to set aside a large chunk of money, let it accumulate interest, and have small milestones set each year that can pay prizes from a portion of that interest if they are met. this automatically ends up raising the value of the milestones over time. s. On Mon, Jul 28, 2008 at 4:24 AM, Mark Boon [EMAIL PROTECTED] wrote: It's a question I have often contemplated. I don't think you can do anything now that will greatly influence what the level in 2010 will be. You have to think a little longer term. What it takes is fairly simple, it takes a million bucks per year (roughly). Getting that million bucks is not so simple, but if I had it to spend on computer-Go, here's what I'd do: - Use a system like CGOS to create an online testing system / community. - At some predetermined date the top n programs (say 16) get a standard state-of-the-art PC to work on. - Half a year later those 16 programs play an extensive tournament using the standard hardware. - Prize-money is $100K, $80K, $60K, $40K and $20K for the top five. - All participants contribute their source-code to an open-source project created for this event. - The cost of organising the competition above is about $500K per year, the other $500K is spent on hiring a team of expert programmers who incorporate the contributions of the competing programs into an open-source framework. This is sketchy and lacks some vital details, but you get the idea. The main points are a) Everybody starts from an equal base each year. b) The PC used is a standardized piece of equipment. c) The prize-money is enough to make people turn in their source-code. Since coming in 2nd or 3rd isnt much less an achievement as coming in 1st, the prize-money is also not much less. With a competition like this in place, I think the progress in a decade will be astounding. Now we have to find a sugar-daddy who's willing to put in the $1M each year :-) Mark On Sun, Jul 27, 2008 at 10:23 PM, Darren Cook [EMAIL PROTECTED] wrote: I have a strong interest in seeing a 19x19 computer go program that is at least 3-dan by 2010. The recent jump in strength on the 9x9 board has given me new hope and I want to ask people here, especially the authors of strong programs, what you now need to make the next jump in strength. There seem to be four broad categories: * More hardware (CPU cycles? Memory? Faster networking? Do you just need that hardware for offline tuning, or for playing too?) * More data * New algorithms (if so, to solve exactly what? evaluation? search? other?) * More community By community I mean things like this mailing list, CGOS, open source projects, etc. By data I mean things like: game records, or board positions, marked up with correct/incorrect moves; game records generally; pattern libraries; test suites; opening libraries. Darren -- Darren Cook, Software Researcher/Developer http://dcook.org/mlsn/ (English-Japanese-German-Chinese-Arabic open source dictionary/semantic network) http://dcook.org/work/ (About me and my work) http://darrendev.blogspot.com/ (blog on php, flash, i18n, linux, ...) ___ 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] Random
the only thing to watch is that you'll likely need
30+ bits from these guys to seed a prng, and
getting those bits in any organized way is likely
going to happen on a regular schedule (i.e. if
you get them in a loop, you're likely going to
space them out in an organized way).
s.
On 5/15/08, Don Dailey [EMAIL PROTECTED] wrote:
For a long time I have pondered whether you could build a very high quality
random number generator that was extremely fast using the pentium RDTSC
instruction as a low order bit entropy source. The idea would be to use
an extremely fast (but low quality) pseudo random number generator, but
modify the output (or the internal state of the generator) with the time
stamp register at each call.
RDTSC reads the pentiums internal clock and is basically just a 64 bit
counter.However it increments very quickly and could be viewed as an
entropy source in the lowest bits as it would introduce at least a little
bit of non-determinism, and I think a little is all you would need to
transform a horrible generator into a good practical one for many
applications. I think the lowest 2 or 3 (or more) bits would appear to
modern processors as almost unpredictable since there is so much going on
inside modern computers that are unpredictable.
I don't know if the call to RDTSC is fast or how it would affect the
parallelism of todays modern machines. I'm not particularly interested in
non-deterministic generators as I sometimes depend on this for testing and
debugging, but it's an idea I thought I would throw out there.
- Don
Don Dailey wrote:
If you are looking for a cheap fast and simple random number generator, A
post by George Marsaglia, an expert/guru on random number generation has
several and a C implemention.
These are one line generators, coded as macros.He also discusses the
period and quality of each of them. This is a gem of a post on
sci.stat.math,sci.math if you are interested in RNG:
http://www.math.niu.edu/~rusin/known-math/99/RNG
- Don
Heikki Levanto wrote:
In addition, xor_shift is better than builtin rand() and faster and
much smaller than MT.
I don't know that much about random numbers, so excuse my ignorance. But
a
bit of googling got me to the Park - Miller Minimal Standard random
number
generator
http://www.firstpr.com.au/dsp/rand31/p1192-park.pdf
From what I read, it should be quite sufficient for go programs. It is
dead simple and fast:
long int pmrand() {
const long int a=16807;
const long int m= ( 1 31 ) -1;
pmrandseed = ( pmrandseed * a ) % m ;
return pmrandseed;
} /* pmrand */
Should I worry about this not being good enough?
- Heikki
___
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] A problem with selectivity and AMAF bias
magnus, I hate to ask the obvious, but how much time does each simulation take? If 100 simulations would be enough information to get it out of its rut, why not just check every legal move for (say) 100 simulations before doing anything else? on another note, i think that it's cool that you have a board situation that exhibits such borderline behavior (i.e. that it takes relatively few simulations to fix the problem, but that the code as it stood would never find the problem on its own). steve. On Fri, Apr 11, 2008 at 4:25 AM, Magnus Persson [EMAIL PROTECTED] wrote: Quoting Michael Williams [EMAIL PROTECTED]: Magnus Persson wrote: Yesterday I noticed an odd phenomena in Valkyria wich was caused by high selectivity and AMAF. Then since there is nothing in the AMAF scores that indicate that move 2 is any good it is never searched, since the search is so selective that the bounds will not grow large to compensate for the bias in a reasonable time. Isn't this fixed by never straying from a move in the tree until it loses and then trying an untried move? Or something like that. It wasn't my idea and I don't remember the details, but it seems like it fixes what you describe. No, it does not because the AMAF score for move 2 is strictly lower than the evaluation for move 1 and all other moves for some reason. It will try other moves deeper in the tree instead and the position is sufficently complex to generate a very large tree until it gives up on the move at the root level. The thing is that if it searches move 2 for at least 100 simulations it will discover it is a good move. But because of the AMAF score is so low and all other moves are indeed losing moves it sticks to move 1 because it at least makes it into a fight although at bad odds. Otherwise I am quite happy with the current implementation since it is strong in testing, this only happens when there are two hot candidates and the first one is searched first because of a limitation in move ordering, and a particularly strong bias works against the second best. The annoying thing is that is can suddenly lose a game it was winning. But I found a better fix. I also tried to enter my pattern priorities as the priors of the AMAF scores. And I now strongly believe that this is also better in general and not for this particular situation. In the position I wrote about yesterday this version get the right move almost immediately. I tested as Valkyria 3.2.0 overnight on CGOS and it seems to be just as strong as the previous version, and I can still tune the parameters of it. This means that the search of position will be guided in order by 1) My pattern priorities disguised as priors of AMAF scores. 2) Then AMAF score will take over 3) If a move is searched, then the true winrates for those moves will be used and there is no bias from the pattern priorities except very weakly from the AMAF scores. -Magnus -- Magnus Persson Berlin, Germany ___ 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] My experience with Linux
The difference (and I'm not defending HP here) is that a print scheduler for your OS shouldn't even be *writable* by the install wizard for your printer. Imagine an OS environment where a printer is a completely passive device that accepts requests to print onto paper. Imagine that it doesn't pong every device on the network, or every other printer on the network (remember appletalk?), and that there is no automatic printer discovery. In my opinion, printer discovery should happen well before the time that the printer is installed. There's nothing to discover if you install the printer yourself. I didn't discover the printer attached to my PC when I plugged it in, I discovered it on the shelf of the store that I bought it from. If i'm a network administrator, I should be pretty much aware of when I plug a networked printer into the local network, and it seems to be a reasonable responsibility of mine to first make the decision about which machines should be able to print from it, and then to take the necessary steps to make that happen. Expecting an entire network of machines to do that job for me is not a particularly smart way to manage your network. s. ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
[computer-go] now: operating systems and love, was: Paper for AAAI (David Silver) PDF problem
That's the real problem with Windows. I need a double boot, place the OS on a FAT32 partition and have a copy of every file + an image of the installed partition. Every day I fight against the operating system I have paid for and if the OS doesn't let me change it the nice way I have to do it the hard way. If I was starting now, I would be a Linux user. There's another way, and it's not too bad, depending upon how often you want to switch operating systems. Get a second drive. I have been burnt by windows more times than I care to have been (twice), so I decided to do the safest thing possible -- I don't even cross the streams. I just separate the OSes onto physically distinct drives, and in my case on different controller types, which makes it super-easy to switch between them. Yes, you can modify the boot loader on the main (windows) drive so that it recognizes the second drive, but I do something even less error-prone -- I just swap which drive is considered the boot drive in my BIOS at boot time. This takes about 2 seconds and does the obvious thing that I want -- if I'm spending weeks in FreeBSD, I don't have to do a thing until for some crazy reason I want to switch back to windows (usually to play a game of some kind, or to use some esoteric feature of my peripherals that nobody has bothered to reverse-engineer yet). Most windows-esque tasks are handleable in a modern unix system: abiword and openoffice do a reasonable job at emulating word and office, respectively (and openoffice is about as bloated a chunk of code as you might expect as a result) can read and save files from/into the relevant formats, and have about the same ease/unease of use. Gimp is a reasonable clone of photoshop, although if you're a serious designer you already have a mac and over $1200 worth of adobe software and are doing it the right way. There isn't, and this is actually a fortunate thing, yet any way to use unix without at some point needing to use a command-line tool. This is what will keep it out of the hands of consumers for a long time to come, but I think that it's an inherent fact of a secure operating system. Anything that runs in the same way that vmware runs is pretty cool, although I'm not aware of anything mature and free that does the same thing as well as it does (i'm sure that someone will correct me on this point.) If the company you work for will pay for it, just tell them that you need a copy to get work done. As of a few years ago, it was working really well (vmware, that is -- the tactic is timeless). The reason that NetBSD is so good is for a similar reason to the reason that you like Windows95. It is tiny. Extremely tiny. Moreso, it will run on just about any hardware that you can still get to power up. Unfortunately, it comes with just enough tools to *compile* everything that you need to use it. So it's a fantastic way to learn about unix, but not practical for people who want something that has, say, a beautiful looking window system with knobs to control everything about their operating system right out of the box (not having these things is a good thing in my mind, though). The reason that it isn't practical for most people is because you're going to need to compile that window system, and there will be a large and painfully recursive tree of dependencies that will need to be compiled first. If you enjoy this kind of one-time masochism in the pursuit of knowledge, then it's well worth your time. Linux is starting to be a good compromise for most folks, and ubuntu is pretty popular these days, but I still think that FreeBSD has the best compromise between features and kernel sanity for someone moderately comfortable with unix. I've seem windows users semi-easily switch to ubuntu without regret or too much of a learning curve, but they will eventually find something that doesn't work and/or is extremely difficult to do without using windows. It's just an issue of compromise -- people are so used to rebooting their broken operating systems that they've forgotten that it's not something that you're supposed to have to do! Unix boxes can brag about 10+ year uptimes, for crying out loud. s. ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
Re: [computer-go] Paper for AAAI (David Silver) PDF problem
Hello, I'm getting the same thing here in windows: Cannot extract the embedded font... Was it made with pdflatex or somesuch? Could it be a version issue there? s. On Mon, Apr 7, 2008 at 6:48 AM, Jacques Basaldúa [EMAIL PROTECTED] wrote: Hi David http://www.cs.ualberta.ca/~silver/research/publications/files/MoGoNectar.pdf Your paper has a PDF problem concerning embedded font BXGQFO+CMR12. I have used different versions of Adobe Reader. I even updated one of the computers to the latest version and I still cannot read any mathematical expressions. I guess this applies to all Windows users. Jacques. ___ 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/
NOW: OS wars, WAS: [computer-go] Paper for AAAI (David Silver) PDF problem
But anyways, NetBSD is the best. yes, this is obviously true. on another (the original?) note, the relevant factor regarding being able to open a scientific paper on multiple platforms is that it be readable by as many people as possible -- even those people who run windows. OS belligerence is charming in its own way, but it's unrelated to whether or not the average person can access the equations in your work without booting into a particular operating system. the brand newest version of acrobat is working fine for me after uninstalling the older version. for what it's worth, there's anecdotal evidence that it was a change in the way that acrobat was dealing with certain fonts that they broke in one version (i think that they were adhering to some internal spec more stringently) and then fixed (probably because it caused lots of problems for people). or maybe it's not adobe's fault at all but something in windows. :) s. ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
Re: [computer-go] Some ideas how to make strong heavy playouts
don, But I also discovered that there seems to be no benefit whatsoever in removing them from the play-outs.I have no real explanation for this. But it does tell me that the play-outs are very different in nature from the tree - you cannot just use the same algorithms for selection and prioritizing moves. did you use the same heuristic in the playouts when pruning them? i.e. that no other stones are anywhere nearby? in any particular playout, they may be the killing move for a group that ends up getting built near to the edge of the board, or a successful monkey jump. so removing them from somewhere deep in the tree as a rule would be bad, but if nothing is anywhere nearby, removing them as a first move choice is pretty reasonable. they make up a fairly small fraction of possible moves, and this is magnified the deeper you go into a search (so the net effect would be diminished, even with the heuristic). anything you can say about what not to do on the very first move of a search, if it applies to every board situation (ha ha ha) is great, though, if it's fast enough to check for. in fact, if *nothing* is *anywhere* nearby, a move on even the second line is bad. third or fourth is much better. s. ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
[computer-go] 9x9
congratulations to mogo on its performance today! it was an excellent result (1-2) versus a professional, s. ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
Re: [computer-go] Floating komi
why doesn't someone simply try this and post the results, if they think that it would help? s. On Thu, Mar 6, 2008 at 8:30 AM, Don Dailey [EMAIL PROTECTED] wrote: Christoph Birk wrote: On Mar 5, 2008, at 11:58 AM, Don Dailey wrote: Don Dailey wrote: not assuming that MC plays the best move. The problem isn't the assumptions I am making, but the assumptions others are making, that it's NOT playing the best move.You want to apply a fix to all positions without really knowing which positions are a problem. One last time: Nobody suggested a one fix for all positions/problems. The floating komi was suggested to guide the UCT search along certain lines of play during specific (close!) endgame positions. When I said all positions I meant all games.You expect to apply this to all winning and losing positions in every game, not just specific ones. - Don Christoph ___ 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: endgame (Was [computer-go] Re: Should 9x9 komi be 8.0 ?])
You have to have a nakade pattern on the board somewhere, the score has to be close and in your favor considering the nakade, and the program has to believe that it is more advantageous to give away stones that not. eh, or it can't see the capture until it's only a few moves away, because its horizon with respect to self-atari is so shallow. deepen the horizon and it'll consider those moves early enough not to screw up its overall win percentage evaluation. Although it's easy to see that nakade is a problem, I agree with someone who said it takes a lot of skill to produce this.In fact, I believe that it cannot be done reliably by any player unless he is already much stronger than the program, in which case he doesn't need to do it in order to beat the program. I wouldn't go this far -- humans learn from their mistakes, but can stay at the same skill level regardless of how much they learn, either because they forget things that they earlier learned, or because they have very shallow reading, say. for a computer, though, it's quite possible that every single player ranked one or two stones lower than (arbitrary mc program with this weakness -- AMCW) could exploit this weakness in a systematic way, more than 50% of the time. this would eventually reduce AMCW's ranking, of course, but wouldn't raise any of those player's rankings, because their ability to beat one specific player consistently isn't enough to modify their ranking. (Indeed, it may be a counterproductive strategy if it distracts you from playing good moves.) these aren't bad moves in any way. they're normal, healthy, strong go-player moves that are recognized instantly by anyone who has a read a copy of life and death or similar. Most MC programs won't just let you pick off points because that is normally a strategy that decreases your winning chances. They will only do that if every move leads to the same win or loss in every single play-out, or if the small win turns out to be easier to manage. or if they aren't reading out the playouts deeply enough that would allow them to correctly consider the impact of those moves early enough to avoid them! I would love to see a 5kyu player get on KGS and beat mogo in more than 1 out of 10 games using this specific strategy.My guess is that if your energy is spent setting up this trick, you will play weaker in general. i dunno. imagine one of the mate in 20 types of sequences that you're supposed to learn when you first learn chess. imagine that you never learn how to deal with them. s. ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
Re: [computer-go] Almost whole board seki
hey, that's great! s. On Wed, Mar 5, 2008 at 2:43 PM, Gunnar Farnebäck [EMAIL PROTECTED] wrote: For those of you who enjoy uncommon positions, CGOS 9x9 game 322479 offers a lot of seki. This is the final position: A B C D E F G H J 9 . X X O . O . X . 9 8 X . X O O X X X X 8 7 O X X X O O O X O 7 6 O X X O X X O O O 6 5 O O X O X X X X O 5 4 O . O O O X . X O 4 3 . O O O O O X X . 3 2 O X X X O O O X X 2 1 . X . X X O O O O 1 A B C D E F G H J Except for the small black group in the upper left the whole board is seki. Amazingly white wins the game without a single independently alive stone, in total one proper and two false eyes. Game record is attached. /Gunnar ___ 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: endgame (Was [computer-go] Re: Should 9x9 komi be 8.0 ?])
cool. do you have any examples from a 19x19 game? that's what i was referring to when i said that i've never seen an MC player play out a ko fight. thanks, s. On Tue, Mar 4, 2008 at 9:35 AM, Magnus Persson [EMAIL PROTECTED] wrote: Attached is an sgf-game of a long kofight on 9x9 between Valkyria and Gnugo. Valkyria of course wins with 0.5 otherwise it would probably not have been such a nice example of a long kofight. -Magnus ___ 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: endgame (Was [computer-go] Re: Should 9x9 komi be 8.0 ?])
So I don't think sophisticated ko fights are resolved but I not strong enough to really quantify this. It's very often the case that games between, say, two 7d players on KGS will come down, in large part, to one or two or three ko fights and their resolution. or even the threat of a ko fight if one player is weak enough. i'm not sure that even the strongest amateurs count all of their ko threats correctly ahead of playing them (the game is quite dynamic, after all) but this is way, way deeper water than i tread in, so i don't have any real idea. i just wonder if anyone has tried to beat these programs by initiating a complicated but critical ko fight. i'd think it'd be a can't-lose if you chose it correctly. i wonder if it's a repeatable way to beat these guys, or if the depth is handled just fine. the thing that got me thinking about this is that i've never seen an MC player really play out a ko fight. (or perhaps they are in their own cryptic MC way that i can't see). s. ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
Re: endgame (Was [computer-go] Re: Should 9x9 komi be 8.0 ?])
the general idea is that if the ko represents something of value X, then making threats of value X will force your opponent to answer, and if he does not have as many threats of value X as you do, then you can eventually win the ko fight (by filling the ko) and gain X-(value of sente) points, or have a threat unanswered and gain ( X - X) points, along with possibly taking sente (which could be worth something near to X, but is probably smaller). this is really relevant when X is large, or when there are multiple kos on the board of varying values. important kos are often at a critical connection point for one or both players, or at a critical eyespace (such as in the corner or along the edge) strong players can crush weaker players simply by starting kos in important places because they know that they can win the ko or gain points in compensation for starting a ko, since ko fights are generally very hard for weaker players, who usually misjudge the value of ko threats, remove ko threats early in the game for no good reason, or have difficulty finding (or creating a sequence of!) reasonably-valued ko threats. s. On Mon, Mar 3, 2008 at 8:49 AM, Don Dailey [EMAIL PROTECTED] wrote: steve uurtamo wrote: So I don't think sophisticated ko fights are resolved but I not strong enough to really quantify this. It's very often the case that games between, say, two 7d players on KGS will come down, in large part, to one or two or three ko fights and their resolution. or even the threat of a ko fight if one player is weak enough. i'm not sure that even the strongest amateurs count all of their ko threats correctly ahead of playing them (the game is quite dynamic, after all) but this is way, way deeper water than i tread in, so i don't have any real idea. i just wonder if anyone has tried to beat these programs by initiating a complicated but critical ko fight. i'd think it'd be a can't-lose if you chose it correctly. i wonder if it's a repeatable way to beat these guys, or if the depth is handled just fine. the thing that got me thinking about this is that i've never seen an MC player really play out a ko fight. (or perhaps they are in their own cryptic MC way that i can't see). Perhaps I don't know what I'm talking about here, but is it possible that most ko fights can be avoided?Perhaps ko fights introduce too much uncertainty and they look for a more simple way to proceed? I've seen lot's of positions where there is a ko back and forth 2 or 3 times and the computer used every other turn to do something constructive in some particular area - then when it stopped fighting it stayed interested in that other area. I don't really know if what I saw meant anything - it involved only 1 ko point.Is that still considered a ko fight? It seemed to me to know what it was doing, picking (what seemed to me) just the right moment to abandon the ko. - Don s. ___ 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: endgame (Was [computer-go] Re: Should 9x9 komi be 8.0 ?])
ah, sorry to respond to my own post, but of course if the game is close, the threat doesn't even need to be of value X, if it is large enough to threaten to win the game, which can happen in near-endgame situations. the idea is that you start a ko for something that your opponent is absolutely unwilling to give up (because it would lose the game), and for which you have no expectation of being able to win that fight, you can still either get small compensation (by making an unanswered tiny threat) or big compensation (by making a threat that if unanswered would lose the game). so simply having these threats lying around in the bank can be quite profitable if they're used correctly. games are sometimes resigned as soon as one player realizes that he doesn't have enough ko threats to win a ko fight, if it's for enough points. but as you mentioned earlier, sometimes MC players abandon the fight because something else looks more interesting. this is fairly rare behavior in human games, which is why i noticed it of these (MC) players. s. On Mon, Mar 3, 2008 at 12:37 PM, steve uurtamo [EMAIL PROTECTED] wrote: the general idea is that if the ko represents something of value X, then making threats of value X will force your opponent to answer, and if he does not have as many threats of value X as you do, then you can eventually win the ko fight (by filling the ko) and gain X-(value of sente) points, or have a threat unanswered and gain ( X - X) points, along with possibly taking sente (which could be worth something near to X, but is probably smaller). this is really relevant when X is large, or when there are multiple kos on the board of varying values. important kos are often at a critical connection point for one or both players, or at a critical eyespace (such as in the corner or along the edge) strong players can crush weaker players simply by starting kos in important places because they know that they can win the ko or gain points in compensation for starting a ko, since ko fights are generally very hard for weaker players, who usually misjudge the value of ko threats, remove ko threats early in the game for no good reason, or have difficulty finding (or creating a sequence of!) reasonably-valued ko threats. s. On Mon, Mar 3, 2008 at 8:49 AM, Don Dailey [EMAIL PROTECTED] wrote: steve uurtamo wrote: So I don't think sophisticated ko fights are resolved but I not strong enough to really quantify this. It's very often the case that games between, say, two 7d players on KGS will come down, in large part, to one or two or three ko fights and their resolution. or even the threat of a ko fight if one player is weak enough. i'm not sure that even the strongest amateurs count all of their ko threats correctly ahead of playing them (the game is quite dynamic, after all) but this is way, way deeper water than i tread in, so i don't have any real idea. i just wonder if anyone has tried to beat these programs by initiating a complicated but critical ko fight. i'd think it'd be a can't-lose if you chose it correctly. i wonder if it's a repeatable way to beat these guys, or if the depth is handled just fine. the thing that got me thinking about this is that i've never seen an MC player really play out a ko fight. (or perhaps they are in their own cryptic MC way that i can't see). Perhaps I don't know what I'm talking about here, but is it possible that most ko fights can be avoided?Perhaps ko fights introduce too much uncertainty and they look for a more simple way to proceed? I've seen lot's of positions where there is a ko back and forth 2 or 3 times and the computer used every other turn to do something constructive in some particular area - then when it stopped fighting it stayed interested in that other area. I don't really know if what I saw meant anything - it involved only 1 ko point.Is that still considered a ko fight? It seemed to me to know what it was doing, picking (what seemed to me) just the right moment to abandon the ko. - Don s. ___ 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: endgame (Was [computer-go] Re: Should 9x9 komi be 8.0 ?])
i'm just saying (and perhaps i'm misunderstanding something here) that lots of playout depth, and therefore lots of simulations are required to see *any* advantage to playing out a ko. s. On Sun, Mar 2, 2008 at 3:17 PM, ivan dubois [EMAIL PROTECTED] wrote: Mogo is already very strong at endgame and certainly plays perfectly near the end of the game. The more advanced the program, the sooner it can play perfect endgame. But correct ko threats playing has nothing to do with the playout part : Since it is a strategic concept that involves global understanting, It is handled by the UCT tree part. - Message d'origine De : steve uurtamo [EMAIL PROTECTED] À : computer-go computer-go@computer-go.org Envoyé le : Dimanche, 2 Mars 2008, 20h25mn 33s Objet : Re: [computer-go] Re: Should 9x9 komi be 8.0 ?] a few subtleties -- it's possible for a machine to play a perfect endgame, and my guess is that machines will play perfect endgames before people do, although most pros are excellent at the endgame. counting ko threats and utilizing kos effectively is tricky in playouts -- kos can naturally extend a playout very, very far beyond where the actual advantage would be taken in a non-ko situation, and the likelihood of getting this far often enough in playouts to see the advantage is going to be difficult for machines without a lot of domain-specific knowledge. different humans are often good at different stages of the game, and making up a few points in the endgame, or getting a massive lead in the beginning of the game may be possible, convincing a computer player of something that isn't true -- either that it's nearly guaranteed to win, or nearly guaranteed to lose. all that having been said, i'm quite impressed with how well these programs are doing. s. ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/ _ Ne gardez plus qu'une seule adresse mail ! Copiez vos mails vers Yahoo! Mail http://mail.yahoo.fr ___ 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: Re : endgame (Was [computer-go] Re: Should 9x9 komi be 8.0 ?])
the issue with ko is the order in which the ko threats are played, which can only be successfully evaluated if the average playout finishes the ko correctly. s. On Sun, Mar 2, 2008 at 4:56 PM, ivan dubois [EMAIL PROTECTED] wrote: Ok, I think I see what you mean, but I am not sure I really agree. As you say, this is related to horizon effect. I think current MC programs can play ko quite well because they are trying do delay the outcome of losing the ko, therefore they tend to play threats do gain time, just like human players do. I dont think it is essential that the ko be resolved inside the tree part. And I dont believe there exist efficient way to handle ko in the playout other than just fordiding simple ko recapture. Ivan - Message d'origine De : Jonas Kahn [EMAIL PROTECTED] À : computer-go computer-go@computer-go.org Envoyé le : Dimanche, 2 Mars 2008, 21h32mn 43s Objet : Re: endgame (Was [computer-go] Re: Should 9x9 komi be 8.0 ?]) But correct ko threats playing has nothing to do with the playout part : Since it is a strategic concept that involves global understanting, It is handled by the UCT tree part. Yes and no. Theoretically, that's the work of the UCT part. But, as Steve pointed out, kos can go on for long. I don't know what depth is attained in the tree (by the way, I would really like to know), but I doubt it is that long. Moreover, some kos must be kept for later. Hence, some basic understanding of kos in the playouts might be useful. That's merely a variation of the horizon effect. We could even imagine a situation where the UCT makes a threat that loses points in the only aim of having the ko past the horizon, where it would be 50-50 (for example) in the playout. Jonas ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/ _ Ne gardez plus qu'une seule adresse mail ! Copiez vos mails vers Yahoo! Mail http://mail.yahoo.fr ___ 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] Leela is now participating in the scalability study
examples: playing Mogo_13_06 vs Leela_05 K10 J10 D4 D6 D10 C9 K4 K9 J9 K11 L10 H9 J8 H8 H10 J11 G7 H7 E6 F6 E7 E5 D5 C7 H6 D9 J7 F5 E9 G10 G6 J6 K6 J5 G8 G9 K7 F8 F7 E8 G5 F3 F4 D7 F9 D8 L11 E10 G3 E3 E4 C3 D3 D2 F2 E2 G2 L12 B4 B3 M12 C4 C5 B5 K12 J12 K13 J13 L13 M13 L12 A4 E1 F1 G1 H2 M2 M3 L2 N2 L3 M1 K5 C6 M6 C2 H3 G11 H5 H4 J4 L4 M4 K2 J2 K3 L5 J1 H1 D11 E11 C10 B6 B8 A7 A8 A6 F11 L9 L8 K8 N3 N4 M7 N7 M8 M9 N9 N10 M11 N11 N12 M10 L1 N1 B+Resign playing Mogo_13_07 vs Leela_10 K10 H10 D4 G4 K4 K8 D10 E9 J9 D9 J7 K6 G5 F5 F6 E5 D5 E6 H5 J8 H8 H9 K7 H7 G8 L7 J6 K9 L10 J10 L6 D6 B6 C6 C5 B7 G7 E10 J12 J11 K11 H12 K12 M6 L8 L5 L9 L3 G11 G12 G9 G10 B5 E3 L2 K3 M3 L4 K2 H4 J9 C3 J3 J4 D3 D2 B9 B2 F10 E11 B8 C7 C11 C10 B10 C12 B12 D11 B11 A7 J5 K5 F4 E4 H2 H11 F3 M8 F11 F12 M7 N7 F9 E8 E12 D12 N5 M9 M5 M4 N4 M2 N2 F2 G3 G2 H3 N3 E7 N6 D7 C8 C13 D8 H13 H1 D13 B13 K4 E13 A8 F7 G6 A12 A6 M10 M1 N1 L1 J2 J1 M12 G13 L12 N12 L11 N11 N10 M13 L13 M11 N13 C9 G1 A2 C2 B1 A3 B4 A10 D10 C13 C1 E1 B3 F13 J13 N2 A9 C10 A11 A10 K13 K8 K9 J8 H13 J13 B8 B9 A4 A8 A3 J4 B11 G13 A11 B12 B10 C11 H4 K4 F8 E7 L10 K12 L9 N11 J2 K9 K10 L8 C4 K11 D1 E2 B11 B10 N5 M5 L10 L9 H6 K10 N9 N8 A1 A5 A4 B4 B5 A3 B1 B6 C1 D1 D5 C5 D3 D4 A2 A1 B1 A2 PASS C1 PASS N4 PASS A11 PASS pass W+108.5 s. ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
Re: [computer-go] Leela is now participating in the scalability study
We should be careful about any conclusions ... your pairing algorithm currently creates leela-vs-leela games only. after 1500 or so games per leela, we should be able to tell. i'm getting some leela vs. mogo games already... s. ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
Re: [computer-go] Scalability study suggestion
i agree with everything except for the seeding. it takes very few games
(especially with the distribution you suggest) to get somewhat near the
right spot. with 500-ish games being played per player, the initial time
to get into the right place isn't unreasonable.
keep in mind that if you totally outmatch someone, likely the time they
spend thinking will be peanuts compared to you, because we're looking
at doublings. so those initial where do i roughly belong games will go
relatively quickly.
another way of thinking about this is that if you use a uniform prior,
the convergence to the actual value isn't much slower than if you
use a (potentially biased) prior. fat14, mogos 17, 18, big16 and potentially
big18 might have all been seeded too high this way, and they're the
ones we want the most accurate numbers on at this point.
s.
- Original Message
From: Chuck Paulson [EMAIL PROTECTED]
To: computer-go computer-go@computer-go.org
Sent: Saturday, February 2, 2008 1:02:15 PM
Subject: [computer-go] Scalability study suggestion
!--
/* Style Definitions */
p.MsoNormal, li.MsoNormal, div.MsoNormal
{margin:0in;margin-bottom:.0001pt;font-size:12.0pt;font-family:Times
New Roman;}
a:link, span.MsoHyperlink
{color:blue;text-decoration:underline;}
a:visited, span.MsoHyperlinkFollowed
{color:purple;text-decoration:underline;}
span.EmailStyle17
{font-family:Arial;color:windowtext;}
_filtered {margin:1.0in 1.25in 1.0in 1.25in;}
div.Section1
{}
--
I have been following the scaling study closely. Thanks for everyone
for gathering such interesting data and especially to Don and the people
donating computers.
I have 2 suggestions that could help increase the amount of information
gathered from all the CPU hours being used to play these games. The first
suggestion is about changing the algorithm used to pair players together, and
the second is about “seeding” players to an appropriate starting
position.
Suppose we have two players A and B who each have about a 50% chance of
winning when they play each other. We expect to gain about 0.5*log2(0.5) +
0.5*log2(0.5) = 1 bit of information from every game they play. On the other
hand, if player A has a 95% chance of beating player B we get about
0.95*log2(0.95) + 0.05*log2(0.05) = about 0.29 bits of information when they
play each other. Therefore, the more often you are playing nearly equal players,
the more information is gained.
Now suppose we have a list of players ranked 0 to N, where the lower
the ranking, the stronger the player. Assume that player n takes twice as long
to play a game as player n+1 for any n. Also assume that the Elo difference
between player n and player n+1 is 80 points, and that the cost of player 0
playing a game is 1.0 time units. These assumptions seem reasonable for the
upper levels of the study if we only consider the Mogo programs up to Mogo_16
(the ones that have about 500 games). Using these assumptions we can build the
following table.
RankCost WinProb Bits Bits/Cost
0 2. 0.5000 1. 0.5000
1 1.5000 0.3869 0.9627 0.6418
2 1.2500 0.2847 0.8618 0.6895
3 1.1250 0.2008 0.7234 0.6431
4 1.0625 0.1368 0.5758 0.5419
5 1.0313 0.0909 0.4395 0.4262
6 1.0156 0.0594 0.3249 0.3199
7 1.0078 0.0383 0.2344 0.2326
8 1.0039 0.0245 0.1660 0.1654
9 1.0020 0.0156 0.1160 0.1157
101.0010 0.0099 0.0801 0.0801
For example, if player 0 plays player1 then the total cost is 1.5
because player 0 takes 1 unit of time and player 1 takes 0.5 (half of player 0
time) for a total cost of 1.5 units of time. The Elo difference is 80, so using
the formula P = 1 / (1 + 10^(80/400)) = 0.3869 we see that player 1 has about a
39% change of winning. The bits of information we expect to get are
0.3869*log2(0.3869) + (1 – 0.3869)*log2(1 – 0.3869) = 0.9627. The
Bits/Cost is 0.9627/1.5 = 0.6418. The table shows the results of player 0
playing all players ranked 0 to 10 ranks lower. If player 0 plays himself the
cost is 2.0, the probability of a win is 50%, resulting in 1 bit of information
and the Bits/Cost is 0.5.
From the table, to maximize the information gain per unit of time, the
best games are played between players that are 2 ranks apart. That has to be
balanced against having a wide variety of games to get robust rankings.
I believe the current method is to pick 3 random opponents
Re: [computer-go] 19x19 Study - prior in bayeselo, and KGS study
I would agree at 100% if it wasn't for the known limitations: Nakade, not filling own eyes, etc. Because the program is blind to them it is blind in both senses: it does not consider those moves when defending, but it does not consider them when attacking either. this is well said. one problem with testing this is that there aren't a lot of good examples of programs that can scale as easily but which are known to not have these disadvantages. it's not an issue of time, really -- anything that can scale as well as mogo would have been worth testing, even if it took 2x as long to run, simply because it'd be nice for mogo to have some alternate competition. and if it really did avoid these particular faults (nakade in the corner, not filling own eyes, correct seki knowledge, etc.), it'd be interesting to see when the two programs crossed over, i.e. at what ELO one started to dominate the other. that would give a rough idea about the strength you'd need to be in order to take advantage of these flaws. my guess is that anyone at the 1k level can generate these situations with some regularity on a 9x9 board, and even more easily on a bigger board. making them game-altering, however, might take a much stronger player, or a much bigger board. i don't mean because bigger boards are harder for programs to read, i literally mean simply because there is more room on the board. s. Never miss a thing. Make Yahoo your home page. http://www.yahoo.com/r/hs ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
Re: [computer-go] More generic GTP
But if ever there's new version of GTP in the making I would suggest replacing the 'komi' and 'board_size' commands by a more general 'set property- name property-value' command and turn the Go Text Protocol more into a Game Text Protocol. okay, this feels a bit trollish, but i can't help myself. especially if you don't intend to write code for any other games... why would people want to modify the go text protocol to be game independent to help your code look cleaner? s. Be a better friend, newshound, and know-it-all with Yahoo! Mobile. Try it now. http://mobile.yahoo.com/;_ylt=Ahu06i62sR8HDtDypao8Wcj9tAcJ ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
Re: [computer-go] More generic GTP
you should rename the protocol TP then. s. - Original Message From: Mark Boon [EMAIL PROTECTED] To: computer-go computer-go@computer-go.org Sent: Wednesday, January 30, 2008 11:47:32 AM Subject: Re: [computer-go] More generic GTP I didn't say there was a big difference. It's simply a matter of elegance, if none of the commands are game-specific a large part of the protocol implementation can be abstracted. I suppose beauty is in the eye of the beholder. On 30-jan-08, at 14:23, Heikki Levanto wrote: On Wed, Jan 30, 2008 at 01:15:39PM -0200, Mark Boon wrote: There's one bit that so far thwarts my effort to obtain maximum modularization. And that is I have a GoEngine interface that is kind of mirroring GTP, since GTP is the preferred communication method between Go-playing engines. My design could be a lot cleaner however if this could be a GameEngine. What stands in the way of this are the commands that are really Go specific like 'komi' and in a lesser way 'board_size' that are part of the 'required' section of GTP. Sorry, I don't see any big difference between having a mandated game-specific command, and having a general set-parameter command with a mandated game-specific parameter name. Sooner or later you need to get down from the fancy abstractions and actually declare that it is go you are playing! And with that comes a number of specific needs you have to support. - 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/ Looking for last minute shopping deals? Find them fast with Yahoo! Search. http://tools.search.yahoo.com/newsearch/category.php?category=shopping___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
Re: [computer-go] 19x19 Study
it is a good thing to make your prior knowledge completely fair (in the sense of not having any bias) when doing bayesian calculations. any estimator being used will reshape that knowledge on the fly. the idea is that your prior knowledge of the ELO ranking should be about the same for every single version of the program, and as you obtain evidence (i.e. wins and losses) between pairs of programs, you can get a more and more confident belief about the actual ELO. so they'll converge to the correct values, and should do so reasonably rapidly. i believe that bayeselo is using maximum likelihood as an estimator of the actual elo, and there are other estimators that can be used, but this whole approach seems much better than the usual elo rating scheme. note that if you have 10 games between a particular pair of players and, say, player A wins 7 games and player B wins 3 games, and you repeat for another 10 games and get that player A wins 7 games and player B wins 3 games, this is *different* (and more!) information than if i simply told you that player A won 14 out of 20 games against player B. even more information is given if i know who won which games and in what order. bayesian inference takes this into account, which is nice. s. - Original Message From: Don Dailey [EMAIL PROTECTED] To: computer-go computer-go@computer-go.org Sent: Tuesday, January 29, 2008 1:46:56 PM Subject: Re: [computer-go] 19x19 Study They seem under-rated to me also. Bayeselo pushes the ratings together because that is apparently a valid initial assumption. With enough games I believe that effect goes away. I could test that theory with some work.Unless there is a way to turn that off in bayelo (I don't see it) I could rate them with my own program. Perhaps I will do that test. - Don Sylvain Gelly wrote: but not linearly and you can see a nice gradual curve in the plot. Now we have something we can argue about for weeks. Why is it not mostly linear? Could it be the memory issue I just mentioned? Hi Don and all participants to that study, that is very interesting! The memory constrains are certainly a valid hypothesis, especially the default settings of the release are rather conservative on that side, because it seemed better to have a weaker player than begin to make the player's machine swapping... Those settings are rather fitting your memory constrains as well, so it is fine. Reading your email and looking at the curve, I wonder if one possible explanation could be an artifact on how the ratings are computed? My question is: what curve would we see for that study if the involved players were exactly linearly scalable? That seems silly, but I wondered if there were an underestimating of higher levels, because of the way the bayeselo works. I am also looking at the curve after the 5-6th level (~gnugo), as behavior may be different for very low levels. I don't know if my hypothesis makes sense. Sylvain ___ 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/ Be a better friend, newshound, and know-it-all with Yahoo! Mobile. Try it now. http://mobile.yahoo.com/;_ylt=Ahu06i62sR8HDtDypao8Wcj9tAcJ ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
Re: [computer-go] 19x19 Study
But that's not relevant for this study. All that matters is the 14 out of 20 total score and the order should not matter one little bit. With players that change, that is very relevant however. lemme think that over. by the way, attached is what a quadratic fit looks like to the maximum ELO for the first 16 mogos, taken at the top end of 2 standard deviations from their current values. it peaks at around 17.8 doublings, if my arithmetic is right. s. Looking for last minute shopping deals? Find them fast with Yahoo! Search. http://tools.search.yahoo.com/newsearch/category.php?category=shoppingattachment: quadfit.jpg___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
Re: [computer-go] 19x19 Study
sorry, of course you're right -- linearity of expectation, after all. the total number of games is relevant for the std. dev., though. which has settled down for everyone but the new guys to a quite respectably small number of elo points. s. - Original Message From: Don Dailey [EMAIL PROTECTED] To: computer-go computer-go@computer-go.org Sent: Tuesday, January 29, 2008 2:18:30 PM Subject: Re: [computer-go] 19x19 Study steve uurtamo wrote: it is a good thing to make your prior knowledge completely fair (in the sense of not having any bias) when doing bayesian calculations. any estimator being used will reshape that knowledge on the fly. the idea is that your prior knowledge of the ELO ranking should be about the same for every single version of the program, and as you obtain evidence (i.e. wins and losses) between pairs of programs, you can get a more and more confident belief about the actual ELO. so they'll converge to the correct values, and should do so reasonably rapidly. i believe that bayeselo is using maximum likelihood as an estimator of the actual elo, and there are other estimators that can be used, but this whole approach seems much better than the usual elo rating scheme. note that if you have 10 games between a particular pair of players and, say, player A wins 7 games and player B wins 3 games, and you repeat for another 10 games and get that player A wins 7 games and player B wins 3 games, this is *different* (and more!) information than if i simply told you that player A won 14 out of 20 games against player B. even more information is given if i know who won which games and in what order. bayesian inference takes this into account, which is nice. But that's not relevant for this study. All that matters is the 14 out of 20 total score and the order should not matter one little bit. With players that change, that is very relevant however. - Don s. - Original Message From: Don Dailey [EMAIL PROTECTED] To: computer-go computer-go@computer-go.org Sent: Tuesday, January 29, 2008 1:46:56 PM Subject: Re: [computer-go] 19x19 Study They seem under-rated to me also. Bayeselo pushes the ratings together because that is apparently a valid initial assumption. With enough games I believe that effect goes away. I could test that theory with some work.Unless there is a way to turn that off in bayelo (I don't see it) I could rate them with my own program. Perhaps I will do that test. - Don Sylvain Gelly wrote: but not linearly and you can see a nice gradual curve in the plot. Now we have something we can argue about for weeks. Why is it not mostly linear? Could it be the memory issue I just mentioned? Hi Don and all participants to that study, that is very interesting! The memory constrains are certainly a valid hypothesis, especially the default settings of the release are rather conservative on that side, because it seemed better to have a weaker player than begin to make the player's machine swapping... Those settings are rather fitting your memory constrains as well, so it is fine. Reading your email and looking at the curve, I wonder if one possible explanation could be an artifact on how the ratings are computed? My question is: what curve would we see for that study if the involved players were exactly linearly scalable? That seems silly, but I wondered if there were an underestimating of higher levels, because of the way the bayeselo works. I am also looking at the curve after the 5-6th level (~gnugo), as behavior may be different for very low levels. I don't know if my hypothesis makes sense. Sylvain ___ 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/ Be a better friend, newshound, and know-it-all with Yahoo! Mobile. Try it now. http://mobile.yahoo.com/;_ylt=Ahu06i62sR8HDtDypao8Wcj9tAcJ ___ 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/ Never miss a thing. Make Yahoo your home page. http://www.yahoo.com/r/hs
Re: [computer-go] 19x19 MC improvement
i recommend: http://www.research.att.com/~njas/gosset/index.html s. - Original Message From: [EMAIL PROTECTED] [EMAIL PROTECTED] To: computer-go computer-go@computer-go.org Sent: Saturday, January 26, 2008 2:35:01 PM Subject: Re: [computer-go] 19x19 MC improvement Eric Boesch This is probably massive overkill, but one of the most successful techniques for multi-parameter optimization is Taguchi methods. http://en.wikipedia.org/wiki/Taguchi_methods However, in my experience, starting with the decisions that make the biggest difference, and then adding in the next-biggest decision, and so on, usually gets close enough to optimal. In my cgbg performance tests, most reasonable decisions affect total program performance by a factor of 2 at most, which translates to 1 rank at most. Likewise, I doubt that tweaking of existing MC parameters will bring more than 1 rank. Further improvement will require new ideas. Michael Wing By the way, does anybody know of any nifty tools or heuristics for efficient probabilistic multi-parameter optimization? In other words, like multi-dimensional optimization, except instead of your function returning a deterministic value, it returns the result of a Bernoulli trial, and the heuristic uses those trial results to converge as rapidly as possible to parameter values that roughly maximize the success probability. The obvious approach is to cycle through all dimensions in sequence, treating it as a one-dimensional optimization problem -- though the best way to optimize in one dimension isn't obvious to me either -- but just as with the deterministic version of optimization, I assume it's possible to do better than that. It might be fun problem to play with, but if good tools already exist then it wouldn't be very productive for me to waste time reinventing the broken wheel. ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/ Looking for last minute shopping deals? Find them fast with Yahoo! Search. http://tools.search.yahoo.com/newsearch/category.php?category=shopping ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
Re: [computer-go] Re: Scalbility study: low end
it's a natural tendency to look for patterns in data as soon as you have any data at all. some of these patterns i'd be willing to bet will hold up over time -- but the bayesian in me would say that is simply because they have further given evidence for my prior beliefs. requiring everyone to stay out of everyone else's first standard deviation will take quite a few more trials, and probably won't change the order of the existing mogos 1-12, for instance. if you were to plot these datapoints with their 1st or 2nd std. dev. errorbars and look at the possible set of curves that you could fit through them, though, it'd give quite a funny story, i'd agree. :) 95% confidence is a bit misleading and overrated, in my opinion. s. - Original Message From: Hideki Kato [EMAIL PROTECTED] To: computer-go computer-go@computer-go.org Sent: Thursday, January 24, 2008 8:34:42 AM Subject: [computer-go] Re: Scalbility study: low end Heikki, The numbers of games are about 200 and their ratings' standard deviations (right of Elo) are 70 to 100, right now. To get 95% of reliability, you have to double them. Don't you think it's too early to conclude any? -Hideki Heikki Levanto: [EMAIL PROTECTED]: Everyone is looking at the top end of the scalability study http://cgos.boardspace.net/study/ But what happens in the low end? Both programs show linear progress to begin with, then a corner, and more (almost?) linear development. Fatman's curve has a clear break at 3 doublings, when it suddenly starts to improve much slower than before. This goes on until 12 doublings, after which we get the mysterious decline. Mogo's curve is pretty well linear to 4 doublings, after that there is more variation (I suppose random), but the overall scope is clearly not what it was below 4. It is possible that both programs have a subtle bug that starts to disturb results around this point, but I find it quite unlikely. The breaks happe at 1350 - 1550 ELO points. Isn't that about the level where plain MC stops improving with more playouts? Would be fun to see if we could isolate the playout parts of those programs, and let them play pure MC. My guess is that they would end up around this level. Could it be that there are other limiting factors higher up? Perhaps Fatman is hitting the next one around 12 doublings, and Mogo will follow at 14 or 15... We will see that in a few days, when the new Mogos join the study and start producing results. - Heikki -- [EMAIL PROTECTED] (Kato) ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/ Looking for last minute shopping deals? Find them fast with Yahoo! Search. http://tools.search.yahoo.com/newsearch/category.php?category=shopping ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
