Re: [computer-go] Monte-Carlo Go simulation

2007-02-09 Thread alain Baeckeroot
Le jeudi 8 février 2007 22:09, Sylvain Gelly a écrit :
  It seems i was ambiguous: I was speaking of the simulation player too.
  What i meant is a random simulation player is not biased, whereas a better
  simulation player is biased by its knowledge, and thus can give wrong
  evaluation of a position.
 I think we have to start defining what the bias. For me the bias is
 the difference between the expected value of the outcomes of playouts
 by the simulation player and the real minimax value. In this
 definition the uniform random simulation player is VERY biased and
 gnugo much less.
OK, by i used bias in common sense, to mean that the strong simulator has
preferences for some moves, and doesn't consider them equally, 
or worse doesn't consider some moves. So it will miss some good points due to
its knowledge, whereas the random player will find the move.

 
  A trivial example is GNU Go: its analyze is sometimes wrong.
 Of course, if not computer go would be solved :-).
 
  Even if it is obviously much stronger than a random player, it would give
  wrong result if used as a simulation player. 
 Hum, are you sure?
I m 100% sure of this :-) 
 
 I think that GnuGo with randomisation, (and much 
 faster of course) would make a very good simulation player (much
 better than any existing simulation player).
Even with randomization, GNU Go considers only a few dozen of possible moves,
and makes systematic errors. Some times ago Rémi Coulom asked for positions
illustrating computer stupidity (2006-11-22) 
http://computer-go.org/pipermail/computer-go/2006-November/007107.html
and GNU Go provided some nice examples where its (wrong/misunderstood) knowledge
induces a failure in play. One very impressive was GNU GO 3.6 not invading
where obviously it is possible to invade (Steven Clark 2006-11-27)
http://computer-go.org/pipermail/computer-go/2006-November/007184.html

 But a weaker player than GnuGo can make an even better simulation player.
yes.
 
  David Doshay experiments with SlugGo showed that
  searching very deep/wide does not improve a lot the strength of the engine,
  which is bound by the underlying weaknesses of GNU Go.
 Yes, this a similar non trivial result. I think there are more
 existing experimental and theoritical analysis of this, though.
 Perhaps such an analysis already exist for MC also, it is just that I
 don't know.
 
  Or maybe i just understood nothing of what you explained ;)
 It was not really explanations, just thoughts. I have no the
 solution, just think that it is an interesting question, and that it
 may be discussed. May be from a strong explanation of this phenomenon
 could come new ideas.
 
 I understand all these counter examples, I just think that it is more
 complicated than that.
 
 Sylvain

I fully agree.
Alain
___
computer-go mailing list
computer-go@computer-go.org
http://www.computer-go.org/mailman/listinfo/computer-go/


Re: [computer-go] MC Go Effectiveness

2007-02-09 Thread Ephrim Khong
Unknown wrote:
 BTW: once you choose the /8 gain by implementing canonicalization,
 you'll probably want to implement /2 color-swaps, too. (but this will
 only be profitable for libraries, not for 'history' such as in Don's
 case.)

The /2 with color-swaps would work fine with librarys that don't store
the whole gamestate, but I doubt it's worth implementing it in
fuseki-librarys: Since there are usually no or very few captures during
the fuseki, the player whos turn it is is determined by the gamestate
itsself: Black if both colors have the same number of stones on the
board, white if it differs. This means that color reflected positions
can only occur if there was a capture or if you don't rely on the whole
gamestate (eg. pattern-librarys, fuseki-librarys that allow ? fields
that are undetermined).

eph

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


Re: [computer-go] MC Go Effectiveness

2007-02-09 Thread Don Dailey
On Fri, 2007-02-09 at 13:19 +0100, Ephrim Khong wrote:
 The /2 with color-swaps would work fine with librarys that don't store
 the whole gamestate, but I doubt it's worth implementing it in
 fuseki-librarys: Since there are usually no or very few captures
 during
 the fuseki, the player whos turn it is is determined by the gamestate
 itsself: Black if both colors have the same number of stones on the
 board, white if it differs. This means that color reflected
 positions
 can only occur if there was a capture or if you don't rely on the
 whole
 gamestate (eg. pattern-librarys, fuseki-librarys that allow ? fields
 that are undetermined).

