Sunday, September 1, 2019

Dave Computes Chair Fractals

The Chair Fractal leads to some surprisingly interesting doodles. The rule for this fractal is simple. Start with an L and subdivide it into 4 smaller L shapes as follows.


Subdivide each L again.


After a while, you'll see something like this.


The result is a simple aperiodic tiling. Before we make it more interesting, it's helpful to learn to draw the fractal without subdividing. Start by drawing several nested L shapes. The number of shapes should be one less than a power of 2 (e.g. 1, 3, 7, 15, 31, 63).


Draw nested L's from each corner to the center.


Continue as follows.


Eventually, a square region is filled in, with only the corner missing.


Things get more interesting when we replace each L shape by the figures shown in the top right of each image below. I have also filled in the shapes in some of these patterns.









Wednesday, July 24, 2019

Dave Computes Ladder Doodles

Here's a kind of doodle I've been drawing for a while now. It started from the idea of tiling a grid with a single square tile.


Here's a small tiling. The tile can be rotated, and adjacent edges must be the same color.


After a while, I stopped thinking of it as a tiling. For lack of a better name, I'll call these ladder doodles. I begin with horizontal line segments across the top of a page of gridded paper. Some lines are drawn on the top row and some on the second row, chosen at random. Then I copy those lines down the page, on every other row.



Then I repeat with random vertical line segments copied across the page.


The entire drawing is uniquely determined by the choices on the top row and left column. Thus, a drawing on an n × n grid contains exactly 2n bits of information. I like drawing diagonal lines to show the paths more clearly.


The paths can get quite intricate in larger drawings.


Here I've filled in the drawing with random colors.


And here are a couple more.





Thursday, June 27, 2019

Dave Computes Too Much: Managing Repetitive Strain Injuries

I've endured years of wrist pain from working at my computer. Switching hands just made the other wrist hurt. I bought ergonomic mice and keyboards, but nothing seemed to stop the dull ache in my wrists. I got a lot of bad advice from doctors and physical therapists before I found routines that worked for me. Here's what I learned.


What Doesn't Work

Painkillers - Don't take painkillers just to continue working. The pain is telling you to change the way you use your body. Drowning out that signal with painkillers might help for a few hours, but it can't be a permanent solution. Painkillers might be helpful if pain is keeping you from sleeping, but even then, consider using a cream like Icy Hot or Bengay.

Splints - Don't use splints just to continue working. Putting my wrists in splints felt better at first. I didn't notice the pain as often when my wrists were immobilized. But it came back if I tried to work with splints on.

Steroid Injections or Surgery - Your doctor may recommend steroid injections or carpal tunnel surgery. That may be good advice for you, but do some research before taking this drastic step. There are lots of people who had steroid injections or surgery, only to have the same pain return a few years or months later.

In short, if you're still using your body in the same way, none of these "treatments" will eliminate your pain.


What's Causing the Pain

There is a bundle of blood vessels and nerves that connects the spinal column to each of your hands. The bundle emerges from the lower neck and passes under the collarbone to the armpit. (To learn more, search brachial plexus and thoracic outlet syndrome.) If, like me, you compute with your body hunched forward to reach the keyboard or to see the screen better, then those nerves and blood vessels will be compressed while you work. Depending on your posture, you may experience numbness in your hand due to a compressed nerve. Or compressed blood vessels may prevent your arm muscles from working properly. Tightened muscle fibers in your arms can exert a constant pull on your wrist, causing a dull pain.

In short, what you feel in your wrists is caused by how you're positioning your neck and shoulders when you work.

It's not easy to change the way you use your body. Years of hunching forward tightens the muscles and fascia in the front of your neck and chest, and it stretches and weakens the muscles in your upper back. To get better, you're going to need to work on all these areas. Harder still, you must become aware of how you're positioning and using your body. You'll need to recognize which muscles you're using, so that you can take breaks as soon as you notice yourself falling back into old habits.


What Works For Me

Massage - This is not the relaxing kind of massage. Instead, I'm talking about targeting specific muscles. There are no muscles in your wrists, so massaging your wrists won't help. Your fingers are pulled on by long tendons that pass through your wrist and connect to the muscles in your forearm that control them. To loosen these muscles, massage your forearm just below your elbow. Use slow movements with strong pressure. This is easiest to do by pressing and sliding your arm firmly and slowly over a ball, letting the ball roll along a wall or tabletop. Lacrosse balls work best, but tennis balls are fine, too. Massaging your forearm often brings relief, but only temporarily. That's because other tight muscles higher up are pulling on the muscles in your forearm. For sustained relief, you'll need to work on muscles in your neck, chest, and upper back. I've spent a lot of time working on my scalene muscles. There are three of these on each side of the neck. They can be massaged by holding one hand pressed into the side of the neck and moving it slowly with appropriate pressure from the other hand. I've also found it helps to work on the muscles under my shoulder blades, by bringing my arm across my chest and pressing my back into a ball on a wall. I even think it's been helpful to work on muscles in my lower back (with ball against the wall), as these seem to help improve my posture and prevent me from leaning forward at the shoulder and neck. I have a theory that massage can help your body find the places that need repair, but you need to get enough restorative sleep for it to heal. I've found massage most helpful for relieving pain in the short term, but other measures are required to prevent it from coming back.

