Re: [computer-go] A plan for building a 7x7 GO solver.

[Dave Dyer]

If the search was depth first, and you seeded the search with some
well played games, then alpha beta pruning ought to result in some
truely enormous reductions in the search space.

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

[computer-go] Re: When is Pass the best move?

[Dave Dyer]

The absolute truth (when pass is the best move) is not relevant
to the current state of the art.   The only case that matters,
where a pass is the best move globally, is when the game is over.

A program should only pass when some heuristics suggest the
end is near (board nearly full, etc) and when all the non-pass
moves it considered have negative evaluations.

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

[computer-go] Re: How to improve my minimax speed?

[Dave Dyer]

Just as a caveat, keep in mind that alpha-beta is only guaranteed
to not affect the result if the rest of your search is completely
deterministic.  While that's a good first order approximation to
the truth, it's rarely actually true in anything as complex as
a Go program.  

For example, if one possible consequence of evaluating a node is developing
a "fact" that a certain group is safe, and alpha beta prunes out the node,
then the fact is also pruned and any deductions you might make based on it
will change.  Another obvious possibility is that since your whole search
is running so much faster, time control will permit a lot more study.

The important point is that alpha-beta doesn't deliberately change
the local result.

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

[computer-go] Re: language choices

[Dave Dyer]

Guys, keep your eyes on the prize.  If your only problem
is that you need to double your speed, all you have to do
is wait 1.5 years.

All this talk of optimizing speed by tweaking language xx to be
more like assembly language (or C) is almost completely a waste 
of time.

Likewise, algoritmic optimizations that are not order of magnitude
improvements (factors of 10 or 100) are not worth persuing.

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

Re: [computer-go] 19x19 CGOS?

[Dave Dyer]

There's still plenty of juice left at boardspace, so 
feel free to host more experiments at cgos.boardspace.net

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

[computer-go] Re: komi argument = silly

[Dave Dyer]

To a first order approximation, would changing the komi change the
rankings?  Presumably, programs are playing the same number of games
as black and white, so any "unfair" advantage or disadvantage black 
has would balance out.

Komi only matters when there is only one game between a pair of opponents.

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

[computer-go] off topic: Tobacco

[Dave Dyer]

>
>By the way,  has anyone seen the Philip Morris commercials?   

I believe they were forced into this as part of the extortion
by the state attorneys general.  It's Penance for illegally
targeting young non-smokers with Joe Camel, and promoting their
products while denying that they were dangerous to your health.

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

[computer-go] Re: My experience with Linux

[Dave Dyer]

The thing that really kills multiple platform programs are GUIs.   
Unless your GUI is "born" expecting to be cross platform, you're 
pretty much screwed.

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

[computer-go] Re: linux and windows

[Dave Dyer]

At 09:29 AM 7/17/2008, David Fotland wrote:
>It irks me a little that Linux people refuse to consider porting their
>programs to Windows :)  With cygwin, it's pretty easy to port Linux
>programs.  

Isn't it the case that Cygwin is no help if the program has a GUI. 
  

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

[computer-go] Re: linux and windows

[Dave Dyer]

At 09:29 AM 7/17/2008, David Fotland wrote:
>It irks me a little that Linux people refuse to consider porting their
>programs to Windows :)  With cygwin, it's pretty easy to port Linux
>programs.  

Isn't it the case that Cygwin is no help if the program has a GUI. 
  

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

[computer-go] Re: tournaments

[Dave Dyer]

One possibility is to use one of the VM products that are available
to host unix on a windows machine, or windows on a unix machine.

VirtualBox looks particilarly promising, since it's free and available
for all the common platforms.   There is some performance penalty
associated with the virtualization, but I would expect for a CPU bound
Go program this would be minimal.

If the performance penalty is significant enough, it could
be equalized by running ALL programs in VM boxes.

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

[computer-go] Re: tournaments

[Dave Dyer]

One possibility is to use one of the VM products that are available
to host unix on a windows machine, or windows on a unix machine.

VirtualBox looks particilarly promising, since it's free and available
for all the common platforms.   There is some performance penalty
associated with the virtualization, but I would expect for a CPU bound
Go program this would be minimal.

If the performance penalty is significant enough, it could
be equalized by running ALL programs in VM boxes.

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

[computer-go] Re: linux and windows

[Dave Dyer]

>
>Of course C can be more or less platform independent if you take some care.

Purely for engine code, that's true.  Standard windows has APIs
that are nearly compatible with xxux for command line initialization
and ordinary file and network operations.  

If your program has ANY gui at all though, you're pretty much screwed.
Mac Windows and Linux GUIs are about as far apart as any three platforms
can be.  There are lots of "compatibility" solutions, including your
choice of platform independent languages; but they all create essentially
a fourth platform that you have to target, and once again, you're screwed
unless you started that way.


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

[computer-go] re: What Do You Need Most?

[Dave Dyer]

Boardspace is a VPS, so CGOS is currently running as a subaccount of a 
VPS.  Boardspace is going to be upgraded sometime in the next few
months, which will allow me to add another 1GB to CGOS allocation.

Or, if computer Go gets a rich sugar daddy, spending $400/yr
for your own VPS would be an excellent first investment.

--

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

[computer-go] Re: Java SGF Parser

[Dave Dyer]

>
>1) Does anybody know of a good Java SGF parser out there?

I have one I've used for many types of games, including Go.  I've used
it to represent large collections with no problems.


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

[computer-go] Re: Java SGF Parser

[Dave Dyer]

>
>1) Does anybody know of a good Java SGF parser out there?

I have one I've used for many types of games, including Go.  I've used
it to represent large collections with no problems.


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

[computer-go] Re: mogo beats pro!

[Dave Dyer]

I watched all the games, and I must say, mogo performed really badly
at the blitz games, and quite a bit better at the 1-hour game. I'd still
take any claims of dan level play with lots of salt.

My take-away from watching the match is that blitz performance wasn't
at all representative.   A human playing blitz games might do 90% as
well as at a full length game, whereas mogo's performance looked like
it scaled more linearly.

