/* ファイルから盤面図を読み込み, 黒番の次の一手を返すプログラム*/
#include
#include
#include
#define TRUE 1
#define FALSE 0
#define SPACE 0 /* 空点 */
#define BLACK 1 /* 黒石 */
#define WHITE 2 /* 白石 */
#define OB 3 /* 盤外 */
#define BOARD_SIZE ( 19 + 2 ) /* 碁盤の大きさ */
/* 相手の色 */
#define reverseColor( color ) ( color == BLACK ? WHITE : BLACK )
/*------------------------------------------------------------------*/
/* 関数 */
/*------------------------------------------------------------------*/
/* メイン関数 */
int main( int argc, char *argv[] );
/* 盤面図入力 */
void InputFigure( int board[][BOARD_SIZE] );
/* 碁盤の初期化 */
void InitializeBoard( int board[][BOARD_SIZE] );
/* 碁盤を表示する */
void DisplayBoard( int board[][BOARD_SIZE] );
/* 次の一手を求める */
void ThinkMove( int board[][BOARD_SIZE], int color, int *x, int *y );
/* 盤面の評価 */
int EvalBoard( int board[][BOARD_SIZE] );
/* 地の設定 */
void SetValue( int board[][BOARD_SIZE], int x, int y );
/* 合法手がどうか調べる */
int CheckLegal( int board[][BOARD_SIZE], int color, int x, int y );
/* 自殺手かどうか調べる */
int CheckSuicide( int board[][BOARD_SIZE], int color, int x, int y );
/* チェック用の碁盤をクリア */
void ClearCheckBoard( void );
/* 相手に囲まれているか調べる */
int DoCheckRemoveStone( int board[][BOARD_SIZE],
int color, int x, int y );
/* 碁盤を複写 */
void CopyBoard( int source[][BOARD_SIZE],
int copied[][BOARD_SIZE] );
/* 碁盤に石を置く*/
void SetStone( int board[][BOARD_SIZE], int color, int x, int y );
/* 囲まれた石を取り除く */
int RemoveStone( int board[][BOARD_SIZE],
int color, int x, int y );
/* 囲まれた石を取り除く */
int DoRemoveStone( int board[][BOARD_SIZE],
int color, int x, int y, int prisoner );
/*------------------------------------------------------------------*/
/* 変数 */
/*------------------------------------------------------------------*/
/* 碁盤の表示のための文字 */
static char stone[] = { '+', '@', 'O', '?' };
/* 合法手かどうか調べるのに使う */
static int checkBoard[BOARD_SIZE][BOARD_SIZE];
/*------------------------------------------------------------------*/
/* メイン関数 */
/*------------------------------------------------------------------*/
int
main( int argc, char *argv[] )
{
int board[BOARD_SIZE][BOARD_SIZE]; /* 碁盤 */
int xBlack, yBlack; /* 黒の着手位置 */
/* 盤面図の入力 */
InputFigure( board );
/* 碁盤の表示 */
DisplayBoard( board );
/* 黒の次の一手を求める */
ThinkMove( board, BLACK, &xBlack, &yBlack );
/* 結果の表示 */
printf( "Computer -> (%2d,%2d)\n", xBlack, yBlack );
return EXIT_SUCCESS;
}
/*------------------------------------------------------------------*/
/* 盤面図入力 */
/* ファイル名"figure"というファイルに盤面図が書かれている */
/* 劫による着手禁止点はないものとする */
/*------------------------------------------------------------------*/
void
InputFigure( int board[][BOARD_SIZE] )
{
FILE *fp;
char buf[256];
int x, y, i;
fp = fopen("./figure.txt","rt");
/* ファイルを開く */
if ( !fp ){
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 );
}
/*------------------------------------------------------------------*/
/* 碁盤の初期化 */
/*------------------------------------------------------------------*/
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]= OB;
board[y][BOARD_SIZE-1] = OB;
board[0][y] = OB;
board[BOARD_SIZE-1][y] = OB;
}
}
/*------------------------------------------------------------------*/
/* 碁盤を表示する */
/*------------------------------------------------------------------*/
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++ ){
int index = board[y][x];
printf( " %c", stone[index] );
}
printf( "\n" );
}
printf( "\n" );
}
/*------------------------------------------------------------------*/
/* 次の一手を求める */
/*------------------------------------------------------------------*/
void
ThinkMove( int board[][BOARD_SIZE],
int color, int *xBlack, int *yBlack )
{
int tmpBoard[BOARD_SIZE][BOARD_SIZE]; /* 複写用碁盤 */
int evalBoard[BOARD_SIZE][BOARD_SIZE]; /* 評価値格納用碁盤 */
int resultX, resultY;
int x, y;
int eval, init_eval, max_eval;
/* 評価値格納用碁盤の初期化 */
for( y=1; y < (BOARD_SIZE-1); y++ ){
for( x=1; x < (BOARD_SIZE-1); x++ ){
evalBoard[y][x] = 0;
}
}
/* 盤面の評価 */
init_eval = EvalBoard( board );
/* 候補手を仮りに盤上に打って評価 */
for( y=1; y < (BOARD_SIZE-1); y++ ){
for( x=1; x < (BOARD_SIZE-1); x++ ){
/* 着手禁止点なら次の点へ */
if( CheckLegal( board, color, x, y ) == FALSE ){
continue;
}
/* 碁盤を複写 */
CopyBoard( board, tmpBoard );
/* 候補手を盤上に打つ */
SetStone( tmpBoard, color, x, y );
/* 着手後の盤面の評価 */
eval = EvalBoard( tmpBoard );
/* 着手前より何目良くなったかを評価値格納用碁盤に記録 */
evalBoard[y][x] = eval - init_eval;
}
}
/* 評価値を表示する */
printf( " [ 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19]\n" );
for( y=1; y < (BOARD_SIZE-1); y++ ){
printf( "[%2d] ", y );
for( x=1; x < (BOARD_SIZE-1); x++ ){
printf( "%3d", evalBoard[y][x] );
}
printf( "\n" );
}
/* 評価値が最高のものを選ぶ */
max_eval = 0;
resultX = resultY = 0;
for( y=1; y < (BOARD_SIZE-1); y++ ){
for( x=1; x < (BOARD_SIZE-1); x++ ){
if( max_eval < evalBoard[y][x] ){
max_eval = evalBoard[y][x];
resultX = x;
resultY = y;
}
}
}
*xBlack = resultX;
*yBlack = resultY;
}
/*------------------------------------------------------------------*/
/* 盤面の評価 */
/*------------------------------------------------------------------*/
int
EvalBoard( int board[][BOARD_SIZE] )
{
int blackBoard[BOARD_SIZE][BOARD_SIZE]; /* 黒石の影響範囲 */
int whiteBoard[BOARD_SIZE][BOARD_SIZE]; /* 白石の影響範囲 */
int totalBoard[BOARD_SIZE][BOARD_SIZE]; /* 地 */
int x, y, value;
/* 初期化 */
for( y=1; y < (BOARD_SIZE-1); y++ ){
for( x=1; x < (BOARD_SIZE-1); x++ ){
blackBoard[y][x] = 0;
whiteBoard[y][x] = 0;
totalBoard[y][x] = SPACE;
}
}
for( y=1; y < (BOARD_SIZE-1); y++ ){
for( x=1; x < (BOARD_SIZE-1); x++ ){
if( board[y][x] == BLACK ){
/* 黒石から距離２以内の点にマークを付ける */
SetValue( blackBoard, x-2, y );
SetValue( blackBoard, x-1, y-1 );
SetValue( blackBoard, x-1, y );
SetValue( blackBoard, x-1, y+1 );
SetValue( blackBoard, x, y-2 );
SetValue( blackBoard, x, y-1 );
SetValue( blackBoard, x, y );
SetValue( blackBoard, x, y+1 );
SetValue( blackBoard, x, y+2 );
SetValue( blackBoard, x+1, y-1 );
SetValue( blackBoard, x+1, y );
SetValue( blackBoard, x+1, y+1 );
SetValue( blackBoard, x+2, y );
}else if( board[y][x] == WHITE ){
/* 白石から距離２以内の点にマークを付ける */
SetValue( whiteBoard, x-2, y );
SetValue( whiteBoard, x-1, y-1 );
SetValue( whiteBoard, x-1, y );
SetValue( whiteBoard, x-1, y+1 );
SetValue( whiteBoard, x, y-2 );
SetValue( whiteBoard, x, y-1 );
SetValue( whiteBoard, x, y );
SetValue( whiteBoard, x, y+1 );
SetValue( whiteBoard, x, y+2 );
SetValue( whiteBoard, x+1, y-1 );
SetValue( whiteBoard, x+1, y );
SetValue( whiteBoard, x+1, y+1 );
SetValue( whiteBoard, x+2, y );
}
}
}
/* 地の合計(黒地が多ければプラス，白地が多ければマイナスになる) */
value = 0;
/* 各点がどちらのマークか調べる */
for( y=1; y < (BOARD_SIZE-1); y++ ){
for( x=1; x < (BOARD_SIZE-1); x++ ){
if( board[y][x] == BLACK ){
totalBoard[y][x] = BLACK;
}else if( board[y][x] == WHITE ){
totalBoard[y][x] = WHITE;
}else{
if( blackBoard[y][x] > whiteBoard[y][x] ){
/* 黒からの影響度の方が大きいので白地である */
totalBoard[y][x] = BLACK;
value++;
}else if( blackBoard[y][x] < whiteBoard[y][x] ){
/* 白からの影響度の方が大きいので白地である */
totalBoard[y][x] = WHITE;
value--;
}
}
}
}
return( value );
}
/*------------------------------------------------------------------*/
/* 地の設定 */
/*------------------------------------------------------------------*/
void
SetValue( int board[][BOARD_SIZE], int x, int y )
{
/* 盤上ならば影響度を加算する */
if( x > 0 && x < (BOARD_SIZE-1) && y > 0 && y < (BOARD_SIZE-1) ){
board[y][x] += 1;
}
}
/*------------------------------------------------------------------*/
/* 合法手かどうか調べる */
/* このサンプルプログラムでは劫のチェックは省略 */
/*------------------------------------------------------------------*/
int
CheckLegal( int board[][BOARD_SIZE], int color, int x, int y )
{
/* 空点じゃないと置けません */
if( board[y][x] != SPACE ){
return( FALSE );
}
/* 自殺手なら置けません */
if( CheckSuicide( board, color, x, y ) == TRUE ){
return( FALSE );
}
/* 以上のチェックをすべてクリアできたので置けます */
return( TRUE );
}
/*------------------------------------------------------------------*/
/* 自殺手かどうか調べる */
/*------------------------------------------------------------------*/
int
CheckSuicide( int board[][BOARD_SIZE], int color, int x, int y )
{
int rtnVal;
int opponent; /* 相手の色 */
/* 仮に石を置く */
board[y][x] = color;
/* マークのクリア */
ClearCheckBoard();
/* その石は相手に囲まれているか調べる */
rtnVal = DoCheckRemoveStone( board, color, x, y );
/* 囲まれているならば自殺手の可能性あり */
if( rtnVal == TRUE ){
/* 相手の色を求める */
opponent = reverseColor( color );
/* その石を置いたことにより, 隣の相手の石が取れるなら自殺手ではない */
if( x > 1 ){
/* 隣は相手？ */
if( board[y][x-1] == opponent ){
/* マークのクリア */
ClearCheckBoard();
/* 相手の石は囲まれているか？ */
rtnVal = DoCheckRemoveStone( board, opponent, x-1, y );
/* 相手の石を取れるので自殺手ではない */
if( rtnVal == TRUE ){
/* 盤を元に戻す */
board[y][x] = SPACE;
return( FALSE );
}
}
}
if( y > 1 ){
/* 隣は相手？ */
if( board[y-1][x] == opponent ){
/* マークのクリア */
ClearCheckBoard();
/* 相手の石は囲まれているか？ */
rtnVal = DoCheckRemoveStone( board, opponent, x, y-1 );
/* 相手の石を取れるので自殺手ではない */
if( rtnVal == TRUE ){
/* 盤を元に戻す */
board[y][x] = SPACE;
return( FALSE );
}
}
}
if( x < (BOARD_SIZE-2) ){
/* 隣は相手？ */
if( board[y][x+1] == opponent ){
/* マークのクリア */
ClearCheckBoard();
/* 相手の石は囲まれているか？ */
rtnVal = DoCheckRemoveStone( board, opponent, x+1, y );
/* 相手の石を取れるので自殺手ではない */
if( rtnVal == TRUE ){
/* 盤を元に戻す */
board[y][x] = SPACE;
return( FALSE );
}
}
}
if( y < (BOARD_SIZE-2) ){
/* 隣は相手？ */
if( board[y+1][x] == opponent ){
/* マークのクリア */
ClearCheckBoard();
/* 相手の石は囲まれているか？ */
rtnVal = DoCheckRemoveStone( board, opponent, x, y+1 );
/* 相手の石を取れるので自殺手ではない */
if( rtnVal == TRUE ){
/* 盤を元に戻す */
board[y][x] = SPACE;
return( FALSE );
}
}
}
/* 盤を元に戻す */
board[y][x] = SPACE;
/* 相手の石を取れないなら自殺手 */
return( TRUE );
}else{
/* 盤を元に戻す */
board[y][x] = SPACE;
/* 囲まれていないので自殺手ではない */
return( FALSE );
}
}
/*------------------------------------------------------------------*/
/* チェック用の碁盤をクリア */
/*------------------------------------------------------------------*/
void
ClearCheckBoard( void )
{
int x, y;
for( y=1; y < (BOARD_SIZE-1); y++ ){
for( x=1; x < (BOARD_SIZE-1); x++ ){
checkBoard[y][x] = FALSE;
}
}
}
/*------------------------------------------------------------------*/
/* 座標(x,y)にあるcolor石が相手に囲まれているか調べる */
/*------------------------------------------------------------------*/
int /* 空点があればFALSEを返し, 空点がなければTRUEを返す */
DoCheckRemoveStone( int board[][BOARD_SIZE], int color, int x, int y )
{
int rtn;
/* その場所は既に調べた点ならおしまい */
if( checkBoard[y][x] == TRUE ){
return( TRUE );
}
/* 調べたことをマークする */
checkBoard[y][x] = TRUE;
/* 何も置かれていないならばおしまい */
if( board[y][x] == SPACE ){
return( FALSE );
}
/* 同じ色の石ならばその石の隣も調べる */
if( board[y][x] == color ){
/* その石の左(x-1,y)を調べる */
if( x > 1 ){
rtn = DoCheckRemoveStone( board, color, x-1, y );
if( rtn == FALSE ){
return( FALSE );
}
}
/* その石の上(x,y-1)を調べる */
if( y > 1 ){
rtn = DoCheckRemoveStone( board, color, x, y-1 );
if( rtn == FALSE ){
return( FALSE );
}
}
/* その石の右(x+1,y)を調べる */
if( x < (BOARD_SIZE-2) ){
rtn = DoCheckRemoveStone( board, color, x+1, y );
if( rtn == FALSE ){
return( FALSE );
}
}
/* その石の下(x,y+1)を調べる */
if( y < (BOARD_SIZE-2) ){
rtn = DoCheckRemoveStone( board, color, x, y+1 );
if( rtn == FALSE ){
return( FALSE );
}
}
}
/* 相手の色の石があった */
return( TRUE );
}
/*------------------------------------------------------------------*/
/* 碁盤を複写 */
/*------------------------------------------------------------------*/
void
CopyBoard( int source[][BOARD_SIZE], int copied[][BOARD_SIZE] )
{
int x, y;
for( y=0; y < BOARD_SIZE; y++ ){
for( x=0; x < BOARD_SIZE; x++ ){
copied[y][x] = source[y][x];
}
}
}
/*------------------------------------------------------------------*/
/* 碁盤に石を置く */
/* このサンプルプログラムでは取った石数は使わない */
/*------------------------------------------------------------------*/
void
SetStone( int board[][BOARD_SIZE], int color, int x, int y )
{
int prisonerN; /* 取り除かれた石の数（上） */
int prisonerE; /* 取り除かれた石の数（右） */
int prisonerS; /* 取り除かれた石の数（下） */
int prisonerW; /* 取り除かれた石の数（左） */
int prisonerAll; /* 取り除かれた石の総数 */
/* 座標(x,y)に石を置く */
board[y][x] = color;
/* 取り除かれた石の数 */
prisonerN = prisonerE = prisonerS = prisonerW = 0;
/* 置いた石の周囲の相手の石が死んでいれば碁盤から取り除く */
if( y > 1 ){
prisonerN = RemoveStone( board, color, x, y-1 );
}
if( x > 1 ){
prisonerW = RemoveStone( board, color, x-1, y );
}
if( y < (BOARD_SIZE-2) ){
prisonerS = RemoveStone( board, color, x, y+1 );
}
if( x < (BOARD_SIZE-2) ){
prisonerE = RemoveStone( board, color, x+1, y );
}
/* 取り除かれた石の総数 */
prisonerAll = prisonerN + prisonerE + prisonerS + prisonerW;
}
/*------------------------------------------------------------------*/
/* 座標(x,y)の石が死んでいれば碁盤から取り除く */
/*------------------------------------------------------------------*/
int /* 碁盤から取り除かれた石数 */
RemoveStone( int board[][BOARD_SIZE], int color, int x, int y )
{
int prisoner; /* 取り除かれた石数 */
/* 置いた石と同じ色なら取らない */
if( board[y][x] == color ){
return( 0 );
}
/* 空点なら取らない */
if( board[y][x] == SPACE ){
return( 0 );
}
/* マークのクリア */
ClearCheckBoard();
/* 囲まれているなら取る */
if( DoCheckRemoveStone( board, board[y][x], x, y ) == TRUE ){
prisoner = DoRemoveStone( board, board[y][x], x, y, 0 );
return( prisoner );
}
return( 0 );
}
/*------------------------------------------------------------------*/
/* 座標(x,y)のcolor石を碁盤から取り除き, 取った石の数を返す */
/*------------------------------------------------------------------*/
int /* アゲハマ */
DoRemoveStone( int board[][BOARD_SIZE],
int color, int x, int y, int prisoner )
{
/* 取り除かれる石と同じ色ならば石を取る */
if( board[y][x] == color ){
/* 取った石の数を１つ増やす */
prisoner++;
/* その座標に空点を置く */
board[y][x] = SPACE;
/* 左を調べる */
if( x > 1 ){
prisoner = DoRemoveStone( board, color, x-1, y, prisoner );
}
/* 上を調べる */
if( y > 1 ){
prisoner = DoRemoveStone( board, color, x, y-1, prisoner );
}
/* 右を調べる */
if( x < (BOARD_SIZE-2) ){
prisoner = DoRemoveStone( board, color, x+1, y, prisoner );
}
/* 下を調べる */
if( y < (BOARD_SIZE-2) ){
prisoner = DoRemoveStone( board, color, x, y+1, prisoner );
}
}
/* 取った石の数を返す */
return( prisoner );
}
/*---------------------- < end of program > ------------------------*/
[BACK]
[HOME]