Best card selection in a card game in C #

Question

The challenge is to choose the best option at every moment of the game, following these rules:

• You can select only the leftmost or rightmost card.

• Your opponent ALWAYS chooses the first one, and ALWAYS chooses the highest card from the leftmost or rightmost card. If it is a tie, he will choose the rightmost one. Please note that this is not always the best choice.

Sometimes it’s impossible to win, but you must in any case display the highest level that you can add by playing against this opponent (or, say, strategy).

Example:

Cards: 1 2 4 2 8 4 3 Opponent: 3 4 2 2 = 11 Me: 1 8 4 = 13 

Here I chose 1 instead of 4 on the second turn, so I could choose 8 later. Therefore, choosing the highest card is not always better.

I am trying to implement this solution using recursion, but I'm not sure if this is the best option. Any ideas on how to develop this algorithm?

[EDIT] Thanks @PengOne for this generous help. This is the code that is trying to implement, but unfortunately it gives me errors. What should I fix? I edit it as I go along.

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

Answer 1

Build a solution from the simplest cases using recursion.

Let D be an array of cards. Let A be the total amount of your cards, and B total amount of your opponent cards. Set the value S = AB as the value of the game. You win if S>0 , lose if S<0 and tie if S==0 .

The easiest way to do two moves at the same time, your movement is accompanied by an opponent of a certain movement. There are two main cases:

• If length(D) == 0 , return S Game over.

• If length(D) == 1 , return S + D[0] . You select the remaining card and the game ends.

For the recursive case when length(D) > 1 , evaluate two possibilities

• Let L be the result of the game if you choose a left card followed by an opponent performing a deterministic move, i.e.

  L = D[0] - max(D[1],D[N-1]) + cardGameValue(newD)

• Let R be the result of the game if you choose the right card, followed by the opponent performing a deterministic move, i.e.

  R = D[N-1] - max(D[0],D[N-2]) + cardGameValue(newD)

Select the playback corresponding to a larger number, i.e. take D[0] if L>=R , otherwise take D[N-1] . Here N = length(D) .

Answer 2

You should look at the Min-Max Algorithm , possibly with Alpha Beta Cropping

Min-Max is the idea that your opponent will always choose the best choice for himself, so you can run every possible scenario to open the best choice, which will lead to the beating of your opponent. "ie, if I make the transition x, my opponent will take the movement y, and then I will take ..." etc., until the end of the game. This way you can determine who wins.

Trimming an alpha beta is similar to looking at possible scenarios, but determines whether the list of possible scenarios will ever produce a winning result. If you know that if you do "move x", then you will always lose, no matter what, you do not need to spend more time looking at "move x then move y". You can trim the entire branch of options from move x because you know that this will never be useful.

Answer 3

This is the code that really worked at the end. Thank you all for your support.

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