好的,我的问题对于玩过棋盘游戏编程的人来说应该很熟悉,所以这里是:
- 我已经实现了 MiniMax 算法的一个变体(返回移动而不是最小/最大值)。
- 我也尝试将其设置为 alpha-beta,尽管它最终完全失败了。
所以,这是我的 MiniMax 代码:
Move* Board::miniMax(int depth)
{
return this->maxMove(1, depth);
}
Move* Board::maxMove(int ply, int depth)
{
vector<Move*> moves = this->possibleMoves();
int movesSize = moves.size();
Move* maxMove = new Move(MINUS_INF);
for (int i=0; i<movesSize; i++)
{
Move* move = moves[i];
HASHMAKE(move,this);
move->value = (ply<depth) ? (this->minMove(ply+1, depth))->value
: this->eval();
maxMove = MAXMOVE(maxMove,move);
UNHASHMAKE(move,this);
}
return maxMove;
}
Move* Board::minMove(int ply, int depth)
{
vector<Move*> moves = this->possibleMoves();
int movesSize = moves.size();
Move* minMove = new Move(PLUS_INF);
for (int i=0; i<movesSize; i++)
{
Move* move = moves[i];
HASHMAKE(move,this);
move->value = (ply<depth) ? (this->maxMove(ply+1, depth))->value
: this->eval();
minMove = MINMOVE(minMove,move);
UNHASHMAKE(move,this);
}
return minMove;
}
有什么想法可以调整上述内容以使其成为 Alpha-Beta 搜索吗?
这是我对 Alpha-Beta 转换的尝试(失败得很惨):
Move* Board::alphaBeta(int depth)
{
return this->alphaMax(1,depth,MINUS_INF,PLUS_INF);
}
Move* Board::alphaMax(int ply, int depth, int a, int b)
{
vector<Move*> moves = this->possibleMoves();
int movesSize = moves.size();
Move* maxMove = new Move(MINUS_INF);
for (int i=0; i<movesSize; i++)
{
Move* move = moves[i];
HASHMAKE(move,this);
move->value = (ply<depth) ? (this->alphaMin(ply+1, depth,a,b))->value
: this->eval();
maxMove = MAXMOVE(maxMove,move);
if (maxMove->value>=b) return maxMove;
a = MAXVAL(a,maxMove->value);
UNHASHMAKE(move,this);
}
return maxMove;
}
Move* Board::alphaMin(int ply, int depth, int a, int b)
{
vector<Move*> moves = this->possibleMoves();
int movesSize = moves.size();
Move* minMove = new Move(PLUS_INF);
for (int i=0; i<movesSize; i++)
{
Move* move = moves[i];
HASHMAKE(move,this);
move->value = (ply<depth) ? (this->alphaMax(ply+1, depth,a,b))->value
: this->eval();
minMove = MINMOVE(minMove,move);
if (minMove->value<=a) return minMove;
b = MINVAL(b,minMove->value);
UNHASHMAKE(move,this);
}
return minMove;
}
提示(避免任何误解):
该
this->eval()
函数从玩家 A 的角度返回一个分数。例如,+100 分表示该位置有利于玩家 A,而 -100 分表示该位置有利于玩家 B。MINUS_INF
并PLUS_INF
分别被定义为一些任意小的和大的值。这不像家庭作业或任何东西(如果是的话,我很可能永远不会有兴趣玩这些东西......哈哈)
Move
是一个简单的类,包含有关移动的详细信息,以及它的相应值(由eval
函数分配。HASHMAKE
并且UNHASHMAKE
只是 2 个 move-(un)making 和 move-(un)hashing 宏,应该没什么区别。MAXMOVE
定义如下:#define MAXMOVE(A,B) (((A)->value>=(B)->value)?(A):(B))
MINMOVE
定义如下:#define MINMOVE(A,B) (((A)->value<=(B)->value)?(A):(B))