Re: [computer-go] Pattern matching - example play

[Vincent Diepeveen <diep@xxxxxxxxx>]

At 10:17 2-12-2004 +0100, Frank de Groot wrote:
>----- Original Message ----- 
From: "Heikki Levanto" <heikki@xxxxxxxxxxxxxxxxx>
>Subject: Re: [computer-go] Pattern matching - example play
>
>
>> Searching all those positions is not a hard problem. Evaluating the
>> resulting positions is hard.
>
>
>Is it really that hard or is the main problem that it takes too much time?
>
>A main difference between Chess and Go is that in chess, you work with a
>single piece and its relation to other pieces or squares but in Go, you work
>with groups that grow and merge and have a whole lot more administration to
>take care of.
>
>I think we should focus a lot on efficient representation/move generation.
>Efficient representation in the sense that finding an eye shape or other
>properties of a group is extremely fast, because pruning the tree is perhaps
>more important than the fastest move generation.
>
>I would like to see publications that thoroughly deal with such mundane
>tasks rather than yet another attempt to work with "symbolized knowledge" or
>yet another Neural Network. But there isn't much glory in that for
>researchers, and I would think that commercial developers keep these things
>secret.
>
>Bitboards, for ex. A major slowdown is counting the # of liberties after
>chains have grown/merged/captured.

Well you don't capture them that much do you?

Ever heard of INCREMENTAL administration?

My primitive go program (19x19), if i still have the source somewhere, did
all that incremental at like 3000 nodes a second at a P5-100Mhz.

That included in evaluation an influence function as described by Mark Boon
at the time.

>Pentiums still don't have a population count instruction, needed after a
>"shake". So I am working on a method to delta-update this stuff.

bitboards and such use vector instructions. Those are dead slow. Normal
simple instructions a processor can execute up to 3 instructions a cycle.
A64 also achieves it. Bitboard instructions such as BSF and BSR are vector
instructions which cost easily more than 7 cycles an instruction. If you
use 2 vector instructions in a row, you also get major stalls of the
processor (especially AMD hardware).

>I think such work is worth 100 hours of time or more. Such relatively simple
>inventions are worth thousands of USD.

Why not offer some money for my incremental administration of liberties and
capturing groups and some incremental influence calculations?

Of course it also sees when 2 groups gets connected to 1 group.

For low price i might sell it to you already, knowing i lack too much go
knowledge to ever write a world top go program.

>They can mean enormous speedups, which can mean the difference of Go program
>#5 or #1 (strength-wise).

Well moving from JAVA to C, your friend Mark Boon can already get a speedup
of a factor 3 for free, and showing up at tournaments with a tad faster
laptop is another factor 2 in speed.

Vincent

>_______________________________________________
>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/