JOIN
Get Time
long_comps_topcoder  Problem Statement
Contest: Marathon Match 14
Problem: TwoCardDraw

Problem Statement

    

Poker has become amazingly popular recently. While some significant progress has been made towards algorithms which play well, very few of them can adapt to their opponents playing styles the way the best human players do.

In this problem, you will play a simplified version of the game, which we will call two-card draw. In this game, each player first antes 1 unit (puts 1 unit in the pot), and is then dealt two 'cards' where a card is simply a random integer from 0 to 4. After the players receive their cards, there is a round of betting. If no one folds (quits) in the first round of betting, each player may then exchange (or draw) 0, 1 or 2 of his cards for new cards. You will draw first, and then your opponent will draw, knowing how many cards you have exchanged. After this exchange, there is another round of betting, followed by a showdown (assuming no one has folded). In the showdown, the two hands are compared just like in regular poker. A hand with two cards that are the same always beats a hand with two different cards. If both hands have a pair (two cards of the same value) the higher pair wins. If neither hand has a pair, then the hand with the highest card wins. If each hand has the same highest card, then the other card is compared. If both hands are the same, then it is a tie. Whoever has the winning hand wins the pot, while the pot is split evenly if there is a tie.

In each round of betting you act first and have two options: check or bet. If you check, you put no more money into the pot. If you choose to bet, you place either bet1 or bet2 units in the pot, depending on whether it is the first or second round of betting. After you decide to check or bet, your opponent can either fold, call, or raise. If he folds, you win the pot. If he calls, he puts the same amount in the pot as you, and the round of betting is over. If he raises, he matches your bet, and puts in one more of his own (whose size is either bet1 or bet2) , and then the decision is put back to you: fold (opponent wins), call (draw or showdown next), or raise. The two players may raise a combined total of at most 3 times in each round of betting (where choosing to bet initially counts as a raise). Thus, the following are the only reasonable valid betting sequences:

YOU   | OPP   | YOU   | OPP   | YOU
------+-------+-------+-------+------
check | call  |       |       |
check | raise | fold  |       |
check | raise | call  |       |
check | raise | raise | fold  |
check | raise | raise | call  |
check | raise | raise | raise | fold
check | raise | raise | raise | call
bet   | fold  |       |       |
bet   | call  |       |       |
bet   | raise | fold  |       |
bet   | raise | call  |       |
bet   | raise | raise | fold  |
bet   | raise | raise | call  |

In this problem, you will be playing against the TopCoder server, which will play a fixed strategy in each test case. Though the server's strategy will be fixed, it will be probabilistic. Thus, in each situation, the server will make a random choice based on a fixed probability distribution and perform the action dictated by this choice. More specifically, we will use the term situation to indicate the combination of the cards held by the server, and all the past actions that have led to the current decision being made by the server. For instance, one situation is: server's cards = (1,1), you raised, the server called, you then drew one card. In this situation, the server must make a decision about how many cards to draw. It will make this decision based on a probability distribution associated with the above situation.

To play against the TC server, you must implement a number of methods, as described below.

  • init(bet1, bet2) -- This is called only once per test case, and gives parameters which are constant over all games for this test case.
  • new_hand(card1, card2, winnings) -- This method indicates that a new hand is starting, where you have cards card1 and card2. winnings gives you your winnings over the previous hands. You should return 0 to check, or 1 to bet in the first round of betting.
  • round1(card1, card2, bets) -- This method asks you what you would like to do when the TC server has raised in the first round of betting, where you have card1 and card2, and the parameter bets specifies the total number of bets so far. Your return should be as follows:
    • 0 to fold
    • 1 to call
    • 2 to raise
    Note that if bets is 3, you cannot raise, since the maximum number of bets is 3.
  • draw(card1, card2, bets) -- After the first round of betting is over, and neither player has folded, this method will be called, asking you how many cards you would like to draw. You should return 0, 1, or 2. If you return 1, it is assumed that you would like to exchange the lower of your two cards (doing otherwise would be a mistake).
  • round2(card1, card2, bets1, bets2, drew) -- This method asks you what you would like to do in the second round of betting. The parameters card1 and card2 tell you what your cards are, bets1 reminds you how many bets there were in the first round, while bets2 tells you how many bets there have been so far in this round of betting. When bets2 is 0, it means that you are acting first in this round, and may check or bet. drew tells you how many cards the TC server drew. Your return should be as follows:
    • 0 to fold
    • 1 to call or check
    • 2 to raise or bet
    Note that if bets2 is 3, you cannot raise, since the maximum number of bets is 3.
  • showdown(card1, card2, opp1, opp2) -- This method will be called if there is a showdown, telling you what cards you have, and what cards your opponent has. Note that this method will not be called if either player folds, and thus the only way to find out what cards the TC server has is to reach a showdown.

