#include <stdio.h>
#include "misc.h"
inline UCHAR GmGetBoardEx(UCHAR *lpBoard, ULONG x, ULONG y)
{
if (x <= CELL_COUNT && x >= 0 && y <= CELL_COUNT && y >= 0 ) {
return lpBoard[x * (CELL_COUNT + 1) + y];
}
return CHESS_BAD;
}
inline VOID GmSetBoardEx(UCHAR *lpBoard, ULONG x, ULONG y, UCHAR ucData)
{
if (x <= CELL_COUNT && y <= CELL_COUNT) {
lpBoard[x * (CELL_COUNT + 1) + y] = ucData;
}
return;
}
UCHAR AiGetInverseChess(UCHAR ucChess)
{
UCHAR ucReturn;
if (ucChess == CHESS_BLACK) {
ucReturn = CHESS_WHITE;
} else if (ucChess == CHESS_WHITE) {
ucReturn = CHESS_BLACK;
} else {
ucReturn = CHESS_BAD;
}
return ucReturn;
}
POS AiGetPosByDirection(POS tPosBase, CHAR cDir)
{
POS tPos;
tPos.x = tPosBase.x; tPos.y = tPosBase.y;
switch (cDir) {
case DIR_UP_COLUMN:
tPos.y--;
break;
case DIR_DOWN_COLUMN:
tPos.y++;
break;
case DIR_UP_ROW:
tPos.x--;
break;
case DIR_DOWN_ROW:
tPos.x++;
break;
case DIR_UP_LEFT_DIAGONAL:
tPos.x--;
tPos.y--;
break;
case DIR_DOWN_LEFT_DIAGONAL:
tPos.x++;
tPos.y++;
break;
case DIR_UP_RIGHT_DIAGONAL:
tPos.x++;
tPos.y--;
break;
case DIR_DOWN_RIGHT_DIAGONAL:
tPos.x--;
tPos.y++;
break;
}
return tPos;
}
CHAR AiGetInverseDirection(CHAR cDir)
{
return (-cDir);
}
//
// 取得任意方向连珠数
ULONG AiCountColumnLoop(UCHAR *lpBoard, POS tPos, UCHAR cDir, UCHAR ucChess, BOOLEAN *lpbIsActive, BOOLEAN *lpbIsInterrupt)
{
UCHAR ucData;
CHAR cDirInverse = AiGetInverseDirection(cDir);
UCHAR ucInverse = AiGetInverseChess(ucChess);
BOOLEAN bIsGap = FALSE;
*lpbIsActive = TRUE;
while (1) {
tPos = AiGetPosByDirection(tPos, cDir);
ucData = GmGetBoardEx(lpBoard, tPos.x, tPos.y);
if (ucData != ucChess) {
POS tPosNext = AiGetPosByDirection(tPos, cDir);
if (ucData == CHESS_NONE && GmGetBoard(tPosNext.x, tPosNext.y) == ucChess) {
if (bIsGap) {
tPos = AiGetPosByDirection(tPos, cDirInverse);
break;
} else {
bIsGap = TRUE;
}
} else {
if (ucData == ucInverse) {
*lpbIsActive = FALSE;
}
tPos = AiGetPosByDirection(tPos, cDirInverse);
break;
}
}
}
bIsGap = FALSE;
*lpbIsInterrupt = FALSE;
ULONG ulLoop = 1;
while (1) {
tPos = AiGetPosByDirection(tPos, cDirInverse);
ucData = GmGetBoardEx(lpBoard, tPos.x, tPos.y);
if (ucData != ucChess) {
POS tPosNext = AiGetPosByDirection(tPos, cDirInverse);
if (ucData == CHESS_NONE && GmGetBoard(tPosNext.x, tPosNext.y) == ucChess) {
if (bIsGap) {
tPos = AiGetPosByDirection(tPos, cDir);
break;
} else {
bIsGap = TRUE;
*lpbIsInterrupt = TRUE;
}
} else {
if (ucData == ucInverse) {
*lpbIsActive = FALSE;
}
tPos = AiGetPosByDirection(tPos, cDir);
break;
}
} else {
ulLoop++;
}
}
return ulLoop;
}
BOOLEAN AiIsColumnLoop(UCHAR *lpBoard, POS tPos, UCHAR ucChess, ULONG ulLoopMax)
{
BOOLEAN bTemp;
BOOLEAN bIsInterrupt;
ULONG ulLoop = AiCountColumnLoop(lpBoard, tPos, DIR_UP_COLUMN, ucChess, &bTemp, &bIsInterrupt);
return ((ulLoop >= ulLoopMax && !bIsInterrupt)? TRUE: FALSE);
}
BOOLEAN AiIsRowLoop(UCHAR *lpBoard, POS tPos, UCHAR ucChess, ULONG ulLoopMax)
{
BOOLEAN bTemp;
BOOLEAN bIsInterrupt;
ULONG ulLoop = AiCountColumnLoop(lpBoard, tPos, DIR_UP_ROW, ucChess, &bTemp, &bIsInterrupt);
return ((ulLoop >= ulLoopMax && !bIsInterrupt)? TRUE: FALSE);
}
BOOLEAN AiIsDiagonalLeftLoop(UCHAR *lpBoard, POS tPos, UCHAR ucChess, ULONG ulLoopMax)
{
BOOLEAN bTemp;
BOOLEAN bIsInterrupt;
ULONG ulLoop = AiCountColumnLoop(lpBoard, tPos, DIR_UP_LEFT_DIAGONAL, ucChess, &bTemp, &bIsInterrupt);
return ((ulLoop >= ulLoopMax && !bIsInterrupt)? TRUE: FALSE);
}
BOOLEAN AiIsDiagonalRightLoop(UCHAR *lpBoard, POS tPos, UCHAR ucChess, ULONG ulLoopMax)
{
BOOLEAN bTemp;
BOOLEAN bIsInterrupt;
ULONG ulLoop = AiCountColumnLoop(lpBoard, tPos, DIR_UP_RIGHT_DIAGONAL, ucChess, &bTemp, &bIsInterrupt);
return ((ulLoop >= ulLoopMax && !bIsInterrupt)? TRUE: FALSE);
}
// ============
//
BOOLEAN AiIsPlayerWin(UCHAR *lpBoard, POS tPos, UCHAR ucChess)
{
BOOLEAN bIsInterrupt;
BOOLEAN bLine = AiIsColumnLoop(lpBoard, tPos, ucChess, 5);
BOOLEAN bRow = AiIsRowLoop(lpBoard, tPos, ucChess, 5);
BOOLEAN bDiagonalLeft = AiIsDiagonalLeftLoop(lpBoard, tPos, ucChess, 5);
BOOLEAN bDiagonalRight = AiIsDiagonalRightLoop(lpBoard, tPos, ucChess, 5);
return ((bLine || bRow || bDiagonalLeft || bDiagonalRight)? TRUE: FALSE);
}
//
// 取得一个点周围N个有效点,0 <= N <= (ulRange * ulRange - 1)
ULONG AiGetValidPosAroundOneChess(PUCHAR lpBoard, POS tBasePos, PPOS lpValidPos, ULONG ulCount, ULONG lRange)
{
if (lRange < 1 || lRange > CELL_COUNT * 2) {
return 0;
}
lRange /= 2;
BOOLEAN bIsAdded;
for (LONG i = tBasePos.x - lRange; i < tBasePos.x + lRange; i++) {
for (LONG j = tBasePos.y - lRange; j < tBasePos.y + lRange; j++) {
if (GmGetBoardEx(lpBoard, i, j) == CHESS_NONE) {
bIsAdded = FALSE;
for (LONG k = ulCount; k >= 0; k--) {
if (lpValidPos[k].x == i && lpValidPos[k].y == j) {
bIsAdded = TRUE;
break;
}
}
if (!bIsAdded) {
lpValidPos[ulCount].x = i;
lpValidPos[ulCount].y = j;
ulCount++;
}
}
}
}
return ulCount;
}
// 取得整个棋盘的所有有效点
ULONG AiGetValidPosComplete(PUCHAR lpBoard, PPOS lpValidPos)
{
ULONG ulCount = 0;
for (ULONG i = 0; i < CELL_COUNT; i++) {
for (ULONG j = 0; j < CELL_COUNT; j++) {
if (GmGetBoardEx(lpBoard, i, j) == CHESS_NONE) {
lpValidPos[ulCount].x = i;
lpValidPos[ulCount].y = j;
ulCount++;
}
}
}
return ulCount;
}
// 取得所有落子周围的有效点
ULONG AiGetValidPosAround(PUCHAR lpBoard, PPOS lpValidPos)
{
ULONG ulCount = 0;
POS tPos;
for (ULONG i = 0; i < CELL_COUNT; i++) {
for (ULONG j = 0; j < CELL_COUNT; j++) {
if (GmGetBoardEx(lpBoard, i, j) != CHESS_NONE) {
tPos.x = i; tPos.y = j;
ulCount = AiGetValidPosAroundOneChess(lpBoard, tPos, lpValidPos, ulCount, 4);
}
}
}
return ++ulCount;
}
// ============
//
//
LONG AiGetTotalScore(UCHAR *lpBoard, POS tPos, UCHAR ucChess)
{
BOOLEAN bIsActive;
BOOLEAN bIsInterrupt;
LONG ulCurrentScore;
LONG ulTotalScore = 0;
// 横
for (ULONG i = 0; i < 4; i++) {
switch (i) {
case 0:
// 列连珠
ulCurrentScore = AiCountColumnLoop(lpBoard, tPos, DIR_UP_COLUMN, ucChess, &bIsActive, &bIsInterrupt);
break;
case 1:
// 行连珠
ulCurrentScore = AiCountColumnLoop(lpBoard, tPos, DIR_UP_ROW, ucChess, &bIsActive, &bIsInterrupt);
break;
case 2:
// 左对角线连珠
ulCurrentScore = AiCountColumnLoop(lpBoard, tPos, DIR_UP_LEFT_DIAGONAL, ucChess, &bIsActive, &bIsInterrupt);
break;
case 3:
// 右对角线连珠
ulCurrentScore = AiCountColumnLoop(lpBoard, tPos, DIR_UP_RIGHT_DIAGONAL, ucChess, &bIsActive, &bIsInterrupt);
}
if (ulCurrentScore == 1) { // 如果是一个单独棋子,设为0分
ulCurrentScore--;
}
if (ulCurrentScore == 4) { // 四连珠
ulCurrentScore *= 2;
}
if (bIsActive) { // 是否为活连珠
if (ulCurrentScore == 3) { // 活三
ulCurrentScore *= 3;
} else if (ulCurrentScore == 8) { // 活四
ulCurrentScore *= 5;
}
ulCurrentScore *= ulCurrentScore;
}
if (!bIsInterrupt) { // 连珠是否有隔断(比如***和* **是不同的)
ulCurrentScore *= 3; // 没有隔断权值更高
} else {
ulCurrentScore *= 2;
}
ulTotalScore += ulCurrentScore;
}
return ulTotalScore;
}
// 计算一个点的基本权值
ULONG AiCalculateBaseScore(UCHAR *lpBoard, POS tPos, UCHAR ucChess)
{
LONG k; // 代表黑棋或白棋
if (ucChess == CHESS_WHITE) {
k = 1;
} else if (ucChess == CHESS_BLACK) {
k = -1;
}
// 如果形成五连珠(则必胜)
LONG lScore = k * SCORE_5 * (AiIsPlayerWin(lpBoard, tPos, ucChess));
if (!lScore) { // 如果没有分出胜负
lScore = k * AiGetTotalScore(lpBoard, tPos, ucChess); // 根据连珠数获取权值
}
return lScore;
}
VOID AiGetRandomPos(UCHAR *lpBoard, PPOS lpPos)
{
UCHAR ucData = 0;
while (1) {
randomize();
lpPos->x = random(CELL_COUNT + 1);
lpPos->y = random(CELL_COUNT + 1);
ucData = GmGetBoardEx(lpBoard, lpPos->x, lpPos->y);
if (ucData == CHESS_NONE) {
break;
}
}
}
/*
关键函数:AiGetBestPos
功能:取得一个一个棋盘上黑子或白子的最佳落子点。采用深度优先搜索。
可以优化的地方:
1.采用启发式搜索
2.采用广度优先搜索
3.使用多线程
参数:
IN - lpBoard - 用于演算的棋盘
IN - ucChess - 演算棋子(黑棋或白棋,分数值正负不同)
OUT - lpMaxScore - 最大分
IN - ulNode - 演算深度(> 1时会进行递归)
返回值:
最佳落子点的坐标,以struct _POS形式返回
*/
POS AiGetBestPos(UCHAR *lpBoard, UCHAR ucChess, PLONG lpMaxScore, ULONG ulNode)
{
POS tPossiblePos[225];
ULONG ulValidPos = AiGetValidPosAround(lpBoard, tPossiblePos); // 找到所有比较合理的落子点
// 先根据棋子颜色把MaxScore设为最低分,以便后面估值
LONG ulPosBaseScore;
LONG ulMaxBaseScore = (ucChess == CHESS_BLACK? 65535: -65535);
LONG ulPosExtraScore;
LONG ulMaxExtraScore = (ucChess == CHESS_BLACK? 65535: -65535);
POS tPos;
for (ULONG i = 0; i < ulValidPos; i++) {
// 先取得基本分(根据连珠数)
UCHAR *lpNewBoard = (PUCHAR)malloc((CELL_COUNT + 1) * (CELL_COUNT + 1));
memcpy(lpNewBoard, lpBoard, (CELL_COUNT + 1) * (CELL_COUNT + 1));
GmSetBoardEx(lpNewBoard, tPossiblePos[i].x, tPossiblePos[i].y, ucChess);
ulPosBaseScore = AiCalculateBaseScore(lpNewBoard, tPossiblePos[i], ucChess);
free(lpNewBoard);
if (ulNode == 0) { // 如果已演算到最后一层,则只根据基本分来估值
//if (ulPosBaseScore != 0) {
if (((ulPosBaseScore < ulMaxBaseScore) && ucChess == CHESS_BLACK) || ((ulPosBaseScore > ulMaxBaseScore) && ucChess == CHESS_WHITE)) {
ulMaxBaseScore = ulPosBaseScore;
tPos.x = tPossiblePos[i].x;
tPos.y = tPossiblePos[i].y;
}
//}
} else { // 否则还要演算下一步
// 递归,取得对手的最佳落子点分数
UCHAR *lpNewBoard = (PUCHAR)malloc((CELL_COUNT + 1) * (CELL_COUNT + 1));
memcpy(lpNewBoard, lpBoard, (CELL_COUNT + 1) * (CELL_COUNT + 1));
GmSetBoardEx(lpNewBoard, tPossiblePos[i].x, tPossiblePos[i].y, ucChess);
AiGetBestPos(lpNewBoard, AiGetInverseChess(ucChess), &ulPosExtraScore, ulNode - 1);
free(lpNewBoard);
ulPosExtraScore += ulPosBaseScore; // 对手的最佳落子点分值加上该点基本分才是该点的最终分(一正一负相加)
//if (ulPosExtraScore != 0) {
if (((ulPosExtraScore < ulMaxExtraScore) && ucChess == CHESS_BLACK) || ((ulPosExtraScore > ulMaxExtraScore) && ucChess == CHESS_WHITE)) {
ulMaxExtraScore = ulPosExtraScore;
tPos.x = tPossiblePos[i].x;
tPos.y = tPossiblePos[i].y;
}
//}
}
}
if (ulNode == 0) {
*lpMaxScore = ulMaxBaseScore;
} else {
*lpMaxScore = ulMaxExtraScore;
if (ulMaxExtraScore == (ucChess == CHESS_BLACK? 65535: -65535)) { // 如果最大分仍是初始化时设置的最低分
AiGetRandomPos(lpBoard, &tPos); // 那么就是出错了,随机选择一个落子点(正常情况不会走到这一步)
}
}
return tPos; // 返回最佳落子点
}