基于博弈树的开源五子棋AI教程[4 静态棋盘评估]

news/2024/11/30 13:42:45/

引子

静态棋盘的评估是棋力的一个很重要的体现，一个优秀的基于博弈树搜索的AI往往有上千行工作量，本文没有做深入讨论，仅仅写了个引子用来抛砖引玉。
评估一般从两个角度入手，一个是子力，另一个是局势。

1 评估维度

1.1子力

所谓的子力，也就是每个子的重要程度，这边用基础棋型来衡量。通过扫描匹配棋型，重要的棋型给予更大的值，这里棋型得分表参考了网上的数值。
另一种衡量子力的方式是是利用五元组，通过判定五元组内子的连续性和阻断性赋予不同的分数。

//------定义基础棋型------//
#define ChessNone          0    // 空棋型:0
#define ChessSleepingOne   1    // 眠一  :0
#define ChessActiveOne     2    // 活一  :20
#define ChessSleepingTwo   3    // 眠二  :20
#define ChessActiveTwo     4    // 活二  :120
#define ChessSleepingThree 5    // 眠三  :120
#define ChessActiveThree   6    // 活三  :720
#define ChessBrokenFour    7    // 冲四  :720
#define ChessActiveFour    8    // 活四  :4320
#define ChessFive          9    // 连五  :50000
#define ChessSix           10   // 长连  :50000

//基础棋型得分表
static const QHash<quint8, int> UtilChessPatternScore ={{ChessNone,          0},       // 0: 无棋子{ChessSleepingOne,   0},       // 1: 眠一{ChessActiveOne,     20},      // 2: 活一{ChessSleepingTwo,   20},      // 3: 眠二{ChessActiveTwo,     120},     // 4: 活二{ChessSleepingThree, 120},     // 5: 眠三{ChessActiveThree,   720},     // 6: 活三{ChessBrokenFour,    720},     // 7: 冲四{ChessActiveFour,    4320},    // 8: 活四{ChessFive,          50000},   // 9: 连五{ChessSix,           50000}    // 10: 长连
};

在后续棋型评估中，本文可以有选择性的开启可识别的基础棋型。

    //定义搜索棋型QVector<quint8> activateChessPattern = {//活棋型ChessActiveOne,ChessActiveTwo,ChessActiveThree,ChessActiveFour,ChessBrokenFour,//眠棋型
//        ChessSleepingTwo,ChessSleepingThree,
//        ChessSleepingOne,ChessFive,ChessSix};

一些特殊棋型需要进行修正，例如双活三，三四。本文在后面会依次介绍。

1.2 局势

所谓局势，就是一方可以轻松的组织起攻势，另一方或许防守，或许反击。通常来说，棋局子力越大，局势可能会更好。由于子力评估天然不关注空间位置，注定了无法准确衡量局势。图中子力[只评估了活棋型]相同，但是两者局势截然不同。

在这里插入图片描述
AI中并没有找到合适的方案来衡量不同的局势，因此这一块暂时为空白状态。

2 实现

实现分成两个部分，一是基础棋型子力计算，二是基础棋型匹配算法。

2.1 子力计算

棋盘得分即是棋盘上所有点的子力。单点子力分成三步实现，第一步计算基础得分。第二步修正分数，修正分数的逻辑就是将活三，三四修正成一个活四。第三步禁手逻辑的处理。

