RE: [computer-go] RE: Scalability

["David Fotland" <fotland@xxxxxxxxxxxxxxx>]

Many Faces does local replies, where local means either a local shape, from
a pattern, or reversing a change in group status (where the group is
unsettled), anywhere on the board.  So a ladder breaker has a "local" effect
on the ladder on the other side of the board.  So if a move casues a living
group to become unsettled, it will generate quiescence moves to make the
unsettled group live again.

David

> -----Original Message-----
> From: computer-go-bounces@xxxxxxxxxxxxxxxxx 
> [mailto:computer-go-bounces@xxxxxxxxxxxxxxxxx] On Behalf Of 
> Persson, Magnus
> Sent: Tuesday, January 18, 2005 1:58 PM
> To: computer-go@xxxxxxxxxxxxxxxxx
> Subject: [computer-go] RE: Scalability
> 
> 
> 
> 
> > -----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/
> 


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