[computer-go] Congratulations to LeelaBot and to greenpeep!

[Nick Wedd]

The results of yesterday's KGS bot tournament are now available at
http://www.weddslist.com/kgs/past/32/index.html.

Your comments and corrections will be appreciated as usual.

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

[computer-go] Speed of generating random playouts

[Petr Baudis]

  Hi,

  I started experimenting with implementing own Go robot and first I
created a generic infrastructure that various engines should be able to
plug into. Currently, a random player and a straightforward MonteCarlo
bot (plays as zzgobot on KGS now) engines are implemented; the sources
are at

http://rover.dkm.cz/w/zzgo.git

in case anyone is interested. I chose to implement it in C so that I can
maximize raw computing speed, but the results have been rather
disappointing for me in this area.

  I'm now wondering about whether I should keep bothering about
optimizing the board library further or if what I have is good enough by
general standards already and I should instead start making the MC
playouts smarter (*NOW* I understand why you want to add domain-specific
knowledge like giving handling atari a preference ;-), implement UCT,
...

  Thus, I would like to ask, how fast can your engines play out random
games (and on what hardware)? My random playouts are limited only with
rule and do-not-fill-1pt-eye constraints.

  Currently, on my meager AMD 1.6 GHz (single core) my engine is able to
play 2500 games per second on 9x9 - with 1000 games per move candidate,
that is about 30s per move in the opening; but it seems that most people
prefer 1 instead of 1000. Is the difference all that visible?

  Based on what I have heard, this is not good at all, but I'm running
out of ideas on what to optimize, thus I'm asking so that I know what
should I set my goal to be here.

  Thank you,

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

Re: [computer-go] Congratulations to LeelaBot and to greenpeep!

[Chris Fant]

Nick, could you include MechaGozilla on
http://www.weddslist.com/kgs/names.html?  Thanks.

Some comments about MechaGozilla's performance...
There were two blunders.  Nick mentions the first one in his analysis.
 Mecha failed to play a move after the cleanup stage.  The other
blunder was that it did not attempt to make a move until about two
minutes into the first game against greenpeep.  The reason it finally
made a move was because I restarted the engine.  I hope that was not
in violation of the rules.  It lost that game anyway, so it did not
affect the outcome.  I fixed one bug between matches that I believe to
be the cause of both problems.  Both situations (the cleanup phase and
starting a game after another game ended) came up later in the
tournament and MechaGozilla handled them correctly.

To the MoGo team, thanks for letting me use your engine.  Sorry I let
you down  :)

-Chris