//评分视角为evaluatePlayer
int GameBoard::evaluateBoard(MPlayerType evalPlayer)
{int score = 0;if (evalPlayer == PLAYER_NONE) return score;if(zobristSearchHash.getLeafTable(evalPlayer, score)){aiCalInfo.hitEvaluateBoardZobristHashCurrentTurn ++;return score;}QElapsedTimer timer;timer.start();aiCalInfo.evaluateBoardTimesCurrentTurn ++;int evaluatePlayerScore = 0;int enemyPlayerScore = 0;// 遍历整个棋盘for(const auto &curPoint : searchSpacePlayers){MPlayerType curPlayer = getSearchBoardPiece(curPoint.x(), curPoint.y());quint8 curChessPatterns[Direction4Num];getSearchBoardPatternDirection(curPoint.x(), curPoint.y(), curChessPatterns);int chessPatternCount[ChessPatternsNum] = {0};for(int direction = 0;direction < Direction4Num; ++direction){if(curPlayer == evalPlayer){evaluatePlayerScore += globalParam::utilChessPatternInfo.utilSpecialPatternScoreTable[curChessPatterns[direction]];}else{enemyPlayerScore += globalParam::utilChessPatternInfo.utilSpecialPatternScoreTable[curChessPatterns[direction]];}++ chessPatternCount[curChessPatterns[direction]];}int fixedScore = 0;//修正分数if(chessPatternCount[ChessActiveThree] > 1){//多个活三修正成一个活四fixedScore += globalParam::utilChessPatternInfo.utilSpecialPatternScoreTable[ChessActiveFour] * 3;}if(chessPatternCount[ChessBrokenFour] + chessPatternCount[ChessActiveThree] > 1 || chessPatternCount[ChessBrokenFour] > 1){//单活三单冲四修正成一个活四//双冲四修正成一个活四fixedScore += globalParam::utilChessPatternInfo.utilSpecialPatternScoreTable[ChessActiveFour] * 2;}//禁手逻辑if(globalParam::utilGameSetting.IsOpenBalanceBreaker && evalPlayer == PLAYER_BLACK){bool isTriggerBalanceBreaker = false;if(chessPatternCount[ChessActiveThree] > 1){//三三禁手(黑棋一子落下同时形成两个活三，此子必须为两个活三共同的构成子)fixedScore -= chessPatternCount[ChessActiveThree] * globalParam::utilChessPatternInfo.utilSpecialPatternScoreTable[ChessActiveThree];isTriggerBalanceBreaker = true;}if(chessPatternCount[ChessActiveFour] + chessPatternCount[ChessBrokenFour]>1){//四四禁手(黑棋一子落下同时形成两个或两个以上的冲四或活四)fixedScore -= chessPatternCount[ChessActiveFour] * globalParam::utilChessPatternInfo.utilSpecialPatternScoreTable[ChessActiveFour];fixedScore -= chessPatternCount[ChessBrokenFour] * globalParam::utilChessPatternInfo.utilSpecialPatternScoreTable[ChessBrokenFour];isTriggerBalanceBreaker = true;}if(chessPatternCount[ChessSix] > 0){//长连禁手(黑棋一子落下形成一个或一个以上的长连)fixedScore -= chessPatternCount[ChessSix] * globalParam::utilChessPatternInfo.utilSpecialPatternScoreTable[ChessSix];isTriggerBalanceBreaker = true;}if(isTriggerBalanceBreaker)fixedScore -= 5 * globalParam::utilChessPatternInfo.utilSpecialPatternScoreTable[ChessSix];}if(curPlayer == evalPlayer)evaluatePlayerScore += fixedScore;elseenemyPlayerScore += fixedScore;}UtilCalculateScore(score, evaluatePlayerScore, enemyPlayerScore,globalParam::utilGameSetting.AttackParam);zobristSearchHash.appendLeafTable(evalPlayer, evaluatePlayerScore, enemyPlayerScore);aiCalInfo.AIEvaluateBoardTime += timer.nsecsElapsed();return score;
}

2.2 棋型匹配算法

棋型匹配方案和算法都有多种。方案一般就及时匹配，增广的匹配。及时匹配是指对于一个给定的棋盘，扫描所有的行来匹配棋型。增广匹配是指利用在已知原有棋型的棋盘上增加一子后，仅扫描匹配变动行的棋型。对于算法我尝试了三种，第一种是字符串的暴力匹配，第二种是改进的位暴力匹配，第三种是AC自动机的匹配。
本文采用的是增广匹配+位暴力匹配的模式来完成的。

//这一段代码即是在原有棋盘上添加evaluatePoint后，更新evaluatePoint所在行列上点的棋型
void GameBoard::updatePointPattern(const MPoint &evaluatePoint)
{//拓展后的位置if(!isValidSearchPosition(evaluatePoint)) return;int row = evaluatePoint.x();int col = evaluatePoint.y();for(int direction = 0;direction < Direction4Num;direction ++){int dx = UtilsSearchDirection4[direction].x();int dy = UtilsSearchDirection4[direction].y();for(int i = -globalParam::utilChessPatternInfo.maxChessPatternLength + 1;i <=globalParam::utilChessPatternInfo.maxChessPatternLength-1;i ++){//更新所在方向上的棋型int tmpRow = row + dx*i;int tmpCol = col + dy*i;if(searchBoardHasPiece(tmpRow,tmpCol)){setSearchBoardPatternDirection(tmpRow,tmpCol,direction,ChessNone);updatePointPattern(tmpRow, tmpCol, direction);}}}
}

下面给出的更新MPoint(row,col)在direction上的棋型，四个方向的处理逻辑大同小异，仅以水平方向为例，循环匹配已经从大到小排好序的基础棋型直到找到一个最大的棋型后退出。匹配过程包含两部分，通过位运算提取棋盘的棋型，接着和库中棋型比较。对于比较也就是简单的几个int值的比较。

