graph-game algorithm

Question

I'm trying to simulate the following game: The game is played with 2 players. Imagine you have a graph, with vertices and edges. Each turn you can remove one edge, if you isolate a vertex you get a point and you can remove another one. You play until there are no more edges at which point the player with the most point wins the game.

I represent the graph by an array, which I read from a separate file generated that's generated by another program, for example this one:

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

Player 1 can win with 4/0, but so can player 2. The best result is 1/3 for player 1.

EDIT: "how can a player win with 4/0?" :

A--B--D 
| /
c

A--B--D
|
C

A  B--D
|
C

As you can see the first player will get 4 points if the middle edge is removed, otherwise the other player will get 4 points.

I can get the best result for each player, but then the other player would not choose his best turn each turn. I've spent a lot of time experimenting with it, but I always get the same problem.

EDIT: I think I'm pretty close to solving this now (then again I have been thinking that all the time), I just need to save 2 scores for each turn, and then somehow I have to make it so that only the highest score of the current player is accepted. That way I should be able to make it so that the player will ignore the 4/0 move..

EDIT: I've tried to implement the suggestion but unfortunately I'm stuck again. I either get a strange output that's way too high, or the function simply gives me -2 as an answer, but it doesn't work on other, bigger graphs. I've tried a lot of things to fix it, but it just doesn't work. The code below is what I'm trying now, unfortunately it doesn't work either:

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

With maxScore and score being member-variables of the class. Could someone please point out what part of it needs correction?

Another EDIT, still not working, now I just don't see the error at all. It keeps outputting 1, it's like it never changed maxScore... Takken is the number of edges left, I tried using the boundaries of the array but it does not make any difference..

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

Thanks in advance.

Answer 1

It seems like you're trying to implement some form of the Minimax algorithm. This finds the best possible score for a player, assuming that both players make the best moves for themselves.

But there are some strange things in your code: too many score variables, unconditionally assigning to maxScore in the middle of the function (and thus losing its old value), and I don't see how the scores could ever receive a nonzero value.

Here's I'd implement this in pseudocode. The function getScore(graph) will return the best possible score for the player whose turn it is (assuming both players play to maximize their own score), where "score" means that player's points minus the other player's points. I'm using the Negamax variant of minimax. This uses the fact that a score of +x for one player is the same as a score of -x for another to avoid having to write things twice. There's not even a need to keep track of whose turn it is because both players can make exactly the same moves.

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