Re: computer-go: Live or Die

[Martin Mueller <mueller@xxxxxxxxx>]

>> Many Faces does a very selective best-first search.  The current
>> version also has some major bugs in the static eye evaluation since
>> I'm part way through a major change.  Many Faces does not stop at
>> the first move that works.  It tries to find all moves that work,
>
>Can I ask the other people on this list who are working on L&D whether
>they also take an approach based on eyes ?
>
>I imagine the reason why ManyFaces does this is because its positions
>are open.. even then, it is probably possible to get by without a notion
>of eyes. My current brute force algorithm works on the concept of
>capture only (eyes are a heuristic for humans beings..)
>

Here is what I do:
For historical reasons my program Explorer has three different ways of eye
evaluation. On the top level, I have a heuristic static eye evaluator
similar to David's. For finding safe stones and territories, I use the
exact rules described in my GPW'97 paper. And during Life&Death search, I
currently recognize only trivial 1 point eyes. It is very fast but stupid.
I think it would be better if I used the other rules, but did not get
around to implementing it yet.

The heuristic static eye evaluator uses the following classification:
int	m_minEyes, // minimum estimated number of eyes in this area: 0,1,or 2
	m_maxEyes,  // maximum estimated number of eyes in this area.
	m_minPotEyes, // minimum estimated number of potential eyes
	m_maxPotEyes; // maximum estimated number of potential eyes

The first two numbers estimate the already completed eye shape, so they
should be achievable even if the opponent goes first. Potential eyes
estimate what you can get if you move first yourself. For example minEyes =
m_maxEyes = 0, m_minPotEyes = m_maxPotEyes = 1 would be 'half an eye',
a point where the player can make an eye and the opponent can prevent it.

Of course this is mostly heuristics, and there are some cases that do not
map well to these numbers.

	Martin