double players_move(int dealer_card, int player_sum, bool player_has_ace, string deck);This returns the probability that the player wins with the given state (I turned the deck into a string so that it was easy to print out for debugging). The rough outline of players_move() is the following:
Now, the first thing to do is to figure out the probability of winning if you don't take any cards. That's gotta be pretty low, don't you think? If you "stand", your total will be 12 (because you'll count one of your aces as 11), and you'll call dealers_move(1, true, 12, "4440000004") -- see below. It will return 0.143506.
Now you calculate the probability of winning by taking a hit. There are only four ranks of cards in the deck: ace, two, three and ten. Let's consider each in turn:
Your total is 6.98776, and the number of ways to get a hit is 16, so your probability of winning if you get a hit is 0.436735. Since that is better than the probability of standing, you return 0.436735.
double dealers_move(int dealer_sum, bool dealer_has_ace, int player_total, string deck);This returns the probability of the player winning when the dealer is done. You have the strict algorithm for how the dealer makes decisions, so you code them up. If the dealer's sum is >= 17, then the dealer sits and you can return 0 or 1 for whether the player won.
Otherwise, the dealer needs to take a hit, and you'll calculate the probability recursively, considering every possible card that the dealer can get, just like above in players_move.
Obviously, you will end up memoizing these recursive procedures -- I turned the parameters into a single long long using bit arithmetic, and that was my key to the cache. I had to be careful about this (at first I only allocated two bits to each card in the deck, and that didn't work out too well, because there are 5 potential values (0 through 4)).
You should write dealers_move() first. Fortunately, you can test this with examples 0 through 4, and that will help you debug it. Memoize it next, and test that too.
It is an unfortunate matter that none of the examples have aces, which is I'm sure why there were 13 bad submissions out of 23. That's where my problems were when I solved it. You can use my example 5 in main.cpp to help. Also, here are my memoization cache's with example 6 in main.cpp, which has dealer = 5, player = { 7, 8 }, and Deck = 1004000002.
lers_move( 5, false, 15, "1004000002") = 0.20952381 dealers_move( 5, false, 16, "0004000002") = 0.26666667 dealers_move( 5, false, 19, "1003000002") = 0.30000000 dealers_move( 5, false, 20, "0003000002") = 1.00000000 dealers_move( 6, true, 15, "0004000002") = 0.06666667 dealers_move( 6, true, 19, "0003000002") = 0.10000000 dealers_move( 9, false, 15, "1003000002") = 0.25000000 dealers_move( 9, false, 16, "0003000002") = 0.30000000 dealers_move( 9, false, 19, "1002000002") = 0.40000000 dealers_move( 9, false, 20, "0002000002") = 1.00000000 dealers_move(10, true, 15, "0003000002") = 0.00000000 dealers_move(10, true, 19, "0002000002") = 0.00000000 dealers_move(13, false, 15, "1002000002") = 0.50000000 dealers_move(13, false, 16, "0002000002") = 0.50000000 dealers_move(13, false, 19, "1001000002") = 1.00000000 dealers_move(13, false, 20, "0001000002") = 1.00000000 dealers_move(14, true, 15, "0002000002") = 0.50000000 dealers_move(14, true, 19, "0001000002") = 1.00000000 dealers_move(15, false, 15, "1004000001") = 0.20000000 dealers_move(15, false, 16, "0004000001") = 0.20000000 dealers_move(15, false, 19, "1003000001") = 0.25000000 dealers_move(15, false, 20, "0003000001") = 1.00000000 dealers_move(16, true, 15, "0004000001") = 0.20000000 dealers_move(16, true, 19, "0003000001") = 0.25000000 dealers_move(17, false, 15, "1001000002") = 0.00000000 dealers_move(17, false, 16, "0001000002") = 0.00000000 dealers_move(17, false, 19, "1000000002") = 1.00000000 dealers_move(17, false, 20, "0000000002") = 1.00000000 dealers_move(18, true, 15, "0001000002") = 0.00000000 dealers_move(18, true, 19, "0000000002") = 1.00000000 dealers_move(19, false, 15, "1003000001") = 0.00000000 dealers_move(19, false, 16, "0003000001") = 0.00000000 dealers_move(19, false, 19, "1002000001") = 0.00000000 dealers_move(19, false, 20, "0002000001") = 1.00000000 dealers_move(20, true, 15, "0003000001") = 0.00000000 dealers_move(20, true, 19, "0002000001") = 0.00000000 dealers_move(23, false, 15, "1002000001") = 1.00000000 dealers_move(23, false, 16, "0002000001") = 1.00000000 dealers_move(23, false, 19, "1001000001") = 1.00000000 dealers_move(23, false, 20, "0001000001") = 1.00000000 dealers_move(24, true, 15, "0002000001") = 1.00000000 dealers_move(24, true, 19, "0001000001") = 1.00000000 dealers_move(25, false, 15, "1004000000") = 1.00000000 dealers_move(25, false, 16, "0004000000") = 1.00000000 dealers_move(25, false, 19, "1003000000") = 1.00000000 dealers_move(25, false, 20, "0003000000") = 1.00000000 dealers_move(26, true, 15, "0004000000") = 1.00000000 dealers_move(26, true, 19, "0003000000") = 1.00000000 players_move( 5, 15, false, "1004000002") = 0.26666667 players_move( 5, 16, true, "0004000002") = 0.66666667 players_move( 5, 19, false, "1003000002") = 0.30000000 players_move( 5, 20, true, "0003000002") = 1.00000000 players_move( 5, 23, false, "1002000002") = 0.00000000 players_move( 5, 24, true, "0002000002") = 0.00000000 players_move( 5, 25, false, "1004000001") = 0.00000000 players_move( 5, 26, true, "0004000001") = 0.00000000 players_move( 5, 29, false, "1003000001") = 0.00000000 players_move( 5, 30, true, "0003000001") = 0.00000000