Re: [computer-go] Re: Lisp time

[Nick Apperson]

Also, with todays chips if you "optimize" like that it will confuse the
processor and your performance will drop faster than you can imagine.  In
fact, under linux I know (probably other OSes as well) you can't actually
use the code segment as the data segment.  Optimizing today is based on
combining instructions in such a way that all the parts of the processor are
fully utilized.  I don't feel like getting into it, but if you are curious
download the optimization manual off intel's website.  One "high level"
optimization thing is to make your code predictable.  Branches are still the
biggest performance killer (not counting waiting on non-memory data).

On Dec 16, 2007 9:19 PM, Heikki Levanto <[EMAIL PROTECTED]> wrote:

> On Sat, Dec 15, 2007 at 03:00:02AM +1800, Nick Apperson wrote:
> >
> > In theory, and ONLY in theory, assembly is the fastest programming
> > language.
>
> I do agree with most of what you said, but I have to squeeze in a comment
> that assembly is not necessarily the most optimized way to write code,
> when
> it really comes to it. If you *really* have to go for it, you need to be
> aware of the binary expression of every instruction... I have (once!) -
> many
> many years ago - optimized some assembly code where I reused the same
> bytes
> as instructions, jump offsets,  and data, carefully placing the code on
> the
> right address so that this trick would work. This might have been possible
> with a good assembler, but at that time I did no have one for that CPU, so
> I
> was working directly in hexadecimal.
>
> With modern processors, assemblers, and compilers, things are different.
> And
> today, nobody will take the time to optimize on that level - which is good
> enough. But in theory...
>
>  - 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] Re: Lisp time

[Nick Apperson]

Look,

 I love C++ and I'd love to say look I told you all, C++ is the fastest,
but frankly it just doesn't work like that.  When we come to a point where
every programmer writes the fastest possible code their language could
create then we have some kind of a comparison.

C++ has a philosophy that you don't pay for what you don't use, but there is
not a single construct in C++ that can't be built in C with enough code
(virtual functions are a grey area since the compiler can better optimizer
them over direct function pointers... but that is irrelevant anyway).
Sometimes the amount of code is rediculous and frequently to obtain the same
speeds one has to sacrifice portability and reusability.

In theory, and ONLY in theory, assembly is the fastest programming
language.  The fact is, in a sufficiently complex program, there will always
be parts of the program left to further optimize.  I would assert that for a
complex program, an assembly programmer and a C++ programmer both writing
the same program and spending the same amount of time will leave the
assembly version slower always.  It is not because assembly is a slower
language, it is because if the assembly guy spends another 1000 hours
optimizing, so will the C++ guy and certainly their are exceptions, but in
general, for most problems and for reasonable amounts of time spent, the C++
code will be faster.

C++ is "faster" than C because the STL (and other generic code) allows the
programmer to spend their precious time optimizing the bottleneck and using
a very fast default for less critical places.  For a sufficiently small
program however I will wager that given enough time, C will be exactly the
same speed as C++ if the programmers involved are both good.

When will you people learn the limits of benchmarks?  They are only useful
for showing how worthless Java is... nothing else.  Got it?

- Nick

On Dec 15, 2007 2:44 AM, Darren Cook <[EMAIL PROTECTED]> wrote:

> >> I thinks it's very difficult to outperform C since C really is just
> >> about at the level of assembly language.
> >
> > No, in special cases it's not that hard to outperform C, because the
> > language spec dictates some not so efficient details. C has an ABI and
> > it's specification is optimized for the general case.
>
> Stefan, judging by this site (which I posted some links from yesterday)
> your intuition is correct:
>  http://shootout.alioth.debian.org/
>
> Overall C comes in 2nd, 10% slower than C++ (due to extra hints to the
> compiler I assume). But C/C++ are not the top of every benchmark. E.g.
> http://shootout.alioth.debian.org/gp4/benchmark.php?test=sumcol&lang=all
>
> Darren
>
>
> --
> Darren Cook
> http://dcook.org/mlsn/ (English-Japanese-German-Chinese free dictionary)
> http://dcook.org/work/ (About me and my work)
> http://dcook.org/work/charts/  (My flash charting demos)
> ___
> 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] Lisp time

[Nick Apperson]

Thanks everyone for being really helpful.  I think I've decided to go with
Scheme I think.  It seems like it is a little friendlier to the newbie.  It
seems to me like in some ways Scheme is less feature bloated than common
lisp.  I'm sure those features are really useful, but I feel it is good to
learn the basics of a language then learn the standard functions that come
with it rather than the other way around.  I'll keep you all updated when I
actually produce something that plays better than random.

- Nick

On Dec 13, 2007 11:32 PM, David Doshay <[EMAIL PROTECTED]> wrote:

> Because I am just starting with Lisp, I find this an easy place to
> start:
>
>http://gigamonkeys.com/book/index.html
>
> In the intro is the line:
> For example, one vacation, having a week or so to hack Lisp, I
> decided to try writing a version of a program--a system for breeding
> genetic algorithms to play the game of Go--that I had written early
> in my career as a Java programmer.
>
>  From this set of pages, here is a link to an array of Lisp choices:
>
>http://gigamonkeys.com/book/lispbox/
>
>
> Cheers,
> David
>
>
>
> On 12, Dec 2007, at 8:34 AM, David Doshay wrote:
>
> > I am presently engaged in the same search, although I run on Macs
> > and am willing to accept either a GUI or a command-line
> > environment. GUI debuggers can be handy.
> >
> > Cheers,
> > David
> >
> >
> >
> > On 12, Dec 2007, at 7:09 PM, Nick Apperson wrote:
> >
> >> I've been (and still am) a die hard supporter of C++, but since I
> >> program in C++ for work (we develop gamelike software) I get tired
> >> of C++ day in and out.  I'd also like to push myself to learn some
> >> new things.
> >>
> >> Lisp seems to me like a language I could really come to respect.
> >> I run linux (no windows, period) and I am comfortable with command-
> >> line if I need to be.  Anyway, I'm trying to figure out what the
> >> best way would be to learn lisp so that I can begin working on a
> >> computer go program in it.  I can't even figure out what the right
> >> dielect would be for computer go.
> >>
> >> Any of you out there using lisp want to maybe point me in the
> >> right direction for how to learn this language as it applies to
> >> writing a go program?  Thanks.
> >>
> >> - Nick
> >> ___
> >> 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/

[computer-go] Lisp time

[Nick Apperson]

I've been (and still am) a die hard supporter of C++, but since I program in
C++ for work (we develop gamelike software) I get tired of C++ day in and
out.  I'd also like to push myself to learn some new things.

Lisp seems to me like a language I could really come to respect.  I run
linux (no windows, period) and I am comfortable with command-line if I need
to be.  Anyway, I'm trying to figure out what the best way would be to learn
lisp so that I can begin working on a computer go program in it.  I can't
even figure out what the right dielect would be for computer go.

Any of you out there using lisp want to maybe point me in the right
direction for how to learn this language as it applies to writing a go
program?  Thanks.

- Nick
___
computer-go mailing list
computer-go@computer-go.org
http://www.computer-go.org/mailman/listinfo/computer-go/

Re: [computer-go] Re: compiler optimizations

[Nick Apperson]

I agree with you 100%.  You embody the methodology behind C++.  The only
problem I can see with adding something like that to C++ is that many times
the compiler can't determine at compile time if a value is violating the
contract.  If the feature were added to C++, the programmer would have to be
able to implicitly cast a value to the contract value datatype without
having the compiler generate any actual checks.  That is then a "you don't
pay for what you don't use" way of doing things...  the C++ way.

On Nov 22, 2007 6:40 PM, Darren Cook <[EMAIL PROTECTED]> wrote:

> > Arguments about the quality of compiler optimizations vs. hand coding
> > are pointless, because programmers optimize programs in ways that
> compilers
> > are (correctly) forbidden to do; by changing the algorithm.
> >
> > For example, if I happen to know "x" will always be an  integer
> > from 0 to 359, I can replace sin(x) with a table lookup.  No compiler
> > can ever do that, even if I include assert(x>=0 && x<360) in the code
> > somewhere (which would be a good idea even if I "know" it).
>
> Unless the assert is part of the language, such as in Eiffel and other
> languages with contracts. (Though I'm not aware of any language that
> uses contracts in the optimization stage.)
>
> I tried (not hard enough, and failed) to push for design-by-contract
> extensions into C++ TR2, and even the author of the proposal seemed
> surprised when I said better optimization was a key feature: it seems
> everybody sees design by contract as all about safety. But it is about
> describing the problem more accurately to the computer so that it can
> not just find more bugs at compile-time but also so it can generate
> better code at compile-time.
>
> Darren
>
>
> --
> Darren Cook
> http://dcook.org/mlsn/ (English-Japanese-German-Chinese free dictionary)
> http://dcook.org/work/ (About me and my work)
> http://dcook.org/work/charts/  (My flash charting demos)
> ___
> 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] Drunken sailor on payday

[Nick Apperson]

Actually, putting all the code in headers helps with function inlining more
than anything.  The virtual function stuff is very complicated because
usually code can be linked in at runtime that adds new functionality (i.e. a
new derived class).

Make no mistake, virtual functions are VERY expensive.  I'm just saying
there are instances where they are a faster than function pointers.  The
reverse is also true sometimes as well.  My point was only that adding new
features to a language that don't incur overhead when they aren't used can't
possibly make a language slower which is why C++ is not a slower language
than C.

As far as the assembler stuff.  I have written assembly code before.  There
are several reasons why compilers are better at it in my opinion:

1) They know the rules of the chip much better than people.
2) The rules change, all that is required is a recompile to optimize for the
new chip.  If you are using direct assembly and you optimized it well for
one chip, it won't be best for the next.
3) Correct optimizing at the machine code level can be calculated very
precisely.  There is much less of an art in organizing instructions and
selecting specific ones.  The reasons why one choice is better than another
are very easy to see, but are extremely computationally intensive.
Computers excel at these types of computations.

That said, there are times when I am programming and I know that my compiler
won't know "the fastest way" to implement something in machine code.  If
there was a good way to implement inline assembly into code, it would be
worth it.  Sadly, inline assembly breaks up the optimization of the code
around it enough that it usually isn't worth it.

Just my thoughts,
Nick

On Nov 22, 2007 9:41 PM, Heikki Levanto <[EMAIL PROTECTED]> wrote:

> On Wed, Nov 21, 2007 at 09:29:42PM +, Stuart A. Yeates wrote:
> > A C++ compiler can make those kinds of assumptions if the object is
> > created within the current compilation unit and can not be overwritten
> > from outside it. There are a whole class of optimizations in Java, C
> > and C++ which can only be applied under these circumstances, which
> > rely on concepts of scope. Whether or not a particular compiler uses
> > these optimizations in a particular case is another matter.
>
> Aha - that must be why LibEGO includes all source files from the mail
> file,
> instead of compiling each one separately.
>
> -H
>
> --
> 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] Drunken sailor on payday

[Nick Apperson]

sure thing:

--

struct foo {
  // some stuff gets executed
  virtual void do_something(somestruct &s); // base case executed by default
};

struct foo_foo : foo {
  // some stuff gets executed
};

struct foo_bar : foo {
  // some stuff gets executed
  virtual void do_something(somestruct &s); // special case
};

So then if we have say:

foo *f;
somestruct s;

// ... some code that sets f to something and changes s

f->do_something(s);



So now when the compiler is optimizing the code, it will optimize for the
base case of foo::do_something by default unless it has information that is
even better.  If our code instead read with f as a function pointer, the
compiler (assuming it can't determine the value) won't have a base case.


On Nov 22, 2007 12:18 PM, Petr Baudis <[EMAIL PROTECTED]> wrote:

> On Thu, Nov 22, 2007 at 12:04:53PM +1800, Nick Apperson wrote:
> > right... well C++ does have this using virtual methods.  I meant to add
> that
> > part.
>
> I'm sorry, I still don't get this - what do virtual methods have to do
> with branch prediction? Can you elaborate, please?
>
> --
>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/
>
___
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

[Nick Apperson]

right... well C++ does have this using virtual methods.  I meant to add that
part.

C++ also has templates which while they theoretically don't add any
performance.  Practically speaking they add tons because you don't have to
split your optimization time between 10 or more versions of the same
function.  I don't buy the stuff people throw down about programmer
productiveity being more important than raw speed, but if you are starting
at the same speed and it is easier to optimize you will likely get a faster
program.

And I totally agree with you that things can get out of hand fast.  I'd say
C++ is probably one of the hardest languages out there.  Templates can make
code blazingly fast in the general case, but writing them to work well can
be extremely challenging.  Multiple inheritence is somewhat easier to me,
but it can definately trip people up really quickly if they design their
code poorly.  There is a saying I think... but yeah C++ is not made for
people that aren't really good programmers.  No training wheels.

On Nov 22, 2007 11:51 AM, Petr Baudis <[EMAIL PROTECTED]> wrote:

> On Thu, Nov 22, 2007 at 11:36:58AM +1800, Nick Apperson wrote:
> > Thanks for a great read there first of all.
> >
> > But...  and this is something I see time and again and I must admit I
> don't
> > really understand.  What makes C faster than C++?  I feel like C++ is
> all
> > about you don't pay for what you don't use.
>
> My personal stance is that the extra cruft and basically mysterious
> behaviour in some cases (I know many programmers and even some gcc
> developers, and only one or maybe two who can say that they completely
> understand identifier lookup mechanism in C++) is not worth the extra
> features you are getting. I believe C gives you all the constructs you
> really need and frequently the extra C++ constructs just reduce
> readability. But this is just question of taste and many people will
> like the extra C++ features and that's really ok, too.
>
> I think C++ is much like Perl. Many oh-so-cool features and constructs,
> but things can get out of hand real fast. ;-)
>
> (And I do like Perl. Including the cool features and constructs. But
> Perl and C are pretty much _the_ two languages I use and I never had too
> much motivation to mix the cool features with low level code as in C++.)
>
> > Furthermore, I feel that C++
> > has at least one feature that in a one certain special case will result
> in
> > faster code.  While I generally would say avoid indirect calls where
> > performance is critical (for obvious reasons) thereare certain times
> when it
> > is faster than climbing through tons of logic.  For these cases, if one
> > indirect branch is reasonably likely the optimization most recent x86
> chips
> > take with static branch prediction is to "assume the [indirect] branch
> is
> > not taken" which might seem wierd but makes sense since the chip can't
> > easily guess this information statically.  Good compilers will usually
> write
> > the most commonly jumped to location after the indirect uncomditional
> jump
> > instruction s
> >
> > JMP  [EBX]
> > JMP  default_function
> >
> > is output.  Unfortunately, C doesnt' have a way to specify this base
> case.
> > Trying to code this yourself won't really work either because a C
> compiler
> > is likely to notice that the branch is unconditional and remove you
> branch
> > that occurs after anyway  Which would be if you were using the low
> level
> > jumping routines anyhow.  There are a couple other features as well.
>
> This is indeed not standardized but C compilers tend to have their own
> extensions for this. Many codebases have likely(a) and unlikely(a) macros
> they use in conditions which are defined to expand to
>
>__builtin_expect(!!(a), 1)
>
> or 0 respectively in case the code is compiled by gcc. I'd expect MSVC
> to have some similar way to hint this.
>
> (gcc also supports -fprofile-generate and -fprofile-use, which is pretty
> cool too - gcc will re-optimize the binary based on profiling
> information gathered from a test run of the program. It can be quite a
> non-trivial boost.)
>
>
> However, I don't get how is this related to C vs C++? AFAIK C++ does not
> have an official way to hint the compiler about branching probability
> either?
>
> --
>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/
>
___
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

[Nick Apperson]

 are that you take other shortcuts  for the "long term
> good".
>
> The problem is that you never stop taking the hit.You say, in 18
> months computers will be 2X faster, so it "doesn't matter."   This is
> the stupidest thing I keep hearing. In 18 months you will have a
> faster computer,  but your program will STILL be a crippled program that
> sucks.Getting a faster wheelchair doesn't stop you from being
> crippled.The drunken sailor borrows money thinking that his next
> paycheck will cover these debts but forgets he will have to borrow money
> again.
>
> When I develop my go program,  the vast majority of the development time
> is spent by the computer, not me.I need to optimize the computers
> time, not my time.   Whatever the program can do in 1 minute,  I would
> like to see happen in 30 seconds. If I had a network of workstations
> my productivity (as measured by program strength) would improve
> significantly because I could try a lot more thing in the same amount of
> time.But even if I had such a network,   I wouldn't willingly
> cripple it by throwing away half the power.
>
> In fact, the whole concept is not to optimize what YOU do, it's to
> optimize what the computer does.   If you are not stingy about the
> performance (playing strength) right from the start you are already
> starting from the wrong mentality. That's probably why the best
> programs are in C or assembler - these programmers see performance as
> part of the overall whole - not something that is "in their way."
> They don't romanticize their language or the tools they use,  they are
> focused on the problem and tend to make the most logical choices, not
> the sexiest ones.
>
> My advice when this question comes up (which language for go programmer)
> is to first ask,  what do you hope to achieve?If you want to build a
> high performance go program,  anything other than C or assembler is like
> tying your hand behind your back. If you do this only as a hobby and
> have no aspirations (just for fun and pleasure) then by all means, you
> will be much happier in a high level language.
>
>
> - Don
>
>
>
>
>
> Raymond Wold wrote:
> > Nick Apperson wrote:
> >
> >> But, to be fair, I totally agree that compiling python or ruby would
> >> give
> >> you noticable speed gains.  And as always, speed comparisons are only
> >> useful
> >> in context.  In terms of go programming if you are prototyping use
> >> whatever the hell you want.  If you are finishing something off,
> >> don't waste
> >> my time with any of those slow languages (that includes java and c#).
> >>
> >>
> > I would posit that coding go, we are _always_ prototyping.
> > ___
> > 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] Language

