五子棋AI

6091820503

大三和同学一起做的下棋机器人
http://www.amobbs.com/thread-5562838-1-1.html

近几日重新看起game AI相关的书，把之前五子棋AI部分重新写了一遍,单文件Console程序
实现细节可以看这篇paper:



code:



e]
#include <iostream>
#include <cstdlib>
#include <ctime>
#include <assert.h>
using namespace std;

#define BOARD_SIZE 15
#define EMPTY 0
#define BLACK 1
#define WHITE 2
#define POTENTIAL 3

const char Symbol[4] = {'.', 'X', 'O', '*'};

#define WIN_LEN 5//length for win


#define ALPHA -10000
#define BETA 10000


#define SCORE_TWO 1
#define SCORE_STRAIGHT_TWO 10
#define SCORE_THREE 10
#define SCORE_STRAIGHT_THREE 100
#define SCORE_FOUR 100
#define SCORE_STRAIGHT_FOUR 1000
#define SCORE_FIVE 10000

const int DIRECTIONS = 8;
int dx[DIRECTIONS] = {-1, -1, -1, 0 , 0, 1, 1, 1};
int dy[DIRECTIONS] = {1,   0, -1, 1, -1, 1, 0, -1};


const int ScoreArr[WIN_LEN*2] = {0, 1, 10, 100, 1000, 10000, 10000, 10000, 10000, 10000}; //len 0 - 9

typedef struct Move
{
        int y, x;
        int player;
        Move(int a, int b, int p): y(a), x(b), player(p){};
}Move;


void getRandomMove(int& score, Move* move, int currBoard[BOARD_SIZE][BOARD_SIZE],int potentialRange[BOARD_SIZE][BOARD_SIZE],  int player);
int Evaluate(int board[BOARD_SIZE][BOARD_SIZE], int player);
int tooglePlayer(int currPlayer);
int moveScore(int board[BOARD_SIZE][BOARD_SIZE], Move* move);
void cancleMove(int currBoard[BOARD_SIZE][BOARD_SIZE], Move* move);

int rowScan(int board[BOARD_SIZE][BOARD_SIZE], Move* move);
int colScan(int board[BOARD_SIZE][BOARD_SIZE], Move* move);
int diagScan(int board[BOARD_SIZE][BOARD_SIZE], Move* move);
int reverseDiagScan(int board[BOARD_SIZE][BOARD_SIZE], Move* move);

void print_board(int board[BOARD_SIZE][BOARD_SIZE])
{
        int i = 0, j = 0;
        for(i = 0; i < BOARD_SIZE; i++){printf(" = ");}
        printf("\n");
        for(i = 0; i < BOARD_SIZE; i++)
        {
                for(j = 0; j < BOARD_SIZE; j++)
                {
                        // if(board[j] == BLACK)
                        // {
                                // printf(" X ");
                        // }else if(board[j] == WHITE)
                        // {
                                // printf(" O ");
                        // }else
                        // {
                                // printf(" . ");
                        // }
                        printf(" %c ", Symbol[board[j]]);
                }
                printf("\n");
        }
        for(i = 0; i < BOARD_SIZE; i++){printf(" = ");}
        printf("\n");
}

int arrayMax(int *arr, int n)
{
        int maxVal = arr[0];
        for(int i = 1; i < n; i++)
        {
                maxVal = max(maxVal, arr);
        }
        return maxVal;
}

//if true, game over and player wins
bool isGameOver(int board[BOARD_SIZE][BOARD_SIZE], int player)
{
        if(Evaluate(board, player) >= 5)
        {
                return true;
        }else
        {
                return false;
        }
}

