我一直在用一种极小极大算法制作一个曼卡拉机器人.它对第一个比特有效,但它通常只给出一个空格上的输出.有谁知道如何解决这个问题,让它发挥得很好?

以下是我的代码:

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] 

...它告诉我将数组第四个点上的一个从右边移到第五个点,这给出了以下输出:

[5, 0, 5, 5, 0, 1, 4, 6, 6, 1, 5, 5, 5, 0]

还有更好的可能的移动(比如索引2),我不知道为什么算法 Select 这个.此外,我正在使用的Minimax算法没有使用阿尔法-贝塔修剪,这是有意的,而且不仅仅是代码中的错误.

推荐答案

您的实施中存在以下问题:

  • 请注意,在minimax中,increment的第一个调用只能返回2或3.这是因为只要停止条件不为真,increment就会继续进行递归调用.当停止is为真时,它返回2或3(在re为假的情况下).因此,minimaxneverdepth-1进行递归调用!我建议按如下方式解决这个问题.当为tboard == 3时,不要停止递归.这是当一个回合"正常"结束时的情况,即没有获得额外回合的权利.在这种情况下,没有理由停止递归.因此,在这种情况下进行递归调用,而不是将Eval设置为-13.
  • if(board[(bltif + ltif + a)%14] == 1 && !re)是个bug这应该是一个else,因为你不想用3覆盖ans,当它已经被设置为2时,但是玩家的store 碰巧有1块石头.在else的情况下,你可以确定这个条件是真的,所以不需要判断它.或者,你可以在if块中使用return ans,所以没有用3重复ans的风险.
  • maxEval = [Math.max(Eval, maxEval[0]),avail[i],tboard];是错误的,因为即使Evalworse,它也会更新maxEval的第二个和第三个条目.这样,你就失go 了已经与最好的分数相关联的移动.当EvalmaxEval[0]更好时,您应该只更新maxEval[1]maxEval[2].(我还建议使用纯对象而不是array.使用普通对象,我们可以为这三个组件指定有意义的名称).
  • final = [maxEval[1], maxEval[2]];是错误的,因为它还在递归树中的更深层次执行,覆盖了已经在递归树顶部注册的结果,而这才是您真正感兴趣的结果.这里更深层次的问题是,final不应该是一个全局变量,而minimax正在改变它,因为它是一个"副作用".这是一种糟糕的做法.相反,拥有minimaxreturn个这样的信息.
  • 对于最大化和最小化用户,如果他们走得很好(因为他们实现了额外的回合),您的代码会给出13分.这不可能是正确的.最小化用户的值应该是-13,否则它实际上将作为bad移动!

其他 comments :

  • 使用更具描述性的变量名称.例如,numStones而不是bltif.
  • 避免重复相同的表达式,如(bltif + ltif + a)%14.相反,使用一个变量来表示该值.你应该只需要在你的代码中出现一次% 14操作.
  • 避免在同一个黑板上两次拨打increment,只为了从其中获得两条不同的信息,基于re.如果您只是在调用increment之前将board.slice()存储在一个变量中,那么在调用increment之后,您就已经拥有了变异的板.这样,您就不需要将re设置为True的调用,并且可以go 掉该参数.
  • 避免使用"magic numbers".例如,应该解释返回值2和3,最好将其替换为具有描述性名称的常量.然而,在这种特殊情况下,我们可以使用布尔值(带有描述性名称),它指示玩家是否有权进行额外的移动.
  • 不要在较大的表达式中执行赋值(如ans = board).将这样的表达式转换为赋值,其中右侧的表达式具有必要的逻辑.
  • 变量使用camelCase,所以不要使用Eval作为名称.我建议使用score(因为eval已经用于本机函数).
  • 要确定avail,不要使用.map,而是立即使用.filter.这样您就不需要虚拟的-1值了.

已更正的代码

以下是我在应用上述更正和建议时得到的代码:

// 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号坑.我玩这个游戏还不够,无法判断这是否真的是最好的走法.

Javascript相关问答推荐

如何使用React渲染器放置根dis?

如何编辑代码FlipDown.js倒计时?

可以的.是否可以在不预编译的情况下使用嵌套 Select 器?

Klaro与Angular的集成

字节数组通过echo框架传输到JS blob

在服务器上放置了Create Reaction App Build之后的空白页面

实现JS代码更改CSS元素

如何控制Reaction路由加载器中的错误状态?

使用Java脚本导入gltf场景并创建边界框

从Nextjs中的 Select 项收集值,但当单击以处理时,未发生任何情况

如何在Svelte中从一个codec函数中调用error()?

400 bad request error posting through node-fetch

Use Location位置成员在HashRouter内为空

同一类的所有div';S的模式窗口

使用auth.js保护API路由的Next.JS,FETCH()不起作用

VSCode中出现随机行

图表4-堆叠线和条形图之间的填充区域

Clip-Path在网页浏览器(Mozilla、Edge、Chrome)上不能正常工作,但在预览版Visual Code Studio HTML、CSS、JS上却能很好地工作

JavaScript&;Reaction-如何避免在不使用字典/对象的情况下出现地狱?

如何压缩图像并将其编码为文本?