[Nick Apperson]

hahaha, good point... good point.  Although I still will stick with C++, I
really ought to learn Lisp I think.

On Nov 22, 2007 2:43 AM, Raymond Wold <[EMAIL PROTECTED]> wrote:

> Nick Apperson wrote:
>
> >But, to be fair, I totally agree that compiling python or ruby would give
> >you noticable speed gains.  And as always, speed comparisons are only
> useful
> >in context.  In terms of go programming if you are prototyping use
> >whatever the hell you want.  If you are finishing something off, don't
> waste
> >my time with any of those slow languages (that includes java and c#).
> >
> >
> I would posit that coding go, we are _always_ prototyping.
> ___
> 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

[Nick Apperson]

I think people that call java interpretted are somewhat misinformed.  You
certianly can interpret it or any other language for that matter... but that
is not what is usually done.  It is usually run through a JIT *compiler* so
that it is compiled.  Interpretted is very different.  I've written both
compilers and interpretters.  The way I alway differentiated is this: if
actual machine language that represents the program is getting executed then
it is compiled if machine language that is parsing bytecodes or sourcecode
or anything else like that is getting run then it is interpretted.

Java certainly supports both modes, but what I said is true.  If you are
executing a loop repeatedly the actual code gets converted into machine
language that represents the actual code.  It is not parsing bytecodes
anymore at this point.

You are right to call me out on my weakly typed "bullshit" as you say.  I
really meant dynamically typed languages are going to be slower all else
equal.  Besides, C in an exception because while it is weakly typed, all the
operations are undefined which is totally different from python or ruby
which handles these cases.

As far as your analysis of relative speeds...  I would say that at the end
of the day, if you are a perfect programmer you can obviously obtain the
best results with assembly (but who has the time... granted I did back in
the day).  But, practically speaking, C++ is just as fast (and for most
coders faster since they don't know how to optimize for their chip).  C has
only one feature I know of that could potentially allow it to be faster (the
restrict keyword).  While C++ has several features that allow for more speed
in certain circumstances than C (this is not to say that you can't easily
make a C++ way slower as evidenced by most C++ programmers out there).

As far as ruby and python though...  These languages are much more difficult
for a compiler to effectively optimize.  In theory, a perfect compiler given
enough time would optimize all languages to the same machine code if the
program does the same thing.  In reality however, in python and ruby the
programmer specifies less information to the compiler which in turn makes it
considerably harder for the compiler to optimize.  But yes, in theory these
languages could be much much faster.  In reality...  it is not going to
happen until we are all obsolete anyway because frankly compilers will have
to understand the program and a very high level to do the necessary
optimizations.

But, to be fair, I totally agree that compiling python or ruby would give
you noticable speed gains.  And as always, speed comparisons are only useful
in context.  In terms of go programming if you are prototyping use
whatever the hell you want.  If you are finishing something off, don't waste
my time with any of those slow languages (that includes java and c#).

- Nick

On Nov 22, 2007 1:44 AM, Stefan Nobis <[EMAIL PROTECTED]> wrote:

> "Nick Apperson" <[EMAIL PROTECTED]> writes:
>
> > Java and C# are both compiled at some point if the same loop is
>
> At some point everything has to be translated to machine code. But
> Java, C#, Ruby etc. are doing this at execution time -- that what most
> people call a interpreter.
>
> You are right, the interpreters of Java and C# have got quite some
> good optimizations, like the JIT (one could say: interpreter
> cache). Python and Ruby lack these optimizations today.
>
> > But, compiling weakly typed languages is unlikely to give a big
> > performance boost and could even hurt it a bit by making large code
>
> Bullshit. C is weakly typed, Python and Ruby have a dynamic type
> system. Two completley different things.
>
> And there are languages like Smalltalk or Scheme or Common Lisp with
> dynamic type systems that are compiled to native machine code. And
> there are big performance boost compared to the interpreted code and
> you can get a performance comparable to C and fast than Java or C#
> with these languages.
>
> So this is quite possible to do for Python or Ruby, but it seems there
> is not enough interest or man-power or knowledge in those communities
> to do it today. It's that simple.
>
> --
> Until the next mail...,
> Stefan.
>
> ___
> 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

[Nick Apperson]

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.

In theory, ruby and python could also be compiled, it just isn't implemented
that way.  But, compiling weakly typed languages is unlikely to give a big
performance boost and could even hurt it a bit by making large code (if the
compiler was not good).  If compilers were much smarter though, perhaps
python and ruby would be able to be compiled and get a signifigant
performance boost.

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). The main reason is that Ruby is not
> very good optimized -- AFAIK during most of the history of Ruby,
> running performance was not one of the main objectives. Recently I
> overheard that this changes these days.
>
> Python has much the same problem (not too much effort in high
> performance interpreters as compared for example to Java or C#).
>
> --
> Until the next mail...,
> Stefan.
>
> ___
> 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

[Nick Apperson]

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 go

Re: [computer-go] Language

[Nick Apperson]

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] Language

[Nick Apperson]

hahaha

one problem though... i can't easily determine the number of letters that
are inside the parenthesis...
maybe this is better:

XML

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:
> >
> >
> >
> > Then it will much more readable - which is one of the strengths of xml.
>
> I don't like XML tags without attributes:
>
> while XML ;
>
> 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/
>
___
computer-go mailing list
computer-go@computer-go.org
http://www.computer-go.org/mailman/listinfo/computer-go/

Re: [computer-go] Language

[Nick Apperson]

Yeah,

I've only dabbled in Lisp, but it seems like a great language to me.  It
is on my list of languages to learn.  I couldn't agree with you more about
Java and C# being about prohibition.  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 stray from Lisp mainly
because it isn't used as much as C++.  But I do respect those that use it.

- Nick

On Nov 13, 2007 3:10 PM, Stefan Nobis <[EMAIL PROTECTED]> wrote:

> "Nick Apperson" <[EMAIL PROTECTED]> writes:
>
> > And I don't htink I missed the point about productivity.  I've heard
> > that argument time and again.  That is fine.  I personally find that
> > with the STL in C++ and with the ability to write my own templates,
> > I can write algorithms in fewer lines of code that in Java.
>
> Wrong comparisson: I loathe Java. Compare to something like Common
> Lisp (or some Scheme like PLT Scheme or Haskell or Erlang -- hey, here
> are quite some guys trying to distribute the go engine over a cluster:
> for this Erlang seems to be a really good choice).
>
> C# and Java are all about rules and prohibition. Other languages like
> Common Lisp are like C and C++ more about freedom and flexibility.
>
> --
> Until the next mail...,
> Stefan.
> ___
> 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

[Nick Apperson]

I already mentioned that reference counting is not enough for GC...  That I
know.  I personally don't user reference counting very often.  The most
common case being a case where a resource doesn't itself point to anything.
That way I know it won't form a loop.  But usually, I just don't use it at
all.

And I don't htink I missed the point about productivity.  I've heard that
argument time and again.  That is fine.  I personally find that with the STL
in C++ and with the ability to write my own templates, I can write
algorithms in fewer lines of code that in Java.  I also can force users of
library code to use my code in specific ways and limit them more with C++.
I find that a library written in C++ can be much tighter than in Java which
prevents debugging later.  I don't find that freeing memory is really
something that takes much programming effort, but if it is something that
slows you down a lot, I can understand that is might hurt your
productivity.  For me, not having templates would slow me down tons.  For
me, not being to overload operators would slow me down tons.  Yes, these
things can be misused; Yes, there is a learning curve; But, I've already
learned that stuff and most of my time is spent designing how classes will
work.  Many times the designs I come up with would not work in Java without
signifigantly more code.  They are also frequently more object oriented than
what is possible with Java.  But that is fine, and it is why there are
multiple languages.  I don't think that Java is a bad language for
everything, but for what I do with my skills, it is not what I'm most
productive with.

On Nov 13, 2007 2:36 PM, Stefan Nobis <[EMAIL PROTECTED]> wrote:

> "Nick Apperson" <[EMAIL PROTECTED]> writes:
>
> > Reference counting and copy on write.
>
> Do you know that there's much more to garbage collection than
> reference counting and that reference counting has some major
> drawbacks? There are even hard real time capable garbage collectors
> out there.
>
> > But I'll be damned if Java takes over the world because there are
> > programmers that don't know when they need to use garbage
> > collection.  If you can't avoid memory leaks, fine, don't use C++ or
> > C, but don't blame the language.  You could use garbage collection
> > if you need it; don't make us all stoop to your level of competency
> > and don't try and claim that your language is just as fast when it
> > isn't.
>
> You miss the point: Using languages with GC is not about programmers
> who can't avoid memory leaks. It's not about ability, it's about
> productivity. If the only reason you don't use assembler is that with
> C your code is easier to port to a new processor I think you won't
> understand, but there are languages that are *much* more expressive
> (in the sense that an problem/algorithm is much more compact and
> readable to write down) than C. Yes, this comes at a cost, but not a
> very high cost and on the pro side you have a (much?) higher
> productivity (and maybe even more maintainable code).
>
> Java and C# are not that interesting, but even as someone who really
> dislikes these languages one has to admit that the default libraries
> are a strong argument in favor of these platforms. I personally really
> like Common Lisp and if I try I get quite comparable performance to C
> (maybe 20-60% off). But I perceive the code so much more readable (and
> maintainance is very important to me), that other aspects lose in
> value. I don't use Common Lisp because I'm not capable to write error
> free C code. For me writing code in Common Lisp is the most natural
> way to express my thoughts to a computer, it's really fun.
>
> Performance is really an important aspect in developing software and
> should be considered from the very beginning on. But it's not the only
> important aspect (and the choice of the language is not the only way
> to influence the overall performance) and often it's hard to balance
> all these aspects and you have to make trade offs. All these trade
> offs have different pros and cons and in most cases the choice is not
> evident even for really brilliant people.
>
> So go on, try new languages, try new ways to express yourself and have
> fun. :)
>
> --
> Until the next mail...,
> Stefan.
> ___
> 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

[Nick Apperson]

I'd also say that Lisp seems like a great choice.  I'm happy to see that C++
has been adding support for all the metaprogramming because that is what is
going to really matter in the future I think and it is why Lisp is such a
great language.

On Nov 13, 2007 2:13 PM, Chris Fant <[EMAIL PROTECTED]> wrote:

> I used Lisp a little bit in college and I enjoyed it.  And you are not
> the first person to mention that it is a good fit for Go.  Thanks for
> everyone's comments and thanks for not being hostile to each other on
> this touchy subject.  Turns out we CAN all just get along.
>
>
> On Nov 13, 2007 2:59 PM, Stefan Nobis <[EMAIL PROTECTED]> wrote:
> > "Chris Fant" <[EMAIL PROTECTED]> writes:
> >
> > > I would like some language recommendations.
> >
> > So I would suggest Common Lisp: The programmable programming
> > language. I think it's the single most flexible language -- you get
> > everything, from imperative over object-oriented to functional and
> > declarative paradigm, from very low level with all the bit twiddling
> > to very abstract ways (a complete prolog like inference engine with
> > quite reasonable performance in just about 100 lines of code).
> >
> > Oh, yes, and quite good interfacing to C.
> >
> > BTW the performace is really good (compared to Java, C# and the like)
> > and in special cases sometimes even better than C. Most Common Lisp
> > implementations compile to native code. There are free and open source
> > as well as commercial compilers and IDEs available.
> >
> > --
> > Until the next mail...,
> > Stefan.
> >
> > ___
> > 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] Language

[Nick Apperson]

Willaim Harold Newman: I actually already addressed this concern earlier
when I said "If you don't directly use the heap in C++ ( i.e. you use the
smart pointer class) you don't have to worry about garbage collection
(except if you make a circular list)."


As far as the other stuff you said, I'd say it is generally pretty fair.  I
would consider Java more if it added in the things that really help me to be
productive.  I think many people program in a subset of C++.  They don't use
metaprogramming to it fullest potential, they don't use multiple
inheritence, they don't use the other advanced idioms avaliable in C++.  I
can understand why these people might prefer Java.  I write lots of code in
C++ that saves me tons of development time that simply couldn't be written
in Java.  So it really depends I think on what you use.  For me, I'm more
productive in C++.

Nick Apperson: You write as though garbage collection is "reference
> counting and copy on write." You are in good company, lots of very
> smart people have arrived at that conclusion over the years, enough of
> them that even decades ago it was a cliche that people joked about
> (see "Moon instructs a student" at
> <http://catb.org/jargon/html/koans.html#id3141202>). And despite that
> cliche, the idea got built into the "garbage collection" in languages
> like Perl. Alas, it is basically incorrect: at least, you need to
> beware of important cases where it breaks down. In particular, it is
> easy to cause memory leaks in a reference counting scheme by setting
> up cyclic references. And alas, not all problem domains make it
> natural to avoid cyclic references. You seem to be used to problem
> domains which feature a clear notion of which object owns which
> object, and that lets you avoid cyclic references by setting up a
> directed acyclic graph of ownership relationships. But not all
> problems are like that. In Go, consider a graph representing the cycle
> of three or more board positions which make up a ko fight. If there
> are records representing representing those board positions and
> referring to each other, which record owns which? Or for another
> problem domain, see
> <http://www.perl.com/pub/a/2002/08/07/proxyobject.html>. For simple
> cases like that, special-purpose hacks suffice to work around the
> problem. But as data structures get more complicated, special-purpose
> hacks scale poorly, while true GC continues to Just Work.
>
___
computer-go mailing list
computer-go@computer-go.org
http://www.computer-go.org/mailman/listinfo/computer-go/

Re: [computer-go] Language

[Nick Apperson]

WARNING: This digresses into a rant by the end...  You've been warned.

If you like to have your garbage collected for you then use one of the
management strategies present in C++.  If you like delayed freeing, overload
new or use a library that does this.  Really, the difference between C++ and
most other programming languages (that are strongly typed) is that C++
doesn't make any assumptions about what you are going to do with it because
of its most basic principle: you don't pay for what you don't use.  If you
want garbage collection, you can have it: it's not like C++ prevents this.
By the same token, Java and C# don't allow you to make any decision here
which might be best in certain circumstances, but it certianly isn't always
ideal.  If you want the subset of features that say java has, you are
welcome to create these restrictions in C++ all while remaining more
portable.

I personally use garbage collection every once in a while in my C++ code.
It is not usually the right tool for me, but there are circumstances where
it makes sense.  I generally use it when I have data that isn't really owned
by any object.  It is data that many parts of the program reference and some
wish to keep a copy for themselves.  This is how the std::string class is
implemented in C++.  Reference counting and copy on write.

But I'll be damned if Java takes over the world because there are
programmers that don't know when they need to use garbage collection.  If
you can't avoid memory leaks, fine, don't use C++ or C, but don't blame the
language.  You could use garbage collection if you need it; don't make us
all stoop to your level of competency and don't try and claim that your
language is just as fast when it isn't.

- Nick

On Nov 12, 2007 11:55 PM, Hellwig Geisse <[EMAIL PROTECTED]>
wrote:

> On Mon, 2007-11-12 at 20:17 -0800, steve uurtamo wrote:
> > C
> > garbage collection: free().
>
> Well, that's not garbage collection. You will begin to notice
> that if you are using shared data structures with different
> lifetimes. The question that comes up again and again is "can
> I free this structure here or does any part of my program hold
> a private pointer to this piece of data?" It is sometimes
> possible to group freeing objects (e.g., a compiler can free
> data structures it needs to compile a function when the end
> of the function is reached - this is called "arena freeing")
> but not always.
>
> > very fast.
>
> 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.
>
> My personal experience is: if you can tolerate the 5-10% loss
> in execution speed, a real garbage collector is invaluable.
>
> Hellwig
>
> ___
> 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

[Nick Apperson]

haha, I was just kidding.  Sorry that humor doesn't always come through.
Anyway, what is a "forth type" language.  I am really interested in learning
about this.  Thanks in advance.

- Nick

On Nov 12, 2007 5:59 PM, Don Dailey <[EMAIL PROTECTED]> wrote:

> How about forth?   A lot of the high level languages we are talking
> about essentially get converted to forth (or I should say a "forth type"
> language.)
>
>
>
> - Don
>
>
> Chris Fant wrote:
> > I would like some language recommendations.  Requirements:
> >Runs in Linux
> >Has garbage collection
> >Fast
> >Well supported
> >Can interface with MPI (can make C calls)
> >
> > Hope this doesn't start a war.
> > ___
> > 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] Language

[Nick Apperson]

Are you a troll?

I'd recomend staying away from proprietary languages personally... for
obvious reasons.  I don't think there is any language that doesn't sacrifice
some speed for garbage collection.  But, speed is a relative thing.  If you
don't directly use the heap in C++ (i.e. you use the smart pointer class)
you don't have to worry about garbage collection (except if you make a
circular list).  If you are willing to sacrifice some speed, you could go
with java or c#, but these will be noticably slower, have mediocre support
for interfaceing with C, and are proprietary...  There aren't that many well
supported languages honestly.

You will probably get a few people here recommending "D", but that is most
definately not well supported and it is slower than C or C++ in terms of
writing a go program.  I guess what I'm trying to say is: you are going to
have to give on one of your requirements.  If you are serious about go
programming, learn a real language like C++...  It might take a few years to
learn, but it is the way to go.  If you are just looking to mess around,
fast isn't really as much of a priority.  Even some of the slowest languages
out there are within an order of magnitude of the speed of C++.

I hope that helps.

On Nov 12, 2007 3:41 PM, Chris Fant <[EMAIL PROTECTED]> wrote:

> I would like some language recommendations.  Requirements:
>   Runs in Linux
>   Has garbage collection
>   Fast
>   Well supported
>   Can interface with MPI (can make C calls)
>
> Hope this doesn't start a war.
> ___
> 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] Solving Go

[Nick Apperson]

This was posted a while ago on here by Terry  Here are the links:

