[Computer-go] Computing CFG distance in practice

[Brian Sheppard]

I use CFG distance only in the tree. The playout uses the concept "adjacent"
which is trivial to compute.

The only distance I am concerned about is the distance to the last move, and
there are only 4 classes: distance 1,2,3, and >3. So it is cheap.

The advantage is in semeais. Moves at CFG distance 3 are the outside
liberties of the opponent's string.

There was not a big difference compared to the other two heuristics. I found
that

- CFG is best
- max(dx, dy) + (dx + dy)/2 is second best
- Manhattan is third.

Brian

-----Original Message-----
From: computer-go-bounces at dvandva.org
[mailto:computer-go-bounces at dvandva.org] On Behalf Of Jacques Basaldúa
Sent: Monday, January 24, 2011 2:41 PM
To: computer-go at dvandva.org
Subject: [Computer-go] Computing CFG distance in practice

Hi,

I got a lot of improvement recently (something you all
did long time ago) with proximity heuristics. I am using

Manhattan distance:
   d = max(dx, dy)

and
   d = max(dx, dy) + (dx + dy)/2

where dx = abs(ex - ox) and dy = abs(ey - oy)

But many people report CFG distance to be superior.

What do you do:

a. Compute it in root. Then build a lookup table and
use the LUT during playouts and tree search.

b. Compute the shortest path from (ox, oy) to (ex, ey)
connected by the stones on the board each time you need
to evaluate a distance.

I don't like a because it looks inefficient as the
board changes a lot during the search.

I don't like b because it looks computing intense
unless there is some smart idea I am missing.


Jacques.







_______________________________________________
Computer-go mailing list
Computer-go at dvandva.org
http://dvandva.org/cgi-bin/mailman/listinfo/computer-go