I also wonder how much playing with a 9 or more stone handicap affected
it's apparent strength.  It's an awful lot easier to appear competent
when you start with 9 stones.  It looked to me like mogo got totally
demolished  any place the pro concentrated his attack, except in the
lower-right where the pro was caught being careless.

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

[computer-go] Re: Program don't start playing on CGOS

[Dave Dyer]

>
>I'm really very weak on networking so I'm not sure what I'm actually
>reading or whether this fix needs to be applied on the server end or the
>client end.   Any ideas is this is relevant?

You also have the same problem, but with much less real information,
if the client end end of the connection is bridged by a router, with 
is pretty common.  I'm absolutely certain that ordinary consumer routers 
are not very reliable.   They have very limited memory, and arbitrary
and undocumented policies for maintaining their connection tables.

Sometimes power cycling them helps.

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

[computer-go] Re: Program don't start playing on CGOS

[Dave Dyer]

>
>I'm really very weak on networking so I'm not sure what I'm actually
>reading or whether this fix needs to be applied on the server end or the
>client end.   Any ideas is this is relevant?

You also have the same problem, but with much less real information,
if the client end end of the connection is bridged by a router, with 
is pretty common.  I'm absolutely certain that ordinary consumer routers 
are not very reliable.   They have very limited memory, and arbitrary
and undocumented policies for maintaining their connection tables.

Sometimes power cycling them helps.

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

[computer-go] Re: What's happening at the European Go Congress?

[Dave Dyer]

I think the result 

 "computer in hopelessly lost position resigns."

is much more satisfactory than

 "computer in hopelessly lost position wins by playing 100
 additional pointless moves"

I think a human who used this tactic in a tournament situation
might win the trophy, but would be unable to show his face again.

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

[computer-go] Re: What's happening at the European Go Congress?

[Dave Dyer]

I think the result 

 "computer in hopelessly lost position resigns."

is much more satisfactory than

 "computer in hopelessly lost position wins by playing 100
 additional pointless moves"

I think a human who used this tactic in a tournament situation
might win the trophy, but would be unable to show his face again.

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

[computer-go] Re: Some thoughts on the event in Leksand

[Dave Dyer]

>This was typically to pick up my queen, change its colour, and
>> capture my rook with it.
>
>Now there's a feature that would make a tournament interesting...

If this appeals to you, try Martian Chess or Shogi

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

[computer-go] Re: Disputes under Japanese rules

[Dave Dyer]

>Japanese: bad.

I don't think this is the case at all.  The Japanese rules
are just a human optimization, to avoid having to make the 
last 100 meaningless moves, and still arrive at the correct 
score with a minimum of extraneous manipulation.  

The tortured details, while not elegant, rarely matter.

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

[computer-go] Re: Disputes under Japanese rules

[Dave Dyer]

The formalized rules are the "tortured details" I referred to.  I've
played thousands of games of Go, and I've never even seen any of those
versions of the rules.

The Japanese rules I refer to are the informal procedures I use every
time I play, both to estimate the score during the game, and at the end.

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

[computer-go] Re: reference bots testing.

[Dave Dyer]

I suggest you add an identical RNG for testing purposes, which you
will know is identical in both implementations even if it is not
ideal.   Run a test with a seeded random sequence which should
provide identical playouts.

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

[computer-go] Re: Git, any other ideas?

[Dave Dyer]

For those of you who use windows, I highly recommend tortoise cvs
and tortoise svn, which map access to whichever repository you prefer
into an incredibly useful and intuitive interface piggybacked on windows
explorer.

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

[computer-go] Re: Git, any other ideas?

[Dave Dyer]

For those of you who use windows, I highly recommend tortoise cvs
and tortoise svn, which map access to whichever repository you prefer
into an incredibly useful and intuitive interface piggybacked on windows
explorer.

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

[computer-go] Re: OT: Harder than go?

[Dave Dyer]

I think the question is largely meaningless, because few games have
been studied by humans (or human computer programmers) with the depth
and intensity that has been achieved for games like chess and go.

In general, games with many choices and no obvious strategies
are good for people and bad for computers.  Two examples that
fit this paradigm, and have been proposed as examples of "hard
for computers" are Arimaa and Havannah

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

[computer-go] Re: Another enhancement to AMAF

[Dave Dyer]

Here's a chance to share an amusing and illustrative anecdote.

I was working on optimizing "Goodbot",  a program that plays Tantrix,
and because of the nature of the game, the only way to really qualify
an improvement is to run many test games against a standard opponent.

At one point, I was making nightly "test runs" of a few hundred games,
with slightly tweaked parameters and underlying tweaks to the algorithms,
always seeking to improve over the reference standard.   At one point,
I discovered that due to some temporary code accidentally left in
place, I had actually been running exactly the same code for about
a month, and all perceived movement in "better" or "worse" directions
was only due to random fluctuations.

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

[computer-go] Re: Another enhancement to AMAF

[Dave Dyer]

Here's a chance to share an amusing and illustrative anecdote.

I was working on optimizing "Goodbot",  a program that plays Tantrix,
and because of the nature of the game, the only way to really qualify
an improvement is to run many test games against a standard opponent.

At one point, I was making nightly "test runs" of a few hundred games,
with slightly tweaked parameters and underlying tweaks to the algorithms,
always seeking to improve over the reference standard.   At one point,
I discovered that due to some temporary code accidentally left in
place, I had actually been running exactly the same code for about
a month, and all perceived movement in "better" or "worse" directions
was only due to random fluctuations.

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

[computer-go] Re: flash crowd from TV

[Dave Dyer]

>
>That's impressive, especially considering the fairly long search path between 
>"Go" and "igowin".

It happens.  One day recently I was idling at boardspace.net, when
in the course a few minutes the site was overrun by about 30 guests,
all speaking German and wanting to play Hex.   It turned out that 
"A Beautiful Mind" was showing on German TV.
  

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

[computer-go] Re: hex robot

[Dave Dyer]