http://senseis.xmp.net/?7x7BestPlay
http://erikvanderwerf.tengen.nl/5x5/5x5solved.html

I hope that is a little bit helpful...

On 11/7/07, Ben Lambrechts <[EMAIL PROTECTED]> wrote:
>
>  I want to create a perfect player on board sizes 3x3, 5x5 and maybe 7x7
> and beyond.
>
> But I have no idea how to start. How do I create the move database and how
> do I select the perfect move for every position?
>
>
>
> I know Go is solved on boards 5x5 and smaller, but there is no program
> that plays by this perfect moves.
>
>
>
> Has anyone did this before or has anybody thoughts about this?
>
>
>
> Ben
>
> ___
> 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] Draughts / Checkers solved

[Nick Apperson]

This is an exercise in proving that computers have more memory and
processing power than before I feel.  To solve a game, very little
programming skill is necessary.  The strategy for using processing power can
only be one of a limited set of possible strategies.  A game that is not
solvable by brute force leaves room for so called AI which I don't think was
present at all in this program what what it sounds like...  Or am I missing
something?

On 7/19/07, Tom Cooper <[EMAIL PROTECTED]> wrote:


http://news.bbc.co.uk/1/hi/sci/tech/6907018.stm

___
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] Opening

[Nick Apperson]

   There are two distinct concepts here.  There is precision and there is
accuracy.  Your test will test precision (how exact the estimate is), but it
fails to test accuracy (a measure of how close the mean is to the actual
value).  But, I do think that knowing the precision is useful.  If the
precision is too high (the noise is too low), it indicated that too many
simulations (on a given position) were done for efficient use of processing
power.  Atleast that is my perception of the situation.

   In a more general sense, I think that data gathering is definately by
far one of the most useful ways to contribute to the computer go community
and I salute you for your proposal.

- Nick

On 6/16/07, Heikki Levanto <[EMAIL PROTECTED]> wrote:


It seems generally accepted that MC or UCT programs are weakest in the
opening. My own experience matches this too. Some times I get the idea
that my program doesn't know at all what it is doing the first few
moves. I propose a simple test to see if that is the case. Before doing
it, I'd like to hear if other programmers are willing to make a similar
test, and agree on the particulars.

The idea is simple: We know that the empty board is symmetrical. How
many iterations does it take before the program gets values for the
first move that are symmetrical too. For example, if the program prefers
the 3-3 point in one corner, but 4-4 in the other corner, then I would
say that it doesn't know much about the situation.

I am sure there is a mathematically sound way to measure how symmetric
the evaluation is, but my math is a bit rusty, so I am asking if someone
can come up with a good way. After that, I'm asking if various
programmers would be willing to run this test, and publish the results?

- Heikki
  (who has no time to debug his own program...)


--
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] Java hounds salivate over this:

[Nick Apperson]

I think Java approaches the speed of C only in a few benchmarks.  I
think if you had a competition by super-experts in any language to write
a very specific program, you would find that the Java program couldn't
approach the C program in speed.



For instance I would like someone to take Lukasz Lew's code base and
come close to it's performance in Java.   I would be really surprised if
you could get half the speed in this case.


I couldn't agree more with what you say here.  If any of you really think
that Java can be as fast as C or C++, then prove it.  I have yet to be even
moderately convinced.  I wouldn't mind seeing it.  I would still probably
use C++ for most of my own work because I prefer its rich feature set, but
it could save me some time when I am able to subcontract out part of a
performance critical job to a dime-a-dozen java programmer.



On 6/15/07, Don Dailey <[EMAIL PROTECTED]> wrote:


I think D keeps improving.  The gcc version is slower anyway, so I
haven't bothered with it but my understanding is that they have made a
lot of optimizations since we last discussed the performance of D on
this group.  Of course I haven't tested it out in a while.

I would use D exclusively for performance programming if it could get
pretty close to C in speed.   In principle the author of D claims it's
has more potential than C does for optimizations.

Are you using D now?


- Don


On Fri, 2007-06-15 at 14:45 -0400, Jason House wrote:
> On 6/15/07, Phil G <[EMAIL PROTECTED]> wrote:
> JIT didn't solve everything - the managed memory management in
> Java (and C#) has overheard which JIT can not always optimized
> away, for example.
>
>
> The D programming language website argues in favor of garbage
> collection... Even claiming that it could be faster than manual memory
> allocation/deallocation. http://www.digitalmars.com/d/garbage.html
>
>
> 
> I'm not yet sold on all the ideas... especially since D's GC crashes
> when using the port to gcc.  Arguments like "you don't have to debug
> memory management code" (like on the website) are nice points, but
> it's far more frustrating when the standard GC doesn't work.
> 
> ___
> 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] Computer tournament at next US Go Congress?

[Nick Apperson]

I was thinking about going anyway.  If some of you all are going to be
there, I would definately get there if it is possible.  Not that I am at the
level of most of the people on this list...

On 4/13/07, Don Dailey <[EMAIL PROTECTED]> wrote:


On Fri, 2007-04-13 at 13:14 -0400, Chris Fant wrote:
> Just how your wife wanted to spend her anniversary!  :)

All I have to do is let her go shopping and she will be
happy!But of course I would spend time with her
outside of the event.   I have heard horror stories
of taking wives to tournaments and they become
virtual widows.

I assume since I would not be playing I would not have
to pay the entry fee,  I would only go to observe and
meet some other GO programmers.It would be fun if
there were several of us there.   Any chance of that?

- Don


___
computer-go mailing list
[EMAIL PROTECTED]
http://www.computer-go.org/mailman/listinfo/computer-go/

___
computer-go mailing list
[EMAIL PROTECTED]
http://www.computer-go.org/mailman/listinfo/computer-go/

Re: [computer-go] average length of 9x9 MC playout

[Nick Apperson]

heavy playouts should yeild a lower number of moves because moves are
slightly more efficient bringing the end of the game sooner.  I'm actually
surprised it isn't a larger difference.

On 3/18/07, Don Dailey <[EMAIL PROTECTED]> wrote:


On Sun, 2007-03-18 at 22:33 -0400, John Tromp wrote:
> I've seen the number 107.3... reported earlier
> for the average length, without the 2 final passes.
> Is this allowing multi stone suicides or not?
> And what's the outcome in the other case?
> Thanks!

This does not allow multi-stone suicide.   I don't
know the number in the other case.

I just checked Lazarus again and it's getting
about 104.63 moves per random game from the
opening.There are some minor implementation
differences such as how suicide is handled,
the exact eye rule used, etc.

The heavy play-out version of Lazarus gets
almost the same number, but it's consistently
about 1/10 of move lower for some reason.

Are you trying to make a Monte Carlo program?

- Don



> 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/

___
computer-go mailing list
computer-go@computer-go.org
http://www.computer-go.org/mailman/listinfo/computer-go/

Re: [computer-go] computer go documentation issues

[Nick Apperson]

I fully agree with your plan.  Merging it all onto wikipedia seems like a
good plan to me.  Certainly forwarding the others is a must too.

On 3/18/07, Peter Christopher <[EMAIL PROTECTED]> wrote:


Taking a look at computer go documentation, I see that there are (at
least) three pages that exist in wiki format for top level "computer go"
  wiki pages-

wikipedia.org - computer go
sensei - computer go
sensei - computer go programming

It seems obvious that these are redundant.  It seems prudent to combine
them in one location.  Which location?  I am thinking that wikipedia
would be the main page.  The other two (sensei pages) would temporarily
just get a big heading on top saying "THIS PAGE IS FOR HISTORICAL
REFERENCE ONLY.  OFFICIAL WIKI COMPUTER GO PAGE IS AT WIKIPEDIA.ORG.
FOLLOW THIS LINK."

On a related note, should *any* computer go documentation be at sensei?
Maybe everything other than the main page? Or maybe everything in
computer go should be moved to wikipedia?

At the very least, we ought to make prominent notes on the wikipedia and
sensei pages of the existence of the other.

Any opinions?

Peter
___
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: Re:[computer-go] MoGo

[Nick Apperson]

one concern i have is that within a family of programs (such as MC) the
estimated skill differences are overestimated.  I would really like to see
an anchor that uses a different technique.  I'm not offering a solution.
Thoughts?

On 3/17/07, Don Dailey <[EMAIL PROTECTED]> wrote:


On Sat, 2007-03-17 at 23:32 +0100, Sylvain Gelly wrote:
> Hi Don,
>
> > I remember when CGOS first came up,  I expected it to be a
> > few years before a program could achieve 2000.0 on the CGOS
> > scale.
> I hope you are more optimistic on the future.

I thought I was just being realistic, based on previous progress
in computer GO which has been basically a crawl.   I did not
anticipate the amazing success of Monte Carlo techniques.  Even
though I predicted it, I didn't expect it to go so far so fast.

> >  At some point the Anchor program will be too weak to be taken
> > seriously and we will have to replace it!
> Having an anchor at a much higher level would be very useful, in order
> to have the rating converge more quickly (and accurately). I think the
> last version of Lazarus would do a great job, for at least two
> (essential) reasons: very strong (rated at 2100 ELO) and keep the
> transitivity (very important) i.e. the winning rate of Lazarus against
> every other programs matches the difference in ELO.
> I know it does not match the "do not take resources" requirement, and
> you would have to dedicate a computer for that. But with the number of
> programs at +- 2000 ELO, the 1500 AnchorMan is far too weak.
> Fortunately, ggexp is almost always connected and strong.

Another possible candidate is Mogo, running at 3K play-outs, like the
version running on CGOS right now.

An idea I have is to fix up a binary of some strong program like Lazarus
or Mogo, with the level and essential parameters hard coded to be an
Anchor
player.Ask 2 or 3 people to run these clones under different names
as Anchor players.   Then there would usually be an Anchor available
to play.

Do you think any version of gnugo is suitable as an anchor?


- Don




> Sylvain

___
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] Grid Cosmos

[Nick Apperson]

I have experience with both.  I will admit that I find both languages to be
very frustrating as it takes way longer to write good code as compared with
a language that isn't written for dummies (i.e. C++), but I have been paid
to write code in both and am therefore somewhat qualified I suppose to make
comments.  First off, the obvious pro of Java is that is much more portable
which is really the only good argument as to why an advanced programmer
would ever use it over C++ to begin with.  That is a serious advantage.  As
far as developement time, syntax and library, C# definately beats java.  The
library with C# is so far superior it isn't even funny (in terms of ease of
use, reliability and running speed).  In addition, the garbage collection is
done much more efficiently in C# as well compared with most java virtual
machines I have seen.  It is too bad in my opinion that sun sued microsoft
for J++ because J++ was compatible with java and seriously WAY faster and
less buggy.  In my opinion, C# blows java away, but I would never use it
because I run linux for everything.  It is also my opinion that being locked
into something proprietary (like the .NET framework) is a horrible, horrible
sin against programmer common sense.  Also worth considering is that Java
has gone open (finally ...) so we can expect it to improve quite a bit now.
Everything considered, I'd pick Java over C#.  Just my experience though.

- Nick

On 3/15/07, Don Dailey <[EMAIL PROTECTED]> wrote:


What does C# bring that Java doesn't?   My understanding is that C#
is Microsofts way to try to supplant Java as a standard,  not a clone
but extremely similar.

What advantages over Java?  It is a higher level language?

- Don


On Thu, 2007-03-15 at 07:04 -0700, Jim O'Flaherty, Jr. wrote:
> Eduardo,
>
> I am a strong Java advocate, no doubt.  However, Mono/C# have
> accomplished quite a bit in the last 3 years.  My own experience in
> that area tells me it is much more mature than you have made it sound.
> To get pretty up-to-date information, try here:
> http://en.wikipedia.org/wiki/Mono_%28software%29
>
>
> Jim
>
>
> - Original Message 
> From: Eduardo Sabbatella <[EMAIL PROTECTED]>
> To: computer-go 
> Sent: Thursday, March 15, 2007 5:11:41 AM
> Subject: Re: [computer-go] Grid Cosmos
>
> As far I know, Mono implements the virtual machine and
> a couple of core libraries. Anyway, A lot of them are
> missing. I don't know for sure, but It looks
> impossible to use real applications inside mono/linux.
>
> By the way, As far I know, there was a scam with
> Icaza/Novell receiving money from Microsoft, plus java
> sdk released as open source (GPL) a couple of weeks
> ago.
>
> All directions shows that mono on linux is stuck.
>
> Specially, after Java SDK published as libre/free
> software.
>
> --- Brian Slesinsky <[EMAIL PROTECTED]> escribió:
>
> > On 3/14/07, Darren Cook <[EMAIL PROTECTED]> wrote:
> >
> > > P.S. Is anyone using C# on linux? I thought C# was
> > standardized so I
> > > expected to find something, but google is only
> > giving me articles from
> > > 2001...
> >
> > I haven't used it, but the Mono project has
> > reimplemented C# and many
> > of the .Net platform libraries, and is
> > cross-platform.
> >
> > - Brian
> > ___
> > computer-go mailing list
> > computer-go@computer-go.org
> >
> http://www.computer-go.org/mailman/listinfo/computer-go/
> >
>
>
>
>
>
>
>
> __
> Preguntá. Respondé. Descubrí.
> Todo lo que querías saber, y lo que ni imaginabas,
> está en Yahoo! Respuestas (Beta).
> ¡Probalo ya!
> http://www.yahoo.com.ar/respuestas
>
> ___
> 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] Go hardware?

[Nick Apperson]

This is definately the direction things are headed.  Processors are going to
eventually have tons of cores.  The main problem with the design you
mentioned though is that the overhead of having all those processors would
almost not make it worth it because of how slow they are.  And also, bus
speed becomes a serious bottleneck.  If each of those processors had its own
1MB of local memory (like a cache) that only it could access then I'd say
that would be great.  I think writing programs these days that don't scale
well to atleast 32 threads, if they are programs that require lots of
resources, is basically irresponsible and certainly shortsighted.  Just my
thoughts though.

- Nick

On 3/9/07, Chris Fant <[EMAIL PROTECTED]> wrote:


Wouldn't it be cool if Intel or AMD would release a CPU with a primary
core somewhere close to today's state of the art along with oh, say,
about 256 lower-tech, existing-design cores.  Like 386s or something.
Definitely the mini-cores would have to be 32 bit, but they don't need
floating point operations (at least for for running MC simulations).
Or if that's a bad design, then use 486s that come with the floating
point unit.  That would be cool.
___
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] GTPv3

[Nick Apperson]

perhaps since every command is numbered we could have a command that tells
the engine to abort a command by number.  The engine can ofcourse reply with
a failure if it already processed the command and can not abort it.  Genmove
still seems to be somewhat of an issue, but atleast this way defines clear
behavior that will work well as long as engines don't take too long to
replay to an abort with a success or failure.

On 3/8/07, Markus Enzenberger <[EMAIL PROTECTED]> wrote:


I am still frightened by your plans, how to permit asynchronous commands
in
GTP. Here are some remarks and questions:

genmove is only one of many commands that the user might want to abort. We
use
GTP extension commands for starting life and death searches or other
lengthy
computations and many of them can be aborted at any time. Do you really
want
a sync and async version and a different abort command for each of them?
Potentially every GTP command can be a candidate for aborting. If a
controller provides support for engine-specific extension commands without
specifically knowing what they do (like GoGui's Analyze Commands), there
should still be a way to let the user send an abort request and let those
commands abort that are able to.

Why is it necessary that the async genmove returns an immediate response?

- Markus
___
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] GTPv3

[Nick Apperson]

I do not think that genmove should work that way.  It makes more sense for
you to have a genmove command and an async_endsearch command or
somethinglike that.  The program is allowed to keep searching as long as it
doesn't receive that command.  genmove doesn't need to have an async mode
really.  You could have async_genmove return the programs best guess at the
moment, but it wouldn't be considered final until genmove returns.

On 3/5/07, Don Dailey <[EMAIL PROTECTED]> wrote:


Yes, it's possible to do all of this with GTP as is and
the addition of a few commands that stay blocking, nothing
but pure GTP extensions and no asyncronous communication.

I already mentioned this as polling.   Instead of genmove,
you send inc_genmove, which is designed to return very
quickly and does only a partial search.   The controller
continues to send a long series of consecutive inc_genmove
until the engine makes a move.   And the controller can
stop sending inc_genmove if it wants to abort.   In fact
it doesn't even need to tell the engine to abort.

I think this is really rather ugly however.   You are
adding a LOT of extra communication and things will
be sluggish if you don't send these at least 3 or 4
times per second.

- Don


On Mon, 2007-03-05 at 09:50 -0300, Eduardo Sabbatella wrote:
> Actually gen_move blocks because every engine uses the
> same thread for both the engine and the comm link.
>
> you can have a couple of sub commands for get_move
> like: get_complete_percent, get_current_best_move,
> chat, etc.
>
> If the engine doesn't support "realtime" gtp, they
> will be answer after the gen_move response. one at a
> time.
>
> I don't know, perhaps I'm pushing too much the gtp
> protocol... I don't think so, but perhaps
>
>
> --- Nick Apperson <[EMAIL PROTECTED]> escribió:
>
> > I think you are mostly correct.  But, the problem is
> > that GTP was designed
> > to block on the genmove command.  This is a problem
> > because genmove is
> > usually not quick to return.  Therefore, there is no
> > way with the current
> > scheme to be able to issue commands while an engine
> > is thinking.  It would
> > require a redesign perhaps using polling instead if
> > GTP is to remain
> > blocking.
> >
> > On 3/5/07, Eduardo Sabbatella
> > <[EMAIL PROTECTED]> wrote:
> > >
> > > Don,
> > >
> > > Perhaps I'm completelly wrong, but pondering is up
> > to
> > > the engine, the controller, nobody outside the
> > engine
> > > will know / have to know if the engine is
> > pondering.
> > >
> > > I think in the threads we are confusing the fact
> > that
> > > the engine and the gtp line controller could be in
> > two
> > > different process threads.
> > >
> > > GTP line could 'answer' questions like: cpu usage,
> > > current best move, at realtime comunicating with
> > the
> > > engine thread. Also, the engine could publish
> > stats
> > > info sending that to the gtp line thread.
> > >
> > > That is not related to the protocol at all. Adding
> > a
> > > couple of new commands will be enough. (and
> > processing
> > > them on realtime from another thread).
> > >
> > > If the engine doesnt supports 'abort'
> > > the controller after a couple of seconds will
> > receive
> > > 'move blah blah' 'command don't understood'.
> > >
> > >
> > >
> > > --- Don Dailey <[EMAIL PROTECTED]> escribió:
> > >
> > > > I like GTP and I champion it.However, there
> > are
> > > > some weaknesses
> > > > and they are not easily fixed without a major
> > > > paridigm change.
> > > >
> > > >   1.  There is no way to STOP a program from
> > > > thinking.  This is
> > > >   needed for a high quality user interface.
> > > >
> > > >   2.  There is no natuaral way to get useful
> > > > information from the
> > > >   go program, such as it's thinking process.
> >   A
> > > > quality user
> > > >   interface should be able to show the user
> > the
> > > > thinking process
> > > >   of the program,  when it changes it's mind
> > > > about the move choice,
> > > >   it's current opinion of the score, etc.
> > > >
> > > >   This can be implemented with "polling" by
> > > >

