алгоритм графической игры

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

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

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

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

РЕДАКТИРОВАТЬ: «Как игрок может выиграть с 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 и рейтингом являются переменные-члены класса. Может ли кто-нибудь указать, какая его часть нуждается в исправлении?

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

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

0

Решение

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

Но в вашем коде есть некоторые странные вещи: слишком много переменных оценки, безоговорочно присваиваемых 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
1

Другие решения

Других решений пока нет …

По вопросам рекламы [email protected]