图形游戏算法

Question

我试图模拟下面的游戏： 游戏与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 ... 达见是边号离开，我尝试使用数组的边界，但它并没有任何区别..

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

在此先感谢。

Answer 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