Java 递归博弈论取得最佳进展

Question

我的任务是编写一个函数，为计算机找到最佳的移动方式，作为回溯算法的一部分。我的解决方案找到了一个可行的答案，但不是最佳答案。我无法找到一种方法来保留分配给不同选项的值，这些值在下一次递归调用期间不会被重置。因此，如果经过第 1、2、3、4 步以及第 2 步和第 3 步都得出可获胜的解决方案，则即使 2 是更好的选择，也将采用 3 而不是 2。我可以明白为什么在我的代码中会发生这种情况，但我似乎无法思考如何修复它。我尝试使用胜利和总胜利变量，但这似乎不起作用。因此，该函数再次致力于寻找可获胜的途径，但并不总是选择最佳的可获胜的 Action 。任何帮助将不胜感激

Move bestMove = null;


    int totalwins= 0;
    public Move findbest(Game g) throws GameException {
        int wins = 0;

        PlayerNumber side = g.SECOND_PLAYER;
        PlayerNumber opp = g.FIRST_PLAYER;
        Iterator<Move> moves = g.getMoves();
        while(moves.hasNext()){

            Move m = moves.next();
            //System.out.println(m + " Totalwins " + totalwins);
            Game g1 = g.copy();
            g1.make(m);
            //System.out.println("Turn: " + g.whoseTurn());
            if(!g1.isGameOver()){
                bestMove = findbest(g1);
            }else{
                if(g1.winner() == side ){
                    bestMove = m;
                    wins++;
                }else if(g1.winner() == opp){
                    wins--;
                }
                if(wins > totalwins){
                    totalwins += wins;
                    bestMove = m;
                }
            }
            if(bestMove == null){//saftey so it won't return a null if there is no winnable move.  
                bestMove = m;
            }
        }
        //System.out.println("Totalwins = " + totalwins);
        return bestMove;
    }

Answer 1

正如评论中所述，您需要某种评级系统来确定哪一步确实是最好的。

然后，创建一个全局变量 Move bestMove，而不是让 findBest 返回“最佳移动”，只需让它检查当前移动是否获胜，如果是，还检查其评级是否优于当前 bestMove。 如果这两个条件都为真，则将当前移动分配给 bestMove。