On Nov 12, 2007 10:30 AM, Nick Wedd <[EMAIL PROTECTED]> wrote:
> The results of yesterday's KGS bot tournament are now available at
> http://www.weddslist.com/kgs/past/32/index.html.
>
> Your comments and corrections will be appreciated as usual.
>
> Nick
> --
> Nick Wedd[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/

Re: [computer-go] Speed of generating random playouts

[Heikki Levanto]

On Mon, Nov 12, 2007 at 04:58:49PM +0100, Petr Baudis wrote:
>   I started experimenting with implementing own Go robot and first I
> created a generic infrastructure that various engines should be able to
> plug into. Currently, a random player and a straightforward MonteCarlo
> bot (plays as zzgobot on KGS now) engines are implemented; the sources
> are at
> 
>   http://rover.dkm.cz/w/zzgo.git

Interesting. I will take a look one of these days.

>   Thus, I would like to ask, how fast can your engines play out random
> games (and on what hardware)? My random playouts are limited only with
> rule and do-not-fill-1pt-eye constraints.

Have you looked at Lukas Lew's libEGO? You can download it and compare
performance. (I'm at work now, so I don't have the link, but googling Lew and
LibEGO will get it).

>   Currently, on my meager AMD 1.6 GHz (single core) my engine is able to
> play 2500 games per second on 9x9 - with 1000 games per move candidate,
> that is about 30s per move in the opening; but it seems that most people
> prefer 1 instead of 1000. Is the difference all that visible?

I may be wrong, but I suspect most of bots specify the total number of
simulations to play, not per move candidate. Thus, your '1000' should be
compared against a '81000' in the beginning of the game. That sounds like an
overly large number to me.  (I am hoping to [get the time to] make some
experiments to see how well I can play with 1k simulations, or even less. If
I like your coding style (and license), I may even switch over to your code,
as I prefer C to C++).

- Heikki

-- 
Heikki Levanto   "In Murphy We Turst" heikki (at) lsd (dot) dk

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

Re: [computer-go] Solving Go

[Harri Salakoski]

5x5 was solved with a massive brute force search approach.   Memory was
used for large hash tables and endgames were scored early using Bensons
algorithm, otherwise it would not have been feasible from what I 
understand.
Yes it was "proof" level paper, doing something lot less mathematically 
valid for example only some open source code which can do good search 
against 7*7 is more realistic. Kind of allowing all possible short-cuts, 
like using several patterns to judge board score even it is not absolutely 
sure that score is right for combination of patterns.



Although that's interesting,  it's just a search.   I would like to try
something a little more clever (I'm just not clever enough to figure out
what that should be!)
I'm thinking perhaps in terms of a database assist.   It would be
interesting if we could come up with a small board scoring system that
is very accurate.
Agree that goal, scoring system must be accurate _when_ it thinks it knows 
score. I see score meaning minimal score for player archieves from this 
position if plays right.



  A database system might identify rules and
exceptions that can be applied. For example, we have the eye rule in
our monte carlo programs - although that is extremely powerful it's not
100% admissible - there are some exceptions although they probably occur
only a fraction of a percent of the time. The eye rule would be
powerful in a hybrid system because it is a fairly large class of
positions where we can say, "never move to that point - it will never be
the best move."
But is this other class of used patterns also to guide search, I see this 
estimator goal should proof minmum scores for player.
All kind of eye knowledge is offcourse important for minimal scoring 
patterns.



A trivial way to include it in a hybrid system is to just put an entry
in a table for the few times that is wrong.   Or even better, try to
determine the exact context where it's wrong.Perhaps it's never
wrong in a 5x5 game?
I have thinked patterns which take area of board and proof that another 
player can take "X" points from that area/group.
If that player has benson alive groups in other areas on board score can be 
proven "benson alive groups" + one group which is not benson alive but can 
be proven to get "X" points if only defending that group for rest of game.



Tables like this can be stored compactly with bloom filters.

Here is a question.  How do you determine what a final board looks
like?   If you are actually building an endgame table, you start with
all the final positions.   But seki seems to be very difficult to 
identify.
I am planning partial table patterns. Seki and other consepts should be used 
with patterns if possible.



I'm doing a little experiment right now with small boards and a table
with a few million hashed entries.   I'm trying to store only perfect
scores in this table but my definition is weak.I search a position
using alpha/beta and if several iterations consecutively return the same
score,  I consider it a perfect score. I know this definition is
subject to error.
Yep, such practical problems are intresting, but atleast those are possible 
to fix as 5*5 and earlier proofs show.


It can be intresting attack 7*7 from end positions side, trying to make 
solver that gives exact score for part of positions and try to "increase" 
that procent but keep score exact. When end position scoring system is good 
enought then it could be possible try start search from some near end middle 
positions. I don't know is anybody really deebly investigated 7*7, kind of 
more like started existing go programs search algorithms from scratch and 
gived up. I also lack of 7*7 board knowledge, other hand 7*7 sounds 
practical, fast and light board.


t. harri


To handle ko,  I ignore everything except simple ko.   I don't store
positions where the previous move was a single stone capture since it
might be a simple ko. My hope is that long superko loops will be
avoiding by some winning side.This is probably not a correct
assumption, but I have read that it works on 5x5 and less - it's always
better for one side to break the loop.

The evaluation function is to consider every stone alive, and any empty
intersection that touches only one color to belong to that color.The
evaluation function is not really used though - except to identify
perfect scores (where several search iterations return the same
results.)

In all the 4x4 examples I've seen,  I've never seen a 3 iterations in a
row return the same score unless it was correct.   However, I'm using 4
in a row to determine that a score for a position is exact. If the
last 4 iterations return the same score, I put the root position in the
hash table as a perfect score.  I sample the space randomly by
making a random move after searching some position, so that it explores
the full space eventually. This is not very systematic, but it's
just for fun right now.


- Don



Ha

Re: [computer-go] Congratulations to LeelaBot and to greenpeep!

[John Tromp]

hi Nick,

On 11/12/07, Nick Wedd <[EMAIL PROTECTED]> wrote:
> The results of yesterday's KGS bot tournament are now available at
> http://www.weddslist.com/kgs/past/32/index.html.
>
> Your comments and corrections will be appreciated as usual.

You wrote:
"In the round 8 game between FirstGoBot and break13, this position
appeared. White has just captured two stones, and Black (break13)
tried to recapture one stone. This ought to be allowed, no superko
repetition is involved. However break13 was not allowed to recapture,
and eventually timed out. Readers of this page can confirm that
something has gone wrong by clicking on the above game link, using
CGoban to look at the game, and going to the final position. It is not
then possible to play a stone at L11, though it ought to be. This is
very odd, and I have reported it to wms."

However, there is nothing strange going on here. It's a simple
case of sending 2, returning 1, which is prohibited by Positional
Superko. Recapturing would repeat the position of 3 plies before
(with white to move instead of black).

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

Re: [computer-go] Congratulations to LeelaBot and to greenpeep!

[Don Dailey]

Hi John,

I get bug reports too, about once per month.   So far they have never
shown an actually superko bug.

- Don


John Tromp wrote:
> hi Nick,
>
> On 11/12/07, Nick Wedd <[EMAIL PROTECTED]> wrote:
>   
>> The results of yesterday's KGS bot tournament are now available at
>> http://www.weddslist.com/kgs/past/32/index.html.
>>
>> Your comments and corrections will be appreciated as usual.
>> 
>
> You wrote:
> "In the round 8 game between FirstGoBot and break13, this position
> appeared. White has just captured two stones, and Black (break13)
> tried to recapture one stone. This ought to be allowed, no superko
> repetition is involved. However break13 was not allowed to recapture,
> and eventually timed out. Readers of this page can confirm that
> something has gone wrong by clicking on the above game link, using
> CGoban to look at the game, and going to the final position. It is not
> then possible to play a stone at L11, though it ought to be. This is
> very odd, and I have reported it to wms."
>
> However, there is nothing strange going on here. It's a simple
> case of sending 2, returning 1, which is prohibited by Positional
> Superko. Recapturing would repeat the position of 3 plies before
> (with white to move instead of black).
>
> 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/

Re: [computer-go] Speed of generating random playouts

[Petr Baudis]

On Mon, Nov 12, 2007 at 05:11:22PM +0100, Heikki Levanto wrote:
> On Mon, Nov 12, 2007 at 04:58:49PM +0100, Petr Baudis wrote:
> >   Thus, I would like to ask, how fast can your engines play out random
> > games (and on what hardware)? My random playouts are limited only with
> > rule and do-not-fill-1pt-eye constraints.
> 
> Have you looked at Lukas Lew's libEGO? You can download it and compare
> performance. (I'm at work now, so I don't have the link, but googling Lew and
> LibEGO will get it).

Thanks, I will have a look!

> >   Currently, on my meager AMD 1.6 GHz (single core) my engine is able to
> > play 2500 games per second on 9x9 - with 1000 games per move candidate,
> > that is about 30s per move in the opening; but it seems that most people
> > prefer 1 instead of 1000. Is the difference all that visible?
> 
> I may be wrong, but I suspect most of bots specify the total number of
> simulations to play, not per move candidate. Thus, your '1000' should be
> compared against a '81000' in the beginning of the game. That sounds like an
> overly large number to me.

Oh! I must have misunderstood the Monte Carlo algorithm description in
that case.

What I do is taking every possible move candidate on current board,
playing out 1000 random games and track win-loss difference over the
sample. Then I choose the move candidate with the highest win-loss
difference. (If it is under -800, I resign.)

I intentially tried to come up with the simplest MonteCarlo-like
algorithm possible - it is supposed to be an example engine, after all.
Are there other possible algorithms for the MonteCarlo approach?
(Apart of UCT; that's the next step.)

I have had it play games on KGS over the day but I still don't have much
idea about its strength. I would say maybe around 15k, but mostly too
strong people play it and the weaker ones escape or undo (I have
disallowed that now).

> (I am hoping to [get the time to] make some
> experiments to see how well I can play with 1k simulations, or even less. If
> I like your coding style (and license), I may even switch over to your code,
> as I prefer C to C++).

It used to be nice code; as I desperately tried to optimize it, the code
got somewhat uglier in some parts. (I got it from initial 650 games per
second to 2500 gps, though!) You might not like the foreach macros. ;-)

The framework and the example engines are MIT-licensed (almost public
domain); I believe this is just something that noone should have to
reimplement yet another time, no matter how evil they are. If I get some
really well-performing engine built on top of it, I might license that
one under GPL or keep the code for myself, depending how evil *I* will
feel.

Since I have a nice number of my university department machines
available at night, I'm currently working on support for low-level
parallelization over many hosts in the infrastructure. I wonder if I can
dig out shells on at least 81 machines... ;-)

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

