Java递归博弈理论得到最好的移动

我已经被授权编写一个函数来寻找计算机作为回溯算法的一部分的最佳步骤。我的解决方案找到了一个可胜任的答案，但不是最佳答案。我很难找出一种方法来保持赋值给不同选项的值，而这些值在下次递归调用时不会被重置。所以如果它经历了1,2,3,4和2和3的移动都会导致一个可赢得的解决方案，那么即使2是更好的选择，它也会花费3而不是2。我可以看到为什么在我的代码中发生这种情况，但我似乎无法考虑如何解决它。我尝试了wins和total wins变量，但这似乎没有奏效。因此，该功能再一次起到了寻找可胜利的途径的作用，但并不总是能够选出最佳的赢球动作。任何帮助将不胜感激Java递归博弈理论得到最好的移动

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; 
    }

来源

2015-11-21 Peter3

为了确定最好的东西，你必须有一个排名系统。如何比另一个更好？你必须有一个明确的方式来比较移动。那么，它将取决于游戏的类型。在一些游戏中，可以通过某种算法来计算最佳移动。在其他情况下，您最好计算所有可能的移动，然后对其进行排序。你的情况似乎是后者。要用递归回溯，您必须找到一种方法来确定，在每次递归调用时，哪个移动最好，然后返回该移动。 – afsantos

我希望能够想出一个方法来计算每次移动可以实现的可赢状态的数量。然后，哪个曾经移动的可赢取状态将会返回 – Peter3

Peter3，看一下基于递归和基于排名/权重的算法，如A *（发音为“A，Star”，这是一种常见于游戏AI中的路径寻找算法）。它可能会给你（非常）有用的提示和/或灵感。这也与afsantos所说的有关，也是一个例子。希望能帮助到你！ – XenoRo

正如在评论中所述，你需要有某种评级制度，以确定哪种举动真的是最好的。

然后，做一个全局变量Move bestMove和，而不必findBest返回“最好的举措”，简单地把它检查是否当前的举动是可以赢的，如果是这样，也请检查其评级比当前的要好bestMove.如果这两个条件都是真的，那么将当前移动分配给bestMove.

来源

2015-11-21 20:30:49 Nerdizzle

你可以跟踪排名最高的移动，而不需要迭代列表 –

对不起，刚刚写了一个类似的算法，我确实需要将所有返回的值存储在一个'ArrayList'中并迭代他们，所以我的想法是在错误的地方。编辑我的答案。 – Nerdizzle

我有bestMove的全局变量已经在上面。我尝试用wins和totalwins变量设置权重，并将bestMove指定为两者中较高的一个。我很感激帮助。我接近完成它在我的桌面上，我会发布我最终做的 – Peter3

Java递归博弈理论得到最好的移动

回答

相关问题