Re: [computer-go] GTPv3

[Nick Apperson]

just a thought...

prefix all async commands with "async_" so that it is clear.  Also, that way
there can be a version of the command that is async and one that blocks and
an engine can support one or both.  This could be useful for commands that
query on state (or estimated score or whatever).  An engine might not be
able to easily support that async, but another engine might be able to.  The
controller can query using get_commands (or whatever the function is called)
and know that it can call it anytime or only when the engine isn't
thinking.  Also, it would make it clearer how a command operates and a
command can be assumed to be blocking unless it has that prefix and if we
change the behavior of the async versions from the blocking ones an engine
can still support both.

- Nick

On 3/5/07, Eduardo Sabbatella <[EMAIL PROTECTED]> wrote:


We got consensus :-)

Yes some messages are async, some are synqued. If an
async message/reply is received in the wrong time, it
could be ignored as they use to be information only
values, no state change of the game.

cool :-)

--- Don Dailey <[EMAIL PROTECTED]> escribió:

> I agree with you.  My idea is to not have a specific
> aync
> command, but to have anycronous versions of
> commands.   The
> engine is free to accept or reject them.   Having an
> async
> command doesn't do anything if you haven't
> implemented the
> useful needed extensions.Of course it could
> change the
> meaning of existing commands but I think it's
> cleaner to
> simply have new GTP commands that are understood to
> be
> asyncrounous.
>
> Even UCI doesn't allow the engine to say anything it
> wants
> whenever it wants.   It is still semi-syncronous.
> All
> communication sent from an engine is still a
> response to
> some command sent from the controller.   The rule is
> that
> you ignore any communication sent out of context and
> this avoids syncronization issues such as when the
> controller
> says to stop searching but the engine sends a move
> before
> this is noticed.
>
> So it's really not as complicated as you might
> think.
>
> "chat" I assume is about informational messages from
> a
> searching engine.   So it's a legitimate response to
> an asyncronous command to search a position, but if
> you are not searching a position it would be ignored
> by the controller.
>
> Abort is the same,  it really means "stop searching
> if you are currently searching"  and so is ignored
> if
> you happen to have stopped at  almost the same
> instant you recieved the command.
>
> - Don
>
>
>
>
>
> On Mon, 2007-03-05 at 09:08 -0300, Eduardo
> Sabbatella wrote:
> > Just an small thought
> >
> > GTP could implement "async" commands. Adding
> commands
> > like:
> > CHAT
> > ABORT
> > etc.
> >
> > Its up to the engine to read them as soon as
> possible,
> > or wait to read/process them after processing a
> > get_move command.
> >
> > I think just adding a couple of new commands that
> some
> > engines could implement them 'in real time' its
> good
> > enough for everybody.
> >
> > I wouldn't add complexity adding a true async
> channel,
> > out of band or whatever.
> >
> > I mean, commands are ordered, as before, as
> always,
> > that wouldn't break current implementations.
> >
> >
> > By the way, I use a lot of stderr, I love it for
> > debuging purposes, please don't use it as a second
> > stream of comunication with the engine.
> >
> > With stdin/out and a thread with a couple of
> mutexes
> > is all you need. (or thread safe queues if you
> like)
> >
> >
> > My 2 cents
>
> ___
> computer-go mailing list
> computer-go@computer-go.org
>
http://www.computer-go.org/mailman/listinfo/computer-go/
>







__
Preguntá. Respondé. Descubrí.
Todo lo que querías saber, y lo que ni imaginabas,
está en Yahoo! Respuestas (Beta).
¡Probalo ya!
http://www.yahoo.com.ar/respuestas

___
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] GTPv3

[Nick Apperson]

I think you are mostly correct.  But, the problem is that GTP was designed
to block on the genmove command.  This is a problem because genmove is
usually not quick to return.  Therefore, there is no way with the current
scheme to be able to issue commands while an engine is thinking.  It would
require a redesign perhaps using polling instead if GTP is to remain
blocking.

On 3/5/07, Eduardo Sabbatella <[EMAIL PROTECTED]> wrote:


Don,

Perhaps I'm completelly wrong, but pondering is up to
the engine, the controller, nobody outside the engine
will know / have to know if the engine is pondering.

I think in the threads we are confusing the fact that
the engine and the gtp line controller could be in two
different process threads.

GTP line could 'answer' questions like: cpu usage,
current best move, at realtime comunicating with the
engine thread. Also, the engine could publish stats
info sending that to the gtp line thread.

That is not related to the protocol at all. Adding a
couple of new commands will be enough. (and processing
them on realtime from another thread).

If the engine doesnt supports 'abort'
the controller after a couple of seconds will receive
'move blah blah' 'command don't understood'.



--- Don Dailey <[EMAIL PROTECTED]> escribió:

> I like GTP and I champion it.However, there are
> some weaknesses
> and they are not easily fixed without a major
> paridigm change.
>
>   1.  There is no way to STOP a program from
> thinking.  This is
>   needed for a high quality user interface.
>
>   2.  There is no natuaral way to get useful
> information from the
>   go program, such as it's thinking process.   A
> quality user
>   interface should be able to show the user the
> thinking process
>   of the program,  when it changes it's mind
> about the move choice,
>   it's current opinion of the score, etc.
>
>   This can be implemented with "polling" by
> adding a GTP command
>   to request information from the engine every
> second or two, but
>   this feels like a hack.
>
> Thinking on the opponents time (pondering) is
> supported naturally by
> the UCI protocol.  Actually, the engine doesn't need
> to know much
> about this,  the controller simply tells the engine
> to start thinking
> on a given move and so the engine doesn't even know
> it's thinking on
> the opponents time.   However, the engine does
> communicate to the
> controller what the ponder move is.
>
> This could ALMOST be implemented directly in GTP,
> except for the fact
> that you cannot stop the engine from searching once
> it begins.  If
> I'm pondering, but the opponent doesn't play the
> ponder move,  there
> is not way in GTP to say, STOP searching NOW because
> the move is not
> relevant!
>
> So GTP could not easily be used to build a high
> quality user interface,
> say
> for a commercial program.   At least not one that
> had the better
> features,
> even given that you can extend the command set with
> additional commands.
>
> It COULD be done, just not easily.   You would have
> to do it all with
> polling.  You could even implement stop search by
> having a GTP command
> to do searching in tiny time slices.   The contoller
> would send
> commands such as "continue_search" which must return
> in a fraction of
> second, possibly with a move.This would be truly
> awkward but
> possible.
>
>
> - Don
>
>
>
> On Thu, 2007-03-01 at 17:10 -0700, Markus
> Enzenberger wrote:
> > On Thu March 1 2007 05:22, £ukasz Lew wrote:
> > > The most important thing is controller - engine
> architecture.
> > > There are situations that engine would like to
> have the control. For
> >
> > these requests come up once in a while, but IMO
> the clear separation between
> > who is the controller and the engine is a big
> advantage of GTP. It makes both
> > the implementation of engines and controllers much
> easier.
> >
> > Can you do simple, single-threaded controller
> scripts with UCI? Is it used for
> > as many use cases as GTP is, ranging from
> regression testing to any kind of
> > automated experiments with Go engines?
> >
> > The Go server protocols are designed for humans
> and asynchronous sending of
> > messages between them at any time, but does it
> make sense for a computer
> > engine to allow it to start chatting, whenever it
> feels like it?
> >
> > I think that GTP should not be extended in a way
> that makes the implementation
> > of engines or controllers more complicated.
> >
> > > In gogui this is solved by using stderr to send
> those commands, but:
> > > - stderr is not network transparent
> >
> > Remi Coulom convinced me that it is more
> convenient for the engine to write to
> > standard error and he was right. Typically the GTP
> interface is only one of
> > several interfaces to lower level Go engine code
> and you don't want to make
> > lower level code aware of this.
> >
> > One idea I had in mind to address this was to
> allow the engine to send comment
> > lines before the ac

Re: [computer-go] GTPv3

[Nick Apperson]

In my view, the most important features of GTP are its ability to mediate
for tournements.  It lowers the bar for building a program.  Anything that
changes that is bad news.  However, there are some problems with the current
protocol such as its inability to handle rules.  I feel it is a step in the
right direction, but it does need to be improved.  However, anything not
completely essential should be made an extension for GTP in my opinion.
Asynchronous functions seem to me to be unecessary as anything more than an
extension.

On 3/5/07, Heikki Levanto <[EMAIL PROTECTED]> wrote:


On Sat, Mar 03, 2007 at 04:10:16PM -0500, Don Dailey wrote:
> And you CAN compare GTP directly to UCI because both are designed for
> the same purpose and both are simple text based protocols and the
> similarities are much greater than the differences.

GTP has many purposes. One of them is to sit betwene an engine and an
UI, but that is not the only one. It is also used for test scripts to
validate engines, and to debug them.

So, what even asynchronous extensions you are adding to GTP, please keep
the simple synchronous mode still available, for it has many uses too!

-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] Library of Effective GO routines v 0.106

[Nick Apperson]

The other thought (kind of silly) but just a pssing thought is that the
threads that are benchmarking are keeping a local copy of their count and
writing it back at the end (which is allowed) so you are actually getting
good performance, but you don't know it because the processors aren't
talking to each other properly.  Exactly 2x is hard to imagine happening by
chance.

On 2/22/07, Sylvain Gelly <[EMAIL PROTECTED]> wrote:


Hello,

> I do not understand it. Maybe someone does?
> I've made some tests on 2 core processors, and I have strange results.
> Some of 2 core processors got results exactly 2x times worse than they
should.
> Why?
> I have no idea.
> But 2.8 Ghz 2 core works exactly like my 1.4 laptop.
> Also version of g++ does matter.

Here, from my experience, the following can matter a lot:
- version of g++ (g++ 4.1 gave me +50% against g++ 4.0 on an opteron!)
- version of the libc: even compiled with a modern compiler, a program
running on a machine with an old version of the libc can be very
significantly slower (-30% observed!).
- exact version of the processor: today the frequency means nothing,
nor the name of the processor. You have to check the exact numbers.
And I also observed that even the small numbers as the "stepping
number", matters. MoGo runs faster on my P4 3.4 Ghz  than on a 3 years
newer P4 3.8 Ghz, which has also more cache. I ran test on other P4,
and the slower had a different stepping, that's all (all are dell
computers using same hardware).
- Measure of time: if you take the CPU time, on multiprocessor
machine, while using multithreading, sometimes the reported time is
not what you expect (generaly reported for all the threads), so when
you calculate the speed of playouts, you can have a 2x/4x factor.

Hope that can help,
Sylvain
___
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] Library of Effective GO routines v 0.106

[Nick Apperson]

if cache is your limiting factor that is usually shared.  Also, if you are
using processors with hyperthreading, it is possible.  Or if bus bandwidth
is your limiting factor... but if it is exactly 2x slower that is indeed
very odd.  My money is on the fact that you have a bottleneck somewhere else
and those processors were operating below capacity the whole time and that
now that you added more, it is becoming more obvious.  If for instance, you
had the following situation:

thread A creates a queue of tasks for the rest of the threads to do.  If
thread A isn't able to keep the queue full, then obviously more processors
won't help.

The only other though I have is that your compiler isn't writing code that
allows for proper multithreading.  Can you be more specific on which
processors are giving you a hard time?

- Nick

On 2/22/07, Łukasz Lew <[EMAIL PROTECTED]> wrote:


I do not understand it. Maybe someone does?
I've made some tests on 2 core processors, and I have strange results.
Some of 2 core processors got results exactly 2x times worse than they
should.
Why?
I have no idea.
But 2.8 Ghz 2 core works exactly like my 1.4 laptop.


Also version of g++ does matter.
Łukasz

On 2/21/07, Brian Slesinsky <[EMAIL PROTECTED]> wrote:
> The only real change is to link against the Boost libraries I
> installed using DarwinPorts.  Here are the diffs:
>
> -CFLAGS += -Wall #-static #-Wno-long-long -Wextra -Wno-variadic-macros
> +CFLAGS += -Wall -I/opt/local/include -L/opt/local/lib
>
> It's a desktop and I don't see any options for power management.
> Maybe it's just a difference in processors?  It's a two core chip but
> perhaps not as fast at single-threaded apps.  Adding multithreading
> might help.
>
> - Brian
>
> On 2/21/07, Łukasz Lew <[EMAIL PROTECTED]> wrote:
> > On 2/21/07, Brian Slesinsky <[EMAIL PROTECTED]> wrote:
> > > [resending; apologies if you get this twice.]
> > >
> > > Hi,
> >
> > Hi Brian,
> >
> > >
> > > This is my first post to the list, so I'll introduce myself:   I'm a
> > > software developer and just getting started with playing Go.  I read
> > > the article in the Economist and thought that the work on
Monte-Carlo
> > > based Go programs sounds promising.  I'm not interested in writing
my
> > > own Go program but would like to experiment with improving existing
> > > programs.
> >
> > Have fun ;)
> >
> > >
> > > I built and started libego on an iMac with a 2GHz Intel Core
Duo.  The
> > > initial benchmark reports these results:
> > >
> > > Performance:
> > >   10 playouts
> > >   1.84255 seconds
> > >   54.2727 kpps
> > > Black wins = 43983
> > > White wins = 56017
> > > P(black win) = 0.43983
> > >
> > > Are these numbers to be expected?
> >
> > They are correct, except rather low performance.
> > It should be rather about 80 kpps (kilo playouts per second)
> >
> > There are few possible reasons for this:
> >  - You are using a laptop with power management
> >   - You changed Makefile or some source files to make it compile on
Mac?
> >
> > Best Regards,
> > Łukasz Lew
> >
> > >
> > > - Brian
> > > ___
> > > 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/

___
computer-go mailing list
computer-go@computer-go.org
http://www.computer-go.org/mailman/listinfo/computer-go/

Re: [computer-go] Big board. Torus ?

[Nick Apperson]

I considered making a version of go that plays with tetrahedral geometry.
It is a 3D arrangment where all nodes have 4 neighbors and the angles
between each are 109 degrees.  Its connection properties though are very
different because of the way it it layed out.  Hence, I am going to have to
disagree.  But if what you mean is that all that matters is the graph
representation of the go board, I will agree with you there.

- Nick

On 2/21/07, Matt Gokey <[EMAIL PROTECTED]> wrote:


Stuart A. Yeates wrote:
> On 2/21/07, alain Baeckeroot <[EMAIL PROTECTED]> wrote:
>> Le mercredi 21 février 2007 02:10, Antonin Lucas a écrit:
>>> No need for those difficulties,  you can play along this board :
>>>
>>> http://www.youdzone.com/go.html
>>
>> I think this is not a torus, even if each vertice has 4 neighbours.
>>  I can easily mentally transform this into a cylinder, with an
>> rectangular lattice and additional connection on the borders to
>> have 4 neighbours.
>
> I agree
>
> If this were a torus, there would be links between the inner ring and
>  the outer ring of vertexes.
Whether it is a torus or not is irrelevant.  The only thing that matters
from a go game play perspective is the graph topology.  If all points
have 4 neighbors the actual physical shape or layout doesn't matter.

___
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

[Nick Apperson]

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

[Nick Apperson]

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

[Nick Apperson]

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] Zobrist hashing with easy transformation comparison

[Nick Apperson]

Sorry for posting then,  I didn't realize that it had been tried.  I may
work through the problem and try to get it to work in order to fully
understand why it in fact does not work.  If by some miracle I manage to get
something working with a collision rate of 1/(2^61) I'll certainly post it.
Thanks for the info.

- Nick

On 2/9/07, Erik van der Werf <[EMAIL PROTECTED]> wrote:


Nick,

The basic idea of what you're describing is well known. It was first
published by Antti Huima several years ago. Unfortunately though, his
implementation was flawed. I didn't check your code but likely it
suffers from a similar defect. It is possible to fix the defects in
Huima's scheme. If you ignore colour symmetry it's relatively easy to
find a defect-free xor-based scheme that works with 8 segments. The
more interesting part is in finding the minimal number of segments,
and then proving correctness.

Nic Schraudolph has done some interesting work on this, but as far as
I know he still hasn't published it. Maybe if we all sit on him we can
finally get him to finish it :-)

Erik