Re: [computer-go] Congratulations to LeelaBot and to greenpeep!

[Nick Wedd]

In message <[EMAIL PROTECTED]>, 
John Tromp <[EMAIL PROTECTED]> writes

hi Nick,

On 11/12/07, Nick Wedd <[EMAIL PROTECTED]> wrote:

The results of yesterday's KGS bot tournament are now available at
http://www.weddslist.com/kgs/past/32/index.html.

Your comments and corrections will be appreciated as usual.


You wrote:
"In the round 8 game between FirstGoBot and break13, this position
appeared. White has just captured two stones, and Black (break13)
tried to recapture one stone. This ought to be allowed, no superko
repetition is involved. However break13 was not allowed to recapture,
and eventually timed out. Readers of this page can confirm that
something has gone wrong by clicking on the above game link, using
CGoban to look at the game, and going to the final position. It is not
then possible to play a stone at L11, though it ought to be. This is
very odd, and I have reported it to wms."

However, there is nothing strange going on here. It's a simple
case of sending 2, returning 1, which is prohibited by Positional
Superko. Recapturing would repeat the position of 3 plies before
(with white to move instead of black).


Yes, you're right.  It's positional Superko.  It's surprisingly easy to 
miss this, even when you are looking for it.


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

Re: [computer-go] Solving Go

[Don Dailey]

Hi Harri,

I don't see a way to do anything larger than 5x5 as a table - and 5x5 is
pushing it.   Even if we had an arbitrary amount of memory it would take
a vast amount of time to enumerate all the positions for anything larger
than 5x5.

But I am more optimistic about some kind of practical solver based on
some the ideas we both mentioned.   It may be that even 7x7 is possible.
  You can test any idea based on scoring (but without 100% certainty) by
doing a search of many positions at different depths looking for
conflicting data, which would prove incorrectness.   It's much more
difficult to prove correctness.  So such a practical solver might
seem correct empirically, but difficult to prove correct. But that
would satisfy me since I am looking for practical applications (such as
building really strong small board players.)

One approach I would like to try to is to gradually build up a set of
rules (likely based on a combination of patterns and heuristics such as
Bensons algorithm)  that return a lower and upper bound on the score.   
For instance with 5x5 we can initially assign (-25, 25) as our upper and
lower bounds for ALL positions.   Rules to prune moves would also be
extremely useful since this would be a search based solver.  I think
for this to be practical the bounds function has to be able to produce
narrow bounds a lot and also it needs to be able to identify perfect
scores a lot.  To do 7x7 it has to produce trees with a branching
factor much lower than 2 and that will be very difficult.   

But first I will have to grapple with some difficult problems.   I am
experimenting with tiny boards such as 2x2 and 3x3.   Those are good
because you can brute force search them without even needing
transposition tables and without dealing with GHI.   

A brute force 2x2 search, using chinese scoring as the evaluation
function and simple KO,   does not produce a stable score.  It
alternates between 2 or 3 different values.I'm sure this is because
I'm using simple KO, but I will experiment with PSK and SSK.

A 3x3 board returns a score of 9, but if you play A2 and then search,
the score is not stable,  it will alternate between 2 scores from one
iteration to the next. If I play forward from there, I get
interesting patterns where one score repeats some number of times and
then another score, then the pattern repeats.Again, I'm thinking
that a good KO rule will solve this.  I'll let you know.

I'm not sure how to handle seki yet,  I'm hoping the deep search
approach will handle it on these small boards.

To summarize, I'm hoping to build an evaluation function that returns a
lower and upper bound for any position passed to it and furthermore I'm
hoping that this evaluation function is admissibly correct. I might
not be able to prove it's correct, but I can test each rule in a
significant way and try to get a lot of empirical evidence that it's
correct.

- Don







Harri Salakoski wrote:
>> 5x5 was solved with a massive brute force search approach.   Memory was
>> used for large hash tables and endgames were scored early using Bensons
>> algorithm, otherwise it would not have been feasible from what I
>> understand.
> Yes it was "proof" level paper, doing something lot less
> mathematically valid for example only some open source code which can
> do good search against 7*7 is more realistic. Kind of allowing all
> possible short-cuts, like using several patterns to judge board score
> even it is not absolutely sure that score is right for combination of
> patterns.
>
>> Although that's interesting,  it's just a search.   I would like to try
>> something a little more clever (I'm just not clever enough to figure out
>> what that should be!)
>> I'm thinking perhaps in terms of a database assist.   It would be
>> interesting if we could come up with a small board scoring system that
>> is very accurate.
> Agree that goal, scoring system must be accurate _when_ it thinks it
> knows score. I see score meaning minimal score for player archieves
> from this position if plays right.
>
>>   A database system might identify rules and
>> exceptions that can be applied. For example, we have the eye rule in
>> our monte carlo programs - although that is extremely powerful it's not
>> 100% admissible - there are some exceptions although they probably occur
>> only a fraction of a percent of the time. The eye rule would be
>> powerful in a hybrid system because it is a fairly large class of
>> positions where we can say, "never move to that point - it will never be
>> the best move."
> But is this other class of used patterns also to guide search, I see
> this estimator goal should proof minmum scores for player.
> All kind of eye knowledge is offcourse important for minimal scoring
> patterns.
>
>> A trivial way to include it in a hybrid system is to just put an entry
>> in a table for the few times that is wrong.   Or even better, try to
>> determine the exact contex

Re: [computer-go] Speed of generating random playouts

[Heikki Levanto]

On Mon, Nov 12, 2007 at 05:31:11PM +0100, Petr Baudis wrote:
> > 
> > I may be wrong, but I suspect most of bots specify the total number of
> > simulations to play, not per move candidate. Thus, your '1000' should be
> > compared against a '81000' in the beginning of the game. That sounds like an
> > overly large number to me.
> 
> Oh! I must have misunderstood the Monte Carlo algorithm description in
> that case.

It could also be me who is wrong! I am just an amateur hanging at the fringe
of the computer go world, programming small experiments with go when I am not
too tired from my daily programming job...

