Re: [computer-go] MC approach

2007-02-12 Thread Weston Markham

I think that you are essentially correct.  However, this is only going
to affect a small number of games where two different moves are
exactly tied for the best winning percentage, after many playouts.
Even if the underlying probabilities are exactly the same, you can't
really expect this to happen much.

Weston

On 2/11/07, Heikki Levanto [EMAIL PROTECTED] wrote:

But there is a way. If we do N play-outs, the effect of any single of
them is 1/N. If we make sure to scale the score to be less than half of
this, it can not disturb anything in cases where the number of wins is
different. Only in cases with exactly the same number of wins in the
play-outs, would the score break the tie.

In other words my large constant of 1000 was far too small. It would
have to be something like 2NM, where M is the maximum score (say 361).
Round it up to 1000N, and we should be safe.

I still believe it would make endgames look more reasonable, and
possibly even better, in case the winning program has overlooked a
detail somewhere, having a large margin of points on the board should
act as an insurance against small blunders.

___
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-12 Thread Jacques BasaldĂșa

Erik van der Werf wrote:

And then we get another small questions with a 
dangerous answer...


1. What makes a question big or small is not a personal
preference, but the number of millions times it happens
during a game.

1a. Database lookup. Happens very few times (Unfortunately,
I must say, because I like the knowledge integration
part and I think it is one of my strong points.)

2a. Local search + legal moves identification (see superko)
This happens billions of times per hour of go computing.

Therefore, finding optimal solutions for 1a is a small question
and for 1b its is not a small question at all. Of course, if your
program is hyper-knowledge driven or does not search, this may 
be different.


2. Using an unnecessarily big hash key slows down the program.
On a 32 bit platform, for using a 64 bit key you have to choose 
between bad (2x32) and worse (FPU 64 bit integers). Due to this
slow down, you will fail to complete searches you could have 
done with a smaller hash. Therefore, the program may suffer 
more from code obesity than from collisions. Don't take this
as if I didn't use 64 bit keys. I do. But only when it is a 
good idea.


3. In the cases where a 32 key is enough, a local search 
with 32 stones or detecting superko, it works with error=0

and therefore, it is better than any hash size. 0 is smaller
than 2^-64.

4. The analysis based on uniform distributions are 
fundamentally flawed because the move sequences are not 
random in go, particularly, the BWBWBW sequence can only

be avoided by pass moves which do not occur in real games
globally before the end of the game.

And finally a question: Why do you admit that having two 
identical hashes is a flaw (which is obvious) and do not

admit that having 32 hashes not forming a base is not?

When you have 31 independent hashes, the probability
that a new key forms a base is 1/2. If it does, you can
use this set with error probability = 0, if it doesn't
you will get collisions because the new key is not 
independent. It's the same as having two identical keys.
If the key is dependent, reject it and get another random 
key. That does not change any other statistical properties.

It could have been a random set, many sets pass as they are
others get some correction.

Jacques.

___
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-12 Thread Heikki Levanto
On Mon, Feb 12, 2007 at 11:20:43AM -0500, Weston Markham wrote:
 I think that you are essentially correct.  However, this is only going
 to affect a small number of games where two different moves are
 exactly tied for the best winning percentage, after many playouts.
 Even if the underlying probabilities are exactly the same, you can't
 really expect this to happen much.

I am not sure I agree. In the end of each game there comes a time when
the winner is already certain, or very neaqrly so. Even a MC player will
see this at some point. When that point comes, there is no direction in
pure MC play, except to avoid the worst blunders.  The winning program
is happy to let a tail be cut off here, a small group die there, and a
territory be invaded here, if none of this shakes its unfaltering faith
in its victory. Conversely, the loosing program doesn't even try all
these tricks, as it sees it looses anyway. Both of them play pure
random. It doesn't affect the result, usually. It can be that both
players have misjudged something, and having wasted the winning margin,
that something may turn out to be valuable anyway.

Alas, I don't have my own MC player coded (haven't even started), so I
can not make the experiment myself. If someone here would like to try,
I'd like to hear of it.

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

2007-02-12 Thread Erik van der Werf

On 2/12/07, Jacques BasaldĂșa [EMAIL PROTECTED] wrote:

