Improving recursion method in C#

Question

This is my code:

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

My code takes a set of cards and represents your maximum possible score when playing against a deterministic opponent. After each of your opponent's plays you have 2 choices until cards are all picked. Is there a way to somehow store my results of the iterations so I can improve my algorithm? So the recursion doesn't do unnecessary iterations? Because after 40 or 50 cards it becomes very slow.

Answer 1

You only access the first or the last element in the list D. Rather than pass the exact list around, you can pass the full list of cards (or even better: as an int array) together with the index of the first and last position.

It's much faster to calculate the opponent's score after the calculation is complete: myScore and opponentScore add up to the sum of the values of the cards, so you can do this in O(n) time. This way, you can eliminate all the code that updates opponentScore.

You don't need to pass myScore either. If you let cardGameValue return the best score obtained from only the remaining cards.

Finally, if you work with the first and last index, you can store the score in a 2D array, indexed by first and last. If all the cards have positive values, then the score must be positive if there are at least two cards remaining.

So at the beginning of the call, you check if the cached score is positive. If it is, you can return it right away. If not, you have to calculate it, and then store it in the cache array.

This is what you end up with:

static int cardGameValue(int[] D, int first, int last) {
    scores = new int[last + 1, last + 1];
    return cardGameValue(D, first, last, scores);
}

static int cardGameValue(int[] D, int first, int last, int[,] scores) {
    // If we have at most 1 card, our score is 0:
    if (first >= last)
        return 0;

    // Otherwise, get the score from the cache array. 
    // If it is positive, return the value.
    int score = scores[first, last];
    if (score > 0)
        return score;

    // Keep the original first and last 
    // for filling in the computed value later.
    int firstOriginal = first;
    int lastOriginal = last;

    // Let the opponent pick a card:
    if (D[first] <= D[last])
        last--;
    else
        first++;

    // Choose our best card:
    int left = D[first] + cardGameValue(D, first + 1, last, scores);
    int right = D[last] + cardGameValue(D, first, last - 1, scores);
    score = Math.Max(left, right);

    // and enter the score into the cache array:
    scores[firstOriginal, lastOriginal] = score;

    // Finally, return the computed score.
    return score;
}

Even for 300 cards, this runs in less than 1 millisecond on my machine.

Answer 2

You can try dynamic programming, just store the intermediate results in some suitable data structure, and when you need to invoke a recursive call, just use the stored value!

You can use a 2-D array of ints to store the results. The element at [i][j] will store the result of the game with the deck D[i] through D[j]. Start with row 0, then using the results fill up row 1, and so on. This will calculate the result in O(n^2) time.