Memoization Recursion C++

Question

I was implementing a recursive function with memoization for speed ups. The point of the program is as follows:

I shuffle a deck of cards (with an equal number of red and black cards) and start dealing them face up. After any card you can say “stop”, at which point I pay you $1 for every red card dealt and you pay me $1 for every black card dealt. What is your optimal strategy, and how much would you pay to play this game?

My recursive function is as follows:

double Game::Value_of_game(double number_of_red_cards, double number_of_black_cards)
{
    double value, key;


    if(number_of_red_cards == 0)
    {
    Card_values.insert(Card_values.begin(), pair<double, double> (Key_hash_table(number_of_red_cards, number_of_black_cards), number_of_black_cards));
    return number_of_black_cards;
    }
    else if(number_of_black_cards == 0)
    {
    Card_values.insert(Card_values.begin(), pair<double, double> (Key_hash_table(number_of_red_cards, number_of_black_cards), 0));
    return 0;
    }

    card_iter = Card_values.find(Key_hash_table(number_of_red_cards, number_of_black_cards));
    if(card_iter != Card_values.end())
    {
        cout << endl << "Debug: [" << number_of_red_cards << ", " << number_of_black_cards << "] and value = " << card_iter->second << endl;
    return card_iter->second; 
    }

    else 
    {
    number_of_total_cards = number_of_red_cards + number_of_black_cards;
        prob_red_card = number_of_red_cards/number_of_total_cards;
        prob_black_card = number_of_black_cards/number_of_total_cards;

    value = max(((prob_red_card*Value_of_game(number_of_red_cards - 1, number_of_black_cards)) + 
             (prob_black_card*Value_of_game(number_of_red_cards, number_of_black_cards - 1))), 
             (number_of_black_cards - number_of_red_cards));
    cout << "Check: value = " << value << endl;

    Card_values.insert(Card_values.begin(), pair<double, double> (Key_hash_table(number_of_red_cards, number_of_black_cards), value));

        card_iter = Card_values.find(Key_hash_table(number_of_red_cards , number_of_black_cards ));
        if(card_iter != Card_values.end());
        return card_iter->second;
     } 
}

double Game::Key_hash_table(double number_of_red_cards, double number_of_black_cards)
{
    double key = number_of_red_cards + (number_of_black_cards*91);
    return key; 
}

The third if statement is the "memoization" part of the code, it stores all the necessary values. The values that are kept in the map can be thought of as a matrix, these values will correspond to a certain #red cards and #black cards. What is really werid is that when I execute the code for 8 cards in total (4 blacks and 4 reds), I get an incorrect answer. But when I execute the code for 10 cards, my answer is wrong, but now my answer for 4 blacks and 4 reds are correct (8 cards)! Same can be said for 12 cards, where I get the wrong answer for 12 cards, but the correct answer for 10 cards, so on and so forth. There is some bug in the code, however, I can't figure it out.

Answer 1

Nobody actually answered this question with an answer. So I will give it a try, though nneonneo actually put his or her finger on the likely source of your problem.

The first problem that's probably not actually a problem in this case, but sticks out like a sore thumb... you are using double to hold a value that you mostly treat as an integer. In this case, on most systems, this is probably OK. But as a general practice, it is very bad. In particular because you check if a double is exactly equal to 0. It probably will be as, on most systems, with most compilers, a double can hold integers values up to a fairly large size with perfect precision as long as you restrict yourself to adding, subtracting and multiplying by other integers or doubles masquerading as integers to get a new value.

But, that's likely not the source of the error you're seeing, it's just trips every good programmer's alarm bells for smelly code. It should be fixed. The only time you really need them to be doubles is when you're calculating the relative probability of red or black.

And that brings me to the thing that probably is your problem. You have these two statements in your code:

number_of_total_cards = number_of_red_cards + number_of_black_cards;
prob_red_card = number_of_red_cards/number_of_total_cards;
prob_black_card = number_of_black_cards/number_of_total_cards;

which, of course, should read:

number_of_total_cards = number_of_red_cards + number_of_black_cards;
prob_red_card = number_of_red_cards/double(number_of_total_cards);
prob_black_card = number_of_black_cards/double(number_of_total_cards);

because you've been a good programmer and declared those variables as integers.

Presumably prob_red_card and prob_black_card are variables of type double. But they are not declared anywhere in the code you show us. This means that no matter where they are declared, or what their types are, they must be effectively shared by all sub-calls in the recursive call tree for Game::Value_of_game.

The is almost certainly not what you want. It makes it extremely difficult to reason about what values those variables have and what those values represent during any given call in the recursive call tree for your function. They really have to be local variables in order for the algorithm to be tractable to analyze. Luckily, they seem to only be used within the else clause of a particular if statement. So they can be declared when they are initially assigned values. Here is probably what this code should read:

unsigned const int number_of_total_cards = number_of_red_cards + number_of_black_cards;
const double prob_red_card = number_of_red_cards/double(number_of_total_cards);
const double prob_black_card = number_of_black_cards/double(number_of_total_cards);

Note that I also declare them const. It is good practice to declare any variable who's value you don't expect to change during the lifetime of the variable as const. It helps you write code that is more correct by asking the compiler to tell you when you accidentally write code that is incorrect. It also can help the compiler generate better code, though in this case even a trivial analysis of the code reveals that they are not modified during their lifetimes and can be treated as const, so most decent optimizers will essentially put the const in for you for the purposes of code optimization, though that still will not give you the benefit of having the compiler tell you if you accidentally use them in a non-const way.