[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]

Re: computer-go: Sharing Go modules

At 02:05 PM 5/17/2001 -0400, you wrote:


I use unit numbers too, but I do have 2 color  bits, one for white and
one for white, only  as an extra  convienence.  I'm happy to  see some
empirical evidence (the fact that a good programmer also uses it) that
the way I chose to represent my board is reasonable.

I am interested in what information  you keep per  unit.  I don't keep
much  right  now,  but  my list  has changed  from  time to  time with
different  versions.  But I'm focused  mainly  on very primitive basic
facts per unit:

     1.  Number of stones in unit.
     2.  A representive stone location. (can be any stone in unit)
     3.  Number of liberties for this unit.
     4.  Unit color

I'm only interested in  things that  can be incrementally  maintained,
otherwise I just compute from scratch when  I need it.   I feel that I
need more primitives in my unit structure.


Don

Here is all of it. I call units "groups", and use all one-dimensional arrays for speed. So rather than

struct {
int size;
etc.
} gr[NUMGROUPS];

and accessing with gr[index].size,
I have a grsize[NUMGROUPS] array and access it with grsize[index].

The syntax is only slightly different, but it's much faster :)

I use chars and shorts where I can, to keep the data smaller, to reduce cache misses.

grcolor, grlibs, grpieces, grlbp, grcnp, grnbp, grlv, grsize are incremental

/* group data structure */
char grcolor[NUMGROUPS]; /* color of group (grcolor[NOGROUP] is NOCOLOR)*/
unsigned char grlibs[NUMGROUPS]; /* number of liberties */
short grpieces[NUMGROUPS]; /* move stack index of first piece in group */

signed char gralprob[NUMGROUPS]; /* probability of living (-50 to 50) per group, as function of color to move. get in getalprob() */
int gralval[NUMGROUPS][2]; /* probability of living if I move first[0], enemy moves first[1] */
int groldalprob[NUMGROUPS];
int grsemval[NUMGROUPS]; /* win semeai prob for group */

char savegral[2][NUMGROUPS]; /* saved alive values */
char savevalid[2]; /* is the saved life data valid */
unsigned int savemove[2]; /* msptr value associated with saved life */
int gralvalid; /* are the gralive values valid */
unsigned char gralive[NUMGROUPS]; /* aliveness of group (0-25)
HERE DOWN ARE DEAD
25 - tactically captured unconditionally
24 - unused.
23 - Temp used for weak groups undecided yet
22 - No eyespace or potential and nbrs all alive
21 - probably dead some eye space or potential, nbrs alive
20 - in semeai loses
HERE DOWN ARE WEAK - PROBABLY WILL DIE
19 - no running ability, weak nbrs and some eye potential)
18 - can't run, lots of eye potential, only one eye
has aji to live, or can be used as ko threats
17 - in a semeai. behind - aji for later
16 - poor running ability - can't live in one move
HERE DOWN ARE UNSETTLED
15 - ko for life, must capture ko, then fill to live
14 - must run away to live - adjacent enemy groups settled
13 - in a semeai. unsettled
12 - surrounded, can live or die in one move
12 - would be alive, but tactically threatened
11 - running fight - have to run to live, and adjacent group also has to run
10 - ko for life, fill ko to live
9 - in a semeai. Ahead or temporary seki
8 - unsettled - can live in one move or limp away
HERE DOWN ARE ALIVE (or settled for now)
7 - can run away easily, no eyes
6 - can run away easily, one eye
needs two moves to make second eye
6 - can live in one move or run easily
5 - Alive because wins semeai
4 - at least a seki - may be actual seki, or temporary seki
3 - miai for barely space for two eyes (dangerous)
2 - barely territory for two eyes (dangerous)
HERE DOWN ARE VERY ALIVE
1 - miai for lots of eye space - 3 or more ways to make
second eye
1 - absolutely unconditionally alive - two small eyes
or lots of territory
0 - temporary value for newly created group
*/

unsigned char grthreatened[NUMGROUPS]; /* TRUE if group is tactically unsettled - */
/* 1 if captured if attacker wins all kos, and defender answers all atari threats */
/* 2 if unconditionally captured when attacker moves first, defender wins kos */
sqr_t grcapmove[NUMGROUPS]; /* move that captures threatened group */
sqr_t grsavemove[NUMGROUPS]; /* move that prevents group from being captured */
army_t groldarmy[NUMSQUARES]; /* old army value */
int grolddefv[NUMSQUARES]; /* value for defending old army here */
char groldalive[NUMSQUARES]; /* aliveness of group after opponent's last move and
before lookahead by square - 0 if there was no stone on that point. */
char groldrun[NUMSQUARES]; /* old running ability */
char groldthreatened[NUMSQUARES]; /* threatened before lookahead by square */
char grlastalive[NUMSQUARES]; /* aliveness of group before opponent's last move - 0 if no stone there */
/* set early in compmove */
char grlv[NUMGROUPS]; /* does group exist */
unsigned char grsize[NUMGROUPS]; /* number of stones in group */
list_t grlbp[NUMGROUPS]; /* liberty lists */
list_t grcnp[NUMGROUPS]; /* connection record lists */
list_t grnbp[NUMGROUPS]; /* enemy neighbor lists */
army_t grarmy[NUMGROUPS]; /* army number for group */
army_t grdeadarmy[NUMGROUPS]; /* army number in which this is dead group */
int grdefval[NUMGROUPS]; /* value of defending the army of which this is a member */
/* set in setdefvals and urgdefenough */
int gratkval[NUMGROUPS]; /* value of attacking the army of which this is a member */
/* set in setatkvals and urgatkenough */





David Fotland