On 2/9/07, Nick Apperson <[EMAIL PROTECTED]> wrote:
> Hey all,
>
> I was thinking about our conversation and i decided to design a
zobrist
> class that allows for easy comparison to check and see if 2 different
> zobrist values are equivalent after a rotation etc...  It updates the
> zobrist in such a way that it can transform them and after trying 8
> possiblilities, it can determine if they are equal.  There are actually
> quite a few optimizations that could be performed on it, but I just
wanted
> to post the basic idea.   See the following source code for the basic
idea:
>
>  http://www.nicholasapperson.com/computergo/zobrist.h
>
>  Essentially it works so that it hashes the played stone as each of the
> rotated forms and stores that in each of the 8 bytes used.  The bytes
are
> arranged in an order such that flipping the 2 DWORDs results in the
zobrist
> value for if there was a rotation in the x axis, flipping WORDs results
in a
> reflection across the y axis and swapping bytes results in a reflection
> across the y=x line.  Order obviously matters in the case of xy so the
> transformation is assumed to take place after the other
reflections.  For
> example:
>
>  if we have 0x1234567890ABCDEF as a zobrist value,
>
>  0x90ABCDEF12345678 would be the zobrist of the position with a
reflection
> across the x-axis
>
>
>  Anyway, I'm sure there is a bug or two, but I wanted to get your alls
> thoughts.
>
>  - Nick
> ___
> 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] Zobrist hashing with easy transformation comparison

[Nick Apperson]

Hey all,

  I was thinking about our conversation and i decided to design a zobrist
class that allows for easy comparison to check and see if 2 different
zobrist values are equivalent after a rotation etc...  It updates the
zobrist in such a way that it can transform them and after trying 8
possiblilities, it can determine if they are equal.  There are actually
quite a few optimizations that could be performed on it, but I just wanted
to post the basic idea.   See the following source code for the basic idea:

http://www.nicholasapperson.com/computergo/zobrist.h

Essentially it works so that it hashes the played stone as each of the
rotated forms and stores that in each of the 8 bytes used.  The bytes are
arranged in an order such that flipping the 2 DWORDs results in the zobrist
value for if there was a rotation in the x axis, flipping WORDs results in a
reflection across the y axis and swapping bytes results in a reflection
across the y=x line.  Order obviously matters in the case of xy so the
transformation is assumed to take place after the other reflections.  For
example:

if we have 0x1234567890ABCDEF as a zobrist value,

0x90ABCDEF12345678 would be the zobrist of the position with a reflection
across the x-axis


Anyway, I'm sure there is a bug or two, but I wanted to get your alls
thoughts.

- Nick
___
computer-go mailing list
computer-go@computer-go.org
http://www.computer-go.org/mailman/listinfo/computer-go/

Re: [computer-go] Serializing a very large object in Java

[Nick Apperson]

What type of data are you trying to serialize or rather store to disk?  Do
you have pointers in the data.  Don't tell me you don't have pointers just
because it is java.  Java has pointers, it just preteneds it doesn't.  Show
us the datastructure and we can probably help you more.  If each entry has
no pointers than your task should be pretty straightforward.  If you do have
them, you are going to need to find a way to store those so that they are
able to be redetermined.  In a language like java, where you can't do
pointer arithmetic or anything of the sort this can get rather difficult.
Also, have you considered using a database instead of a flat file to store
this data?

- Nick

On 2/9/07, [EMAIL PROTECTED] <[EMAIL PROTECTED]> wrote:


Peter, java serialization is not a good way to do persistent storage
of any kind, especially large data structures.

It has some pretty severe drawbacks:

- It is slow
- It breaks easily (ie, becomes unable to load older data sets) when
  you make even small changes in your code.
- It makes inefficient use of space
- The format is difficult to decode or manipulate in any way other
  than reading or writing with the exact .class file used to generate
  the serialization code.

Java serialization is excellent for RMI, but is pretty poor for any
other use. I've used serialization myself several times and I
regretted it every time (except for when I used it for RMI).

My advice would be to come up with your own data format and use
that.
___
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] MC approach

[Nick Apperson]

If it only did one playout you would be right, but imagine the following
cases:

case 1: White wins by .5 x 100, Black wins by .5 x 100
case 2: White wins by 100.5 x 91, Black wins by .5 x 109

the method that takes into account score would prefer the second case even
though it has a lower winning percentage that may be represented by the fact
that white is making an overplay for instance.  Obviously this is just one
example, but there are many cases like this and overplays tend to be
priveledged in a sense I would suspect with this kind of algorithm.

- Nick

On 2/7/07, Matt Gokey <[EMAIL PROTECTED]> wrote:


Don Dailey wrote:

> On Wed, 2007-02-07 at 11:34 +0100, Heikki Levanto wrote:
>
>>All this could be avoided by a simple rule: Instead of using +1 and -1
>>as the results, use +1000 and -1000, and add the final score to this.
>
>
> Heikki,
>
> I've tried ideas such as this in the past and it's quite
> frustrating - everything that tries to take territory
> scoring into account weakens the program.
>
> If you just need to see prettier moves,  I think it is
> good enough to priortize the moves using some other
> algorithm at the root of the tree.   If you just cover
> the case where a program is "easily winning" or losing
> it will play "nicer" but not stronger.

Don, do you have any theories or information about why this is the case?

I would think either way the algorithm should always prefer higher
average win probabilities, but faced with alternatives where the win
probabilities are same or nearly the same but the average winning
margins are higher for one alternative, wouldn't it be better to take
the path with the better margin? I mean it may in fact be wrong about
the win/loss classifications so choosing the better scores would seem to
make sense within reason as long as it's not greedy.


___
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] Details of AnchorMan

[Nick Apperson]

question:

should " if ( (bs + bt) - (ws - wt) > komi ) then black_wins else
white_wins." be " if ( (bs + bt) - (ws + wt) > komi ) then black_wins else
white_wins." ?  or maybe you meant "if ( (bs + bt - ws - wt) > komi ) then
black_wins else white_wins." ?

and floats are rounded down when converting to ints so even with komi as a
float this should work.  This is how I do it too.

On 2/5/07, Don Dailey <[EMAIL PROTECTED]> wrote:


Did you look at the games?   Sometimes there is something obvious.
For instance does it pass too early or lose games on forfeit?

Although I can't see your code, I would suspect the following
problems:

  1.  Is the eye avoid routine 100% correct?

  2.  Are the moves actually uniformly random?  You cannot just
  shuffle the list of moves for instance (without doing other
  things too.)

  3.  Make sure you are scoring the end of game correctly.

  4.  See if black is winning a lot more than white or visa versa.

For 3,  you must consider komi correctly
and you must keep stats on the wins and losses,  not on the
amount of territory for each side - that would weaken you
signficiantly.

Here is how my program scores:

   if ( (bs + bt) - (ws - wt) > komi ) then black_wins else white_wins.

  bs = black stones
  bt = black territory
  ws = white stones
  wt = white territory
  komi = integer komi (but it works with fractions too.)

- Don



On Mon, 2007-02-05 at 16:57 -0500, Chris Fant wrote:
> I must still have some bugs.  Here's my current numbers:
>
> Stoned100k1286
> Stoned10k 1009
> Stoned1k  755
>
>
> On 2/5/07, Christoph Birk <[EMAIL PROTECTED]> wrote:
> > On Sat, 3 Feb 2007, Don Dailey wrote:
> >
> > > GenericMC_300K 1455.0
> > > GenericMC_200K 1391.6
> > > GenericMC_11142.9
> > > GenericMC_100K 1453.9
> >
> > I run theses once a week for a few hours to keep them on the CGOS
list.
> >
> > myCtest1 10k 1075
> > myCtest5 50k 1385
> > myCtest25250k1445
> >
> > They do random playouts (from root) without any "tricks" until only
> > 1 point-eyes are left.
> >
> > 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/

___
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: Re: [computer-go] Why not forums?

[Nick Apperson]

I'm using gmail right now.  It is definately awesome.  Let me know if you
need an invite.

On 2/4/07, Chris Fant <[EMAIL PROTECTED]> wrote:


On 2/4/07, Dmitry Kamenetsky <[EMAIL PROTECTED]> wrote:
> In a forum you can read all the messages at once using your
scroll-wheel. You don't have to click next-message every time. You can also
add images and links, change font type. It would be nice to have a feature
where you can easily draw Go diagrams, just like in sensei wiki.


Gmail lets you scroll through the messages in a thread.  I highly
recommend it.
___
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] New CGOS

[Nick Apperson]

Are you going to release the source for it?  If you are, some of us might be
able to make some suggestions for how to port it to various platforms.  Just
a thought.  BTW, I know that I appreciate the work you are putting in and
I'm sure others are as well.

- Nick

On 2/3/07, Don Dailey <[EMAIL PROTECTED]> wrote:


On Sat, 2007-02-03 at 14:41 -0500, Chris Fant wrote:
> Don,
>
> How is the new version of cgos coming along?  From what I understood,
> you were very close to finished, but didn't have much time to devote
> to it.

It's currently on hold.  I'm worried about having a good cross-platform
viewing client.   The one I have is written in tcl/TK and I can produce
exe files for windows users.  But I ran into some difficulties with
some linux versions using tclkit's which is how I package them.

So I'm still contemplating (and procrastnating)  how to proceed.
I'm also consider wxWidgets or GTK+ which are both cross-platform.

I'm also considering whether to support multiple levels and/or
boardsizes and perhaps a couple of other nice features.

The latest version actually works - you can play games and watch
them in real time with a very nice viewing client - but it is not
quite there yet - there is no web reporting yet.

- Don



> (Excuse the incorrect subject on my previous thread, "Details of
> AnchorMan" -- I was originally going to ask about Anchorman, but then
> decided GenericMC_1000 was a better first try).
> ___
> 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] Is skill transitive? No.

[Nick Apperson]

I feel that what we need essentially is a set of functions that tell us
expected winning percentages with certain matchups.  In an extreme example,
we could imagine 3 rock, paper, scissors players.  One always plays rock,
one always scissor and one always plays paper.  In this case, we would be
able to define a ranking function as a relative ranking, but absolutre
ranking would not exist.  And this is consistent with our whole approach
here that skill is not transitive.  A simple 2D ranking system could work
like this:

let W = chance that player 1 will beat player 2
1-W = chance that player 2 will beat player 1

our skill is expressed in R and T (for theta)

ELO = (R1-R2)+k*sin(T1-T2)   where k is some constant, R1, R2, T1, T2 are R
of player 1 and 2, theta of player 1 and 2 respectively


This would result in a  nontransitive 2D skill map.  There are many, more
compex functions that could be worked out and this has the nice property
that it easily collapses into a 1D map by merely setting everyone's theta to
the same value.  Essentially R is "general skill" and theta is a rock paper
scissor type thing where one strategy is better against certain other types
of strategies.


On 1/31/07, Vlad Dumitrescu <[EMAIL PROTECTED]> wrote:


Hi,

On 1/30/07, Don Dailey <[EMAIL PROTECTED]> wrote:
> It would be interesting if it would be possible to construct a 2
> dimensional
> model statistically.   A 2 dimensional system would not be a perfect fit
> either,
> but would simply be a better approximation.So in some way a players
> "strength" could be expressed by 2 numbers instead of 1,  and the 2
> numbers
> together would predict your chances of beating another (2 dim) player
> more accurately that a 1 dimension system could.   And of course you
> could
> extend this.   But I don't have a clue how one would construct such a
> system
> or if it's even possible - but it seems like more information should be
> better
> than less.

Unfortunately, having more than one dimensions makes comparisons
impossible - if an ordering relation is defined over the domain, then
this domain is "one-dimensional" with regard to that relation.

In other words, one can't compare vectors, just scalars. So the
multi-dimensional "strength vector" has to be turned into a scalar (by
for example a weighted sum) and we're back where we started...

best regards,
Vlad (master of the obvious :-)
___
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] Re: Scaling monte carlo up to 19x19

[Nick Apperson]

I believe this to be a good idea, but I couldn't get around some minor
problems.  Essentially, because the local searches are coupled to one
another, it ends up exploding as you consider this coupling (scaling to
larger regions).  You then have to trade accuracy or have more computing
power than I have access to...  There are cases though where you can find
local solutions that are independent in some sense from the rest of the
board and the program I am working on now does that.  I'm sure someone
smarter than me will be able to figure out a better way though.  There are
certain times when this technique is highly useful.  For a simple example,
imagine a board with two walls down the middle bordering on each other.  In
some sense, as long as both those walls live, there are 2 subgames taking
place.  This type of situation is where I see your approach as being the
most useful.  Just my thoughts.

- Nick

On 1/30/07, Weston Markham <[EMAIL PROTECTED]> wrote:


I have an idea in the back of my mind that is an extreme version of
this:  Divide the board into 361 separate local searches, then use
information from these to guide a global search.  The local searches
would be done on the full board, but would only search for strategies
that will capture or defend individual intersections.  I suspect that
this first phase could potentially benefit from parallelization for a
significant portion of the game.  Eventually this parallelism will
break down because there will only be a limited number of local
battles, and the eventual status of points that are in the same chain
will almost always be the same.  Any practical program would need to
deal with this gracefully, of course, rather than duplicate its effort
many times.  Also, I only have a vague idea of how to take advantage
of the information gained from the local searches, when performing the
global search.

Weston

On 1/30/07, Dave Dyer <[EMAIL PROTECTED]> wrote:
> The idea isn't more than lightly toasted (less than half baked), but
> the kernal is turn the full board search into set of searches on
> much smaller boards, using the overlapping strips as boundary
> conditions, then do some unifying final step to pick the move.
___
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] Is skill transitive? No.

[Nick Apperson]

I completely agree with everything you have said.  I would also just add
that one thing humans learn to do, is to stear the game into zones where
they play better.  When facing a computer opponent, this generally means
stearing the game into positions where "judgement" is a much larger factor.
Computers generally don't understand their own weaknesses and strengths so
they are particularly prone to this type of assault.  It is also a similar
strategy that a strong player will use when they play double approach moves
in a handicap game.  For me, I haven't been playing go for as long as many
other people, but I have a very good intuition for the game.  I just lack
the mental stamina to read at "my level" so my friend will exploit this by
fighting in situations where he expects a slightly negative result because
he knows I will have to expend much of my finite mental energy on this which
will cause me to make a blunder later.

- Nick

On 1/29/07, Don Dailey <[EMAIL PROTECTED]> wrote:


I was looking at many of the posts on the threads about
how things scale with humans and computers and I'm
trying to reconcile many of the various opinions and
intuitions.  I think there were many legitimate points
brought up that I appeared to be brushing off.

In computations done by computer, there can usually be a
trade-off between time and memory.  In the discussions,
we rarely talked about memory and how it figures in to
the picture.  A lot was said about just knowing
something (where a strong player looks at a position and
instantly knows a weaker player made a mistake for
instance) and the feeling expresses by many was that
this was a barrier that could not be penetrated by
thinking about the position no matter how much time
was allowed.

Although I consider the evidence pretty strong for
rating curve in both humans and computer, the model of a
fixed strength increase per doubling is actually a
simplification - in the real world it is more
complicated than that.

It's important to realize that the ELO formula is based
on assumptions about human playing strength that are
only approximations.  One of those assumptions is that
playing strength is transitive and can be expressed as a
single value - a number that we call a persons "rating."

Nevertheless, intransitivity is a real thing.  The way
we sometimes erroneously think about GO is that you have
some fixed strength expressed as a kyu or dan "number"
and that every move is a reflection of this level of
play.

A better model, which is still a simplification, is that
a move is either right or wrong and the stronger you
are, the more likely you will choose the better move.
Some move are easy to find and the weaker players find
them, but on average you are faced with moves of every
level of difficulty and the difference between stronger
and weaker players is how many of these positions they
solve - kind of like a big test with a mixture of easy
and hard problems and the one that gets the most answers
right wins!

>From a purely theoretical point of view, a move really
is either best or not-best but as humans we judge moves
on a sliding scale of "goodness" and refer to some moves
as being horrible and others as being brilliant, good,
second best, etc.  On this group we recently discussed
how to define error vs blunder and so on.

The intuition behind judging moves like this is that
indeed, some moves give you better practical chances in
the real world.   So if you are slightly losing, a move
my be referred to as "a good try" because it complicates
things, or at least requires the opponent to find a
refutation that in human terms is difficult to find.

Sometimes a good player, or even a computer can
instantly find the right move where a weaker player has
no clue and is not likely to discover the correct
principle even given several hours of meditation.  This
has been mentioned a number of times recently.  This an
example of a chunk of knowledge having a profound effect
on the quality of a single move.  Even with computers it
is possible that a good life and death routine can
discover things (more or less) instantly that might take
a very long time to find with a global brute force
search.

Because knowledge can be imperfectly and unevenly
applied, one player might play some types of positions
much better than others.  So even among players of
roughly equal abilities, one player may see at a glance
what another player would have a very difficult time
discerning.

What this causes in my opinion is instransitivity.  It
doesn't cause a player to stop improving substantially
with time as many experiments have proved.  But it's a
known phenomenon that because of intransitivity and
these knowledge gaps, you might improve much more
against a particular opponent (opponents just like
yourself for instance) and much less against other kinds
of opponents.

But this is also about memory scalability.  Better
players have more knowledge about the game.  It's very
difficult to measure knowle

[computer-go] A ponder only engine

[Nick Apperson]

So I was thinking.  I wonder if anyone has written a go engine that can play
using only the time that it takes their opponent to think.  It seems some of
your monte carlo programs would be able to do this decently well.  Has
anyone tried to see how much it hurts the ranking of a program?  I would
estimate that it would lose only 600 ELO = around 3 doublings of thinking
time.  That is assuming the engine spends on *proper average 1/8 the time it
has trying the move that the opponent picked.  Proper average I am defining
to be: e^(mean(ln(time spent))).  So essentially, the expected ELO of the
move picked.  Any thoughts or data?

- Nick
___
computer-go mailing list
computer-go@computer-go.org
http://www.computer-go.org/mailman/listinfo/computer-go/

[computer-go] C++ GTP class wrappers

[Nick Apperson]

Hey all,

don't know if any of you are intereseted, but I am giveing out my GTP
wrappers written in C++.  I hope to improve them and add more features with
time.

