囲碁プログラムの作り方(上級編)

2002年12月27日:初版
2004年6月18日:加筆、修正

はじめに

初級編で囲碁プログラムの簡単な思考ルーチンを解説し、中級編で思考ルーチンのうちの盤面認識の改良を行ないました。今回は、思考ルーチンのうちの候補手生成部分の改良を行ないます。

候補手生成の改良

囲碁は、自殺手や劫による着手禁止点を除けば、盤面上の空点はすべて着手可能です。ですから、着手可能な点はすべて候補手として良いのですが、それでは効率が悪すぎます。なぜなら、生成した候補手の中から最善手を選ぶためには、すべての候補手を評価しなければならないからです。明らかに候補手としてふさわしくない手に対して評価をするのは時間の無駄でしょう。そこで、良い手しか思い浮かばない（候補手としない）ようなプログラムを作りましょう。

人間はどのような手を候補手としているでしょうか。相手の石を取る手、模様を広げる手、定石の手など、いろいろな知識や探索（先読み）の結果から、候補手を生成していることがわかります。多くの囲碁プログラムでも同じように候補手を生成しています。

局所的な探索の結果から候補手の生成
石を取る手や取られないように逃げる手、石と石がつながる手や切る手は、局所的な探索の結果から生成します。
パターン(データベース)から候補手の生成
定石や手筋の手を生成するために、石の配置と候補手の位置を記述したパターンの　　　データベースを用意します。
その他の方法からの候補手の生成
布石の手や模様の手などは、石の強さや距離をもとに候補手の位置を決めています。　　　このような手を求めるためのアルゴリズムを用意します。

局所的な探索の結果から候補手の生成

石を取る手や取られないように逃げる手、石と石がつながる手や切る手は、局所的な探索の結果から生成します。
中級編で、盤面の認識のときに石の生死や連結については探索が必要であると説明しました。この探索のときに、どこに打てば石を取れるのか、逃げられるのか、石がつながるのか、切れるのかを覚えておけば、そのまま候補手として使えます。

盤面              白を取る手        白が逃げる手
┼┼┼┼┼┼┼    ┼┼┼┼┼┼┼    ┼┼┼┼┼┼┼
┼┼●●●┼┼    ┼┼●●●┼┼    ┼┼●●●┼┼
┼●○○┼●┼    ┼●○○Ａ●┼    ┼●○○┼●┼
┼┼●┼┼○○    ┼┼●ＢＣ○○    ┼┼●┼Ａ○○
┼●┼●┼┼┼    ┼●┼●┼┼┼    ┼●┼●┼┼┼
┼┼┼┼┼┼┼    ┼┼┼┼┼┼┼    ┼┼┼┼┼┼┼

パターン(データベース)から候補手の生成

定石や手筋の手を生成するために、石の配置と候補手の位置を記述したパターンを用意します。このパターンを集めたもの(データベース)は、プログラムのための定石事典や手筋事典なのです。
もっとも簡単なパターンは、石の配置と、そのときの候補手の位置と、手番を組とするデータの集合です。対局中に常に盤面とパターンを比べて、同じ手番で同じ石の配置が現れたら、そのパターンに書かれている候補手の位置をプログラムの候補手とします。

データの例（×は黒番の候補手）
┼┼┼┼┼      ┼●┼┼┼
┼┼○┼┼      ┼┼┼┼┼
┼○●×┼      ┼┼×┼┼
┼┼┼┼┼      ┼○┼┼┼
┼●┼●┼      ┼┼┼●┼

対局中の盤面
┏┯┯┯┯┯┯┯┯┯┯┯┯┯┯┯┯┯┓
┠┼┼┼┼┼┼┼┼┼┼┼┼┼┼┼┼┼┨
┠○●●┼┼┼┼●┼┼┼┼┼┼┼┼┼┨
┠┼○┼●┼┼┼┼┼┼┼┼●┼●┼┼┨  黒番ならば
┠○┼┼┼┼┼┼┼┼┼┼┼┼┼┼┼┼┨  右のデータから
┠┼┼○┼┼┼┼┼┼┼┼┼┼○┼○┼┨  Ａが候補手として
┠┼┼┼┼┼┼┼┼┼┼┼┼┼┼┼┼┼┨  生成される
┠┼┼┼┼┼┼┼┼┼┼┼┼┼Ｂ○●┼┨
┠┼┼┼┼┼┼┼┼┼┼┼┼┼┼●┼┼┨
┠┼○┼┼┼┼┼┼┼┼┼┼┼┼┼┼┼┨  白番ならば
┠┼┼┼┼┼┼┼┼┼┼┼┼┼┼┼┼┼┨  左のデータから
┠┼○┼●┼┼┼┼┼┼┼┼┼┼┼┼┼┨  Ｂが候補手として
┠┼┼┼┼┼┼┼┼┼┼┼┼┼┼┼┼┼┨  生成される
┠┼○┼┼Ａ┼┼┼┼┼┼┼┼┼┼┼┼┨
┠┼┼┼○┼┼┼┼┼┼┼┼┼┼┼●┼┨
┠┼┼┼┼┼●┼┼┼┼┼┼┼┼┼┼┼┨
┠┼┼┼○┼┼┼┼┼●┼┼┼┼●┼┼┨
┠┼┼┼┼┼┼┼┼┼┼┼┼┼┼┼┼┼┨
┗┷┷┷┷┷┷┷┷┷┷┷┷┷┷┷┷┷┛

