首页 > 代码库 > 人机博弈-吃子棋游戏（四）搜索算法
人机博弈-吃子棋游戏（四）搜索算法
博弈树搜索技术简介：
博弈树的搜索算法，负值极大搜索，alpha-beta搜索，渴望搜索，PVS极窄窗口搜索等。通常来说，搜索算法常常和以下技术联合在一起。
如下：
1.置换表，记录已经搜索过的棋局，避免再次搜索。
2.吃子启发，优先试下能够吃对方棋子的走法。
3.杀手启发，历史启发简化版。
4.历史启发，优先试下历史统计数据得出的比较好的走法。
5.静止期搜索，继续对某些叶子结点搜索，避免水平线效应。
6.迭代加深搜索，根据搜索时间，状态。决定是否继续搜索。
有兴趣的朋友可以深入研究一下上述技术和算法。
吃子棋搜索算法：
我的程序最初的实现使用的负值极大搜索算法，之后改用alpha-beta搜索算法，后来又使用PVS极窄窗口搜索算法。
在我自己的实现里没有使用置换表，历史启发等技术。是因为吃子棋每层的走法数相对较少，所以并没有使用。
但我们知道，这些技术可以很大的提高搜索效率。
吃子棋搜索算法源码：
接下来，看看吃子棋搜索算法的源代码：
负值极大算法
1 int CNegaMaxEngine::negaMax(int depth) 2 { 3 int currentMaxScore = -20000;//init value mini 4 int score; 5 int nextMoveCount; 6 int overNum = IsGameOver(CurPosition, depth); 7 if (overNum != 0)return overNum; 8 if (depth <= 0) 9 return m_pEval->Eveluate(CurPosition, (m_nMaxDepth - depth ) % 2 );10 nextMoveCount = m_pMG->CreatePossibleMove(CurPosition, depth, (m_nMaxDepth - depth) % 2);11 for (int i = 0; i < nextMoveCount; i++)12 {13 MakeMove(&m_pMG->m_MoveList[depth][i], (m_nMaxDepth - depth) % 2);14 score = -negaMax(depth-1);15 UnMakeMove(&m_pMG->m_MoveList[depth][i]);16 if (score>currentMaxScore)17 {18 currentMaxScore = score;19 if (depth == m_nMaxDepth){20 21 m_cmBestMove = m_pMG->m_MoveList[depth][i];22 }23 }24 }25 return currentMaxScore;26 }
alpha-beta算法
int CAlphtBetaEngine::alphabeta(int depth,int alpha ,int beta){ int score; int nextMoveCount; int overNum = IsGameOver(CurPosition, depth); if (overNum != 0)return overNum; int whoTurn = (m_nMaxDepth - depth) % 2; if (depth <= 0) return m_pEval->Eveluate(CurPosition, whoTurn); nextMoveCount = m_pMG->CreatePossibleMove(CurPosition, depth, whoTurn); for (int i = 0; i < nextMoveCount; i++) { MakeMove(&m_pMG->m_MoveList[depth][i], whoTurn); score = -alphabeta(depth - 1, -beta, -alpha); UnMakeMove(&m_pMG->m_MoveList[depth][i]); if (score>alpha) { alpha = score; if (depth == m_nMaxDepth){ m_cmBestMove = m_pMG->m_MoveList[depth][i]; } } if (alpha >= beta)break; } return alpha;}
PVS算法：
1 int CPVS_Engine::PrincipalVariation(int depth, int alpha, int beta) 2 { 3 int score; 4 int Count, i; 5 BYTE type; 6 int best; 7 8 i = IsGameOver(CurPosition, depth); 9 if (i != 0)10 return i;11 12 if (depth <= 0) //叶子节点取估值13 return m_pEval->Eveluate(CurPosition, false);14 15 Count = m_pMG->CreatePossibleMove(CurPosition, depth, (m_nMaxDepth - depth ) % 2);16 17 18 MakeMove(&m_pMG->m_MoveList[depth][0], (m_nMaxDepth - depth ) % 2);19 best = -PrincipalVariation(depth - 1, -beta, -alpha);20 UnMakeMove(&m_pMG->m_MoveList[depth][0]);21 if (depth == m_nMaxDepth)22 m_cmBestMove = m_pMG->m_MoveList[depth][0];23 24 for (i = 1; i<Count; i++)25 {26 27 if (best < beta)28 {29 if (best > alpha)30 alpha = best;31 MakeMove(&m_pMG->m_MoveList[depth][i], (m_nMaxDepth - depth ) % 2);32 score = -PrincipalVariation(depth - 1, -alpha - 1, -alpha);33 if (score > alpha && score < beta)34 {35 best = -PrincipalVariation(depth - 1, -beta, -score);36 if (depth == m_nMaxDepth)37 m_cmBestMove = m_pMG->m_MoveList[depth][i];38 }39 else if (score > best)40 {41 best = score;42 if (depth == m_nMaxDepth)43 m_cmBestMove = m_pMG->m_MoveList[depth][i];44 }45 UnMakeMove(&m_pMG->m_MoveList[depth][i]);46 }47 }48 49 return best;50 }
有兴趣的同学可以看一下 王小春 编写的《PC游戏编程-人机博弈》，上述算法均参考自此书。
最后，展示一下，目前游戏雏形，嵌入视频一段。
目前最新的外链不正常，可以转至总序那篇博文看之前的视频
人机博弈-吃子棋游戏（四）搜索算法
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。