http://www.nicholasapperson.com/go/computer

Any feedback is always welcome.

- Nick
___
computer-go mailing list
computer-go@computer-go.org
http://www.computer-go.org/mailman/listinfo/computer-go/

Re: [computer-go] an idea... computer go program's rank vs time

[Nick Apperson]

On 1/25/07, Don Dailey <[EMAIL PROTECTED]> wrote:


On Thu, 2007-01-25 at 20:16 -0600, Matt Gokey wrote:
> Don Dailey wrote:
> > You are still missing the point.
> I can say the same of you.
>
> I merely am raising a question about the assertion that doubling of
> _human_ thinking time results in _linear_ improvements. I am not
> claiming that there is no improvement - never have.  I am not claiming
> that every turn must produce better results to improve overall play -
> never have.  However I am trying to explain a rationale for the
> possibility that improvements may not be linear based on the nature of
Go.

It's possible,  but I think my curve (it is a curve, it gradually tapers
off as you get closer to perfection which is an obvious limit)  holds
in all non-trivial games of perfect information.   The curve may have
a different shape or slope but it's there.

It's already easy to produce in computer go despite a reluctance by
many (not you of course) to  admit it.   My sense is that
many on this group want to believe that we just happen to be at the
top of the curve but that it immediately falls off.   There is no
rational reason to believe that other than superstition.




I am not trying to say that you don't know what you are talking about, but
how are you so sure that we must be on the linear part of the curve?  Based
on what you said, I estimate your ideal (non empirical) formula to be
something like the following:

S = P * (1 - e^-kt)

where S is skill level and P is perfect play and k is some constant specific
to the game.  In fact this is an ideal formula that should apply given the
reasonable assumption that the chance of reading one unit of skill is
proportional to the amount of time taken and the amount left to be seen.
This makes sense assuming a very specific distribution of the difficulties
of different items that can be seen.  That distrobution would have to have
all units capable of being seen as equally likely to be seen.  I think this
could be a good theoretical model.


Anyway, I would like to see you make more specific claims with formula and
justifications for them.  Vague statements about linear relationships that
taper off and how we are clearly not anywhere near the top help nobody.  You
seem to know a lot about this.  I would appreciate it if you would share
your reasoning.  You seem pretty skeptical of intuition.  So, what is the
reason you believe these things about go?
___
computer-go mailing list
computer-go@computer-go.org
http://www.computer-go.org/mailman/listinfo/computer-go/

Re: [computer-go] an idea... computer go program's rank vs time

[Nick Apperson]

I don't rememeber citing you as saying that.  My however was in reference to
myself.

On 1/25/07, Don Dailey <[EMAIL PROTECTED]> wrote:


On Thu, 2007-01-25 at 12:17 -0600, Nick Apperson wrote:
> I am writing my program to scale to n processors because I think that
> is the direction hardware is headed.  However, I think clever
> programming will do more than computational power with go.

I take the point of view that clever programming IS more computational
power.  I have never advocated WASTING power.

- Don


___
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] an idea... computer go program's rank vs time

[Nick Apperson]

I am writing my program to scale to n processors because I think that is the
direction hardware is headed.  However, I think clever programming will do
more than computational power with go.

On 1/25/07, terry mcintyre <[EMAIL PROTECTED]> wrote:


So what would it take to get corporate sponsorship of the sort which
drove the chess computing field? Where is the Go equivalent of Deep
Thought?

Near as I can tell, David Doshay's Sluggo is the only large-scale
parallel effort. Mogo uses at most 4 CPUs. What might be accomplished
with one of the top500.org clusters of hundreds or thousands of CPUs?


--
Expecting? Get great news right away with email 
Auto-Check.
Try the Yahoo! Mail 
Beta.

___
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] an idea... computer go program's rank vs time

[Nick Apperson]

ofcourse you are correct, P = 1.0 is just the random player.  Obviously the
ELO as a function of P is going to be continuous.  So, being really close to
P=1.0 will make for a player that is only very slightly better than random.

I think it is also interesting to consider a player worse than random.  Take
your 1 trial MC program and instead of playing only moves than win, play
only moves that lose.  My guess is that the skill difference between this
program and random would be greater than between random and 1 trial MC, but
I would be interested to see a trial of this.

On 1/25/07, Stuart A. Yeates <[EMAIL PROTECTED]> wrote:




On 1/25/07, Don Dailey <[EMAIL PROTECTED]> wrote:
>
>
> I also had a difficult time producing a player that was less than
> 200 ELO stronger than a random player.   Even a single play-out,
> which seems hardly enough to discriminate between moves, is
> enormously stronger than a random player.It was pretty much
> like this:
>
>ASSUME computer is black


 0.  with probably P, play a random move (using the same selection
methodology as the random player)

   1. play 1 random game.
>
>2. If black wins,  play one of the first N black moves in the
>   play-out  (all-as-first, for me it's some-as-first.)
>
>3. If white wins, play one of the black move NOT in the play-out.
>
>4. Crush a random player!
>


Surely by varying P, you can get a player arbitarily close to the random
player?

Or am I missing something?

cheers
stuart

___
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] Can a computer beat a human?

[Nick Apperson]

actually, one more trip to Gateway Electronics (the local circuit parts
store) and my lookup table will be complete... suckers!

On 1/24/07, Don Dailey <[EMAIL PROTECTED]> wrote:




On Wed, 2007-01-24 at 21:11 +0100, alain Baeckeroot wrote:
> Le mercredi 24 janvier 2007 19:56, Stuart A. Yeates a écrit :
> > Since no one has mentioned bounding memory, a complete lookup table (a
> > complete table of correct moves, perfect-hashed by board state) should
do
> > the trick.
>
> With 10^170 legal position for 19x19 what would be the size of this
table ?
> I m afraid we cannot build it with all the matter in visible universe.

I'm glad you set us straight on that.

- Don





> Cheers.
> Alain
> ___
> 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] Can a computer beat a human?

[Nick Apperson]

To do a complete lookup you would need more than 32 GB of memory, but I
think that the question was more about making programs smarter more than it
was about unlimited hardware.  Infact, my question was what is the minimum
hardware.  That said, 300 Mhz should be plenty to do a lookup.  There are
what 10^170 legal positions.  That means that if you were able to generate
an index so that there was exactly one index into your lookup table for each
legal position.  You would need about a 564-bit number (or higher if it
proved too difficult to make a unique continuous indexing function).  You
would be able to perform that lookup with a 1KHz computer in a reasonable
amount of time (under a second) assuming the processor had a way to address
all that memory (I think even 512-bit processors are still a bit over the
horizen however...)



On 1/24/07, Chris Fant <[EMAIL PROTECTED]> wrote:


> Since no one has mentioned bounding memory, a complete lookup table (a
> complete table of correct moves, perfect-hashed by board state) should
do
> the trick.
>
> cheers
> stuart

You're going to need more than 300MHz to do that lookup.
___
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] Can a computer beat a human?

[Nick Apperson]

In my original question I stated minimum resources.  I agree with you that
lots of memory could be highly useful: "... I would say a computer with
perfect software, 32 GB of RAM (so a lot) and a 300 Mhz processor (slow
processor) would be able to beat a human." (from my original post)

So it sounds to me like most people think that if we had a perfect program,
computers would be able to win.  So at this point hardware will only allow
us to get away with writing less perfect code.

On 1/24/07, Stuart A. Yeates <[EMAIL PROTECTED]> wrote:



On 1/24/07, Don Dailey <[EMAIL PROTECTED]> wrote:

> I am fairly sure a perfect program would be impossible, even among
> the set of all possible programs that could find a move within let's
> say 60 seconds per move.


Since no one has mentioned bounding memory, a complete lookup table (a
complete table of correct moves, perfect-hashed by board state) should do
the trick.

cheers
stuart




___
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] Can a computer beat a human?

[Nick Apperson]

I am thinking that God would use a much larger portion of the memory as code
space.  Hardcoding lots of the programming.  Reason being, there would be no
point in learning and go has so many special cases that it might be easier
to do it this way (for a being that has lots of time to program that is).

On 1/24/07, Don Dailey <[EMAIL PROTECTED]> wrote:


On Wed, 2007-01-24 at 09:17 -0800, terry mcintyre wrote:
> > I could make a guess, but I certainly don't trust my intuition here.
> > My guess is that God could program a core 2 duo system of today to
> > beat a strong human.
>
>
> There are limits to what a core 2 duo can compute in a reasonable
> amount of time, no matter how sophisticated the program. So many
> instructions per second, so many bits of change, so much information
> gathered ... does this approach what a Meijin does with a large
> fraction
> of 10^15 neurons all working in tandem?

I envision God using something perhaps like an extremely sophisticated
neural net.  It would be enhanced way beyond what we know - and there
would be no training involved, it would just be hard coded with the
right connection weights.   However it's quite certain that this program
would be advanced WAY beyond the software we are writing today.

Of course I don't know if anything resembling a neural network would
be used, but I use it as an example.   It could have the ideal topology,
the ideal weights,  and a far more advanced design in general.

I also believe, based on the design of the human brain, that it might
have on the fly learning features.   When humans study a position for
a long time,  we tend to get "waves of understanding."I know I
have done that with chess,  where I think I understand the basics of
a position but as I consider it I keep getting updates that make me
understand it better.

Another thing we do when playing a game is that we don't start fresh
at every move.   Most of what we know about the 40th move we learned
from the first 39 moves - we just keep updating information as it's
added and removed.

There are many possibilities that an omniscient begin would know how
to add to a program.

I am fairly sure a perfect program would be impossible, even among
the set of all possible programs that could find a move within let's
say 60 seconds per move.

- Don


___
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] Can a computer beat a human?

[Nick Apperson]

Let me clear one thing up...  I mean, a professional go player.  A rough
approximation of what the human brain is capable of when it is optimized for
go compared with a computer that has its software optimized (not limited by
programming ability and programmer time) for go.

On 1/23/07, Joshua Shriver <[EMAIL PROTECTED]> wrote:


My 500mhz computer beats me fairly easy ;) with Gnugo so depends on
the person you're comparing.

-Josh

On 1/23/07, Nick Apperson <[EMAIL PROTECTED]> wrote:
> This is something I have been wrestling with.  It is kind of a
theoretical
> question.  Assuming a program that utilizes all avaliable resources
> perfectly.  It plays the best game you could ever program it to
play.  How
> fast would the computer have to be to beat a human?  I could see people
> argue that if the program had enough knowledge it could be a pretty slow
> computer (less than 100 Mhz), I could also see someone state the reality
> that our brains (when you sum up the computational power of an entire
> thinking brain) have way more processing power than a cluster of high
> performance workstations and so technology isn't able to provide
computer
> hardware that would be fast enough.  I think I vastly underestimate the
> human brain, but I would say a computer with perfect software, 32 GB of
RAM
> (so a lot) and a 300 Mhz processor (slow processor) would be able to
beat a
> human.  Thoughts?
>
> ___
> 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] Can a computer beat a human?

[Nick Apperson]

This is something I have been wrestling with.  It is kind of a theoretical
question.  Assuming a program that utilizes all avaliable resources
perfectly.  It plays the best game you could ever program it to play.  How
fast would the computer have to be to beat a human?  I could see people
argue that if the program had enough knowledge it could be a pretty slow
computer (less than 100 Mhz), I could also see someone state the reality
that our brains (when you sum up the computational power of an entire
thinking brain) have way more processing power than a cluster of high
performance workstations and so technology isn't able to provide computer
hardware that would be fast enough.  I think I vastly underestimate the
human brain, but I would say a computer with perfect software, 32 GB of RAM
(so a lot) and a 300 Mhz processor (slow processor) would be able to beat a
human.  Thoughts?
___
computer-go mailing list
computer-go@computer-go.org
http://www.computer-go.org/mailman/listinfo/computer-go/

Re: [computer-go] an idea... computer go program's rank vs time

[Nick Apperson]

you are right about my math being wrong.  I wasn't paying that much
attention to that step, but with the correct math (as was pointed out) you
end up with a linear equation assuming what I said to assume.  Man, its only
been a couple years and my precalc skills have gone to crap...  Thanks for
the correction.  And Dave, you said what I was trying to say, except
better.  The only thing I have to add is that one major difference between
humans and computers is that brains are able to think in parallel much more
effeciently.  For a game such as go, we are able to use that ability more
because of the larger branching factor.

On 1/23/07, [EMAIL PROTECTED] <[EMAIL PROTECTED]> wrote:


- Oorspronkelijk bericht -
Van: Matt Gokey <[EMAIL PROTECTED]>
Datum: maandag, januari 22, 2007 9:59 pm
Onderwerp: Re: [computer-go] an idea... computer go program's rank vs
time
> Nick Apperson wrote:
>
> > He is saying this (I think):
> >
> > to read m moves deep with a branching factor of b you need to
> look at p
> > positions, where p is given by the following formula:
> >
> > p = b^m (actually slightly different, but this formula is
> close enough)
> >
> > which is:
> >
> > log(p) = m log(b)
> > m = log(p) / log(b)
> >
> > We assume that a doubling in time should double the number of
> positions
> > we can look at, so:
> >
> >
> > m(with doubled time) = log(2p) / log(b)
> > m(with doubled time) = log(2) * log(p) / log(b)
> Your math is wrong (I think).
>
> The correct equivalency for the last line would be:
> m(with doubled time) = (log(2) + log(p)) / log(b)
>

Yes. Don's scalability argument states that ELO gain is proportional
to time doubling.
For me scalable use of time implies that time translates into depth.
The extra depth is:

m - m0 = log(2)/log(b).

So if the ELO gain for time doubling in Chess equals 100 over a wide
time scale and if Go has a 10 times larger branching factor than
Chess, then the ELO gain for time doubling in Go would equal 100/log
(10) = 43 (everything else assumed equal).

I'm not sure i agree with Don, but i just want so say that if he is
right, than mathematically he is also right with a larger branching
factor.

Dave
___
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] an idea... computer go program's rank vs time

[Nick Apperson]

He is saying this (I think):

to read m moves deep with a branching factor of b you need to look at p
positions, where p is given by the following formula:

p = b^m   (actually slightly different, but this formula is close enough)

which is:

log(p) = m log(b)
m = log(p) / log(b)

We assume that a doubling in time should double the number of positions we
can look at, so:


m(with doubled time) = log(2p) / log(b)
m(with doubled time) = log(2) * log(p) / log(b)

So, as we can see we get a linear relationship no matter what b, the
branching factor, is.  However, the slop on the line changes accordingly.
We are also assuming that the number of moves deep that one reads is
proportional to playing strength.  This is in fact simply a way of defining
playing strength.  There are many scales that could be constructed where
this is not the case, however, this is a good one to pick from a theory
perspective because the formula holds with any game that has a branching
factor.  What you are talking about in terms of using "sense" is another
factor is strength that isn't really addressed by the above math (in my
opinion).  There are certainly ways in which one could say that by having a
better sense of the game one can effectively reduce the branching factor,
but one could also say that sense could be capable of restructuring the way
people read a situation so that it is possible to read much deeper than is
allowed by simple brute force search strategy.  That is an issue for
psychologists to address.  I am looking forward to good data from
experiments on this subject to answer some of these questions.  I think
until we have good data for go, we won't really know.  Just my opinion
(guess it is the scientist in me...)

- Nick


On 1/22/07, Matt Gokey <[EMAIL PROTECTED]> wrote:


[EMAIL PROTECTED] wrote:
>>What if we look at it mathematically by looking at the branching
>>factor?
>>Go's branching factor is generally considered to be about an order
>>of
>>magnitude greater than chess – perhaps a bit less, right?  That
>>means
>>that after each ply go becomes another additional order of
>>magnitude
>>more complex.
>
>
> Mathematically a bigger branching factor does not matter. If the level
> increase is proportional to the 2log of time, then it is also
> proportional to the 10log of time. The only difference is the
> proportionality factor.
I'm not sure I follow your logic here.  Sounds like you are using the
hypothesis to support itself in a circular argument.  Perhaps you could
elaborate.



___
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] an idea for a new measure of a computer go program's rank.

[Nick Apperson]

the thing about blunders is that frequently one player making ablunder
causes the other player to make one as well.  For instance if one player
plays somewhere that can be ignored.  Frequently the other player will not
ignore it.  BOth are making blunders relative to perfect strategy but it is
very common.  And many times a sequence will be played out like this with
lots of the traded moves being blunders.  It is however more reasonable to
look at the choice to follow a sequence as the blunder and the choice of the
opponent to play it out a blunder.  That is 2 blunders not 30 if the
sequence is 30 moves.  In my opinion atleast.

- Nick

On 1/21/07, Ray Tayek <[EMAIL PROTECTED]> wrote:


At 03:43 AM 1/21/2007, you wrote:


>- Oorspronkelijk bericht -
>Van: Ray Tayek <[EMAIL PROTECTED]>
>Datum: zondag, januari 21, 2007 4:18 am
>Onderwerp: Re: [computer-go] an idea for a new measure of a computer go
> program's rank.
> >
> > also i suspect that at least 33% of the moves (at my 1-dan level)
> > are
> > wrong (what you might call in chess a "blunder"?).
> >
> > what do other people of different strengths think about this 33%?
> >
>
>I don't know the percentage of blunders. It also depends on what you
>call a blunder. Is a 1 point mistake a blunder?

no, maybe 10 or more points

thanks


---
vice-chair http://ocjug.org/


___
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] an idea for a new measure of a computer go program's rank.

[Nick Apperson]

Assuming that the average divergence from perfect play doubles every say 50
ELO points, you would expect that handicap stone would become worth less as
you went to lower ranks.  And this would also make sense because of how ELO
is defined.  You can imagine that a player that is perfect would only see
one move to play (or more if they are strictly equivalent), but a player 50
ELO weaker might see twice as many "valid games" defined as valid because
both players were playing their best the whole time.  This makes sense
because a handicap stone worth almost nothing to a random player.  It also
makes sense because komi has to be higher as players get better.