Traction - It's not just muscles that can become too tight. It's also fascia--the stuff that covers your muscles like plastic wrap. To work on tightened muscles and fascia, I tried many stretches without success before discovering traction. With traction, you let friction pull just slightly on some part of your body over several minutes. I lie down with a foam roller under the length of my spine. I place my head so that my neck is stretched just a little taller than usual, and I spread my arms out wider than usual with my hands resting on the floor. After 10 minutes, I get up and feel much better. It works even better when combined with meditation, which I'll get to shortly.

Strengthening - You've probably relied too much on some muscles and ignored others. You'll need to strengthen the right muscles in order to put them to work again. If you've been working in a compressed position, you've probably stretched and ignored your upper back muscles. Regular exercise of this area can go a long way. I've found that I benefit from exercises that squeeze my shoulder blades together. I've also recently discovered that strengthening my core by doing lower back exercises seems to improve my posture (and body awareness) in a way that's perhaps been the most effective way to prevent the pain from returning.

Meditation - This has been the most important piece for me, with pain reduction being just one of many benefits. I practice mindfulness meditation, where you bring your attention to your breath, returning to it whenever you notice your mind wandering. It's best to set aside at least 10 minutes a day for this. Stress can drive you to work in awkward positions without breaks, and meditation can reduce that stress. My favorite kind of meditation is called a body scan, in which you bring your attention to one body part at a time, focusing especially on those areas where you experience tightness or pain. Observe these sensations with curiosity, accepting them without judgment. Sometimes, just by bringing your attention to a part of your body, you'll sense the muscles there relaxing, but you shouldn't strive to make this happen. To start, you might try listening to body scan recordings on YouTube. Over time, you'll become more aware of how you're using your body when you're at your computer. You'll discover which positions cause unnecessary strain. You'll learn to sit or stand with better posture in ways that don't strain those tight muscles. Personally, I've noticed through meditation that I tend to breathe too much from my abdomen. I find a lot of relief if I imagine the air in my chest sliding upward and into my shoulders (which seems to encourage my scalene muscles to lift my collarbone). I have also discovered that the seat of my consciousness seems to live in my jaw or neck region. If I pay more attention to sensations around my eyes, sometimes my neck loosens up and I breathe easier.

Best of luck!

Friday, April 26, 2019

Dave Computes U.S. Coin Frequencies

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.

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.
<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)
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)
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.

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.

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.

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

Ace of Hearts Jack of Diamonds Jack of Clubs Seven of Clubs Queen of Hearts 

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:

Jack of Diamonds Jack of Clubs Ace of Hearts Queen of Hearts Seven of Clubs 


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




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.]

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.

Friday, January 4, 2019

Dave Computes Multiplication With Rulers

In this post, we're going to see how to multiply with rulers. Along the way, we'll learn how slide rules work and how to make your own, along with a bit about logarithms.


Part 1:  Adding With Rulers

To start, let's see how to add with 10-inch rulers.


We'll use two such rulers, one on top of the other. Place them so the left edge of the top ruler lines up with the 2 on the bottom ruler:


Notice that the values on the bottom ruler are now 2 more than the values in the corresponding positions of the top ruler. We can therefore now compute 2 + 3 by finding the 3 on the top ruler and then finding the sum (5) just below it on the bottom ruler. In general, to find x + y, place the left edge of the top ruler at x on the bottom ruler, find y on the top ruler, and the sum x + y will be just below it on the bottom ruler.

We can subtract, too. Let's say we want to find 7 - 4. We think of this as "4 plus what gives us 7" Line the rulers up so that the left edge of the top ruler is at the 4 on the bottom ruler. Find the sum (7) on the bottom ruler, and the answer (3) appears above it.


Let's try a trickier problem. If we attempt to find 7 + 5 in this manner, something goes wrong. The sum should be below the 5 on the top ruler, but we've run out of ruler!


We could solve this problem by introducing a third ruler, but we don't have to. Instead, we'll line up the right edge of the top ruler with the 7 on the bottom ruler. We look for the number below the 5, and find 2 there. This represents the ones digit of the sum. Essentially, by placing the right side of the top ruler at 7, we've computed 7 - 10 + 5 = 2. We just need to add 10 to our final answer to see that 7 + 5 = 12.


One more thing to note. When we line up the left edges of the rulers, the top and bottom numbers match. We can think of this as adding 0. Thus, the left edge of the ruler must be 0--the identity element for addition.



Part 2:  Multiplying with Rulers

Surprisingly, it turns out we can also multiply with rulers, but we'll need to mark them differently. Beginning from an unmarked ruler, we first need to make a single arbitrary decision. What number should we put on the right edge? When adding, the right side represented 10, and that made adding a bit easier in our base-10 system (see 7 + 5). So let's also put 10 on the right edge of our multiplication rulers.