Notice that you will not always be explicitly told everything that happens. For example, if the TC server decides to fold, you will not be explicitly told, but you may deduce it from the fact that the new_hand method will be called instead of one of the other methods. Similarly, when you raise in the first round and the TC server calls, you won't be told explicitly, but can deduce what happened since the draw method will then be called.

Here is a simple example of a hand:



First, new_hand is called, with c1 = 1 and c2 = 2, indicating that you have a 1 and a 2. Let's assume you want to bet in round 1 of the betting, so you would return 1 from the new_hand method. Assuming the server calls, you would now have to decide how many cards to draw, and so the draw method would be called with c1=1, c2=2, bets=1. To draw 1 cards, you return 1. Now, assume that the server draws 1 card. The round2 method would then be called, and let's assume that you draw a 4 so, the parameters would be card1=2, card2=4, bets1=1, bets2=0, drew=1 (since there are no bets yet in round 2, and the server drew 1 card). Lets say that you check (return 1 from the round2 method), and the server calls. We then go to the showdown, where you would learn what the server holds. It turns out that the server a 4 and a 3, and so you lose. You put a total of 1 (your ante) plus one small bet (of size bet1) in the pot, and so that is how much you would lose on this hand.

Scoring

In each test case, you will play 10,000 hands. Your score for a test case will be your total profit (or loss) plus 10,000. If this ends up being negative, it is increased to 0. Your overall score will simply be your average score for all the tests.

Further Server Play Details

This section describes the behavior of the TC Server in further detail, and is not strictly necessary for understanding the problem, but it may help you play better.



In the first round of betting a situation for the server is fully specified by the two cards held, along with the number of bets placed so far. Note that if the number of bets is even, it means that you checked as your initial action, while if it is odd, it means that you bet as your initial action. For these situations, the server has three probabilities, which form a probability distribution: the probabilities to fold, call, or raise. Another type of situation occurs when the first round of betting is over and the server must draw cards. In this case, a situation is defined by the cards held, the betting action of the first round (number of bets, and who bet first), along with the number of cards drawn by you. Finally, the situations in the second round of betting are defined by the cards held, the betting action of the first round, and the number of cards drawn by each player. Note that in the second round of betting, the decision is in no way dependent on the cards which were exchanged.



The exact probability distributions for the various actions in all the situations combine to form a strategy for the TC server. The value of a server strategy is defined to be the amount that it wins (or loses) when playing against an opposing strategy that is perfectly tuned to it. In other words, the value of the strategy is the worst that strategy could do (in expectation) against an opponent (like you) who played perfectly (against this strategy), assuming that that opponent fully understood the strategy (knew all the probabilities). In general, a random strategy is very bad, and has an extremely low value. However, a random strategy can serve as a starting point to find a good strategy, with a higher value. More specifically, we start with a random probability distribution chosen uniformly from the unit simplex. From this starting point, we consider the probability distributions for each situation, one distribution at a time. For each situation, we generate a new probability distribution, and see if using this distribution instead of the current one improves the value of the strategy. If it does, we install it, otherwise, we simply move on to the next situation. For each test case, we do this between 10,000 and 200,000 times (total, not per situation). Finally, in practice this algorithm performs better with a couple of slight tweaks. Instead of evaluating the value of the strategy against an opponent who plays perfectly, the value is evaluated against an opponent who plays almost perfectly, but does the wrong thing a very small fraction of the time (1 time in a thousand for each wrong possible wrong thing).



