Re: [computer-go] Zobrist hashing
On Wed, Apr 8, 2009 at 2:07 PM, Isaac Deutsch i...@gmx.ch wrote: What I don't understand is: How do you know from just a single xor hash if you have played a certain position/color before? Don't you somehow have to store for each possible hash (which is 2 bytes in my example) if it has been used before? The amount of possible hashes even for 2 bytes is quite large. Like any hash function, multiple board positions can hash to the same value. The idea is that the probability of encountering two board positions in the same game that have the same hash value is so low, that if you get a duplicate hash value you are practically guaranteed that it's a superko. Colin ___ 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?
On Tue, Apr 7, 2009 at 12:33 PM, Łukasz Lew lukasz@gmail.com wrote: Thanks. What about linked lists? They seem to be both compact and fast to merge and detect duplicates. Why have you abandoned them? Lukasz Or a Hash Set, which has constant time insert, delete, contains, and size operations and guarantees no duplicates. Merging groups would be linear, I think. Colin ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
Re: [computer-go] Presentation of my personnal project : evolution of an artificial go player through random mutation and natural selection
On Tue, Feb 24, 2009 at 2:40 AM, Daniel Burgos dbur...@gmail.com wrote: Nice project! I worked on this some time ago. I did not use neural networks but patterns with feedback. The problem with feedback is that it is difficult to know when it reaches its final state. Usually you get oscillations and that state never happens. I tried to solve that using timeouts, but what I got were random players. How are you going to solve this? Dani 2009/2/13 Ernest Galbrun ernest.galb...@gmail.com On Fri, Feb 13, 2009 at 22:42, Mark Boon tesujisoftw...@gmail.com wrote: Just curious, did you ever read 'On Intelligence' by Jeff Hawkins? After reading that I got rather sold on the idea that if you're ever going to attempt making a program with neural nets that behaves intelligently then it needs to have a lot of feed-back links. Not just the standard feed-forward type of networks. Some other good ideas in that book too IMO. Mark Oh, thank you for the advice, this is the kind of things that can very smoothly be implemented in the program, I will surely a/ buy and read this book and b/ introduce some feedback interaction in my neuronal network. I have not introduced it so far because it seemed some ineffective expense in calculation power. ___ 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/ I read a paper a couple years ago about a genetic algorithm to evolve a neural network for Go playing (SANE I think it was called?). The network would output a value from 0 to 1 for each board location, and the location that had the highest output value was played as the next move. I had an idea that the outputs could be sorted to get the X best moves, and that that set of moves could be used to direct a minimax or monte carlo search. I haven't had the chance to prototype this, but I think it would be an interesting and possibly effective way to combine neural networks with the current Go algorithms. Colin ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
Re: [computer-go] Drunken sailor on payday
On Nov 21, 2007 3:36 PM, Petr Baudis [EMAIL PROTECTED] wrote: On Wed, Nov 21, 2007 at 09:16:48PM +0100, Raymond Wold wrote: On Wed, 2007-11-21 at 14:11 -0500, Don Dailey wrote: Experience in a language is a factor, but nobody refutes that properly coded C is fastest (next to properly code assembly) and if performance is your goal, then anything else accepts some compromise. That compromise may work well for a particular individual and may even produce a stronger program for them, but it's still a handicap. Do you have anything to back this up? I was under the impression that most decent assembly programmers agreed that they can't compete with the best C compilers. Assembly is for when you *need* to be in touch with the very lowest level, which in most cases you don't, because lots and lots of other assembly programmers have been there before you and distilled their knowledge into really really smart compilers that know more, and can try out more, than you ever could in a lifetime. I guess that you could say the original statement holds but humans generally can't properly code assembly anymore. ;-) What's to say that a computer program can't code assembly better than any human possibly could? There are a ton of tasks that computers do thousands of times better than humans. I think it makes perfect sense that code written in C can execute faster than human-written assembly code. Colin ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
Re: [computer-go] Drunken sailor on payday
On Nov 21, 2007 5:37 PM, Ben Lambrechts [EMAIL PROTECTED] wrote: Some chess programmers have told me that this feature works much better in Visual C++ than in gcc. It's too bad I am not willing to program in Windows to verify it. I have compiled GNU Go with both GCC and Visual C++ 2008. The binary of Visual C++ was almost half the size of the GCC one, but 3 times slower. I think I choose for the speed instead of the size. Ben I'm not sure about the Visual C++ compiler, but with GCC there are a number of options for optimization, some sacrificing size for speed, and others vice versa. It could just be a matter of compiler options. Colin ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
Re: [computer-go] Drunken sailor on payday
On Nov 21, 2007 6:12 PM, [EMAIL PROTECTED] wrote: What's to say that a computer program can't code assembly better than any human possibly could? There are a ton of tasks that computers do thousands of times better than humans. I think it makes perfect sense that code written in C can execute faster than human-written assembly code. No compiler will ever do *all* of the optimizations that are possible, because most optimizations are NP-complete or even much worse. For example the equivalance of boolean expressions is NP-complete. Some potential optimizations (such as replacement of data structures) may not even computable. This is why humans must choose the algorithms and data strucures. Compilers are very good at *small, local optimizations*, such as putting variables in registers, common sub-expression elimination, and choosing the fastest instructions. Compilers almost always outperform humans on these tasks because compilers consistently try every trick they know, and they don't get tired. Even way back in the 1970s, studies showed that optimizers consistently outperformed humans on these tasks, and back then, many people still practiced doing assembler regularly. Today, performance combines programmer and compiler intelligence. Neither can replace the other. Please use both. Michael Wing So this seems to support the idea that C code is potentially faster than hand-coded assembly, because the more complicated optimizations can be done by the programmer in C while the optimizations better suited to a computer are done by the compiler. Although it would also be possible to hand-code in assembly and then run a program to optimize it, but then it seems like there is no advantage over C. As far as I can tell, the optimizations that a compiler can't do are higher-level optimizations that can be done in C and wouldn't require the programmer to write assembly, or am I wrong about this? Colin ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
Re: [computer-go] Drunken sailor on payday
On Nov 21, 2007 7:24 PM, Don Dailey [EMAIL PROTECTED] wrote: Raymond Wold wrote: On Wed, 2007-11-21 at 14:11 -0500, Don Dailey wrote: Experience in a language is a factor, but nobody refutes that properly coded C is fastest (next to properly code assembly) and if performance is your goal, then anything else accepts some compromise. That compromise may work well for a particular individual and may even produce a stronger program for them, but it's still a handicap. Do you have anything to back this up? I was under the impression that most decent assembly programmers agreed that they can't compete with the best C compilers. Assembly is for when you *need* to be in touch with the very lowest level, which in most cases you don't, because lots and lots of other assembly programmers have been there before you and distilled their knowledge into really really smart compilers that know more, and can try out more, than you ever could in a lifetime. I know that there are assembler programmers who specialize in the skills requires to beat C code.However, there is no need to back this up. You can express any C program in assembler and better C compilers do this better and they continue to improve. Until C compilers are perfect, then it will always be possible to express a (non-trivial) program in more efficient assembler code. But the point is that humans are also not perfect, and so they too can't automatically write the optimal assembly code. The question is whether the massively superior processing power of a computer gives it an advantage over the creative ability of a human. Colin ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
Re: [computer-go] Re: more on languages
On Nov 21, 2007 7:06 PM, Don Dailey [EMAIL PROTECTED] wrote: You see to have very old-fashioned ideas about the whole programming philosophy.You take the view that a project like go is a fixed static task and that you must optimize the programmers time in typing in code. And then you are done.And since it takes many man hours, it doesn't matter if it takes 10 seconds to find a move instead of 1.After all, waiting an extra 9 seconds is nothing compared to the hundreds of hours programming this task.Or you can wait 5 years and that 9 seconds is now 1 second. You can look at this from a completely different point of view and come to the opposite conclusion. Because creating a Go program is NOT a static task, it means that you can't just code the program once and be done. You will constantly be revising old code and writing new code. Therefore, it seems like writing in a language that is fast and easy would be beneficial. Suppose I have a Go program written in a language that is fast to write and slow to run and you have one in a language that is slow to write and fast to run. Right now, your program is faster than mine and therefore better. Now let's say a new technique is developed that will improve our programs. I can add this technique into my program in, say, two weeks, but it will take you 2 months. So for a month and a half, I have a better program. By the time you finish your implementation, it's possible that another new technique will have been developed. From that point of view, it seems like it is the person with the slow-to-code, fast-to-run language that will always be playing catch up. It seems like it really comes down to the programmer. I don't think any language is necessarily faster or easier to code than another one, it all depends on the experience and skill of the programmer. This model might be reasonable in a corporate environment where you have different priorities, but the whole POINT of a GO program is to make it as strong as possible. That may be true if your goal is to have the strongest Go program in the world, but another completely legitimate goal is to develop new techniques and algorithms to address the problem. In that case, it doesn't really matter if your program is slow. Colin ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
Re: [computer-go] Language
Hi, I think the reason for Ruby being so much slower is because it is an interpreted language rather than a compiled language. So when you run the program, a Ruby interpreter has to translate the instructions to machine code as they are running, instead of a compiled language like C where this is done at compile time. As for my opinions on languages, most of my experience is with C/C++, but I have begun using Java recently. Java is what I am using for the Go program I am writing, mainly because even after years of using C++, I still find it easier and faster to code in Java (using Eclipse) than with C++. The OP mentioned that Java is slow, but I have actually read that in the recent years it has become comparably faster to C++, although I haven't tested this personally (I hope this isn't going to start a holy war between the Java and C++ people here). I have also done quite a bit of Perl programming, although it's use seems much more specialized that C++ or Java. I basically only use it in two situations: When I have to do a lot of processing with text, or when I want to create a program very quickly to perform a certain task and I don't care that I won't be able to understand what I wrote if I look at it a week later. Colin (I just joined this list last week, this is my first post) On Nov 20, 2007 9:58 AM, Chuck Paulson [EMAIL PROTECTED] wrote: My 2 cents about languages. C is the universal assembly language. I don't think I've ever used a computer family that didn't have a C compiler on it (after C was invented of course). Often new languages, to get started, will just translate into C code and then compile with the C compiler. I wrote my first Go programs earlier this year. I first used Ruby and it was short and easy to write. The GTP protocol (enough for CGOS) took only about 1 page of code. However in timing tests, it could only do about 30 game simulations per second. This was unacceptable and I abandoned Ruby. Next I translated the ideas into C++. Everything was more work, but I anticipated a 10-20 times speed up so it seemed the tradeoff would be worth it. After finishing, I did the same timing tests as with Ruby and it did 9000 game simulations per second without much optimization. I knew, of course, that Ruby is slower than C++ but a factor of 300 is amazing. It helps to have explicit control of memory and mature C compilers that generate fast code. I am still wondering how Ruby could be so much slower than C++. Perhaps this problem is just not suited for Ruby. Chuck Paulson ___ 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 Nov 20, 2007 1:56 PM, Nick Apperson [EMAIL PROTECTED] wrote: On Nov 20, 2007 12:48 PM, Stefan Nobis [EMAIL PROTECTED] wrote: Colin Kern [EMAIL PROTECTED] writes: I think the reason for Ruby being so much slower is because it is an interpreted language rather than a compiled language. It's not the main problem (interpreted languages are slower than those compiled to native code, but than even Java and C# are interpreted and don't have such big slowdowns). Java and C# are both compiled at some point if the same loop is running repeatedly. Java is usually compiled just in time which is to say as each function is first run. I'm not sure how C# is executed, but I think it gets compiled before execution. I just found this looking around for things about Java's speed. Looks like some useful ways to boost Java's performance. http://www.cs.cmu.edu/~jch/java/speed.html -Colin ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