> I intentially tried to come up with the simplest MonteCarlo-like
> algorithm possible - it is supposed to be an example engine, after all.
> Are there other possible algorithms for the MonteCarlo approach?
> (Apart of UCT; that's the next step.)

There is the "all moves as first" (AMAF), that counts a win or loss not only
to the move that started the random playout, but to every move that was
played in that playout.  Somewhat weaker, they say, but gets good results
quicker (in a smaller number of simulations).

> I have had it play games on KGS over the day but I still don't have much
> idea about its strength. I would say maybe around 15k, but mostly too
> strong people play it and the weaker ones escape or undo (I have
> disallowed that now).

Why don't you play it on cgos, that is where most go programs meet? 
http://cgos.boardspace.net/

> It used to be nice code; as I desperately tried to optimize it, the code
> got somewhat uglier in some parts. (I got it from initial 650 games per
> second to 2500 gps, though!) You might not like the foreach macros. ;-)

I have to live with such macros in the libego code as well. As long as I
don't have to use them everywhere in my own code, I don't mind. And as long
as there are decent interfaces to the functions, I don't really care how ugly
the insides are coded.

> The framework and the example engines are MIT-licensed (almost public
> domain); I believe this is just something that noone should have to
> reimplement yet another time, no matter how evil they are. If I get some
> really well-performing engine built on top of it, I might license that
> one under GPL or keep the code for myself, depending how evil *I* will
> feel.

GPL is fine with me. I only want to be able to make my experiments and show
the world how I did it, in case I get some interesting results.

> Since I have a nice number of my university department machines
> available at night, I'm currently working on support for low-level
> parallelization over many hosts in the infrastructure. I wonder if I can
> dig out shells on at least 81 machines... ;-)

Interesting. But since those are not going to be equally powerful, nor
equally close to your master machine, I suspect there could be a more
efficient way to distribute the job among them, than just giving one
candidate move to each. Why not let each of them try all possible moves, and
report their results back after a given time. Simply sum up the results, and
choose the best. That way you can use as many or as few machines as you
happen to have at hand, and the fast ones don't need to wait for the slower
ones. But I think MC is so fast that this will not pay off. I seem to recall
that the quality of play does not improve much over 5000 play-outs, anyway.

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

Re: [computer-go] Speed of generating random playouts

[Heikki Levanto]

On Mon, Nov 12, 2007 at 04:58:49PM +0100, Petr Baudis wrote:
>   http://rover.dkm.cz/w/zzgo.git

I seem not to be able to find anything there. Is that link correct?

  - Heikki

-- 
Heikki Levanto   "In Murphy We Turst" heikki (at) lsd (dot) dk

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

Re: [computer-go] Speed of generating random playouts

[Petr Baudis]

On Mon, Nov 12, 2007 at 06:05:01PM +0100, Heikki Levanto wrote:
> On Mon, Nov 12, 2007 at 04:58:49PM +0100, Petr Baudis wrote:
> > http://rover.dkm.cz/w/zzgo.git
> 
> I seem not to be able to find anything there. Is that link correct?

Sorry, it's http://repo.or.cz/w/zzgo.git

Petr "Pasky" Baudis
___
computer-go mailing list
computer-go@computer-go.org
http://www.computer-go.org/mailman/listinfo/computer-go/

Re: [computer-go] Solving Go

[Don Dailey]

Ok,  on 2x2 I get a consistent result now that I implemented PSK.   It
gives the same result with SSK too.  It's a 1 point win for the first
player. I'm not sure this is in agreement with other peoples
findings.   But it appears to be consistent.I can work my way
through the game and it always returns the same score if I make the
move(s) the search believes is best.

After black plays the first move,  white's best response is to move to
the opposite corner.Otherwise it's a 4 point win for black.


Here are the parameters I use:

   1.  positional superko unless otherwise stated.
   2.  evaluation function:   Each stone is alive - an empty point
belongs to a player if only his stones touch it.
   3.  game over after 2 passes. 
   4.  suicide illegal.


3x3 gives a black win by 9 points (the whole board.) 

If black plays first move on the edge (a2 for instance)  then he wins by
3 points instead of 9.
If black plays first move on corner,  white wins by 9 points.

Does anyone have any data to check these "facts" ??

It may try this with 4x4 after doing something to improve the move ordering.


- Don





Harri Salakoski wrote:
>> 5x5 was solved with a massive brute force search approach.   Memory was
>> used for large hash tables and endgames were scored early using Bensons
>> algorithm, otherwise it would not have been feasible from what I
>> understand.
> Yes it was "proof" level paper, doing something lot less
> mathematically valid for example only some open source code which can
> do good search against 7*7 is more realistic. Kind of allowing all
> possible short-cuts, like using several patterns to judge board score
> even it is not absolutely sure that score is right for combination of
> patterns.
>
>> Although that's interesting,  it's just a search.   I would like to try
>> something a little more clever (I'm just not clever enough to figure out
>> what that should be!)
>> I'm thinking perhaps in terms of a database assist.   It would be
>> interesting if we could come up with a small board scoring system that
>> is very accurate.
> Agree that goal, scoring system must be accurate _when_ it thinks it
> knows score. I see score meaning minimal score for player archieves
> from this position if plays right.
>
>>   A database system might identify rules and
>> exceptions that can be applied. For example, we have the eye rule in
>> our monte carlo programs - although that is extremely powerful it's not
>> 100% admissible - there are some exceptions although they probably occur
>> only a fraction of a percent of the time. The eye rule would be
>> powerful in a hybrid system because it is a fairly large class of
>> positions where we can say, "never move to that point - it will never be
>> the best move."
> But is this other class of used patterns also to guide search, I see
> this estimator goal should proof minmum scores for player.
> All kind of eye knowledge is offcourse important for minimal scoring
> patterns.
>
>> A trivial way to include it in a hybrid system is to just put an entry
>> in a table for the few times that is wrong.   Or even better, try to
>> determine the exact context where it's wrong.Perhaps it's never
>> wrong in a 5x5 game?
> I have thinked patterns which take area of board and proof that
> another player can take "X" points from that area/group.
> If that player has benson alive groups in other areas on board score
> can be proven "benson alive groups" + one group which is not benson
> alive but can be proven to get "X" points if only defending that group
> for rest of game.
>
>> Tables like this can be stored compactly with bloom filters.
>>
>> Here is a question.  How do you determine what a final board looks
>> like?   If you are actually building an endgame table, you start with
>> all the final positions.   But seki seems to be very difficult to
>> identify.
> I am planning partial table patterns. Seki and other consepts should
> be used with patterns if possible.
>
>> I'm doing a little experiment right now with small boards and a table
>> with a few million hashed entries.   I'm trying to store only perfect
>> scores in this table but my definition is weak.I search a position
>> using alpha/beta and if several iterations consecutively return the same
>> score,  I consider it a perfect score. I know this definition is
>> subject to error.
> Yep, such practical problems are intresting, but atleast those are
> possible to fix as 5*5 and earlier proofs show.
>
> It can be intresting attack 7*7 from end positions side, trying to
> make solver that gives exact score for part of positions and try to
> "increase" that procent but keep score exact. When end position
> scoring system is good enought then it could be possible try start
> search from some near end middle positions. I don't know is anybody
> really deebly investigated 7*7, kind of more like started existing go
> programs search algorithms from scratch and gived up. I also lack of
> 7*7 

