Re: [computer-go] OT: XML [was fairly OT: Language]
[XML] is like going backwards to the 60ies (OK, there are some thing XML is good for -- is't developed as HTML successor and in this area XML has quite some advantages; in some cases it's also good as intermediate data exchange format, but not always; as an primary format to save data in most cases it's one of the worst choices... IMHO). I'm also quite firmly not in the XML-for-everything camp (*) but have you considered the business reason: why bother with both a primary data format and an intermediate data exchange format; there may as well be just one format. Optimize later. Darren *: The first thing I do with most XML files that I need to do anything serious with is turn them into a csv file (unless the data is genuinely hierarchical, and collapsing it is unreasonable, but that is rare) ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
Re: [computer-go] OT: XML [was fairly OT: Language]
You could use YAML/JSON to keep all information without all XML overhead.. *: The first thing I do with most XML files that I need to do anything serious with is turn them into a csv file (unless the data is genuinely hierarchical, and collapsing it is unreasonable, but that is rare) ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
Re: [computer-go] Solving Go
If black plays first move on corner, white wins by 9 points. Hmm does white also capture that first stone and win 10 points. I am fixing search algorithm, which was little faulty as not done small board investigations for some time. So if there is list for right scores in different rule sets for small boards(2-5) in different first moves available in net like to see that. t. hArri - Original Message - From: Don Dailey [EMAIL PROTECTED] To: computer-go computer-go@computer-go.org Sent: Monday, November 12, 2007 8:39 PM Subject: Re: [computer-go] Solving Go Ok, on 2x2 I get a consistent result now that I implemented PSK. It gives the same result with SSK too. It's a 1 point win for the first player. I'm not sure this is in agreement with other peoples findings. But it appears to be consistent.I can work my way through the game and it always returns the same score if I make the move(s) the search believes is best. After black plays the first move, white's best response is to move to the opposite corner.Otherwise it's a 4 point win for black. Here are the parameters I use: 1. positional superko unless otherwise stated. 2. evaluation function: Each stone is alive - an empty point belongs to a player if only his stones touch it. 3. game over after 2 passes. 4. suicide illegal. 3x3 gives a black win by 9 points (the whole board.) If black plays first move on the edge (a2 for instance) then he wins by 3 points instead of 9. If black plays first move on corner, white wins by 9 points. Does anyone have any data to check these facts ?? It may try this with 4x4 after doing something to improve the move ordering. - Don Harri Salakoski wrote: 5x5 was solved with a massive brute force search approach. Memory was used for large hash tables and endgames were scored early using Bensons algorithm, otherwise it would not have been feasible from what I understand. Yes it was proof level paper, doing something lot less mathematically valid for example only some open source code which can do good search against 7*7 is more realistic. Kind of allowing all possible short-cuts, like using several patterns to judge board score even it is not absolutely sure that score is right for combination of patterns. Although that's interesting, it's just a search. I would like to try something a little more clever (I'm just not clever enough to figure out what that should be!) I'm thinking perhaps in terms of a database assist. It would be interesting if we could come up with a small board scoring system that is very accurate. Agree that goal, scoring system must be accurate _when_ it thinks it knows score. I see score meaning minimal score for player archieves from this position if plays right. A database system might identify rules and exceptions that can be applied. For example, we have the eye rule in our monte carlo programs - although that is extremely powerful it's not 100% admissible - there are some exceptions although they probably occur only a fraction of a percent of the time. The eye rule would be powerful in a hybrid system because it is a fairly large class of positions where we can say, never move to that point - it will never be the best move. But is this other class of used patterns also to guide search, I see this estimator goal should proof minmum scores for player. All kind of eye knowledge is offcourse important for minimal scoring patterns. A trivial way to include it in a hybrid system is to just put an entry in a table for the few times that is wrong. Or even better, try to determine the exact context where it's wrong.Perhaps it's never wrong in a 5x5 game? I have thinked patterns which take area of board and proof that another player can take X points from that area/group. If that player has benson alive groups in other areas on board score can be proven benson alive groups + one group which is not benson alive but can be proven to get X points if only defending that group for rest of game. Tables like this can be stored compactly with bloom filters. Here is a question. How do you determine what a final board looks like? If you are actually building an endgame table, you start with all the final positions. But seki seems to be very difficult to identify. I am planning partial table patterns. Seki and other consepts should be used with patterns if possible. I'm doing a little experiment right now with small boards and a table with a few million hashed entries. I'm trying to store only perfect scores in this table but my definition is weak.I search a position using alpha/beta and if several iterations consecutively return the same score, I consider it a perfect score. I know this definition is subject to error. Yep, such practical problems are intresting, but atleast those are possible to fix as 5*5 and earlier proofs show. It can be intresting attack 7*7 from end positions side, trying
Re: [computer-go] Language
Don Dailey wrote: My Go program doesn't use any libraries except the standard C libraries. I agree at 99.9% !! The only exception in my case is SFMT. http://www.math.sci.hiroshima-u.ac.jp/~m-mat/MT/SFMT/index.html SFMT is 100% clean C software, easy to compile, easy to use and free. A good RNG makes a huge difference. We all called his software buzzword compliant because he admitted that he wanted to try out several new technologies. Ha, ha. These guys exist in all latitudes. I've met a few ;-) Jacques. ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
Re: [computer-go] Language
On Tue, Nov 13, 2007 at 11:57:30PM +0100, Benjamin Teuber wrote: On Nov 13, 2007 10:18 PM, Nick Apperson [EMAIL PROTECTED] wrote: With the next generation of C++ with variadic templates I think C++ may overtake Lisp for metaprogramming, but I don't know enough to really make that claim. I don't know about variadic templates, but in general it is almost impossible to overtake Lisp in terms of metaprogramming, because every time a new cool programming technique is invented, some guy will implement this in 10-50 lines of Lisp code and voila - Lisp now has it, too =) There is a considerable amount of truth in that. Usually someone has to see it to believe how CL is flexible enough to support things like hand-rolling things like your own object system, only Forth in my experience brings the same you can do *that* too?! level of surprise. Still, though, sometimes useful things resist elegant implementation in CL. For example: * I doubt CL can be customized to support a thread library nearly as gracefully as languages designed around threading from the ground up. * For complicated code where a very expressive static type system for higher order functions is a good fit (like the SML code in Umut Acar's thesis) CL is still typesafe, but the way CL postpones much of the error detection to runtime can be a significant source of friction (and loss of expressiveness, as code doesn't say as clearly what it is doing). (I'd much rather translate that SML library into CL than into C++, though, though I admit I know very little about Boost except that it's designed to help with that sort of thing.) * I don't know any way of expressing functors in CL that's as nice as languages which have them built in. Also, to the considerable extent that that is true, note that it carries a sting in its tail. CL is so insanely flexible because fundamentally a CL program is not a declarative blueprint of the finished program, but an imperative recipe for building the finished program: a CL program is not as much like a C program as it is like a software package which can include C programs which write other C programs (e.g., software packages like lex or yacc or the old cfront). So you can express anything, but your program analysis tools (debuggers, profilers, code coverage tools, profilers, automatic refactoring tools...) may be hard-pressed to keep up in an understandable and/or reliable way, for pretty fundamental reasons. -- William Harold Newman [EMAIL PROTECTED] PGP key fingerprint 85 CE 1C BA 79 8D 51 8C B9 25 FB EE E0 C3 E5 7C Ubi saeva indignatio ulterius cor lacerare nequit. -- Jonathan Swift's epitaph ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
Re: [computer-go] Language
I don't have any problems with libraries, just ones that are gratuitously introduced for no good reason. I'm the first one to use a needed library. Also, now that I think about it, I do use Mersenne Twister - I just forgot about it because this was a late addition to my program. I will look at the SIMD version - just using the non-SIMD version was a big speedup over the standard library rand() function. - Don Jacques Basaldúa wrote: Don Dailey wrote: My Go program doesn't use any libraries except the standard C libraries. I agree at 99.9% !! The only exception in my case is SFMT. http://www.math.sci.hiroshima-u.ac.jp/~m-mat/MT/SFMT/index.html SFMT is 100% clean C software, easy to compile, easy to use and free. A good RNG makes a huge difference. We all called his software buzzword compliant because he admitted that he wanted to try out several new technologies. Ha, ha. These guys exist in all latitudes. I've met a few ;-) 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/
Re: [computer-go] Language
you guys are forgetting *all* about internationalization. i mean, do you really think that i can parse that xml if i don't even know what character set i'm supposed to be using? s. - Original Message From: Nick Apperson [EMAIL PROTECTED] To: computer-go computer-go@computer-go.org Sent: Tuesday, November 13, 2007 10:34:26 PM Subject: Re: [computer-go] Language hahaha one problem though... i can't easily determine the number of letters that are inside the parenthesis... maybe this is better: paren type:open/parenspace type=normal/spaceletter type=normal case=capitalX/letterletter type=normal case=capitalM/letterletter type=normal case=capitalL/letterspace type=normal/spaceparen type:close/paren That way there can be no confusion. I love XML, it is so easy. On Nov 13, 2007 6:12 PM, Andrés Domínguez [EMAIL PROTECTED] wrote: 2007/11/14, Don Dailey [EMAIL PROTECTED]: Good, I wouldn't want it without XML libraries. Is there any versions that use XML for writing code?I want to be able to use xml tags instead of parenthesis: paren /paren Then it will much more readable - which is one of the strengths of xml. I don't like XML tags without attributes: whileparen type:open/paren XML paren type:close/paren; Much more readable, and easy to parse. Andrés ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/ Be a better sports nut! Let your teams follow you with Yahoo Mobile. Try it now. http://mobile.yahoo.com/sports;_ylt=At9_qDKvtAbMuh1G1SQtBI7ntAcJ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
Re: [computer-go] Language
On 11/14/07, steve uurtamo [EMAIL PROTECTED] wrote: you guys are forgetting *all* about internationalization. i mean, do you really think that i can parse that xml if i don't even know what character set i'm supposed to be using? s. No need to worry. It's UTF-8 if you don't specify. Lars Nilsson - Original Message From: Nick Apperson [EMAIL PROTECTED] To: computer-go computer-go@computer-go.org Sent: Tuesday, November 13, 2007 10:34:26 PM Subject: Re: [computer-go] Language hahaha one problem though... i can't easily determine the number of letters that are inside the parenthesis... maybe this is better: paren type:open/parenspace type=normal/spaceletter type=normal case=capitalX/letterletter type=normal case=capitalM/letterletter type=normal case=capitalL/letterspace type=normal/spaceparen type:close/paren That way there can be no confusion. I love XML, it is so easy. On Nov 13, 2007 6:12 PM, Andrés Domínguez [EMAIL PROTECTED] wrote: 2007/11/14, Don Dailey [EMAIL PROTECTED]: Good, I wouldn't want it without XML libraries. Is there any versions that use XML for writing code?I want to be able to use xml tags instead of parenthesis: paren /paren Then it will much more readable - which is one of the strengths of xml. I don't like XML tags without attributes: whileparen type:open/paren XML paren type:close/paren; Much more readable, and easy to parse. Andrés ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/ Get easy, one-click access to your favorites. Make Yahoo! your homepage. ___ 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] Language
And it's not fast either. Free() has a reputation of being slow, and that's not surprising if you look at the way it is almost always implemented: scanning a list of addresses in order to amalgamate the newly freed memory with adjacent free areas. this is a burden for the OS, not a defect in the language. as far as the executing code is concerned, it's just releasing responsibility for the block attached to the pointer. the OS can merrily insertion sort it for all i care, but that's being handled elsewhere and isn't a function of the language. heck, the kernel could tell me that it's done within 2 microseconds and then give me an error on my next malloc because it isn't really done putting it back into place. but that's fine with me, because of the way that i use memory. i don't mind having to make friends with the OS. it follows pretty clearly-defined rules. i guess if i had some multithreaded request handler dealing with... no, i can't even imagine what i might desperately want garbage collection for. having garbage collection happen at random times would really, really make it difficult for me to profile. the reality is that the way i use memory, i know when i need it and when i need to get rid of it, and very frequently, once i've gotten all that i need, i don't need to ask for more for a really long time and can point to the exact place where i'm going to ditch it. i like knowing exactly how much memory i'm using, because i often need to use nearly all of it, for very long periods of time. how do i know how much i'm using? because everything has a very clearly defined size, and when i need more, i know that i can get it without placing an undue burden on the system (via going into swap). for me the strict typing of C means that i always know the maximal-size problem i can handle using whatever algorithm i've implemented. if i get desperate, i can pack bits. but i don't have to try to worry (or calculate) what the hell happens when i do a new(), or when some object is implicitly created or cast. sure, i could use an object-oriented language in the same way, but then i wouldn't really be using the language as its intended to be used (flexibly overloading operators, implicitly creating and casting objects from here to creation, then taking a breather from time to time to let the memory management catch up). My personal experience is: if you can tolerate the 5-10% loss in execution speed, a real garbage collector is invaluable. it sounds like you're working on more sophisticated code than i am, from the way that you describe using garbage collection. i'm just a speed junkie who needs to use all of my ram to do scientific computing and i don't mind counting all of my own beans. (in the real world i used perl, because development time is about 1/3 that of C. just don't try to calculate anything with it.) s. Be a better pen pal. Text or chat with friends inside Yahoo! Mail. See how. http://overview.mail.yahoo.com/ ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
Re: [computer-go] Language
whew. i need to switch out my ascii, then. s. - Original Message From: Lars Nilsson [EMAIL PROTECTED] To: computer-go computer-go@computer-go.org Sent: Wednesday, November 14, 2007 10:10:15 AM Subject: Re: [computer-go] Language On 11/14/07, steve uurtamo [EMAIL PROTECTED] wrote: you guys are forgetting *all* about internationalization. i mean, do you really think that i can parse that xml if i don't even know what character set i'm supposed to be using? s. No need to worry. It's UTF-8 if you don't specify. Lars Nilsson - Original Message From: Nick Apperson [EMAIL PROTECTED] To: computer-go computer-go@computer-go.org Sent: Tuesday, November 13, 2007 10:34:26 PM Subject: Re: [computer-go] Language hahaha one problem though... i can't easily determine the number of letters that are inside the parenthesis... maybe this is better: paren type:open/parenspace type=normal/spaceletter type=normal case=capitalX/letterletter type=normal case=capitalM/letterletter type=normal case=capitalL/letterspace type=normal/spaceparen type:close/paren That way there can be no confusion. I love XML, it is so easy. On Nov 13, 2007 6:12 PM, Andrés Domínguez [EMAIL PROTECTED] wrote: 2007/11/14, Don Dailey [EMAIL PROTECTED]: Good, I wouldn't want it without XML libraries. Is there any versions that use XML for writing code?I want to be able to use xml tags instead of parenthesis: paren /paren Then it will much more readable - which is one of the strengths of xml. I don't like XML tags without attributes: whileparen type:open/paren XML paren type:close/paren; Much more readable, and easy to parse. Andrés ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/ Get easy, one-click access to your favorites. Make Yahoo! your homepage. ___ 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 sports nut! Let your teams follow you with Yahoo Mobile. Try it now. http://mobile.yahoo.com/sports;_ylt=At9_qDKvtAbMuh1G1SQtBI7ntAcJ ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
Re: [computer-go] Language
On Nov 14, 2007 10:54 AM, steve uurtamo [EMAIL PROTECTED] wrote: I just wanted to point out that free() is not a system call. The heap is handled by the C library, and the OS is mostly not involved in it. my bad. thanks. :) in that case, i'm impressed that i can do 2GB allocations. Well, the process has some memory assigned to it, and the C library will ask for more when it runs out (most likely when you allocate 2GB), but most calls to malloc() won't result in a system call, and I don't think a call to free() ever results in a system call. The details of how more memory is acquired depend on the platform. You can get a very good idea of how all of this works by reading section 8.7 of The C programming language, by Kernighan and Ritchie. Álvaro. ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
Re: [computer-go] Language
On Nov 14, 2007 10:25 AM, steve uurtamo [EMAIL PROTECTED] wrote: And it's not fast either. Free() has a reputation of being slow, and that's not surprising if you look at the way it is almost always implemented: scanning a list of addresses in order to amalgamate the newly freed memory with adjacent free areas. this is a burden for the OS, not a defect in the language. as far as the executing code is concerned, it's just releasing responsibility for the block attached to the pointer. the OS can merrily insertion sort it for all i care, but that's being handled elsewhere and isn't a function of the language. heck, the kernel could tell me that it's done within 2 microseconds and then give me an error on my next malloc because it isn't really done putting it back into place. but that's fine with me, because of the way that i use memory. i don't mind having to make friends with the OS. it follows pretty clearly-defined rules. I just wanted to point out that free() is not a system call. The heap is handled by the C library, and the OS is mostly not involved in it. Anyway, go programmers should probably not be using a whole lot of dynamic memory allocation, and certainly not enough to make the performance of free() matter at all. Álvaro. ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
Re: [computer-go] Language
I just wanted to point out that free() is not a system call. The heap is handled by the C library, and the OS is mostly not involved in it. my bad. thanks. :) in that case, i'm impressed that i can do 2GB allocations. s. Get easy, one-click access to your favorites. Make Yahoo! your homepage. 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] Language
thanks. i loaned my copy out (having never read that section, i'm sad that this is the case) and will have to go score another. s. - Original Message From: Álvaro Begué [EMAIL PROTECTED] To: computer-go computer-go@computer-go.org Sent: Wednesday, November 14, 2007 11:04:41 AM Subject: Re: [computer-go] Language On Nov 14, 2007 10:54 AM, steve uurtamo [EMAIL PROTECTED] wrote: I just wanted to point out that free() is not a system call. The heap is handled by the C library, and the OS is mostly not involved in it. my bad. thanks. :) in that case, i'm impressed that i can do 2GB allocations. Well, the process has some memory assigned to it, and the C library will ask for more when it runs out (most likely when you allocate 2GB), but most calls to malloc() won't result in a system call, and I don't think a call to free() ever results in a system call. The details of how more memory is acquired depend on the platform. You can get a very good idea of how all of this works by reading section 8.7 of The C programming language, by Kernighan and Ritchie. Álvaro. 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] Language
On Wed, Nov 14, 2007 at 11:04:41AM -0500, Álvaro Begué wrote: On Nov 14, 2007 10:54 AM, steve uurtamo [EMAIL PROTECTED] wrote: I just wanted to point out that free() is not a system call. The heap is handled by the C library, and the OS is mostly not involved in it. my bad. thanks. :) in that case, i'm impressed that i can do 2GB allocations. Well, the process has some memory assigned to it, and the C library will ask for more when it runs out (most likely when you allocate 2GB), but most calls to malloc() won't result in a system call, and I don't think a call to free() ever results in a system call. The details of how more memory is acquired depend on the platform. You can get a very good idea of how all of this works by reading section 8.7 of The C programming language, by Kernighan and Ritchie. For example on Linux (and probably most other UNIX systems), there are two distinct syscalls that malloc() _might_ call to get memory from the OS: brk() - This increases data segment size of the program; whatever is put inside the data segment is managed by malloc() data structures and small allocations typically get a chunk from the data segment mmap() - This just asks the kernel for an arbitrarily-sized block of memory; you can slam your header on the block and then return it from malloc(). This is normally used only for large allocations (like 128kb up) since it rounds up the allocation to whole pages and making a syscall has quite an overhead (you need to brk() only rarely when the chunk does not fit in the already requested data segment anymore) Of course, this is heavily simplified. -- Petr Pasky Baudis We don't know who it was that discovered water, but we're pretty sure that it wasn't a fish. -- Marshall McLuhan ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
Re: [computer-go] Language
On Wed, 2007-11-14 at 07:25 -0800, steve uurtamo wrote: And it's not fast either. Free() has a reputation of being slow, and that's not surprising if you look at the way it is almost always implemented: scanning a list of addresses in order to amalgamate the newly freed memory with adjacent free areas. this is a burden for the OS, not a defect in the language. as far as the executing code is concerned, it's just releasing responsibility for the block attached to the pointer. the OS can merrily insertion sort it for all i care, but that's being handled elsewhere and isn't a function of the language. heck, the kernel could tell me that it's done within 2 microseconds and then give me an error on my next malloc because it isn't really done putting it back into place. but that's fine with me, because of the way that i use memory. i don't mind having to make friends with the OS. it follows pretty clearly-defined rules. No, sorry, this has nothing to do with the OS, but only with the implementation within the stdlib library. The kernel gets involved only when malloc() has exhausted its free list and is requesting another big block of memory via the brk() system call, which happens infrequently. So it *is* a function of (the implementation of) the language. having garbage collection happen at random times would really, really make it difficult for me to profile. the reality is that the way i use memory, i know when i need it and when i need to get rid of it, and very frequently, once i've gotten all that i need, i don't need to ask for more for a really long time and can point to the exact place where i'm going to ditch it. That's my point: Not all uses of memory follow the pattern you are describing. My personal experience is: if you can tolerate the 5-10% loss in execution speed, a real garbage collector is invaluable. it sounds like you're working on more sophisticated code than i am, from the way that you describe using garbage collection. i'm just a speed junkie who needs to use all of my ram to do scientific computing and i don't mind counting all of my own beans. The type of software I had in mind was an interactive system, running for days (or even months) without restarting, together with the possibility of creating function closures. I find it hard to imagine how you can do that without a garbage collector. I realized such a system in plain C, but I wrote my own garbage collector for it - I just saw no other way to determine when objects created by the user's processes could be freed. Hellwig ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
[computer-go] KGS: kgs-chat GTP command in games
Hi, is anyone successfully using the kgs-chat GTP command in games? I cannot get kgsGtp to send me the command when I make a comment inside a game (as the bot's opponent). I receive the command when I private-message the bot. Is there a special trick I need to do to enable this inside games as well? I have tried with 3.0.13 and 3.0.20. BTW, the in-game kgs-chat semantics is somewhat unclear. Specifically, how can I make my bot *ignore* some messages? Or does the part about sending talk string when I return error apply only to private messages? Thank you, -- Petr Pasky Baudis We don't know who it was that discovered water, but we're pretty sure that it wasn't a fish. -- Marshall McLuhan ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
Re: [computer-go] Speed of generating random playouts
On Tue, Nov 13, 2007 at 04:11:24PM -0500, Imran Hendley wrote:
I definitely understand the idea now, and it looks very good. However
this implementation could break:
Say we have pseudoliberties at intersections: 99,100,101. We sum those
up to get 300, divide by the number of pseudoliberties - 3, get back
100, check to see if 100 is a liberty, and since it is we conclude
that we have one liberty at intersection 100 that we counted three
times, and hence our string is in atari.
So we cant use numbers 1..81
Let elaborate a little more on this. We want one number for each cells :
nums = {n1, n2, n3, ..., n81}
And we want the following properties :
for any a, b in nums :
(a + b) / 2 is in nums -- a == b
for any a, b, c in nums :
(a + b + c) / 3 is in nums -- a == b == c
for any a, b, c, d in nums :
(a + b + c + d) / 4 is in nums -- a == b == c == d
If we have this we are sure to don't have problems like you pointed.
Using brute force search, I've produced the following sequence of
numbers :
[17, 18, 21, 30, 49, 86, 134, 274, 590, 1061, 1348, 2301, 3005, 4805,
7609, 11157, 17802, 19393, 29046, 31538, 41442, 49154, 74823, 97358,
134625, 148826, 217801, 234930, 294657, 402550, 452686, 610274,
726514, 885190, 1040877, 1070361, 1337862, 1611001, 1829345, 1962193,
2308061, 3007701, 3133837, 4007989, 4727218, 4883797, 5546029, 7454733,
8548661, 9547305, 11552366, 13177582, 13697142, 14689461, 15538838,
15733662, 21054617, 22691377, 24433197, 27274934, 31994414, 35217106,
37507258, 41114134, 45045090, 47089386, 57357330, 62400606, 68297193,
75036946, 83039110, 96477718, 110160994, 119390498, 122575210,
148912497, 156351446, 168096257, 176942297, 194310098, 211199842]
This sequence is not the best you can found, but it was quick to
generate...
But now we have another problem... We have the sum of the number of the
pseudo libertyes of a chain, and we can compute (sum / nb_plibs) but
next we have to check if the resulting number is in the list.
In some cases the number (sum / nb_plibs) will not be an integer so it
is trivialy not in nums, but for all the other cases this will require
log(81) operation using a binnary search.
Actually, when I need to check for atari on a group with 2,3,4 pseudo
liberties, I search a liberty of this group and check how mch plibs it
add to this group. I don't known if this will improve the speed but it
add a lot of complexity and atari-checking doesn't represent so much of
the calculations done by my engine to be valuable.
And the second problems is that this solution doesn't scale well. On
19x19 you need 361 numbers in your list, so even if you find a list like
this, I doubt that you can sum up the value of all the pseudo liberties
of a big group without overflowing an unsigned and you have to switch
to bigger int like int 64.
So I think John was suggesting something different in his first mail,
but I still search what it can be...
Does anyone have an idea ?
Tom
PS: I'm very sorry for my poor english
--
Thomas Lavergne Le vrai rêveur est celui qui rêve
de l'impossible. (Elsa Triolet)
[EMAIL PROTECTED] http://reveurs.org
___
computer-go mailing list
computer-go@computer-go.org
http://www.computer-go.org/mailman/listinfo/computer-go/
Re: [computer-go] KGS: kgs-chat GTP command in games
On Wed, 2007-11-14 at 19:27 +0100, Petr Baudis wrote: Hi, is anyone successfully using the kgs-chat GTP command in games? I cannot get kgsGtp to send me the command when I make a comment inside a game (as the bot's opponent). I receive the command when I private-message the bot. Is there a special trick I need to do to enable this inside games as well? I have tried with 3.0.13 and 3.0.20. 6-12 months ago, I played with this feature. At that time, it only worked with private messages. I guess that's still the case? BTW, the in-game kgs-chat semantics is somewhat unclear. Specifically, how can I make my bot *ignore* some messages? Or does the part about sending talk string when I return error apply only to private messages? I have no clue :( I'd just return an empty string and see what KGS does with it. ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
Re: [computer-go] Speed of generating random playouts
On Nov 14, 2007 1:44 PM, Lavergne Thomas [EMAIL PROTECTED] wrote:
Let elaborate a little more on this. We want one number for each cells :
nums = {n1, n2, n3, ..., n81}
And we want the following properties :
for any a, b in nums :
(a + b) / 2 is in nums -- a == b
for any a, b, c in nums :
(a + b + c) / 3 is in nums -- a == b == c
for any a, b, c, d in nums :
(a + b + c + d) / 4 is in nums -- a == b == c == d
If you want to make use of the pseudoliberty count, yes.
My solution doesn't make use of that, and satisfies the stronger property:
0 = a_i = 4 and sum a_i * n_i is in 1*nums union 2*nums union 3*nums
union 4*nums
= only one a_i is nonzero.
If we have this we are sure to don't have problems like you pointed.
Using brute force search, I've produced the following sequence of
numbers :
...
148912497, 156351446, 168096257, 176942297, 194310098, 211199842]
This sequence is not the best you can found, but it was quick to
generate...
indeed, it's possible with much smaller numbers.
But now we have another problem... We have the sum of the number of the
pseudo libertyes of a chain, and we can compute (sum / nb_plibs) but
next we have to check if the resulting number is in the list.
And the second problems is that this solution doesn't scale well. On
19x19 you need 361 numbers in your list, so even if you find a list like
this, I doubt that you can sum up the value of all the pseudo liberties
of a big group without overflowing an unsigned and you have to switch
to bigger int like int 64.
So I think John was suggesting something different in his first mail,
but I still search what it can be...
Does anyone have an idea ?
you might try to encode the x and y coordinate of a point separately...
regards,
-John
___
computer-go mailing list
computer-go@computer-go.org
http://www.computer-go.org/mailman/listinfo/computer-go/
Re: [computer-go] KGS: kgs-chat GTP command in games
Jason House wrote: On Wed, 2007-11-14 at 19:27 +0100, Petr Baudis wrote: Hi, is anyone successfully using the kgs-chat GTP command in games? I cannot get kgsGtp to send me the command when I make a comment inside a game (as the bot's opponent). I receive the command when I private-message the bot. Is there a special trick I need to do to enable this inside games as well? I have tried with 3.0.13 and 3.0.20. 6-12 months ago, I played with this feature. At that time, it only worked with private messages. I guess that's still the case? Note that this feature does not work during tournaments, as tournament players are not allowed to chat during their games. I am thinking about letting Crazy Stone write its analysis/comments/chat to a web site during the game, and give a link to that web site in the version string. This way, it could communicate better with spectators. Rémi ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
[computer-go] Chinese Computer Games Championship
I have now found what seems to be the results page of the Chinese Computer Games Championship, held in Chongqing in early October. It's at http://aigames.cn:8081/CCGCC/teamInfo.jsp It seems that Break won the 19x19 Go, and BitStronger won the 9x9. But there seem to be no scores listed, so it's possible that these aren't results tables. Nick -- Nick Wedd[EMAIL PROTECTED] ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
Re: [computer-go] Language
On Wed, 14 Nov 2007, Don Dailey wrote: Also, now that I think about it, I do use Mersenne Twister - I just forgot about it because this was a late addition to my program. I will look at the SIMD version - just using the non-SIMD version was a big speedup over the standard library rand() function. I do use MT too, but I don't consider it a library. It's 50 lines of additional source code inside one of my Go-program files. Christoph ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
Re: [computer-go] Language
On Wed, 14 Nov 2007, Hellwig Geisse wrote: The type of software I had in mind was an interactive system, running for days (or even months) without restarting, together with the possibility of creating function closures. I find it hard to imagine how you can do that without a garbage collector. I write (astronomical) instrument control software in C that runs for days (upto weeks). I call malloc() when I need memory and free() when the particular sub-task is done ... no problem. Christoph ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
Re: [computer-go] Speed of generating random playouts
On Nov 14, 2007 2:00 PM, John Tromp [EMAIL PROTECTED] wrote:
My solution doesn't make use of that, and satisfies the stronger property:
0 = a_i = 4 and sum a_i * n_i is in 1*nums union 2*nums union 3*nums
union 4*nums
= only one a_i is nonzero.
that was not quite correct. it should say:
let a_i be the number of adjacencies to a liberty at point i.
if sum a_i = 4, and sum (a_i * n_i) is in {1,2,3,4} * nums,
then only one a_i is nonzero.
regards,
-John
___
computer-go mailing list
computer-go@computer-go.org
http://www.computer-go.org/mailman/listinfo/computer-go/
Re: [computer-go] Language
I don't think of it as a library either, and technically it's not.I do compile those few lines of code and link them in separately. - Don Christoph Birk wrote: On Wed, 14 Nov 2007, Don Dailey wrote: Also, now that I think about it, I do use Mersenne Twister - I just forgot about it because this was a late addition to my program. I will look at the SIMD version - just using the non-SIMD version was a big speedup over the standard library rand() function. I do use MT too, but I don't consider it a library. It's 50 lines of additional source code inside one of my Go-program files. 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/
Re: [computer-go] Language
On Wed, 2007-11-14 at 12:30 -0800, Christoph Birk wrote: I write (astronomical) instrument control software in C that runs for days (upto weeks). I call malloc() when I need memory and free() when the particular sub-task is done ... no problem. Then you are a lucky guy... ;-) With closures you almost never know when exactly the task is done. They can float indefinitely within your system, they can get part of other data structures, and last but not least, they are cyclical in nature. *I* would have had many problems without garbage collection. But I will happily concede that these particular problems may play no roll at all in computer Go - except if you decide to program in a functional language. Then again, you won't do that without a good GC. Hellwig ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
Re: [computer-go] Language
On Wed, 14 Nov 2007, Hellwig Geisse wrote: On Wed, 2007-11-14 at 12:30 -0800, Christoph Birk wrote: I write (astronomical) instrument control software in C that runs for days (upto weeks). I call malloc() when I need memory and free() when the particular sub-task is done ... no problem. Then you are a lucky guy... ;-) With closures you almost never know when exactly the task is done. They can float indefinitely within your system, they can get part of other data structures, and last but not least, they are cyclical in nature. *I* would have had many problems without garbage collection. Looks like we are living in very different worlds. I had never even heard of 'closures' (I have never used a functional language and I just read up on them on Wikipedia :-) But I will happily concede that these particular problems may play no roll at all in computer Go - except if you decide to program in a functional language. Then again, you won't do that without a good GC. It appears that the question of GC is not dependent on the problem (eg. computer-Go) but on the language you use. Christoph ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
[computer-go] Re: Language
It appears that the question of GC is not dependent on the problem (eg. computer-Go) but on the language you use. This really gets back to the core of the language question. The kind of language you choose depends in part on the kind of program you intend to write. If you're writing a monte carlo with the simplest and fastest possible structure, then manual memory management is probably also not a handicap. If you're writing a stateful evaluator with lots of caches, lazy evaluation and a sophisticated search strategy, it can be VERY difficult to keep track of when a particular bit of data is no longer needed, and lack of GC is a major handicap. ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
Re: [computer-go] Language
On Wed, Nov 14, 2007 at 10:40:15AM -0500, Álvaro Begué wrote: Anyway, go programmers should probably not be using a whole lot of dynamic memory allocation, and certainly not enough to make the performance of free() matter at all. Doesn't that depend strongly on how a program works? For example, if you had a program which were really good at the endgame --- or, perhaps, just a program which deeply understood sente and gote as used in the middlegame, so that it could correctly cope with things like a play becoming double sente as the game progresses --- it'd be natural for it to manipulate expressions at least as complicated as combinatorial games, because we know that combinatorial games arise in the limit of exactly known position values. And good luck working with combinatorial games without heap allocation. If that seems implausible to you, very well, but the UCT approach didn't strike me as particularly plausible when I heard of it, either, and I find myself forced to remain openminded about what's going to turn out to be important in strong programs. -- William Harold Newman [EMAIL PROTECTED] PGP key fingerprint 85 CE 1C BA 79 8D 51 8C B9 25 FB EE E0 C3 E5 7C 'C'est la vie,' said the old folks, 'just goes to show you never can tell.' -- Chuck Berry ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
Re: [computer-go] Speed of generating random playouts
On Nov 14, 2007 3:19 PM, John Tromp [EMAIL PROTECTED] wrote:
On Nov 14, 2007 2:00 PM, John Tromp [EMAIL PROTECTED] wrote:
My solution doesn't make use of that, and satisfies the stronger property:
0 = a_i = 4 and sum a_i * n_i is in 1*nums union 2*nums union 3*nums
union 4*nums
= only one a_i is nonzero.
that was not quite correct. it should say:
let a_i be the number of adjacencies to a liberty at point i.
if sum a_i = 4, and sum (a_i * n_i) is in {1,2,3,4} * nums,
then only one a_i is nonzero.
I'm really lost now. a_i is the number of stones we have adjacent to a
liberty at intersection i? Do we need to know the location of our
liberties to update sum a_i? How is this easier than just remembering
the locations of all real liberties you saw? How do we know that the
stones around i are from the same group? What are the n_i in
sum(a_i*n_i)? is {1,2,3,4}*nums supposed to be a cartesian product of
two sets? Is this related to what you said about encoding x and y
separately?
___
computer-go mailing list
computer-go@computer-go.org
http://www.computer-go.org/mailman/listinfo/computer-go/
Re: [computer-go] Language
On Nov 14, 2007 4:58 PM, William Harold Newman [EMAIL PROTECTED] wrote: On Wed, Nov 14, 2007 at 10:40:15AM -0500, Álvaro Begué wrote: Anyway, go programmers should probably not be using a whole lot of dynamic memory allocation, and certainly not enough to make the performance of free() matter at all. Doesn't that depend strongly on how a program works? For example, if you had a program which were really good at the endgame --- or, perhaps, just a program which deeply understood sente and gote as used in the middlegame, so that it could correctly cope with things like a play becoming double sente as the game progresses --- it'd be natural for it to manipulate expressions at least as complicated as combinatorial games, because we know that combinatorial games arise in the limit of exactly known position values. And good luck working with combinatorial games without heap allocation. I bet you can work with combinatorial games without heap allocation, but it would take some smart tricks. To be honest, I was only thinking of the two more conventional approaches: alpha-beta search and UCT (and some unholy marriages of the two that I have in mind...). Álvaro. ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
Re: [computer-go] Speed of generating random playouts
On Nov 14, 2007 5:03 PM, Imran Hendley [EMAIL PROTECTED] wrote:
On Nov 14, 2007 3:19 PM, John Tromp [EMAIL PROTECTED] wrote:
On Nov 14, 2007 2:00 PM, John Tromp [EMAIL PROTECTED] wrote:
My solution doesn't make use of that, and satisfies the stronger property:
0 = a_i = 4 and sum a_i * n_i is in 1*nums union 2*nums union 3*nums
union 4*nums
= only one a_i is nonzero.
that was not quite correct. it should say:
let a_i be the number of adjacencies to a liberty at point i.
if sum a_i = 4, and sum (a_i * n_i) is in {1,2,3,4} * nums,
then only one a_i is nonzero.
I'm really lost now. a_i is the number of stones we have adjacent to a
liberty at intersection i? Do we need to know the location of our
liberties to update sum a_i? How is this easier than just remembering
For every string, you can keep track of this sum incrementally.
When the string establishes a new adjacency to an empty point i,
you add code[i] into the sum.
the locations of all real liberties you saw? How do we know that the
stones around i are from the same group? What are the n_i in
n_i was the name that Tom gave to my code[i].
sum(a_i*n_i)? is {1,2,3,4}*nums supposed to be a cartesian product of
no, it's just my shorthand for the union of the 4 sets nums, 2*nums,
3*nums and 4*nums.
regards,
-John
___
computer-go mailing list
computer-go@computer-go.org
http://www.computer-go.org/mailman/listinfo/computer-go/
Re: [computer-go] Language
perhaps this is an obvious statement... The best language depends on the way in which your program works. Having used C++ extensively, my program designs naturally fit easily into that language. I'm sure a lisp programmer would think of better solutions that would only work in lisp. As far as languages about restriction, well #$* those languages. I make sharper turns without training wheels thank you very much. On Nov 14, 2007 3:58 PM, William Harold Newman [EMAIL PROTECTED] wrote: On Wed, Nov 14, 2007 at 10:40:15AM -0500, Álvaro Begué wrote: Anyway, go programmers should probably not be using a whole lot of dynamic memory allocation, and certainly not enough to make the performance of free() matter at all. Doesn't that depend strongly on how a program works? For example, if you had a program which were really good at the endgame --- or, perhaps, just a program which deeply understood sente and gote as used in the middlegame, so that it could correctly cope with things like a play becoming double sente as the game progresses --- it'd be natural for it to manipulate expressions at least as complicated as combinatorial games, because we know that combinatorial games arise in the limit of exactly known position values. And good luck working with combinatorial games without heap allocation. If that seems implausible to you, very well, but the UCT approach didn't strike me as particularly plausible when I heard of it, either, and I find myself forced to remain openminded about what's going to turn out to be important in strong programs. -- William Harold Newman [EMAIL PROTECTED] PGP key fingerprint 85 CE 1C BA 79 8D 51 8C B9 25 FB EE E0 C3 E5 7C 'C'est la vie,' said the old folks, 'just goes to show you never can tell.' -- Chuck Berry ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/ ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
Re: [computer-go] Speed of generating random playouts
For every string, you can keep track of this sum incrementally.
When the string establishes a new adjacency to an empty point i,
you add code[i] into the sum.
OK that's what I thought before then I got really confused. And nums
is just U_all_i code[i], right?
if sum a_i = 4, and sum (a_i * n_i) is in {1,2,3,4} * nums,
then only one a_i is nonzero.
So a_i could be 2 and sum(a_i * n_i) could be in 4*nums (for example)
and this would mean that we are in atari? We are not only interested
in whether sum(a_i * n_i) is in sum(a_i) * nums?
___
computer-go mailing list
computer-go@computer-go.org
http://www.computer-go.org/mailman/listinfo/computer-go/
Re: [computer-go] Chinese Computer Games Championship
The tables are the list of the programs, not the results. I read Ping Yu's blog. He is a professional go player. His program should have won both on 19x19 and 9x9. Here is the link of his blog, again it is in Chinese. http://blog.csdn.net/Yoenix/archive/2007/10/10/1817821.aspx According to his blog, Professor Chen's program should have won, but Professor Chen's program was participating not for the prize. On Nov 14, 2007 2:53 PM, Nick Wedd [EMAIL PROTECTED] wrote: I have now found what seems to be the results page of the Chinese Computer Games Championship, held in Chongqing in early October. It's at http://aigames.cn:8081/CCGCC/teamInfo.jsp It seems that Break won the 19x19 Go, and BitStronger won the 9x9. But there seem to be no scores listed, so it's possible that these aren't results tables. Nick -- Nick Wedd[EMAIL PROTECTED] ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/ ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
Re: [computer-go] Speed of generating random playouts
Sorry, I didn't mean to send that one yet. I pressed tab, meaning to
print a tab character, and return soon after, which caused gmail to,
first, change the focus to the send button, and second, send the
mail. That last bit was supposed to be
if (code_sum 5 * threshold) {
int pseudoliberty_count = code_sum / threshold;
if (code_sum % pseudoliberty_count == 0) {
int average = code_sum / pseudoliberty_count;
if (average is in my original code_value set) then there is
just one liberty.
}
}
The if average is in my original code_value set seems like a
bottleneck here, requiring about #bits (i.e. about 9, since 361 is a
9-bit number) operations no matter how you do it as far as I can tell
(unless you use a stupidly gigantic lookup table), and there's a
solution to that, too, if you don't mind wasting a little more space.
Use base 8 instead of base 5. Unfortunately, then it is no longer
possible (without using a separate pseudoliberty count) to squeeze the
result into a 32-bit number and be sure that, for chains with 19
liberties, for example, you don't get overflow. But it does permit
using a bitmask to convert the in my original code_value set test to
constant-time:
if ((average 0b110110110110110110110110110) == 0) { then there
is just one liberty }
Here, 0bfoo is the binary number foo (yes, I know that's not
legitimate C code) and I'm supposing that #bits == 9. I hope I got
this right -- I'm sort of hurrying to correct it before anybody wasted
too much time trying to decode it. (Sorry, Jason :)
On 11/14/07, Eric Boesch [EMAIL PROTECTED] wrote:
Encode each number by swapping base 2 with base 5, without changing
the digits. So binary 11011 (27) is represented as base-5 11011 (756).
This allows you to sum up to 4 such numbers without experiencing
overflow from one digit to the next (since 4 1's adds up to just 4).
Essentially, you are performing b additions in parallel. If the
numbers you are summing are all the same, and the pseudoliberty count
(#libs) is no more than 4, then each base-5 digit of the sum will
equal 0 or #libs.
With a slight modification, you can also eliminate the pseudoliberty
count completely and just use a single number. Take the largest code
value you will need, add 1, multiply by four, round up to the next
power of 5, and add this value to every code value, and now you can
just use the test
___
computer-go mailing list
computer-go@computer-go.org
http://www.computer-go.org/mailman/listinfo/computer-go/
Re: [computer-go] Speed of generating random playouts
Encode each number by swapping base 2 with base 5, without changing
the digits. So binary 11011 (27) is represented as base-5 11011 (756).
This allows you to sum up to 4 such numbers without experiencing
overflow from one digit to the next (since 4 1's adds up to just 4).
Essentially, you are performing b additions in parallel. If the
numbers you are summing are all the same, and the pseudoliberty count
(#libs) is no more than 4, then each base-5 digit of the sum will
equal 0 or #libs.
With a slight modification, you can also eliminate the pseudoliberty
count completely and just use a single number. Take the largest code
value you will need, add 1, multiply by four, round up to the next
power of 5, and add this value to every code value, and now you can
just use the test
if (code_sum = threshold) {
((code_sum code_sum div threshold
! All you have to do is to add a sufficiently large fixed value to
every single representation.
Intersperse double-zeroes inside your input value, so binary 11011 is
encoded as 100101001. Now summing up to 7 such values is
guaranteed not to overflow one triad of bits to another, so
essentially you're performing b binary additions in parallel.
That's it. Divide the sum by
a little bit more than 3b bits. 3b bits seems to be very much
This could be made more compact, but then bitmasking wouldn't be as easy.
. Any coordinate is just a sequence of bits. Each bit can be encoded
separately. So the problem reduces to how to encode a single bit (0 or
1) so that the sum of up to 4 values equals a given number (say 0)
only if the bit is equal each time.
For bitmasking ease, you can use 3 bits per bit. Spread each input
number out like this: the
Up to 4 times 1 (mod 0) equals 0 only if
On 11/14/07, John Tromp [EMAIL PROTECTED] wrote:
On Nov 14, 2007 5:03 PM, Imran Hendley [EMAIL PROTECTED] wrote:
On Nov 14, 2007 3:19 PM, John Tromp [EMAIL PROTECTED] wrote:
On Nov 14, 2007 2:00 PM, John Tromp [EMAIL PROTECTED] wrote:
My solution doesn't make use of that, and satisfies the stronger
property:
0 = a_i = 4 and sum a_i * n_i is in 1*nums union 2*nums union 3*nums
union 4*nums
= only one a_i is nonzero.
that was not quite correct. it should say:
let a_i be the number of adjacencies to a liberty at point i.
if sum a_i = 4, and sum (a_i * n_i) is in {1,2,3,4} * nums,
then only one a_i is nonzero.
I'm really lost now. a_i is the number of stones we have adjacent to a
liberty at intersection i? Do we need to know the location of our
liberties to update sum a_i? How is this easier than just remembering
For every string, you can keep track of this sum incrementally.
When the string establishes a new adjacency to an empty point i,
you add code[i] into the sum.
the locations of all real liberties you saw? How do we know that the
stones around i are from the same group? What are the n_i in
n_i was the name that Tom gave to my code[i].
sum(a_i*n_i)? is {1,2,3,4}*nums supposed to be a cartesian product of
no, it's just my shorthand for the union of the 4 sets nums, 2*nums,
3*nums and 4*nums.
regards,
-John
___
computer-go mailing list
computer-go@computer-go.org
http://www.computer-go.org/mailman/listinfo/computer-go/
___
computer-go mailing list
computer-go@computer-go.org
http://www.computer-go.org/mailman/listinfo/computer-go/
Re: [computer-go] Speed of generating random playouts
Your post is very interesting. The tail part of it seems mangled. On Wed, 2007-11-14 at 20:37 -0500, Eric Boesch wrote: . Any coordinate is just a sequence of bits. Each bit can be encoded separately. So the problem reduces to how to encode a single bit (0 or 1) so that the sum of up to 4 values equals a given number (say 0) only if the bit is equal each time. For bitmasking ease, you can use 3 bits per bit. Spread each input number out like this: the Up to 4 times 1 (mod 0) equals 0 only if ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
Re: [computer-go] Language
On Wed, Nov 14, 2007 at 04:44:25PM -0600, Nick Apperson wrote: perhaps this is an obvious statement... The best language depends on the way in which your program works. Having used C++ extensively, my program designs naturally fit easily into that language. I'm sure a lisp programmer would think of better solutions that would only work in lisp. As far as languages about restriction, well #$* those languages. I make sharper turns without training wheels thank you very much. I agree it depends on how the program works, and I would even grant that often you have a large amount of design freedom to choose how the program works. In Go programming today there seems to be an especially large amount of freedom, because we are deeply uncertain how a good program should work. That freedom isn't guaranteed, though: sometimes a problem domain can push you pretty hard into using a feature. E.g., who needs more than 16-bit integers? Sometimes you don't. I think it should be easy to write a reasonably serious Go program of conventional design in a language supporting no numeric types other than 16-bit integers. But if you were in the problem domain of atomic physics simulations, the first thing you'd want to do is change languages or, failing that, at least write a floating point library in terms of the built-in 16-bit integer support. Not only floating point numbers but heap allocation, recursion, and inheritance are examples of abstractions that people working in particular problem domains can avoid for years with no difficulty, but if you get into a problem domain that calls for them, it can be really painful to do without them, regardless of whether you have been trained in a language and style which encourages them. I think it's pretty likely that someday we'll learn that the Go problem domain pushes that way for dynamic memory (heap) allocation, but YMMV. I'm in partial agreement with you on the (un)desirability of restrictions imposed by programming languages. My disagreement is that some significant fraction of the time, the restrictions of some programming language can turn out to be a good fit to what you're doing. When one is doing a lot of work in a domain where the restrictions are a good fit, a language which imposes tasteful restrictions which make it easier to reason about the program can actually be quite valuable. (Tasteless restrictions are pretty useless: I will never use a language which lets me express no numbers other than primes between 1010 and 1460.) As an example that you might agree on (at least agreeing that it's valuable, but perhaps needing to be convinced that it should be considered a restriction), I bet that as a happy C++ programmer you value the guarantees provided by the static type system when you reason about a program. But fundamentally the C++ static type system (like the fancier ones in ML and Haskell) is a restriction which limits some valid computations a program could do in a dynamically-typed language (like Lisp and many scripting languages). C++ and ML and Haskell are still Turing-complete, of course, so you can still do those valid computations somehow, typically by faking up dynamic types on top of the static type system. But doing that is clumsy enough to make it pretty clear that you're working around a restriction. (Similarly, Fortran 77 didn't have heap allocation, but programmers could fake it up by allocating one monster array and then reusing parts of it for different things. Ew.) The Turbak and Wells paper Cycle Therapy is my current favorite example of having to fake up a dynamic type system in order to express a reasonable computation --- the rose trees they define are pretty weakly typed compared to the usual objects in the SML and Haskell type systems. (Sorry, no C++ in that paper, but I think the effect should be the same in C++.) I have worked on similar code in CL, and it seems to just naturally fit into the CL dynamic type system with no hassle. Also I bet that you welcome --- or take for granted as an obviously good thing --- C++'s prohibitions on bizarre constructs like a goto statement which leaps out of the body of one function into the body of another. (C++ doesn't support the Fortranmythos/Intercal come from construct, http://www.fortran.com/come_from.html, either.:-) Such restrictions make it so much easier to reason about the vast majority of the programs we want to write that we'd need an amazingly compelling reason to want to relax them. So I think I disagree with your characterization of restrictions as training wheels. Some restrictions *are* like training wheels. But some are more like choosing to commute in a car instead of a motorcycle. Some are like having a highrise balcony which is a continuous sheet of reinforced concrete with a railing instead of just a few scattered small pads where the architect anticipates you are most likely to want to place your feet.:-| And some are controversial: you might not be happy
Re: [computer-go] Language
I definately agree with the spirit of what you are saying, and probably I am just missing something, but I'm not sure that the examples you gave are truly restricted in C++. You can import the setjmp header from C (or any number of other similar such libraries) and have crazy gotos. Every major compiler I am familiar with has ways to include assembly code as well which can't be said for all languages. As far as what C++ does to force static typing... I'm not sure I totally buy what you are saying. You can easily create a class that can have multiple types, you can overload operators to allow you to mix types and their operations, you can use polymorphism, you can use reinterpret_cast or static_cast depending on the situation. The list goes on... I don't think C++ limits you in any way. It is true that by default the language doesn't support those operations, but the beauty of C++ is that you can add to its abilities in a way that only some languages support. The fact that some languages allow you to add a string to a number by default is great if you know for sure what that means, but in C++ we must define what that means or use someone else's definition of what it means because it really isn't a core feature. But we have the tools to extend the language. The same can be said for languages like lisp and D (and probably tons of other languages I don't know). Sometimes I feel that having any primitives at all is limiting. A language where integers and floats were not built in types but libraries would be even nicer in some ways in my opinion. But, I feel being able to extend a language and metaprogram are a must for any language that will stand the test of time. With the goto example. After C++0x comes out, it would be possible (with gcc) to write a template that takes the arguments of 2 seperate functions, the first being the one jumped out of and the second being the one jumped into and wrap the interfunction goto. I think that while this may have limited utility, it should be allowed... There are times when you as a programmer know that something like that will work best. (Granted it is rare) The job of a compiler is to compile what you have told it to compile not to limit you in ways you didn't request. C++ does by default make certain things ugly but this was a conscious choice to deter you from just abusing the power of the language when it isn't really necessary. Just my thoughts, Nick On Nov 14, 2007 8:46 PM, William Harold Newman [EMAIL PROTECTED] wrote: On Wed, Nov 14, 2007 at 04:44:25PM -0600, Nick Apperson wrote: perhaps this is an obvious statement... The best language depends on the way in which your program works. Having used C++ extensively, my program designs naturally fit easily into that language. I'm sure a lisp programmer would think of better solutions that would only work in lisp. As far as languages about restriction, well #$* those languages. I make sharper turns without training wheels thank you very much. I agree it depends on how the program works, and I would even grant that often you have a large amount of design freedom to choose how the program works. In Go programming today there seems to be an especially large amount of freedom, because we are deeply uncertain how a good program should work. That freedom isn't guaranteed, though: sometimes a problem domain can push you pretty hard into using a feature. E.g., who needs more than 16-bit integers? Sometimes you don't. I think it should be easy to write a reasonably serious Go program of conventional design in a language supporting no numeric types other than 16-bit integers. But if you were in the problem domain of atomic physics simulations, the first thing you'd want to do is change languages or, failing that, at least write a floating point library in terms of the built-in 16-bit integer support. Not only floating point numbers but heap allocation, recursion, and inheritance are examples of abstractions that people working in particular problem domains can avoid for years with no difficulty, but if you get into a problem domain that calls for them, it can be really painful to do without them, regardless of whether you have been trained in a language and style which encourages them. I think it's pretty likely that someday we'll learn that the Go problem domain pushes that way for dynamic memory (heap) allocation, but YMMV. I'm in partial agreement with you on the (un)desirability of restrictions imposed by programming languages. My disagreement is that some significant fraction of the time, the restrictions of some programming language can turn out to be a good fit to what you're doing. When one is doing a lot of work in a domain where the restrictions are a good fit, a language which imposes tasteful restrictions which make it easier to reason about the program can actually be quite valuable. (Tasteless restrictions are pretty useless: I
Re: [computer-go] Speed of generating random playouts
Nice work!
I've convinced myself that what you're doing will work. If you
sacrifice the two least significant bits for zero padding, you can avoid
code_sum % pseudoliberty_count == 0 check.
On Wed, 2007-11-14 at 21:02 -0500, Eric Boesch wrote:
Sorry, I didn't mean to send that one yet. I pressed tab, meaning to
print a tab character, and return soon after, which caused gmail to,
first, change the focus to the send button, and second, send the
mail. That last bit was supposed to be
if (code_sum 5 * threshold) {
int pseudoliberty_count = code_sum / threshold;
if (code_sum % pseudoliberty_count == 0) {
int average = code_sum / pseudoliberty_count;
if (average is in my original code_value set) then there is
just one liberty.
}
}
The if average is in my original code_value set seems like a
bottleneck here, requiring about #bits (i.e. about 9, since 361 is a
9-bit number) operations no matter how you do it as far as I can tell
(unless you use a stupidly gigantic lookup table), and there's a
solution to that, too, if you don't mind wasting a little more space.
Use base 8 instead of base 5. Unfortunately, then it is no longer
possible (without using a separate pseudoliberty count) to squeeze the
result into a 32-bit number and be sure that, for chains with 19
liberties, for example, you don't get overflow. But it does permit
using a bitmask to convert the in my original code_value set test to
constant-time:
if ((average 0b110110110110110110110110110) == 0) { then there
is just one liberty }
Here, 0bfoo is the binary number foo (yes, I know that's not
legitimate C code) and I'm supposing that #bits == 9. I hope I got
this right -- I'm sort of hurrying to correct it before anybody wasted
too much time trying to decode it. (Sorry, Jason :)
On 11/14/07, Eric Boesch [EMAIL PROTECTED] wrote:
Encode each number by swapping base 2 with base 5, without changing
the digits. So binary 11011 (27) is represented as base-5 11011 (756).
This allows you to sum up to 4 such numbers without experiencing
overflow from one digit to the next (since 4 1's adds up to just 4).
Essentially, you are performing b additions in parallel. If the
numbers you are summing are all the same, and the pseudoliberty count
(#libs) is no more than 4, then each base-5 digit of the sum will
equal 0 or #libs.
With a slight modification, you can also eliminate the pseudoliberty
count completely and just use a single number. Take the largest code
value you will need, add 1, multiply by four, round up to the next
power of 5, and add this value to every code value, and now you can
just use the test
___
computer-go mailing list
computer-go@computer-go.org
http://www.computer-go.org/mailman/listinfo/computer-go/
___
computer-go mailing list
computer-go@computer-go.org
http://www.computer-go.org/mailman/listinfo/computer-go/
Re: [computer-go] Speed of generating random playouts
Let elaborate a little more on this. We want one number for each cells :
nums = {n1, n2, n3, ..., n81}
And we want the following properties :
for any a, b in nums :
(a + b) / 2 is in nums -- a == b
for any a, b, c in nums :
(a + b + c) / 3 is in nums -- a == b == c
for any a, b, c, d in nums :
(a + b + c + d) / 4 is in nums -- a == b == c == d
If we have this we are sure to don't have problems like you pointed.
Using brute force search, I've produced the following sequence of
numbers :
[17, 18, 21, 30, 49, 86, 134, 274, 590, 1061, 1348, 2301, 3005, 4805,
7609, 11157, 17802, 19393, 29046, 31538, 41442, 49154, 74823, 97358,
134625, 148826, 217801, 234930, 294657, 402550, 452686, 610274,
726514, 885190, 1040877, 1070361, 1337862, 1611001, 1829345, 1962193,
2308061, 3007701, 3133837, 4007989, 4727218, 4883797, 5546029, 7454733,
8548661, 9547305, 11552366, 13177582, 13697142, 14689461, 15538838,
15733662, 21054617, 22691377, 24433197, 27274934, 31994414, 35217106,
37507258, 41114134, 45045090, 47089386, 57357330, 62400606, 68297193,
75036946, 83039110, 96477718, 110160994, 119390498, 122575210,
148912497, 156351446, 168096257, 176942297, 194310098, 211199842]
-- snip --
And the second problems is that this solution doesn't scale well. On
19x19 you need 361 numbers in your list, so even if you find a list like
this, I doubt that you can sum up the value of all the pseudo liberties
of a big group without overflowing an unsigned and you have to switch
to bigger int like int 64.
Based on more recent emails, this may not be useful anymore, but I
have a list of 361 32-bit numbers that satisfy these properties in
case anyone is interested.
___
computer-go mailing list
computer-go@computer-go.org
http://www.computer-go.org/mailman/listinfo/computer-go/
