алгоритм графика-игры

Question

Я пытаюсь подражать следующей игре: В игру играют 2 игрока. Представьте, что у вас есть граф с вершинами и ребрами. В каждом случае вы можете удалить один край, если вы изолируете вершину, вы получите точку, и вы можете удалить другую. Вы играете, пока не будет больше ребер, в этот момент игрок с наибольшим количеством очков выигрывает игру.

Я представляю граф, массив, который я прочитал из отдельного файла генерируется, который генерируется другой программой, например, этот:

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

Игрок 1 может выиграть 4/0, но так может игрок 2. Лучший результат 1/3 для игрока 1.

EDIT: «Как игрок может выиграть с 4/0?» :

A--B--D 
|/
c 

A--B--D 
| 
C 

A B--D 
| 
C 

Как вы можете видеть, что первый игрок получит 4 очка, если средний край удаляется, в противном случае другой игрок получает 4 очка.

Я могу получить лучший результат для каждого игрока, но тогда другой игрок не выберет свой лучший поворот на каждом шагу. Я потратил много времени, экспериментируя с ним, но у меня всегда возникает та же проблема.

EDIT: Я думаю, что я довольно близко к решению этого сейчас (тогда я снова думал, что все время), мне просто нужно сохранить 2 балла за каждый ход, а потом как-то я должен сделать так что принимается только самый высокий балл текущего игрока. Таким образом, я должен быть в состоянии сделать так, чтобы игрок проигнорировал ход 4/0.

EDIT: Я пытался реализовать это предложение, но, к сожалению, я снова застрял. Я либо получаю странный вывод, который слишком высок, либо функция просто дает мне -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 и оценка принадлеж-переменные класса. Может ли кто-нибудь указать, какая часть его нуждается в исправлении?

Другой EDIT, все еще не работающий, теперь я просто не вижу ошибки вообще. Он продолжает выводить 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; 
} 

Заранее спасибо ,

Answer 1

Похоже, вы пытаетесь реализовать какую-либо форму алгоритма Minimax. Это находит лучший возможный счет для игрока, предполагая, что оба игрока делают лучшие шаги для себя.

Но в вашем коде есть какие-то странные вещи: слишком много переменных оценки, безоговорочно назначая maxScore в середине функции (и, таким образом, теряя ее старое значение), и я не вижу, как можно было бы получить оценки ненулевое значение.

Вот я бы реализовал это в псевдокоде. Функция getScore(graph) вернет наилучший результат для игрока, чей ход (при условии, что оба игрока играют, чтобы максимизировать собственный счет), где «оценка» означает, что очки игрока минус очки другого игрока. Я использую вариант минимаксного 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