为什么我的alpha-beta修剪的实现不起作用？

我使用维基百科伪立足反对 -为什么我的alpha-beta修剪的实现不起作用？

function alphabeta(node, depth, α, β, Player)   
    if depth = 0 or node is a terminal node 
     return the heuristic value of node 
    if Player = MaxPlayer 
     for each child of node 
      α := max(α, alphabeta(child, depth-1, α, β, not(Player)))  
      if β ≤ α 
       break        (* Beta cut-off *) 
     return α 
    else 
     for each child of node 
      β := min(β, alphabeta(child, depth-1, α, β, not(Player)))  
      if β ≤ α 
       break        (* Alpha cut-off *) 
     return β

，这里是我的java实现 -

private int alphabeta(Node newNode, int depth, int alpha, int beta, boolean Player) { 
    Integer[] children; 
    if(depth == 0 || newNode.allNodesFull()){ 
     return (newNode.blacknodes() - newNode.whitenodes()); 
    } 
    if(Player == false){ 
     children = newNode.findMovesBlack(); 
     Arrays.sort(children); 
     for(Integer child: children){ 
      nodesGenerated ++; 
      alpha = Math.max(alpha, alphabeta(new Node(newNode.move(child), true), 
          depth - 1, alpha, beta, !Player)); 
      if(beta <= alpha) 
       break; 
     }return alpha; 
    }else{ 
     children = newNode.findMovesWhite(); 
     Arrays.sort(children); 
     for(Integer child: children){ 
      nodesGenerated ++; 
      beta = Math.min(beta, alphabeta(new Node(newNode.move(child), false), 
          depth - 1, alpha, beta, !Player)); 
      if(beta <= alpha) 
       break; 
     }return beta; 
    } 
}

一些修改我的代码后，就不再与它早期的返回问题，但我确实有α和β的问题从来没有改变

我给的会发生什么解释，假设他们的工作

findMovesBlack（）和findMovesWhite（）都返回具有可能位置的Integer []数组，这些位置无论玩家转动的位置，都可以移动。对于黑白棋，findMovesBlack（）的初始位置将返回[19，26，37，44]

allNodesFull（）返回如果findMovesBlack（）和findMovesWhite（）都具有为0

长度的布尔blacknodes（）和whitenodes（）分别返回黑色或白色节点的数量。

Node.move（int coordinate）返回一个String []数组，其中包含已翻转并放置的新位置。相信我，它工作正常。

Node（String [] gameboard，boolean player-to-move）只是用我们找到的参数设置一个新的位置。

我相信这就是你需要看到的。我已经解决了后端的所有问题。

来源

2012-04-19 Sam P

我们需要'Node'实现来告诉发生了什么。算法本身看起来不错，但是'allNodesFull（）'，'findMovesBlack（）'，'move（）'等等呢？初始呼叫的参数是什么？ – Thomas 2012-04-19 14:05:51

我已经添加了我的Node类。我希望你能帮助我 – 2012-04-19 14:55:15

另外最初的参数是这样的 alphabeta（Node包含reversei的开放位置，12,100，-100，false） – 2012-04-19 15:00:38

答案在于beta和alpha值的实现。我不得不乱用相对于=号的位置。

来源

2012-09-19 07:29:38

对不起，我使用的是来自WikiPedia的相同算法，也有问题。 MinMax完美的工作，但alpha-beta不断犯一些虚假的错误。你可以分享你的成功代码？ – 2016-06-17 17:46:36

为什么我的alpha-beta修剪的实现不起作用？

回答

相关问题