Or if there is a pass.   You can throw my program out of book by passing
on one of the first moves :-)

 eph 

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


[computer-go] pure random mode

2007-02-09 Thread Don Dailey
Hi Sylvain,

In the MoGo report paper, you make this statement:   

   We also privilege the moves eating some stones.

This refers to a version of MoGo that doesn't have the
pattern knowledge and you call it the pure random mode.

My program does this too but in a probabilistic way.  I'm
curious about how you did that in Mogo.   Did you always
play a capture when one was available for instance?   Were
you selective about which captures to play?


- Don


P.S.

Here is more context from your paper:

In our pure random mode, legal moves are played on the Go board
uniformly randomly, with few rules preventing the program from filling
its own eyes. This is probably like what the other Monte-Carlo
programs use. We also privilege the moves eating some stones. On CGOS
the bot named MoGo using exactly this mode has achieved rank 1647.


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


Re: [computer-go] pure random mode

2007-02-09 Thread Sylvain Gelly

Hi Don,


In the MoGo report paper, you make this statement:
   We also privilege the moves eating some stones.

This refers to a version of MoGo that doesn't have the
pattern knowledge and you call it the pure random mode.



My program does this too but in a probabilistic way.  I'm
curious about how you did that in Mogo.   Did you always
play a capture when one was available for instance?   Were
you selective about which captures to play?

To your two questions: Yes and No.
It was very simple: IF there exist at least one capture move, THEN
play one of them uniformly from all capture moves, else play uniformly
over all possible moves (excluding eye filling).

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


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

2007-02-09 Thread wms
Peter, java serialization is not a good way to do persistent storage
of any kind, especially large data structures.

It has some pretty severe drawbacks:

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

Java serialization is excellent for RMI, but is pretty poor for any
other use. I've used serialization myself several times and I
regretted it every time (except for when I used it for RMI).
 
My advice would be to come up with your own data format and use
that.
___
computer-go mailing list
computer-go@computer-go.org
http://www.computer-go.org/mailman/listinfo/computer-go/


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

2007-02-09 Thread terry mcintyre
Is this opening book database used for the UCT portion, or the playout portion 
of Orego? In the UCT portion, speed of access may not be that important; a 
database would probably be ideal. If used during the playout, then speed of 
access is more crucial.
 
Terry McIntyre
UNIX for hire
software development / systems administration / security

[EMAIL PROTECTED]
- Original Message 
From: Nick Apperson [EMAIL PROTECTED]

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


- Nick

On 2/9/07, [EMAIL PROTECTED] [EMAIL PROTECTED] wrote:
Peter, java serialization is not a good way to do persistent storage
of any kind, especially large data structures.

It has some pretty severe drawbacks:

- It is slow
- It breaks easily (ie, becomes unable to load older data sets) when

  you make even small changes in your code.
- It makes inefficient use of space
- The format is difficult to decode or manipulate in any way other
  than reading or writing with the exact .class file used to generate

  the serialization code.

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


My advice would be to come up with your own data format and use
that.
___
computer-go mailing list
computer-go@computer-go.org

http://www.computer-go.org/mailman/listinfo/computer-go/



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






 

Any questions? Get answers on any topic at www.Answers.yahoo.com.  Try it now.___
computer-go mailing list
computer-go@computer-go.org
http://www.computer-go.org/mailman/listinfo/computer-go/

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

2007-02-09 Thread Peter Drake

On Feb 9, 2007, at 10:48 AM, Nick Apperson wrote:

What type of data are you trying to serialize or rather store to  
disk?  Do you have pointers in the data.  Don't tell me you don't  
have pointers just because it is java.


I wouldn't dream of it. Java has pointers and I use the hell out of 'em.

