Re: [computer-go] Tactical search: alpha-beta or and-or?

[Darren Cook <darren@xxxxxxxxx>]

I was surprised no replies to this yet, so I'll throw out one of my
"secrets" to see if it can generate some discussion.

> For tactical search, are people using alpha-beta search or a simpler 
> and-or search to answer the boolean question of whether the block can 
> be saved/killed?

And-or search. If anyone is doing alpha-beta I'd be interested in
hearing how they assign a score and how it worked better than just
searching for dead vs. N+ libs.

It might be better: after all chess is a boolean search to capture the
king, yet alpha-beta works well.

> I've heard several people say that a block is considered alive if it 
> has five liberties.  I've recently starting considering a block alive 
> if it has four or more potential eyes.  A potential eye is a vacant 
> point where none of the adjacent points, and at most one of the 
> diagonal points, are occupied by enemy stones.  (Yes, this misses the 
> fact that enemy stones might be captured.)

How is this going? 4 sounds too high: you'll do a lot more search than
searching for 5 simple libs.

I've experimented a lot with a "good lib" concept. E.g. 3+ good libs is
alive, and a good lib has 2+ slibs. plib means primary lib, slib means
secondary lib (and tlib is tertiary lib). A plib adjacent to another
plib doesn't count as an slib. So to rephrase, if a defender plays at a
plib with:
  1 slib: he has one less liberty
  2 slibs: his liberty count doesn't change
  3 slibs: his liberty count increases by 1
  etc.

It gets complicated by weak enemy neighbours but they matter a lot. I've
had best results following the above description, so if playing at a
plib would capture something then I increase the slib count accordingly.

I firmly believe "good lib tac search" would give better results than a
simple N+ libs is alive search, for the same CPU time. The downside is
code complexity and working out the best combination of parameters (e.g.
4 good libs where a good lib is 2 slibs, or 2 good libs where a good lib
is 3 slibs, or ....)

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