//calculate maxVal in a row of this player  
int Evaluate(int board[BOARD_SIZE][BOARD_SIZE], int player)
{
        int i = 0, j = 0, k = 0;
        int maxInRow[BOARD_SIZE] = {0};
        int maxVal = 0;
        int imin = 0, imax = 0;
        //row scan
        for(i = 0; i < BOARD_SIZE; i++)
        {
                memset(maxInRow, 0, sizeof(int)*BOARD_SIZE);
                maxInRow[0] = (board[0] == player);
                for(j = 1; j < BOARD_SIZE; j++)
                {
                        if(board[j] == player)
                        {
                                maxInRow[j] = maxInRow[j-1] + 1;
                        }else
                        {
                                maxInRow[j] = 0;
                        }
                }
                maxVal = max(maxVal, arrayMax(maxInRow, BOARD_SIZE));
        }
        //col scan
        for(j = 0; j < BOARD_SIZE; j++)
        {
                memset(maxInRow, 0, sizeof(int)*BOARD_SIZE);
                maxInRow[0] = (board[0][j] == player);
                for(i = 1; i < BOARD_SIZE; i++)
                {
                        if(board[j] == player)
                        {
                                maxInRow = maxInRow[i-1] + 1;
                        }else
                        {
                                maxInRow = 0;
                        }
                }
                maxVal = max(maxVal, arrayMax(maxInRow, BOARD_SIZE));
        }
        //diagonal scan
        for(k = 0; k < sqrtf(2.0f)*BOARD_SIZE; k++)
        {
                if(k < BOARD_SIZE)
                {
                        imin = 0; imax = k;
                }else
                {
                        imin = k - BOARD_SIZE + 1;
                        imax = BOARD_SIZE - 1;
                }
                memset(maxInRow, 0, sizeof(int)*BOARD_SIZE);
                maxInRow[imin] = (board[imin][k - imin] == player);
                for(i = imin + 1; i <= imax; i++)
                {
                        j = k - i;
                        if(board[j] == player)
                        {
                                maxInRow = maxInRow[i-1] + 1;
                        }else
                        {
                                maxInRow = 0;
                        }
                }
                maxVal = max(maxVal, arrayMax(maxInRow, BOARD_SIZE));
        }
        //reverse diagonal scan
        for(k = -sqrtf(2.0f)*BOARD_SIZE/2; k < sqrtf(2.0f)*BOARD_SIZE/2; k++)
        {
                if(k <= 0)
                {
                        imin = 0; imax = k + BOARD_SIZE - 1;
                }else
                {
                        imin = k;
                        imax = BOARD_SIZE - 1;
                }
                memset(maxInRow, 0, sizeof(int)*BOARD_SIZE);
                maxInRow[imin] = (board[imin][imin-k] == player);
                for(i = imin + 1; i <= imax; i++)
                {
                        j = i - k;
                        if(board[j] == player)
                        {
                                maxInRow = maxInRow[i-1] + 1;
                        }else
                        {
                                maxInRow = 0;
                        }
                }
                maxVal = max(maxVal, arrayMax(maxInRow, BOARD_SIZE));
        }
        //printf("maxVal: %d", maxVal);
        return maxVal;
}

void makeMove(int currBoard[BOARD_SIZE][BOARD_SIZE], Move* move)
{
        int y = move->y;
        int x = move->x;
        if(x < 0 || x >= BOARD_SIZE || y < 0 || y >= BOARD_SIZE)
        {
                return;
        }
        currBoard[y][x] = move->player;
}

void cancleMove(int currBoard[BOARD_SIZE][BOARD_SIZE], Move* move)
{
        int y = move->y;
        int x = move->x;
        if(x < 0 || x >= BOARD_SIZE || y < 0 || y >= BOARD_SIZE)
        {
                return;
        }
        currBoard[y][x] = EMPTY;
}


/*
//return score
int minimax(Move* move, int currBoard[][], int player, int maxDepth, int currDepth)
{
       
}
*/

//return score
// int getBestMove(Move* move, int currBoard[][], int player, int maxDepth)
// {
        // int score = minimax(move, currBoard, player, maxDepth, 0);
        // return score;
// }

void getBestMove(int& maxScore, Move* bestMove, int board[BOARD_SIZE][BOARD_SIZE], int potentialRange[BOARD_SIZE][BOARD_SIZE], int player, int currDepth, int maxDepth)
{
       
        int i = 0, j = 0;
        int score = 0;
        maxScore = INT_MIN;//initial
        Move* move = new Move(-1, -1, player);
       
        if(currDepth == maxDepth)
        {
                maxScore = 0;
                return;
        }
        assert(bestMove != NULL);
        bestMove->player = player;
        Move* matchBestMove = new Move(-1, -1, tooglePlayer(player));
        int maxMathScore = INT_MIN;
       
        for(i = 0; i < BOARD_SIZE; i++)
        {
                for(j = 0; j < BOARD_SIZE; j++)
                {
                        if(potentialRange[j] != POTENTIAL)
                        {
                                continue;
                        }
                       
                        if(board[j] == EMPTY)
                        {
                                move->y = i;
                                move->x = j;
                                score = moveScore(board, move);
                               
                                if(score > BETA)//beta pruning
                                {
                                        bestMove->x = move->x;
                                        bestMove->y = move->y;
                                        maxScore = score;
                                        return;
                                }
                               
                                makeMove(board, move);
                                getBestMove(maxMathScore, matchBestMove, board, potentialRange, tooglePlayer(player), currDepth + 1, maxDepth);
                                //maxMathScore = moveScore(board, matchBestMove);
                                cancleMove(board, move);
                               
                                score -= 0.8*maxMathScore;
                                if(score > maxScore)
                                {
                                        maxScore = score;
                                        bestMove->x = move->x;
                                        bestMove->y = move->y;
                                }
                        }
                }
        }
        if(bestMove->y < 0 || bestMove->x < 0)
        {
                 getRandomMove(maxScore, bestMove, board, potentialRange, player);
        }
        //printf("%c score: %d (%d, %d)\n", Symbol[player], score, bestMove->y, bestMove->x);
        //return bestMove;
}

