Re: [computer-go] 3-4-5 rule
Don Dailey wrote: After 842 games with 19x19 go the version with the 3-4-5 line rule is scoring about 55% I thought it might do better, I think the rule is reasonably sound - but 55% is pretty respectable for such an easy change and it hardly slows down the search at all. Rank Name Elo+- games score oppo. draws 1 d2p 2037 12 12 842 55% 20000% 2 base 2000 12 12 842 45% 20370% You are using the rule for move selection during the playouts and the search, right? I think such a change may make engine objectively stronger while making it more vulnerable against humans. Even if the human opponent isn't aware of the move pruning logic initially, it wouldn't take a lot of games to figure out that the computer never makes a move away from the last move to the center or to the sides. Once the player understands the reason (because the engine never _considers_ such moves) building traps should be very easy for a good go player. For example, start a losing ladder towards the center on one side, then start another losing ladder to the center from another side, such that a ladder breaker in the center can break both ladders. Now the engine would play thinking all of its stones in the ladder are safe, oblivious to the fact it will be able to rescue only one group of them, if a move to the center is made. Of course the same idea may be used by a programmer to specifically build an engine stronger against engines with 3-4-5 rule too. The engine should at least allow _opponent_ to break the rule in the search tree. That is quite a bit harder to exploit. Now the player must find moves with refutations outside of the allowed search window. But there is now the problem of increased evaluation difference between odd and even depths (as one player is objectively stronger.) Therefore I think you shouldn't let engine prune in the tree with *any* simple heuristic rule, no matter how often that rule is a useful guide. OTOH pruning in the playouts seems safe enough. Does that increase strength too? ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
Re: [computer-go] Publishing source for (yet another) MC simulator
terry mcintyre wrote: From: Don Dailey [EMAIL PROTECTED] On Tue, 2008-11-04 at 10:13 -0800, terry mcintyre wrote: Some language may make it easy to encapsulate information gleaned during local searches into a kind of short term memory and exploit that to speed up evaluation of many branches of the search tree. Who knows? We have a long way to go before playing at the pro level on a 19x19 board. I'm a firm believer that computer I.Q. is directly correlated with processing power. In this case, the ability to win at GO for a computer is going to be a function of the CPU performance and memory capacity. Some languages will facilitate the exploration of ideas exactly as you say. But at some level it will come down to an efficient implementation.One can always take a good idea, and then re-implement it in a boring but very fast execution language such as C or assembly. It would be a shame to have to do this however if you already have a language that can really express the idea superbly. At some level, this is true; it comes down to crafting an efficient implementation; but some languages make it easier to express some ideas than others. For instance, some languages make it very natural to perform operations on every element of an aggregate - a list, set, array, or whatever - without having to express the details of the loop. Haskell, among other languages, makes it easy to embed Domain Specific Languages in one's program; one can imagine a program which expresses Go-specific terms in a very natural way. C/C++ with MPI is not the last word on multiprocessing support; other languages probably do it better. Functional languages permit much lighter-weight concurrency and multiprocessing, avoiding the need for locks and semaphores. That is excellent in theory but I would advise against anyone trying to *learn* a functional language for experimenting with go programming. I have tried doing exactly that with Clean, a very fast Haskell like language according to debian language shootout . Although very complicated parts of the search became easy to express, very simple things like using a doubly linked list for string membership or getting random numbers for the MC simulations became a nightmare. I'm sure someone experienced in the language could do a much better job than me, but it is not at all easy for a newcomer. ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
[computer-go] random numbers with functional languages
Hi, I'm currently writing a UCT based go program in Clean to see if it is feasible to write one in a functional language. This is my first attempt at functional languages, and I'm having trouble with random numbers. A mersenne twister module is available for Clean. Once initialized it is reasonably fast to extract a new random number from the generator. However, it is about a hundred times slower to initialize it with a new random seed. Therefore my first attempt at generating random numbers by storing seeds at tree nodes and creating a new random list and a new seed each time random numbers are required for mc evaluation is very slow. The alternative seems to be passing around an index to a global random list, which is both ugly and complicated. Is there another way? ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
Re: [computer-go] random numbers with functional languages
That was not the problem, as the source code is available and it doesn't call system libraries at all. I was initializing with known seed in my tests anyway. Thanks though, in the process of composing a reply demonstrating the problem, I found a partial solution. Now random number generation takes 3% of running time, compared to 60% of older version and ~1% of a hypothetical ideal solution. Berk. Stuart A. Yeates wrote: Probably the reason that it is so slow is that it's aiming for a cryptographically random number sequence. These are usually derived ultimately from kernel timings (often via /dev/random on linux systems) and it can take a while to establish a degree of confidence in the randomness of these bits. If you want a sequence of numbers that is very unlikely to repeat but that doesn't have to be cryptographically random, standard practice is to initialise the random number generator with the current time (usually a long expressed in milliseconds). This naturally fails if you ever create more than one sequence per millisecond. cheers stuart On 19/12/2007, Berk Ozbozkurt [EMAIL PROTECTED] wrote: Hi, I'm currently writing a UCT based go program in Clean to see if it is feasible to write one in a functional language. This is my first attempt at functional languages, and I'm having trouble with random numbers. A mersenne twister module is available for Clean. Once initialized it is reasonably fast to extract a new random number from the generator. However, it is about a hundred times slower to initialize it with a new random seed. Therefore my first attempt at generating random numbers by storing seeds at tree nodes and creating a new random list and a new seed each time random numbers are required for mc evaluation is very slow. The alternative seems to be passing around an index to a global random list, which is both ugly and complicated. Is there another way? ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
Re: [computer-go] random numbers with functional languages
Your solution would still be way faster, as I still have to generate a new random number every time I need one. The problem is lack of side effects in Clean. If I stick to functional programming paradigm -and that is the whole point of my effort- I can't write function which returns a different number each time it is called. A function is supposed to return same result every time it is called with same parameters so I can't/shouldn't write an analogue of getNextInt() (whether or not getNextInt() returns a number from a list or from a random number generator.) I just shaved off time by not initializing a new random generator each time a node is visited. Instead, when a leaf node is visited, first maxMoves terms of random list is sent to MC evaluation, and remaining terms are used to create a new list. Sharing this list across whole search tree would be ugly and complicated. So I still initialize a new random list for each new tree node but reuse it for subsequent MC evaluations from that node. Berk. Imran Hendley wrote: A sorry about that. Glad to hear you fixed the problem. What was your solution? It seems you mentioned the global list approach in your email which I missed too. Why did you think this was an ugly approach? I just put my random array in a Singleton object (call it MyRandomNumberGenerator) which internally stores the next index and has a method for getting the next random number. So I just replace all my calls to Random.getNextInt() with MyRandomNumberGenerator.getNextInt(). Actually I can see how a lot of people would still call this ugly... But it's just a lookup so I think it will beat any other solution that involves generating a new random number by a reasonable margin. On Dec 19, 2007 5:15 AM, Berk Ozbozkurt [EMAIL PROTECTED] mailto:[EMAIL PROTECTED] wrote: That was not the problem, as the source code is available and it doesn't call system libraries at all. I was initializing with known seed in my tests anyway. Thanks though, in the process of composing a reply demonstrating the problem, I found a partial solution. Now random number generation takes 3% of running time, compared to 60% of older version and ~1% of a hypothetical ideal solution. Berk. Stuart A. Yeates wrote: Probably the reason that it is so slow is that it's aiming for a cryptographically random number sequence. These are usually derived ultimately from kernel timings (often via /dev/random on linux systems) and it can take a while to establish a degree of confidence in the randomness of these bits. If you want a sequence of numbers that is very unlikely to repeat but that doesn't have to be cryptographically random, standard practice is to initialise the random number generator with the current time (usually a long expressed in milliseconds). This naturally fails if you ever create more than one sequence per millisecond. cheers stuart On 19/12/2007, Berk Ozbozkurt [EMAIL PROTECTED] mailto:[EMAIL PROTECTED] wrote: Hi, I'm currently writing a UCT based go program in Clean to see if it is feasible to write one in a functional language. This is my first attempt at functional languages, and I'm having trouble with random numbers. A mersenne twister module is available for Clean. Once initialized it is reasonably fast to extract a new random number from the generator. However, it is about a hundred times slower to initialize it with a new random seed. Therefore my first attempt at generating random numbers by storing seeds at tree nodes and creating a new random list and a new seed each time random numbers are required for mc evaluation is very slow. The alternative seems to be passing around an index to a global random list, which is both ugly and complicated. Is there another way? ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
Re: [computer-go] Efficiently selecting a point to play in a random playout
Álvaro Begué wrote:
At least for Windows programmers, providing a solution that
compiles with major IDEs would help. I assume what you do is
standard in Linux, but the things the compiler did not understand
neither did I, and I could not find the time for googleing.
With 1.08 version of lego and Turbo C++, there are too many errors
related to namespaces, system libraries etc.
With *wx-Devcpp* http://wxdsgn.sourceforge.net/ windows compilation is
relatively straightforward. Create a new project file (main.cpp and
gtp.cpp is enough for benchmarking), Replace get_seconds(), install
boost library (a package is available at devpaks.org if you don't want
to compile the library) and you are done.
---
float get_seconds () {
return double(clock()) / double(CLOCKS_PER_SEC);
}
I know this is not a precise way of calculating time, but if it is good
enough for fruit, it is good enough for me.
___
computer-go mailing list
computer-go@computer-go.org
http://www.computer-go.org/mailman/listinfo/computer-go/
