RE: [computer-go] Pattern Matcher

["David Fotland" <fotland@xxxxxxxxxxxxxxx>]

Agreed.  Go progams have small data and lots of decision trees.  Since there
is
no single big search, there is no need for a big hash table, so all hash
table
data is irrelevant.  Many Faces has large data for joseki and fuseki
databases,
which are rarely used.  The pattern database is probed a few thousand times
a second,
for full board move generation, but it's under 100 KB.  The rest of the data
used by the engine
is under 100 KB.  So everything that needs to be fast fits in the second
level cache.

I use single dimension arrays to avoid multiplies, everything is integer, to
avoid slow
floating point instructions.

I use small hash tables during tactical search, but the trees are only a few
hundred nodes each,
so no need for large tables.  I save life and death reading trees from move
to move, but there
are only a few thousand active nodes at any one time.

David

> -----Original Message-----
> From: computer-go-bounces@xxxxxxxxxxxxxxxxx 
> [mailto:computer-go-bounces@xxxxxxxxxxxxxxxxx] On Behalf Of Arend Bayer
> Sent: Tuesday, November 09, 2004 7:09 AM
> To: computer-go
> Subject: Re: [computer-go] Pattern Matcher
> 
> 
> 
> 
> On Tue, 9 Nov 2004, Vincent Diepeveen wrote:
> 
> > The best possible book you can get is for free.
> > 
> > Go to the AMD and intel websites and get the processor 
> documentation.
> > 
> > If you realize what the processor is fast at, and what it 
> is slow at, 
> > it is very trivial to code for that.
> 
> I did this some time ago, and found it pretty much a waste of 
> time as far as optimizing GNU Go is concerned. The reason is 
> that GNU Go's performance is 90 % bound by 
> branch-misprediction, and that you cannot optimize these 
> branches away. Btw I was told that the same held true for the 
> version of Many Faces that David Fotland had submitted to 
> SPEC95, and I would not be surprised if that is true for any 
> go program.
> 
> Arend
> 
> 
> _______________________________________________
> computer-go mailing list
> computer-go@xxxxxxxxxxxxxxxxx 
> http://www.computer-go.org/mailman/listinfo/computer-go/
> 


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