[computer-go] RE: Scalability

["Persson, Magnus" <persson@xxxxxxxxxxxxxxxxxx>]

> -----Original Message-----
> From: Don Dailey [mailto:drd@xxxxxxxxxxxxxxxxx]


> From your email, it occured to me that YOUR quiecence search could
> simply be:  Add 1 ply to the leaf if the move resulting in the leaf
> position increased the score by some margin.

This is almost the same as a 2-ply search with iterative deepening, if I
understand you correctly. After the first 1-ply a program would try to
search as many moves as possible to two ply, using a move order based on
the score from the 1st ply search. "Highest score first" would of course
include all moves larger than the margin proposed.

By using the same local move heuristics for move ordering at the second
ply, then most moves would be refuted immediately. But every time there
is no beta cut all the legal moves will be searched, assuming normal
alfa beta.

Right now my program searches at most about 2-3 N moves (N = number of
legal moves, (and many moves are never searched)). But if a better move
than alfa is found 6 times then there will be more than 6N evaluations.

But the worst problem is what to do with all moves at the second ply
that is also "disturbing"? The same simple solution cannot be used
recursively for infinity.

Restraining the 2nd ply to only local responses is therefore perhaps the
simplest and most effective solution (but in principle to restrictive
since a reply to a forcing move is often a forcing move itself).
Especially for my program where not even a 1-ply search is feasible late
in the middlegame. It will sometimes barely search 20 moves (but up to
10 moves 2ply locally for both colors) in positions with 150 legal
moves.

Only playing local moves then becomes analogical to exchanges in chess
where the disturbing material simply is captured. In go, the aji of
shape defects disappears when many stones are played in a local
exchange.

Interesting discussion! I do not think my way of doing is the best. I
think it is too restrictive. It cannot handle situations where the best
response is non-local. Because by "local" my program only count the
moves very close the last played stone. The proper way of thinking about
locality is at the group level and in the cases of semeais this is all
weak groups recursively adjacent to the group under attack... which in
the worst case is almost every legal move on the board...

Regards
Magnus
--
Magnus Persson
Center for Adaptive Behavior and Cognition
Tel: +49-(30)-82406-350
Cell phone: +49 163 6639868

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