Another way that this strategy generation algorithm is improved is to choose the random probability distributions subject to the following constraints, which attempt to prevent the strategy from doing anything that seem to be clearly wrong. Additionally, in each iteration of the improvement algorithm, these constraints will be maintained:
  • Never fold or exchange cards when holding the best hand (two 4's)
  • Never draw two cards when one card is a 4 (drawing one would be better).
  • Never draw just one card when holding a pair.
  • Always raise with a pair of 4's in the second round of betting.
  • Never fold when calling is free.
 

Definition

    
Class:TwoCardDraw
Method:init
Parameters:int, int
Returns:int
Method signature:int init(int bet1, int bet2)
 
Method:new_hand
Parameters:int, int, int
Returns:int
Method signature:int new_hand(int card1, int card2, int winnings)
 
Method:round1
Parameters:int, int, int
Returns:int
Method signature:int round1(int card1, int card2, int bets)
 
Method:draw
Parameters:int, int, int
Returns:int
Method signature:int draw(int card1, int card2, int bets)
 
Method:round2
Parameters:int, int, int, int, int
Returns:int
Method signature:int round2(int card1, int card2, int bets1, int bets2, int drew)
 
Method:showdown
Parameters:int, int, int, int
Returns:int
Method signature:int showdown(int card1, int card2, int opp1, int opp2)
(be sure your methods are public)
    
 

Notes

-You may return any integer from the showdown and init methods -- it will be ignored.
-The memory limit is 64MB and the time limit is 20 seconds (which only includes time spent in your code).
-A sample solution is available in Java, C#, Python, or C++. The strategy is very simple: bet/raise with a pair of fours and check/call otherwise.
-There are 4 example test cases and 16 full submission test cases.
-If you return 0 on the first call to round2 (when you should return 1 to check, or 2 to bet), it will be treated as if you returned 1 and you will check.
 

Constraints

-BET1 will be between 1 and 5, inclusive.
-BET2 will be between BET1 and 3*BET1, inclusive.
-card1 will always be the smaller valued of the two cards.
 

Examples

0)
    
This strategy has value -0.09331885, meaning that if you were to play perfectly against it, you would expect to make 0.09331885 per hand. You can download the strategy here.



The first line of the file gives the bet sizes: bet1 and bet2. Each other line in the file corresponds to one situation, as described above. The first lines in the file are formatted as:

ROUND1 <CARD1> <CARD2> <BETS> <fold> <call> <raise>

This specifies the situation where the server holds CARD1 and CARD2, and there have been BETS bets. fold, call, and raise give the probabilities of the three actions. Next, there will be drawing probabilities. Each line will be formatted as:

DRAW <CARD1> <CARD2> <BETS> <DREW> <FIRST> <draw0> <draw1> <draw2>

CARD1 and CARD2 specify the cards held, BETS gives the number of bets made in the first round. FIRST specifies who bet first (or is 0 if no one bet): 0 stands for you, 1 for the TC server. DREW gives the number of cards you exchanged. Finally, draw0, draw1, and draw2 give the probabilities for drawing 0, 1 or 2 cards. The rest of the lines will give the round 2 betting probabilities. Each line will be formatted as:

ROUND2 <CARD1> <CARD2> <BETS1> <BETS2> <DREW1> <DREW2> <FIRST> <fold> <call> <raise>

BETS1 gives the number of bets in the first round, while BETS2 gives the number of bets in the second round. FIRST again specifies who bet first in the first round. DREW1 tells how many cards you drew, while DREW2 tells how many cards the TC server drew.
1)
    
This strategy has value -0.2749814.
2)
    
This strategy has value -0.13201468.
3)
    
This strategy has value -0.2939506.

This problem statement is the exclusive and proprietary property of TopCoder, Inc. Any unauthorized use or reproduction of this information without the prior written consent of TopCoder, Inc. is strictly prohibited. (c)2010, TopCoder, Inc. All rights reserved.