五子棋AI (amobbs.com 阿莫电子技术论坛) -

6091820503 发表于 2015-4-12 15:01:13

五子棋AI

本帖最后由 6091820503 于 2015-4-12 19:40 编辑

大三和同学一起做的下棋机器人
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 = {'.', '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 = {-1, -1, -1, 0 , 0, 1, 1, 1};
int dy = {1, 0, -1, 1, -1, 1, 0, -1};

const int ScoreArr = {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,int potentialRange,int player);
int Evaluate(int board, int player);
int tooglePlayer(int currPlayer);
int moveScore(int board, Move* move);
void cancleMove(int currBoard, Move* move);

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

void print_board(int board)
{
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 == BLACK)
// {
// printf(" X ");
// }else if(board == WHITE)
// {
// printf(" O ");
// }else
// {
// printf(" . ");
// }
printf(" %c ", Symbol]);
}
printf("\n");
}
for(i = 0; i < BOARD_SIZE; i++){printf(" = ");}
printf("\n");
}

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

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

//calculate maxVal in a row of this player
int Evaluate(int board, int player)
{
int i = 0, j = 0, k = 0;
int maxInRow = {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 = (board == player);
for(j = 1; j < BOARD_SIZE; j++)
{
if(board == player)
{
maxInRow = maxInRow + 1;
}else
{
maxInRow = 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 = (board == player);
for(i = 1; i < BOARD_SIZE; i++)
{
if(board == player)
{
maxInRow = maxInRow + 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 = (board == player);
for(i = imin + 1; i <= imax; i++)
{
j = k - i;
if(board == player)
{
maxInRow = maxInRow + 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 = (board == player);
for(i = imin + 1; i <= imax; i++)
{
j = i - k;
if(board == player)
{
maxInRow = maxInRow + 1;
}else
{
maxInRow = 0;
}
}
maxVal = max(maxVal, arrayMax(maxInRow, BOARD_SIZE));
}
//printf("maxVal: %d", maxVal);
return maxVal;
}

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

void cancleMove(int currBoard, Move* move)
{
int y = move->y;
int x = move->x;
if(x < 0 || x >= BOARD_SIZE || y < 0 || y >= BOARD_SIZE)
{
return;
}
currBoard = 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, int potentialRange, 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 != POTENTIAL)
{
continue;
}

if(board == 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, score, bestMove->y, bestMove->x);
//return bestMove;
}

//the player will obtain how much score if take this step
// int moveScore(int board, 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 != 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 != match)
// {
// maxVal += (board == move->player);
// j--;
// }
// j = x+1;
// while(j <= max_x && board != match)
// {
// maxVal += (board == move->player);
// j++;
// }
// score += ScoreArr;

// //col
// i = y-1; maxVal = 1;
// while(i >= min_y && board != match)
// {
// maxVal += (board == move->player);
// i--;
// }
// i = y+1;
// while(i <= max_y && board != match)
// {
// maxVal+= (board == move->player);
// i++;
// }
// score += ScoreArr;
// //diagonal
// j = x-1; i = y-1; maxVal = 1;
// while(j >= min_x && i >= min_y && board != match)
// {
// maxVal+= (board == move->player);
// j--;
// i--;
// }
// j = x+1; i = y+1;
// while(j <= max_x && i <= max_y && board != match)
// {
// maxVal+= (board == move->player);
// j++;
// i++;
// }
// score += ScoreArr;

// //reverse diagonal
// j = x-1; i = y+1; maxVal = 1;
// while(j >= min_x && i <= max_y && board != match)
// {
// maxVal+= (board == move->player);
// j--;
// i++;
// }
// j = x+1; i = y-1;
// while(j <= max_x && i >= min_y && board != match)
// {
// maxVal+= (board == move->player);
// j++;
// i--;
// }
// score += ScoreArr;
// return score;
// }
// int moveScore(int board, 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 != 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 == player)
// {
// maxVal += (board == move->player);
// j--;
// }
// j = x+1;
// while(j <= max_x && board == player)
// {
// maxVal += (board == move->player);
// j++;
// }
// score += ScoreArr;

// //col
// i = y-1; maxVal = 1;
// while(i >= min_y && board == player)
// {
// maxVal += (board == move->player);
// i--;
// }
// i = y+1;
// while(i <= max_y && board == player)
// {
// maxVal+= (board == move->player);
// i++;
// }
// score += ScoreArr;
// //diagonal
// j = x-1; i = y-1; maxVal = 1;
// while(j >= min_x && i >= min_y && board == player)
// {
// maxVal+= (board == move->player);
// j--;
// i--;
// }
// j = x+1; i = y+1;
// while(j <= max_x && i <= max_y && board == player)
// {
// maxVal+= (board == move->player);
// j++;
// i++;
// }
// score += ScoreArr;

// //reverse diagonal
// j = x-1; i = y+1; maxVal = 1;
// while(j >= min_x && i <= max_y && board == player)
// {
// maxVal+= (board == move->player);
// j--;
// i++;
// }
// j = x+1; i = y-1;
// while(j <= max_x && i >= min_y && board == player)
// {
// maxVal+= (board == move->player);
// j++;
// i--;
// }
// score += ScoreArr;
// return score;
// }

int moveScore(int board, 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, 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 != 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 == player)
{
low--;
}

high = x+1;
while(high <= max_id && board == player)
{
high++;
}

int cnt = high - low - 1;
if(cnt == 2)
{
if(low >= 0 && high < BOARD_SIZE)
{
if(board == EMPTY && board == EMPTY)
{
return SCORE_STRAIGHT_TWO;
}else if(board == EMPTY || board == EMPTY)
{
return SCORE_TWO;
}
}
}else if(cnt == 3)
{
if(low >= 0 && high < BOARD_SIZE)
{
if(board == EMPTY && board == EMPTY)
{
return SCORE_STRAIGHT_THREE;
}else if(board == EMPTY || board == EMPTY)
{
return SCORE_THREE;
}
}
}else if(cnt == 4)
{
if(low >= 0 && high < BOARD_SIZE)
{
if(board == EMPTY && board == EMPTY)
{
return SCORE_STRAIGHT_FOUR;
}else if(board == EMPTY || board == EMPTY)
{
return SCORE_FOUR;
}

}else if(low < 0)
{
if(board == EMPTY)
{
return SCORE_FOUR;
}
}else if(high >= BOARD_SIZE)
{
if(board == EMPTY)
{
return SCORE_FOUR;
}
}
}else if(cnt >= 5)
{
return SCORE_FIVE;
}
return 0;
}

//compute the score of the threats
int colScan(int board, 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 != 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 == player)
{
low--;
}

high = y+1;
while(high <= max_id && board == player)
{
high++;
}

int cnt = high - low - 1;
if(cnt == 2)
{
if(low >= 0 && high < BOARD_SIZE)
{
if(board == EMPTY && board == EMPTY)
{
return SCORE_STRAIGHT_TWO;
}else if(board == EMPTY || board == EMPTY)
{
return SCORE_TWO;
}
}
}else if(cnt == 3)
{
if(low >= 0 && high < BOARD_SIZE)
{
if(board == EMPTY && board == EMPTY)
{
return SCORE_STRAIGHT_THREE;
}else if(board == EMPTY && board == EMPTY)
{
return SCORE_THREE;
}
}
}else if(cnt == 4)
{
if(low >= 0 && high < BOARD_SIZE)
{
if(board == EMPTY && board == EMPTY)
{
return SCORE_STRAIGHT_FOUR;
}else if(board == EMPTY || board == EMPTY)
{
return SCORE_FOUR;
}

}else if(low < 0)
{
if(board == EMPTY)
{
return SCORE_FOUR;
}
}else if(high >= BOARD_SIZE)
{
if(board == EMPTY)
{
return SCORE_FOUR;
}
}
}else if(cnt >= 5)
{
return SCORE_FIVE;
}
return 0;
}

int diagScan(int board, 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 != 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 == player)
{
lowx--;
lowy--;
}

highx = x+1;
highy = y+1;
while(highx <= max_x && highy <= max_y && board == player)
{
highx++;
highy++;
}

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

int reverseDiagScan(int board, 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 != 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 == player)
{
lowx--;
highy++;
}

highx = x+1;
lowy = y-1;
while(highx <= max_x && lowy >= min_y && board == player)
{
highx++;
lowy--;
}

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

//random move for test
Move* getRandomMove(int currBoard,int player)
{
srand(time(0));
int row = 0, col = 0;

while(1)
{
row = rand()%BOARD_SIZE;
col = rand()%BOARD_SIZE;
if(currBoard == EMPTY)
{
Move* move = new Move(row, col, player);
return move;
}
}
}

void getRandomMove(int& score,Move* move,int currBoard,int potentialRange,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 == 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)
{
int i = 0, j = 0;
for(i = 0; i < BOARD_SIZE; i++)
{
for(j = 0; j < BOARD_SIZE; j++)
{
board = 0;
}
}
}

void updatePotentialRange(int potentialRange, 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 = POTENTIAL;
}
potentialRange = BLACK;
}
}

void setPotentialRange(int potentialRange)
{
int i = 0, j = 0;
for(i = 0; i < BOARD_SIZE; i++)
{
for(j = 0; j < BOARD_SIZE; j++)
{
potentialRange = POTENTIAL;
}
}
}
int main()
{
int board = {0};
int potentialRange = {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 = 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, 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;
}

6091820503 发表于 2015-4-12 15:03:28

占层楼

6091820503 发表于 2015-4-12 15:03:45

再占一层

6091820503 发表于 2015-4-12 15:04:12

再多占一层

Puppey 发表于 2015-4-12 15:35:21

支持一波！

zhaoxukiller 发表于 2015-4-12 15:40:30

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

6091820503 发表于 2015-4-12 16:08:21

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

这里不考虑禁手

小咯咯怒 发表于 2015-4-12 16:30:33

通篇没有注释

jlhgold 发表于 2015-4-12 19:35:08

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

wx85105157 发表于 2015-4-12 21:33:08

没注释没中文好难受

hanshiruo 发表于 2015-4-13 08:45:32

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

页: [1]

amobbs.com 阿莫电子技术论坛's Archiver

五子棋AI