For addition, the choice to put 10 on the right side of the ruler fixes the locations of any other numbers we wished to mark. The same is true for multiplication. Let's line up two multiplication rulers.


This picture represents a multiplication problem:  something times 10 equals 10. Clearly, that something must be 1, the identity element for multiplication. So, for multiplication rulers, the left edge represents the value 1 (not zero).

But how can we locate numbers between 1 and 10? Let's figure out where the number 2 belongs.

If we line up 3 rulers end to end, the values on the rulers will span from 1 to 1,000.


By a lucky coincidence, 210 = 2 × 2 × 2 × 2 × 2 × 2 × 2 × 2 × 2 × 2 = 1,024 is very close to 1,000. That means that we can multiply by 2 ten times in roughly the span of three rulers.


Divide 3 rulers by 10 to find that we can multiply by 2 once in roughly 0.3 rulers (0.301 would be more exact). On a 10-inch ruler, we would therefore write the number 2 at the 3" mark.


We can now go about finding other numbers on our ruler. Using two rulers, we can compute 2 × 2 and write the result (4) at the corresponding position (near the 6" mark of a 10" ruler).


Now we compute 2 × 4 and write that result (8) there (near the 9" mark).


Notice that we've basically turned multiplication into addition. Adding the lengths of rulers is telling us the results of multiplication problems. We can also perform division with our rulers. Consider the question "2 times what equals 10?" This lets us find where to write the number 5 (near the 7" mark).


Using nothing but multiplication and division by 2, we could go on to find decimal values. For example, we could ask "2 times what equals 5" to find 2.5 (near the 4" mark).


Alternatively, we could compute 2 × 8 to find 16.


Unfortunately, we've run out of ruler, so instead we'll position the right edge of the top ruler on the 2 from the bottom ruler. This has the effect of dividing our result by 10, so instead of 16, we get 1.6 (near the 2" mark).


(Because we made an approximation when we wrote 2 at the 3" mark, the more we multiply or divide by 2, the more error we introduce.)

Based only on the fact that 210 ≈ 103, we are able to perform calculations involving multiples of 2 and 5. To write any more numbers on our ruler, we'll need to find other such coincidences. The insight we'll use next is that 8 × 10 ≈ 9 × 9.

If we line up our rulers to find 8 × 10, we find that the number 80 belongs at the 19" mark. Since 9 × 9 should also reach near the 19" mark, we should write 9 at the halfway point, near the 9½" mark.

(A better approximation would be to write the 9 at 9.54", which is closer to the 9 9/16" mark on a ruler.)

We got from 81 to its square root, 9, by cutting that length in half. We can cut that length in half again to find that 3 (the square root of 9) belongs near the 4¾" mark.

Multiply 2 × 3 to find 6. The correct value of 6 is around 0.778, nearest to the 7 13/16" mark.


To locate 7, we can use the fact that 5 × 10 ≈ 7 × 7.

We've now succeeded in making a simple slide rule, and along the way, we've learned how to use one to multiply or divide simple numbers. If we place 0.1, 0.2, ..., 0.99 on our slide rule (perhaps just as tick marks between integer values), then we could perform calculations with 2 significant digits.


Part 3:  Logarithms

Instead of using inches, let's label all positions on the ruler from 0.000 at the left edge to 1.000 at the right edge. In that case, we would write 3 near position 0.477 (what we previously referred to as the 4.77" mark of a 10" ruler). There is a simple relationship between these two numbers: 100.477 ≈ 3. In the language of logarithms, the notation "log 3" means "10 to what power is 3?" Therefore, we write log 3 ≈ 0.477. Here's a table of logarithms for the numbers we investigated earlier. (Technically, these are approximations of base-10 logarithms.)

 x     log x
 1     0.000
 2     0.301
 3     0.477
 4     0.602
 5     0.699
 6     0.778
 7     0.845
 8     0.903
 9     0.954
10     1.000

When we used our slide rule to compute 2 × 3 = 6, we were taking advantage of the fact that log 2 + log 3 = log 6. But why does that work?

First, some basics of logarithms. We know that 103 = 1000, and therefore log 1000 = 3.

In 103 = 1000, replace the 3 with the equivalent log 1000 to get:  10log 1000 = 1000.

Or, more generally: 10log A = A

Using that and the fact that 10B = 10A × 10B, we can work out log 2 + log 3 as follows:

10log 2 + log 3
= 10log 2 × 10log 3
= 2 × 3
= 6

Since 10log 2 + log 3 = 6, then the definition of logarithms gives us log 2 + log 3 = log 6.

In general, log(A) + log(B) = log(A × B).

This fact lets us use our knowledge of just a few logarithms to compute many others. For example, since 98 = 2 × 7 × 7, we can find log 98 by calculating log 2 + log 7 + log 7 ≈ 0.301 + 0.845 + 0.845 = 1.991. Thus, we can factor any integer N into its primes and compute log N by adding up the logarithms of those prime factors.