//the player will obtain how much score if take this step
// int moveScore(int board[BOARD_SIZE][BOARD_SIZE], Move* move)
// {
        // int score = 0;
        // int maxVal = 0;
        // int y = move->y;
        // int x = move->x;
       
        // if(x < 0 || x >= BOARD_SIZE || y < 0 || y >= BOARD_SIZE)
        // {
                // return 0;
        // }
       
        // if(board[y][x] != EMPTY)
        // {
                // return -1;//not allowed
        // }
       
        // //search window
        // int min_x = 0, min_y = 0, max_x = 0, max_y = 0;
        // min_x = max(0, x - (WIN_LEN - 1));
        // min_y = max(0, y - (WIN_LEN - 1));
        // max_x = min(BOARD_SIZE -1, x + (WIN_LEN - 1));
        // max_y = min(BOARD_SIZE -1, y + (WIN_LEN - 1));
        // int i = 0, j = 0;
        // //row
        // j = x-1; maxVal = 1;
        // int match = tooglePlayer(move->player);
        // while(j >= min_x && board[y][j] != match)
        // {
                // maxVal += (board[y][j] == move->player);
                // j--;
        // }
        // j = x+1;
        // while(j <= max_x && board[y][j] != match)
        // {
                // maxVal += (board[y][j] == move->player);
                // j++;
        // }
        // score += ScoreArr[maxVal];
       
        // //col
        // i = y-1; maxVal = 1;
        // while(i >= min_y && board[x] != match)
        // {
                // maxVal += (board[x] == move->player);
                // i--;
        // }
        // i = y+1;
        // while(i <= max_y && board[x] != match)
        // {
                // maxVal+= (board[x] == move->player);
                // i++;
        // }
        // score += ScoreArr[maxVal];
        // //diagonal
        // j = x-1; i = y-1; maxVal = 1;
        // while(j >= min_x && i >= min_y && board[j] != match)
        // {
                // maxVal+= (board[j] == move->player);
                // j--;
                // i--;
        // }
        // j = x+1; i = y+1;
        // while(j <= max_x && i <= max_y && board[j] != match)
        // {
                // maxVal+= (board[j] == move->player);
                // j++;
                // i++;
        // }
        // score += ScoreArr[maxVal];
       
        // //reverse diagonal
        // j = x-1; i = y+1; maxVal = 1;
        // while(j >= min_x && i <= max_y && board[j] != match)
        // {
                // maxVal+= (board[j] == move->player);
                // j--;
                // i++;
        // }
        // j = x+1; i = y-1;
        // while(j <= max_x && i >= min_y && board[j] != match)
        // {
                // maxVal+= (board[j] == move->player);
                // j++;
                // i--;
        // }
        // score += ScoreArr[maxVal];
        // return score;