Re: [computer-go] Solving Go

[John Tromp]

On 11/12/07, Don Dailey <[EMAIL PROTECTED]> wrote:
> Ok,  on 2x2 I get a consistent result now that I implemented PSK.   It
> gives the same result with SSK too.  It's a 1 point win for the first
> player. I'm not sure this is in agreement with other peoples
> findings.   But it appears to be consistent.I can work my way

Yes, this is consistent with my programs at
  http://www.cwi.nl/~tromp/java/go/twoxtwo.html

> through the game and it always returns the same score if I make the
> move(s) the search believes is best.
>
> After black plays the first move,  white's best response is to move to
> the opposite corner.Otherwise it's a 4 point win for black.

> Here are the parameters I use:
>1.  positional superko unless otherwise stated.
>2.  evaluation function:   Each stone is alive - an empty point
> belongs to a player if only his stones touch it.
>3.  game over after 2 passes.
>4.  suicide illegal.

Suicide is particularly useless on 2x2 :-)

> 3x3 gives a black win by 9 points (the whole board.)
> If black plays first move on the edge (a2 for instance)  then he wins by
> 3 points instead of 9.

The only subtlety is that after white B2, black must "clamp" at c2,
since the hane moves at b1/b3 only win by 2.

> If black plays first move on corner,  white wins by 9 points.
> Does anyone have any data to check these "facts" ??

matches manual analysis and previous computer search.

> It may try this with 4x4 after doing something to improve the move ordering.

That should come out as B+2.

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

Re: [computer-go] Speed of generating random playouts

[Heikki Levanto]

On Mon, Nov 12, 2007 at 06:10:21PM +0100, Petr Baudis wrote:
> Sorry, it's http://repo.or.cz/w/zzgo.git

I've had a quick look at it, and have already two comments:

1) You seem to use struct {x,y} for coordinates all the way. I think using a
single int is usually faster. I was involved with GNU Go when we made that
change, and it did make sense. Gives some speed, but costs a bit of work, and
some readability.

2) It looks like your montecarlo algorithm tries to pick random points and
discards those that are not empty or legal to play in. It ought to be faster
to make a list of legal points in advance (or at least empty ones), and pick
from that list. This list can be maintained incrementally during the MC
simulation.


Still, I like your style, and may yet decide to take advantage of your
library instead of LibEGO at least in some of my experiments.

  - Heikki

-- 
Heikki Levanto   "In Murphy We Turst" heikki (at) lsd (dot) dk

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

Re: [computer-go] Speed of generating random playouts

[Christoph Birk]

On Mon, 12 Nov 2007, Heikki Levanto wrote:

I may be wrong, but I suspect most of bots specify the total number of
simulations to play, not per move candidate. Thus, your '1000' should be
compared against a '81000' in the beginning of the game. That sounds like an
overly large number to me.


Oh! I must have misunderstood the Monte Carlo algorithm description in
that case.


My code (myCtest- on CGOS) works like yours. But when I (and others)
refer to 10k playout that's still the total (not per candidate move).

My (not very optimized) C-code plays 12k games per seconds from the
opening position. The average game length is about 109 moves using
an early-termination rule when a "big" group gets captured that leaves
"most" stones beeing from one color.

I strongly recommend using CGOS for tests as you get a lot of games
against a great variety of (computer) opponents. It allows you in
particular to verify your (basic) algorithms:

pure MC 10k 1050 ELO
50k 1350
AMAF10k 1450
50k 1450
UCT 10k 1300
50k 1550

All algorithms above are "basic" playouts. No Go knowledge, except
the "dont-fill-your-1-pt-eye" rule.

Christoph

ps. 3.2 GHz Pentium4, Linux (Fedora Core-5)
___
computer-go mailing list
computer-go@computer-go.org
http://www.computer-go.org/mailman/listinfo/computer-go/

Re: [computer-go] Speed of generating random playouts

[Imran Hendley]

Sorry I did not have time to look at your code, but here a few quick hints:

1) Before any optimization make sure that your code works 100%
correctly. This means testing extensively and writing tests that you
can use as you start optimizing to make sure nothing breaks in the
process. You might get into big trouble if there is a bug you find
after doing lots of optimizations.

2) Learn how to profile your code. I don't work in C so unfortunately
I can't give you specific directions. But this is always the first
step in optimizing a large project. When you can see exactly where
your bottlenecks are it is 100 times easier and more efficient to
optimize. Without profiling you might find yourself spending a week on
an optimization that ends up giving you only 1% speedup.

The main optimization for me was squeezing every little bit out of
random number generation. This meant using a third party random number
generator in java (because the built in one is slow and also not
really pseudorandom anyway) and using various other tricks...

3) Think very carefully about data structures and algorithms at a high
level. I tried to simplify my board structure and my structure for
representing strings as much as possible and this also generated a lot
of speedup. As the last poster mentioned, if you are picking a random
intersection and rejecting the ones that are occupied until you have
filled the board this will take a lot longer than mainting a list of
empty intersections and only sampling from these. More specifically,
only sampling from empty intersections will take O(n) to fill the
board, while sampling with replacement and rejecting occupied
intersections will take O(nlogn) which is actually pretty bad since a
lot of time is spent deciding where to play as it is.

I hope that helps!