ここで注意することが二つあります。

一つは、色の反転です。データには黒番の候補手位置しか書かれていませんが、白番でもその候補手を生成できなくてはいけません。そこで、データに書かれている石の色を反転（黒を白に、白を黒に）して、盤面と比較するのです。そうしないと、右上のＢの候補手が生成されません。

もう一つは、対称形の判定です。盤面の右上と、候補手Ｂをの元となった左のデータを見比べて下さい。色が反転しているだけでなく、向きも異なっているのがわかるでしょう。このように、データと同じ形だけど向きが違う場合も候補手にしなければいけません。対称形は全部で8種類あります（以下の図）。

そのまま　    ９０度回転    １８０度回転　２７０度回転
┼┼┼┼┼　　┼┼┼┼┼　　┼●┼●┼　　┼┼┼┼┼
┼┼○┼┼　　┼┼×┼●　　┼┼┼┼┼　　●┼○┼┼
┼○●×┼　　┼○●┼┼　　┼×●○┼　　┼┼●○┼
┼┼┼┼┼　　┼┼○┼●　　┼┼○┼┼　　●┼×┼┼
┼●┼●┼　　┼┼┼┼┼　　┼┼┼┼┼　　┼┼┼┼┼

上下が逆　　　９０度回転    １８０度回転　２７０度回転
┼●┼●┼　　┼┼┼┼┼　　┼┼┼┼┼　　┼┼┼┼┼
┼┼┼┼┼　　●┼×┼┼　　┼┼○┼┼　　┼┼○┼●
┼○●×┼　　┼┼●○┼　　┼×●○┼　　┼○●┼┼
┼┼○┼┼　　●┼○┼┼　　┼┼┼┼┼　　┼┼×┼●
┼┼┼┼┼　　┼┼┼┼┼　　┼●┼●┼　　┼┼┼┼┼

対称形を作るためには、座標の変換作業を行わなければいけません。通常は行列演算を使いますが、ここでの説明は省略します。

候補手生成のためのパターンマッチングは次のようになります。

for( すべての座標 ){

    /* (1) 盤面から(x,y)を含む５×５の形を切り出す */

    /* (2) 白番ならば白黒を反転する（黒番ならばそのまま） */

    for( i=0; i < データ数; i++ ){

        /* (3) データから８種類の対称形を作る */

        /* (4) データと切り出した５×５を比較する */

        /* (4.1) もし一致したら、データに書かれている候補手位置を覚える */

    }
}

ここでは、データを５×５の正方形として説明しましたが、もちろん正方形にする必要はありませんし、もっと大きくても（小さくても）かまいません。また、盤の端の方のデータを書きたいときのために、黒、白、空点だけでなく、盤外という表記もできた方が便利です。さらに、「黒または空点」というような点を記述できると、データが書きやすいでしょう。ここは、みなさんがいろいろと工夫して下さい。

盤の端に打つ手の例（＃は盤外）

サルスベリ    三三への打ち込み
　　　　　    ＃┼┼┼○
●○○○○    ＃┼┼×┼
●┼┼┼┼    ＃┼┼┼┼
┼┼┼×┼    ＃┼┼┼┼
＃＃＃＃＃    ＃＃＃＃＃

データのプログラム例

データは構造体を使って書きます。

/* 色 */
#define SPACE 0            /* 空点 */
#define BLACK 1            /* 黒   */
#define WHITE 2            /* 白   */
#define OUT   3            /* 盤外 */

/* データ */
struct go_data {
  int x;                   /* 候補手のＸ座標 */
  int y;                   /* 候補手のＹ座標 */
  int data[5][5];          /* 石の配置       */
};

