[computer-go] Territory Computation

["Jean-Charles" <jean-charles.pouplard@xxxxxxxxxx>]

Hello,

 just for fun, I've implemented the territory computation as described in 
Bouzy's article "Mathematical Morphology applied to computer Go" (see 
http://www.math-info.univ-paris5.fr/~bouzy/publications.html for more 
details). Because I've spent some time to understand the algorithm and clean 
up Bouzy's code, I'm just offering this "standalone" implementation to 
anybody who could find some interest in such a code.

Regards

 Jean-Charles

#include <iostream>
#include <time.h>
#include <memory.h>

using namespace std;

#define BOARD_SIZE  19
#define GOBAN_SIZE  BOARD_SIZE * BOARD_SIZE

static const int goban[ GOBAN_SIZE ] =
{
 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
 0, 0,-1,-1, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
 0, 0,-1, 1, 0, 1, 0, 0, 0, 1, 0,-1, 0,-1, 0, 0,-1, 0, 0,
 0, 0,-1, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,-1, 0, 1, 0,
 0,-1, 1, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0,
 0,-1, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0,
 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0,
 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
 0, 0,-1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0,
 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
 0, 0,-1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,-1, 0, 0,
 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,-1, 0, 0,
 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,-1,-1, 1, 1, 0,
 0, 0, 0, 0, 1, 0,-1, 0, 0,-1, 0, 0, 0, 0,-1, 1, 0, 0, 0,
 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,-1, 1, 1, 0, 0, 0,
 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
};

static int NEIGHBORS[ GOBAN_SIZE ][ 4 ];

// ----------------------------------------------------------------------------
struct Potential
// ----------------------------------------------------------------------------
{
 static int buffer_nature[ GOBAN_SIZE ];
 static int nature       [ GOBAN_SIZE ];
 static int intensity    [ GOBAN_SIZE ];

 static void copy();
 static void dilate_z( int count );
 static void dilate_z_element(int);
 static void erase_z( int count );
 static void erase_z_element(int);
};

// ----------------------------------------------------------------------------
// static data
// ----------------------------------------------------------------------------
int Potential::buffer_nature   [ GOBAN_SIZE ] = { 0 };
int Potential::nature          [ GOBAN_SIZE ] = { 0 };
int Potential::intensity       [ GOBAN_SIZE ] = { 0 };

// ----------------------------------------------------------------------------
void Potential::copy()
// ----------------------------------------------------------------------------
{
 memcpy( buffer_nature, nature, sizeof( buffer_nature ));
}

// ----------------------------------------------------------------------------
void Potential::dilate_z( int count )
// ----------------------------------------------------------------------------
{
 while ( count-- )
 {
   copy();
   for (int position = 0; position < GOBAN_SIZE; position++ )
   {
     dilate_z_element( position );
   }
 }
}

// ----------------------------------------------------------------------------
void Potential::dilate_z_element( int point )
// ----------------------------------------------------------------------------
{
 int ma_nature = buffer_nature[ point ];
 int direction;
 int voisin;

 for ( direction = 3; direction >= 0; direction-- )
 {
   voisin = NEIGHBORS[ point][ direction ];

   if ( voisin                  != -1       &&
        buffer_nature[ voisin ] &&
        buffer_nature[ voisin ] != ma_nature )
   {
     if ( ma_nature )
       return;
     else
       ma_nature = buffer_nature[ voisin ];
   }
 }

 if ( !ma_nature )
   return;

 nature[ point ] = ma_nature;

 for (direction = 3; direction >= 0; direction--)
 {
   voisin = NEIGHBORS[ point ][ direction ];

   if ( voisin                  != -1       &&
        buffer_nature[ voisin ] == ma_nature )
   {
     intensity[ point ]++;
   }
 }
}

// ----------------------------------------------------------------------------
void Potential::erase_z( int count )
// ----------------------------------------------------------------------------
{
 while ( count-- )
 {
   copy();
   for (int idx=0; idx < GOBAN_SIZE; idx++) erase_z_element(idx);
 }
}

