Problem Statement |
| | We're going to play a very simple game of poker. As in regular poker, there is a pot, and the winner of the hand wins the money in the pot. In this game, each of two players will be given a single card, numbered between 0 and N-1, inclusive. The pot initially contains $1, and the size of each bet is also $1. The player who goes first may either check (put nothing in the pot) or bet (put $1 in the pot). If the first player checked, the second player may either check or bet. If he bets the first player must then either fold (concede the pot to the second player) or call (put $1 in). If, on the other hand, the first player bets, the second player must decide whether to fold or call. If one player folds, then the other player wins the pot automatically. If neither player folds, then the player with the higher card wins the pot (ties split the pot). Thus, there will only be five possible outcomes to the betting:
- Player 1 bets, player 2 folds; player 1 wins the pot
- Player 1 bets, player 2 calls; the player with the higher card wins, a tie results in the pot being evenly divided
- Player 1 checks, player 2 checks; the player with the higher card wins, a tie results in the pot being evenly divided
- Player 1 checks, player 2 bets, player 1 folds; player 2 wins the pot
- Player 1 checks, player 2 bets, player 1 calls; the player with the higher card wins, a tie results in the pot being evenly divided
You will be given a complete description of a probabilistic strategy played by player 1. You, as player two, want to maximize your expected value, and must play accordingly, given player one's strategy.
A double[] betProb gives the probability that player one will bet with each of the N cards. betProb[i] gives the probability that player one will bet given that his card is i. Similarly, callProb[i] gives the probability that player one will first check, and then call if you bet, given that his card is i. Therefore, 1-betProb[i]-callProb[i] gives the probability that player one will check and then fold to your bet.
You should return your expected profit (including the initial $1 in the pot) given that you play optimally (knowing player one's strategy), and that each player's card is assigned independently and uniformly at random. |
| |
Definition |
| | | Class: | OptimalPlay | | Method: | winnings | | Parameters: | double[], double[] | | Returns: | double | | Method signature: | double winnings(double[] betProb, double[] callProb) | | (be sure your method is public) |
|
| |
|
| |
Notes |
| - | The players do not know each other's cards. |
| - | The call probability is not conditional on not betting. It gives the joint probability of checking and then calling. |
| - | The profit is the amount you get from the pot that you didn't put in. Thus, if you tie your profit is $0.5, half of the original $1. If you call a bet and win your profit is $2. If you call a bet and lose, your profit is -$1. |
| - | Your return must have relative or absolute error less than 1E-9. |
| |
Constraints |
| - | N will be between 2 and 50, inclusive. |
| - | betProb and callProb will each contain exactly N elements between 0 and 1, inclusive. |
| - | The sum of corresponding elements of betProb and callProb will be at most 1. |
| |
Examples |
| 0) | |
| | | Returns: 1.0 | | You can win every time -- just bet and your opponent will fold, giving you the initial $1. |
|
|
| 1) | |
| | | Returns: 0.6666666666666666 | | Your opponent bets no matter what. You should call if your card is a 1 or a 2. When it is a one, you will lose $1 when your opponent has a 2, win $2 when your opponent has a 0, and win $0.5 when your opponent also has a 1. |
|
|
| 2) | |
| | | Returns: 0.5833333333333334 | We can describe your optimal strategy one card at a time (this is not the unique optimal strategy):
- If you have a 0, you should fold to a bet, and check if player one checks.
- If you have a 1, you should fold to a bet, and check if player one checks.
- If you have a 2, you should call a bet, and bet if player one checks.
Using this strategy you will win 0.083 when you have card 0, 0.333 when you have card 1, and 1.333 when you have card 2. Thus 1.75/3=0.583 overall. |
|
|