Recently, my kid had to count our pennies, nickels, dimes, and quarters for homework. It'd be a pointless exercise, except that we had about $100 in change. I pay for every purchase in bills only, and then I take all the change home. Based on this, I wondered what the expected frequencies would be of each coin type, assuming that all change values 0 - 99 are equally likely, and that change is always paid using the fewest coins. Here's how I found those frequencies.
I can get 0, 1, 2, 3, or 4 pennies with equal probability, so I expect 2 pennies.
When I ignore pennies and quarters, the remaining coins must add up to 0, 5, 10, 15, or 20 with equal probability, as follows:
0 = 0 nickels, 0 dimes
5 = 1 nickel, 0 dimes
10 = 0 nickels, 1 dime
15 = 1 nickel, 1 dime
20 = 0 nickels, 2 dimes
That's 2 nickels in 5 scenarios, so I expect 2 / 5 = 0.4 nickels.
And that's 4 dimes in 5 scenarios, so I expect 4 / 5 = 0.8 dimes.
I can get 0, 1, 2, or 3 quarters with equal probability, so I expect 1.5 quarters.
Overall, that's 2 pennies, 0.4 nickels, 0.8 dimes, and 1.5 quarters--a total of 4.7 coins.
I can get any number from 0 to 99 cents in change with equal probability, so I expect 49.5 cents in change. Sure enough, 2 pennies, 0.4 nickels, 0.8 dimes, and 1.5 quarters is worth exactly 49.5 cents.
Of that 49.5 cents, I've got 2 cents in pennies, 2 cents in nickels, 8 cents in dimes, and 37.5 cents in quarters.
Back to my initial problem, about 42.5% of my coins should be pennies, 8.5% nickels, 17% dimes, and 32% quarters.
But most of the value is in quarters. Specifically, about 76% of my change is in quarters, 16% in dimes, 4% in nickels, and 4% in pennies.
Friday, April 26, 2019
Sunday, April 7, 2019
Dave Computes a Simple Machine Learning Algorithm
Here's a relatively straightforward way to develop a bot that uses machine learning to discover optimal game play. The approach is appropriate for any turn-based game (with 1 or more players) that can be reduced to a manageable number of game states and possible choices. So far, I have used this algorithm with some success for multi-player Five-Card Draw poker and for the game of Coup.
Idea
Play a game billions of times. As you play, keep track of every game state reached, every choice made in those states, how often each choice was made, and how often each choice resulted in a win. When learning, use the data accumulated to make choices that maximize the chance of winning. When done learning, the recommended strategy consists of the choices that were made most often.
Details
1. Identify every game state. A game state includes everything currently known to the player. In poker, this could include the player's hand and opponents' betting, but it cannot include opponents' unseen hands or the arrangement of cards in the deck. For most interesting games, a collection of game states would be too large to store in memory, or would be so large that finding an optimal strategy would be too computationally intensive. Therefore, much work goes into identifying which aspects of a game state to consider and which to ignore. For example, we might include a poker player's hand category (high card, pair, two pair, etc) but not their particular cards. Likewise, we might include the amount of money on a poker table, but not the details of who contributed that money and when.
2. Identify all possible choices that a player might make from any particular game state. Again, some games may need to be simplified to keep this manageable (such as limiting how much a poker player can raise).
3. For each game state and choice, store the number of times that choice was made and the accumulated gains resulting from that choice. For example, I might have encountered a particular state S on 100 occasions. On 30 of those times, I chose option C. In 20 out of those 30 cases, I went on to win the game. I would therefore record that state S and choice C resulted in 20 wins in 30 games. In the case of poker, instead of recording the number of games won, we would record the total amount of money gained as a result of a choice. For example, I might record that state S and choice C resulted in earning -12 dollars after 40 hands.
Let's call all this data our result table. It maps any game state and choice to the resulting number of wins and games.
5. In the course of learning, whenever a player must make a choice, use the result table to compute the expected value for each possible choice, and choose the option with the greatest expected value. For example, suppose I find myself in some game state, and I must choose from among options A, B, and C. I determine the expected value of A is 0.5, the expected value of B is 0.9, and the expected value of C is 0.1. I will therefore choose option B to maximize my expected value.
6. During the course of each game played, record each game state reached and each choice made. For example, I might record that, when I found myself in game state S1, I made choice A, and when I then found myself in game state S2, I made choice B.
Note that this list of choices made is separate from the result table. In fact, each bot using this learning algorithm must keep its own list of choices made, even though they might all share a single result table.
7. After each game (or poker hand), when the outcome is known (who won the game, or how much each player earned), go through all of the choices made by a player and record the results of those choices in the result table. For example, suppose I reached game state S and made choice C at some point during a game. In previous games, I had made choice C in game state S on 9 occasions, and I went on to win the game on 6 of those occasions. Suppose I now win this particular game. I must increment both the number of games and the number of wins for state S and choice C, so they now show I went on to win the game on 7 of 10 occasions. On the other hand, if I had lost, then I would not have incremented the number of wins, and my result table would record that I had won the game on 6 of 10 occasions. Once I've recorded the outcomes of all choices made in the game, then I can safely discard the list of choices made and begin the next game with an empty list.
8. In the course of learning, a player must sometimes make a choice with a lower expected value. This is because an issue arises if a player always makes the choice with the greatest expected value. Before the result table closes in on an optimal strategy, it will often guide a player to make a non-optimal choice. For example, suppose that in a certain game state, choice A's theoretical expected value is 0.8, while choice B's expected value is 0.5. Choice A is therefore the optimal choice in this game state. In the long run, we hope the data in our result table will converge to these expected values. But early in our learning, the expected values in our result table may be very different. Let's consider two scenarios.
In the first scenario, a moment occurs when choice A's expected value is 0.8 and choice B's is 0.9. Because B currently has the greater expected value, our player will keep choosing B. Eventually, we expect that option B will perform poorly enough that its expected value drops below A's (0.8), and the player will then begin to make the optimal choice. In this scenario, the algorithm has self-corrected.
In the second scenario, a moment occurs when choice A's expected value is 0.3 and choice B's is 0.9. Again, because B currently has the greater expected value, our player will keep choosing B. We expect that B's expected value will approach the theoretical value of 0.5. But in doing so, it may never drop below A's current expected value of 0.3, and therefore the player may never get the chance to try out option A again and discover that it will outperform B in the long run. Our algorithm has gotten stuck.
For this reason, it is necessary for the player to sometimes make a choice with a lower expected value. Perhaps 1% of the time, a player should make a random choice (instead of the one with the greatest expected value). In practice, 1% is a good probability to use. The higher this probability is, the less likely the algorithm is to get stuck. It will therefore converge more quickly, but to less accurate values. A lower probability of random play gives more accurate values, but is more likely to get stuck without finding an optimal strategy.
9. Ultimately, the learning algorithm will most likely require billions of games before the result table converges to meaningful results. (Note that 32-bit integers are therefore unlikely to be sufficient for storing numbers of wins and games.)
10. At the conclusion of the learning process, focus on the result table's numbers of games--not expected values. For example, suppose that, for some particular game state, our result table shows the following data:
On the other hand, option C was used twice as often as A, and both resulted in similar expected values. Most likely, whenever the computer chose C a couple of times in a row, it learned to defend against that choice. This temporarily made A's expected value greater than C's, and so the computer chose A next. But then the computer adjusted to defend against A, making C the better choice again.
So, which choice does our result table recommend? The answer comes from the numbers of games. The computer reached this game state in roughly 15 billion games. It chose A in 5 billion of those games and C in 10 billion. Therefore, the optimal strategy suggested by the result table is for us to choose A with probability 1/3, choose C with probability 2/3, and never choose B. In other words, a mixed strategy is required. A pure strategy (in which the computer always makes the same choice) could be exploited.
11. A game may have many optimal strategies (each of which may itself be a mixed strategy). Suppose we run our software once, and it recommends one strategy, and then we run it again only to find it recommends a different strategy. This might mean that we didn't run the software long enough for it to arrive at an optimal strategy. But it might simply mean that the software converged to two different and equally optimal strategies.
Example
Let's see how this algorithm is used to solve a toy version of poker. In this 2-player game, each player pays a $1 ante. Each player is dealt an ace (highest), king, or queen (each equally likely). Note that both players may be dealt the same card value. Players take turns acting by folding, calling/checking, or betting/raising in increments of $1, with a maximum of 2 raises. A couple examples illustrate how the game is played.
Example #1. After antes, there is $2 in the pot. Player 1 is dealt an ace and player 2 is dealt a king. Player 1 checks. Player 2 bets. There is now $3 in the pot. Player 1 raises. There is now $5 in the pot. Player 2 folds. Player 1 keeps all $5. Player 1 has gained $2 and player 2 has lost $2.
Example #2. After antes, there is $2 in the pot. Both players are dealt a king. Player 1 bets. There is now $3 in the pot. Player 2 calls. There is now $4 in the pot. Both players show their cards. Because they hold the same cards, they split the pot, each collecting $2. Each player has gained $0.
Let's identify the game states. A player may hold one of three possible cards: A, K, or Q. They may be asked to act after any of 6 possible betting histories:
History Meaning
no actions have taken place yet
c player 1 checked
cr player 1 checked, player 2 bet
crr player 1 checked, player 2 bet, player 1 raised
r player 1 bet
rr player 1 bet, player 2 raised
With 3 cards and 6 histories, there are a total of 3 × 6 = 18 game states.
When it's their turn, a player may make one of three choices: fold (f), check/call (c), or bet/raise (r). Not all choices are available in all game states. A player can only fold in response to an opponent's raise, and a player cannot raise if two raises have already occurred.
Initially, our result table stores a 0 for the number of games and amount won in response to each choice. After thousands of games it might look something like this:
Game State Choice Games Won
...
K c 2000 1600
K r 1000 900
...
Krr f 300 0
Krr c 10 -3
...
Suppose I have $10 in my stack. I pay a $1 ante, leaving me with $9 in my stack. I'm dealt a king, and I'm the first player to act. I find myself in game state K (representing a king and an empty betting history). I can check or raise. The result table above shows the expected value for betting (900/1000 = 0.9) is higher than the value for checking (1600/2000 = 0.8). I therefore bet. I record the game state (K), my choice to bet (r), and the amount in my stack at the time (9).
<K, r, 9>
Now suppose my opponent raises. I now find myself in game state Krr (representing a king, a bet, and then a raise). I now have $8 (having just bet $1). I can fold or call. Normally, I'd consult the result table, which tells me that folding (0/300 = 0.0) is preferable to calling (-3/10 = -0.3). However, we'll suppose this is the 1% of the time that I make a random choice instead of following the table. At this time, I randomly choose to call. I record the game state (Krr), my choice to call (c) and the amount in my stack at the time (8).
<K, r, 9>, <Krr, c, 8>
I now have $7 (having just called $1). Suppose my opponent reveals a queen. I win the $6 pot, which means I now have $13 in my stack.
Now I go back and update the result table. When I bet in state K, I had $9. As a result of that choice, I wound up with $13. Betting earned me $13 - $9 = $4. Previously, that choice had earned me $900 in 1000 games. Now, it's earned me $900 + $4 = $904 in 1001 games. Likewise, when I called in state Krr, I had $8. I wound up with $13, so calling earned me $13 - $8 = $5. Previously, that choice had earned me $-3 in 11 games. Now, it's earned me $-3 + $5 = $2 in 11 games. I therefore update the result table as follows.
Game State Choice Games Won
...
K c 2000 1600
K r 1001 904
...
Krr f 300 0
Krr c 11 2
...
It took about 3 hours for my learning software to run for 10 billion games. Here are the results, presented in a more compact format. The values show the amount won divided by the number of games played, for each valid choice. The result of that division would give the expected value. (M signifies millions and B represents billions.)
Game State Fold Check/Call Bet/Raise
Q 699M/3.2B 29M/164M
K 2.5B/3.3B 44M/61M
A 5.6B/3.1B 361M/206M
Qcr 0/1.4B -2.4M/4.7M -3.4M/4.7M
Kcr 0/546M 1.2k/937M -3.1M/5.0M
Acr 0/4.8M 7.5M/4.8M 2.2B/1.4B
Qc 705M/2.0B 394M/1.1B
Kc 3.2B/3.2B 15M/18M
Ac 26M/15M 6.0B/3.2B
Qcrr 0/394M -2.0M/2.0M
Acrr 0/5.2M 2.1B/1.0B
Using the strategy suggested here, game states like Ar and Kcrr are never reached and have been omitted from the results above. (A careful study shows that player 1 never begins with a bet, and player 2 never bets a king.)
The boldfaced data above show which choices we should make for correct play. The suggested strategy is summarized in the following table.
Player Card Play
1 queen check+fold
1 king check+call 2/3, check+fold 1/3
1 ace check+raise
2 queen check 2/3, bet 1/3
2 king check
2 ace bet
It shows that player 1 should always begin by checking. If, for example, player 2 responds with a bet and player 1 has a king, then player 1 should call with probability 2/3 and fold with probability 1/3.
In the event that player 1 deviates from correct play by leading off with a bet, then player 2 should fold a queen, fold (1/2) or call (1/2) with a king, and raise an ace. If raised, player 1 should fold a queen but call with a king or ace.
Background
My earlier exploration of Counterfactual Regret Minimization (CRM) led me to the much simpler idea I presented here. Also, a weakness of CRM is that it requires a special implementation of the game software during training, whereas my approach allows a bot to train without modifying the game software. I suspect that the results of my approach are equivalent to CRM. It would be worth exploring ways to speed up learning, so that my algorithm approaches an optimal strategy in fewer games.
Idea
Play a game billions of times. As you play, keep track of every game state reached, every choice made in those states, how often each choice was made, and how often each choice resulted in a win. When learning, use the data accumulated to make choices that maximize the chance of winning. When done learning, the recommended strategy consists of the choices that were made most often.
Details
1. Identify every game state. A game state includes everything currently known to the player. In poker, this could include the player's hand and opponents' betting, but it cannot include opponents' unseen hands or the arrangement of cards in the deck. For most interesting games, a collection of game states would be too large to store in memory, or would be so large that finding an optimal strategy would be too computationally intensive. Therefore, much work goes into identifying which aspects of a game state to consider and which to ignore. For example, we might include a poker player's hand category (high card, pair, two pair, etc) but not their particular cards. Likewise, we might include the amount of money on a poker table, but not the details of who contributed that money and when.
2. Identify all possible choices that a player might make from any particular game state. Again, some games may need to be simplified to keep this manageable (such as limiting how much a poker player can raise).
3. For each game state and choice, store the number of times that choice was made and the accumulated gains resulting from that choice. For example, I might have encountered a particular state S on 100 occasions. On 30 of those times, I chose option C. In 20 out of those 30 cases, I went on to win the game. I would therefore record that state S and choice C resulted in 20 wins in 30 games. In the case of poker, instead of recording the number of games won, we would record the total amount of money gained as a result of a choice. For example, I might record that state S and choice C resulted in earning -12 dollars after 40 hands.
Let's call all this data our result table. It maps any game state and choice to the resulting number of wins and games.
<game state, choice> → <wins, games>4. For any particular game state, the expected value of a particular choice is the number of wins (or money gained) divided by the number of times that choice was made. This value is easily computed from the result table. For example, if state S and choice C resulted in 20 wins in 30 games, then the expected value for choice C in state S is 20 / 30 ≈ 0.667. Likewise, if state S and choice C resulted in earning -12 dollars after 40 poker hands, then the expected value is -12 / 40 = -0.3.
5. In the course of learning, whenever a player must make a choice, use the result table to compute the expected value for each possible choice, and choose the option with the greatest expected value. For example, suppose I find myself in some game state, and I must choose from among options A, B, and C. I determine the expected value of A is 0.5, the expected value of B is 0.9, and the expected value of C is 0.1. I will therefore choose option B to maximize my expected value.
6. During the course of each game played, record each game state reached and each choice made. For example, I might record that, when I found myself in game state S1, I made choice A, and when I then found myself in game state S2, I made choice B.
<game state, choice>, <game state, choice>, ..., <game state, choice>If this is a game like poker, I must record the amount of money I had at the time a choice was made, so that I can later determine how much I gained or lost as a result of that choice.
Note that this list of choices made is separate from the result table. In fact, each bot using this learning algorithm must keep its own list of choices made, even though they might all share a single result table.
7. After each game (or poker hand), when the outcome is known (who won the game, or how much each player earned), go through all of the choices made by a player and record the results of those choices in the result table. For example, suppose I reached game state S and made choice C at some point during a game. In previous games, I had made choice C in game state S on 9 occasions, and I went on to win the game on 6 of those occasions. Suppose I now win this particular game. I must increment both the number of games and the number of wins for state S and choice C, so they now show I went on to win the game on 7 of 10 occasions. On the other hand, if I had lost, then I would not have incremented the number of wins, and my result table would record that I had won the game on 6 of 10 occasions. Once I've recorded the outcomes of all choices made in the game, then I can safely discard the list of choices made and begin the next game with an empty list.
8. In the course of learning, a player must sometimes make a choice with a lower expected value. This is because an issue arises if a player always makes the choice with the greatest expected value. Before the result table closes in on an optimal strategy, it will often guide a player to make a non-optimal choice. For example, suppose that in a certain game state, choice A's theoretical expected value is 0.8, while choice B's expected value is 0.5. Choice A is therefore the optimal choice in this game state. In the long run, we hope the data in our result table will converge to these expected values. But early in our learning, the expected values in our result table may be very different. Let's consider two scenarios.
In the first scenario, a moment occurs when choice A's expected value is 0.8 and choice B's is 0.9. Because B currently has the greater expected value, our player will keep choosing B. Eventually, we expect that option B will perform poorly enough that its expected value drops below A's (0.8), and the player will then begin to make the optimal choice. In this scenario, the algorithm has self-corrected.
In the second scenario, a moment occurs when choice A's expected value is 0.3 and choice B's is 0.9. Again, because B currently has the greater expected value, our player will keep choosing B. We expect that B's expected value will approach the theoretical value of 0.5. But in doing so, it may never drop below A's current expected value of 0.3, and therefore the player may never get the chance to try out option A again and discover that it will outperform B in the long run. Our algorithm has gotten stuck.
For this reason, it is necessary for the player to sometimes make a choice with a lower expected value. Perhaps 1% of the time, a player should make a random choice (instead of the one with the greatest expected value). In practice, 1% is a good probability to use. The higher this probability is, the less likely the algorithm is to get stuck. It will therefore converge more quickly, but to less accurate values. A lower probability of random play gives more accurate values, but is more likely to get stuck without finding an optimal strategy.
9. Ultimately, the learning algorithm will most likely require billions of games before the result table converges to meaningful results. (Note that 32-bit integers are therefore unlikely to be sufficient for storing numbers of wins and games.)
10. At the conclusion of the learning process, focus on the result table's numbers of games--not expected values. For example, suppose that, for some particular game state, our result table shows the following data:
choice A: 2 billion wins in 5 billion games (expected value = 0.40)It would be incorrect to conclude that choice A is optimal just because it has the greatest expected value. Notice that the computer chose option C twice as often as it chose A, and that their expected values (0.40 and 0.39) are very close. Notice also that the computer chose option B far less often (in only 50 million games), and that B's expected value is much lower (0.10). What probably happened here is that the computer found that option B performed poorly compared with A and C. After a while, it stopped choosing option B (except on those 1% of occasions when it made a choice at random), resulting in a much lower number of games.
choice B: 5 million wins in 50 million games (expected value = 0.10)
choice C: 3.9 billion wins in 10 billion games (expected value = 0.39)
On the other hand, option C was used twice as often as A, and both resulted in similar expected values. Most likely, whenever the computer chose C a couple of times in a row, it learned to defend against that choice. This temporarily made A's expected value greater than C's, and so the computer chose A next. But then the computer adjusted to defend against A, making C the better choice again.
So, which choice does our result table recommend? The answer comes from the numbers of games. The computer reached this game state in roughly 15 billion games. It chose A in 5 billion of those games and C in 10 billion. Therefore, the optimal strategy suggested by the result table is for us to choose A with probability 1/3, choose C with probability 2/3, and never choose B. In other words, a mixed strategy is required. A pure strategy (in which the computer always makes the same choice) could be exploited.
11. A game may have many optimal strategies (each of which may itself be a mixed strategy). Suppose we run our software once, and it recommends one strategy, and then we run it again only to find it recommends a different strategy. This might mean that we didn't run the software long enough for it to arrive at an optimal strategy. But it might simply mean that the software converged to two different and equally optimal strategies.
Example
Let's see how this algorithm is used to solve a toy version of poker. In this 2-player game, each player pays a $1 ante. Each player is dealt an ace (highest), king, or queen (each equally likely). Note that both players may be dealt the same card value. Players take turns acting by folding, calling/checking, or betting/raising in increments of $1, with a maximum of 2 raises. A couple examples illustrate how the game is played.
Example #1. After antes, there is $2 in the pot. Player 1 is dealt an ace and player 2 is dealt a king. Player 1 checks. Player 2 bets. There is now $3 in the pot. Player 1 raises. There is now $5 in the pot. Player 2 folds. Player 1 keeps all $5. Player 1 has gained $2 and player 2 has lost $2.
Example #2. After antes, there is $2 in the pot. Both players are dealt a king. Player 1 bets. There is now $3 in the pot. Player 2 calls. There is now $4 in the pot. Both players show their cards. Because they hold the same cards, they split the pot, each collecting $2. Each player has gained $0.
Let's identify the game states. A player may hold one of three possible cards: A, K, or Q. They may be asked to act after any of 6 possible betting histories:
History Meaning
no actions have taken place yet
c player 1 checked
cr player 1 checked, player 2 bet
crr player 1 checked, player 2 bet, player 1 raised
r player 1 bet
rr player 1 bet, player 2 raised
With 3 cards and 6 histories, there are a total of 3 × 6 = 18 game states.
When it's their turn, a player may make one of three choices: fold (f), check/call (c), or bet/raise (r). Not all choices are available in all game states. A player can only fold in response to an opponent's raise, and a player cannot raise if two raises have already occurred.
Initially, our result table stores a 0 for the number of games and amount won in response to each choice. After thousands of games it might look something like this:
Game State Choice Games Won
...
K c 2000 1600
K r 1000 900
...
Krr f 300 0
Krr c 10 -3
...
Suppose I have $10 in my stack. I pay a $1 ante, leaving me with $9 in my stack. I'm dealt a king, and I'm the first player to act. I find myself in game state K (representing a king and an empty betting history). I can check or raise. The result table above shows the expected value for betting (900/1000 = 0.9) is higher than the value for checking (1600/2000 = 0.8). I therefore bet. I record the game state (K), my choice to bet (r), and the amount in my stack at the time (9).
<K, r, 9>
Now suppose my opponent raises. I now find myself in game state Krr (representing a king, a bet, and then a raise). I now have $8 (having just bet $1). I can fold or call. Normally, I'd consult the result table, which tells me that folding (0/300 = 0.0) is preferable to calling (-3/10 = -0.3). However, we'll suppose this is the 1% of the time that I make a random choice instead of following the table. At this time, I randomly choose to call. I record the game state (Krr), my choice to call (c) and the amount in my stack at the time (8).
<K, r, 9>, <Krr, c, 8>
I now have $7 (having just called $1). Suppose my opponent reveals a queen. I win the $6 pot, which means I now have $13 in my stack.
Now I go back and update the result table. When I bet in state K, I had $9. As a result of that choice, I wound up with $13. Betting earned me $13 - $9 = $4. Previously, that choice had earned me $900 in 1000 games. Now, it's earned me $900 + $4 = $904 in 1001 games. Likewise, when I called in state Krr, I had $8. I wound up with $13, so calling earned me $13 - $8 = $5. Previously, that choice had earned me $-3 in 11 games. Now, it's earned me $-3 + $5 = $2 in 11 games. I therefore update the result table as follows.
Game State Choice Games Won
...
K c 2000 1600
K r 1001 904
...
Krr f 300 0
Krr c 11 2
...
It took about 3 hours for my learning software to run for 10 billion games. Here are the results, presented in a more compact format. The values show the amount won divided by the number of games played, for each valid choice. The result of that division would give the expected value. (M signifies millions and B represents billions.)
Game State Fold Check/Call Bet/Raise
Q 699M/3.2B 29M/164M
K 2.5B/3.3B 44M/61M
A 5.6B/3.1B 361M/206M
Qcr 0/1.4B -2.4M/4.7M -3.4M/4.7M
Kcr 0/546M 1.2k/937M -3.1M/5.0M
Acr 0/4.8M 7.5M/4.8M 2.2B/1.4B
Qc 705M/2.0B 394M/1.1B
Kc 3.2B/3.2B 15M/18M
Ac 26M/15M 6.0B/3.2B
Qcrr 0/394M -2.0M/2.0M
Acrr 0/5.2M 2.1B/1.0B
Using the strategy suggested here, game states like Ar and Kcrr are never reached and have been omitted from the results above. (A careful study shows that player 1 never begins with a bet, and player 2 never bets a king.)
The boldfaced data above show which choices we should make for correct play. The suggested strategy is summarized in the following table.
Player Card Play
1 queen check+fold
1 king check+call 2/3, check+fold 1/3
1 ace check+raise
2 queen check 2/3, bet 1/3
2 king check
2 ace bet
It shows that player 1 should always begin by checking. If, for example, player 2 responds with a bet and player 1 has a king, then player 1 should call with probability 2/3 and fold with probability 1/3.
In the event that player 1 deviates from correct play by leading off with a bet, then player 2 should fold a queen, fold (1/2) or call (1/2) with a king, and raise an ace. If raised, player 1 should fold a queen but call with a king or ace.
Background
My earlier exploration of Counterfactual Regret Minimization (CRM) led me to the much simpler idea I presented here. Also, a weakness of CRM is that it requires a special implementation of the game software during training, whereas my approach allows a bot to train without modifying the game software. I suspect that the results of my approach are equivalent to CRM. It would be worth exploring ways to speed up learning, so that my algorithm approaches an optimal strategy in fewer games.
Dave Computes Simple Five-Card Draw Poker Strategies
We're considering a 5-player game of Five-Card Draw Poker with the following simple structure:
1. Each player pays a $1 ante and is dealt 5 cards.
2. A round of betting occurs, with betting in increments of $1 up to a cap of $4.
3. Active players exchange 0 - 5 cards.
4. Active players participate in a second round of betting, still with increments of $1 and a cap of $4.
5. Active players show their cards and the winner takes the pot.
It seemed to me that the simplest interesting strategy would be to ignore everything but the strength of my own hand, folding weak hands, calling middle hands, and raising strong hands. To that end, I programmed a computer to play 100 million rounds using counterfactual regret minimization. Here's the mixed strategy that emerged:
With probability 66%, always raise AA or better, folding all else.
With probability 14%, always raise QQ or better, folding all else.
With probability 10%, always raise JJ or better, folding all else.
With probability 10%, always raise any pair or better or 4-flush or open-ended straight draw, folding all else.
A player using this mixed strategy chooses one of these pure strategies at the beginning of each hand (before seeing any cards), and then uses that strategy through the end of the hand, choosing the next pure strategy at the beginning of the next hand.
After this experiment, I went on to use a much more comprehensive machine learning algorithm (explained in the next post). Here are some things I learned from it (and from other experiments), or that I suspect are true after watching a number of bots play and performing some rudimentary calculations:
1. Before the exchange, generally bet high pairs, raise 2-pairs, reraise trips, and cap with straights or better. Call for 1 bet with any pair or 4-flush or open-ended straight draw. It probably takes 2-pair or possibly a high pair to call 2 bets.
2. Exchange 0 cards if you've got a 5-card hand (straight, flush, full house). Exchange 1 card if you've got quads, just to let your opponents think you might have 2 pairs. Exchange 2 cards if you've got trips. Exchange 1 card if you've got 2 pairs. Exchange 3 cards if you've got a pair. Exchange 1 card if you've got a 4-flush or open-ended straight draw and no pair. Exchange 4 cards if you've got an ace-high or king-high hand. Exchange all 5 cards if you've got a queen-high hand or worse. Sometimes it's advantageous to exchange fewer cards in order to appear stronger. Doing so may prevent an opponent from betting and allow you to see a showdown for free, or it may allow you to bluff an opponent out of a pot if they show weakness. For example, you might exchange 3 with a high-card hand or exchange 2 with a pair.
3. Raise all the way with a straight or better. Otherwise, notice how many cards each player exchanges. If someone exchanged 0 (representing a straight or better) or 2 (representing trips), generally don't bet. But in case they're bluffing, be prepared to call 1 opponent with a high pair or multiple opponents with 2 pairs or better. Otherwise, if someone exchanged 1, they probably have 2 pairs that did not improve. Bet with trips and a strong 2 pair. Be prepared to call with a high pair. It's possible that an opponent who exchanged 1 is on a flush or straight draw. In that case, it's probably best not to bet. If they made their draw, betting or raising will cost you more than if you just call their bet. If they missed their draw, they probably won't call your bet anyway. Otherwise, if someone exchanged 3, you can probably bet high pairs safely. If many opponents exchanged 3, it's likely someone will make 2-pair or better, so now you want to be more careful with what you bet. If everyone exchanged 4 or more, you can probably bet high pairs.
1. Each player pays a $1 ante and is dealt 5 cards.
2. A round of betting occurs, with betting in increments of $1 up to a cap of $4.
3. Active players exchange 0 - 5 cards.
4. Active players participate in a second round of betting, still with increments of $1 and a cap of $4.
5. Active players show their cards and the winner takes the pot.
It seemed to me that the simplest interesting strategy would be to ignore everything but the strength of my own hand, folding weak hands, calling middle hands, and raising strong hands. To that end, I programmed a computer to play 100 million rounds using counterfactual regret minimization. Here's the mixed strategy that emerged:
With probability 66%, always raise AA or better, folding all else.
With probability 14%, always raise QQ or better, folding all else.
With probability 10%, always raise JJ or better, folding all else.
With probability 10%, always raise any pair or better or 4-flush or open-ended straight draw, folding all else.
A player using this mixed strategy chooses one of these pure strategies at the beginning of each hand (before seeing any cards), and then uses that strategy through the end of the hand, choosing the next pure strategy at the beginning of the next hand.
After this experiment, I went on to use a much more comprehensive machine learning algorithm (explained in the next post). Here are some things I learned from it (and from other experiments), or that I suspect are true after watching a number of bots play and performing some rudimentary calculations:
1. Before the exchange, generally bet high pairs, raise 2-pairs, reraise trips, and cap with straights or better. Call for 1 bet with any pair or 4-flush or open-ended straight draw. It probably takes 2-pair or possibly a high pair to call 2 bets.
2. Exchange 0 cards if you've got a 5-card hand (straight, flush, full house). Exchange 1 card if you've got quads, just to let your opponents think you might have 2 pairs. Exchange 2 cards if you've got trips. Exchange 1 card if you've got 2 pairs. Exchange 3 cards if you've got a pair. Exchange 1 card if you've got a 4-flush or open-ended straight draw and no pair. Exchange 4 cards if you've got an ace-high or king-high hand. Exchange all 5 cards if you've got a queen-high hand or worse. Sometimes it's advantageous to exchange fewer cards in order to appear stronger. Doing so may prevent an opponent from betting and allow you to see a showdown for free, or it may allow you to bluff an opponent out of a pot if they show weakness. For example, you might exchange 3 with a high-card hand or exchange 2 with a pair.
3. Raise all the way with a straight or better. Otherwise, notice how many cards each player exchanges. If someone exchanged 0 (representing a straight or better) or 2 (representing trips), generally don't bet. But in case they're bluffing, be prepared to call 1 opponent with a high pair or multiple opponents with 2 pairs or better. Otherwise, if someone exchanged 1, they probably have 2 pairs that did not improve. Bet with trips and a strong 2 pair. Be prepared to call with a high pair. It's possible that an opponent who exchanged 1 is on a flush or straight draw. In that case, it's probably best not to bet. If they made their draw, betting or raising will cost you more than if you just call their bet. If they missed their draw, they probably won't call your bet anyway. Otherwise, if someone exchanged 3, you can probably bet high pairs safely. If many opponents exchanged 3, it's likely someone will make 2-pair or better, so now you want to be more careful with what you bet. If everyone exchanged 4 or more, you can probably bet high pairs.
Saturday, April 6, 2019
Dave Computes Five-Card Draw Probabilities
In this post, I'll provide most probabilities as percentages rounded to the nearest percent.
(It's harder to memorize or identify patterns with more precise numbers.)
A hand of 5 cards is dealt. How strong is it likely to be?
1% chance of straight-or-better
2% chance of trips
5% chance of 2 pair
42% chance of a pair
50% chance of high card hand
Let's break those high card hands down further. Of all hands,
50% are pairs or better
19% are A high
13% are K high
8% are Q high
5% are J high
3% are T high
1% are 9 high
0.5% are 8 high
0.15% are 7 high
There's about a 42 / 13 ≈ 3.23% chance of being dealt any particular pair.
We can therefore rank all hands as follows:
top 1%: straight-or-better
top 3%: trips
top 8%: 2 pair
top 11%: AA
top 14%: KK
top 18%: QQ
top 21%: JJ
top 24%: TT
top 27%: 99
top 31%: 88
top 34%: 77
top 37%: 66
top 40%: 55
top 44%: 44
top 47%: 33
top 50%: 22
top 69%: A high
top 82%: K high
top 90%: Q high
top 95%: J high
top 98%: T high
top 99%: 9 high
top 100%: 8 high or 7 high
Now let's consider what happens when we exchange cards.
We're dealt a pair and we exchange the other 3 cards:
71% chance unimproved
16% chance of 2 pair
11% chance of trips
1% chance of full house
We're dealt 2 pairs and we exchange the other 1 card:
91.5% chance unimproved
8.5% chance of full house
We're dealt trips and we exchanged the other 2 cards:
90% chance unimproved
6% chance of full house
4% chance of quads
There's a 5% chance we'll be dealt a high card hand with a 4-flush or open-ended straight draw.
We're dealt a 4-flush and we exchange the other 1 card:
19% chance of flush
26% chance of pair
55% chance unimproved
We're dealt an open-ended straight and we exchange the other 1 card:
17% chance of straight
26% chance of pair
57% chance unimproved
A common situation occurs when I have a pair and I'm up against a single opponent, who I believe has a higher pair. We each exchange 3 cards. To win, I need to make 2-pair or better, and I need my opponent to remain unimproved. I've got a 29% change of improving, and my opponent has a 71% of not improving. Overall, that's a 29% × 71% ≈ 21%. That's very close to the probability that I make my 4-flush or open-ended-straight draw.
On the other hand, if I make a straight or flush draw, it's much more likely to hold up in a multi-player hand. If I'm one of 3 players holding a pair, then now I only have a 29% × 71% × 71% ≈ 15% chance of overtaking my opponents. That number falls to 10% if 4 players exchange.
(It's harder to memorize or identify patterns with more precise numbers.)
A hand of 5 cards is dealt. How strong is it likely to be?
1% chance of straight-or-better
2% chance of trips
5% chance of 2 pair
42% chance of a pair
50% chance of high card hand
Let's break those high card hands down further. Of all hands,
50% are pairs or better
19% are A high
13% are K high
8% are Q high
5% are J high
3% are T high
1% are 9 high
0.5% are 8 high
0.15% are 7 high
There's about a 42 / 13 ≈ 3.23% chance of being dealt any particular pair.
We can therefore rank all hands as follows:
top 1%: straight-or-better
top 3%: trips
top 8%: 2 pair
top 11%: AA
top 14%: KK
top 18%: QQ
top 21%: JJ
top 24%: TT
top 27%: 99
top 31%: 88
top 34%: 77
top 37%: 66
top 40%: 55
top 44%: 44
top 47%: 33
top 50%: 22
top 69%: A high
top 82%: K high
top 90%: Q high
top 95%: J high
top 98%: T high
top 99%: 9 high
top 100%: 8 high or 7 high
Now let's consider what happens when we exchange cards.
We're dealt a pair and we exchange the other 3 cards:
71% chance unimproved
16% chance of 2 pair
11% chance of trips
1% chance of full house
We're dealt 2 pairs and we exchange the other 1 card:
91.5% chance unimproved
8.5% chance of full house
We're dealt trips and we exchanged the other 2 cards:
90% chance unimproved
6% chance of full house
4% chance of quads
There's a 5% chance we'll be dealt a high card hand with a 4-flush or open-ended straight draw.
We're dealt a 4-flush and we exchange the other 1 card:
19% chance of flush
26% chance of pair
55% chance unimproved
17% chance of straight
26% chance of pair
57% chance unimproved
A common situation occurs when I have a pair and I'm up against a single opponent, who I believe has a higher pair. We each exchange 3 cards. To win, I need to make 2-pair or better, and I need my opponent to remain unimproved. I've got a 29% change of improving, and my opponent has a 71% of not improving. Overall, that's a 29% × 71% ≈ 21%. That's very close to the probability that I make my 4-flush or open-ended-straight draw.
On the other hand, if I make a straight or flush draw, it's much more likely to hold up in a multi-player hand. If I'm one of 3 players holding a pair, then now I only have a 29% × 71% × 71% ≈ 15% chance of overtaking my opponents. That number falls to 10% if 4 players exchange.
Dave Computes Opening Betting in Poker with an Ante Structure
In a blind structure, a player should generally open with a raise or fold. Once a player folds, it's as if they were never in the hand to any players who have left to act.
Things are more complicated in an ante structure, where a player can open with a bet or check. Later players must consider that they may be beat by an earlier player who checked.
2 Players
P1 (the first player to act) assumes P2 (the second to act) is likely to have a 50th-percentile hand. Thus, P1 expects a top-50% hand is likely to win.
If P1 bets any top-50% hand, P2 figures that P1 is likely to have a hand in the middle of that range: a 25th-percentile hand. Thus, P2 needs a top-25% hand for a likely win. P2 might therefore raise with a top-25% hand and fold the rest.
Alternatively, if P1 checks a bottom-50% hand, then P2 figures that P1 is likely to have a hand in the middle of that range: a 75th-percentile hand. Thus, P2 only needs a top-75% hand for a likely win. P2 might therefore open by betting a top-75% hand and checking the rest.
We can summarize this play as:
P1 bet top 50% -> P2 raise top 25%
P1 check bottom 50% -> P2 bets top 75%
(Of course, we're simplifying things considerably by ignoring possibilities of check-raising or bluffing.)
3 Players
Suppose P1 has a top-10% hand. There's a 90% chance they've got P2 beat and a 90% chance they've got P3 beat. That's a 0.9 * 0.9 = 81% chance they've got both players beat. Suppose P1 holds a top-x hand For an even chance of holding the best hand, (1 - x)(1 - x) = 0.5, which is satisfied when x = 29%. Therefore, P1 might open by betting a top 29% hand and checking the rest.
Suppose P1 bets. P2 can expect to beat P1 with a top-14.5% hand (29/2), but things are worse when we consider that P3 might still beat such a hand. P2 needs a top-12% hand for a likely win over both players.
Alternatively, if P1 checks, P2 expects P1 to have a bottom-71% hand and P3 to have any hand. P2 needs a top-40% hand for a likely win over both now.
Now considering all situations that P3 might face, we can summarize this play as:
P1 bets top 29% -> P2 raises top 12% -> P3 reraises top 4%
P1 bets top 29% -> P2 folds bottom 88% -> P3 raises top 14%
P1 checks bottom 71% -> P2 bets top 40% -> P3 raises top 19%
P1 checks bottom 71% -> P2 checks bottom 60% -> P3 bets top 47%
4 Players
P1 bets top 20% -> P2 raises top 8% -> P3 reraises top 3% -> P4 caps top 1%
P1 bets top 20% -> P2 raises top 8% -> P3 folds -> P4 reraises top 3%
P1 bets top 20% -> P2 folds bottom 92% -> P3 raises top 9% -> P4 reraises top 3%
P1 bets top 20% -> P2 folds bottom 92% -> P3 folds bottom 91%- > P4 raises top 9%
P1 checks bottom 80% -> P2 bets top 26% -> P3 raises top 11% -> P4 reraises top 4%
P1 checks bottom 80% -> P2 bets top 26% -> P3 folds -> P4 raises top 12%
P1 checks bottom 80% -> P2 checks bottom 74% -> P3 bets top 33% -> P4 raises top 16%
P1 checks bottom 80% -> P2 checks bottom 74% -> P3 checks bottom 67% -> P4 bets 41%
5 Players
P1 bets top 15% -> P2/P3/P4/P5 raises top 5 - 7%
P1 checks bottom 85% -> P2 bets top 19% -> P3/P4/P5 raises top 7 - 9%
P1 checks bottom 85% -> P2 checks bottom 81% -> P3 bets top 23%
-> P4/P5 raises top 10 - 11%
P1 checks bottom 85% -> P2 checks bottom 81% -> P3 checks bottom 77%
-> P4 bets top 28% -> P5 raises top 13%
P1 checks bottom 85% -> P2 checks bottom 81% -> P3 checks bottom 77%
-> P4 checks bottom 72% -> P5 bets top 33%
Dave Computes Evaluating Poker Hands
Here's a simple algorithm for categorizing and sorting a 5-card poker hand, for the purpose of determining whether one hand is stronger than another.
Step 1: Determine frequencies of each rank
Ranks range from 2 to 14, where Jack is 11, Queen is 12, King is 13, and Ace is 14.
Make an array rankFreqs of 15 integers, indexed from 0 to 14, so that rankFreqs[6] indicates the number of 6s in a particular hand. Positions 0 and 1 are ignored. The values in the array are first initialized to 0.
int[] rankFreqs = new int[15];
For each card in the hand, increment the value in rankFreqs corresponding to that card's rank.
for (Card card : hand)
rankFreqs[card.getRank()]++;
For the following hand
rankFreqs contains [0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 2, 1, 0, 1].
Step 2: Sort the hand, first by rank frequency, and then by rank
In the course of sorting the hand, card x should precede card y if x's rank occurs more often than y's. If both ranks occur the same number of times, then x should precede y if x's rank is greater than y's.
For the hand above, J precedes A (because there are more jacks than aces) and Q precedes 7 (because there are the same number of Qs and 7s, and Q is higher than 7). Here's an implementation using selection sort.
for (int i = 0; i < hand.length; i++)
{
for (int j = i + 1; j < hand.length; j++)
{
int ranki = hand[i].getRank();
int rankj = hand[j].getRank();
int freqi = rankFreqs[ranki];
int freqj = rankFreqs[rankj];
if (freqj > freqi || (freqj == freqi && rankj > ranki))
swap(hand, i, j);
}
}
After sorting, the hand contains:
Step 3: Test for a flush
Simply determine that all 5 cards in the hand have the same suit. No loop required.
boolean flush =
hand[0].getSuit() == hand[1].getSuit() &&
hand[0].getSuit() == hand[2].getSuit() &&
hand[0].getSuit() == hand[3].getSuit() &&
hand[0].getSuit() == hand[4].getSuit();
Step 4: Test for a straight
Straights are just as easy, except that we need to test for 5-high straights. These are currently mis-sorted as A5432 and must be re-sorted as 5432A. For any other straight, we just need to test that each card's rank is one higher than the next.
boolean straight;
if (hand[0].getRank() == 14 && hand[1].getRank() == 5 &&
hand[2].getRank() == 4 && hand[3].getRank() == 3 &&
hand[4].getRank() == 2)
{
straight = true; //5-high straight
Card ace = hand[0];
hand[0] = hand[1];
hand[1] = hand[2];
hand[2] = hand[3];
hand[3] = hand[4];
hand[4] = ace;
}
else
{
straight =
hand[0].getRank() == hand[1].getRank() + 1 &&
hand[1].getRank() == hand[2].getRank() + 1 &&
hand[2].getRank() == hand[3].getRank() + 1 &&
hand[3].getRank() == hand[4].getRank() + 1;
}
Step 5: Categorize the hand, testing for the strongest categories first
Now that we've done the hard work, categorizing the hand is easy. Assume we have integer constants defined for categories, such that STRAIGHT_FLUSH > FOUR_OF_A_KIND > FULL_HOUSE > FLUSH > STRAIGHT > THREE_OF_A_KIND > TWO_PAIR > PAIR > HIGH_CARD. We test for the strongest categories first.
if (straight && flush) return STRAIGHT_FLUSH;
if (hand[0].getRank() == hand[3].getRank()) return FOUR_OF_A_KIND;
if (hand[3].getRank() == hand[4].getRank()) return FULL_HOUSE;
if (flush) return FLUSH;
if (straight) return STRAIGHT;
if (hand[0].getRank() == hand[2].getRank()) return THREE_OF_A_KIND;
if (hand[2].getRank() == hand[3].getRank()) return TWO_PAIR;
if (hand[0].getRank() == hand[1].getRank()) return PAIR;
return HIGH_CARD;
Comparing Hands
Having sorted hands and identified their categories, it's easy to determine whether one hand beats another. If hand x's category is greater than y's, then x is the better hand. If they have the same category, then we compare the sorted hands, card by card. If x's card ever outranks y's, then x is the better hand. If all corresponding cards have the same ranks, then the hands are equal, presumably resulting in a split pot.
if (category1 > category2) return 1; //hand 1 is stronger
if (category2 > category1) return 2; //hand 2 is stronger
for (int i = 0; i < 5; i++)
{
int rank1 = hand1[i].getRank();
int rank2 = hand2[i].getRank();
if (rank1 > rank2) return 1; //hand 1 is stronger
if (rank2 > rank1) return 2; //hand 2 is stronger
}
return 0; //hands are equally strong
Step 1: Determine frequencies of each rank
Ranks range from 2 to 14, where Jack is 11, Queen is 12, King is 13, and Ace is 14.
Make an array rankFreqs of 15 integers, indexed from 0 to 14, so that rankFreqs[6] indicates the number of 6s in a particular hand. Positions 0 and 1 are ignored. The values in the array are first initialized to 0.
int[] rankFreqs = new int[15];
For each card in the hand, increment the value in rankFreqs corresponding to that card's rank.
for (Card card : hand)
rankFreqs[card.getRank()]++;
rankFreqs contains [0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 2, 1, 0, 1].
Step 2: Sort the hand, first by rank frequency, and then by rank
In the course of sorting the hand, card x should precede card y if x's rank occurs more often than y's. If both ranks occur the same number of times, then x should precede y if x's rank is greater than y's.
For the hand above, J precedes A (because there are more jacks than aces) and Q precedes 7 (because there are the same number of Qs and 7s, and Q is higher than 7). Here's an implementation using selection sort.
for (int i = 0; i < hand.length; i++)
{
for (int j = i + 1; j < hand.length; j++)
{
int ranki = hand[i].getRank();
int rankj = hand[j].getRank();
int freqi = rankFreqs[ranki];
int freqj = rankFreqs[rankj];
if (freqj > freqi || (freqj == freqi && rankj > ranki))
swap(hand, i, j);
}
}
After sorting, the hand contains:
Step 3: Test for a flush
boolean flush =
hand[0].getSuit() == hand[1].getSuit() &&
hand[0].getSuit() == hand[2].getSuit() &&
hand[0].getSuit() == hand[3].getSuit() &&
hand[0].getSuit() == hand[4].getSuit();
Step 4: Test for a straight
Straights are just as easy, except that we need to test for 5-high straights. These are currently mis-sorted as A5432 and must be re-sorted as 5432A. For any other straight, we just need to test that each card's rank is one higher than the next.
boolean straight;
if (hand[0].getRank() == 14 && hand[1].getRank() == 5 &&
hand[2].getRank() == 4 && hand[3].getRank() == 3 &&
hand[4].getRank() == 2)
{
straight = true; //5-high straight
Card ace = hand[0];
hand[0] = hand[1];
hand[1] = hand[2];
hand[2] = hand[3];
hand[3] = hand[4];
hand[4] = ace;
}
else
{
straight =
hand[0].getRank() == hand[1].getRank() + 1 &&
hand[1].getRank() == hand[2].getRank() + 1 &&
hand[2].getRank() == hand[3].getRank() + 1 &&
hand[3].getRank() == hand[4].getRank() + 1;
}
Step 5: Categorize the hand, testing for the strongest categories first
Now that we've done the hard work, categorizing the hand is easy. Assume we have integer constants defined for categories, such that STRAIGHT_FLUSH > FOUR_OF_A_KIND > FULL_HOUSE > FLUSH > STRAIGHT > THREE_OF_A_KIND > TWO_PAIR > PAIR > HIGH_CARD. We test for the strongest categories first.
if (straight && flush) return STRAIGHT_FLUSH;
if (hand[0].getRank() == hand[3].getRank()) return FOUR_OF_A_KIND;
if (hand[3].getRank() == hand[4].getRank()) return FULL_HOUSE;
if (flush) return FLUSH;
if (straight) return STRAIGHT;
if (hand[0].getRank() == hand[2].getRank()) return THREE_OF_A_KIND;
if (hand[2].getRank() == hand[3].getRank()) return TWO_PAIR;
if (hand[0].getRank() == hand[1].getRank()) return PAIR;
return HIGH_CARD;
Comparing Hands
Having sorted hands and identified their categories, it's easy to determine whether one hand beats another. If hand x's category is greater than y's, then x is the better hand. If they have the same category, then we compare the sorted hands, card by card. If x's card ever outranks y's, then x is the better hand. If all corresponding cards have the same ranks, then the hands are equal, presumably resulting in a split pot.
if (category1 > category2) return 1; //hand 1 is stronger
if (category2 > category1) return 2; //hand 2 is stronger
for (int i = 0; i < 5; i++)
{
int rank1 = hand1[i].getRank();
int rank2 = hand2[i].getRank();
if (rank1 > rank2) return 1; //hand 1 is stronger
if (rank2 > rank1) return 2; //hand 2 is stronger
}
return 0; //hands are equally strong
Sunday, March 24, 2019
Dave Computes a Courtroom Drama
So Help Me Gödel
a play in one act
CAST OF CHARACTERS
DEFENSE ATTORNEY
REGISTRAR
DEFENDANT
JUDGE
PROSECUTOR
[A typical courtroom. A trial is in progress.]
DEFENSE ATTORNEY: Your honor, the defense now calls the defendant to the stand.
[The defendant rises and approaches the stand. He sits down and places his right hand on an important-looking book presented to him by the court registrar.]
REGISTRAR: Do you solemnly swear that you will tell the truth, the whole truth, and nothing but the truth?
DEFENDANT: I do.
DEFENSE ATTORNEY: Your honor, if it pleases the court, the defendant wishes to read a prepared statement.
JUDGE: Proceed.
[The defense attorney hands the defendant a sheet of paper. The defendant unfolds it.]
DEFENDANT: [reading] The square of the hypotenuse of a right triangle is equal to the sum of the squares of the other two sides.
DEFENSE ATTORNEY: The jury will note that the statement read by my client is true beyond a reasonable doubt. Your honor, the defendant will now read a second prepared statement.
JUDGE: Another statement?
DEFENSE ATTORNEY: Yes, your honor.
JUDGE: Very well. I'll allow it.
[The defense attorney hands the defendant a second sheet of paper.]
JUDGE: All right. I'll allow one more statement, but you're on thin ice counselor. The state's objection is overruled.
DEFENSE ATTORNEY: Thank you.
[The defense attorney hands the defendant a third sheet of paper.]
a play in one act
CAST OF CHARACTERS
DEFENSE ATTORNEY
REGISTRAR
DEFENDANT
JUDGE
PROSECUTOR
[A typical courtroom. A trial is in progress.]
DEFENSE ATTORNEY: Your honor, the defense now calls the defendant to the stand.
[The defendant rises and approaches the stand. He sits down and places his right hand on an important-looking book presented to him by the court registrar.]
REGISTRAR: Do you solemnly swear that you will tell the truth, the whole truth, and nothing but the truth?
DEFENDANT: I do.
DEFENSE ATTORNEY: Your honor, if it pleases the court, the defendant wishes to read a prepared statement.
JUDGE: Proceed.
[The defense attorney hands the defendant a sheet of paper. The defendant unfolds it.]
DEFENDANT: [reading] The square of the hypotenuse of a right triangle is equal to the sum of the squares of the other two sides.
DEFENSE ATTORNEY: The jury will note that the statement read by my client is true beyond a reasonable doubt. Your honor, the defendant will now read a second prepared statement.
JUDGE: Another statement?
DEFENSE ATTORNEY: Yes, your honor.
JUDGE: Very well. I'll allow it.
[The defense attorney hands the defendant a second sheet of paper.]
DEFENDANT: [reading] The square root of two cannot be expressed as the quotient of two integers.
DEFENSE ATTORNEY: True again. Thank you. Your honor, the defendant now wishes to read a third prepared statement.
PROSECUTOR: Objection! What is the relevance of all these statements to the case at hand?
DEFENSE ATTORNEY: Your honor, these statements are necessary to establish the credibility of the defendant.
JUDGE: All right. I'll allow one more statement, but you're on thin ice counselor. The state's objection is overruled.
DEFENSE ATTORNEY: Thank you.
[The defense attorney hands the defendant a third sheet of paper.]
DEFENDANT: [reading] There are infinitely many natural numbers greater than one that cannot be formed by multiplying two smaller natural numbers.
DEFENSE ATTORNEY: So true. So true. Your honor, the defendant will now read a fourth prepared statement.
PROSECUTOR: Objection!
JUDGE: Sustained. Counselor, what is the meaning of all these statements?
DEFENSE ATTORNEY: Your honor, as I said, these statements establish my client's credibility. He swore to tell the truth, and that is exactly what he has done. The court can verify that each of his statements is true. All further statements my client might read would be true as well. Having fulfilled his oath to the court, we may proceed with the case at hand.
PROSECUTOR: Objection! The defendant has indeed told the truth, but he has clearly not told the whole truth.
JUDGE: That's true.
DEFENSE ATTORNEY: But the defendant would clearly tell the whole truth if given sufficient time.
JUDGE: But you require an infinite amount of time.
DEFENSE ATTORNEY: Yes, of course.
PROSECUTOR: Given the court's finite time, the state is willing to interpret the defendant's oath as only pertaining to finite statements, such as those that might fit on a single page.
DEFENSE ATTORNEY: Thank you. Then the state will agree that, of all such finite statements, the defendant, given time, would read all those statements that are truthful. Thus, we can all agree that, with sufficient time, my client would meet the terms of his oath by stating the truth. The whole truth.
PROSECUTOR: But what of nothing but the truth? Surely, in the course of reading all such true finite statements, the defendant is bound to recite a false one.
DEFENSE ATTORNEY: How dare you! My client would do no such thing. He is an honorable man.
JUDGE: Enough of this. Counselor, please proceed with your case.
DEFENSE ATTORNEY: Very well, your honor. The defense has no further questions.
JUDGE: The prosecution may now cross-examine the defendant.
[The prosecutor takes out a sheet of paper and writes on it with a black marker.]
PROSECUTOR: Your honor, I have written a statement onto this piece of paper. The state wishes to enter this statement into evidence as Exhibit G.
JUDGE: What is the meaning of this statement?
PROSECUTOR: The state simply wishes to know whether the defendant would read this simple statement, in keeping with his oath to tell the truth, the whole truth, and nothing but the truth.
DEFENSE ATTORNEY: Your honor, I must insist on knowing exactly what the statement says. If it is true, then of course the defendant will read this statement.
PROSECUTOR: The defendant will not read this statement.
DEFENSE ATTORNEY: Oh yes he will! Unless, of course, the statement labeled Exhibit G is false. Now I demand that you tell us the statement.
PROSECUTOR: The defendant will not read this statement.
JUDGE: The court orders the prosecution to reveal the content of Exhibit G.
PROSECUTOR: The defendant will not read this statement.
[The registrar grabs Exhibit G and hands it to the judge, who puts on his glasses and clears his throat.]
JUDGE: [reading from Exhibit G] The defendant will not read this statement. [The judge looks up at the defense attorney.] That is what it says. It says, "The defendant will not read this statement."
PROSECUTOR: Well?
DEFENSE ATTORNEY: Well, what?
PROSECUTOR: Will your client read Exhibit G?
DEFENSE ATTORNEY: Certainly not! Exhibit G is a bunch of nonsense, and my client will have no part in it.
JUDGE: Very well. Let the jury note that the defendant will not read this statement.
PROSECUTOR: Exactly as Exhibit G foretold! That statement told us that the defendant would not read it, and that is indeed what has come to pass.
JUDGE: That does appear to be true.
PROSECUTOR: The jury will note that the statement labeled Exhibit G has turned out, in fact, to be a true statement. The jury will also note that the defendant refused to read this true statement. Your honor, the state has shown that the defendant has not been forthright with this courtroom. By his unwillingness to read a true statement, he has violated his oath to tell the whole truth. His testimony is thus incomplete. The state therefore requests that he be held in contempt of court.
DEFENSE ATTORNEY: Objection! The prosecution is making a mockery of this courtroom.
JUDGE: Overruled. The prosecution has made a valid point.
DEFENSE ATTORNEY: Very well. Your honor, the defense wishes to change its position with respect to Exhibit G.
JUDGE: What do you propose?
DEFENSE ATTORNEY: My client will agree to read the irksome Exhibit G, provided that the prosecution will, at last, get on with the substance of its case against him. There will be no reason to hold my client in contempt.
JUDGE: The court agrees to the defense's proposal. The registrar will now provide the defendant with Exhibit G, to be read aloud to the jury.
PROSECUTOR: Objection!
JUDGE: Oh, what is it now?
PROSECUTOR: The state cannot allow the defendant to knowingly perjure himself on the stand.
JUDGE: Excuse me?
PROSECUTOR: By reading Exhibit G, the defendant will declare to the court that "the defendant will not read this statement." The defendant's action would be inconsistent with the content of Exhibit G. By reading the statement, the defendant would, in fact, make that very statement false. As you know, if he reads a false statement to the court, he will be in violation of his oath to tell nothing but the truth, and the state would have no choice but to accuse him of perjury.
DEFENSE ATTORNEY: Well, then I will certainly not allow my client to utter this false statement.
PROSECUTOR: But then, by not saying it, your client makes the statement a true one. By refusing to say a true statement, his testimony is incomplete.
DEFENSE ATTORNEY: But you have just insisted that he should not recite Exhibit G.
PROSECUTOR: Indeed, he should not. By saying it, your client would make the statement a false one. By uttering a false statement, his testimony would be inconsistent.
JUDGE: Then it appears there are two equally unpalatable options. In the one case, the defendant's testimony will be incomplete, in that it cannot be the whole truth, since it does not include the true statement labeled Exhibit G. In the other case, the defendant's testimony will be inconsistent, in that it is not nothing but the truth, since it requires him to utter the false statement labeled Exhibit G. We find ourselves in quite a pickle then. Is there no way then to avoid a descent into lawlessness?
DEFENSE ATTORNEY: I say we ban any statements that refer to themselves. A statement that refers to "this statement" is clearly troublesome, like the one in Exhibit G, or the paradoxical "This statement is false."
JUDGE: That is a fair compromise. It seems to me that Exhibit G is problematic because it refers to itself.
PROSECUTOR: Your honor, you just told us that "Exhibit G is problematic because it refers to itself." That itself is a statement about a statement, and thus I am currently making statements about statements about statements. Is the court to allow such statements that refer to statements?
JUDGE: Of course it will. I don't see how we could proceed without being able to make statements about statements.
PROSECUTOR: In that case, the state wishes to enter a new statement into evidence.
JUDGE: You will please share the proposed statement with the court.
PROSECUTOR: Certainly. The statement will read: "The defendant will not read Exhibit H."
JUDGE: I see no problem with your statement.
PROSECUTOR: Very well then. The state enters this new statement into evidence, to be labeled Exhibit H, which states that "the defendant will not read Exhibit H."
DEFENSE ATTORNEY: Objection! Your honor, do you see what the prosecution has done? He has found a loophole, allowing him to make a statement about itself.
PROSECUTOR: I have done no such thing. I am merely making a statement about a statement.
DEFENSE ATTORNEY: But your statement is about Exhibit H.
PROSECUTOR: It is.
DEFENSE ATTORNEY: And Exhibit H would be that very statement.
PROSECUTOR: It would be.
DEFENSE ATTORNEY: Therefore Exhibit H would, in fact, refer to itself, leading us back to the same conundrum.
JUDGE: The defense makes a good point, and yet the court cannot prevent such a statement.
DEFENSE ATTORNEY: In that case, I propose a different solution. Suppose we allow such a statement, but we concede that it is not a precise mathematical statement like those given by my client earlier. As such, we cannot determine the prosecution's statements to be true or false in the same sense.
PROSECUTOR: A worthy idea. Alas, my statement can indeed be written in rigorous mathematical language, as Kurt Gödel did when he introduced these ideas in 1931. All testimony must therefore necessarily be incomplete or inconsistent.
JUDGE: Very well. In that case, the court releases the defendant from his previous and unattainable oath. In its place, the defendant must now swear a new oath to this courtroom.
[The registrar holds out an important-looking book, and the defendant places his right hand on it.]
JUDGE: Do you solemnly swear that you will tell the truth, much of it, and not too much else?
[The defendant looks at his lawyer, then back at the judge, then back to the lawyer. He is sweating and visibly upset. At last, he speaks.]
DEFENDANT: OK! I did it! I killed him! And I'd do it again!
[The jury gasps, and the lights in the courtroom slowly fade to black.]
Author's Note
This story is based on the work of Kurt Gödel. In 1931, he constructed an arithmetic statement that signified "There is no proof of this statement." If arithmetic could be used to prove such a statement, then it must be inconsistent. If it couldn't, then it must be incomplete. In other words, Gödel put arithmetic on trial, and showed that it couldn't be used to prove all true arithmetic statements and nothing but true arithmetic statements.
DEFENSE ATTORNEY: So true. So true. Your honor, the defendant will now read a fourth prepared statement.
PROSECUTOR: Objection!
JUDGE: Sustained. Counselor, what is the meaning of all these statements?
DEFENSE ATTORNEY: Your honor, as I said, these statements establish my client's credibility. He swore to tell the truth, and that is exactly what he has done. The court can verify that each of his statements is true. All further statements my client might read would be true as well. Having fulfilled his oath to the court, we may proceed with the case at hand.
PROSECUTOR: Objection! The defendant has indeed told the truth, but he has clearly not told the whole truth.
JUDGE: That's true.
DEFENSE ATTORNEY: But the defendant would clearly tell the whole truth if given sufficient time.
JUDGE: But you require an infinite amount of time.
DEFENSE ATTORNEY: Yes, of course.
PROSECUTOR: Given the court's finite time, the state is willing to interpret the defendant's oath as only pertaining to finite statements, such as those that might fit on a single page.
DEFENSE ATTORNEY: Thank you. Then the state will agree that, of all such finite statements, the defendant, given time, would read all those statements that are truthful. Thus, we can all agree that, with sufficient time, my client would meet the terms of his oath by stating the truth. The whole truth.
PROSECUTOR: But what of nothing but the truth? Surely, in the course of reading all such true finite statements, the defendant is bound to recite a false one.
DEFENSE ATTORNEY: How dare you! My client would do no such thing. He is an honorable man.
JUDGE: Enough of this. Counselor, please proceed with your case.
DEFENSE ATTORNEY: Very well, your honor. The defense has no further questions.
JUDGE: The prosecution may now cross-examine the defendant.
[The prosecutor takes out a sheet of paper and writes on it with a black marker.]
PROSECUTOR: Your honor, I have written a statement onto this piece of paper. The state wishes to enter this statement into evidence as Exhibit G.
JUDGE: What is the meaning of this statement?
PROSECUTOR: The state simply wishes to know whether the defendant would read this simple statement, in keeping with his oath to tell the truth, the whole truth, and nothing but the truth.
DEFENSE ATTORNEY: Your honor, I must insist on knowing exactly what the statement says. If it is true, then of course the defendant will read this statement.
PROSECUTOR: The defendant will not read this statement.
DEFENSE ATTORNEY: Oh yes he will! Unless, of course, the statement labeled Exhibit G is false. Now I demand that you tell us the statement.
PROSECUTOR: The defendant will not read this statement.
JUDGE: The court orders the prosecution to reveal the content of Exhibit G.
PROSECUTOR: The defendant will not read this statement.
[The registrar grabs Exhibit G and hands it to the judge, who puts on his glasses and clears his throat.]
JUDGE: [reading from Exhibit G] The defendant will not read this statement. [The judge looks up at the defense attorney.] That is what it says. It says, "The defendant will not read this statement."
PROSECUTOR: Well?
DEFENSE ATTORNEY: Well, what?
PROSECUTOR: Will your client read Exhibit G?
DEFENSE ATTORNEY: Certainly not! Exhibit G is a bunch of nonsense, and my client will have no part in it.
JUDGE: Very well. Let the jury note that the defendant will not read this statement.
PROSECUTOR: Exactly as Exhibit G foretold! That statement told us that the defendant would not read it, and that is indeed what has come to pass.
JUDGE: That does appear to be true.
PROSECUTOR: The jury will note that the statement labeled Exhibit G has turned out, in fact, to be a true statement. The jury will also note that the defendant refused to read this true statement. Your honor, the state has shown that the defendant has not been forthright with this courtroom. By his unwillingness to read a true statement, he has violated his oath to tell the whole truth. His testimony is thus incomplete. The state therefore requests that he be held in contempt of court.
DEFENSE ATTORNEY: Objection! The prosecution is making a mockery of this courtroom.
JUDGE: Overruled. The prosecution has made a valid point.
DEFENSE ATTORNEY: Very well. Your honor, the defense wishes to change its position with respect to Exhibit G.
JUDGE: What do you propose?
DEFENSE ATTORNEY: My client will agree to read the irksome Exhibit G, provided that the prosecution will, at last, get on with the substance of its case against him. There will be no reason to hold my client in contempt.
JUDGE: The court agrees to the defense's proposal. The registrar will now provide the defendant with Exhibit G, to be read aloud to the jury.
PROSECUTOR: Objection!
JUDGE: Oh, what is it now?
PROSECUTOR: The state cannot allow the defendant to knowingly perjure himself on the stand.
JUDGE: Excuse me?
PROSECUTOR: By reading Exhibit G, the defendant will declare to the court that "the defendant will not read this statement." The defendant's action would be inconsistent with the content of Exhibit G. By reading the statement, the defendant would, in fact, make that very statement false. As you know, if he reads a false statement to the court, he will be in violation of his oath to tell nothing but the truth, and the state would have no choice but to accuse him of perjury.
DEFENSE ATTORNEY: Well, then I will certainly not allow my client to utter this false statement.
PROSECUTOR: But then, by not saying it, your client makes the statement a true one. By refusing to say a true statement, his testimony is incomplete.
DEFENSE ATTORNEY: But you have just insisted that he should not recite Exhibit G.
PROSECUTOR: Indeed, he should not. By saying it, your client would make the statement a false one. By uttering a false statement, his testimony would be inconsistent.
JUDGE: Then it appears there are two equally unpalatable options. In the one case, the defendant's testimony will be incomplete, in that it cannot be the whole truth, since it does not include the true statement labeled Exhibit G. In the other case, the defendant's testimony will be inconsistent, in that it is not nothing but the truth, since it requires him to utter the false statement labeled Exhibit G. We find ourselves in quite a pickle then. Is there no way then to avoid a descent into lawlessness?
DEFENSE ATTORNEY: I say we ban any statements that refer to themselves. A statement that refers to "this statement" is clearly troublesome, like the one in Exhibit G, or the paradoxical "This statement is false."
JUDGE: That is a fair compromise. It seems to me that Exhibit G is problematic because it refers to itself.
PROSECUTOR: Your honor, you just told us that "Exhibit G is problematic because it refers to itself." That itself is a statement about a statement, and thus I am currently making statements about statements about statements. Is the court to allow such statements that refer to statements?
JUDGE: Of course it will. I don't see how we could proceed without being able to make statements about statements.
PROSECUTOR: In that case, the state wishes to enter a new statement into evidence.
JUDGE: You will please share the proposed statement with the court.
PROSECUTOR: Certainly. The statement will read: "The defendant will not read Exhibit H."
JUDGE: I see no problem with your statement.
PROSECUTOR: Very well then. The state enters this new statement into evidence, to be labeled Exhibit H, which states that "the defendant will not read Exhibit H."
DEFENSE ATTORNEY: Objection! Your honor, do you see what the prosecution has done? He has found a loophole, allowing him to make a statement about itself.
PROSECUTOR: I have done no such thing. I am merely making a statement about a statement.
DEFENSE ATTORNEY: But your statement is about Exhibit H.
PROSECUTOR: It is.
DEFENSE ATTORNEY: And Exhibit H would be that very statement.
PROSECUTOR: It would be.
DEFENSE ATTORNEY: Therefore Exhibit H would, in fact, refer to itself, leading us back to the same conundrum.
JUDGE: The defense makes a good point, and yet the court cannot prevent such a statement.
DEFENSE ATTORNEY: In that case, I propose a different solution. Suppose we allow such a statement, but we concede that it is not a precise mathematical statement like those given by my client earlier. As such, we cannot determine the prosecution's statements to be true or false in the same sense.
PROSECUTOR: A worthy idea. Alas, my statement can indeed be written in rigorous mathematical language, as Kurt Gödel did when he introduced these ideas in 1931. All testimony must therefore necessarily be incomplete or inconsistent.
JUDGE: Very well. In that case, the court releases the defendant from his previous and unattainable oath. In its place, the defendant must now swear a new oath to this courtroom.
[The registrar holds out an important-looking book, and the defendant places his right hand on it.]
JUDGE: Do you solemnly swear that you will tell the truth, much of it, and not too much else?
[The defendant looks at his lawyer, then back at the judge, then back to the lawyer. He is sweating and visibly upset. At last, he speaks.]
DEFENDANT: OK! I did it! I killed him! And I'd do it again!
[The jury gasps, and the lights in the courtroom slowly fade to black.]
Author's Note
This story is based on the work of Kurt Gödel. In 1931, he constructed an arithmetic statement that signified "There is no proof of this statement." If arithmetic could be used to prove such a statement, then it must be inconsistent. If it couldn't, then it must be incomplete. In other words, Gödel put arithmetic on trial, and showed that it couldn't be used to prove all true arithmetic statements and nothing but true arithmetic statements.
Subscribe to:
Posts (Atom)