// ----------------------------------------------------------------------------
void Potential::erase_z_element( int point )
// ----------------------------------------------------------------------------
{
 int ma_nature = buffer_nature[ point ];
 int voisin;

 if ( ma_nature == 0 )
   return;

 for ( int direction = 3; direction >= 0; direction--)
 {
   voisin = NEIGHBORS[ point ][ direction ];

   if ( voisin                  != -1       &&
        buffer_nature[ voisin ] != ma_nature )
   {
     if ( !--intensity[ point ] )
     {
       nature[ point ] = 0;
       break;
     }
   }
 }
}

// ----------------------------------------------------------------------------
void dump( const int array[] )
// ----------------------------------------------------------------------------
{
 for ( int i = 0; i < BOARD_SIZE; i++ )
 {
   for ( int j= 0; j < BOARD_SIZE; j++ )
   {
     cout.width( 3 );
     cout << array[ i*BOARD_SIZE + j ];
   }
   cout << endl;
 }

 cout << endl;
}

// ----------------------------------------------------------------------------
void dump( const int nature   [] ,
          const int intensity[] ,
          int   mode = 0        )
// ----------------------------------------------------------------------------
{
 int tmp;

 for ( int i = 0; i < BOARD_SIZE; i++ )
 {
   for ( int j= 0; j < BOARD_SIZE; j++ )
   {
     tmp = nature   [ i*BOARD_SIZE + j ] * intensity[ i*BOARD_SIZE + j ] ;

     switch( mode ) {
     case 1:
       if ( tmp <  0 ) cout << "W ";
       if ( tmp >  0 ) cout << "B ";
       if ( tmp == 0 ) cout << ". ";
       break;
     default:
       cout.width( 4 );
       cout << tmp;
       break;
     }
   }
   cout << endl;
 }

 cout << endl;
}

// ----------------------------------------------------------------------------
void initializeTerritories()
// ----------------------------------------------------------------------------
{
 for ( int i = 0; i < GOBAN_SIZE; i++ )
 {
   switch( goban[ i ] )
   {
   case 1:
     Potential::nature   [ i ] = 1;
     Potential::intensity[ i ] = 64;
     break;
   case -1:
     Potential::nature   [ i ] = -1;
     Potential::intensity[ i ] = 64;
     break;
   default:
     Potential::nature   [ i ] = 0;
     Potential::intensity[ i ] = 0;
     break;

   }
 }
}

// ----------------------------------------------------------------------------
static void initializeNeighbors()
// ----------------------------------------------------------------------------
{
 enum { NORTH = 0 ,
        EAST  = 1 ,
        SOUTH = 2 ,
        WEST  = 3 };

 for ( int i = 0; i < GOBAN_SIZE; i++ )
 {
   for ( int j = 0; j < 4; j++ )
   {
     switch ( j )
     {

     case NORTH:
       if ( i < BOARD_SIZE )
         NEIGHBORS[ i ][ j ] = -1;
       else
         NEIGHBORS[ i ][ j ] = i - BOARD_SIZE;
       break;

     case EAST:
       if ( ( i + 1 ) % BOARD_SIZE == 0 )
         NEIGHBORS[ i ][ j ] = -1;
       else
         NEIGHBORS[ i ][ j ] = i + 1;
       break;

     case SOUTH:
       if ( i >= GOBAN_SIZE - BOARD_SIZE )
         NEIGHBORS[ i ][ j ] = -1;
       else
         NEIGHBORS[ i ][ j ] = i + BOARD_SIZE;
       break;

     case WEST:
       if ( i % BOARD_SIZE == 0 )
         NEIGHBORS[ i ][ j ] = -1;
       else
         NEIGHBORS[ i ][ j ] = i - 1;
       break;

     }
   }
 }
}

// ----------------------------------------------------------------------------
int main( int, char ** )
// ----------------------------------------------------------------------------
{
 static int const d = 4;
 static int const e = d*(d-1) + 1;

 initializeTerritories();
 initializeNeighbors  ();

 dump( goban );

 Potential::dilate_z( d );
 Potential::erase_z ( e );

 dump( Potential::nature, Potential::intensity, 0 );

 return 0;
}







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