Re: Advice on evaluation

[Bruno Bouzy <Bruno.Bouzy@xxxxxxxxxxxxxxxxxxxxxxxx>]

Hi,

A 21:26 16/05/99 -0700, David Fotland a écrit :
>I'm thinking about evaluating differently based on who is moving next.
>For group strength today, I have a single value.  I'll have two values
>after this change:  one for white to move, and one for black to move.
>I can look at the difference between those values to see if a group is
>worth attacking or defending.
...
>
>Can any of the other people with programs let me know what they
>think?  
...
>
>David

I sent an answer to David and to the mailing list a few days ago.
But I realized that the mailing list sent back the answer to me.
So after having subscribed to the list again, I try to post the message again.
Sorry David if you received the message twice.

Even if they do not strictly match your question,
my program (Indigo) has two values for each group anyway.
Therefore here is my answer:
 the first value is the group strength (a number between 0 and 1) 
 and the second one is the uncertainty about the group strength 
 (also a number between 0 and 1).

group strength = 0 (resp. = 1) means that the group is dead (resp. alive)
uncertainty = 0 means that the group is dead or alive 
uncertainty = 1 means the the group is weak, very near from death, no life
base,
circling almost completed.

The fact is that killing a near-from-death-group is difficult. 
At least more difficult than making a group living. 
In order to kill a group you must gather all the conditions. Killing
is an AND of conditions.
To make life you may satisfy only one condition among many. 
Making life is an OR of conditions.
For this reason, I modeled uncertainty with high value for groups that are
near from death.

The evaluation function has also 2 values:
  the first value is the classical one (sum of ...)
  the second one is the sum of the uncertainty of groups
In other words ef is an interval.

I did that in order to capture the fact that Indigo is not able to read fights
until the end but anyway its strategical level needs some approximation
of what is happening on the board. 
In fighting situations, the ef is almost 0 and its uncertainty is the
size of the situation
In terminal situations, the ef is of course the difference of size of
territories
for black and white and uncertainty is 0.

Then a reformulation about group strength and some questions:

Let P (resp. Q) be the smallest number of moves of the friendly (resp. enemy)
color to make a group alive (resp. dead)
Each group has two numbers {P|Q}
When P or Q = 1 or 2, (or 3?) classical lookahead is relevant because life
or death
of the group is a reachable goal.
When P or Q >= 3 (or 4?), classical lookahead may not end.

Groups with P or Q = 0 are stable (because they are dead or alive :-))
Groups with P and Q >= 3 or 4 are more or less stable (because one move 
on them does not change their status in a clear way). This the gray area.

The basic question reformulated is what to do with groups with P and Q >= 3 ?
  You may tenuki if you consider they are more or less stable
    (The danger is that Q may suddenly become 0, 1 or 2 and it will
     be too late to save the group)
  You may add P moves to make it alive 
    (The danger is to spend almost P-2 moves and see the opponent
     answering and kill the group definitely...)
These two answers are not satisfactory.
According to me, this is one of the big question computer go.

What to do ?
Try to uncover more accurate static conditions ?
It is very difficult to capture static conditions for group strength.
If we have uncover such conditions, we should be able to reduce the
gray area between life and death and perhaps we could have groups with 
P and Q = 1 or 2 only, lookahead would be more relevant and computer go 
would be simpler :-(

In the absence of such conditions, I like the simple idea of
the 2 values for each side to move and the use of the difference
to choose the important group to focus on.

Bruno

--------------------------------------------------------------
	Bruno Bouzy
	C.R.I.P.5 - UFR de mathematiques et d'informatique
	Universite Rene Descartes (Paris V) 
	45, rue des Saints-Peres 75270 Paris Cedex 06 FRANCE
	tel: (33) (0)1 44 55 35 58 fax: (33) (0)1 44 55 35 35
	e-mail: bouzy@xxxxxxxxxxxxxxxxx 
	http://www.math-info.univ-paris5.fr/~bouzy/
--------------------------------------------------------------