On 1/20/07, Ray Tayek <[EMAIL PROTECTED]> wrote:


At 05:30 PM 1/20/2007, you wrote:
>...
> >  I don't really know how  much 1 extra dan represents at this
> level - I think it translates to 200 or
> > more  ELO points.   We can figure this out - what is the win
> expectancy of 5  dan over 4 dan without handicap?
> >
>http://gemma.ujf.cas.cz/~cieply/GO/statev.html
>  4D   30.6% (out of 4000 games)

this seem to non linear. and indicates that the value of one handicap
stone is worth more the stronger you are. which would imply that the
differences between the ranks are greater the higher you go (seems
like it to me).

thanks

---
vice-chair http://ocjug.org/


___
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] Mega transposition table

[Nick Apperson]

I don't think Don was clear about whether he was using stack, heap or static
allocation of that structure.  I am just saying that it could be done in
such a way that any code anywhere can know where that object is without
having to pass around a pointer to the structure which is a really nice
feature in C/C++.  To do something like that in Java you have to contruct a
singleton or equivalent hack which is obviously slower and hacked design.
Of course the downside to having a global variable like that is that you can
only have one of those structures at a time, but for us that is likely to be
the case so it is worth making it static in my opinion.  It was really just
a side comment and the advantages of making it static aren't that big.

- Nick

On 1/19/07, Jim O'Flaherty, Jr. <[EMAIL PROTECTED]> wrote:


 Nick,

I am not sure I follow.  Are you implying the following
"...&(big_array[1300])" an strong indication that big_array is stack based,
as opposed to heap based?  It is possible to do such a thing as stack based
in Java, although quite uncustomary and require special start-up parameters
to force a larger stack to accommodate something so large.

However, my interpretation of Don's description and code had me assuming
he was preallocating tons of heap space.  If my assumption is accurate, then
I do the same thing in Java.  As for then interpreting the bits - I would do
the identical mechanics as are done in C without any "new" operator using
several different techniques depending upon whether this was a CPU or memory
bottleneck.


Don,

So could you elaborate on where you are allocating space for big_array in
your code snippet below?


Jim


Nick Apperson wrote:

This is a very good design in my opinion.  I was about to ask why you used
an index instead of a pointer until I saw that you were using a pointer
actually.  Using global data like this highlights one of the ways that C++
can blow away Java's requirement that everything must be allocated on the
heap.

On 1/19/07, Don Dailey <[EMAIL PROTECTED]> wrote:
>
> On Fri, 2007-01-19 at 16:51 +, Eduardo Sabbatella wrote:
> > Sorry, I didn't understand the big table but It sounds
> > promissing. I don't understand how do you access to
> > different variations ... it seems like a merge-sort
> > array but not sure.
>
> It forms a tree in memory, but it's just a huge array of nodes.
>
> Each node has this:
>
> move   - the move played from parent to get us here
> visits - number of times this node visited
> score  - number of wins from this node
> first_child- index of node of first child
> child_count- number of legal moves from this position.
>
> (the move and child_count are 16 bits, everything else 32 bits,
> total structure size = 32 + 32 + 32 + 16 + 16 bits. = 128 bits. )
>
> if child_count == 0 the node has not yet been expanded.
>
> If first child is stored at index 1300, for example and there
> are 10 children, then
>
>  1300 - first child
>  1301 - second child
>  1302 - third child
>  etc.
>
> first_child is actually a pointer in my implementation, but to
> make this explanation clearer you can think of it as an index
> into the global array.   In the example the pointer addresses
> array location 1300 .. in c ->  (node_t *) child = &(big_array[1300]);
>
> - Don
>
>
>
>
>
>
> ___
> computer-go mailing list
> computer-go@computer-go.org
> http://www.computer-go.org/mailman/listinfo/computer-go/
>

--

___
computer-go mailing list
[EMAIL PROTECTED]://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] Mega transposition table

[Nick Apperson]

This is a very good design in my opinion.  I was about to ask why you used
an index instead of a pointer until I saw that you were using a pointer
actually.  Using global data like this highlights one of the ways that C++
can blow away Java's requirement that everything must be allocated on the
heap.

On 1/19/07, Don Dailey <[EMAIL PROTECTED]> wrote:


On Fri, 2007-01-19 at 16:51 +, Eduardo Sabbatella wrote:
> Sorry, I didn't understand the big table but It sounds
> promissing. I don't understand how do you access to
> different variations ... it seems like a merge-sort
> array but not sure.

It forms a tree in memory, but it's just a huge array of nodes.

Each node has this:

move   - the move played from parent to get us here
visits - number of times this node visited
score  - number of wins from this node
first_child- index of node of first child
child_count- number of legal moves from this position.

(the move and child_count are 16 bits, everything else 32 bits,
total structure size = 32 + 32 + 32 + 16 + 16 bits. = 128 bits. )

if child_count == 0 the node has not yet been expanded.

If first child is stored at index 1300, for example and there
are 10 children, then

 1300 - first child
 1301 - second child
 1302 - third child
 etc.

first_child is actually a pointer in my implementation, but to
make this explanation clearer you can think of it as an index
into the global array.   In the example the pointer addresses
array location 1300 .. in c ->  (node_t *) child = &(big_array[1300]);

- Don






___
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] an idea for a new measure of a computer go program's rank.

[Nick Apperson]

especially because computers don't have to click the relevent move with a
mouse.  They just think it and its done.  Make a computer go program move
the mouse and click like the human or make a computer go program physically
place the stone on the board and if a computer can win in speed go, i'll be
impressed then.  Although that is a somewhat different task.

On 1/18/07, [EMAIL PROTECTED] <[EMAIL PROTECTED]> wrote:


I would not consider it very impressing nor interesting if a fast 10k
program beats strong players on time. It think the stronger player
will win with 10 seconds per move, but lowering the time limit until
the stronger player loses on time is just silly.

Dave

- Oorspronkelijk bericht -
Van: dan <[EMAIL PROTECTED]>
Datum: donderdag, januari 18, 2007 10:18 pm
Onderwerp: [computer-go] an idea for a new measure of a computer go
program's rank.

> Hi,
>
> The challenge to write a go playing program that could beat a
> professional was
> issued before the wide availability of Internet Go Servers, and
> broadband
> access.
>
> Under these new conditions, it is trivial to write such a program,
> provided
> the game takes place on a server, and at time limits chosen by the
> program.
> For example a random point playing program could choose time
> limits of half
> a second per move, sudden death.
>
> Therefore I suggest that a program's strength can (if needed) be
> expressed as
> the shortest time limits that a player of a standard strength (eg
> Pro. 1 dan)
> would be willing to play the program at, given an equal
> reward/loss regime
> (ie the chance of either winning would be 0.5).
>
> The format of time limits for such games would need to be
> standardised, for
> example - it could be decided that only limits of the type 'sudden
> death, x
> number of seconds per move' were allowed.
>
> In that case, 'x' could be used as a measure of the program's
> strength (as an
> abreviation for 'would beat a standard strength player half the
> time at x
> seconds per move')
>
> Of course the strength of a 'standard strength' Go player varies,
> and
> professional one dans would likely be unwilling to be beaten in
> ultra blitz
> games for the benefit of computer go programmers, so 'amateur 1
> dan' is a
> realistic idea for a standard strength go player.
>
> dan
>
>
>
> ___
> 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] Can Go be solved???... PLEASE help!

[Nick Apperson]

I bet Windows Vista would still run slow on God's computer though.  Go
Microsoft!  Sorry to get off topic, I just figure we have beat this subject
to death.

- Nick

On 1/17/07, Eduardo Sabbatella <[EMAIL PROTECTED]> wrote:


As far I know, just coffee speaking with some physics
friends. WE ALL live in multi dimensional world.
Indeed, if more then 3 dimensions exists, we exist in
them, also our computers.  The thing is, our eyes only
see the first three ones.

I think you are talking about the God's computer ;-).


--- Don Dailey <[EMAIL PROTECTED]> escribió:

> On Tue, 2007-01-16 at 16:21 -0800, Christoph Birk
> wrote:
> > On Sat, 13 Jan 2007, Don Dailey wrote:
> > > One of the theoretical limitations to
> > > computing power (which was layed out in someones
> posts) and I have
> > > always understood to be the case, is related to
> > > space - the physical size of the universe.
> >
> > The problem with higher dimensions is that they
> are small AND they do
> > NOT increase the 3-dimensional volume of our
> universe.
> > Imagine a 2 dimesional (finite) surface and bend
> it in some way
> > (eg. cylinder) ... even though your 2-dim
> "universe" exists now in
> > 3 dimensions, it did not increase in area.
> >
> > > If a computer can exist in 3
> > > dimensions,  couldn't an infinite number of them
> exist with 1 more
> > > dimension?
>
> I'm suggesting computers that might exist outside
> our 3 dimensional
> space, not confined to our 3 dimensional space.
> Perhaps there are
> beings that see our space as flat from their many
> dimensions and any
> physical objects they deal with, are infinitely
> bigger that we can
> observe.
>
> For instance if there existed 2 dimensional beings,
> we could not show
> them 3 dimensional objects, just reflections of them
> and any of our
> objects would be infinitely large to them.If we
> could build
> 2 dimensional computers, we could stack any number
> of them
> on top of each other and they would not take up any
> extra space,  no?
>
> - Don
>
>
>
> > Nope; see above.
> >
> > Christoph
>
> ___
> computer-go mailing list
> computer-go@computer-go.org
>
http://www.computer-go.org/mailman/listinfo/computer-go/
>







__
Preguntá. Respondé. Descubrí.
Todo lo que querías saber, y lo que ni imaginabas,
está en Yahoo! Respuestas (Beta).
¡Probalo ya!
http://www.yahoo.com.ar/respuestas

___
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] Can Go be solved???... PLEASE help!

[Nick Apperson]

oops, accidentally sent to just Don Dailey

-- Forwarded message --
From: Nick Apperson <[EMAIL PROTECTED]>
Date: Jan 13, 2007 5:11 PM
Subject: Re: [computer-go] Can Go be solved???... PLEASE help!
To: [EMAIL PROTECTED]

Here is a link for anybody that is interested in why I say 2 dimensions.
There are ofcourse many papers on it, but this is the basic idea.
Essentially says that the maximum amount of information is proportional to
the 2D surface around it.  Even if we live in a many-dimensional world (I
happen to believe we do), the area surrounding it would still be 2
dimensional as long as these are small dimensions.  Sorry to get off track I
just thought someone might find it interesting.  For us we are no where near
the theoretical limit of computing power, but if we had enough of it we
would be subject to the theoretical maximum.  Essentially, if you had enough
computers to reach this limit, they would collapse into a black hole.

http://en.wikipedia.org/wiki/Holographic_principle

- Nick

P.S.  Sorry I was going ape last night.

On 1/13/07, Don Dailey <[EMAIL PROTECTED]> wrote:


Ok Nick,

The funny thing about this,  is that I was originally defending someone
who
after making a simple post got flooded with all the stale size of the
universe
and grains of sands arguments - presumably to prove he was wrong when he
made
a simple statement which was correct.   He made the horrible mistake of
saying "1 billion" years and I guess that's where he went wrong.
Everyone
jumped in as if he was an idiot for thinking it would only take 1
billion years.

I also admit I got annoyed with those arguments about the size of the
game,
I felt it was pretty redundant and I don't know of anyone on this group
that needed a refresher course on this - everyone knows how huge this
problem is.

I'm sure you understand physics much more than I do.   However, I
disagree about dimensionality and if I'm wrong I have a thick skin and
you can explain it to
me and I will believe you.   One of the theoretical limitations to
computing power (which was layed out in someones posts) and I have
always understood to be the case, is related to
space - the physical size of the universe.If a computer can exist in
3
dimensions,  couldn't an infinite number of them exist with 1 more
dimension?
Couldn't one be constructed that is far more highly parallel that what
we
can construct in our 3 physical dimensions?


- Don




On Sat, 2007-01-13 at 03:38 -0600, Nick Apperson wrote:
> I would first just like to say, there have been many times in my life
> where I have known 1000 times more than someone else and I didn't feel
> the need to be an ass.  I'm sure you are a nice person, but please
> don't treat me like I am a moron.  Some assumptions you made about me
> that aren't true:
>
> 1) you assume I didn't understand what "solvable" means in a
> mathematical sense.  I think in a more important way, solvable means
> "is able to be solved" and frankly that question is still able to be
> debated regarding go.  From a mathematical standpoint, any game with a
> finite set of states is solvable.
>
> 2) You assume that I took 1 billion years literally...   Oh my, I
> would venture to say that I have had a whole lot more physics than you
> have my friend and I understand how people get those numbers.
>
> 3) You assume that I don't know that changing the board size doesn't
> necessariyl change all the properties of the game.  I mean how dumb do
> you think I am?
>
> But, I am going to point out a couple problems in what you said since
> you seem to be up for being an ass.
>
> 1) Multiple dimensions doesn't help at all.  Information processing
> ability as well as informataion storing ability is proportional to a
> 2D surface surrounding the area that is able to be used for the
> computation.  This is the upper limit given with thermodynamics which
> is probably the only part of physics that has laws that are well
> founded.
>
> 2) The reason I object to infinity as a concept is not because of my
> mental inferiority.  In fact, infinity is a concept that comes quite
> readily to me.  I learned it early in my youth and when I first saw a
> graph of velocity versus time (age 12 maybe) I knew that the area
> under it was displacement.  I had taken calc 2 as a sophmore in
> highschool.  The problem I have with it in regards to what you were
> talking about is that it has never been proven to exist anywhere in
> the actual world and there is lots of evidence that it doesn't exist.
>
>
>
> That said, I have seen you post before and I enjoy reading your posts,
> but please don't flame me.  Just because I am new to computer go
> doesn't mean I am a moron.  I might bring something new.  If y

Re: [computer-go] Testing against gnugo

[Nick Apperson]

This isn't quite the answer you seek, but one way to test it is to actually
use your program in the console and just type commands to it.  It is a text
based protocol.  I tested my GTP that way and it works perfectly with the
clients i've tried.  There is no GTP test though, but it would be nice to
have one.  Sorry I can't be of more help.

- Nick

On 1/13/07, Stuart A. Yeates <[EMAIL PROTECTED]> wrote:


A closely related question:

Is there a test suite for GTP, other than using the various forms of
TwoGTP?

I've got a computer-go player for which I'm currently writing an interface
to GTP, and would like to test it comprehensively, including the moves that
TwoGTP doesn't seem to use. I'm not averse to writing my own junit suite for
GTP, but would rather not duplicate anyone else's work (also, my
misunderstandings of the protocol are like to present themselves in both my
implementation and my tests...).


cheers
stuart

___
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] Can Go be solved???... PLEASE help!

[Nick Apperson]

I would first just like to say, there have been many times in my life where
I have known 1000 times more than someone else and I didn't feel the need to
be an ass.  I'm sure you are a nice person, but please don't treat me like I
am a moron.  Some assumptions you made about me that aren't true:

1) you assume I didn't understand what "solvable" means in a mathematical
sense.  I think in a more important way, solvable means "is able to be
solved" and frankly that question is still able to be debated regarding go.

From a mathematical standpoint, any game with a finite set of states is

solvable.

2) You assume that I took 1 billion years literally...   Oh my, I would
venture to say that I have had a whole lot more physics than you have my
friend and I understand how people get those numbers.

3) You assume that I don't know that changing the board size doesn't
necessariyl change all the properties of the game.  I mean how dumb do you
think I am?

But, I am going to point out a couple problems in what you said since you
seem to be up for being an ass.

1) Multiple dimensions doesn't help at all.  Information processing ability
as well as informataion storing ability is proportional to a 2D surface
surrounding the area that is able to be used for the computation.  This is
the upper limit given with thermodynamics which is probably the only part of
physics that has laws that are well founded.

2) The reason I object to infinity as a concept is not because of my mental
inferiority.  In fact, infinity is a concept that comes quite readily to
me.  I learned it early in my youth and when I first saw a graph of velocity
versus time (age 12 maybe) I knew that the area under it was displacement.
I had taken calc 2 as a sophmore in highschool.  The problem I have with it
in regards to what you were talking about is that it has never been proven
to exist anywhere in the actual world and there is lots of evidence that it
doesn't exist.



That said, I have seen you post before and I enjoy reading your posts, but
please don't flame me.  Just because I am new to computer go doesn't mean I
am a moron.  I might bring something new.  If you all had it figured out
already, we wouldn't be having this discussion.  I have a lot to learn from
you and I look forward to that.  Please be more respectful.  I am sorry that
this was a harsh message, but I feel you were unfair to attack me as you
did.

Sincerely,
Nick

On 1/12/07, Don Dailey <[EMAIL PROTECTED]> wrote:


On Fri, 2007-01-12 at 15:43 -0600, Nick Apperson wrote:
> yeah, there are upper limits placed on computation rate by
> thermodynamics.  19x19 is way beyond those as Dave pointed out.  But,
> even if you believe that technology will improve and the most
> revolutionary change yet will come to understanding of physics and
> that change will give us signifigantly more computational power and
> time etc...  You can always make a bigger board.  If life comes to a
> point where go could be solved for any size board, you will no longer
> be in this world and solving things such as "is go solvable?" will
> have no meaning.

Yes, you can always make a bigger problem by making a bigger go board
but
that doesn't change the theoretical properties of the game.   The game
will always be solvable.

The game might be trivially solvable even now to a being not confined
to our 3 physical dimensions.   I hate to get philosophical like this,
but there are theories of other dimensions that (if true) say we live
in a multi-dimensional universe.There may be much more here than
we can sense and that we can perhaps take advantage of.