// }
// int moveScore(int board[BOARD_SIZE][BOARD_SIZE], Move* move)
// {
        // int score = 0;
        // int maxVal = 0;
        // int y = move->y;
        // int x = move->x;
       
        // if(x < 0 || x >= BOARD_SIZE || y < 0 || y >= BOARD_SIZE)
        // {
                // return 0;
        // }
       
        // if(board[y][x] != EMPTY)
        // {
                // return -1;//not allowed
        // }
       
        // //search window
        // int min_x = 0, min_y = 0, max_x = 0, max_y = 0;
        // min_x = max(0, x - (WIN_LEN - 1));
        // min_y = max(0, y - (WIN_LEN - 1));
        // max_x = min(BOARD_SIZE -1, x + (WIN_LEN - 1));
        // max_y = min(BOARD_SIZE -1, y + (WIN_LEN - 1));
        // int i = 0, j = 0;
        // //row
        // j = x-1; maxVal = 1;
        // int player = move->player;
        // int match = tooglePlayer(move->player);
        // while(j >= min_x && board[y][j] == player)
        // {
                // maxVal += (board[y][j] == move->player);
                // j--;
        // }
        // j = x+1;
        // while(j <= max_x && board[y][j] == player)
        // {
                // maxVal += (board[y][j] == move->player);
                // j++;
        // }
        // score += ScoreArr[maxVal];
       
        // //col
        // i = y-1; maxVal = 1;
        // while(i >= min_y && board[x] == player)
        // {
                // maxVal += (board[x] == move->player);
                // i--;
        // }
        // i = y+1;
        // while(i <= max_y && board[x] == player)
        // {
                // maxVal+= (board[x] == move->player);
                // i++;
        // }
        // score += ScoreArr[maxVal];
        // //diagonal
        // j = x-1; i = y-1; maxVal = 1;
        // while(j >= min_x && i >= min_y && board[j] == player)
        // {
                // maxVal+= (board[j] == move->player);
                // j--;
                // i--;
        // }
        // j = x+1; i = y+1;
        // while(j <= max_x && i <= max_y && board[j] == player)
        // {
                // maxVal+= (board[j] == move->player);
                // j++;
                // i++;
        // }
        // score += ScoreArr[maxVal];
       
        // //reverse diagonal
        // j = x-1; i = y+1; maxVal = 1;
        // while(j >= min_x && i <= max_y && board[j] == player)
        // {
                // maxVal+= (board[j] == move->player);
                // j--;
                // i++;
        // }
        // j = x+1; i = y-1;
        // while(j <= max_x && i >= min_y && board[j] == player)
        // {
                // maxVal+= (board[j] == move->player);
                // j++;
                // i--;
        // }
        // score += ScoreArr[maxVal];
        // return score;
// }


int moveScore(int board[BOARD_SIZE][BOARD_SIZE], Move* move)
{
       
        int rowScore = rowScan(board, move);
        int colScore =  colScan(board, move);
        int diagScore = diagScan(board, move);
        int reverseDiagScore = reverseDiagScan(board, move);
        //if(move->player == BLACK)
        //{
        //        printf("(x, %d, %d)", move->y, move->x);
        //}else if(move->player == WHITE)
        //{
        //        printf("(o, %d, %d)", move->y, move->x);
        //}
        //printf(" %d %d %d %d    ",  rowScore, colScore, diagScore, reverseDiagScore);
        int score =  rowScore + colScore + diagScore + reverseDiagScore;
        return score;
}
//compute the score of the threats
int rowScan(int board[BOARD_SIZE][BOARD_SIZE], Move* move)
{
        int y = move->y;
        int x = move->x;
       
        if(x < 0 || x >= BOARD_SIZE || y < 0 || y >= BOARD_SIZE)
        {
                return 0;
        }
       
        if(board[y][x] != EMPTY)
        {
                return -1;//not allowed
        }
       
        //search window
        int min_id = max(0, x - (WIN_LEN - 1));
        int max_id = min(BOARD_SIZE -1, x + (WIN_LEN - 1));
       
        int i = 0, j = 0;
        int low = 0, high = 0;
       
        //row
        low = x-1;
        int player = move->player;
       
        while(low >= min_id && board[y][low] == player)
        {
                low--;
        }

        high = x+1;
        while(high <= max_id && board[y][high] == player)
        {
                high++;
        }
       
        int cnt = high - low - 1;
        if(cnt == 2)
        {
                if(low >= 0 && high < BOARD_SIZE)
                {
                        if(board[y][low] == EMPTY && board[y][high] == EMPTY)
                        {
                                return SCORE_STRAIGHT_TWO;
                        }else if(board[y][low] == EMPTY || board[y][high] == EMPTY)
                        {
                                return SCORE_TWO;
                        }
                }
        }else if(cnt == 3)
        {
                if(low >= 0 && high < BOARD_SIZE)
                {
                        if(board[y][low] == EMPTY && board[y][high] == EMPTY)
                        {
                                return SCORE_STRAIGHT_THREE;
                        }else if(board[y][low] == EMPTY || board[y][high] == EMPTY)
                        {
                                return SCORE_THREE;
                        }
                }
        }else if(cnt == 4)
        {
                if(low >= 0 && high < BOARD_SIZE)
                {
                        if(board[y][low] == EMPTY && board[y][high] == EMPTY)
                        {
                                return SCORE_STRAIGHT_FOUR;
                        }else if(board[y][low] == EMPTY || board[y][high] == EMPTY)
                        {
                                return SCORE_FOUR;
                        }
                       
                }else if(low < 0)
                {
                        if(board[y][high] == EMPTY)
                        {
                                return SCORE_FOUR;
                        }
                }else if(high >= BOARD_SIZE)
                {
                        if(board[y][low] == EMPTY)
                        {
                                return SCORE_FOUR;
                        }
                }
        }else if(cnt >= 5)
        {
                return SCORE_FIVE;
        }
        return 0;
}

