帮助我的MinMax实现

我一直在试图实现一个minMax算法（稍后将尝试alphabeta修剪）为一个简单的游戏....我见过很多伪代码和教程，但我无法得到它工作...帮助我的MinMax实现

一点点帮助将不胜感激:)

下面是相关的类...（为清楚起见移除实现）

class Board { //Stores board state, Immutable 

    Board playMove(Move m); //generates new Board after playing "Move m" 

    List<Move> nextMoves(Move m); // generates all possible moves, previous move is required to decide the validity of the next moves 

    boolean isTerminal(); //board at terminal state? 
} 


class Move { //stores positions played and score gained from that move 

}

，这里是我的最小 - 最大的实现...有人可以指出我做错了什么吗？谢谢。

private Move bestMove = null; // field variable 

private int maxMove(Board board, Move prevMove, int myScore, int oppnScore) { 
    out("maxMove " + board); 
    if(board.isTerminal()) { 
     return myScore - oppnScore; 
    } 
    int mx = Integer.MIN_VALUE; 
    for(Move nxtMove: board.nextMoves(prevMove)) { 
     int k = minMove(board.playMove(nxtMove), 
         nxtMove, 
         myScore + nxtMove.score, 
         oppnScore); 
     if(k > mx) { 
      mx = k; 
      bestMove = nxtMove; 
     } 
    } 
    return mx; 
} 

private int minMove(Board board, Move prevMove, int myScore, int oppnScore) { 
    if(board.isTerminal()) { 
     return myScore - oppnScore; 
    } 
    out("minMove " + board); 
    int mn = Integer.MAX_VALUE; 
    for(Move nxtMove: board.nextMoves(prevMove)) { 
     int k = maxMove(board.playMove(nxtMove), 
         nxtMove, 
         myScore, 
         oppnScore + nxtMove.score); 
     if(k < mn) { 
      mn = k; 
      bestMove = nxtMove; 
     } 
    } 
    return mn; 
}

编辑：游戏简要说明如下，你有一定数量的硬币的不同教派面前的硬币。你和另一位玩家轮流从消费者一侧（左侧或右侧）取出一枚硬币。硬币的面额表示你为这一举动得分。某些硬币有特殊的含义，比如说Picking X意味着你会跳过一个转弯，或者Y意味着你会再转一圈。你的目标是比对手得分更多。

来源

2011-03-15 st0le

也许告诉我们一些关于游戏规则的信息会有所帮助。 – MAK 2011-03-15 08:51:37

@MAK，done ..... – st0le 2011-03-15 08:59:35

游戏的目标是什么？尽可能多地得分？比对手得分更多？ – MAK 2011-03-15 09:06:34

我只看到一个错误：你不记得你给定板子状态的哪个回合，所以你多次计算它，算法变慢。或者速度不是你的问题？

来源

2011-03-15 08:56:05

速度不是问题。这是不正确的，它会选择错误的（如非优化）移动（有时候是无效移动）。 – st0le 2011-03-15 09:00:18

我不认为我明白游戏规则，但它看起来像你的终端条件不太正确。

您正在返回玩家之间的分数差异。这意味着一个玩家想要最大化这个数值（与对手最大的差距），而另一个想要最小化这个数值（他试图将最接近的分数作为对手）。这看起来并不像真正的游戏会有什么样的目标。

我想你想要的是得分最高的玩家获胜。因此，您可以检查myScore> oppScore是否相应地返回1,0和-1。这意味着第一个玩家想要最大限度地获得回报（即他试图让它成为1--他赢了），而对手试图最小化回报（即如果它是-1，他就赢了）。如果没有取得胜利，他们宁可选择0（平局）。

另外，您为什么需要prevMove来产生下一步？ board没有关于游戏当前状态的所有信息（即剩下的硬币）？

来源

2011-03-15 09:15:49 MAK

我需要'prevMove'，因为如果之前的移动移除了一个'X'硬币，这意味着我需要选择2个硬币而不仅仅是一个。否则我只挑一枚硬币。 – st0le 2011-03-15 09:19:22

@ st0le：我明白了。我会将它作为“board”中的一个标记，但我想保留'prevMove'也可以。 – MAK 2011-03-15 09:24:00

@MAK，你的观察似乎是正确的，我会试试看，并报告。 – st0le 2011-03-15 09:27:19

帮助我的MinMax实现

回答

相关问题