But it doesn't matter.   When Chris said 1 billion years you should
have instantly realized that he didn't mean this literally,   he just
meant a correct procedure exists for solving the game. Since no
one has proved how long the universe will last, I don't think you
can even prove that in a practical sense it's unsolvable.   If you
lack imagination you can simply say it's not solvable because you
believe it can't be done in your lifetime - as if science and math
cares about how long we live or even the universe.If the universe
will die in 10 trillion years does that mean the number 20 trillion
is an impossible number?

The concept of infinity is important in mathematics.   It's even useful,
but I suppose that it really should be considered meaningless since
we all die after 70 or 80 years.

- Don



___
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] Can Go be solved???... PLEASE help!

[Nick Apperson]

indeed, and I think most of us wouldn't be here if we didn't think a better
rule could be designed.  Your point is well taken.  Sorry if I didn't
acknowledge it properly.

- Nick

On 1/12/07, Ray Easton <[EMAIL PROTECTED]> wrote:



On Friday, Jan 12, 2007, at 16:39 US/Central, Nick Apperson wrote:

> The solution is a rule. It is only a matter of how easy that rule is
> to apply. We have a rule that works now: Do a full min-max search on
> every move and play the move that results in the highest expected
> return given that your opponent is aiming for the lowest... Game
> theory gives us that rule and we know it works for all games. We
> might want a slightly more useful rule however. All rules require
> computation, just to varying degrees while returning varying degrees
> of correctness.

Well, of course.  But it appears that you were claiming a lot more than
that:

> a person would not be able to solve 19x19 because a person lacks the
> necessary computational resources to form a solution in any reasonable
> amount of time. A computer would therefore have to solve go.

What I'm asserting is that we do not know  -- and in fact have no good
reason to have any particular opinion -- about whether every rule for
Go requires this sort of computation.

Ray

___
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] Can Go be solved???... PLEASE help!

[Nick Apperson]

The solution is a rule.  It is only a matter of how easy that rule is to
apply.  We have a rule that works now: Do a full min-max search on every
move and play the move that results in the highest expected return given
that your opponent is aiming for the lowest...  Game theory gives us that
rule and we know it works for all games.  We might want a slightly more
useful rule however.  All rules require computation, just to varying degrees
while returning varying degrees of correctness.

On 1/12/07, Ray Easton <[EMAIL PROTECTED]> wrote:



On Friday, Jan 12, 2007, at 16:04 US/Central, Nick Apperson wrote:

> Mathematical solutions are certainly a good possibility to reduce the
> amount of processing power needed. However, a person would not be
> able to solve 19x19 because a person lacks the necessary computational
> resources to form a solution in any reasonable amount of time. A
> computer would therefore have to solve go.

For all we know, there may be a mathematical solution to Go that does
not depend upon performing any sort of computation.  For all we know,
there might be a *rule* that tells one how to play optimally.  There
are game that have such solutions.

It seems unlikely that this would be the case with Go, but it is not
impossible and I suspect that any "intuitions" any of us have about
this one way or the other are simply delusions -- we don't know enough
to have any genuine intuitions.

Ray

___
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] Can Go be solved???... PLEASE help!

[Nick Apperson]

I appreciate your response.  Mathematical solutions are certainly a good
possibility to reduce the amount of processing power needed.  However, a
person would not be able to solve 19x19 because a person lacks the necessary
computational resources to form a solution in any reasonable amount of
time.  A computer would therefore have to solve go.  I think this is as
close to a possibility as we can get, but it isn't enough to solve go.  And
if somehow it ever is, make the board bigger...  But, as I said, I think
your comment is a good one and suggests a strategy for computer go that I
think could be highly fruitful and I have been exploring.

- Nick

On 1/12/07, Vlad Dumitrescu <[EMAIL PROTECTED]> wrote:


Hi,

On 1/12/07, Nick Apperson <[EMAIL PROTECTED]> wrote:
> yeah, there are upper limits placed on computation rate by
thermodynamics.
> 19x19 is way beyond those as Dave pointed out.  But, even if you believe
> that technology will improve and the most revolutionary change yet will
come
> to understanding of physics and that change will give us signifigantly
more
> computational power and time etc...  You can always make a bigger
board.  If
> life comes to a point where go could be solved for any size board, you
will
> no longer be in this world and solving things such as "is go solvable?"
will
> have no meaning.

Well, if I may be excused for being way too pedantic on this topic,
raw computing power isn't the only way. Mathematical solutions might
easily reduce the search space just enough to allow a full search of
what's left of it.

On the other hand, I'm not worried. There will always be challenging
games to play and to try to master.

best regards,
Vlad
___
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] Can Go be solved???... PLEASE help!

[Nick Apperson]

yeah, there are upper limits placed on computation rate by thermodynamics.
19x19 is way beyond those as Dave pointed out.  But, even if you believe
that technology will improve and the most revolutionary change yet will come
to understanding of physics and that change will give us signifigantly more
computational power and time etc...  You can always make a bigger board.  If
life comes to a point where go could be solved for any size board, you will
no longer be in this world and solving things such as "is go solvable?" will
have no meaning.

On 1/12/07, [EMAIL PROTECTED] <[EMAIL PROTECTED]> wrote:


And Mark Boon also neglected the future use of wormholes, replicators
and who knows what? :)

Sorry, but how do you what future quantum computers can churn so much
data?

10^400 is a rediculously large number. Even if you multiply the volume
of the visible universe expressed in in cubic Planck lengths (1.4 e26
1.6x10^-36 m) by the age of the universe expressed in Planck times
(5.4x10^-44 s) and the higher estimate for the number of particles in
the universe (10^87) you get only 10^326, wich is much, much smaller
than 10^400.

It is impossible to handle this much data in the lifetime of the
universe, whatever the technology. Even if a device would use every
particle and every spacetime wrinkle in the universe in a big parallel
quantum computer at a clock cycle of 10^44 hz.

I do believe someone (something?) will eventually be able to build a
program that beats any human. But solve go? Never.

Dave

- Oorspronkelijk bericht -
Van: Chris Fant <[EMAIL PROTECTED]>
Datum: vrijdag, januari 12, 2007 7:03 pm
Onderwerp: Re: [computer-go] Can Go be solved???... PLEASE help!
> You neglected to consider the power of future quantum computers.
>
> On 1/12/07, Mark Boon <[EMAIL PROTECTED]> wrote:
> >
> >
> > On 12-jan-07, at 14:16, Chris Fant wrote:
> >
> >
> > Plus, some would argue that any Go
> >
> > already is solved (write simple algorithm and wait 1 billion years
> >
> > while it runs).
> > To 'solve' a game in the strict sense you need to know the best
> answer to
> > every move. And you need to be able to prove that it's the best
> move. To do
> > so you need to look at the following number of positions
> AMP^(AGL/2) where
> > AMP is average number of moves in a position and AGL is the
> average game
> > length. If I take a conservative AGL of 260 moves, we can
> compute the AMP
> > from that, being (365+(365-AGL))/2=235 So we get 235^130, which
> is about
> > 10^300 as a lower bound. The upper bound is something like
> 195^170 (play
> > until all groups have 2 eyes) which my calculator is unable to
> compute, but
> > I think it's roughly 10^400. I'm guessing it's questionable
> whether we'd be
> > able to compute that even with a computer the size of this
> planet before the
> > sun goes out. Distributing the work over other planets or star-
> sysems will
> > only help marginally due to the time it takes to send
> information to Earth
> > by the speed of light. So I'd say it's impossible.
> >
> > Mark
> >
> >
> > ___
> > 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] Re: Interesting problem

[Nick Apperson]

well, i'm pretty sure that against a top player i would need around 20
stones to have much of a shot, but if I remember correctly, at the
professional level, a 17-18 stone free placement is needed to take the
entire board.  A 9 stone handicap is not nearly enough to take the whole
board no matter where they are placed.

On 1/5/07, Heikki Levanto <[EMAIL PROTECTED]> wrote:


On Thu, Jan 04, 2007 at 04:37:08PM -0500, Don Dailey wrote:
>
> I have a question.  With perfect play, obviously a 9 stone handicap
> game is dead lost.   If 2 perfect players played a game where one
> was given the 9 stones, and they played for maximum territory (obviously
> it doesn't make sense to play for a win) would the handicapped player
> be able to hold some territory at the end of the game?Could he
> carve out a little piece for himself even against his perfect
> opponents wishes?

If the handicap stones are placed on the traditional points (4-4, etc),
then the answer is obviously yes. It is possible to live with a 3-3
invasion under such a stone.

If the handicap stones are placed at 3-4 points, there should be ample
room to approach from the side, and live in the corner or on the side.

I guess that if the stones are places on 3-3, it should be possible to
approach at 4-4, and slide to one of the sides, and possibly make a life
there. Here I am not strong enough to say for sure.

The last alternative I can think is to use 2 stones for each corner, but
that leaves the sides wide open. Black can invade the middle of a side,
and probably make a life there. Again I ask stronger players' opinions.


So, my guess is that white can always squeeze a small life somewhere. In
normal play black would of course welcome that, because he can secure so
much more by containing the small white group.

But what kind of player can give 9 stones to one who plays (near?)
perfect?

-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] Re: Interesting problem

[Nick Apperson]

The japanese rules have problems and there have been cases where 2
professionals argue about the outcome of a game.  They are not clearly
defined for obscure cases.  In addition, they are not simple.  Ing rules and
chinese rules are both reasonable sets of rules because there is no room for
argument about who wins.  Japanese rules in my opinion shouldn't ever be
used for tournements.

On 1/3/07, Don Dailey <[EMAIL PROTECTED]> wrote:


On Wed, 2007-01-03 at 14:30 -0800, David Doshay wrote:
> I think our only real disagreement is when and where we raise
> the bar. I think we could do it very soon in public tournaments.

But I don't feel any of this is important.   Japanese rules
isn't raising the bar - it's merely a different set of rules.

All that's really important is making your program play as well
as possible.   Japanese rules doesn't have anything to do with
this.

My terminology isn't quite right.  Forgiving ignorance is one
way to look at it,  but it conjures up images of "rewarding
ignorance" in humans and creating problems.   In my view Chinese
is more objective and logical  because it's
fair about penalizing ignorance.   If you play badly,  you
will be penalized and that's fair.   But in Japanese you
get penalized "needlessly" and "extra" in my view for not being sure
about something that I feel doesn't really matter anyway.

Of course I don't have any problem with writing programs that
can handle Japanese rules - but I thought this was already
common?

- Don


___
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] Fw: Compensation for handicap plays?

[Nick Apperson]

using gen_move to place handicap stones seems unreasonable to me when there
is a command intended for that purpose.  The point of GTP is to make it easy
to implement the protocol.  Anything that either breaks programs that are
written to the specification (as in using gen_move instead of
free_place_handicap) or makes GTP more complicated works.  "Implicit"
handicaps are rediculous.  Send it as the komi.  The following steps will
always make it clear to any bot that implements GTP correctly what they
should do:

1) send a komi
2) use the handicap functions built into GTP if they are supported
3) else, use gen_move
4) send play_move to other client
5) play out the game until both players pass
6) ask engines what stones are dead
7) if they disagree, keep playing if they support that
8) when both players pass again, ask them both to score the game
9) programs can score however they want, but it should be consistent with
the following:
   black wins if (# of black stones on board + # of spaces black has as
territory) > (komi + # of white stones on board + # of spaces white has as
territory)

chinese rules are consistent with this approach as are japanese rules if
both players pass an equal number of times.  Further, the komi should
include all compensation given because then programs don't need to be
programmed to support various different sets of compensation.  kgsGTP should
either have a layer put on top or itself altered so that komi includes all
compensation.  This was a mistake imho in how GTP talks with KGS and it
should be fixed.  These are just my thoughts.

- Nick

On 12/29/06, Weston Markham <[EMAIL PROTECTED]> wrote:


As someone who might write programs that will play on the server, I
would like to put my 2 cents in:

As long as the final score is simply the difference in the number of
intersections controlled by each of the players, adjusted by komi,
then I will be happy.  Whatever compensation for the handicap stones
is decided upon, it should be accounted for in the komi value sent by
the server, which should be exactly the komi value that is used to
adjust the final Tromp-Taylor score.  (This is clearly what Dave
Hillis has in mind.  Am I correct in inferring that this is also what
Don Dailey has in mind, but with no compensation for the handicap
stones?)

If I understand correctly, kgsGtp relies on some mechanism where the
compensation is implicit; so, either the komi value is not specified
by the server, or the komi value that is used to adjust the final
score is not the same as the value that is sent by the server.  (I am
not aware which is the case, since I have never used kgsGtp.)  This
might be incompatible with the mechanism that I describe above.  If
that is the case, it would be nice to have both of the GTP controller
programs would have special commands (say, "kgs_rules" and/or
"cgos_rules") that would be sent to the programs, in order to
explicitly inform them of the rules that are in effect.  (These could
take version numbers of the rule sets, as arguments, in order to allow
for future changes to the rules.)

Aside from this, I have one very minor complaint about simply asking
one player for multiple consecutive moves.  In my opinion, the player
should know ahead of time how many consecutive moves will be
requested.  The proposed method should only be used as a fallback, if
there are programs that we would like to participate on CGOS, but for
some reason these cannot be easily made to provide a
place_free_handicap command.  Even in that event, I would personally
prefer to simply wrap those programs behind adapter programs that will
automatically perform the translation of place_free_handicap to
multiple genmove commands.  (Does gtpadapter, available in gogui,
already do it?)

This latter point is minor.  If I don't get what I want, it really
won't bother me much.  However, at the moment it seems to me that it
should be such a small burden on developers to support the command,
that it is worthwhile to ask.

Weston

On 12/29/06, [EMAIL PROTECTED] <[EMAIL PROTECTED]> wrote:
>
>   This seems clean and reasonable to me. (Or you could just as
easily
> have the server do the adjustment and set Komi to 3.5; that would also
be
> consistent with TT rules). If my bot sees 2 black moves in a row, it can
> figure out it's in a handicap game.
>   A bigger question to me is, how large a handicap might be
encountered.
> Will we see Mogo playing Random with 100 stone handicap, or will
excessive
> mismatches be disallowed altogether?
>
> Dave Hillis
>
>  -Original Message-
>  From: [EMAIL PROTECTED]
> On Fri, 2006-
> 
> If your program is taking black you would get someting
> like this from the GTP channel:
>
>  clear_board
>  komi 0.5
>  boardsize 19
>  genmove black
>  genmove black
>  genmove black
>
> for a 3 stone handicap game. The opponent would get the
> corresponding consecutive play commands.
>
> I know this won't make everyone happy - but I believe it is
> more in the s

Re: [computer-go] Interesting problem

[Nick Apperson]

This is an interesting problem.  It seems to me that the reality is that
when you are talking about non-ideal play, ranking systems aren't linear.
Program A could beat B which could beat C which could beat A.  How would you
rank those?  Clearly there is going to have to be some degree of arbitrary
selection.  I propose convenience as the best reason for picking one anchor
over another.  I think a completely random player is the only other choice
from a theoretically perfect player that doesn't have arbitrariness.  But,
by defining players relative to that anchor, we would really be measuring
how effectively a program exploits a weak player rather than how good the
program is.

It is my opinion that it is more important to have a relative ranking system
than an absolute system.

- Nick

On 12/28/06, Aloril <[EMAIL PROTECTED]> wrote:


On Wed, 2006-12-27 at 21:34 -0500, Don Dailey wrote:
> I'm having an interesting problem - my hope is to set
> a random legal move making player (who doesn't fill
> 1 point eyes) at ELO zero.
>
> I feel this would define a nice standard that is
> easy to reproduce and verify experimentally and
> at least would be a known quantity even 100 years
> from now.
>
> But I'm having a difficult time creating players
> who are slightly better than this at 19x19.  I need
> incrementally better and better players.

I suspect this is quite hard problem. On 9x9 we have some of this and I
suspect even there "do not fill eyes random" (PythonBrown) has not yet
settled (maybe 100-200 ELO overrated). Probably too few weak players ;-)
On 19x19 I think problem is much harder and required amount of
intermediate players is much bigger. I'm of course interested in hearing
your experimentation results. Maybe I'm wrong and it is actually
feasible.

My vague recollection was that random player is maybe 200 kuy, "do not
fill eyes" adds 60 stones, atari detection adds about 20-30 stones,
idiotbot is maybe 100 kuy, weakbot50k maybe 50 kuy. However differences
between computers tend to be much bigger than when they play against
humans! For example GNU Go 2.0 can give Liberty 1.0 easily 9 stones and
win more than 50% of games (based on few ha9 test games), but at KGS
they are rated at 10k and 14k. Even WeakBot50k is rated at 20k while
latest GNU Go rated at 6k can give it numerous handicap stones (much
more than 14 stones, I think it's more than 40 stones).

Here is my proposal for anchor player: Use GNU Go 3.7.10 (or any enough
recent with super-ko support) at level 0 and use well defined
randomization on top of moves it returns. Ie. ask all_move_values (lists
only moves that gnugo considers positive) and add remaining moves and
then apply slight randomization so that it still plays close to original
strength but is much more unpredictable than GNU Go.

Example program (by blubb and me):
http://londerings.cvs.sourceforge.net/londerings/go/gtpTuner/

Reasons:
- reasonably strong, no need for huge amount of intermediate players
- source code available
- well known entity
- with some randomization should be unpredictable

I suspect that GNU Go without randomization is too predictable. This is
very clearly case on 9x9 board and possibly on 19x19 too.

--
Aloril <[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/

[computer-go] hello everybody

[Nick Apperson]

Hi all,

   I just signed up for this newsgroup and have been following the posts.
I am (you guessed it) building a computer go program.  My question is, what
tournament should I aim to be a part of?  I have been cruising the net
trying to figure out when the next big tournament is so that I can have my
program done by then.  I am writing everything from scratch using C++.  What
tournaments are  you all planning on going to?  Thanks, and I am really
excited to be a member of this community.

- Nick
___
computer-go mailing list
computer-go@computer-go.org
http://www.computer-go.org/mailman/listinfo/computer-go/