计算跳棋的最佳举动

我创建了一个checkress游戏，我希望计算机能够计算出最优的举措。以下是我迄今所做的：计算跳棋的最佳举动

public BoardS calcNextMove(BoardS bs) 
{ 
    ArrayList<BoardS>options = calcPossibleOptions(bs); 
    int max = -1; 
    int temp; 
    int bestMove = 0; 

    for(int k=0;k<options.size();k++) 
    { 
     temp = calculateNextMove2(options.get(k)); 
     if(max<temp) 
     { 
      max = temp; 
      bestMove = k; 
     } 
    } 
    return options.get(bestMove); 
} 

public int calculateNextMove2(BoardS bs) 
{ 
    int res = soWhoWon(bs); 

    if(res == 2) //pc won(which is good so we return 1) 
     return 1; 
    if(res == 1) 
     return 0; 

    ArrayList<BoardS>options = calcPossibleOptions(bs); 

    int sum = 0; 
    for(int k=0;k<options.size();k++) 
    { 
     sum += calculateNextMove2(options.get(k)); 
    } 
    return sum; 
}

我不断收到

异常在线程 “AWT-EventQueue的 - 0” java.lang.StackOverflowError的

calcPossibleOptions效果很好，它是一个返回所有可能选项的数组的函数。

BoardS是一个代表游戏板的类。

我想我必须让它更有效率，怎么样？

来源

2013-04-06 Imri Persiado

检查是否与检查员一样？ – NPE 2013-04-06 14:25:33

对不起，我会更新。 – 2013-04-06 14:28:04

也许“calculateNextMove2”中的递归太深了？任何想法在结束条件发生前通常会调用多少次（我会说很多...）？ – 2013-04-06 14:42:35

“calculateNextMove2（）”上的递归会运行得太深，这就是为什么你会得到一个StackOverFlow。如果你期望游戏运行到最后（除非相对接近真正的胜利），这可能需要很长时间。像国际象棋一样（我有更多的经验），一个引擎可能会走20步，然后才可能走到目前为止所发现的。如果你从一场国际象棋比赛开始就运行它......它可以在当前的技术上运行数百年（并且还不能真正说出胜利的第一步是什么）。也许只是尝试10或20步深？（它仍然会击败大多数人类，并且仍然可能被归类为“最佳举动”）。和国际象棋一样，你将难以评估一个职位的好坏（通常以物质优势和位置优势的结合来计算）。这是棘手的部分。注意：奇努克项目已经完成了你想要实现的目标 - 它已经“击败”了跳棋游戏（没有这样的事情存在于国际象棋编辑中：Magnus Carslen已经为所有意图和目的“游戏”了游戏）。

看到：Alpha-beta pruning （它可能会有所帮助）

而且，这里是（老气）的纸我关于这个问题的看到：

Graham Owen 1997 Search Algorithms and Game Playing （也可能是有用的）

还要注意返回导致“获胜”的第一步是'天真' - 因为如果对手不以非常特殊的胜利进行比赛，对手将获得优势，这可能是完全不可能的一系列动作 - 例如为傻瓜玩伴侣或学者在国际象棋伴侣...（快但很容易处罚）

来源

2013-04-06 15:07:31

假设我在20步之后停止，现在我怎么知道谁处于更好的位置？我应该返回什么？我知道混合最大/ alpha测试版，但你可以看到我甚至不使用游戏树..我更喜欢x的动作进行得很深，但它又将我引向我上面写的那些 – 2013-04-06 15:32:51

这正是你现在面临的问题......认真。这是目前最大的挑战。也许只是开始，你可以看到谁是最重要的“上”来判断一个位置 - 即开始移动x（不管之后的移动）玩家往往是2个动作之后......并没有其他开始提高这种“优势”。 – 2013-04-06 15:37:26

甚至20也许很高......可能会发现实际上有多少种移动可能性。（它可能是某个地方像（4 * 2）^ 20 - 或2^22 - 相当大的数字） – 2013-04-06 15:38:50

您需要找到一种替代MinMax的方法，即使是最有可能的alpha-beta修剪方法，因为董事会过于庞大，会造成太多可能的举动，并会出现反击。这导致堆栈溢出。

我很惊讶地看到，为Tic-Tac-Toe制作完整的决策树没有溢出自己，但恐怕我对AI规划还是不够了解，或者是有其他算法来解决这些问题，以帮助你超越。

来源

2013-04-06 15:03:45

计算跳棋的最佳举动

回答

相关问题