Re: [computer-go] Effective Go Library v0.101
On 2/17/07, Luke Gustafson <[EMAIL PROTECTED]> wrote:
Lukasz, any chance you can access the assembly to see how the compiler
optimized it differently? That is a strange result. All that I could think
of is, if you have several places where the function is called, and the
compiler used to be inlining it, it may be faster (for cache reasons) to
make it a function call instead of inlining. Inlining is not always
fastest!
There was only one place and no inlineing :)
So it was pure difference static/dynamic call.
And I did immediately look at the asm, the difference was very small.
exactly static / dynamic call :) So I don't get it.
But I don't won't to get it. Is to much for me. I.e. too absorbing :)
Regarding function pointers--from Agner Fog's guide:
"3.7 Indirect jumps (all processors except PM and Core2)
Indirect jumps, indirect calls, and returns may go to a different address
each time. The
prediction method for an indirect jump or indirect call is, in all
processors except PM and
Core2, simply to predict that it will go to the same target as last time it
was executed. The
first time an indirect jump or indirect call is seen, it is predicted to go
to the immediately
following instruction." (The Pentium M & Core2 have more sophisticated
indirect jump prediction)
I tested on PM, so this may be an explanation.
But anyway this is so small *detail* that I prefer to concentrate in
different places.
For instance I just implemented UCT and I want to publish it asap.:)
Lukasz
So, if a function pointer always points to the same function, all processors
will predict the branch correctly! I am doubtful function objects would be
much faster, except that they may be more likely to be inline-able.
Also I disagree that well-designed code should cause function objects to be
predicted at compile time--it seems to me that their purpose is for run-time
polymorphism!
>I will just tell You about my experiences:
>
> - allmost all code of benchmark in Ego library is inlined (remove_stone is
> not)
> - function pointer are usually inefficient, because jump prediction works
> poorly
> - when I introduced a parameter to simple_playout::run: function
> pointer that replaced play_one and always put address of play_one
> there, then the code was slightly faster.
> I have *no idea* why it was so.
>
> - and most important: KISS
>
> Lukasz
>
>
> On 2/16/07, Darren Cook <[EMAIL PROTECTED]> wrote:
>> >> trouble. Also, the alternative is usually function pointers which
>> >> have
>> >> atleast 50 times the overhead of a function object. Correct me if I'm
>> >> wrong.
>> >>
>> > function objects really cannot be 50 times more efficient as function
>> > pointer are rather efficient with very little overhead.
>>
>> With well-designed code, function objects ("functors") should be
>> compiled inline, and have zero overhead. Function pointers are never
>> inlined (unless modern compilers are getting *really* clever), so they
>> always have some overhead. Functors are therefore divide-by-zero-times
>> more efficient (I don't know where Nick got the 50 times figure from :-).
>>
>> (If the functor is large enough to not be inlined then it is execution
>> time that dominates and function call overhead is not important.)
>>
>> Using functors might cause more code, so less code fits in cache. I
>> don't know how that affects overall performance.
>>
>> Darren
>>
>> ___
>> computer-go mailing list
>> computer-go@computer-go.org
>> http://www.computer-go.org/mailman/listinfo/computer-go/
>>
> ___
> computer-go mailing list
> computer-go@computer-go.org
> http://www.computer-go.org/mailman/listinfo/computer-go/
___
computer-go mailing list
computer-go@computer-go.org
http://www.computer-go.org/mailman/listinfo/computer-go/
___
computer-go mailing list
computer-go@computer-go.org
http://www.computer-go.org/mailman/listinfo/computer-go/
Re: [computer-go] Effective Go Library v0.101
I highly disagree that the point of function objects is to allow runtime
polymorphism. Certainly that is useful, and I have no objection to it. I
like templates because they allows the compiler to optimize anything that is
optimizable and doesn't make the programmer worry about it at all. This is
the goal of a well designed language. A template that uses the functors
will be written once and work for ALL cases and always be optimized as best
as is possible byt the compiler because it is independently compiled for
each case. This is a pretty impressive accomplishment and in my mind it is
one of the major features of C++ that sets it way ahead of simpler languages
such as Java. Not that Java doesn't have its place, but for for advanced
and highly flexible designs, templates are pretty close to the perfect tool
imho.
Just look at the STL. Its sort is faster than ones that most people hand
code and it works with any datatype and can be passed functors... Pretty
impressive, highly flexible (any datatypes and any way of sorting) and it is
generally optimized to be as fast or faster than anything that ever really
good programmers create for their one specific case. That is the power of
templates. And the best part is that if a better algorithm comes along in 2
years, only one function needs to be changed instead of 200 different
sorting functions. That is indicative of a good design. But this has
nothing to do with Effective Go Library anymore.
With regard to what you wrote about the branch always being predicted
correctly ... you are correct assuming there are not too many branches in
the code. The processor has a table that stores these branches but that
table is only of a certain size. Anyway, it doesn't really matter much
because future processors are likely to change how they function anyway.
Templated code is an ideal solution though because it abstracts a concept
from the specifics of how it is implemented which gives maximum flexibility
and close to perfect optimization.
And my number of 50... I didn't even think about it, but I got it from some
calculations I did a long time ago. Yeah, really kind of a meaningless
number now that I think about it.
On 2/16/07, Luke Gustafson <[EMAIL PROTECTED]> wrote:
Lukasz, any chance you can access the assembly to see how the compiler
optimized it differently? That is a strange result. All that I could
think
of is, if you have several places where the function is called, and the
compiler used to be inlining it, it may be faster (for cache reasons) to
make it a function call instead of inlining. Inlining is not always
fastest!
Regarding function pointers--from Agner Fog's guide:
"3.7 Indirect jumps (all processors except PM and Core2)
Indirect jumps, indirect calls, and returns may go to a different address
each time. The
prediction method for an indirect jump or indirect call is, in all
processors except PM and
Core2, simply to predict that it will go to the same target as last time
it
was executed. The
first time an indirect jump or indirect call is seen, it is predicted to
go
to the immediately
following instruction." (The Pentium M & Core2 have more sophisticated
indirect jump prediction)
So, if a function pointer always points to the same function, all
processors
will predict the branch correctly! I am doubtful function objects would
be
much faster, except that they may be more likely to be inline-able.
Also I disagree that well-designed code should cause function objects to
be
predicted at compile time--it seems to me that their purpose is for
run-time
polymorphism!
>I will just tell You about my experiences:
>
> - allmost all code of benchmark in Ego library is inlined (remove_stone
is
> not)
> - function pointer are usually inefficient, because jump prediction
works
> poorly
> - when I introduced a parameter to simple_playout::run: function
> pointer that replaced play_one and always put address of play_one
> there, then the code was slightly faster.
> I have *no idea* why it was so.
>
> - and most important: KISS
>
> Lukasz
>
>
> On 2/16/07, Darren Cook <[EMAIL PROTECTED]> wrote:
>> >> trouble. Also, the alternative is usually function pointers which
>> >> have
>> >> atleast 50 times the overhead of a function object. Correct me if
I'm
>> >> wrong.
>> >>
>> > function objects really cannot be 50 times more efficient as function
>> > pointer are rather efficient with very little overhead.
>>
>> With well-designed code, function objects ("functors") should be
>> compiled inline, and have zero overhead. Function pointers are never
>> inlined (unless modern compilers are getting *really* clever), so they
>> always have some overhead. Functors are therefore divide-by-zero-times
>> more efficient (I don't know where Nick got the 50 times figure from
:-).
>>
>> (If the functor is large enough to not be inlined then it is execution
>> time that dominates and function call overhead is not important.)
>>
>> Using functors might cause more
Re: [computer-go] Effective Go Library v0.101
Lukasz, any chance you can access the assembly to see how the compiler
optimized it differently? That is a strange result. All that I could think
of is, if you have several places where the function is called, and the
compiler used to be inlining it, it may be faster (for cache reasons) to
make it a function call instead of inlining. Inlining is not always
fastest!
Regarding function pointers--from Agner Fog's guide:
"3.7 Indirect jumps (all processors except PM and Core2)
Indirect jumps, indirect calls, and returns may go to a different address
each time. The
prediction method for an indirect jump or indirect call is, in all
processors except PM and
Core2, simply to predict that it will go to the same target as last time it
was executed. The
first time an indirect jump or indirect call is seen, it is predicted to go
to the immediately
following instruction." (The Pentium M & Core2 have more sophisticated
indirect jump prediction)
So, if a function pointer always points to the same function, all processors
will predict the branch correctly! I am doubtful function objects would be
much faster, except that they may be more likely to be inline-able.
Also I disagree that well-designed code should cause function objects to be
predicted at compile time--it seems to me that their purpose is for run-time
polymorphism!
I will just tell You about my experiences:
- allmost all code of benchmark in Ego library is inlined (remove_stone is
not)
- function pointer are usually inefficient, because jump prediction works
poorly
- when I introduced a parameter to simple_playout::run: function
pointer that replaced play_one and always put address of play_one
there, then the code was slightly faster.
I have *no idea* why it was so.
- and most important: KISS
Lukasz
On 2/16/07, Darren Cook <[EMAIL PROTECTED]> wrote:
>> trouble. Also, the alternative is usually function pointers which
>> have
>> atleast 50 times the overhead of a function object. Correct me if I'm
>> wrong.
>>
> function objects really cannot be 50 times more efficient as function
> pointer are rather efficient with very little overhead.
With well-designed code, function objects ("functors") should be
compiled inline, and have zero overhead. Function pointers are never
inlined (unless modern compilers are getting *really* clever), so they
always have some overhead. Functors are therefore divide-by-zero-times
more efficient (I don't know where Nick got the 50 times figure from :-).
(If the functor is large enough to not be inlined then it is execution
time that dominates and function call overhead is not important.)
Using functors might cause more code, so less code fits in cache. I
don't know how that affects overall performance.
Darren
___
computer-go mailing list
computer-go@computer-go.org
http://www.computer-go.org/mailman/listinfo/computer-go/
___
computer-go mailing list
computer-go@computer-go.org
http://www.computer-go.org/mailman/listinfo/computer-go/
___
computer-go mailing list
computer-go@computer-go.org
http://www.computer-go.org/mailman/listinfo/computer-go/
Re: [computer-go] Effective Go Library v0.101
Will small recursive functions be inlined when they are called from outside the function itself? ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
Re: [computer-go] Effective Go Library v0.101
I will just tell You about my experiences:
- allmost all code of benchmark in Ego library is inlined (remove_stone is not)
- function pointer are usually inefficient, because jump prediction works poorly
- when I introduced a parameter to simple_playout::run: function
pointer that replaced play_one and always put address of play_one
there, then the code was slightly faster.
I have *no idea* why it was so.
- and most important: KISS
Lukasz
On 2/16/07, Darren Cook <[EMAIL PROTECTED]> wrote:
>> trouble. Also, the alternative is usually function pointers which have
>> atleast 50 times the overhead of a function object. Correct me if I'm
>> wrong.
>>
> function objects really cannot be 50 times more efficient as function
> pointer are rather efficient with very little overhead.
With well-designed code, function objects ("functors") should be
compiled inline, and have zero overhead. Function pointers are never
inlined (unless modern compilers are getting *really* clever), so they
always have some overhead. Functors are therefore divide-by-zero-times
more efficient (I don't know where Nick got the 50 times figure from :-).
(If the functor is large enough to not be inlined then it is execution
time that dominates and function call overhead is not important.)
Using functors might cause more code, so less code fits in cache. I
don't know how that affects overall performance.
Darren
___
computer-go mailing list
computer-go@computer-go.org
http://www.computer-go.org/mailman/listinfo/computer-go/
___
computer-go mailing list
computer-go@computer-go.org
http://www.computer-go.org/mailman/listinfo/computer-go/
Re: [computer-go] Effective Go Library v0.101
>> trouble. Also, the alternative is usually function pointers which have
>> atleast 50 times the overhead of a function object. Correct me if I'm
>> wrong.
>>
> function objects really cannot be 50 times more efficient as function
> pointer are rather efficient with very little overhead.
With well-designed code, function objects ("functors") should be
compiled inline, and have zero overhead. Function pointers are never
inlined (unless modern compilers are getting *really* clever), so they
always have some overhead. Functors are therefore divide-by-zero-times
more efficient (I don't know where Nick got the 50 times figure from :-).
(If the functor is large enough to not be inlined then it is execution
time that dominates and function call overhead is not important.)
Using functors might cause more code, so less code fits in cache. I
don't know how that affects overall performance.
Darren
___
computer-go mailing list
computer-go@computer-go.org
http://www.computer-go.org/mailman/listinfo/computer-go/
Re: [computer-go] Effective Go Library v0.101
Functors if known at compile time will usually be inlines, but if they are too big to be inlined then a regular (not indirect) function call will be made so like "call foo" instead of like "call [EDX]" but when you use a function pointer instead of a template function, this is what happens: if all of the following conditions are met then we will get a direct call (like we do with templates) 1) function body of the function that takes a function pointer as a parameter is avaliable in current compilation unit (possible) 2) the function that takes a function pointer as a parameter is small enough to inline (possible, but for what we are talking about not the case probably) 3) the compiler has to be smart enough to know how to do this type of substitution (many compilers don't) with templates, the template code must be avaliable in a header (like condition #1 above) and the function is generated from that function and the functor will be compiled as a direct call. There are obviously 2 downsides. First, you have to use templates and have the template function body avaliable in the header (but this is a standard deal with templates). Second, if there are multiple possibilities for what the functor or callback could be (not the case in what we are talking about) this could lead to code bloat. As far as indirect calls being inefficient. I know it seems counterintuitive since they are so "low level" and I use them in certain instances (and I love them), but the reality is that indirect function calls are one of the worst things for performance because the decoding of instructions is done considerably ahead of time and the processor needs to predict branches in code to keep the pipeline of decoded instructions full. If it comes to a branch that is 2 way, it has a 50% chance and with recent processors this has been optimized so that if it guesses wrong it isn't the end of the world, but with an indirect call, it has no good way to guess the location (the most likely is supposed to be placed as an unconditional jump after the indirect call on intel platforms) and it can't spread its resources across all possible locations it could jump to because there are millions of possibilities. If a function is getting called many times and it is a small function, most of the resources are devoted to this overhead. I know they have made some strides with the core 2 duo, but this is a really hard to deal with problem. And all this is irrelevent if this aspect isn't the bottleneck. Anyway, this is kind of off topic... Point is, templates and functors are going to be faster and they certainly are cleaner so I prefer those. That is why the STL uses them. - Nick On 2/16/07, Petri Pitkanen <[EMAIL PROTECTED]> wrote: 2007/2/16, Nick Apperson <[EMAIL PROTECTED]>: > trouble. Also, the alternative is usually function pointers which have > atleast 50 times the overhead of a function object. Correct me if I'm > wrong. > > - Nick > function objects really cannot be 50 times more efficient as function pointer are rather efficient with very little overhead. Besides unless unless function object is small enough to be inlined it will be compiled as function pointer in many cases so there cannot be any efficiency difference - well unless function object get inlined that is. Petri ___ 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] Effective Go Library v0.101
2007/2/16, Nick Apperson <[EMAIL PROTECTED]>: trouble. Also, the alternative is usually function pointers which have atleast 50 times the overhead of a function object. Correct me if I'm wrong. - Nick function objects really cannot be 50 times more efficient as function pointer are rather efficient with very little overhead. Besides unless unless function object is small enough to be inlined it will be compiled as function pointer in many cases so there cannot be any efficiency difference - well unless function object get inlined that is. Petri ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
Re: [computer-go] Effective Go Library v0.101
C++ function objects have overhead? This is news to me... Any decent compiler can optimize these as well as a direct function call. Also because of the way that the code is generated using templates (as in machine language isn't generated until the actual call is reached), function bodies are visible to the compiler at compile time a larger percentage of the time which allows for better optimization. Ofcourse there are ways to break this rule, but it is like anything in C++, if you don't know how to use it for speed, you can get yourself into trouble. Also, the alternative is usually function pointers which have atleast 50 times the overhead of a function object. Correct me if I'm wrong. - Nick On 2/15/07, Jason House <[EMAIL PROTECTED]> wrote: Heikki Levanto wrote: > To get down to earth, I would like to look at the board at the end of > each playout, calculate something more than just win/loss, and pass that > info back to who ever called playout. One way to do that would be to > pass a function pointer and a (void?) pointer to playout, and have it > call back the function with the board, winner, and the void pointer. If > that sounds more like C than C++, it is because I am a C programmer. If > some other C++ idiom could do the same thing, all the better. > If you're going for more of a C++ library feel, function objects are the way to go. Function objects impose extra overhead but add a potential for a more generic adapter around other code that uses it. I have yet to convince myself of the benefit of C++ function objects for most applications. C++'s support for them is just too clunky in comparison to other C++ language features (or equivalent ones in other languages with built-in support). ___ 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] Effective Go Library v0.101
Heikki Levanto wrote: To get down to earth, I would like to look at the board at the end of each playout, calculate something more than just win/loss, and pass that info back to who ever called playout. One way to do that would be to pass a function pointer and a (void?) pointer to playout, and have it call back the function with the board, winner, and the void pointer. If that sounds more like C than C++, it is because I am a C programmer. If some other C++ idiom could do the same thing, all the better. If you're going for more of a C++ library feel, function objects are the way to go. Function objects impose extra overhead but add a potential for a more generic adapter around other code that uses it. I have yet to convince myself of the benefit of C++ function objects for most applications. C++'s support for them is just too clunky in comparison to other C++ language features (or equivalent ones in other languages with built-in support). ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
Re: [computer-go] Effective Go Library v0.101
On Thu, Feb 15, 2007 at 11:23:57AM +0100, ?ukasz Lew wrote: > I'm realistic, what matters is: what You have learned, does Your > program works. So just get the code and hack it as fast as You can to > get some effect asap, to feed Your motivation, to get more effect > fast, etc... Ok, I do that. Actually I have already started, and if my experiment shows anything, I will report here some day soon. Need a few spare days first to do the main part of the hacking, but (as usual) I am busy with work, life, universe, and everything... Thanks again for a good library! -Heikki -- Heikki Levanto "In Murphy We Turst" heikki (at) lsd (dot) dk ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
Re: [computer-go] Effective Go Library v0.101
The library is just a bunch of code and You can do whatever You want with it. I'm realistic, what matters is: what You have learned, does Your program works. So just get the code and hack it as fast as You can to get some effect asap, to feed Your motivation, to get more effect fast, etc... Concerning new versions ... it should be no big deal i guess. You can just copy some files and hack the copies. Another option is getting whole repository, so You can commit and branch locally: hg clone http://www.mimuw.edu.pl/~lew/hg/ cd libego hg commit (this is local commit) hg pull (then whenever You want to check for new version) But repository-solution may be too much for a less than few weeks of work, it will be just a burden. So just grab the source, do something and be happy :) Lukasz On 2/14/07, Heikki Levanto <[EMAIL PROTECTED]> wrote: On Wed, Feb 14, 2007 at 10:57:38PM +0100, ?ukasz Lew wrote: > Basically I wanted to implement a board in a hope that more people get > attracted to Computer Go. But now this is more or less accomplished. > So I decided to implement some kind of set canonical algorithms. > But only those most common, I do not intend to make another GnuGo :) > > I just started UCT, as majority voted for it. Maybe patterns will come next. > If You have something to propose, just go ahead :) I have a question about your philosophy. Do you mean us - the users of your library - to take the current version of the code, and start modifying it to our needs? Or do you want us to link with the library, so that we can upgrade to a later version without branching? I am asking because I would need a bit different playout routine. I could easily hack the library to do what I want, but that would in effect be a branch, and lead to maintenance problems later if/when you release a better version. I could also inherit from your classes, and override what I need. That would probably require a new header file, or something. Or I could abstract my needs into a more general interface, submit that as a patch, hope you accept it, and then use that. To get down to earth, I would like to look at the board at the end of each playout, calculate something more than just win/loss, and pass that info back to who ever called playout. One way to do that would be to pass a function pointer and a (void?) pointer to playout, and have it call back the function with the board, winner, and the void pointer. If that sounds more like C than C++, it is because I am a C programmer. If some other C++ idiom could do the same thing, all the better. Also, you have implemented the mercy rule in the playout code. If the library should be used without duplicating the code, this might be better left as a settable parameter. Like I said, I could easily write my own playout. But then I'd have to modify the gtp code to call that, and probably change a bit more here and there. In the end I would have forked your code, and when you release the next version, I would have to merge the changes in, and/or decide to go our separate ways. Perhaps I am worrying too much at such early state. I am just about considering to start my own project. But I'd like to do the right thing from the beginning. What do you think? Heikki -- Heikki Levanto "In Murphy We Turst" heikki (at) lsd (dot) dk ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/ ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
Re: [computer-go] Effective Go Library v0.101
On Wed, Feb 14, 2007 at 10:57:38PM +0100, ?ukasz Lew wrote: > Basically I wanted to implement a board in a hope that more people get > attracted to Computer Go. But now this is more or less accomplished. > So I decided to implement some kind of set canonical algorithms. > But only those most common, I do not intend to make another GnuGo :) > > I just started UCT, as majority voted for it. Maybe patterns will come next. > If You have something to propose, just go ahead :) I have a question about your philosophy. Do you mean us - the users of your library - to take the current version of the code, and start modifying it to our needs? Or do you want us to link with the library, so that we can upgrade to a later version without branching? I am asking because I would need a bit different playout routine. I could easily hack the library to do what I want, but that would in effect be a branch, and lead to maintenance problems later if/when you release a better version. I could also inherit from your classes, and override what I need. That would probably require a new header file, or something. Or I could abstract my needs into a more general interface, submit that as a patch, hope you accept it, and then use that. To get down to earth, I would like to look at the board at the end of each playout, calculate something more than just win/loss, and pass that info back to who ever called playout. One way to do that would be to pass a function pointer and a (void?) pointer to playout, and have it call back the function with the board, winner, and the void pointer. If that sounds more like C than C++, it is because I am a C programmer. If some other C++ idiom could do the same thing, all the better. Also, you have implemented the mercy rule in the playout code. If the library should be used without duplicating the code, this might be better left as a settable parameter. Like I said, I could easily write my own playout. But then I'd have to modify the gtp code to call that, and probably change a bit more here and there. In the end I would have forked your code, and when you release the next version, I would have to merge the changes in, and/or decide to go our separate ways. Perhaps I am worrying too much at such early state. I am just about considering to start my own project. But I'd like to do the right thing from the beginning. What do you think? Heikki -- Heikki Levanto "In Murphy We Turst" heikki (at) lsd (dot) dk ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
Re: [computer-go] Effective Go Library v0.101
On 2/14/07, Jason House <[EMAIL PROTECTED]> wrote: ?ukasz Lew wrote: > Generally http://en.wikipedia.org/wiki/Disjoint-set_data_structure > In my program it's a tree for each group of stones. In the root is > number of pseudoliberties. > Joining is cheap and checking group membership is cheap. > > Look at chain_t class. in board.cpp > > Best, > ?ukasz Lew I had done similar once upon a time in my bot and later moved away from the disjoint set approach because of the headache that undo created. Undo can be done efficiently exactly like in Gnu Go. Out of curiosity, is this library intended to support MC clients specifically or other types of searches (such as alpha-beta that tends to back up its search frequently? Basically I wanted to implement a board in a hope that more people get attracted to Computer Go. But now this is more or less accomplished. So I decided to implement some kind of set canonical algorithms. But only those most common, I do not intend to make another GnuGo :) I just started UCT, as majority voted for it. Maybe patterns will come next. If You have something to propose, just go ahead :) Lukasz ___ 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] Effective Go Library v0.101
?ukasz Lew wrote: Generally http://en.wikipedia.org/wiki/Disjoint-set_data_structure In my program it's a tree for each group of stones. In the root is number of pseudoliberties. Joining is cheap and checking group membership is cheap. Look at chain_t class. in board.cpp Best, ?ukasz Lew I had done similar once upon a time in my bot and later moved away from the disjoint set approach because of the headache that undo created. Out of curiosity, is this library intended to support MC clients specifically or other types of searches (such as alpha-beta that tends to back up its search frequently? ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
Re: [computer-go] Effective Go Library v0.101
On 2/13/07, Heikki Levanto <[EMAIL PROTECTED]> wrote: On Sun, Feb 04, 2007 at 02:13:33PM +0100, ?ukasz Lew wrote: > Optimizing and refactoring became my hobby, but it's too absorbing :) > It's time to add some features now. Just one question: Is the gtp support sufficient to play against other machines (if we ignore the rather trivial genmove code :-)? If not, adding the missing commands, even as dummies, would be a help for beginning programmers. Yes it is. Also, I notice that I can not use quarry (graphical interface for Go and Try GoGui. other games) to play against 'engine_opt'. Presumably it needs a few more gtp commands implemented. I will look into this, because if I am to write any sort of engine, I will want to be able to play agaist it. Will make a good warming-up exercise. Thanks again for a good, useful library. I have started to look into it, and once I got aroundthe namespaces and short names within, it looks reasonably clear. I will experiment with some ideas, and if anything useful comes out of them, I let you know. If I run into obvious improvements, I may even send a patch. Thanks :) Łukasz Regards Heikki -- Heikki Levanto "In Murphy We Turst" heikki (at) lsd (dot) dk ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
Re: [computer-go] Effective Go Library v0.101
Generally http://en.wikipedia.org/wiki/Disjoint-set_data_structure In my program it's a tree for each group of stones. In the root is number of pseudoliberties. Joining is cheap and checking group membership is cheap. Look at chain_t class. in board.cpp Best, Łukasz Lew On 2/13/07, Chris Fant <[EMAIL PROTECTED]> wrote: Does anyone know what "find-union algorithms" Lukasz is referring to in the README file? ___ 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] Effective Go Library v0.101
This was discussed on the list a while back. There's a good Wikipedia article: http://en.wikipedia.org/wiki/Disjoint-set_data_structure On 2/13/07, Chris Fant <[EMAIL PROTECTED]> wrote: Does anyone know what "find-union algorithms" Lukasz is referring to in the README file? ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
Re: [computer-go] Effective Go Library v0.101
Does anyone know what "find-union algorithms" Lukasz is referring to in the README file? ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
Re: [computer-go] Effective Go Library v0.101
On Sun, Feb 04, 2007 at 02:13:33PM +0100, ?ukasz Lew wrote: > Optimizing and refactoring became my hobby, but it's too absorbing :) > It's time to add some features now. Just one question: Is the gtp support sufficient to play against other machines (if we ignore the rather trivial genmove code :-)? If not, adding the missing commands, even as dummies, would be a help for beginning programmers. Also, I notice that I can not use quarry (graphical interface for Go and other games) to play against 'engine_opt'. Presumably it needs a few more gtp commands implemented. I will look into this, because if I am to write any sort of engine, I will want to be able to play agaist it. Will make a good warming-up exercise. Thanks again for a good, useful library. I have started to look into it, and once I got aroundthe namespaces and short names within, it looks reasonably clear. I will experiment with some ideas, and if anything useful comes out of them, I let you know. If I run into obvious improvements, I may even send a patch. Regards Heikki -- Heikki Levanto "In Murphy We Turst" heikki (at) lsd (dot) dk ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
Re: [computer-go] Effective Go Library v0.101
On 2/7/07, steve uurtamo <[EMAIL PROTECTED]> wrote:
> And of course don't forget about this no_variable_in_for thing...
i'll have to read up on what you're describing.
The following pseudocode block
for (int i = 0; i < 10; ++i) {
... code ...
}
// i's lifetime ends after the for loop does
is valid in just about any version of C++ and in the 1999 ISO C standard
(also known as C99), but it is not valid in most older C standards. (Some
older versions of gcc would accept this code but assign the wrong lifetime
(according to the standard) to variable i. If you want to test this code
with gcc, then use the -std=c99 flag, which, as of quite recently at least,
was not enabled by default.) There are at least a couple other C++-isms --
offhand, the // single-line comment form and variable declarations in the
middle of code blocks come to mind -- that are also valid in C99 but invalid
in at least some of the older C standards.
I'm not trying to run off on a language standards tangent! I just feared
that we might be headed towards one anyway, and I wanted to make sure the
information in it was not 8 years out of date.
Sorry, now back to go (I hope)...
___
computer-go mailing list
computer-go@computer-go.org
http://www.computer-go.org/mailman/listinfo/computer-go/
Re: [computer-go] Effective Go Library v0.101
> And of course don't forget about this no_variable_in_for thing... > Of course no printing on streams, i'll have to read up on what you're describing. > A lot of pain. > A LOT. there aren't too many lines of code, right? > Maybe You prefer D? eh, i prefer C. :) i'll take a look and see if i can make some headway. s. Do you Yahoo!? Everyone is raving about the all-new Yahoo! Mail beta. http://new.mail.yahoo.com ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
Re: [computer-go] Effective Go Library v0.101
There is nothing inherently cplusplusic, You can change class to struct (provided that Your compiler supports functions in structs). Add prefix player_ to every function in player:: namespace. And of course don't forget about this no_variable_in_for thing... Of course no printing on streams, etc etc etc. A lot of pain. A LOT. Maybe You prefer D? Łukasz On 2/5/07, steve uurtamo <[EMAIL PROTECTED]> wrote: has anyone tried writing a C interface to these functions? any suggestions about how to start? i love the idea of the library, but do not love the idea of writing C++. thanks, s. - Original Message From: Łukasz Lew <[EMAIL PROTECTED]> To: computer-go Sent: Monday, February 5, 2007 2:41:23 AM Subject: Re: [computer-go] Effective Go Library v0.101 Effective Go Library: http://www.mimuw.edu.pl/~lew/ Don't pick lemons. See all the new 2007 cars at Yahoo! Autos. http://autos.yahoo.com/new_cars.html ___ 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] Effective Go Library v0.101
has anyone tried writing a C interface to these functions? any suggestions about how to start? i love the idea of the library, but do not love the idea of writing C++. thanks, s. - Original Message From: Łukasz Lew <[EMAIL PROTECTED]> To: computer-go Sent: Monday, February 5, 2007 2:41:23 AM Subject: Re: [computer-go] Effective Go Library v0.101 Effective Go Library: http://www.mimuw.edu.pl/~lew/ Don't pick lemons. See all the new 2007 cars at Yahoo! Autos. http://autos.yahoo.com/new_cars.html ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
Re: [computer-go] Effective Go Library v0.101
Effective Go Library: http://www.mimuw.edu.pl/~lew/ On 2/4/07, David Doshay <[EMAIL PROTECTED]> wrote: UCT. Cheers, David On 4, Feb 2007, at 5:13 AM, Łukasz Lew wrote: > It's time to add some features now. > > I consider 3 things: > - liberties tracing > - UCT tree search > - pattern tracing > > Which feature You would like to see implemented? > ___ 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] Effective Go Library v0.101
UCT. Cheers, David On 4, Feb 2007, at 5:13 AM, Łukasz Lew wrote: It's time to add some features now. I consider 3 things: - liberties tracing - UCT tree search - pattern tracing Which feature You would like to see implemented? ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
Re: [computer-go] Effective Go Library v0.101
Le Sun, 4 Feb 2007 14:13:33 +0100 "Lukasz Lew" <[EMAIL PROTECTED]> a écrit : > Hi, > > EGB 0.101 is the last "performance" release: > 50 kpps on 1.4 GHz and > 80 kpps on 2.2 GHz. > > Optimizing and refactoring became my hobby, but it's too absorbing :) > It's time to add some features now. > > I consider 3 things: > - liberties tracing > - UCT tree search > - pattern tracing > > Which feature You would like to see implemented? > > Do You have any idea how to implement liberties efficiently? No, but I have a question : where can this library be found ? \bye -- Nicolas FRANCOIS http://nicolas.francois.free.fr A TRUE Klingon programmer does NOT comment his code ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
[computer-go] Effective Go Library v0.101
Hi, EGB 0.101 is the last "performance" release: 50 kpps on 1.4 GHz and 80 kpps on 2.2 GHz. Optimizing and refactoring became my hobby, but it's too absorbing :) It's time to add some features now. I consider 3 things: - liberties tracing - UCT tree search - pattern tracing Which feature You would like to see implemented? Do You have any idea how to implement liberties efficiently? Best Regards, Łukasz ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
