关于算法的一点探讨
本人一直在想自己编写出一个优良的五子棋AI
自行设计了一个五子棋的棋势分析
感觉还不错，基本解决了，攻和堵得问题
现在把我卡住的，就是关于递归的部分
只能思考一层的五子棋，无疑是很差劲的，
我的设计思想是，从今后的5步中找出必胜步骤来
既然是必胜的步骤，减枝的过程，当然很凶残，基本的原则是，敌方如果还可以走而不失败，就剪去整个枝条。换句话说，就是如果电脑让自己走一步（假设该步为a)，然后“思考”敌方的行动，如果5步内敌方仍然存活,则放弃对a的思索（即使a的子孙还没有被遍历完）
思想似乎没错，设计时候却遇到了一个不可逾越的问题-----对于整棵树的存储，非常迷茫。另外，减枝的代码不知道如何实现。判断语句写了N多，还是乱七八糟，头脑一团迷糊，望高人指点
问题点数：100、回复次数：7Top
1 楼LordSimon（lordsimon@x.cn）回复于 2005-07-03 18:02:44 得分 0
用邻接表存的话，应该是可行的。Top
2 楼zhuangfangjun（哈哈）回复于 2005-07-03 18:23:15 得分 0
这个注意不错Top
3 楼killer1984（人在天涯）回复于 2005-07-03 19:08:02 得分 30
普通AlphaBeta剪枝的代码，基本思想基于极大极小搜索，在极大搜索时，若极小层某节点A估值比下一极小节点B产生的极大子节点中的某一个还大，那么可以肯定C估值比B小，于是可以不再对C的其余子节点进行估值；极小搜索时亦然。
int CFAlphaBetaEngine::FAlphaBeta(int depth, int alpha, int beta)
{
int current = -20000 ;
int score;
int Count,i;
BYTE type;
i = IsGameOver(CurPosition, depth);
if (i != 0)
return i;
if (depth <= 0) //叶子节点取估值
return m_pEval->Eveluate(CurPosition, (m_nMaxDepth-depth)%2);
Count = m_pMG->CreatePossibleMove(CurPosition, depth, (m_nMaxDepth-depth)%2);
for (i=0;i<Count;i++)
{
type = MakeMove(&m_pMG->m_MoveList[depth][i]);
score = -FAlphaBeta(depth - 1, -beta, -alpha);
UnMakeMove(&m_pMG->m_MoveList[depth][i],type);
if (score > current)
{
current = score;
if(depth == m_nMaxDepth)
m_cmBestMove = m_pMG->m_MoveList[depth][i];
if (score > alpha)
alpha = score;
if (score >= beta) //beta剪枝
break;
}
}
return current;
}Top
4 楼killer1984（人在天涯）回复于 2005-07-03 19:12:15 得分 30
整个执行过程就是一个搜索树的深度优先遍历过程，并不需要对整棵树进行存储，只需要最大（最小）期望存储估值分数和当前局势就行了。需要注意的是遍历中间产生的回溯，必须有好的方法保证回溯的顺利进行。Top
5 楼arrowcy（长弓手）回复于 2005-07-08 15:07:04 得分 30
我估计楼主就是在怎么存储那个决策树卡住了吧
如楼上所说，那个树是没有必要存储的，只需要对树进行深度优先搜索，如果搜索过程中遇到能够提前估计出不可行的分枝，就不深入进去，否则就一直搜索到叶结点，另外要用一个数据结构来保存目前搜索到的最好解，其他就没有什么了吧Top
6 楼jixingzhong（瞌睡虫·星辰）回复于 2005-07-24 20:04:36 得分 10
用邻接表
由于 楼主你的算法的原因
表的简化会很快
应该不是很麻烦才是...Top
7 楼caocheng8230（学C++而不知疲倦）回复于 2005-08-09 19:53:50 得分 0
upTop
相关问题
关键词
得分解答快速导航
相关链接
广告也精彩
反馈