On Nov 12, 2007 2:45 PM, Heikki Levanto <[EMAIL PROTECTED]> wrote:
> On Mon, Nov 12, 2007 at 06:10:21PM +0100, Petr Baudis wrote:
> > Sorry, it's http://repo.or.cz/w/zzgo.git
>
> I've had a quick look at it, and have already two comments:
>
> 1) You seem to use struct {x,y} for coordinates all the way. I think using a
> single int is usually faster. I was involved with GNU Go when we made that
> change, and it did make sense. Gives some speed, but costs a bit of work, and
> some readability.
>
> 2) It looks like your montecarlo algorithm tries to pick random points and
> discards those that are not empty or legal to play in. It ought to be faster
> to make a list of legal points in advance (or at least empty ones), and pick
> from that list. This list can be maintained incrementally during the MC
> simulation.
>
>
> Still, I like your style, and may yet decide to take advantage of your
> library instead of LibEGO at least in some of my experiments.
>
>   - 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] Speed of generating random playouts

[Petr Baudis]

On Mon, Nov 12, 2007 at 08:45:14PM +0100, Heikki Levanto wrote:
> On Mon, Nov 12, 2007 at 06:10:21PM +0100, Petr Baudis wrote:
> > Sorry, it's http://repo.or.cz/w/zzgo.git
> 
> I've had a quick look at it, and have already two comments:
> 
> 1) You seem to use struct {x,y} for coordinates all the way. I think using a
> single int is usually faster. I was involved with GNU Go when we made that
> change, and it did make sense. Gives some speed, but costs a bit of work, and
> some readability.

Thanks for the tip, I will have a look at it.

> 2) It looks like your montecarlo algorithm tries to pick random points and
> discards those that are not empty or legal to play in. It ought to be faster
> to make a list of legal points in advance (or at least empty ones), and pick
> from that list. This list can be maintained incrementally during the MC
> simulation.

I have rewritten it so that it now picks a random point at the board,
then searches the whole board starting from that point and picks up the
first valid point.

I guess this is pretty much equivalent to what you suggested?

Incrementally maintaining cache of legal points would be probably huge
win, but seems very hard to do to me. Anyway, the most time-consuming
part is maintenance of liberty count for all the groups.

> Still, I like your style, and may yet decide to take advantage of your
> library instead of LibEGO at least in some of my experiments.

In the meantime I have moved random move generator to the board library
(and it's much faster now, apparently speeding up random games playing
from 2500 to 3500 - wow), and converted the example monte carlo engine
to use total number of moves instead of per move candidate.

It's interesting how the latter completely changed the playing style of
the bot. Before, it used to play very solid moves and liked very much to
crawl around the board. It usually ended up making a chain of stones in
the middle of the board, then running out of eyespace. Now it jumps
around much wilder.


Does any frequently playing real-world bot use libEGO? It seems still
order of magnitude faster, but it looks like that is because it
simplifies some things too much. For example, its board::merge_chains()
does not seem to take account for merging chains that might have had
liberties in common. But maybe I just overlooked something?

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

Re: [computer-go] KGS connection

[Nick Wedd]

In message <[EMAIL PROTECTED]>, 
Chris Fant <[EMAIL PROTECTED]> writes

Do you know of any reasons why it would not be granted to the program author?


1.  The admin considering granting it is not fully certain that the bot 
account is indeed controlled by the program author.
2.  The program is very volatile in strength, with new algorithms being 
tested, so its presence in the rating system will be destructive.


Reason 1 is the usual reason for refusals.  I suspect that I know more 
than any other KGS admin about which are bona fide programs controlled 
by their authors rather than GNU Go clones controlled by children;  most 
admins are unwilling to get involved.  I have now discussed this with 
other KGS admins.


So if for instance you, Chris, want MechaGozilla set to rated, I will do 
it for you.


Nick




On Nov 9, 2007 12:53 PM, Nick Wedd <[EMAIL PROTECTED]> wrote:

In message <[EMAIL PROTECTED]>,
Chris Fant <[EMAIL PROTECTED]> writes
>Unlikely to be granted?  I assume you mean only if you are not the
>program author?

It is more likely to be granted if you can convince them that you are
the author;  but by no means certain.  I don't know what the guidelines
are.  As an admin myself, I ought to know.  I shall try to find out.

Nick


>On Nov 9, 2007 12:17 PM, Nick Wedd <[EMAIL PROTECTED]> wrote:
>> In message
>> <[EMAIL PROTECTED]>, Joshua
>> Shriver <[EMAIL PROTECTED]> writes
>> >Aye, it would be bad to enter a tournament with a bot I didn't write.
>> >I was thinking more general. Just for play.
>>
>> Anyone can run a bot on KGS, the only obstacles are the small amount of
>> technical competence required to get it and kgsGtp running and
>> connected, and the need for an internet-connected platform to run it on.
>> The bot can be one that they have written, downloaded, or stolen, KGS
>> won't know nor care.
>>
>> Running a _rated_ bot on KGS is another matter.  This requires active
>> intervention by an admin, which is unlikely to be granted.  While your
>> bot is unrated, it won't be able to play any rated games, and won't
>> acquire a rating.
>>
>> Nick
>> --
>> Nick Wedd[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/

--

Nick Wedd[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/


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

[computer-go] Language

[Chris Fant]

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/

Re: [computer-go] Language

[Lars Nilsson]

On 11/12/07, 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)

OCaml. Check on all counts.

Lars Nilsson
___
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] Language

[Peter Drake]

Opinions may differ as to what counts as "fast", but Java may be your  
best choice here.


(Hint: double your speed by using the -server command-line option.)

Peter Drake
http://www.lclark.edu/~drake/




On Nov 12, 2007, at 1:41 PM, 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/

Re: [computer-go] Language

[terry mcintyre]

From: Peter Drake <[EMAIL PROTECTED]>

> Opinions may differ as to what counts as "fast", but Java may be your  best 
> choice here.

> (Hint: double your speed by using the -server command-line option.)


I googled "java option server" and found this tidbit which goes into more 
detail:


In the article "Performance Tuning in Java", Java Developer's Journal,
August 2002, Dov Kruger wrote: "Let's start by saying that if you want
a program to run fast, get JDK 1.4 and run it with optimization turned
on:

java -server MyClass



The -server option scans the entire loaded program as it's being run,
eliminating methods by inlining them, turning methods into native
assemblers, removing constant evaluations from loops, and other
optimizations. It improves performance, often by a factor of 10 in
CPU-intensive bits of code. It might surprise you to think about
optimizing programs at runtime, but considering that Java runs on
different machine, the only way to optimize for your processor is at
runtime.






__
Do You Yahoo!?
Tired of spam?  Yahoo! Mail has the best spam protection around 
http://mail.yahoo.com ___
computer-go mailing list
computer-go@computer-go.org
http://www.computer-go.org/mailman/listinfo/computer-go/