Java has pointers, it just preteneds it doesn't.  Show us the  
datastructure and we can probably help you more.  If each entry has  
no pointers than your task should be pretty straightforward.  If  
you do have them, you are going to need to find a way to store  
those so that they are able to be redetermined.


Java's serialization mechanism does this automagically.

In a language like java, where you can't do pointer arithmetic or  
anything of the sort this can get rather difficult.  Also, have you  
considered using a database instead of a flat file to store this data?


I'm going to try Terry's idea of storing individual Nodes instead of  
storing the entire Node pool. Stay tuned...


Peter Drake
Assistant Professor of Computer Science
Lewis  Clark College
http://www.lclark.edu/~drake/

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


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

2007-02-09 Thread Peter Drake
The UCT portion. I'm storing/loading a pre-built UCT tree once at  
startup; the disk is not accessed during the game.


Peter Drake
Assistant Professor of Computer Science
Lewis  Clark College
http://www.lclark.edu/~drake/




On Feb 9, 2007, at 11:08 AM, terry mcintyre wrote:

Is this opening book database used for the UCT portion, or the  
playout portion of Orego? In the UCT portion, speed of access may  
not be that important; a database would probably be ideal. If used  
during the playout, then speed of access is more crucial.


Terry McIntyre
UNIX for hire
software development / systems administration / security

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


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

2007-02-09 Thread Stuart A. Yeates

I serialised some very large Markov models (tens to low hundreds of
megabytes) for my PhD using java serialisation. A couple of hints:

*) they can be faster if you compress them (I used the standard Java
libraries). Disk access was the limiting factor in my case and
compression (I got 80% compression routinely) eased this bottleneck.

*) write functions to allow standard tail recursion optimisations to
performed by the compiler. I admit I never actually tested the
effectiveness of this, but it should improve with successive
generations of compiler. http://en.wikipedia.org/wiki/Tail_recursion

*) I only ever serialised classes of trivial structure which other
classes acted upon. I don't recall serialisation ever breaking. If the
classes you are serialising are the same classes you're changing every
time you make a minor change to your algorithm, that many change. Yes,
this breaks the vision of objects as both the data and the algorithms
acting on them.

*) If your data structure is very deep (which I imagine it is, if
you're seeing stack overflows), you may be better to store pointers to
every node in a hashtable (which is iterated though by the serialiser)
and serialise that.

*) The command line option -Xss controls the size of the stack (with
the Sun JVM). Use it just like the other memory options.

*) as pointed out elsewhere, this is probably not an ideal archival format.

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


[computer-go] Zobrist hashing with easy transformation comparison

2007-02-09 Thread Nick Apperson

Hey all,

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

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

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

if we have 0x1234567890ABCDEF as a zobrist value,

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


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

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

Re: [computer-go] MC approach

2007-02-09 Thread Weston Markham

I don't seem to have any numbers on this anymore, but I should be able
to try some experiments this weekend.  I do have some code that does
what I describe below.  It is also using an all moves as first
heuristic.  According to my notes, I made this change in an attempt to
avoid severely conservative (in my non-expert opinion) moves near the
beginning of the game, which seem to be preferred when using
all-moves-as-first.  It specifically aims for a 30-point lead at the
beginning of the game, and reduces this by one point for each turn
into the game.

I should point out that I am not averaging scores, but simply changing
which games I count as wins for the evaluation of a move.  This is
perhaps not quite what Steve Uurtamo had in mind when he was
originally musing about being greedy at the beginning of the game.
Nevertheless, it is a very similar sort of idea to what he described,
so I thought that I would mention it.

Weston

On 2/8/07, Chris Fant [EMAIL PROTECTED] wrote:

On 2/8/07, Weston Markham [EMAIL PROTECTED] wrote:
 I believe that I have had some success with an approach like this,
 actually.  I believe that I initially only tally games that are won by
 a certain margin, and reduce that margin to zero as the game
 progresses.  I am pretty sure that this improves upon straight Monte
 Carlo.  I think that I can get some numbers on it, if anyone is
 interested.

 Weston

Yes, please.

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


Re: [computer-go] Zobrist hashing with easy transformation comparison

