Re: [computer-go] Re: Open source real time Go server
computer-go-boun...@computer-go.org wrote on 18-01-2010 11:34:52: (i) IGS is derivation of NNGS, which is free software (GPLv2)! It has even seen some slight development in past few years. I don't think that's correct - NNGS was a functional copy of IGS created by duplicating the published (telnet based) interfaces. It eventually was open sourced before it died. (ii) NNGS might be used as possible base of a modern go server. The obvious advantage is that _right now_ you have something that you can (in theory) compile, start, connect to and chat and play go on (!) and you can evolve things from here. Yes. It is intended to compile and install out-of-the-box. Most of my contribution to the source was to make the program easyer to install and administer. I have done some tidying and refactoring, too. NNGS is alive and well as software, but no one is actively running a copy for human use as far as I know. Boardspace is still running a completely ignored copy, intended to be used by robots. http://boardspace.net/nngs/ In my personal opinion, there are a few NNGS clones running in asia. Most of them have been overhauled beyond recognition (= translated) You need reasonable detailed knowledge and information (eg formatting errors; trailing space on lines;) to recognise them as clones. The NNGS source @ sourceforge gets a handfull of downloads per day; I really don't know what people are doing with it. I get only one or two forum-responses per year, so maybe the software is perfect ;-) If one wanted to develop a client for the blind, you could certainly start with a NNGS clone as your target server, and one of the open source IGS clients as your client. I can imagine WMS to not wanting to get involved in protocol-opening-stuff anymore; it is a waste of time. The whole server-wars started in the first place because of the open protocol, not open to implementation. NNGS is (provably) derived from FICS (a chess server), I don't know about IGS's origins, since I never saw its source. For those who want to construct client-software: The protocol.txt file still floating around on the net somewhere; reversed engineering of IGS and NNGS will do the rest. Don't blame me for the protocol; it's terrible, but we're stuck with it. NB: My excuses for the Macro-based translation effort. Translation is bullshit anyway, since most users use a client and never use the commandline or read the help pages. It was started because some (polish?,Chinse?) guys had created translated forks of the code, which we wanted to remerge. HTH, Adriaan van Kessel. Disclaimer RIVM___ 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
computer-go-boun...@computer-go.org wrote on 18-01-2010 09:21:43: Back up a bit - what's your primary interest ? I can readily believe that not many near blind play Go on the internet now, but what makes you believe a properly supportive server would bring them out of the woods, or that FSF would be interested in supporting it? And if so, why must it be open source? Maybe the blind people want to read the source ? On second thought: they'd rather not. ;-) AvK Disclaimer RIVM___ 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
computer-go-boun...@computer-go.org wrote on 18-01-2010 18:16:28: On Mon, Jan 18, 2010 at 05:43:34PM +0100, Adriaan van Kessel wrote: computer-go-boun...@computer-go.org wrote on 18-01-2010 11:34:52: (ii) NNGS might be used as possible base of a modern go server. The obvious advantage is that _right now_ you have something that you can (in theory) compile, start, connect to and chat and play go on (!) and you can evolve things from here. Yes. It is intended to compile and install out-of-the-box. Most of my contribution to the source was to make the program easyer to install and administer. I have done some tidying and refactoring, too. Unfortunately, I have found the task far from trivial since the ratings code is not included for reasons I don't understand, and the only copy I have found seems to use completely different build system to what the NNGS documentation expects. I'm not sure if I even succeeded in the end. The ratings (mlrate, by PEM) is a bit of a problem, since the build needs it, even if you don't use them. It original was an add-on, but the code got more or less intertwined. It still is on my TODO list ... Maybe I could just supply a stub-version. AvK Disclaimer RIVM___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
Re: [computer-go] Pseudo liberties: Detect 2 unique liberties?
computer-go-boun...@computer-go.org wrote on 07-04-2009 18:33:34: Thanks. What about linked lists? They seem to be both compact and fast to merge and detect duplicates. Why have you abandoned them? Linked lists have a terrible cache behaviour: every pointer (or index) dereference has a nearly 100% chance of causing a cache miss. Lists as arrays and bitmaps have the smallest cache footprint. Not storing them at all, but recomputing them as David Fotland does (only in the playouts) has no memory footprint at all. AvK Disclaimer RIVM___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
Re: [computer-go] Transpostions in UCT search
[EMAIL PROTECTED] wrote on 27-10-2008 14:57:54: On 27-okt-08, at 11:51, terry mcintyre wrote: - Original Message From: Mark Boon [EMAIL PROTECTED] snippage Let me first describe what I did (ar attempted to do): all nodes are stored in a hash-table using a checksum. Whenever I create a new node in the tree I add it in the hash-table as well. If two nodes have the same checksum, they are stored at the same slot in the hashtable in a small list. When I add a node to a slot that already contains something, then I use the playout statistics of the node(s) already there and propagate that up the tree. Am I reading this right? Are all nodes in the same slot considered equivalent? Could some of these nodes be collisions? Yes, all the nodes in the same slot are considered equivalent. They're not collisions. If a node hashes to a slot with a different checksum, it keeps looking for an empty slot. If it doesn't find an empty slot it throws out some nodes to which it collided. Do you mean the Graph History Interaction ? (GHI) If you implement (some kind of) superko, the result of the evaluation ( = playouts) *should* depend on the path taken. For simple ko, the path is not relevant, IMHO. There may also be some information-theoretic complications (propagating twice means that some measurements are counted twice, while they have been estimated only once. This _could_ lead to inflation, because you underestimate the variance in these branches)I am not a statistician. YMMV. AvK ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
Re: [computer-go] symmetry optimizations vs statistics?
Perhaps this is also among the well-known material (or something
There have been discussions about handling symmetry in the past.
See for instance Heikki Levanto's group theoretic hashing paper.
For 'classic' (non MC) programs, board-symmetries were not important,
except for handling joseki/ fuseki collections: in a 'normal' game, the board
has no simmetries after a few moves, and there will
after that point *never* be a position that has one of its 15
mirror images present in the same gametree. So there is no need to check for
them,
because there is no possible gain.
MC is different, because it needs to re-evaluate the same
position many times, the even boardsize in Don's example
will make it even more pathological.
can be reached in multiple ways (a generalization of miai?), so counting
The miai-case is the topological variant of a symmetry.
Recognising these would need a whole different coding
('topological hashing' ?), and probably save a lot of
(wasted) effort in tsumego/semeai/endgame playing.
IMHO (I am not a statistician) not being aware of the symmetries
in MC (as in Don's case) just leads to wasted effort (and under-estimation of
the samples quality), but not to wrong results.
HTH,
AvK
___
computer-go mailing list
computer-go@computer-go.org
http://www.computer-go.org/mailman/listinfo/computer-go/
Re: [computer-go] symmetry optimizations vs statistics?
Oops I confused you with Antti Huima. No offense... I meant: http://fragrieu.free.fr/zobrist.pdf Sorry, AvK ___ 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?
Oops. Please ignore ... AvK ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
Re: [computer-go] Random
A reasonable xor+shift random (similar to Marsaglia's, but only 64bit
instead of 128 bits), using the pentium's rdtsc-instrunction to add
additional entropy (i used gnu's inline assembler) :::
#define rdtscll(val) \
__asm__ __volatile__(rdtsc : =A (val))
typedef unsigned long long BIGTHING;
BIGTHING rdtsc_rand(void);
/**/
BIGTHING rdtsc_rand(void)
{
static BIGTHING val=0xULL;
BIGTHING new;
rdtscll(new);
val ^= (val 15) ^ (val 14) ^ 9 ^ new;
return val;
}
/**/
The extra ^9 at the end can be omitted if the new is nonzero.
(is only meant to avoid the val becoming all-zeros. And shifting zeros won't
change the value ;-)
HTH,
AvK
___
computer-go mailing list
computer-go@computer-go.org
http://www.computer-go.org/mailman/listinfo/computer-go/
Re: [computer-go] Random
The question I have is how much does RDTSC slow this down?I may do I don't know. If I understand correctly, rdtsc can be executed in parallen with *some* other instructions (and places no barrier in the code), in which case it could be executed at no additional cost (except the instruction fetching, of course) I have not yet been able to instruct GCC to use the mmx or sse3 instructions/ registers to do the shifting. Code could be reshuffeled to allow the compiler more freedom. AvK ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
Re: [computer-go] Random
I would like to mention that your generator is 64 bit and the other That is correct. My timings (Haven't profiled yet): WITH TSC: real0m0.902s user0m0.870s sys 0m0.002s WITHOUT: real0m0.613s user0m0.582s sys 0m0.000s That's for 100 M random numbers. And inlining would probably help a lot, too. AvK ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
Re: [computer-go] Random
I Just omitted the new variable:
/**/
BIGTHING rdtsc_rand(void)
{
static BIGTHING val=0xULL;
#if WANT_RDTSC
BIGTHING new;
rdtscll(new);
val ^= (val 15) ^ (val 14) ^ new;
#else
val ^= (val 15) ^ (val 14) ^ 9 ;
#endif
return val;
}
/**/
AvK
___
computer-go mailing list
computer-go@computer-go.org
http://www.computer-go.org/mailman/listinfo/computer-go/
Re: [computer-go] Random
Has anyone looked at the resultant distributions, to Well, mine was pretty random. Maybe a bit too random. Changing the 14 and 15 shifts effectively cripples it. I have not looked at sequential correlation, only at the distribution, by binning the values into a histogram. As far as I could see it has a good spreading. YMMV. AvK ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
Re: [computer-go] Random
Measurements ar pretty consistent. Hardware: Linux localhost.localdomain 2.6.23.1-42.fc8 #1 SMP Tue Oct 30 13:55:12 EDT 2007 i686 athlon i386 GNU/Linux (I didnot even know it was an athlon !) AvK ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
Re: [computer-go] Random
Mine: cat /proc/cpuinfo processor : 0 vendor_id : AuthenticAMD cpu family : 6 model : 10 model name : AMD Athlon(tm) XP 2800+ stepping: 0 cpu MHz : 2079.595 cache size : 512 KB fdiv_bug: no hlt_bug : no f00f_bug: no coma_bug: no fpu : yes fpu_exception : yes cpuid level : 1 wp : yes flags : fpu vme de pse tsc msr pae mce cx8 apic mtrr pge mca cmov pat pse36 mmx fxsr sse syscall mmxext 3dnowext 3dnow up ts bogomips: 4160.98 clflush size: 32 AvK ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
Re: [computer-go] scalability with the quality of play-outs.
Alpha-beta gets better with increasing depth even with a random evaluation. http://www.cs.umd.edu/~nau/papers/pathology-aaai80.pdf (this link is from an earlier discussion: http://computer-go.org/pipermail/computer-go/2005-January/002344.html ) AvK ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
Re: [computer-go] scalability with the quality of play-outs.
decades it has been understood that a chess program with a better evaluation function improves MORE with increasing depth than one with a lesser evaluation function so it appears that Go is not unique in this Well, isn't that trivial? suppose, you have a perfect evaluation function, but you add a random value to each of it's evaluation values. Once your S/N value reaches 1/1, adding more probes/playouts will not yield a better signal. So you reach a soft horizon: you got stuck in the fog. Adding false heuristics (cutting corners) such as pseudo-liberties, or don't-play-inside-own-territory may even worsen the case. IIRC this has been described before on the the mailinglist, when alpha/beta was still fashionable. AvK ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
Re: [computer-go] scalability with the quality of play-outs.
I don't understand how what you describe relates at all to the study. It doesn't. It is a reaction to Don's explanation of it. AvK ___ 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 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). Well this could easily be solved by *always* investigating moves that take (or create) a ko. This of course will force the program to actually *recognise* the ko's. A sloppy way to always investigate would be to always try moves that capture. A similar approach can be used for ladders. Perhaps snapbacks can be handled this way, too. Not sure. Some classical programs return special values in their evaluation function, such as can win, but needs ko(s). This outcome can be used to steer the upper parts of the programs. IIRC there is some stuff about this on Dave Dyer's website. HTH, AvK ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
Re: [computer-go] Suicide question
So it's possible to create a triple-ko repetition, take that move sequence and find a non-triple-ko situation that uses the exact same repeated move sequence ? I am afraid I don't follow. Please rephrase. In my words: you have a sequence of moves (M0) leading, to a certain position (P0). After P0 , you continue with a sequence of moves (M1) leading to position (P1) Now if P0==P1, this means that the move leading to P1 (the last move of M1 is invalid. If the sequence M1 would occur anywhere inside of M0, it would cause no harm, EXCEPT when it would be the final part of M0. But in that case, P0 would itself would be a repetition of some position length(M1) *before* P0. Am I missing something ? AvK ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
Re: [computer-go] Suicide question
An alternative to matching board hashes is to test for repeated move sequences. No. repeated position != repeated sequence. Since one stone is added to the board with each move, a repetition can only exist between two moves if exactly that number of stones was captured inbetween (+- pass moves) So you only have to check the positions in the game-stack where exactly the same number of black,white stones is on the board HTH, AvK ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
Re: [computer-go] Micro-Matrix GO Machine
I wonder if the power supply can be adapted to European 230V system. It Without modifications, the system would centainly play at dan level. At least: close to God. BTW: the Fotland-article about ladders is very readable. A must-read, even if you want to implement things differently. AvK ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
Re: [computer-go] euler numbers
There was a thread on this list, started by Chrilly, around 30 Mar 2006: http://computer-go.org/pipermail/computer-go/2006-March/005127.html Note: there is an error in the 16-element table, corrected later in the thread. HTH, AvK ___ 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
(compressed) bitmaps. You don't just keep a sorted list? With (compressd) I mean that (most of) the bitmaps are relatively sparse. For an isolated stone, the needed size only needs to be about ((2*19) +1) / sizeof(bitmap_element), ~= 2 or 3 32bit ints. By skipping the leading and trailing zeros, you can speed up operations on the bitmaps. The problem with bitmaps is that iterating over them is quite costly. (the advantage is that set/get is very cheap) Sorted lists need to be resorted on every addition/merge. Linked lists are cumbersome for liberties, because a liberty can be a part of more than one list. (dynamic allocation is out of the question here, IMHO) The best quality of bitmaps is that you don't have to worry about duplicates. This duplicate-checking is where all this pseudo-liberties -talk is all about. (that is: trying to avoid it) Merging two (or more)This duplicate-checking is where all this pseudo-liberties -talk is all about. (that is: trying to avoid it) Merging two (or more) chains is extremely easy with bitmaps: merge (== OR) their members, merge (== OR) their liberties. simple comme bonjour! Splitting chains is a bit more difficult, but that will never happen. (without undo, that is) Adriaan van Kessel ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
Re: [computer-go] IEEE Spectrum article by Deep Blue creator
I think he is betting on null move proving - but I'm real skeptical that it will be effective in Computer Go. It will indeed reduce the tree IMHO null-move mixes badly with ko-tactics, effectively doubling (or squaring ? ;-) the tree size. It might be of some use in solving local sub-problems. It still has the scent of alpha-beta-with-some-evaluation-function, which is probably not the right paradigm for go. We'll see. AvK ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
Re: [computer-go] OT: median of a data stream
You can use a binary tree. In each node you store the number of child nodes in the left subtree. (maybe also for the right subtree) If you want to handle duplicates, you could add yet another counter to the nodes. Finding the median is easy. As a bonus, you can also find the value for *any* rank or percentile. Cost is 2 or3 pointers plus 2 or 3 ints per node, say 20 bytes. If your input is reasonably random, balancing will not be needed. Avoiding dynamic allocation will probably speed things up. (and make deallocation easyer ;-) HTH, AvK ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
Re: [computer-go] Go and UCT: article in June 2007 SciAm
... It was done as a simulated annealing. Yep: http://nngs.ziar.net/cgml/split/7/5/9/[EMAIL PROTECTED] [ maybe simulated annealing is Monte Carlo as performed by blacksmiths, after all ;-] AvK ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
Re: [computer-go] Mega transposition table
UCT could help to tiddy up the transposition table Erik van der Werf's thesis was mainly about transposition table replacement algorihtms, IIRC. My personal summary: it is very hard to be more clever (at replacement) than always replace when hitting an occupied slot. (this is very similar to beating a LRU-replacement-sheme for disk-blocks; but totally different ;-) after a degree of confidence is gained. This could I think, this is exactly what the transposition table's purpose is: Avoid doing the same computations over and over. If you avoid them by some other means, the hash-nodes will be replaced anyway, eventually. No sweat. HTH, AvK ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
