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

2007-02-13 Thread Jacques Basaldúa

Hi Erik


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


The interest in rotation/mirror. In database search, what is good for
a position is good for the mirror/rotation. In tree search, rotation
of the full board does not happen, and if it does (in a very simple
position) its pointless to detect because it is not the same position.


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?


Of course. The most important superko that really happens in strong
games is triple ko. Detecting triple ko with probability=1 and a 32
bit hash is not a trivial question. And it requires B keys to have
some difference with W keys. Note that to be _sure_ that a move is 
legal, you only have to check 6x32 bit keys. That would be impossible 
if the hashes were pure random. You simply cannot control any 
combination of 19x19x2=722 hashes of length 6, but you can control 
BWBWBW even of length 7. Since the test is faster than any another and 
is also, unlike the others, with error probability=0 it is simply the 
best. Of course, it does not consider board repetitions of longer 
cycles. I have searched for (the possibility of) such cycles in my 50K 
games database and did not find any. I would love to see a game where 
both players are at least shodan, in which a superko other than triple 
ko limits the legal options. If someone has such a game, please post it.



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. 


Of course. That's because full global search is intractable. But local
search with 16 empty cells (which can be either B or W, and therefore
you only have 32 keys) is not. That's what I mean when I say when it 
makes sense. Again, I do use 64 bit hashes.



And my favorite:

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


We have seen this when talking about programming language. Each time
someone cares about details and builds programs that are optimized
from the day of their birth, they are:

 a. Dirty and hard to maintain. (IMO only patched programs are
hard to maintain and they are patched because important issues
were thought too late.)

 b. Caring about stupid issues == ignoring Big Algorithmic
Improvements. (IMO If you don't really care about details you
don't really control the big picture. And more important, you
only have to do it once, if you do it well. That will give you a 
lot of time for thinking about algorithms.)



Jacques.


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


Re: [computer-go] Bit Twiddling Hacks

2007-02-13 Thread Erik van der Werf

On 2/12/07, Phil G [EMAIL PROTECTED] wrote:

For those doing a lot of bit logic in their computer go programs, you might
be interested in this collection of highly optimized methods for doing
things with bits

(like counting bits sets in parallel and computing the minmum or maximin of
two integers without branching):

http://graphics.stanford.edu/~seander/bithacks.html



Seen it before, but still a very nice site with lots of clever tricks.

I have some improved bit counters, if anyone is interested...

Erik
___
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-13 Thread Chris Fant

The following code did not hurt the strength against self-play in over
2000 games at boardsize 8x8 (faster games) with 10k playouts per move:

  moveEval[m] = (float)wins[m]/nGames[m] +
points[m]/(nGames[m]*Board-Spaces*100)

where points[m] is accumulated only for wins.
___
computer-go mailing list
computer-go@computer-go.org
http://www.computer-go.org/mailman/listinfo/computer-go/


Re: [computer-go] Bit Twiddling Hacks

2007-02-13 Thread Jim O'Flaherty, Jr.
Erik,

I am.


Jim


- Original Message 
From: Erik van der Werf [EMAIL PROTECTED]
To: computer-go computer-go@computer-go.org
Sent: Tuesday, February 13, 2007 3:37:13 PM
Subject: Re: [computer-go] Bit Twiddling Hacks

On 2/12/07, Phil G [EMAIL PROTECTED] wrote:
 For those doing a lot of bit logic in their computer go programs, you might
 be interested in this collection of highly optimized methods for doing
 things with bits

 (like counting bits sets in parallel and computing the minmum or maximin of
 two integers without branching):

 http://graphics.stanford.edu/~seander/bithacks.html


Seen it before, but still a very nice site with lots of clever tricks.

I have some improved bit counters, if anyone is interested...

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




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

Re: [computer-go] Effective Go Library v0.101

2007-02-13 Thread Chris Fant

Does anyone know what find-union algorithms Lukasz is referring to
in the README file?
___
computer-go mailing list
computer-go@computer-go.org
http://www.computer-go.org/mailman/listinfo/computer-go/


Re: [computer-go] Effective Go Library v0.101

2007-02-13 Thread Weston Markham

This was discussed on the list a while back.  There's a good Wikipedia article:

http://en.wikipedia.org/wiki/Disjoint-set_data_structure

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

Does anyone know what find-union algorithms Lukasz is referring to
in the README file?

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


Re: [computer-go] Effective Go Library v0.101

2007-02-13 Thread Łukasz Lew

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

On Sun, Feb 04, 2007 at 02:13:33PM +0100, ?ukasz Lew wrote:
 Optimizing and refactoring became my hobby, but it's too absorbing :)
 It's time to add some features now.

Just one question: Is the gtp support sufficient to play against other
machines (if we ignore the rather trivial genmove code :-)? If not,
adding the missing commands, even as dummies, would be a help for
beginning programmers.

Yes it is.



Also, I notice that I can not use quarry (graphical interface for Go and

Try GoGui.


other games) to play against 'engine_opt'. Presumably it needs a few
more gtp commands implemented. I will look into this, because if I am to
write any sort of engine, I will want to be able to play agaist it. Will
make a good warming-up exercise.

Thanks again for a good, useful library. I have started to look into it,
and once I got aroundthe namespaces and short names within, it looks
reasonably clear. I will experiment with some ideas, and if anything
useful comes out of them, I let you know. If I run into obvious
improvements, I may even send a patch.


Thanks :)

Łukasz



Regards

   Heikki

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


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

Re: [computer-go] MC approach

2007-02-13 Thread Weston Markham

On 2/9/07, Weston Markham [EMAIL PROTECTED] wrote:

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.



I did run some tests over the weekend, but they did not complete as
quickly as I had expected.  Anyway, I have enough data at this point
to say that although there is nothing spectacular to show one way or
the other, I was probably wrong that the code was an improvement.

Playing against gnugo 3.7.10, komi 7.5, playing black in 50% of the games:

86/732 games won baseline (11.7%)
106/1000 games won after enabling logic described above. (10.6%, a
slight degradation)

I also tried a version that dynamically adjusts an expected score,
and tallies the number of games where the score exceeds this.  It
appears to give an improvement:  12.8% of the games were won, out of
1000.

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


Re: [computer-go] Bit Twiddling Hacks

2007-02-13 Thread Erik van der Werf

Here's a link:

http://erikvanderwerf.tengen.nl/pubdown/bitcounters.c

Have fun,
Erik


On 2/13/07, Jim O'Flaherty, Jr. [EMAIL PROTECTED] wrote:


Erik,

I am.


Jim



- Original Message 
From: Erik van der Werf [EMAIL PROTECTED]
To: computer-go computer-go@computer-go.org
Sent: Tuesday, February 13, 2007 3:37:13 PM
Subject: Re: [computer-go] Bit Twiddling Hacks


On 2/12/07, Phil G [EMAIL PROTECTED] wrote:
 For those doing a lot of bit logic in their computer go programs, you
might
 be interested in this collection of highly optimized methods for doing
 things with bits

 (like counting bits sets in parallel and computing the minmum or maximin
of
 two integers without branching):

 http://graphics.stanford.edu/~seander/bithacks.html


Seen it before, but still a very nice site with lots of clever tricks.

I have some improved bit counters, if anyone is interested...

Erik

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