At 01:31 PM 11/26/2008, Denis fidaali wrote:
>Speaking of hex ... I really think it would be a nice intermediary game before 
>tackling the complexity of go. Do you know of any good community (and protocol 
>equivalent to GTP) where i could start to look for submitting a bot ?

There are a couple of pretty decent programs and some nice underlying
theory.  Also a perfect play bot for a small board.  I would start
at the Hex wiki page to research them.

A credible Hex bot is on my wish list for Boardspace.   The one I wrote
is laughably weak, but it will be a significant effort to write a better
one.  If you're willing to work in Java and within the constraints of
a realtime web site, lets talk.  

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

[computer-go] Re: hex robot

[Dave Dyer]

At 01:52 AM 11/27/2008, Denis fidaali wrote:

...
> But what really lacks (or i wasn't able to find anyway) is a strong community 
> like there is for go.
>
> A CGOS equivalent.
> A GTP equivalent.
> A Gogui equivalent.
> A Kgs equivalent.


I don't think there's a match between your goals and what boardspace 
wants, but you ought to discuss cloning and adapting CGOS/GTP for
Hex with Don.



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

[computer-go] RE: hex robot

[Dave Dyer]

Permit me to play the skeptic here; I think you're going about it absolutely 
backwards - unless you already have a strong algorithm which depends on 128 bit 
rotations, and only lack an efficient hardware engine to run it on.

If your idea of fun is to really feel the bits squishing between your toes, by 
all means do, but I don't think it's likely you will simultaneously make 
advances in Hex theory or practice.


At 12:19 AM 11/27/2008, Denis fidaali wrote:


> My current plan is to tackle directly the power of x86-64bits architecture. 
> Because it's now quite well represented. And there is this "larrabee" project 
> that may get out in one or two years (48 x86-64bits processors). So my true 
> goal is to try and see what i can do with my quad Q9300 2.5Ghz running a 64 
> bits linux. Obviously one need a bit of work before being able to hope to 
> achieve something with assembly.

etc...

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

[computer-go] Re: Hardware limits

[Dave Dyer]

I think general hardware limits are good, because they will permit
more teams to be competitive without altering the nature of the
competition.

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

[computer-go] Re: Hardware limits

[Dave Dyer]

Lets look at it another way - no one would care what hardware
you choose to use, unless you win.   So at the very least, you
ought to be able to use arbitrary hardware until it becomes 
established that only that class of hardware can win.

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

[computer-go] Re: Is computer Havannah welcome here?

[Dave Dyer]

There's already a "havannah" section on this game programming
forum:  http://www.grappa.univ-lille3.fr/
-- which could use an influx of traffic.

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

[computer-go] Re: remote time measurement

[Dave Dyer]

My theory is that the organizers of tournaments with remote participants
could appoint official observers, to observe the operators at the remote
end of connections.  Not foolproof, but simple and doesn't interfere with
the conduct of the tournament.

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

[computer-go] Re: remote time measurement

[Dave Dyer]

At 12:59 AM 2/4/2009, David Fotland wrote:
>What do you mean by operator at remote end?  In my case, the program was
>running on a cluster at Microsoft in some computer data center.  There was
>no operator at Microsoft.  The cluster was operated from Beijing through a
>remote desktop.  The operator was at the contest site.

In that case, the operator is watching you.  The goal is to
certify that the human putatively responsible for the program
is behaving consistent with the competition, not unplugging
cables or feeding in moves from a hidden 9 dan.  It wouldn't
prevent a deliberate attempt to defraud, but it would add a
significant amount of complexity.

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

[computer-go] Re: static evaluators for tree search

[Dave Dyer]

While your goal is laudable, I'm afraid there is no such thing
as a "simple" tree search with a plug-in evaluator for Go.  The
problem is that the move generator has to be very disciplined,
and the evaluator typically requires elaborate and expensive to
maintain data structures.  It all tends to be very convoluted and
full of feedback loops, in addition to the actual alpha-beta which
is trivial by comparison.

If you look at GnuGo or some other available program, I'm pretty sure
you'll find a line of code where "the evaluator" is called, and you could
replace it, but you'll find it's connected to a pile of spaghetti.

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

[computer-go] Re: static evaluators for tree search

[Dave Dyer]

>Do you mean that the evaluator might be used during move ordering somehow
>and that generating the nodes to expand is tightly coupled with the static 
>evaluator?

That's the general idea.  

No search program can afford to use a fan-out factor of 361.  The information
about what to cut has to come from somewhere.

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

[computer-go] Re: static evaluators for tree search

[Dave Dyer]

>Do you mean that the evaluator might be used during move ordering somehow
>and that generating the nodes to expand is tightly coupled with the static 
>evaluator?

That's the general idea.  

No search program can afford to use a fan-out factor of 361.  The information
about what to cut has to come from somewhere.

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

[computer-go] Re: static evaluators for tree search

[Dave Dyer]

This is old and incomplete, but still is a starting point you might
find useful  http://www.andromeda.com/people/ddyer/go/global-eval.html

General observations (from a weak player's point of view):  

Go is played on a knife edge between life and death.  The only evaluator
that matters is "is this stone alive", and there are no known proxies 
that will not fall short a significant amount of the time.  If you fall
short once or twice in a game against a competent player, you will lose.

General strategic considerations will play you false every time.

-- Notwithstanding the above, improving general considerations
will improve play, but not much.  It's all about the minutia of
the situation.

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

[computer-go] cgos: Donn Daily?

[Dave Dyer]

Donn, your email at d...@mit.edu is bouncing. 

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

[computer-go] Berlekamp lecture on mathematical Go

[Dave Dyer]

Highly recommended

Mathematics
 and Go by Elwyn Berlekamp 
___
computer-go mailing list
computer-go@computer-go.org
http://www.computer-go.org/mailman/listinfo/computer-go/

[computer-go] Re: Implications of a CPU vs Memory trend on MCTS

[Dave Dyer]

Storing an opening book for the first 10 moves requires 
331477745148242200 nodes.  Even with some reduction for symmetry,
I don't see that much memory becoming available anytime soon, and you still
have to evaluate them somehow.

Actually storing a tree, except for extremely limited special cases, is not
even conceptually possible, and doesn't save much time.  Consider that if
you store the tree you saw at the previous move, by the time you get to
use the stored tree 99% of it is useless because your opponent chose his move.

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

[computer-go] Re: Implications of a CPU vs Memory trend on MCTS

[Dave Dyer]

At 02:13 PM 5/12/2009, Michael Williams wrote:
>Where does your 99% figure come from?

1/361 < 1%

by endgame there are still easily 100 empty spaces
on the board.


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

[computer-go] Re: Implications of a CPU vs Memory trend on MCTS

[Dave Dyer]

At 02:13 PM 5/12/2009, Michael Williams wrote:
>Where does your 99% figure come from?

1/361 < 1%

by endgame there are still easily 100 empty spaces
on the board.


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

[computer-go] Re: Implications of a CPU vs Memory trend on MCTS

[Dave Dyer]

An essential feature of monte carlo is that it's search space is
random and extremely sparse, so consequently opportunity to re-use
nodes is also extremely sparse.

On the other hand, if the search close to the root is not sparse, my
previous arguments about the number of nodes and the number of them
that will continue to be useful still apply.

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

Re: [personal] Re: [computer-go] Re: Implications of a CPU vs Memory trend on MCTS

[Dave Dyer]

>
>I assume Dave Dyer does not understand alpha beta pruning either, or he would 
>not assume the branching factor is 361.

The branch at the root is about (361-move number) - you have to consider
all top level moves. A/B only kicks in by lowering the average branching
factor at lower levels.

If you're trying to save and reuse trees to reduce work, alpha beta makes
most of the saved nodes useless for anything outside the principle variation.
This is precisely because the nodes were mostly not fully explored, and all
you know (from the previous evaluation) is that this node is better or worse
than some other, now-irrelevant branch.

I did a lot of work trying to reuse trees for iterative deepening
of alpha-beta searches. It required a lot of bookkeeping and a lot
of memory, and it didn't turn out to be a good strategy even for
small searches where the memory was essentially cost free.

I suppose it's possible there's something fundamentally different here,
but you ought to think carefully before investing in terrabyte memories.

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

[computer-go] Re: Implications of a CPU vs Memory trend on MCTS

[Dave Dyer]

>
>If I use persistent storage and do that search again in another game,   I can 
>start exactly where I left off and generate 50,000 more nodes.   It will be 
>the same as if I did 100,000 nodes instead of 50,000 nodes.Or put another 
>way,  it will be the same as if I spent 20 seconds on this move instead of 10 
>seconds.  

Sure, but except for openings you'll never reach the same
position position in another game unless the players are 
deliberately copying their play.

Consider move 20 (for example).  If you saved every "move 20" node you
ever encountered, how often do you think you'd encounter a duplicate
from a different game, such that you can either avoid an evaluation,
or improve your knowledge of that position by studying it 
a bit more.   I contend it is a vanishingly small percentage.

-- 

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

[computer-go] Re: Implications of a CPU vs Memory trend on MCTS

[Dave Dyer]

>>
>>But then MCTS is invalid.   The point is that you do spend time learning that 
>>these nodes are not relevant, so you might as well try to remember that. 

It is invalid. It's just a heuristic that is working within the current domain.

>>If you are playing a game of chess and fall for a trap,  do you consider it 
>>silly to try to remember this for the next game?

The point is that if your opponent wanders into a space you did not consider,
you still have to know how to respond.  What clever humans recognize as the
"same" trap is actually just one of zillions of similar positions that will
be flooding your database of "known" positions.

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

[computer-go] Re: verifiable claims

[Dave Dyer]

Some lines of play involving large captures will effectively never
terminate, even with superko rules in effect.

I doubt it is possible to eliminate all these non-terminating
lines of play in any way that is provably correct.

.. So while claims of solution by exhaustive search might be very
convincing, I doubt they can ever be proved.

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

[computer-go] Re: verifiable claims

[Dave Dyer]

>
>You can just prove that you can make a large-enough chain that is
>unconditionally alive. I believe that's what Erik did. In practice,
>you cannot do an exhaustive search using superko rules because then
>hash table scores cannot be used.

I don't think you can always do that.  For example, if white
is capturing a chain of size 30, how can you prove that black
can never profit by continuing inside that 30 space void. In
fact, in many cases you can demonstrate that he should.

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

[computer-go] Re: verifiable claims

[Dave Dyer]

At 06:31 PM 5/22/2009, David Doshay wrote:
>there are no chains of size 30 on a 5x5 board, 

I'll concede for a 5x5 board, but I think my point
is valid for "sufficiently large" boards, probably 7x7.

Almost any strategy other than playing out all legal moves
involves a lot of hand waving that is unlikely to be
accepted as a proof.  There are just too many cases where
a pitch inside a captured space has global effects.

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

[computer-go] Re: verifiable claims

[Dave Dyer]

I've written dozens of games with alpha-beta searches, so I think
it's fair to say that I have a basic understanding of the process.

Your description is correct but incomplete.  Alpha beta is good at eliminating
lines of play once a strong outcome is known somewhere in the tree, but much
weaker before that.  If a "big capture" occurs at ply 30, but the shortest
win is at ply 60, you still have to explore an enormous number of silly
variations as you iteratively deepen between ply 30 and 59.  The fact that you
don't need to explore continuations of the silly moves past move 59 is 
cold comfort.  The other half of the bad news is that while only the
"best" move of the winning lines needs to be explored, generally all
of the possible responses have to be explored.  So the tree actually
explored tends to be narrow for the winning line, but very wide as
all possible responses to the "correct" move are explored.  In the case
of a "big capture" being the correct move, pitching into every one of
the captured spaces will have to be explored.

Alpha beta engines which do not use inadmissible (but probably valid)
tricks waste exponentially more time than those that do.  It's quite
possible that 5x5 is on the sweet side of the equation with today's
available CPUs, but at some point not much further away, you have
to accept results that you believe but can't prove, as better than
no result at all.

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

[computer-go] Re:verifiable claims

[Dave Dyer]

>
>And somehow I don't ever see comments anywhere suggesting that this could be a 
>problem. So what I'd like to know is: is this so  trivial that no one ever 
>mentions it, or are the heuristics that programs use to terminate playouts so 
>obscure that they are too embarrasing to mention?

Completely solving a game by search is a special case, because you're
only interested in terminals where the game is over.  

In the more common case, you're only searching to choose the next move,
with no guarantee that it is best.  Such playouts are typically depth
limited, but strategies for deciding exactly where to stop can be quite
complex.


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

[computer-go] Re:verifiable claims

[Dave Dyer]

>
>And somehow I don't ever see comments anywhere suggesting that this could be a 
>problem. So what I'd like to know is: is this so  trivial that no one ever 
>mentions it, or are the heuristics that programs use to terminate playouts so 
>obscure that they are too embarrasing to mention?

Completely solving a game by search is a special case, because you're
only interested in terminals where the game is over.  

In the more common case, you're only searching to choose the next move,
with no guarantee that it is best.  Such playouts are typically depth
limited, but strategies for deciding exactly where to stop can be quite
complex.


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

[computer-go] Re: Problems with CGOS

[Dave Dyer]

>
>So I believe this is a design flaw in CGOS itself.   I wrote CGOS without 
>having had any experience writing servers.   

If there's a problem with larger databases, perhaps it can be
fixed by adding the right indexes to the sql database.  If
you add a little time monitoring code around your queries
to determine which are slowest, you may be able to devise a 
1 line fix, by added an index to the schema.



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

[computer-go] Re: Cgos redesign

[Dave Dyer]

My $0.02

The choice of language is mostly arbitrary.  

CGOS is really two separate programs:
(1) an I/O multiplexer that manages the clients connections and detailed 
communication, 
(2) a scheduler/planner/recorder that manages the overall operation of the 
site.  

I would definitely separate those two, so the scheduler can
be developed and tweaked independently of the client manager.

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

[computer-go] Re: MCTS, 19x19, hitting a wall?

[Dave Dyer]

I think one approach to scaling playouts is to subdivide the board,
stipulate the outcome in a fixed part, and do "norman" playout in
the interesting part.  The trick is to do a reasonable subdivision
in the first place.  Imagine an advanced UCT model that conceptually
behaves like human evaluation, where you try to divine the outcome
of some local fight (ignoring everything else) as a first pass.

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

[computer-go] Re: Dynamic komi in commercial programs

[Dave Dyer]

If you are in a lost position, "good play" is play that maximizes
the probability of a turnaround, which is quite different depending
on how far behind you are, and for what reason.

If the status of all the major groups is solid, then concentrating
on tactics which can gain a few points reliably might be the right
thing. 

On the other hand, if the status of some groups is less than
immutable, then focusing on changing their status favorably might
be correct. It's hard to see how shifting Komi will influence
the style of play in this direction.

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

[computer-go] Re: self atari

[Dave Dyer]

It's easy to construct self-atari of unlimited size that both
can occur and should be played, if the capturing move that follows
the self-atari is then recaptured in a snapback.

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

[computer-go] Re: Rating variability on CGOS

[Dave Dyer]

In any rating scheme, who you play can be as important as how well.
This is especially true for small groups.   

Suddenly adding or dropping a strong player will certainly cause 
all the other player's ratings to shift.

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

[computer-go] OT: AI article I found interesting

[Dave Dyer]

At 10:12 AM 10/24/2009, Joshua Shriver wrote:
>Came across this today, and since this is also an AI oriented list thought 
>some of you might enjoy it too.
>
>http://www.techradar.com/news/world-of-tech/future-tech/the-past-present-and-future-of-ai-643838

I won't believe it even if I see it.  Google "Mechanical Turk"
___
computer-go mailing list
computer-go@computer-go.org
http://www.computer-go.org/mailman/listinfo/computer-go/

[computer-go] RE: other challenges

[Dave Dyer]

There's already a pretty satisfactory blokus server and a pretty active
community of players, at blokus.com.

If computer go people are looking for easier worlds to conquer (call
it educational training for the real challenge) there is no shortage
of candidate games.  One that has an active community of developers
is arimaa, www.arimaa.com

Also, I would personally like to have a better robot player for Hex
at boardspace.net.  If anyone want to divert themselves with Hex, I'd
welcome a serious collaborator.

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

[computer-go] Re: MC thought

[Dave Dyer]

I wonder if MC programs shouldn't prune game branches when
sufficiently large captures occur.  The loss/win might not
be strictly allocated to the right player, but it certainly
means that the current game has entered sillyspace.

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

[computer-go] Re: MC thought

[Dave Dyer]

At 11:10 AM 1/15/2007, Magnus Persson wrote:
>Quoting Dave Dyer <[EMAIL PROTECTED]>:
>
>>I wonder if MC programs shouldn't prune game branches when
>>sufficiently large captures occur.  The loss/win might not
>>be strictly allocated to the right player, but it certainly
>>means that the current game has entered sillyspace.
>
>Are you talking about pruning a full board search tree or deep down a
>simulation?

Lets say that in your MC game a 20 point group is captured (on a 81 point
board).  There isn't any additional real information to be gleaned from
this branch, so you might as well assign it to the capturing player.

Suppose you have a realistic endgame position with two large
groups that are actually alive with correct play.  In a MC game,
a lot of games that start with incorrect play will pretty rapidly
capture one of the big groups, and then spend hundreds of moves
filling in the empty space.  Is anything really learned from that
exercise?

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

[computer-go] Re: Scaling monte carlo up to 19x19

[Dave Dyer]

Here's an idea for scaling up, which should result in "only" factor
of 10 slower speed.   To scale from 9x9 to 19x19, subdivide the
board into four, overlapping 10x10 boards.   Run a standard 9x9
monte carlo up to the 90% full stage on each of the four boards,
then run a full board monte on the whole board remaining.   

Treat the ovelapping stripes as edges in a slightly more sophisticated
way than usual, becuase you might be connecting to liberties by playing
in the stripe.

To avoid artifacts caused by the location of the overlaps: the number 
of zones, and the location of the stripes, is also subject to randomization.

It might be interesting to try this on a 9x9 board using a 5x5 zone 
to begin with.

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

[computer-go] Re: Scaling monte carlo up to 19x19

[Dave Dyer]

At 02:59 PM 1/30/2007, [EMAIL PROTECTED] wrote:
> I'm having difficulty picturing this, so I'll start with the most basic 
> questions. 
> 
>Do you mean Monte Carlo by itself or Monte Carlo combined with tree search 
>(e.g. UCT)?
> 

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.


>Do you mean partition the larger board for the course of each playout 
>(randomizing zones from one to the next) or in some other sense?

I imagine you'd want to randomizing the set of zones in the
course of the search.

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

[computer-go] Re: Scaling monte carlo up to 19x19

[Dave Dyer]

>
>Of course, everything depends on how you can deal with the boarders - how 
>about some monte-carlo-simulations over the possible boarder-configurations?

My thought is that one thing you could easily get from the rollouts
is a good estimate of the status of each string of stones currently
on the board, and the eventual owner of each empty space.

In the zone logic, stones adjacent to the border would count the border
as friendly or unfriendly based on the best estimate of that status.

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

[computer-go] Re: documentation for the IGS protocol ?

[Dave Dyer]

The NNGS clone on boardspace.net is still running, but completely
idle.  It would be a suitable place to test clients.

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

[computer-go] Re: LISP question (littlle bit off topic)

[Dave Dyer]

>
>I don't know, but from the description "list of atoms," perhaps
>numbers were represented as linked lists of bits (using the facilities
>built in to support linked lists of anything).


I don't believe that any non-toy version of lisp ever used anything
as ineffecient as representing numbers as lists of bits.  In early
lisp implementations, all data are presumed to be pointers to structures.  
The address space (usually 16 or 18 bits in those days) was partitioned 
so that some range of addresses was used to represent integers, so for 
example "pointers" with values 0-255 represented integers from -128 to 127.
Real pointers all had values greater thatn 255.   Integers ouside
of the "small" range were represented by real pointers to structures
whose type and organization was determinable by inspection.

To do arithmetic, you'd first check (and hope for) the reserved range
of addresses, then interpret the data structure to retrieve the
actual values of larger integers.  Perform your arithmetic, then
reverse the process (including allocating memory to represent results
out of the small range).

With no compiler at all, as was the case in the earliest systems,
this was obviously horribly ineffecient.  As compiler technology
improved, it gradually became true that usual cases like multiplying
two integers were only 10x or so less effecient than executing on
the raw hardware.  Really good compilers can now do better than that.

.. then of course there were lisp machines, which put all the type
checking in the hardware, so ordinary arithmetic ran at full hardware
speed.   Symbolics lisp machines had 44 bit word size, which represented
32 bit integers directly.


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

[computer-go] Re: Pondering

[Dave Dyer]

My theory on pondering is that it's not very productive to
use it to just jump start the next global search.

In my conceptual model for a playing program, there are a lot
of "facts" that in fact are nothing of the kind - they're assertions
that you are willing to assume are true.  I'm thinking of things
like "a can connect to b" and "c is alive".

In global evaluation, you use these facts to anchor the evaluation.

Pondering time is spent refining and re-evaluating these facts.

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

[computer-go] Re: 9x9 vs 19x19 (was: computer-go Digest)

[Dave Dyer]

I suggest that it would be more convenient for everyone
if various sizes of cgos all ran on the same server.  If
you want to donate horsepower to the project, a good use
of the resource would be to run "anchorman" type clients.

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

[computer-go] Re: 9x9 vs 19x19 (was: computer-go Digest)

[Dave Dyer]

I figured that a credible anchor player for 19x19 might
need a lot of cycles, and need to play a lot of games
at first, so spreading the load would be a good idea.

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

[computer-go] Re: Java hounds salivate over this:

[Dave Dyer]

> 
>So if there was any language which allows a programmer to port their code to 
>be compileable and executable on a wide variety of systems it is C.
> 

Java and C support two fundamentally different approaches to portability.  

The approach that C supports is "chaos: deal with it".  Figure out
exactly what platform you're dealing with, compile code accordingly.
You end up with godawful kludges like "configure".  It can work, but 
it requires constant maintenance to keep up with the latest twists 
in the "compatible" environments.

Java's aproach is to define a virtual machine, and implement it 
faithfully on each platform.  Java programs run the same everwhere;
they don't know what OS or CPU they're running on.

The same kind of approach is used to virtualize for whole platforms
- I can also run linux or windows on my intel mac.   I can run my old
PDP10 system in a window on my PC (and incidentally, MUCH faster 
than it ever ran on real hardware)

Both approaches suffer from not offering access to useful (but not
modeled) aspects of the targeted platform.

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

[computer-go] Re: deep platform emulation

[Dave Dyer]

At 02:48 PM 6/15/2007, terry mcintyre wrote:
>Now that takes me back to days of your. Can we run TECO on a PDP-10 emulator? 
>Early 
>versions of EMACS were actually written on top of TECO -- how's that for 
>layers upon layers 
>of emulation?

The emulator runs the PDP10 processor, and emulators for several
popular period I/O devices.   On top of that you run your choice
of Tops-10, Tops-20 or ITS.  Then you log into your similated 
timesharing system and run any damn thing you want.   

Yes, you can run teco, if you can remember how.

The emulator is packaged quite nicely with a disk image (yes,
the entire disk) of good 'ol diska.   For communication it
can read similated magtapes.  In fact, I used this to read
file images of backup tapes that had long gone to their graves,
and get back all my code from bygone eras.  Totally cool.
http://simh.trailing-edge.com/


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

[computer-go] Re: Java hounds salivate over this:

[Dave Dyer]

At 03:12 PM 6/15/2007, steve uurtamo wrote:
>my last $0.02 on this -- let me know when you've written a kernel in java, and 
>tell me how fast your operating system (written entirely in java) runs. 

I could point out that lisp machines had no other language at the
core.  The entire operating system (which had windows, networks,
and virutal memory) was written in lisp.  Even the garbage collector
was written in lisp.


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

[computer-go] Java hounds salivate over this:

[Dave Dyer]

>i did this for an IDEA (encryption) routine once, and
>was heartbroken to discover that it was less than a
>10% increase in speed over the optimized C routine.

Very similarly for an encoder for JBIG image format.  I wrote
some very straightforward C code with some macros to unroll
the loops, and it beat hand coded assembler.

Basically, a compiler might sometimes produce better code,
because it can deal with more complexity, but it will never
produce a better algorithm.  Of course, that argument cuts
both ways. 

This is actually the relevant argument for computer Go.  At this
stage of development, advances come from better algorithms, 
not better code.

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

[computer-go] Re: Explanation to MoGo paper wanted.

[Dave Dyer]

One of my favorite observations about Go is that expert play tends
to be "on the edge of catastrophy".  

By playing better moves on the average, you become more vulnerable
to the occasional misstep.

If a program is not very good, random better or worse moves do not have
much effect.  If the program improves, it's closer to the edge, and 
random missteps are more likely to make it fall off the cliff.

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

[computer-go] Re: Explanation to MoGo paper wanted.

[Dave Dyer]

One of my favorite observations about Go is that expert play tends
to be "on the edge of catastrophy".  

By playing better moves on the average, you become more vulnerable
to the occasional misstep.

If a program is not very good, random better or worse moves do not have
much effect.  If the program improves, it's closer to the edge, and 
random missteps are more likely to make it fall off the cliff.

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

[computer-go] Re: Why are different rule sets?

[Dave Dyer]

I think your table tennis analogy is not really applicable.  
The rule changes in table tennis were presumably motivated
by the need to fix a real problem, and really changed the
game.

On the other hand, all the rules arguments in Go are really
only applicable to incredibly marginal, bordering on imaginary
situations.  There's no motivation to change the way the game
is actually played.  

With the stakes so low, there's no limit to debate.

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

[computer-go] Re: Why are different rule sets?

[Dave Dyer]

I think your table tennis analogy is not really applicable.  
The rule changes in table tennis were presumably motivated
by the need to fix a real problem, and really changed the
game.

On the other hand, all the rules arguments in Go are really
only applicable to incredibly marginal, bordering on imaginary
situations.  There's no motivation to change the way the game
is actually played.  

With the stakes so low, there's no limit to debate.

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

[computer-go] U. of Alberta bots vs. the Poker pros

[Dave Dyer]

>The only thing a computer can to is to model opponent's behavior, which may 
>deviate from the best play. What did I miss?

No, you didn't miss a thing.  I look forward to meeting you
at a poker table, preferably with high stakes.

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

[computer-go] Re: repeat postings

[Dave Dyer]

>
>How does this foul spamming programs?   Does it prevent a spammer from
>sending out a lot of email or just delay the receiving of it?

It doesn't delay per se, it rejects the incoming mail with a
"try again later" tag.  The theory is that spambots which
act as their own mailers will not retry.   I'm not sure
how much spam it really stops, but it does make hash of
the expectation that mail is received immediately.

IMO this is a really bad strategy for two additional reasons.  First,
it takes something that is intended as a fallback/recovery procedure
(ie; retrying) and makes it part of the protocol, which just gums up
the works for everyone.  Second, if it were even marginally sucessful,
spambots would simply evolve to keep track of retry requests.

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

[computer-go] Re: Most common 3x3 patterns

[Dave Dyer]

I built a similar database of 3x3 patterns found in professional games.  The
results looked interesting, but I never found a way to use it in a way
that really contributed to the evaluation.

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

[computer-go] Re: Former Deep Blue Research working on Go

[Dave Dyer]

Considering how monte carlo actually works, I think it's plausible
to argue that it works best where the distance to endgame is small.

For a 19x19 board, the playing speed may be only a factor of 4 worse,
but the effective learning speed for an opening position might be
exponentially worse.  In other words, doing 4x as many playouts won't
get you to the same quality of play.  I'm not aware of any data about
what the scaling exponent is, but I'll wager 1 is not the answer.

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

[computer-go] Re: XML alternatives to SGF

[Dave Dyer]

XML per se is not an improvement - it's just another way of wrapping
data in a parseable package.   XML says nothing about the structure,
content, and semantics of the data.  SGF does all that, it's very
Go-friendly, and there are already many tools that use it for Go.

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

[computer-go] Re: XML alternatives to SGF

[Dave Dyer]

XML per se is not an improvement - it's just another way of wrapping
data in a parseable package.   XML says nothing about the structure,
content, and semantics of the data.  SGF does all that, it's very
Go-friendly, and there are already many tools that use it for Go.

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

[computer-go] Re: alternatives to SGF

[Dave Dyer]

>
>However, I am in favor of changing the SGF format to allow coordinate encoding 
>using the "standard" coordinates system rather than the one created just for 
>SGF; i.e., "a1" vs "aa". 

I routinely use sgf for non-go games and completely ignore the
standard set of tag names and contents.  This works fine for me
because I only have to be compatibile with myself - anyone else
who wanted to read sgf-encoded trax games (for example) would
have to follow my example.

The problem with this for Go is that all the existing tools which
are Go oriented would be unlikely to follow your lead on "improving"
the format.


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

[computer-go] Re: alternatives to SGF

[Dave Dyer]

>
>However, I am in favor of changing the SGF format to allow coordinate encoding 
>using the "standard" coordinates system rather than the one created just for 
>SGF; i.e., "a1" vs "aa". 

I routinely use sgf for non-go games and completely ignore the
standard set of tag names and contents.  This works fine for me
because I only have to be compatibile with myself - anyone else
who wanted to read sgf-encoded trax games (for example) would
have to follow my example.

The problem with this for Go is that all the existing tools which
are Go oriented would be unlikely to follow your lead on "improving"
the format.


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

[computer-go] Re: XML alternatives to SGF

[Dave Dyer]

At 04:03 PM 10/22/2007, Markus Enzenberger wrote:
>On Mon October 22 2007 10:15, Don Dailey wrote:
>> almost impossible to write XML manually without bugs.
>
>it also seems to be hard to write an SGF file without bugs.
>I recently run a test on a collection of about 5000 SGF files
>from various sources on the web and more than 20% of them
>generated a warning when reading with GoGui. The most frequent
>problems are duplicate properties or root-properties in
>non-root nodes.

What makes you think GoGui is right?

Thought experiment;  If you took a spec, any spec, and wrote
a program to implement it, what are the odds that it would be
completely compatible with my implementation of the same spec
without rigorous testing?   


>Another problem I have with SGF is that it allows user-defined
>properties. 

And your alternative is?  If you don't allow user defined properties
at all, either you will be ignored, the extra information will be
shoehorned into other properties, for example by magically formatted
comments.  In either case you still have the same problems.  Having
namespaces solves nothing unless you have a central authority dishing
out names for namespace.  Absent a central authority that everyone
respects, you still have potential conflicts from people using
the default namespace or making up their own namespaces.


>Think of resolving a conflict in a Go game file in your version
>control system. If the file format was XML-based, a meta-tool
>could merge changes like version control systems do right now with
>text-based files. Do you want to write a different
>conflict-resolvers for every file format?

True, but against this consider that there already ARE a bunch
of tools to parse, split, merge, copy, bless etc sgf format descriptions
of games.  Not to mention millions of game records in that format.
Do you want to write XML based tools to replace all of them?

Except possibly for XML parse/pretty print programs, I'm pretty sure
there are no existing XML tools of interest to game development.

--

This really falls in the category of distractions.  If your goal in life
is to define the ultimate document format, have at it.  On the other hand,
if you're interested in Go programming, forget it. Work with sgf, and
get back to the actual task.



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

[computer-go] Re: use for Monte Carlo on 19X19?

[Dave Dyer]

>
>the idea is: identify at least one stone from every unconditionally
>living and every unconditionally dead group on the board, and
>report them as dead or alive.

It can be done very fast, but the problem is that in a typical 
endgame board under Japanese rules, the number of unconditionally 
alive stones is zero.


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

[computer-go] Re: use for Monte Carlo on 19X19?

[Dave Dyer]

>
>the idea is: identify at least one stone from every unconditionally
>living and every unconditionally dead group on the board, and
>report them as dead or alive.

It can be done very fast, but the problem is that in a typical 
endgame board under Japanese rules, the number of unconditionally 
alive stones is zero.


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

[computer-go] Re: use for Monte Carlo on 19X19?

[Dave Dyer]

At 05:22 PM 11/6/2007, Ray Tayek wrote:
>At 03:50 PM 11/6/2007, you wrote:
>>... in a typical
>>endgame board under Japanese rules, the number of unconditionally
>>alive stones is zero.
>
>maybe for pro games. for amatuer 1-kyu to 10-kyu games, i suspect that after 
>about 1/2 of the moves in the entire game have been made, enough groups are a 
>few stones away from being benson alive that it would be worthwhile to find 
>these.

The whole problem is to determine what ought to be considered dead.
Finding a group that needs a few more stones to be completely alive
doesn't help at all, because you have to do a full board search to
find out if those moves could actually be made.

A strategy that starts by anchoring the determination in
unconditionally alive groups starts with nothing.

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

[computer-go] Re: use for Monte Carlo on 19X19?

[Dave Dyer]

At 05:22 PM 11/6/2007, Ray Tayek wrote:
>At 03:50 PM 11/6/2007, you wrote:
>>... in a typical
>>endgame board under Japanese rules, the number of unconditionally
>>alive stones is zero.
>
>maybe for pro games. for amatuer 1-kyu to 10-kyu games, i suspect that after 
>about 1/2 of the moves in the entire game have been made, enough groups are a 
>few stones away from being benson alive that it would be worthwhile to find 
>these.

The whole problem is to determine what ought to be considered dead.
Finding a group that needs a few more stones to be completely alive
doesn't help at all, because you have to do a full board search to
find out if those moves could actually be made.

A strategy that starts by anchoring the determination in
unconditionally alive groups starts with nothing.

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

[computer-go] Re: randomness

[Dave Dyer]

>Am I making *any* sense?  If so, you may need some sort of psychiatric help, 
>or alternatively, you could do me the favor of explaining how to ask for what 
>I want or even how to actually get it.  :)

Most computer applications use uniform randomness, but it sounds like
what you want is normally distributed randomness, with mean = 50
and variance to be specified.  Changing the variance changes the slope
of the curve and in effect, the degree to which is is bunched near the
mean.

Given that computer "random" numbers are uniform, you
need to transform them into normally distributed numbers.

Try this:  http://www.taygeta.com/random/gaussian.html

I didn't fully parse it, but it looks like a reasonable source.

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

[computer-go] Re: Language

[Dave Dyer]

>It appears that the question of GC is not dependent on the problem
>(eg. computer-Go) but on the language you use.

This really gets back to the core of the language question.  The
kind of language you choose depends in part on the kind of program
you intend to write.

If you're writing a monte carlo with the simplest and fastest
possible structure, then manual memory management is probably
also not a handicap.

If you're writing a stateful evaluator with lots of caches, lazy
evaluation and a sophisticated search strategy, it can be VERY
difficult to keep track of when a particular bit of data is no 
longer needed, and lack of GC is a major handicap.

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

[computer-go] Re: Language

[Dave Dyer]

>It appears that the question of GC is not dependent on the problem
>(eg. computer-Go) but on the language you use.

This really gets back to the core of the language question.  The
kind of language you choose depends in part on the kind of program
you intend to write.

If you're writing a monte carlo with the simplest and fastest
possible structure, then manual memory management is probably
also not a handicap.

If you're writing a stateful evaluator with lots of caches, lazy
evaluation and a sophisticated search strategy, it can be VERY
difficult to keep track of when a particular bit of data is no 
longer needed, and lack of GC is a major handicap.

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