//compute the score of the threats
int colScan(int board[BOARD_SIZE][BOARD_SIZE], Move* move)
{
        int y = move->y;
        int x = move->x;
       
        if(x < 0 || x >= BOARD_SIZE || y < 0 || y >= BOARD_SIZE)
        {
                return 0;
        }
       
        if(board[y][x] != EMPTY)
        {
                return -1;//not allowed
        }
       
        //search window
        int min_id = max(0, y - (WIN_LEN - 1));
        int max_id = min(BOARD_SIZE -1, y + (WIN_LEN - 1));
       
        int i = 0, j = 0;
        int low = 0, high = 0;
       
        //row
        low = y-1;
        int player = move->player;
       
        while(low >= min_id && board[low][x] == player)
        {
                low--;
        }

        high = y+1;
        while(high <= max_id && board[high][x] == player)
        {
                high++;
        }
       
        int cnt = high - low - 1;
        if(cnt == 2)
        {
                if(low >= 0 && high < BOARD_SIZE)
                {
                        if(board[low][x] == EMPTY && board[high][x] == EMPTY)
                        {
                                return SCORE_STRAIGHT_TWO;
                        }else if(board[low][x] == EMPTY || board[high][x] == EMPTY)
                        {
                                return SCORE_TWO;
                        }
                }
        }else if(cnt == 3)
        {
                if(low >= 0 && high < BOARD_SIZE)
                {
                        if(board[low][x] == EMPTY && board[high][x] == EMPTY)
                        {
                                return SCORE_STRAIGHT_THREE;
                        }else if(board[low][x] == EMPTY && board[high][x] == EMPTY)
                        {
                                return SCORE_THREE;
                        }
                }
        }else if(cnt == 4)
        {
                if(low >= 0 && high < BOARD_SIZE)
                {
                        if(board[low][x] == EMPTY && board[high][x] == EMPTY)
                        {
                                return SCORE_STRAIGHT_FOUR;
                        }else if(board[low][x] == EMPTY || board[high][x] == EMPTY)
                        {
                                return SCORE_FOUR;
                        }
                       
                }else if(low < 0)
                {
                        if(board[high][x] == EMPTY)
                        {
                                return SCORE_FOUR;
                        }
                }else if(high >= BOARD_SIZE)
                {
                        if(board[low][x] == EMPTY)
                        {
                                return SCORE_FOUR;
                        }
                }
        }else if(cnt >= 5)
        {
                return SCORE_FIVE;
        }
        return 0;
}


