bridgit.c

数据挖掘中的bridgit算法的例子。 非常经典

/*----------------------------------------------------------------------
  File    : bridgit.c
  Contents: bridg-it game with computer player
  Author  : Christian Borgelt
  History : 29.05.2001 file created
            03.06.2001 first version completed
----------------------------------------------------------------------*/
#include <stdio.h>
#include <stdlib.h>
#include <math.h>
#include <assert.h>
#include "vecops.h"
#include "bridgit.h"

/*----------------------------------------------------------------------
  Preprocessor Definitions
----------------------------------------------------------------------*/
#define EPSILON  1e-12         /* to handle roundoff errors */

/* compute resistor index from row and column coordinates */
#define bi_index(b,c,r) (((c) & 1) \
                        ? (((r)/2)   * (b)->size    +((c)/2))  \
                        : (((r)/2-1) *((b)->size-1) +((c)/2-1) \
                           + (b)->size * (b)->size))

/* check whether point given by row and column is a proper crossing */
#define bi_cross(b,c,r) (  ((c) > 0) && ((c) <= 2 *(b)->size) \
                        && ((r) > 0) && ((r) <= 2 *(b)->size) \
                        && !(((r) + (c)) & 1))

/*----------------------------------------------------------------------
  Auxiliary Functions
----------------------------------------------------------------------*/

static int ccmp (const void *i1, const void *i2, void *vec)
{                              /* --- comparison of currents */
  double c1, c2;               /* currents to compare */

  c1 = ((const double*)vec)[(int)i1];
  c2 = ((const double*)vec)[(int)i2];
  if     (c1 > c2 +EPSILON) return 1; /* return the sign of the diff. */
  return (c1 < c2 -EPSILON) ? -1 : 0; /* of the two currents */
}  /* ccmp() */                       

/*----------------------------------------------------------------------
  Main Functions
----------------------------------------------------------------------*/

BRIDGIT* bi_create (int size)
{                               /* --- create a bridg-it game */
  int     n, nl, nc;            /* numbers of resistors */
  BRIDGIT *bi;                  /* created bridg-it game */

  assert((size >= BI_MINSIZE)   /* check size against minimum */
      && (size <= BI_MAXSIZE)); /* and maximum board size */
  nl =  size    * size;         /* number of longitudinal resistors */
  nc = (size-1) *(size-1);      /* number of crossway     resistors */
  n  = nl +nc;                  /* total number of resistors */
  bi = (BRIDGIT*)malloc(sizeof(BRIDGIT) +(3*n -1) *sizeof(int));
  if (!bi) return NULL;         /* create the base structure */
  bi->size   = size;            /* and note the number of points */
  bi->ptcnt  = n;
  bi->states = bi->moves  +n;   /* organize the different vectors */
  bi->buf    = bi->states +n;
  bi->vert   = mat_create(n,n);
  bi->horz   = mat_create(n,n); /* create matrices and vectors */
  bi->tmp    = mat_create(n,n); /* for the current equations */
  bi->vec    = (double*)malloc(n *sizeof(double));
  bi->sol    = (double*)malloc(n *sizeof(double));
  if (!bi->horz || !bi->vert || !bi->tmp || !bi->vec || !bi->sol) {
    bi_delete(bi); return NULL; }
  return bi;                    /* return the created bridg-it game */
}  /* bi_create() */

/*--------------------------------------------------------------------*/

void bi_delete (BRIDGIT *bi)
{                               /* --- delete a bridg-it game */
  assert(bi);                   /* check the function arguments */
  if (bi->sol)  free(bi->sol);
  if (bi->vec)  free(bi->vec);
  if (bi->tmp)  mat_delete(bi->tmp);
  if (bi->vert) mat_delete(bi->vert);
  if (bi->horz) mat_delete(bi->horz);
  free(bi);                     /* delete the matrix, the vectors, */
}  /* bi_delete() */            /* and the base structure */

/*--------------------------------------------------------------------*/

void bi_init (BRIDGIT *bi)
{                               /* --- initialize a bridg-it game */
  int x, y, r = 0;              /* loop variables, index */
  int size;                     /* number of points on the panels */
  int nl, nc;                   /* number of long./cross. resistors */
  int ol, oc;                   /* offsets for resistor indices */

  assert(bi);                   /* check the function arguments */
  size = bi->size;              /* get the number of points and the */
  nl   =  size    * size;       /* numbers of long./cross. resistors */
  nc   = (size-1) *(size-1);    /* init. the matrices and the vector */
  vec_init(bi->vec, nl +nc, nl +nc -1);   
  mat_init(bi->horz, MAT_ZERO, NULL);
  mat_init(bi->vert, MAT_ZERO, NULL);

  /* --- horizontal mesh equations / vertical node equations --- */
  ol = nl; oc = nl +nc;         /* traverse the network rows */
  for (y = size-1; --y >= 0; ){ /* and the columns of each row */
    ol -= size; oc -= size-1;   /* and set the coefficients */
    for (x = size; --x >= 0; r++) {
      mat_set(bi->horz, r, ol +x -size, -1);
      mat_set(bi->vert, r, ol +x -size,  1);
      mat_set(bi->horz, r, ol +x,        1);
      mat_set(bi->vert, r, ol +x,       -1);
      if (x > 0)      { mat_set(bi->horz, r, oc +x-1,  1);
                        mat_set(bi->vert, r, oc +x-1,  1); }
      if (x < size-1) { mat_set(bi->horz, r, oc +x,   -1);
                        mat_set(bi->vert, r, oc +x,   -1); }
    }                           /* (do not set fourth coefficient */
  }                             /* for first/last network column) */

  /* --- horizontal node equations / vertical mesh equations --- */
  ol = nl; oc = nl +nc;         /* traverse the network rows */
  for (y = size; --y >= 0; ) {  /* and the columns of each row */
    ol -= size; oc -= size-1;   /* and set the coefficients */
    for (x = size-1; --x >= 0; r++) {
      mat_set(bi->horz, r, ol +x,     1);
      mat_set(bi->vert, r, ol +x,     1);
      mat_set(bi->horz, r, ol +x +1, -1);
      mat_set(bi->vert, r, ol +x +1, -1);
      if (y > 0)      { mat_set(bi->horz, r, oc +x,          1);
                        mat_set(bi->vert, r, oc +x,         -1); }
      if (y < size-1) { mat_set(bi->horz, r, oc +x +size-1, -1);
                        mat_set(bi->vert, r, oc +x +size-1,  1); }
    }                           /* (do not set fourth coefficient */
  }                             /* for first/last network row) */

  /* --- boundary equations --- */
  for (ol = nl -size, y = size; --y >= 0; ol -= size)
    mat_set(bi->horz, r, ol, 1);/* horizontal network */
  for (x = size; --x >= 0; )
    mat_set(bi->vert, r, x,  1);/* vertical   network */

  /* --- other initializations --- */
  bi->mvcnt = bi->curr = 0;     /* clear the number of moves */
  for (x = nl +nc; --x >= 0; )  /* and the state vector */
    bi->states[x] = BI_NONE;    /* (no bridges built yet) */
}  /* bi_init() */