void GameBoard::updatePointPattern(MPositionType row, MPositionType col, int direction)
{//拓展后的位置MPlayerType evalPlayer = getSearchBoardPiece(row, col);int dx = UtilsSearchDirection4[direction].x();int dy = UtilsSearchDirection4[direction].y();if(getSearchBoardPiece(0,0,true) == evalPlayer)setSearchBoardBoarder(UtilReservePlayer(evalPlayer));quint16 curEvaluatePointChessPattern = ChessNone;int xx,yy;switch (direction) {case MHorizontal://水平[右]for(int i = -globalParam::utilChessPatternInfo.maxChessPatternLength+1;i <=0;i ++){int tmpRow = row + dx*i;int tmpCol = col + dy*i;if(!isValidSearchPosition(tmpRow,tmpCol,true)) continue;for(int chessPatternId = globalParam::utilChessPatternInfo.chessPatternSize-1;chessPatternId>=0; chessPatternId --){int chessPatternLength = globalParam::utilChessPatternInfo.standLengthInfo[chessPatternId];int searchLength = - i + 1;if(searchLength > chessPatternLength) continue;if(globalParam::utilChessPatternInfo.standPatternInfo[chessPatternId] <= curEvaluatePointChessPattern) continue;int mask = (1 << chessPatternLength) - 1;int Datamask = (searchBoardMask[tmpRow] >> tmpCol) & mask;int Data = (searchBoard[tmpRow] >> tmpCol) & Datamask;int cpmask = globalParam::utilChessPatternInfo.utilWhiteChessPatternMaskInfo[chessPatternId];int cp = globalParam::utilChessPatternInfo.utilWhiteChessPatternDataInfo[chessPatternId];int cpReverse = globalParam::utilChessPatternInfo.utilBlackChessPatternDataInfo[chessPatternId];if( Datamask == cpmask && ((Data == cp && evalPlayer == PLAYER_WHITE)|| (Data == cpReverse && evalPlayer == PLAYER_BLACK))){quint8 chessPattern = globalParam::utilChessPatternInfo.standPatternInfo[chessPatternId];setSearchBoardPatternDirection(row,col,direction,chessPattern);curEvaluatePointChessPattern = chessPattern;break;}}}break;}
}

http://www.ppmy.cn/news/1278676.html

相关文章

java并发编程九 ABA 问题及解决，原子数组和字段更新

java并发编程九 ABA 问题及解决，原子数组和字段更新

文章目录 ABA 问题及解决ABA 问题 原子数组不安全的数组安全的数组 字段更新器 ABA 问题及解决 ABA 问题 ABA问题是在使用CAS&#xff08;Compare and Swap&#xff09;操作时可能遇到的一种典型问题。 它指的是一个共享变量的值在操作期间从A变为B&#xff0c;然后再从B变回…
阅读更多...
LangChain入门指南：定义、功能和工作原理

LangChain入门指南：定义、功能和工作原理

LangChain入门指南&#xff1a;定义、功能和工作原理 引言LangChain是什么&#xff1f;LangChain的核心功能LangChain的工作原理LangChain实际应用案例如何开始使用LangChain 引言 在人工智能的浪潮中&#xff0c;语言模型已成为推动技术革新的重要力量。从简单的文本生成到复…
阅读更多...
Flutter笔记：Web支持原理与实践

Flutter笔记：Web支持原理与实践

Flutter笔记 Web支持原理与实践 作者&#xff1a;李俊才 &#xff08;jcLee95&#xff09;&#xff1a;https://blog.csdn.net/qq_28550263 邮箱 &#xff1a;291148484163.com CSDN&#xff1a;https://blog.csdn.net/qq_28550263/article/details/135037756 华为开发者社区…
阅读更多...
itk中的配准整理

itk中的配准整理

文章目录 Perform 2D Translation Registration With Mean Squares效果:源码: 多模态互信息配准 Perform Multi Modality Registration With Viola Wells Mutual Information效果图源码: Register Image to Another Using Landmarks 通过标记点配准图像效果图源码 Perform 2D T…
阅读更多...
npm run dev 与npm run serve的区别

npm run dev 与npm run serve的区别

npm run serve 和 npm run dev 是在开发阶段使用 npm 运行脚本的两种常见命令&#xff0c;它们的区别主要在于脚本的配置和执行方式。 npm run serve&#xff1a;通常与 Vue.js 相关的项目中使用。这个命令是在 package.json 文件中定义的一个脚本命令&#xff0c;用来启动开发…
阅读更多...
软考高级难度排行榜，哪个科目相对较容易呢？

软考高级难度排行榜，哪个科目相对较容易呢？

面对软考的5大高级科目&#xff0c;你是不是也想知道哪个科目相对较“容易”一些呢&#xff1f;今天&#xff0c;让我们一起来看看吧 软考高级科目岗位描述 首先&#xff0c;大家可以看一下官方发布的《计算机技术与软件专业技术资格(水平)考试岗位设置与岗位描述》中有关软考…
阅读更多...
arduino+pir传感器练习和lcd屏幕库练习

arduino+pir传感器练习和lcd屏幕库练习

// C code // #include <Adafruit_LiquidCrystal.h>//lcd屏幕库 库根据屏幕下载Adafruit_LiquidCrystal lcd_1(0);//定义lcd屏幕对象void setup() {pinMode(5, INPUT);//定义pir针脚lcd_1.begin(16, 2);/* begin(16, 2)&#xff1a;是 lcd_1 对象的一个方法调用&#xff…
阅读更多...
Linux: config: CONFIG_NODES_SHIFT；numa；强制挂钩

Linux: config: CONFIG_NODES_SHIFT；numa；强制挂钩

文章目录 简介config NODES_SHIFT循环接口简介 node和numa算是强挂钩关系了。和node相关的，几乎全部是numa。所以不要疑惑node和numa的强关联性。 config NODES_SHIFT Redhat提供的是10，也就是支持1024个node，但实际上用不了这么多，但是为了通用性，设置了这么大，其实可…
阅读更多...
最新文章

Copyright @ 2022~2023