c++ - 图博弈算法

我在模拟下面的游戏：
这个游戏有两个玩家。假设有一个带顶点和边的图每转一圈，你可以移除一条边，如果你分离一个顶点，你得到一个点，你可以移除另一条边你一直玩到没有更多的边，在这一点上，得分最多的球员赢得比赛。
我用一个数组来表示图形，从另一个程序生成的单独文件中读取，例如：

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

提前谢谢。

最佳答案

似乎您正在尝试实现某种形式的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