北京移动官网网站建设,怎么建设游网站主页,网络托管公司,长春seo全网营销引子
静态棋盘的评估是棋力的一个很重要的体现#xff0c;一个优秀的基于博弈树搜索的AI往往有上千行工作量#xff0c;本文没有做深入讨论#xff0c;仅仅写了个引子用来抛砖引玉。 评估一般从两个角度入手#xff0c;一个是子力#xff0c;另一个是局势。
1 评估维度 …引子
静态棋盘的评估是棋力的一个很重要的体现一个优秀的基于博弈树搜索的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 QHashquint8, 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: 长连
};在后续棋型评估中本文可以有选择性的开启可识别的基础棋型。 //定义搜索棋型QVectorquint8 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.maxChessPatternLength1;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;chessPatternId0; 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;}
}
