0

我正在尝试模拟以下游戏：该游戏由 2 名玩家进行。想象一下，你有一个图，有顶点和边。每转一圈，您可以删除一条边，如果您隔离一个顶点，您会得到一个点，您可以删除另一条边。你一直玩到没有更多的边缘，此时得分最高的玩家赢得比赛。

我用一个数组表示图形，该数组是从另一个程序生成的单独文件中读取的，例如这个：

0 1 1 0
1 0 1 1
1 1 0 0
0 1 0 0

玩家 1 可以以 4/0 获胜，但玩家 2 也可以。最好的结果是玩家 1 的 1/3。

编辑：“玩家如何以 4/0 获胜？” ：

A--B--D 
| /
c

A--B--D
|
C

A  B--D
|
C

如您所见，如果中间边缘被移除，第一个玩家将获得 4 分，否则另一个玩家将获得 4 分。

我可以为每个玩家得到最好的结果，但是另一个玩家不会在每回合都选择他最好的回合。我花了很多时间尝试它，但我总是遇到同样的问题。

编辑：我想我现在非常接近解决这个问题（然后我一直在想），我只需要为每回合保存 2 个分数，然后我必须以某种方式做到这一点，以便只有最高当前玩家的分数被接受。这样我应该能够做到，这样玩家就会忽略 4/0 移动..

编辑：我试图实施这个建议，但不幸的是我又被卡住了。我要么得到一个太高的奇怪输出，要么函数只是给我 -2 作为答案，但它不适用于其他更大的图表。我已经尝试了很多方法来修复它，但它只是不起作用。下面的代码是我现在正在尝试的，不幸的是它也不起作用：

int Matrix::getTurn (bool** array) {
   if (edges == 0) 
      return 0;
    for (int i=0; i<edges; i++) {
        for (int j=0; j<edges; j++) {
            if (array[i][j] == true) {
                array[i][j] = false;
                array[j][i] = false;
                score = getScore (array, i, j);

                if (score > 0)
                   score += getTurn (array);
                else score -= getTurn (array);

                if (score > maxScore)
                   maxScore = score;

                array[i][j] = true;
                array[j][i] = true;
            }
        }
    }
   return maxScore;
}

maxScore 和 score 是类的成员变量。有人可以指出它的哪一部分需要更正吗？

另一个编辑，仍然无法正常工作，现在我根本看不到错误。它一直输出 1，就好像它从未改变过 maxScore ... Takken 是剩下的边数，我尝试使用数组的边界，但它没有任何区别..

int Matrix::berekenZet (bool** array) {
   if (takken == 0)
      return 0;
   int maxScore = 0, score = 0;
    for (int i=0; i<takken; i++) {
        for (int j=0; j<takken; j++) {
            if (array[i][j] == true) {
                array[i][j] = false;
                array[j][i] = false;
                takken -= 1;
                score = berekenScore (array, i, j);

                if (score > 0)
                   score += berekenZet (array);
                 else score -= berekenZet (array);

                if (score > maxScore)
                   maxScore = score;

                array[i][j] = true;
                array[j][i] = true;
                takken += 1;
                score = 0;
            }
        }
    }
   return maxScore;
}

提前致谢。

4

1 回答 1

1

您似乎正在尝试实现某种形式的Minimax算法。假设两个玩家都为自己做出了最好的动作，这将为玩家找到可能的最佳分数。

但是你的代码中有一些奇怪的东西：太多的分数变量，maxScore在函数中间无条件地赋值（因此失去了它的旧值），我看不出分数怎么会收到一个非零值。

这是我用伪代码实现的。该函数getScore(graph)将为轮到的玩家返回可能的最佳分数（假设两个玩家都玩以最大化自己的分数），其中“分数”意味着玩家的分数减去其他玩家的分数。我正在使用 minimax 的Negamax变体。这使用了这样一个事实，即一个玩家的 +x 分数与另一个玩家的 -x 分数相同，以避免必须写两次。甚至不需要跟踪轮到谁了，因为两个玩家都可以做出完全相同的动作。

int getScore(graph):
    if no possible moves:
        return 0
    maxScore = -infinity
    for each possible move:
        make the move
        score = the score directly obtained by this move
        if the player gets another turn:
            score += getScore(graph)
        else:  //opponent turn - subtract opponent's best score from player score
            score -= getScore(graph)
        maxScore = max(maxScore, score)
        undo the move
    return maxScore
于 2013-03-28T16:59:08.037 回答