这个博弈树代码,不带剪枝的。问题就是当算到棋盘满的时候,他总是会选择一个和局,为什么会这样?
BoardOptimalMove BoardTree::getOptimalMove(const unsigned int depth)
{
if(root==nullptr)
{
return BoardOptimalMove(); //如果重复下子会返回一个root为nullptr的树,判断如果成立的话会返回一个ILLEGAL的move
}
if((depth==0)||(root->board.isFinished()==true)) //如果算完了或者没位了
{
BoardCoordinate a=BoardCoordinate(0,0);
return BoardOptimalMove(root->board.getBoardScore(),a);//返回当前棋盘分数
}
int estimate;
if(root->board.getCurPlayer()==X)//判断是应该选最大还是最小
{
estimate=-100000000;
}
else
{
estimate=100000000;
}
BoardOptimalMove bestMove;
for (int i =0; i<BOARD_SIZE; i++)
{
for (int t = 0; t<BOARD_SIZE; t++)
{
BoardCoordinate a=BoardCoordinate(i,t);
BoardTree* b=getSubTree(a);
BoardOptimalMove childMove =b->getOptimalMove(depth - 1);
if (childMove.score == ILLEGAL) //判断是否在重复下子,如果是就跳到下一个能下的位置
{
continue;
}
if(root->board.getCurPlayer()==X)判断是应该选最大还是最小
{
if(childMove.score>estimate)
{
estimate=childMove.score;//更改最好的分
bestMove=BoardOptimalMove(estimate,a);//记录目前最好的下棋地址
}
}
else
{
if(childMove.score<estimate)
{
estimate=childMove.score;//更改最好的分
bestMove=BoardOptimalMove(estimate,a);//记录目前最好的下棋地址
}
}
b->~BoardTree();
}
}
return bestMove; //返回当前整个棋盘最好的下棋地址
}
引用chatgpt部分指引作答:
在没有剪枝的情况下,当博弈树的搜索深度达到棋盘已经下满的状态时,博弈树的搜索就会停止。在这种情况下,由于博弈树搜索已经结束,所以它会直接返回当前棋盘的得分。
对于井字棋游戏而言,如果在搜索深度达到棋盘已经下满的状态时,没有任何一方达成胜利,那么就会判断为和局。因此,当博弈树搜索到棋盘已经下满的状态时,它会返回一个和局,而不是任何一方获胜。
因此,当博弈树搜索到棋盘已经下满的状态时,返回和局的结果是正常的。但是,需要注意的是,由于没有剪枝,这种搜索方式可能会导致搜索时间很长。
注:本文以一个例子来演示广义表的基本操作,含有一个头文件《GList.h》和一个测试源文件《main.cpp》