Re: [computer-go] Language

[Chris Fant]

I'm not a troll, I promise.  I'm asking because I want to start a new
project.  I already have a bunch of code in C++, but I've never
considered myself an expert.  I think I'll cherry-pick from that and
convert to use smart pointers.  Thanks for the help.


On Nov 12, 2007 5:03 PM, terry mcintyre <[EMAIL PROTECTED]> wrote:
>
>
> From: Peter Drake <[EMAIL PROTECTED]>
>
>
> > Opinions may differ as to what counts as "fast", but Java may be your
> best choice here.
>
> > (Hint: double your speed by using the -server command-line option.)
>
> I googled "java option server" and found this tidbit which goes into more
> detail:
>
> 
> In the article "Performance Tuning in Java", Java Developer's Journal,
> August 2002, Dov Kruger wrote: "Let's start by saying that if you want a
> program to run fast, get JDK 1.4 and run it with optimization turned on:
>  java -server MyClass
>
>  The -server option scans the entire loaded program as it's being run,
> eliminating methods by inlining them, turning methods into native
> assemblers, removing constant evaluations from loops, and other
> optimizations. It improves performance, often by a factor of 10 in
> CPU-intensive bits of code. It might surprise you to think about optimizing
> programs at runtime, but considering that Java runs on different machine,
> the only way to optimize for your processor is at runtime.
>  
>
>
> __
> Do You Yahoo!?
> Tired of spam? Yahoo! Mail has the best spam protection around
> http://mail.yahoo.com
> ___
> 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] Speed of generating random playouts

[Eric Boesch]

On 11/12/07, Petr Baudis <[EMAIL PROTECTED]> wrote:
> Does any frequently playing real-world bot use libEGO? It seems still
> order of magnitude faster, but it looks like that is because it
> simplifies some things too much. For example, its board::merge_chains()
> does not seem to take account for merging chains that might have had
> liberties in common. But maybe I just overlooked something?

I believe those are pseudo-liberty counts, not actual liberty counts.
If either count equals zero, then the other one will too, so
pseudo-liberties are good enough for identifying suicide and captures.
Check the mailing list archive.
___
computer-go mailing list
computer-go@computer-go.org
http://www.computer-go.org/mailman/listinfo/computer-go/

Re: [computer-go] Language

[Phil Garcia]

> - Original Message 
> From: Chris Fant <[EMAIL PROTECTED]>
> 
> I'm not a troll, I promise.  I'm asking because I want to start a new
> project.  I already have a bunch of code in C++, but I've never
> considered myself an expert.  I think I'll cherry-pick from that and
> convert to use smart pointers.  Thanks for the help.

Consider C# since you are already familiar with C++. Yes, it's not as fast as 
native C, but it's easier to develop in C# because of it's automatically memory 
management, gargage collection, generics, class libraries, etc. I'm pretty good 
at C/C++ but writing/testing/debuging in C# is several times faster. The 
trade-off between code speed and development time may be worth wild for you.  
It also meets all your requirements, including MPI and Linux (using the Mono).
 
BTW. The type of optimization that Peter mentioned for Java is automatically in 
C#.

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

Re: [computer-go] Language

[Don Dailey]

D is a truly beautiful language that has all things you require.   I
recommend it highly. 

Ocaml is another viable choice if you are willing to delve into
functional programming.

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

Re: [computer-go] Language

[Chris Fant]

Yes, I have plenty of experience with C# and have a full UCT engine
built in it that works for arbitrary board topographies (standard,
cylindrical, toroidal, others could be easily added).  And I agree,
writing/testing/debugging is very easy.  I've never used Mono.
Perhaps I should also consider that route.  I don't care about whether
the language is open or not as I am probably the only person who is
ever going to see this code.


On 11/12/07, Phil Garcia <[EMAIL PROTECTED]> wrote:
>
> > - Original Message 
> > From: Chris Fant <[EMAIL PROTECTED]>
> >
> > I'm not a troll, I promise.  I'm asking because I want to start a new
> > project.  I already have a bunch of code in C++, but I've never
> > considered myself an expert.  I think I'll cherry-pick from that and
> > convert to use smart pointers.  Thanks for the help.
>
> Consider C# since you are already familiar with C++. Yes, it's not as fast
> as native C, but it's easier to develop in C# because of it's automatically
> memory management, gargage collection, generics, class libraries, etc. I'm
> pretty good at C/C++ but writing/testing/debuging in C# is several times
> faster. The trade-off between code speed and development time may be worth
> wild for you.  It also meets all your requirements, including MPI and Linux
> (using the Mono).
>
>
> BTW. The type of optimization that Peter mentioned for Java is automatically
> in C#.
>
> Phil
> ___
> 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

[Chris Fant]

Topologies, not topographies.


On 11/12/07, Chris Fant <[EMAIL PROTECTED]> wrote:
> Yes, I have plenty of experience with C# and have a full UCT engine
> built in it that works for arbitrary board topographies (standard,
> cylindrical, toroidal, others could be easily added).  And I agree,
> writing/testing/debugging is very easy.  I've never used Mono.
> Perhaps I should also consider that route.  I don't care about whether
> the language is open or not as I am probably the only person who is
> ever going to see this code.
>
>
> On 11/12/07, Phil Garcia <[EMAIL PROTECTED]> wrote:
> >
> > > - Original Message 
> > > From: Chris Fant <[EMAIL PROTECTED]>
> > >
> > > I'm not a troll, I promise.  I'm asking because I want to start a new
> > > project.  I already have a bunch of code in C++, but I've never
> > > considered myself an expert.  I think I'll cherry-pick from that and
> > > convert to use smart pointers.  Thanks for the help.
> >
> > Consider C# since you are already familiar with C++. Yes, it's not as fast
> > as native C, but it's easier to develop in C# because of it's automatically
> > memory management, gargage collection, generics, class libraries, etc. I'm
> > pretty good at C/C++ but writing/testing/debuging in C# is several times
> > faster. The trade-off between code speed and development time may be worth
> > wild for you.  It also meets all your requirements, including MPI and Linux
> > (using the Mono).
> >
> >
> > BTW. The type of optimization that Peter mentioned for Java is automatically
> > in C#.
> >
> > Phil
> > ___
> > 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

[Phil Garcia]

