CODEWITHSUNDEEP
algorithmstrategy-patternevolutionary-algorithm
Sunil
Sunil

Reputation: 307

Algorithm: Maximizing profit in card game with m winning cards and n losing cards

Let's say a Casino (C) has a game which involves only one player and one dealer. The game is played with m+n cards, m are marked as winning cards and 'n' as losing cards.

Rules/Information regarding the game :

  1. Player knows the number of winning cards 'm' and number of losing cards 'n' at every stage.
  2. Player starts playing with 'X' amount and plays until all the cards are drawn out.
  3. Dealer is very very smart, and has the power to draw either a winning card or a loosing card based on the bet placed by Player on table.
  4. Every draw reduces the number of cards of either category, i.e. if winning card is drawn, number of winning cards becomes 'm-1' and vice versa.
  5. Player can bet '0' amount as well.

  6. If player bets 'W' amount and a winning card is drawn. Player gets 2W in return else he loses the betted amount

    Question : Derive an algorithm or strategy which player should follow to maximize his profit.

Some examples :

Testcase - 1: 

Lets say m=0, n=1

Player knows dealer has no chance but to make him lose on whatever he bets, so he bets '0' amount. Thus, maximum he can make is X.

Testcase - 2:

m=1, n=0

Player knows dealer has no option but to draw the only card i.e. winning card so he bets everything i.e. 'X' and gets back '2X'. So, he backs out of casino with 2X amount.

TestCase - 3:

m=1, n=1 :

Lets say player bets 'W' amount - Lets say Dealer draws winning card: so net amount = X+W and m->0 and n->1 : Thus maximum amount in this case X+W -If dealer draws losing card: so net amount left = X-W and m->1 and n->0 : Thus, maximum amount in this case 2(X-W)

Player will choose 'W' to maximize his profit which can be done only in the case when 2(X-W)=X+W => W=X/3

Thus, maximum amount player can walk out in this case = 4X/3

Upvotes: 3

Views: 573

Answers (1)

colinfang
colinfang

Reputation: 21707

Here is a solution from F#

Suggestion: don't do symbolic programming unless you have to. In this case we assume X = 1

let stake = Array2D.zeroCreate 100 100
let bankroll =  Array2D.zeroCreate 100 100

for i in 1 .. 99 do
    stake.[0, i] <- 0.0
    bankroll.[0, i] <- 1.0

for i in 1 .. 99 do
    stake.[i, 0] <- 1.0
    bankroll.[i, 0] <- 2.0

stake.[0, 0] <- 0.0
bankroll.[0, 0] <- 1.0

let rec solve i j =
    if bankroll.[i, j] <> 0.0 then (stake.[i, j], bankroll.[i, j])
    else
       let a = snd (solve (i - 1) j)
       let b = snd (solve i (j - 1))
       let x = (b - a) / (a + b)  // solve (1 + x)a = (1 - x)b
       let y = (x + 1.0) * a
       stake.[i, j] <- x
       bankroll.[i, j] <- y
       (x, y)

solve 10 10 // = (0.06182352702, 1.333333333)

It seems as long as the number of winning cards equals the number of losing cards, the max profit a player can gain is always 4X/3

Upvotes: 1

Related Questions