int diagScan(int board[BOARD_SIZE][BOARD_SIZE], Move* move)
{
        int y = move->y;
        int x = move->x;
       
        if(x < 0 || x >= BOARD_SIZE || y < 0 || y >= BOARD_SIZE)
        {
                return 0;
        }
       
        if(board[y][x] != EMPTY)
        {
                return -1;//not allowed
        }
       
        //search window
        int min_x = max(0, x - (WIN_LEN - 1));
        int max_x = min(BOARD_SIZE -1, x + (WIN_LEN - 1));
        int min_y = max(0, y - (WIN_LEN - 1));
        int max_y = min(BOARD_SIZE -1, y + (WIN_LEN - 1));
       
        int i = 0, j = 0;
        int lowx = 0, highx = 0, lowy = 0, highy = 0;
       
        //row
        lowx = x-1;
        lowy = y-1;
        int player = move->player;
       
        while(lowx >= min_x && lowy >= min_y && board[lowy][lowx] == player)
        {
                lowx--;
                lowy--;
        }

        highx = x+1;
        highy = y+1;
        while(highx <= max_x && highy <= max_y && board[highy][highx] == player)
        {
                highx++;
                highy++;
        }
       
        int cnt = highx - lowx - 1;
        if(cnt == 2)
        {
                if(!(lowx <= 0 || lowy <= 0 || highx >= BOARD_SIZE || highy >= BOARD_SIZE))
                {
                        if(board[lowy][lowx] == EMPTY && board[highy][highx] == EMPTY)
                        {
                                return SCORE_STRAIGHT_TWO;
                        }else if(board[lowy][lowx] == EMPTY || board[highy][highx] == EMPTY)
                        {
                                return SCORE_TWO;
                        }
                }
        }else if(cnt == 3)
        {
                if(!(lowx <= 0 || lowy <= 0 || highx >= BOARD_SIZE || highy >= BOARD_SIZE))
                {
                        if(board[lowy][lowx] == EMPTY && board[highy][highx] == EMPTY)
                        {
                                return SCORE_STRAIGHT_THREE;
                        }
                }
        }else if(cnt == 4)
        {
                if(!(lowx <= 0 || lowy <= 0 || highx >= BOARD_SIZE || highy >= BOARD_SIZE))
                {
                        if(board[lowy][lowx] == EMPTY && board[highy][highx] == EMPTY)
                        {
                                return SCORE_STRAIGHT_FOUR;
                        }else if(board[lowy][lowx] == EMPTY || board[highy][highx] == EMPTY)
                        {
                                return SCORE_FOUR;
                        }
                }
        }else if(cnt >= 5)
        {
                return SCORE_FIVE;
        }
        return 0;
}

int reverseDiagScan(int board[BOARD_SIZE][BOARD_SIZE], Move* move)
{
        int y = move->y;
        int x = move->x;
       
        if(x < 0 || x >= BOARD_SIZE || y < 0 || y >= BOARD_SIZE)
        {
                return 0;
        }
       
        if(board[y][x] != EMPTY)
        {
                return -1;//not allowed
        }
       
        //search window
        int min_x = max(0, x - (WIN_LEN - 1));
        int max_x = min(BOARD_SIZE -1, x + (WIN_LEN - 1));
        int min_y = max(0, y - (WIN_LEN - 1));
        int max_y = min(BOARD_SIZE -1, y + (WIN_LEN - 1));
       
        int i = 0, j = 0;
        int lowx = 0, highx = 0, lowy = 0, highy = 0;
       
        //row
        lowx = x-1;
        highy = y+1;
        int player = move->player;
       
        while(lowx >= min_x && highy <= max_y && board[highy][lowx] == player)
        {
                lowx--;
                highy++;
        }

        highx = x+1;
        lowy = y-1;
        while(highx <= max_x && lowy >= min_y && board[lowy][highx] == player)
        {
                highx++;
                lowy--;
        }
       
        int cnt = highx - lowx - 1;
        if(cnt == 2)
        {
                if(!(lowx <= 0 || lowy <= 0 || highx >= BOARD_SIZE || highy >= BOARD_SIZE))
                {
                        if(board[lowy][highx] == EMPTY && board[highy][lowx] == EMPTY)
                        {
                                return SCORE_STRAIGHT_TWO;
                        }else if(board[lowy][highx] || EMPTY && board[highy][lowx] == EMPTY)
                        {
                                return SCORE_TWO;
                        }
                }
        }else if(cnt == 3)
        {
                if(!(lowx <= 0 || lowy <= 0 || highx >= BOARD_SIZE || highy >= BOARD_SIZE))
                {
                        if(board[lowy][highx] == EMPTY && board[highy][lowx] == EMPTY)
                        {
                                return SCORE_STRAIGHT_THREE;
                        }else if(board[lowy][highx] == EMPTY && board[highy][lowx] == EMPTY)
                        {
                                return SCORE_THREE;
                        }
                }
        }else if(cnt == 4)
        {
                if(!(lowx <= 0 || lowy <= 0 || highx >= BOARD_SIZE || highy >= BOARD_SIZE))
                {
                        if(board[lowy][highx] == EMPTY && board[highy][lowx] == EMPTY)
                        {
                                return SCORE_STRAIGHT_FOUR;
                        }else if(board[lowy][highx] == EMPTY || board[highy][lowx] == EMPTY)
                        {
                                return SCORE_FOUR;
                        }
                }
        }else if(cnt >= 5)
        {
                return SCORE_FIVE;
        }
        return 0;
}