/* 黒番の候補手のデータベース */
static struct pattern_data patternData[] =
{
/* 例の左のデータ */
{ 3,                                   /* 候補手のＸ座標 */
  2,                                   /* 候補手のＹ座標 */                                   /* 候補手の座標 */
 {{ SPACE, SPACE, SPACE, SPACE, SPACE },   /* ┼┼┼┼┼ */
  { SPACE, SPACE, WHITE, SPACE, SPACE },   /* ┼┼○┼┼ */
  { SPACE, WHITE, BLACK, SPACE, SPACE },   /* ┼○●×┼ */
  { SPACE, SPACE, SPACE, SPACE, SPACE },   /* ┼┼┼┼┼ */
  { SPACE, BLACK, SPACE, BLACK, SPACE }}}, /* ┼●┼●┼ */
/* 例の右のデータ */
{ 2,                                   /* 候補手のＸ座標 */
  2,                                   /* 候補手のＹ座標 */                                   /* 候補手の座標 */
 {{ SPACE, BLACK, SPACE, SPACE, SPACE },   /* ┼●┼┼┼ */
  { SPACE, SPACE, SPACE, SPACE, SPACE },   /* ┼┼┼┼┼ */
  { SPACE, SPACE, SPACE, SPACE, SPACE },   /* ┼┼×┼┼ */
  { SPACE, WHITE, SPACE, SPACE, SPACE },   /* ┼○┼┼┼ */
  { SPACE, SPACE, SPACE, BLACK, SPACE }}}  /* ┼┼┼●┼ */

その他の方法からの候補手の生成

布石の手や模様の手も、データベースをから生成することができますが、予めデータベースを作るのが大変手間がかかります。なぜなら、布石や模様の手は、広い範囲の石の配置を考慮しなければいけないので、データを列挙するのが大変なのです。勿論、典型的なデータのみをデータベースにするという方法はありますが、ここでは、それ以外の方法について一例を紹介します。

囲碁において相手の模様を抑制する手の位置として好ましいものは、「相手の模様の先端を結んだ線上の中央に打つ手」と言われています。このような手は、石の座標から計算して求めることが可能です。
例えば下の図では、右下の黒の模様の先端の石は(13,10)と(11,17)です。この２つの座標の中央は((13+10)/2,(10+17)/2)なので、白の候補手は(12,13)と(12,14)になります。

┏┯┯┯┯┯┯┯┯┯┯┯┯┯┯┯┯┯┓
┠┼┼┼┼┼┼┼┼┼┼┼┼┼┼┼┼┼┨
┠○●●┼┼┼┼●┼┼┼┼┼┼┼┼┼┨
┠┼○┼●┼┼┼┼┼┼┼┼●┼●●●┨
┠○┼┼┼┼┼┼┼┼┼┼┼┼┼┼┼○┨
┠┼┼○┼┼┼┼┼┼┼┼┼┼○┼○┼┨
┠┼┼┼┼┼┼┼┼┼┼┼┼┼┼┼○┼┨
┠┼┼┼┼┼┼┼┼┼┼┼┼○○○●○┨
┠┼┼┼┼┼┼┼┼┼┼┼┼┼●●●●┨
┠┼┼┼┼┼┼┼┼┼┼┼●┼┼┼┼┼┨  <-- (13,10)が模様の先端
┠┼○┼┼┼┼┼┼┼┼┼┼┼┼┼┼┼┨
┠┼┼┼┼┼┼┼┼┼┼┼┼┼┼┼┼┼┨
┠┼┼┼┼┼┼┼┼┼┼Ａ┼┼┼┼┼┼┨  <-- (12,13)は模様を抑制する手
┠┼┼┼┼┼┼┼┼┼┼Ｂ┼┼┼┼┼┼┨  <-- (12,14)は模様を抑制する手
┠┼┼○┼┼┼┼┼┼┼┼┼┼┼┼●┼┨
┠┼┼┼┼┼┼┼┼┼┼┼┼┼┼┼┼┼┨
┠┼┼○┼┼┼○┼┼●┼┼┼┼●┼┼┨  <-- (11,17)が模様の先端
┠┼┼┼┼┼┼┼┼┼┼┼┼┼┼┼┼┼┨
┗┷┷┷┷┷┷┷┷┷┷┷┷┷┷┷┷┷┛

負の候補手

ここまでは、候補手としてふさわしい点を求める処理について説明しました。ここではその全く逆の、候補手としてふさわしくない点（打ってはいけない悪い点）を求める処理について説明します。説明の便宜上、今まで説明してきた候補手を「正の候補手」、候補手としてふさわしくない点を「負の候補手」と呼びます。
負の候補手の例は、愚形を作る点（囲碁用語でアキ三角など）やダメ詰まりになる点、などです。
これらの負の候補手は、もしも正の候補手として生成されても、打たない方が良いでしょう。

┼┼┼┼┼┼┼    黒石がシチョウで取られとき、
┼┼┼┼┼┼┼    黒は取られないように逃げる手を生成します。
┼┼┼Ａ┼┼┼    図のＡに打てば、シチョウになりませんが、
┼○●●○┼┼    愚形なので、上手な人は打たないでしょう。
┼┼○○○┼┼    このような点Ａが、負の候補手です。

実現方法はいろいろありますが、正の候補手と同様に、負の候補手もパターンのデータベースから生成すると作るのが簡単です。盤面から切り出して、比較するところまで、全く同じアルゴリズムが使えるからです。

パターンから候補手を生成するプログラムのサンプル

このプログラムは、"figure"という名前のファイルを読んで、次の一手を返すプログラムです。 "figure"というファイルには、次の一手を求めたい盤面を描いておきます。

"figure"の例
+++++++++++++++++++
+++++++++++++++++++
+O**++++*++++++++++
++O+*++++++++*+*+++
+O+++++++++++++++++
+++O++++++++++O+O++
+++++++++++++++++++
+++++++++++++++O*++
+++++++++++++++*+++
++O++++++++++++++++
+++++++++++++++++++
++O+*++++++++++++++
+++++++++++++++++++
++O++++++++++++++++
++++O+++++++++++*++
++++++*++++++++++++
++++O+++++*++++*+++
+++++++++++++++++++
+++++++++++++++++++

/*----------------------------------------*/
/* パターンから候補手を生成するプログラム */
/*----------------------------------------*/

#include <stdio.h>
#include <string.h>

#define TRUE 1
#define FALSE 0

#define SPACE 0            /* 空点(石が置かれていない) */
#define BLACK 1            /* 黒   */
#define WHITE 2            /* 白   */
#define OUT   3            /* 盤外 */

#define BOARD_SIZE 21                       /* 碁盤の大きさ */
#define PURE_BOARD_SIZE (BOARD_SIZE-2)      /* 本当の碁盤の大きさ */


#define PATTERN_SIZE 5  /* パターンのサイズ */

struct pattern_data {
  int x;                   /* 候補手のＸ座標 */
  int y;                   /* 候補手のＹ座標 */
  int data[PATTERN_SIZE][PATTERN_SIZE];  /* 石の配置       */
};

/* 相手の色 */
#define reverseColor( color ) ( color == BLACK ? WHITE : ( color == WHITE ? BLACK : color ) )

/* 回転方向 */
#define ROTATE_000  0           /* そのまま              */
#define ROTATE_090  1           /* ９０度回転            */
#define ROTATE_180  2           /* １８０度回転          */
#define ROTATE_270  3           /* ２７０度回転          */
#define ROTATE_M000 4           /* 上下が逆              */
#define ROTATE_M090 5           /* 上下が逆 ９０度回転   */
#define ROTATE_M180 6           /* 上下が逆 １８０度回転 */
#define ROTATE_M270 7           /* 上下が逆 ２７０度回転 */


/*------------------------------------------------------------------*/
/* 関数                                                             */
/*------------------------------------------------------------------*/

/* メイン関数 */
int main( int argc, char *argv[] );

/* 盤面図入力 */
static void InputFigure( int board[][BOARD_SIZE] );       

/* 碁盤の初期化 */
static void InitializeBoard( int board[][BOARD_SIZE] );

/* 碁盤を表示する */
static void DisplayBoard( int board[][BOARD_SIZE] );

/* データベースから候補手の生成 */
static void MakePatternCandidates( int turn, int board[][BOARD_SIZE], int evalBoard[][BOARD_SIZE] );

/* ボードからパターンを切り出す */
static void GetPatternFromBoard( int board[][BOARD_SIZE], struct pattern_data *pattern, int x, int y );

/* パターンの白黒反転 */
static void ReverseColorPattern(struct pattern_data *pattern);

/* パターンの回転 */
static void RotatePattern(struct pattern_data *from, struct pattern_data *to, int type);

/* 候補手の認識 */
static int  ClassificationPatternCandidates( int board[][BOARD_SIZE], int x, int y,
                                             int color, int number );

/* 候補手の表示 */
static void DisplayPatternCandidates( int evalBoard[][BOARD_SIZE] );

/*------------------------------------------------------------------*/
/* 変数                                                             */
/*------------------------------------------------------------------*/

/* 碁盤の表示のための文字 */
static char stone[] = { '+', '*', 'O', '?' };

/* パターン */
static struct pattern_data patternData[] =
{
{ 3, 2,                                    /* 候補手の座標 */
 {{ SPACE, SPACE, SPACE, SPACE, SPACE },   /* ┼┼┼┼┼ */
  { SPACE, SPACE, WHITE, SPACE, SPACE },   /* ┼┼○┼┼ */
  { SPACE, WHITE, BLACK, SPACE, SPACE },   /* ┼○●×┼ */
  { SPACE, SPACE, SPACE, SPACE, SPACE },   /* ┼┼┼┼┼ */
  { SPACE, BLACK, SPACE, BLACK, SPACE }}}, /* ┼●┼●┼ */
{ 2, 2,                                    /* 候補手の座標 */
 {{ SPACE, BLACK, SPACE, SPACE, SPACE },   /* ┼●┼┼┼ */
  { SPACE, SPACE, SPACE, SPACE, SPACE },   /* ┼┼┼┼┼ */
  { SPACE, SPACE, SPACE, SPACE, SPACE },   /* ┼┼×┼┼ */
  { SPACE, WHITE, SPACE, SPACE, SPACE },   /* ┼○┼┼┼ */
  { SPACE, SPACE, SPACE, BLACK, SPACE }}}  /* ┼┼┼●┼ */
};

/* パターンの数 */
int patternNumber = sizeof(patternData)/sizeof(struct pattern_data);

/*------------------------------------------------------------------*/
/* メイン関数                                                       */
/*------------------------------------------------------------------*/
int
main( int argc, char *argv[] )
{
  int board[BOARD_SIZE][BOARD_SIZE];      /* 碁盤 */
  int evalBoard[BOARD_SIZE][BOARD_SIZE];  /* 評価値格納碁盤 */

  printf( "Sample Program Start\n" );

  /* 盤面図の入力 */
  InputFigure( board );

  /* 碁盤の表示 */
  DisplayBoard( board );

  /* 黒番の候補手の生成 */
  MakePatternCandidates( BLACK, board, evalBoard );

  /* 候補手の表示 */
  DisplayPatternCandidates( evalBoard );

  /* 白番の候補手の生成 */
  MakePatternCandidates( WHITE, board, evalBoard );

  /* 候補手の表示 */
  DisplayPatternCandidates( evalBoard );

  printf( "Sample Program End\n" );
}

/*------------------------------------------------------------------*/
/* 盤面図入力                                                       */
/* ファイル名"figure"というファイルに盤面図が書かれている           */
/*------------------------------------------------------------------*/
static void
InputFigure( int board[][BOARD_SIZE] )
{
  FILE *fp;
  char buf[256];
  int  x, y, i;

  /* ファイルを開く */
  if( (fp = fopen( "figure", "r" )) == NULL ){
    fprintf( stderr, "ERROR: file(figure) open fail\n" );
    exit(1);
  }

  /* 碁盤の初期化 */
  InitializeBoard( board );

  /* 各座標を読む */
  for( y=1; y < (BOARD_SIZE-1); y++ ){
    buf[0] = '\0';
    fgets( buf, 256, fp );
    for( x=1, i=0; x < (BOARD_SIZE-1); x++ ){
      if( buf[i] == 'O' ){
        board[y][x] = WHITE;
      }else if( buf[i] == '*' ){
        board[y][x] = BLACK;
      }else if( buf[i] == '+' ){
        board[y][x] = SPACE;
      }else{
        board[y][x] = SPACE;
      }
      i++;
    }
  }

  /* ファイルを閉じる */
  fclose( fp );
}

/*------------------------------------------------------------------*/
/* 碁盤の初期化                                                     */
/*------------------------------------------------------------------*/
static void
InitializeBoard( int board[][BOARD_SIZE] )
{
  int x, y;

  for( y=1; y < (BOARD_SIZE-1); y++ ){
    for( x=1; x < (BOARD_SIZE-1); x++ ){
      board[y][x] = SPACE;
    }
  }

  for( y=0; y < BOARD_SIZE; y++ ){
    board[y][0]= OUT;
    board[y][BOARD_SIZE-1] = OUT;
    board[0][y] = OUT;
    board[BOARD_SIZE-1][y] = OUT;
  }
}

/*------------------------------------------------------------------*/
/* 碁盤を表示する                                                   */
/*------------------------------------------------------------------*/
static void
DisplayBoard( int board[][BOARD_SIZE] )
{
  int x, y;

  printf( "    [ 1 2 3 4 5 6 7 8 910111213141516171819]\n" );
  for( y=1; y < (BOARD_SIZE-1); y++ ){
    printf( "[%2d] ", y );
    for( x=1; x < (BOARD_SIZE-1); x++ ){
      printf( " %c", stone[board[y][x]] );
    }
    printf( "\n" );
  }
}

/*------------------------------------------------------------------*/
/* データベースから候補手の生成                                     */
/*------------------------------------------------------------------*/
static void
MakePatternCandidates( int turn, int board[][BOARD_SIZE], int evalBoard[][BOARD_SIZE] )
{
  int x, y;
  int n, r;
  struct pattern_data cutData;
  struct pattern_data rotateData;

  /* 評価用のボードの初期化 */
  for( y=0; y < BOARD_SIZE; y++ ){
    for( x=0; x < BOARD_SIZE; x++ ){
      evalBoard[y][x] = -1;
    }
  }

  for( y=1-PATTERN_SIZE+1; y <= PURE_BOARD_SIZE; y++ ){
    for( x=1-PATTERN_SIZE+1; x <= PURE_BOARD_SIZE; x++ ){
      /* 盤面の切りだし */
      GetPatternFromBoard( board, &cutData, x, y );

      if( turn == WHITE ) {
        /* 白番なら白黒を反転 */
	ReverseColorPattern( &cutData );
      }

      /* パターンと比較 */
      for ( n = 0; n < patternNumber; n++) {

        /* そのまま比較する */
	RotatePattern( patternData + n, &rotateData, ROTATE_000);
	if( ComparePattern( &rotateData, &cutData ) == 0 ) {
	  printf("(%2d, %2d) pattern data found (%d)\n", x+rotateData.x, y+rotateData.y, n);
	  evalBoard[y+rotateData.y][x+rotateData.x] = n;
	}

        /* パターンを 90度回転して比較する */
	RotatePattern( patternData + n, &rotateData, ROTATE_090);
	if( ComparePattern( &rotateData, &cutData ) == 0 ) {
	  printf("(%2d, %2d) pattern data found (%d)\n", x+rotateData.x, y+rotateData.y, n);
	  evalBoard[y+rotateData.y][x+rotateData.x] = n;
	}

        /* パターンを 180度回転して比較する */
	RotatePattern( patternData + n, &rotateData, ROTATE_180);
	if( ComparePattern( &rotateData, &cutData ) == 0 ) {
	  printf("(%2d, %2d) pattern data found (%d)\n", x+rotateData.x, y+rotateData.y, n);
	  evalBoard[y+rotateData.y][x+rotateData.x] = n;
	}

        /* パターンを 270度回転して比較する */
	RotatePattern( patternData + n, &rotateData, ROTATE_270);
	if( ComparePattern( &rotateData, &cutData ) == 0 ) {
	  printf("(%2d, %2d) pattern data found (%d)\n", x+rotateData.x, y+rotateData.y, n);
	  evalBoard[y+rotateData.y][x+rotateData.x] = n;
	}

        /* パターンを 上下が逆にして比較する */
	RotatePattern( patternData + n, &rotateData, ROTATE_M000);
	if( ComparePattern( &rotateData, &cutData ) == 0 ) {
	  printf("(%2d, %2d) pattern data found (%d)\n", x+rotateData.x, y+rotateData.y, n);
	  evalBoard[y+rotateData.y][x+rotateData.x] = n;
	}

        /* パターンを 上下が逆にして 90度回転して比較する */
	RotatePattern( patternData + n, &rotateData, ROTATE_M090);
	if( ComparePattern( &rotateData, &cutData ) == 0 ) {
	  printf("(%2d, %2d) pattern data found (%d)\n", x+rotateData.x, y+rotateData.y, n);
	  evalBoard[y+rotateData.y][x+rotateData.x] = n;
	}

        /* パターンを 上下が逆にして 180度回転して比較する */
	RotatePattern( patternData + n, &rotateData, ROTATE_M180);
	if( ComparePattern( &rotateData, &cutData ) == 0 ) {
	  printf("(%2d, %2d) pattern data found (%d)\n", x+rotateData.x, y+rotateData.y, n);
	  evalBoard[y+rotateData.y][x+rotateData.x] = n;
	}

        /* パターンを 上下が逆にして 270度回転して比較する */
	RotatePattern( patternData + n, &rotateData, ROTATE_M270);
	if( ComparePattern( &rotateData, &cutData ) == 0 ) {
	  printf("(%2d, %2d) pattern data found (%d)\n", x+rotateData.x, y+rotateData.y, n);
	  evalBoard[y+rotateData.y][x+rotateData.x] = n;
	}
      }
    }
  }
}

/*------------------------------------------------------------------*/
/* Board から patternを切り出す                                     */
/*------------------------------------------------------------------*/
static void 
GetPatternFromBoard( int board[][BOARD_SIZE], struct pattern_data *pattern, int x, int y )
{
  int i, j;
  int x1,y1;

  /* 値をかえす変数をクリア */
  memset( pattern, 0, sizeof(struct pattern_data) );

  /* 指定された座標から PATTERN_SIZEだけ 切り出す */
  for ( y1=0,i=y; i < y+PATTERN_SIZE; i++,y1++ ) {
    for ( x1=0,j=x; j < x+PATTERN_SIZE; j++,x1++ ) {
      if( i < 1 || i > PURE_BOARD_SIZE || j < 1 || j > PURE_BOARD_SIZE ) {
        /* 盤外 */
	pattern->data[y1][x1] = OUT;
      } else {
	pattern->data[y1][x1] = board[i][j];
      }
    }
  }
}

/*------------------------------------------------------------------*/
/* pattern を白黒反転させる                                         */
/*------------------------------------------------------------------*/
static void 
ReverseColorPattern( struct pattern_data *pattern )
{
  int x, y;

  for( y=0; y < PATTERN_SIZE; y++ ) {
    for( x=0; x < PATTERN_SIZE; x++ ) {
      /* 白黒を反転させる */
      pattern->data[y][x] = reverseColor( pattern->data[y][x] );
    }
  }
}

/*------------------------------------------------------------------*/
/* pattern を回転させる                                             */
/*------------------------------------------------------------------*/
static void
RotatePattern( struct pattern_data *from, struct pattern_data *to, int type )
{
  int x, y;
  memset( to, 0, sizeof(struct pattern_data) );
    
  switch(type) {
  case ROTATE_000:
    /* そのまま                   */
    /* ┼┼┼┼┼      ┼┼┼┼┼ */
    /* ┼┼○┼┼      ┼┼○┼┼ */
    /* ┼○●×┼ ===> ┼○●×┼ */
    /* ┼┼┼┼┼      ┼┼┼┼┼ */
    /* ┼●┼●┼      ┼●┼●┼ */
    *to = *from;
    break;

  case ROTATE_090:
    /* パターンを 90度回転する   */
    /* ┼┼┼┼┼      ┼┼┼┼┼ */
    /* ┼┼○┼┼      ┼┼×┼● */
    /* ┼○●×┼ ===> ┼○●┼┼ */
    /* ┼┼┼┼┼      ┼┼○┼● */
    /* ┼●┼●┼      ┼┼┼┼┼ */

    for( y=0; y < PATTERN_SIZE; y++ ) {
      for( x=0; x < PATTERN_SIZE; x++ ) {
	to->data[y][x] = from->data[x][PATTERN_SIZE-y-1];
      }
    }
    to->x = from->y;
    to->y = PATTERN_SIZE - from->x - 1;
    break;

  case ROTATE_180:
    /* パターンを 180度回転する   */
    /* ┼┼┼┼┼      ┼●┼●┼ */
    /* ┼┼○┼┼      ┼┼┼┼┼ */
    /* ┼○●×┼ ===> ┼×●○┼ */
    /* ┼┼┼┼┼      ┼┼○┼┼ */
    /* ┼●┼●┼      ┼┼┼┼┼ */

    for( y=0; y < PATTERN_SIZE; y++ ) {
      for( x=0; x < PATTERN_SIZE; x++ ) {
	to->data[y][x] = from->data[PATTERN_SIZE-y-1][PATTERN_SIZE-x-1];
      }
    }
    to->x = PATTERN_SIZE - from->x - 1;
    to->y = PATTERN_SIZE - from->y - 1;
    break;

  case ROTATE_270:
    /* パターンを 270度回転する   */
    /* ┼┼┼┼┼      ┼┼┼┼┼ */
    /* ┼┼○┼┼      ●┼○┼┼ */
    /* ┼○●×┼ ===> ┼┼●○┼ */
    /* ┼┼┼┼┼      ●┼×┼┼ */
    /* ┼●┼●┼      ┼┼┼┼┼ */

    for( y=0; y < PATTERN_SIZE; y++ ) {
      for( x=0; x < PATTERN_SIZE; x++ ) {
	to->data[y][x] = from->data[PATTERN_SIZE-x-1][y];
      }
    }
    to->x = PATTERN_SIZE - from->y - 1;
    to->y = from->x;
    break;

  case ROTATE_M000:
    /* パターンの 上下を逆にする  */
    /* ┼┼┼┼┼      ┼●┼●┼ */
    /* ┼┼○┼┼      ┼┼┼┼┼ */
    /* ┼○●×┼ ===> ┼○●×┼ */
    /* ┼┼┼┼┼      ┼┼○┼┼ */
    /* ┼●┼●┼      ┼┼┼┼┼ */

    for( y=0; y < PATTERN_SIZE; y++ ) {
      for( x=0; x < PATTERN_SIZE; x++ ) {
	to->data[y][x] = from->data[PATTERN_SIZE-y-1][x];
      }
    }
    to->x = from->x;
    to->y = PATTERN_SIZE - from->y - 1;
    break;

  case ROTATE_M090:
    /* パターンの 上下を逆にして 90度回転する */
    /* ┼┼┼┼┼      ┼┼┼┼┼ */
    /* ┼┼○┼┼      ●┼×┼┼ */
    /* ┼○●×┼ ===> ┼┼●○┼ */
    /* ┼┼┼┼┼      ●┼○┼┼ */
    /* ┼●┼●┼      ┼┼┼┼┼ */

    for( y=0; y < PATTERN_SIZE; y++ ) {
      for( x=0; x < PATTERN_SIZE; x++ ) {
	to->data[y][x] = from->data[PATTERN_SIZE-x-1][PATTERN_SIZE-y-1];
      }
    }
    to->x = PATTERN_SIZE - from->y - 1;
    to->y = PATTERN_SIZE - from->x - 1;
    break;

  case ROTATE_M180:
    /* パターンの 上下を逆にして 180度回転する */
    /* ┼┼┼┼┼      ┼┼┼┼┼ */
    /* ┼┼○┼┼      ┼┼○┼┼ */
    /* ┼○●×┼ ===> ┼×●○┼ */
    /* ┼┼┼┼┼      ┼┼┼┼┼ */
    /* ┼●┼●┼      ┼●┼●┼ */

    for( y=0; y < PATTERN_SIZE; y++ ) {
      for( x=0; x < PATTERN_SIZE; x++ ) {
	to->data[y][x] = from->data[y][PATTERN_SIZE-x-1];
      }
    }
    to->x = PATTERN_SIZE - from->x - 1;
    to->y = from->y;
    break;

  case ROTATE_M270:
    /* パターンの 上下を逆にして 270度回転する */
    /* ┼┼┼┼┼      ┼┼┼┼┼ */
    /* ┼┼○┼┼      ┼┼○┼● */
    /* ┼○●×┼ ===> ┼○●┼┼ */
    /* ┼┼┼┼┼      ┼┼×┼● */
    /* ┼●┼●┼      ┼┼┼┼┼ */

    for( y=0; y < PATTERN_SIZE; y++ ) {
      for( x=0; x < PATTERN_SIZE; x++ ) {
	to->data[y][x] = from->data[x][y];
      }
    }
    to->x = from->y;
    to->y = from->x;
    break;
  }
}

/*------------------------------------------------------------------*/
/* pattern を比較する                                               */
/*------------------------------------------------------------------*/
static int
ComparePattern( struct pattern_data *p1, struct pattern_data *p2 )
{
  int x, y;

  for( y=0; y < PATTERN_SIZE; y++ ) {
    for( x=0; x < PATTERN_SIZE; x++ ) {
      if( p1->data[y][x] != p2->data[y][x] ) {
        /* 一致していなかったら -1 を返す */
	return( -1 );
      }
    }
  }

  /* 一致していたら 0 を返す */
  return( 0 );
}

/*------------------------------------------------------------------*/
/* 候補手の表示                                                     */
/*------------------------------------------------------------------*/
static void
DisplayPatternCandidates( int evalBoard[][BOARD_SIZE] )
{
  int x, y;

  printf( "### Pattern ID ###\n" );
  for( y=1; y < (BOARD_SIZE-1); y++ ){
    for( x=1; x < (BOARD_SIZE-1); x++ ){
      if( evalBoard[y][x] < 0 ){
	printf( "  +" );
      }else{
	printf( "%3d", evalBoard[y][x] );
      }
    }
    printf( "\n" );
  }
}

/*---------------------- < end of program > ------------------------*/

勝也のページへ戻る