Melhor escolha de cartas em jogos de cartas em C #
-
27-10-2019 - |
Pergunta
O problema consiste em escolher a melhor opção em cada momento do jogo seguindo estas regras:
-
Você só pode escolher o cartão mais à esquerda ou mais à direita.
-
Seu oponente SEMPRE escolherá primeiro, e SEMPRE escolherá a carta mais alta da mais à esquerda ou da mais à direita. Se for um empate, escolherá o mais à direita. Leve em consideração que nem sempre é a melhor escolha.
Às vezes, é impossível vencer, mas você deve, de qualquer maneira, mostrar o valor mais alto que pode agregar ao jogar contra esse oponente (ou estratégia, digamos).
Exemplo:
Cards: 1 2 4 2 8 4 3
Opponent: 3 4 2 2 = 11
Me: 1 8 4 = 13
Aqui, escolhi 1 em vez de 4 na segunda curva, para poder escolher o 8 mais tarde. É por isso que escolher a carta mais alta nem sempre é a melhor.
Tenho tentado implementar essa solução usando recursão, mas não tenho certeza se é a melhor opção. Alguma ideia de como projetar este algoritmo?
[EDITAR] Obrigado a @PengOne por sua ajuda generosa. Este é o código que estou tentando implementar, mas infelizmente está me dando erros. O que devo consertar? Estou editando conforme avanço.
static int cardGameValue(List<int> D, int myScore, int opponentScore)
{
if (D.Count == 0) return myScore;
else
{
if (D[0] <= D[D.Count - 1])
{
opponentScore += D[D.Count - 1];
D.RemoveAt(D.Count - 1);
}
else
{
opponentScore += D[0];
D.RemoveAt(0);
}
int left = cardGameValue(
new List<int>(D.GetRange(1, D.Count - 1)),
myScore + D[0],
opponentScore);
int right = cardGameValue(
new List<int>(D.Take(D.Count - 2)),
myScore + D[D.Count - 1],
opponentScore);
if (left >= right)
{ return left; }
else
{ return right; }
}
}
Solução
Construa a solução a partir dos casos mais simples usando recursão.
Seja D
a matriz de cartões. Deixe A
ser o total de suas cartas e B
ser o total de cartas de seu oponente. Defina S = A-B
como o valor do jogo. Você ganha se S>0
, perde se S<0
e empata se S==0
.
O mais fácil é fazer dois movimentos ao mesmo tempo, o seu movimento seguido pelo movimento determinado do oponente. Existem dois casos básicos a serem considerados:
-
Se
length(D) == 0
, retorneS
. O jogo terminou. -
Se
length(D) == 1
, retorneS + D[0]
. Você escolhe a carta restante e o jogo termina.
Para o caso recursivo, ao length(D) > 1
, avalie as duas possibilidades
-
Deixe
L
ser o resultado do jogo se você escolher a carta da esquerda seguida pelo oponente fazendo seu movimento determinístico, ou seja,L = D[0] - max(D[1],D[N-1]) + cardGameValue(newD)
-
Deixe
R
ser o resultado do jogo se você escolher a carta certa seguida pelo oponente fazendo seu movimento determinístico, ou seja,R = D[N-1] - max(D[0],D[N-2]) + cardGameValue(newD)
Escolha a reprodução correspondente ao número maior, ou seja, use D[0]
se L>=R
, caso contrário, use D[N-1]
. Aqui, N = length(D)
.
Outras dicas
Você deve olhar para o Algoritmo Min-Max , possivelmente com Poda alfa-beta
Min-Max é a ideia de que seu oponente sempre escolherá a melhor escolha para si, assim você pode rodar cada cenário possível para descobrir a melhor escolha que resultará em você derrotar seu oponente. "ou seja, dado que eu faço o lance x, meu oponente vai fazer o lance y, então eu vou ..." etc, até o final do jogo. Assim, você pode determinar quem vencerá.
A poda alfa-beta é semelhante, pois olha para cenários possíveis, mas determina se uma lista de cenários possíveis produzirá um resultado vencedor. Se você sabe que se fizer "mover x", sempre perderá, não importa o que aconteça, você não precisa perder mais tempo olhando para "mover x depois mover y". Você pode "podar" todo o ramo de opções de "mover x" porque sabe que nunca será útil.
Este é o código que realmente funcionou no final.Obrigado a todos pelo apoio.
static int cardGameValue(List<int> D, int myScore, int opponentScore)
{
if (D.Count == 0) return myScore;
else if (D.Count == 1)
{
opponentScore += D[0];
return myScore;
}
else
{
if (D[0] <= D[D.Count - 1])
{
opponentScore += D[D.Count - 1];
D.RemoveAt(D.Count - 1);
}
else
{
opponentScore += D[0];
D.RemoveAt(0);
}
int left = cardGameValue(new List<int>(D.GetRange(1, D.Count - 1)), myScore + D[0], opponentScore);
int right = cardGameValue(new List<int>(D.GetRange(0, D.Count - 1)), myScore + D[D.Count - 1], opponentScore);
if (left >= right)
{
return left;
}
else
{
return right;
}
}
}