- Original Message 
From: Chris Fant <[EMAIL PROTECTED]>
>  [...] I don't care about whether the language is open or not as I am 
> probably the only person who is ever going to see this code.

That's unfortunate for us! I'd love to see a UCT implementation in C#. 

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

Re: [computer-go] Language

[Don Dailey]

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/

Re: [computer-go] Language

[Don Dailey]

Nick Apperson wrote:
> Are you a troll?

Hi Nick,

We should definitely be able to talk about programming languages for our
domain of Go.   I see no problem here.


- Don



> 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/
___
computer-go mailing list
computer-go@computer-go.org
http://www.computer-go.org/mailman/listinfo/computer-go/

Re: [computer-go] Language

[Christoph Birk]

On Mon, 12 Nov 2007, 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)


Forget 'garbage collection' and use 'C'.

Christoph

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

Re: [computer-go] Language

[Chris Fant]

I think he was joking since he went ahead and responded to the question.

On 11/12/07, Don Dailey <[EMAIL PROTECTED]> wrote:
>
>
> Nick Apperson wrote:
> > Are you a troll?
>
> Hi Nick,
>
> We should definitely be able to talk about programming languages for our
> domain of Go.   I see no problem here.
>
>
> - Don
>
>
>
> > 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/
> ___
> 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] Congratulations to LeelaBot and to greenpeep!

[Jason House]

The following text is incorrect:

"In the round 8 game between FirstGoBot and break13, this position
appeared, White has just played the marked stone. Now Black played
(stupidly) at a, White captured two stones at b, and Black (break13)
tried to recapture the one marked stone."

There is only one marked stone, and it's not in the corner discussed.


On Mon, 2007-11-12 at 15:30 +, Nick Wedd wrote:
> The results of yesterday's KGS bot tournament are now available at
> http://www.weddslist.com/kgs/past/32/index.html.
> 
> Your comments and corrections will be appreciated as usual.
> 
> Nick

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

Re: [computer-go] Language

[Jason House]

On Mon, 2007-11-12 at 15:53 -0600, Nick Apperson wrote:
> 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.

D is definitely slower in execution than C/C++, but I do find it faster
for development.  Built in unit testing, invariants, and in/out
contracts make it easy to stress test your code.

My use of D has not all been positive.  It's rarely the fault of the
compiler itself, but stems from the immaturity of the libraries and
supporting tools.

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

Re: [computer-go] Language

[steve uurtamo]

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.

---

let's see...

C

garbage collection: free().

very fast.

s.



  

Be a better sports nut!  Let your teams follow you 
with Yahoo Mobile. Try it now.  
http://mobile.yahoo.com/sports;_ylt=At9_qDKvtAbMuh1G1SQtBI7ntAcJ
___
computer-go mailing list
computer-go@computer-go.org
http://www.computer-go.org/mailman/listinfo/computer-go/

Re: [computer-go] Language

[Hellwig Geisse]

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/

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] Python bindings for libego?

[Darren Cook]

On Oct 2nd 2007 Heikki wrote:
>> I was thinking that it could be quicker to do prototyping in something like
>> python, while having fast low-level functions in C. Since we already have
>> Lukasz Lew's ego library, I wonder if anyone has written a wrapper around it
>> to call it from python (or ruby, perl, or some other scripting language).

And I wondered:
> I think if you used swig then we could use your work for any scripting
> language, not just python:
>   http://www.swig.org/exec.html
> (Supported languages are listed on http://www.swig.org/compat.html )
> 
> I've not used swig, so cannot be much help there, but I would be able to
> test it with PHP.

Rather than join in the current language war thread I thought I'd bump
this one. Heikki I wondered if you looked into this any further?

Darren

P.S. I'm especially interested if you found some problems with swig -
I'm reading up on making php extensions at the moment and wondering if
swig is easier or harder than going the php-only route.
___
computer-go mailing list
computer-go@computer-go.org
http://www.computer-go.org/mailman/listinfo/computer-go/

Re: [computer-go] Language

[Sartak]

On 11/12/07, 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)

Practically all high level languages support these features. Perl,
Python, Scheme, Lua, Haskell, Forth...

Look around and see what tickles you most.

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

Re: [computer-go] Language

[Heikki Levanto]

On Mon, Nov 12, 2007 at 10:20:23PM -0500, Jason House wrote:
> My use of D has not all been positive.  It's rarely the fault of the
> compiler itself, but stems from the immaturity of the libraries and
> supporting tools.

I think that highlights an often-ignored problem in language discussions.
There are only relatively small differences between most modern languages,
btu their libraries tend be vary more. Also, learning the language basics
should not take long for any experienced programmer, but to learn the
"proper" way to use the libraries, that can take much longer.

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

Re: [computer-go] Python bindings for libego?

[Heikki Levanto]

On Tue, Nov 13, 2007 at 03:11:40PM +0900, Darren Cook wrote:
>
> On Oct 2nd 2007 Heikki wrote:
> >> I was thinking that it could be quicker to do prototyping in something like
> >> python, while having fast low-level functions in C. Since we already have
> >> Lukasz Lew's ego library, I wonder if anyone has written a wrapper around 
> >> it
> >> to call it from python (or ruby, perl, or some other scripting language).
> 
> And I wondered:
> > I think if you used swig then we could use your work for any scripting
> > language, not just python:
> >   http://www.swig.org/exec.html
> 
> Rather than join in the current language war thread I thought I'd bump
> this one. Heikki I wondered if you looked into this any further?

I gave it up pretty quickly. I came to the conclusion that I have so little
time for mesing around, that the idea of learning a new language (say
python), and how to build swig interfaces to it, and getting all that to
work, it would probably take me so long that I wouldn't get around to doing
any go experiments for a long time. 

I have a feeling that although swig is probably a good toolkit, most people
avoid using it if they only need to interface to one or two languages. But no
hard facts to prove this...

> P.S. I'm especially interested if you found some problems with swig -
> I'm reading up on making php extensions at the moment and wondering if
> swig is easier or harder than going the php-only route.

I have seen some php extensions (our company makes one, but I am not directly
involved). I seem to recall that making an extension to php was not all too
hard.

But as one who has to program some php for living, I wonder why would you
like to use a language like that? I am *so* tired of the way it happily
declares a new variable when you mistype one, or finds mistyped function
names only at run time, if you happen to call that function... As a
C-programmer, I want my compiler to catch silly mistakes for me, when ever
possible.

Regards

   Heikki

-- 
Heikki Levanto   "In Murphy We Turst" heikki (at) lsd (dot) dk

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