带有 Alpha Beta 剪枝的 MiniMax 黑白棋不工作
MiniMax with Alpha Beta Pruning for Othello not working
我有以下用于黑白棋游戏的 alpha beta minimax 实现。不知何故,这从来都不是 return 采取的正确行动。似乎 return 我在函数 (0, 0) 中放入的默认操作和 -32768 的辅助值,这意味着它在 MAX 子例程中被修剪。关于我可以改进什么以及如何解决这个问题的任何提示?
注意:我已经确定大部分后继者 return 都得到了正确的编辑。目前的最大深度是 8。计算机玩家的 pn(玩家编号)是 1,人类玩家的是 0。第一阶段,0,是 MINIMAX_MAX。 Alpha 和 Beta 最初分别设置为 INT_MIN 和 INT_MAX。
mm_out minimax(Grid& G, int alpha, int beta, Action& A, uint pn, uint depth, bool stage) {
if (G.check_terminal_state() || depth == MAX_DEPTH) {
#ifdef DEBUG
cout << "best action: (" << A.get_x() << ", " << A.get_y() << ")\n";
#endif
return mm_out(A, G.get_utility(pn));
}
// add end game score total here
#ifdef DEBUG
if (stage == MINIMAX_MAX) {
cout << "max " << alpha << " " << beta << "\n";
}
else {
cout << "min " << alpha << " " << beta << "\n";
}
#endif
set<Action> succ_temp = G.get_successors(pn);
for (Action a : succ_temp) {
#ifdef DEBUG
cout << a.get_x() << " " << a.get_y() << '\n';
#endif
Grid gt(G);
a.evaluate(gt);
}
set<Action, action_greater> successors(succ_temp.begin(), succ_temp.end());
#ifdef DEBUG
Player p(0, "minimaxtest");
G.display(p);
int test;
cin >> test;
#endif
// if no successor, that player passes
if (successors.size()) {
for (auto a = successors.begin(); a != successors.end(); ++a) {
Grid gt(G);
gt.do_move(pn, a->get_x(), a->get_y(), !PRINT_ERR);
Action at = *a;
mm_out mt = minimax(gt, alpha, beta, at, pn ^ 1, depth + 1, !stage);
int temp = mt.val;
// A = mt.best_move;
if (stage == MINIMAX_MAX) {
if (alpha < temp) {
alpha = temp;
A = *a;
#ifdef DEBUG
cout << "Current action: (" << A.get_x() << ", " << A.get_y() << ") alpha = " << alpha << "\n";
#endif
}
if (alpha >= beta) {
#ifdef DEBUG
cout << "pruned at max\n";
#endif
return mm_out(A, beta);
}
}
else {
if (beta > temp) {
beta = temp;
A = *a;
#ifdef DEBUG
cout << "Current action: (" << A.get_x() << ", " << A.get_y() << ") beta = " << beta << "\n";
#endif
}
if (alpha >= beta) {
#ifdef DEBUG
cout << "pruned at min\n";
#endif
return mm_out(A, alpha);
}
}
}
return mm_out(A, (stage == MINIMAX_MAX) ? alpha : beta);
}
else {
cout << "no successor\n";
return mm_out(A, (stage == MINIMAX_MAX) ? (std::numeric_limits<int>::max() - 1) : (std::numeric_limits<int>::min() + 1));
}
}
效用函数:
int Grid::get_utility(uint pnum) const {
if (pnum)
return wcount - bcount;
return bcount - wcount;
}
您应该按值(而不是按引用)传递 alpha
/ beta
参数:
mm_out minimax(Grid& G, int alpha, int beta, Action& A, uint pn, uint depth, bool stage)
每个节点将 alpha 和 beta 值传递给它的 children。 children 然后根据轮到谁更新他们自己的 副本 的 alpha 或 beta 值以及 return 该节点的最终评估。然后用于更新 parent.
的 alpha 或 beta 值
我有以下用于黑白棋游戏的 alpha beta minimax 实现。不知何故,这从来都不是 return 采取的正确行动。似乎 return 我在函数 (0, 0) 中放入的默认操作和 -32768 的辅助值,这意味着它在 MAX 子例程中被修剪。关于我可以改进什么以及如何解决这个问题的任何提示?
注意:我已经确定大部分后继者 return 都得到了正确的编辑。目前的最大深度是 8。计算机玩家的 pn(玩家编号)是 1,人类玩家的是 0。第一阶段,0,是 MINIMAX_MAX。 Alpha 和 Beta 最初分别设置为 INT_MIN 和 INT_MAX。
mm_out minimax(Grid& G, int alpha, int beta, Action& A, uint pn, uint depth, bool stage) {
if (G.check_terminal_state() || depth == MAX_DEPTH) {
#ifdef DEBUG
cout << "best action: (" << A.get_x() << ", " << A.get_y() << ")\n";
#endif
return mm_out(A, G.get_utility(pn));
}
// add end game score total here
#ifdef DEBUG
if (stage == MINIMAX_MAX) {
cout << "max " << alpha << " " << beta << "\n";
}
else {
cout << "min " << alpha << " " << beta << "\n";
}
#endif
set<Action> succ_temp = G.get_successors(pn);
for (Action a : succ_temp) {
#ifdef DEBUG
cout << a.get_x() << " " << a.get_y() << '\n';
#endif
Grid gt(G);
a.evaluate(gt);
}
set<Action, action_greater> successors(succ_temp.begin(), succ_temp.end());
#ifdef DEBUG
Player p(0, "minimaxtest");
G.display(p);
int test;
cin >> test;
#endif
// if no successor, that player passes
if (successors.size()) {
for (auto a = successors.begin(); a != successors.end(); ++a) {
Grid gt(G);
gt.do_move(pn, a->get_x(), a->get_y(), !PRINT_ERR);
Action at = *a;
mm_out mt = minimax(gt, alpha, beta, at, pn ^ 1, depth + 1, !stage);
int temp = mt.val;
// A = mt.best_move;
if (stage == MINIMAX_MAX) {
if (alpha < temp) {
alpha = temp;
A = *a;
#ifdef DEBUG
cout << "Current action: (" << A.get_x() << ", " << A.get_y() << ") alpha = " << alpha << "\n";
#endif
}
if (alpha >= beta) {
#ifdef DEBUG
cout << "pruned at max\n";
#endif
return mm_out(A, beta);
}
}
else {
if (beta > temp) {
beta = temp;
A = *a;
#ifdef DEBUG
cout << "Current action: (" << A.get_x() << ", " << A.get_y() << ") beta = " << beta << "\n";
#endif
}
if (alpha >= beta) {
#ifdef DEBUG
cout << "pruned at min\n";
#endif
return mm_out(A, alpha);
}
}
}
return mm_out(A, (stage == MINIMAX_MAX) ? alpha : beta);
}
else {
cout << "no successor\n";
return mm_out(A, (stage == MINIMAX_MAX) ? (std::numeric_limits<int>::max() - 1) : (std::numeric_limits<int>::min() + 1));
}
}
效用函数:
int Grid::get_utility(uint pnum) const {
if (pnum)
return wcount - bcount;
return bcount - wcount;
}
您应该按值(而不是按引用)传递 alpha
/ beta
参数:
mm_out minimax(Grid& G, int alpha, int beta, Action& A, uint pn, uint depth, bool stage)
每个节点将 alpha 和 beta 值传递给它的 children。 children 然后根据轮到谁更新他们自己的 副本 的 alpha 或 beta 值以及 return 该节点的最终评估。然后用于更新 parent.
的 alpha 或 beta 值