Erik van der Werf wrote:

 And then we get another small questions with a
 dangerous answer...

1. What makes a question big or small is not a personal
preference, but the number of millions times it happens
during a game.


Can't take a joke? IMO informed hash key generation is interesting
from an academic viewpoint, and a fun exercise. However, in my
experience anything to do with this subject tends to lead only to
relatively small over-all improvements (unless you have a crappy
implementation to start with), and when not used with great care and a
good understanding of the consequences of the domain-specific
optimizations then it easily weakens the performance. To give an
example, if you optimize your keys for global tree-search (using,
e.g., the BCH construction), I would not be surprised if they perform
sub-par on things like opening book construction, or shape hashing.



 1a. Database lookup. Happens very few times (Unfortunately,
 I must say, because I like the knowledge integration
 part and I think it is one of my strong points.)


And what distinguishes database look up from things like transposition
table look up? Why wouldn't one use database look up during tree
search?




 2a. Local search + legal moves identification (see superko)
 This happens billions of times per hour of go computing.


Forget about using hashes for superko/legal move detection, it's a
non-issue. For this you should only use hashes as a last resort.



 Therefore, finding optimal solutions for 1a is a small question
and for 1b its is not a small question at all. Of course, if your
program is hyper-knowledge driven or does not search, this may
be different.

2. Using an unnecessarily big hash key slows down the program.


Hardly. IMO, if the hash calculation is a major factor in the
performance of your program, you should seriously consider adding some
knowledge.

In Migos I had 96-bit hashes and the update time was never an
important factor in the performance. Moreover, I could recompute all
relevant symmetrical hashes from scratch whenever needed without
severely hurting the performance.


On a 32 bit platform, for using a 64 bit key you have to choose
between bad (2x32) and worse (FPU 64 bit integers). Due to this
slow down, you will fail to complete searches you could have
done with a smaller hash. Therefore, the program may suffer
more from code obesity than from collisions. Don't take this
as if I didn't use 64 bit keys. I do. But only when it is a
good idea.


And what fraction of your searches is affected by your new
superior-strength hash keys?


snip


0 is smaller than 2^-64.


Thanks for sharing that :-)



4. The analysis based on uniform distributions are
fundamentally flawed because the move sequences are not
random in go, particularly, the BWBWBW sequence can only
be avoided by pass moves which do not occur in real games
globally before the end of the game.


So?



And finally a question: Why do you admit that having two
identical hashes is a flaw (which is obvious) and do not
admit that having 32 hashes not forming a base is not?


I have no idea what you're talking about here.



When you have 31 independent hashes, the probability
that a new key forms a base is 1/2. If it does, you can
use this set with error probability = 0, if it doesn't
you will get collisions because the new key is not
independent. It's the same as having two identical keys.
If the key is dependent, reject it and get another random
key. That does not change any other statistical properties.
It could have been a random set, many sets pass as they are
others get some correction.


I'm speculating here because I seem to be missing some context, but
AFAICS almost any Go-specific application will have more legal moves /
hash keys than bits for the hash. Consequently for all practical
purposes you will never be able to set up a complete independent set
of hash keys, and in the rare case where you could do it (e.g., on a
small board) you might just as well store the complete state as a
hash.

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


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

2007-02-12 Thread David Doshay

On 9, Feb 2007, at 4:40 AM, Sylvain Gelly wrote:

Alain's point, that knowledge can both help narrow the search to  
good

moves and at the same time steer you away from the best move is
absolutely true in SlugGo's case.

I completely agree with that.
However can we agree that we want a better player in a whole, and not
only better in some particular positions? So perhaps, I think, behind
far from the best move, while playing always good moves is already
good no?

Sylvain


Absolutely. I notice that when SlugGo makes moves that a professional
said look quite playable a huge mistake is going to happen very soon.

Making the best move from the point of view of a really strong player
is also NOT what I want SlugGo to do. SlugGo has no concept of what
the implications are and what the required followup moves will be.

It is clearly better for SlugGo to make many 90% moves in a row than to
have it try to make any 100% moves. There is a much better chance of
it finding the correct followup to slightly lower quality moves.



Cheers,
David






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