/*----------------------------------------------------------------------
The resistors (or, what is the same, the crossing points) are numbered
from left to right in each row, and from top to bottom over the rows.
For the horizontal network, the horizontal resistors are numbered first,
the vertical resistors after all horizontal ones have been numbered.
For the vertical network it is the other way round (vertical resistors
are numbered before horizontal ones). In this way resistors that
correspond to the same crossing point have the same numbers.
The currents always flow from left to right and from top to bottom.
----------------------------------------------------------------------*/

int bi_hint (BRIDGIT *bi, int player, double randfn (void))
{                               /* --- give a hint for a player */
  int    i, k;                  /* loop variables */
  MATRIX *mat;                  /* matrix of the system to solve */
  int    col, row;              /* row and column of bridge */

  assert(bi && randfn           /* check the function arguments */
      && ((player == BI_HORZ) || (player == BI_VERT)));
  mat = (player & BI_HORZ)      /* get the corresponding matrix */
      ? bi->horz : bi->vert;    /* and solve the equation system */
  #if 0
  mat_gjsol(&bi->sol, mat, &bi->vec, 1, MAT_FULLPIV, NULL);
  #endif                        /* solve directly with Gauss alg. */
  #if 0
  mat_gjinv(bi->tmp, mat, MAT_FULLPIV, NULL);
  mat_mulmv(bi->sol, bi->tmp, bi->vec);
  #endif                        /* solve by multiplying with inverse */
  #if 1
  mat_ludecom(bi->tmp, mat);    /* decompose the coefficient matrix */
  mat_lusubst(bi->sol, bi->tmp, bi->vec);
  #endif                        /* do forward/backward substitution */
  for (i = bi->ptcnt; --i >= 0; ) {
    bi->sol[i] = fabs(bi->sol[i]);
    bi->buf[i] = i;             /* make all currents positive */
  }                             /* and initialize the index vector */
  for (i = bi->curr; --i >= 0; ) {
    k = bi->moves[i];           /* traverse the moves of the opponent */
    if (k & player) continue;   /* (i.e., the blocked connections) */
    k = bi_index(bi, bi_col(k), bi_row(k));
    if (bi->sol[k] > 1e-5)      /* a non-negligible current through */
      return BI_NONE;           /* a blocked connection indicates */
  }                             /* that the game has been lost */
  v_shuffle(bi->buf, bi->ptcnt, randfn);     /* shuffle and then */
  v_sort(bi->buf, bi->ptcnt, ccmp, bi->sol); /* sort the resistors */
  for (k = bi->ptcnt; --k >= 0; ) {
    if (bi->states[bi->buf[k]] == BI_NONE)
      break;                    /* traverse the resistors/crossings */
  }                             /* and find one without a bridge */
  if (k < 0) return BI_NONE;    /* check whether one was found and */
  k = bi->buf[k];               /* get the resistor/crossing index */
  i = bi->size *bi->size;       /* get number of long. resistors */
  if (k < i) {                  /* if longitudinal resistor */
    col =  (k    %  bi->size)    *2 +1;
    row =  (k    /  bi->size)    *2 +1; }
  else {                        /* if crossway resistor */
    col = ((k-i) % (bi->size-1)) *2 +2;
    row = ((k-i) / (bi->size-1)) *2 +2;
  }                             /* get coordinates of crossing point */
  return bi_bridge(player & (BI_VERT|BI_HORZ), col, row);
}  /* bi_hint() */              /* return the corresponding bridge */

/*--------------------------------------------------------------------*/

void bi_build (BRIDGIT *bi, int bridge)
{                               /* --- build a bridge */
  int    i, n, r;               /* loop variables, resistor index */
  int    col, row;              /* coordinates of crossing point */
  double h, v, o;               /* new and old resistor values */

  assert(bi);                   /* check the function arguments */
  col = bi_col(bridge);         /* get the coordinates */
  row = bi_row(bridge);         /* of the crossing point */
  assert(bi_cross(bi,col,row)); /* check for a correct crossing point */
  if ((bi->mvcnt <= bi->curr)   /* if the bridge is not rebuilt */