雪崩版播棋(Mancala)Minimax算法问题:代码输出错误走法
雪崩版播棋(Mancala)Minimax算法问题排查
我正在用Minimax算法开发雪崩版播棋机器人,程序能正常运行但经常输出糟糕的走法(比如选择空格落子)。说明一下:我没有给Minimax算法添加alpha-beta剪枝是有意设计,并非代码错误。
以下是我的实现代码:
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);
代码基于文本编辑器运行,结果直接打印到控制台,每次仅处理单个棋盘状态。
举个具体的测试案例:
初始棋盘状态:
[4, 4, 4, 4, 4, 4, 0, 4, 4, 4, 4, 4, 4, 0]
算法选择移动数组第4位的棋子,得到的结果棋盘为:
[1, 6, 6, 6, 0, 1, 3, 6, 1, 6, 6, 0, 6, 0]
但存在明显更优的走法(比如选择索引2的位置),我无法理解算法为何做出这样的选择。
我对Minimax算法经验不足,希望得到问题排查的思路。
内容的提问来源于stack exchange,提问作者human
相关产品推荐
相关产品推荐