2007-02-09 Thread Antoine de Maricourt

Hi,

did you read Anti Huima's paper? The idea looks similar, but 
unfortunately it does not work. I provided a proof of the defect on this 
list (end of 2002 if I remember well). It's not that easy to get a 
working scheme. In fact there is only one combination with 8 chunks of 
data. In 2002 I exchanged a lot of email with Nici Schraudolph, and we 
found the right scheme. We wanted to write a paper, but we did not (it 
takes time, and I had not that much time - mathematic and computer go is 
just a hobby for me).


After having the right scheme, the tricky part is to perform a 
statistical analysis: unfortunately introducing constraints to deal with 
symetries weakens the hash key. The probability of collision becomes non 
uniform and depends on the board configuration. In short: if you take 
two different random board configurations, then the probability that 
they have the same key becomes higher if one of the configuration has 
self symetries.


If there is strong interest, I can post the scheme. But I'm not sure I 
will post the statistical analysis (it was almost ten hand writen pages, 
and I'm not sure I still have them).


Antoine.

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


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

2007-02-09 Thread Lucas, Simon M

 Three alternative options to Java's native serialisation:

  * Object database db4o: http://db4o.com  

  * WOX (Web Objects in XML) (my own)
 http://algoval.essex.ac.uk/wox/serial/readme.html

  * JSON (JavaScript Object Notation) - also has Java libraries.

   Simon Lucas


-Original Message-
From: [EMAIL PROTECTED]
[mailto:[EMAIL PROTECTED] On Behalf Of [EMAIL PROTECTED]
Sent: 09 February 2007 18:40
To: computer-go@computer-go.org
Subject: Re: [computer-go] Serializing a very large object in Java

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

It has some pretty severe drawbacks:
 

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

Java serialization is excellent for RMI, but is pretty poor for any
other use. I've used serialization myself several times and I regretted
it every time (except for when I used it for RMI).
 
My advice would be to come up with your own data format and use that.
___
computer-go mailing list
computer-go@computer-go.org
http://www.computer-go.org/mailman/listinfo/computer-go/
___
computer-go mailing list
computer-go@computer-go.org
http://www.computer-go.org/mailman/listinfo/computer-go/


Re: [computer-go] Zobrist hashing with easy transformation comparison

2007-02-09 Thread Łukasz Lew

On 2/10/07, Antoine de Maricourt [EMAIL PROTECTED] wrote:

Hi,

did you read Anti Huima's paper? The idea looks similar, but
unfortunately it does not work. I provided a proof of the defect on this
list (end of 2002 if I remember well). It's not that easy to get a
working scheme. In fact there is only one combination with 8 chunks of
data. In 2002 I exchanged a lot of email with Nici Schraudolph, and we
found the right scheme. We wanted to write a paper, but we did not (it
takes time, and I had not that much time - mathematic and computer go is
just a hobby for me).

After having the right scheme, the tricky part is to perform a
statistical analysis: unfortunately introducing constraints to deal with
symetries weakens the hash key. The probability of collision becomes non
uniform and depends on the board configuration. In short: if you take
two different random board configurations, then the probability that
they have the same key becomes higher if one of the configuration has
self symetries.

If there is strong interest, I can post the scheme.

Please do.


But I'm not sure I
will post the statistical analysis (it was almost ten hand writen pages,
and I'm not sure I still have them).

Have You performed an empirical test for collisions?

Best,
Łukasz Lew



Antoine.

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

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

Re: [computer-go] Zobrist hashing with easy transformation comparison

2007-02-09 Thread Nick Apperson

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

- Nick

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


Nick,

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

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

Erik


On 2/9/07, Nick Apperson [EMAIL PROTECTED] wrote:
 Hey all,

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

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

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

  if we have 0x1234567890ABCDEF as a zobrist value,

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


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

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

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

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

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

2007-02-09 Thread Ray Tayek

At 09:55 AM 2/9/2007, you wrote:

..., Java  has a stack overflow error.


i assume you have tried the java -Xss to set the stack size (type 
java -X for help on these)?


thanks

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


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