//random move for test
Move* getRandomMove(int currBoard[BOARD_SIZE][BOARD_SIZE],  int player)
{
        srand(time(0));
        int row = 0, col = 0;
       
        while(1)
        {
                row = rand()%BOARD_SIZE;
                col = rand()%BOARD_SIZE;
                if(currBoard[row][col] == EMPTY)
                {
                        Move* move = new Move(row, col, player);
                        return move;
                }
        }
}

void getRandomMove(int& score,Move* move,  int currBoard[BOARD_SIZE][BOARD_SIZE],int potentialRange[BOARD_SIZE][BOARD_SIZE],  int player)
{
        srand(time(0));
        int row = 0, col = 0;
        assert(move != NULL);
        move->player = player;
        while(1)
        {
                row = rand()%BOARD_SIZE;
                col = rand()%BOARD_SIZE;
                if(currBoard[row][col] == EMPTY)
                {
                        move->y = row;
                        move->x = col;
                        score = moveScore(currBoard, move);
                        return;
                }
        }
}

int tooglePlayer(int currPlayer)
{
        if(currPlayer == BLACK)
        {
                return WHITE;
        }else if(currPlayer == WHITE)
        {
                return BLACK;
        }
}

void resetBoard(int board[BOARD_SIZE][BOARD_SIZE])
{
        int i = 0, j = 0;
        for(i = 0; i < BOARD_SIZE; i++)
        {
                for(j = 0; j < BOARD_SIZE; j++)
                {
                        board[j] = 0;
                }
        }
}

void updatePotentialRange(int potentialRange[BOARD_SIZE][BOARD_SIZE], Move* move)
{
        int i = 0, j = 0;
        int x = 0, y = 0;
        for(i = 0;i < DIRECTIONS; i++)
        {
                x = move->x + dx;
                y = move->y + dy;
                if(x >= 0 && x < BOARD_SIZE && y >= 0 && y < BOARD_SIZE)
                {
                        potentialRange[y][x] = POTENTIAL;
                }
                potentialRange[move->y][move->x] = BLACK;
        }
}

void setPotentialRange(int potentialRange[BOARD_SIZE][BOARD_SIZE])
{
        int i = 0, j = 0;
        for(i = 0; i < BOARD_SIZE; i++)
        {
                for(j = 0; j < BOARD_SIZE; j++)
                {
                        potentialRange[j] = POTENTIAL;
                }
        }
}
int main()
{
        int board[BOARD_SIZE][BOARD_SIZE] = {0};
        int potentialRange[BOARD_SIZE][BOARD_SIZE] = {0};//decrease the search range
        resetBoard(board);
        resetBoard(potentialRange);

        print_board(board);
       
        bool ret = isGameOver(board, BLACK);
        ret = isGameOver(board, WHITE);
        int player = BLACK;
        Move * move = new Move(0, 0, player);

#if 0
        potentialRange[BOARD_SIZE/2][BOARD_SIZE/2] = POTENTIAL;
#else
        move = getRandomMove(board, player);;
        makeMove(board, move);
        updatePotentialRange(potentialRange, move);
        player = tooglePlayer(player);
#endif       

        int score = 0;
        int maxDepth = 2;
        while(1)
        {
                //move = getRandomMove(board, player);
                 getBestMove(score, move, board, potentialRange, player, 0, maxDepth);
                //score = moveScore(board, move);

                printf("%c score: %d (%d, %d)\n", Symbol[player], score, move->y, move->x);
                makeMove(board, move);
                updatePotentialRange(potentialRange, move);
               
                print_board(board);
                if(isGameOver(board, player))
                {
                        printf("\nPlayer %d wins!\n", player);
                        break;
                }
                player = tooglePlayer(player);
        }
       
        return 0;
}
[/code]

6091820503

占层楼            

6091820503

再占一层           

6091820503

再多占一层            

Puppey

支持一波！

zhaoxukiller

先手不允许33连的考虑了吗

6091820503

zhaoxukiller 发表于 2015-4-12 15:40
先手不允许33连的考虑了吗

这里不考虑禁手

小咯咯怒

通篇没有注释

jlhgold

为啥不考虑来个文件的 直接贴代码 好长好长啊

wx85105157

没注释没中文好难受

hanshiruo

hao............