我一直在使用极小极大算法制作一个曼卡拉机器人。它适用于第一位，但通常只是在空白处提供输出。有人知道如何解决这个问题，使其发挥良好吗？
这是我的代码：
let final;
function increment(board, ltif, player, re) {
let a = 0;
for(let i = 0; i < board[ltif]; i++) {
if((player && (ltif+i+a+1)%14 == 13) || (!player && (ltif+i+a+1)%14 == 6)) {
a += 1;
}
board[(ltif + i + a + 1)%14] += 1;
}
const bltif = board[ltif];
board[ltif] = 0;
let ans;
board[(bltif + ltif + a)%14] == 1 || (bltif + ltif + a)%14 == 6 || (bltif + ltif + a)%14 == 13 ? ans = board : ans = increment(board, (bltif + ltif + a)%14, player);
if(((bltif + ltif + a)%14 == 6 || (bltif + ltif + a)%14 == 13) && !re) {
ans = 2;;
}
if(board[(bltif + ltif + a)%14] == 1 && !re) {
ans = 3;
}
return ans;
}
function minimax(board, depth, player) {
if(board[6] > 24) {
return 15;
}else if(board[13] > 24) {
return -15;
}else if(board[6] == 24 && board[13] == 24) {
return 0;
}else if(depth === 0) {
return Math.floor((board[6]-board[13])/2);
}
let avail = board.map((element, index) => (element !== 0 && ((index < 6 && player)|| (index < 13 && index > 6 && !player)) ? index : -1)).filter(element => element !== -1);
if(player) {
let maxEval = [-Infinity];
for(let i = 0; i < avail.length; i++) {
let tboard = increment(board.slice(), avail[i], player, false);
let Eval;
if(tboard == 2) {
Eval = 13;
tboard = increment(board.slice(), avail[i], player, true);
}else if(tboard == 3) {
Eval = -13;
tboard = increment(board.slice(), avail[i], player, true);
}else{
Eval = minimax(tboard, depth - 1, false);
}
maxEval = [Math.max(Eval, maxEval[0]),avail[i],tboard];
}
final = [maxEval[1], maxEval[2]];
return maxEval[0];
}else{
let minEval = +Infinity;
for(let i = 0; i < avail.length; i++) {
let tboard = increment(board.slice(), avail[i], player, false);
let Eval;
if(tboard == 2) {
Eval = 13;
tboard = increment(board.slice(), avail[i], player, true);
}else if(tboard == 3) {
Eval = -13;
tboard = increment(board.slice(), avail[i], player, true);
}else{
Eval = minimax(tboard, depth - 1, false);
}
minEval = Math.min(Eval, minEval);
}
return minEval;
}
}
minimax([
5, 0, 5, 5, 5, 0,
3, 5, 5, 0, 5, 5,
5, 0
], 9, true);
console.log(final);
它用完了基于文本的编辑器，所以这就是为什么输出进入控制台并且它只检查一个板，然后你必须输入另一个板。另外澄清一下，这是曼卡拉的雪崩版本。
我没有太多使用极小极大算法的经验，所以如果有人对这个问题有任何见解，那将会非常有帮助。
其中一个例子是，当给定棋盘状态时：
[5, 0, 5, 5, 5, 0, 3, 5, 5, 0, 5, 5, 5, 0]
...它告诉我将数组的第 4 个位置上的那个移动到右侧 5 个位置，从而给出以下输出：
[5, 0, 5, 5, 0, 1, 4, 6, 6, 1, 5, 5, 5, 0]
还有更好的可能移动（如索引 2），我不知道为什么算法选择这个。另外，我使用的极小极大算法没有使用 alpha-beta 剪枝，这是有意的，而不仅仅是代码中的错误。
您的实施中存在以下问题：
minimaxincrementincrementreminimaxdepth-1tboard == 3Evalif(board[(bltif + ltif + a)%14] == 1 && !re)elseanselsereturn ansif覆盖
ansmaxEval = [Math.max(Eval, maxEval[0]),avail[i],tboard];maxEval更差，它也会更新
Eval 的第二个和第三个条目。这样你就失去了已经与最好成绩相关的动作。仅当 maxEval[1]maxEval[2]EvalmaxEval[0]final = [maxEval[1], maxEval[2]];finalminimaxminimaxnumStonesbltif(bltif + ltif + a)%14% 14incrementreboard.slice()incrementincrementreans = boardcamelCaseEvalscoreevalavail.map.filter这是我在应用上述更正和建议时最终得到的代码：
// Don't use magic values, but instead define constants with meaningful names:
const STORE = { false: 13, true: 6 }; // Per player: the index of their store
const STORES = new Set(Object.values(STORE));
// Per player: the indices of their pits
const PITS = { false: [7, 8, 9, 10, 11, 12], true: [0, 1, 2, 3, 4, 5] };
const NUM_STONES = 48;
const GOOD_SCORE = NUM_STONES / 4 + 1; // Better score than max heuristic score
const MAX_SCORE = GOOD_SCORE + 1; // Overall best possible score
// The function increment returns a boolean that is true when the move ended with a stone
// in the player's store, giving them a right to an extra move.
// The given board is mutated, so the caller can see the effect of the move in that board.
function increment(board, startPit, player) {
const numStones = board[startPit];
let lastPit = startPit;
for (let i = 1; i <= board[startPit]; i++) {
// We can use a conditional inline expression to decide to add an extra 1 or not.
lastPit = (lastPit + 1 + (lastPit + 1 == STORE[!player])) % board.length;
board[lastPit]++;
}
board[startPit] = 0;
// There are three cases:
if (lastPit === STORE[player]) { // Extra turn!
return true;
}
if (board[lastPit] == 1) { // Normal move ended.
return false;
}
// The turn is not finished yet; continue...
return increment(board, lastPit, player);
}
function minimax(board, depth, player) {
if (board[STORE[true]] * 2 > NUM_STONES) {
// Maximizing player has more than half of the stones, so they won the game.
return MAX_SCORE;
} else if (board[STORE[false]] * 2 > NUM_STONES) {
// Minimizing player has more than half of the stones, so they won the game.
return -MAX_SCORE;
} else if (board[STORE[true]] + board[STORE[false]] == NUM_STONES) {
// All stones are in the stores, and both players have an equal amount: it's draw
return 0;
} else if (depth === 0) {
// Search must stop here. Give a heuristic value:
return Math.floor((board[STORE[true]] - board[STORE[false]]) / 2);
}
// Get the player's own pits that have at least one stone in it:
const availablePits = PITS[player].filter(pit => board[pit]);
if (player) { // Maximizing player
let best = { score: -Infinity };
for (const pit of availablePits) {
const newBoard = board.slice(); // Keep a reference to the new board
const extraTurn = increment(newBoard, pit, player);
const score = extraTurn ? GOOD_SCORE // We get an extra turn (good!), so we will not look deeper
// Otherwise: no extra turn. Continue the recursion.
: minimax(newBoard, depth - 1, false).score; // Get score component
if (score > best.score) {
// Only make updates when the score is better
best = { score, pit, board: newBoard };
}
}
return best; // Don't alter a global. Just return complete information: {score, pit, board}.
} else {
let best = { score: +Infinity };
for (const pit of availablePits) {
const newBoard = board.slice();
const extraTurn = increment(newBoard, pit, player);
const score = extraTurn ? -GOOD_SCORE // Minimizing user wants a negative value here!
: minimax(newBoard, depth - 1, false).score;
if (score < best.score) {
best = { score, pit, board: newBoard };
}
}
return best;
}
}
// Minimax should *return* the information instead of setting a global variable.
const { score, pit, board } = minimax([
// Layout was confusing. This seems clearer:
5, 0, 5, 5, 5, 0, 3,
5, 5, 0, 5, 5, 5, 0
], 9, true);
console.log(`The best move is from pit ${pit}. It got score ${score}, and leads to this board: ${board}`);算法现在返回最佳走法，坑号 2。我玩这个游戏的时间不够长，无法判断这是否真的是最佳走法。