[no subject]

[Joan Pons Semelis <joan@xxxxxxxxxxxxxxxx>]

generating moves and evaluating
A couple of years ago I posted "Taking care of trees", I've
not been able to work too much on The Turtle (my go program)
for a while but finally it has almost reached anter-pre-gamma
stage. ( I mean, it's rather a program to develop a go program
than actually a go program. )
I'll enter the ladder any time *really* soon now :-)

It's written in forth (no fancy GUI yet) and will be slow. 
In the meantime some thoughts:

Let's divide go positions in 2 kinds, this will give some
restrictions:
a)  one and only one is the right move ( i.e. big group has to
    make 2 eyes )
b)  there are half a dozen of reasonable moves, leading to
    different strategies and games.

The program is based in:
1) a move generator that filters/chooses some % of all the legal
   moves, GenMov from now on.
   It's obvious that it has to include _the_ right move in case a).
   but only some of them in case b).

2) an evaluation function that scores a position : who is ahead,
   by how much, probability of victory, stability (vs aji), ...
   Eval from now on.
   Again, it has to be able to sort out _the_ right one from all
   the moves proposed by GenMov in a) but it's not so terrible in b).

To get a move:
 1. Eval the position (we need information to choose a move)
 2. GenMov proposes some moves.
 3. Eval each of these moves to actualy *find* which is better.
 n. Mini-max/alfa-beta/... ad libitum (while there's need/time)

Of course 1.Eval and 3.Eval could be different, as well as GenMov
can be chosen from a pool depending on 1.Eval output, and the same
with 3.Eval. This will remain implicit.

First trade off to think of is on the relationship between Eval and 
GenMov, it looks natural (to me) to have an (as) accurate (as 
possible) Eval and a fast GenMov, so we'll try to keep the later's 
speed negligible. Of course this may mean that we are passing to 
1.Eval some work not needed (?) in 3.Eval. I'll keep talking of
1./3.Eval, but I think anything done in 1. will be useful to get
a more accurate (and slower) 3. so they coul be the same.

Next trade off is speed/accuracity of Eval, the cases being:

a: 1.Eval So Good that GenMov is able to pick up the right move at once.
b: 3.Eval So Good that no look ahead is needed.
   GenMov only needs be sure to throw the good one between any others.
(back to reality)
c: 3.Eval Good Enough to dismiss stupid moves proposed by GenMov.
   GenMov only needs be sure to throw the good one between any others.
d: 3.Eval has blind-spots and can chose a stupid move. GenMov must
   filter those or mini-max can (?) solve problem.
e: GenMov does not propose any ridiculous move, but it's neither
   sure that best one is there. 3.Eval has to stand this mediocrity.
f: You know it.

To narrow GenMov's proposal, 2 strategies are possible:
a: filter out bad moves, as many as possible.
   This way best one is (hopefully) always in but number can be high
   and 3.Eval is busy discarding stupid moves.
b: choose only good moves. 3.Eval has not to cope with silly moves,
   number of proposed moves can be kept small (?) but the risk of
   letting out _the_ good one in go position case a) is higher.  


Conclusions:
  Global look ahead is necessary: it's not only a question of finding
how to save a group in danger, that could be local, but whether it is
possible to save it _and_ win the game. So either Eval is used after
tactical exploration and it does not only return 'alive/dead' but also
'and wining/losing' (does any one use this approach) or it's the global
look ahead that takes care of this.
  Because of the complexity of an Eval that can tell who wins even when
the game is over, GenMov must propose as few moves as possible, while
assuring that the good(s) one(s) are proposed; this means 1.Eval has to
provide enough information. But once the branching factor is narrowed
enough, maybe (experiences ?) it's globally faster, thus better, to have
  . a faster 1.Eval even if that means 1 more move proposed by GenMov or 
    the need of 1 more step to go for mini-max to sort the moves proposed
    or a slower 3.Eval
  . a faster 3.Eval even if that means the need of 1 more step to go for 
    minimax to sort the moves proposed or a slower 1.Eval to allow GenMov
    a smaller/better_suited proposal.


Joan Pons i Semelis
joan@xxxxxxxxxxxxxxxxx