Sunday, September 30, 2012

Dave Computes Solitaire Strategy

Having invested countless hours in playing Klondike Solitaire, I have decided to share my current wisdom on Solitaire strategy.  Note that I'm talking here about the version where 3 cards are dealt from the stock at once, which necessarily complicates the strategy.  I should also say that my goal in solitaire is to attain the highest winning percentage.  Many people will prefer winning the most games per unit time, or scoring the most points per win.  Any of these goals will lead to different strategies.  Anyway, here are the rules that guide my play.


Rule #1:  Prefer to expose face-down cards.

At the beginning of the game, there are 24 cards in the stock, 7 face-up cards on the table, and 21 face-down cards underneath them.  To win the game, I must eventually gain access to all cards.  Clearly, I already have access to the 7 face-up cards.  Of the 24 stock cards, one cycle through the deck immediately grants me access to 8 of them, and the remaining 16 are just a play or two away.  On the other hand, most of the 21 face-down cards are buried under 2 or more cards, and the deepest is buried under 6 cards.  So, not only should I make plays that reveal face-down cards, but I should strive to reveal cards from the piles with the most face-down cards.  At the start of the game, revealing just one face-down card from the rightmost pile gets me one play closer to revealing each of the 5 cards below it.

Therefore, I will generally make all the plays I can with the table cards (first moving the cards from piles with the most face-down cards) before dealing further from the stock.


Rule #2:  Never empty a pile unless there is a king immediately available.

This rule is fairly straightforward.  There is absolutely no advantage to emptying out a pile unless you have a king handy.  Any move that would have left a pile empty has the potential to block a future play that may arise before a king comes up.


Rule #3:  Usually play the last playable card in the stock.

Let's number the cards in the stock from 1 to 24.  As I cycle through the stock, I first see card #3, then #6, #9, #12, #15, #18, #21, and #24.  Suppose I can play card #6 and #12.  Which should I play first?  Most people would play card #6 before they even discover card #12.  I'm convinced that's not a winning strategy.  Here's why.  If I play #6 and then #12, then on the next deal I'll have access to 6 new cards (#7, #10, #14, #17, #20, and #23).  If I instead play only #12, the next deal will give me access to #13, #16, #19, and #22, and if I now play #6 (which is still available to me), the deal after that will expose #7, #10, #14, #17, #20, and #23--a total of 10 new cards!

Therefore, I will always cycle through the entire stock once before choosing which card to play--usually the last playable card.  Yes, it takes longer to play this way.  No, it doesn't bother me.

Exception To Rule #3:
The exception to this rule is when playing a later card in the stock will prevent me from being able to play an earlier card.  For example, if both the 4-of-diamonds and the 4-of-hearts are accessible to me, but I can only play one red 4, then I should play the earlier four so as to expose more new cards on the next deal.  Here's another example where this comes up.  I have a 4-of-hearts exposed, and a 3-of-spades sitting on the table.  I can move the 3 onto the 4, in order to play a king from the stock, or I can put a 3-of-clubs from the stock onto the 4.  I can't make both plays, so I should play whichever appears earlier in the stock.  This kind of situation arises quite frequently, and if misplayed, can easily turn a winning game into a losing one.  Also, bear in mind that the two playable (but mutually exclusive) cards may be separated and/or followed by other playable cards which should be played first.  And sometimes playing a stock card may reveal a new playable card that should be ignored if it would prevent me from playing a card I saw earlier in the stock.


Rule #4:  Never play more than 3 cards from the stock on a single deal.

On a particular deal, once I've played a third card from the stock, all remaining accessible cards will continue to be accessible on the next deal.  By ignoring these remaining cards until the next deal, I may discover newly accessible cards that should be played first.


Rule #5:  Don't move any card to the foundations if it could still prove useful on the table.

For example, I shouldn't move the 3-of-spades onto the spades foundation if there's still a chance that I'll need it to support a red 2.  Of course, if both red aces have already come up, or if the ace-of-hearts has come up and the 2-of-diamonds is already supported by the 3-of-clubs, then it's safe to move the 3-of-spades to the foundation.  But I shouldn't be in a rush to move cards to the foundations.  I am certain that people who always move cards onto foundations are not playing optimally.  And yes, this means I always disable any auto-move feature on my Solitaire software.


Saturday, September 15, 2012

Dave Computes Interest Payments

We're usually taught two ways to calculate interest payments--simple and compound.  The truth is there's only one way to calculate interest and several models for paying back a loan.

The Basics

Whenever I borrow anything, the lender and I must agree on how much rent I need to pay, and how often I need to pay it.  Borrowing money is no different.  The money I borrow at the beginning of a loan is called the principal, and the rent I pay for borrowing it is called interest.  Unlike rents on other items, the interest I pay when I borrow money is not a fixed amount.  Rather it's (usually) a fixed interest rate--a percentage that tells me how much of the amount borrowed I need to pay in rent.  For example, I might borrow $500 and agree to pay 2% of the borrowed amount every month.  Then, after the first month, I would owe 2% × $500 = $10 in interest.  (Recall that 2% = 0.02.)

Note:  The 2% interest rate in my example is what I call the periodic interest rate--the percent charged every period when interest is collected/assessed.  By convention, we usually speak in terms of annual interest rates--the percent due each year.  Therefore, the first step of any interest calculation is usually to convert an annual interest rate into the more useful periodic interest rate.  In my example, the annual interest is 24%, the period is 1 month, and therefore the periodic interest rate I need for my calculations is 24% ÷ 12 = 2%.

The One Law Of Interest Payments

Every period, the borrower is charged an amount of interest equal to the periodic interest rate (r) multiplied by the borrowed amount (b).
Initially, the borrowed amount b is simply the principal (the amount of money initially borrowed).  Surprisingly, this is the only law you ever need to calculate interest payments.

Let's return to the example where I borrow $500 and I'm charged 2% interest each month.  We already determined (using The One Law Of Interest Payments) that I owe 2% × $500 = $10 in interest for the first month.  But suppose I pay only $7.  Since I owed $10 but paid only $7, I've effectively borrowed another $3.  Now I've borrowed a total of $503, so The One Law Of Interest Payments tells me that next month I'll owe 2% × $503 = $10.06 in interest.  The extra 6 cents is really interest on the interest I didn't pay.  Now, $7 is an unusual payment, so let's look at some more common payment plans.

Payment Plan #1:  Simple Interest

In this plan, I pay the full amount of interest every period, and at the end of the loan I also pay back the principal in full.  Again, suppose I've borrowed $500, and I'm charged 2% interest each month, which works out to be $10.  In this plan, I pay exactly $10.  The next month, since I've still borrowed $500, I again owe $10.  By paying the full interest every month, the amount I've borrowed doesn't change, which keeps the math simple.  At the end of the loan, I pay back the $500.  If the loan lasts for 1 year, then I've paid 12 × $10 = $120 in interest.  In general, I'll pay a total of t × r × p in interest, where t is the number of periods in the loan, r is the periodic interest rate, and p is the principal.

Payment Plan #2:  Compound Interest

In this plan, I'm charged interest each period (as always) but I don't pay any of it.  At the end of the loan, I pay back the principal in full, along with all the accumulated interest.  So, this time when I'm charged $10 interest on my $500 loan, I pay $0.  That means I've effectively borrowed an additional $10, so I've now borrowed a total of $510.  Next month, The One Law Of Interest Payments tells me I'll owe 2% × $510 = $10.20 in interest.  Again, I pay $0, so I've now borrowed $510 + $10.20 = $520.20, and next month I'll be charged 2% × $520.20 = $10.404, and again I'll pay $0, and so on.  But how much will I have to pay back at the end of the loan?

Originally, I borrowed $500.
After 1 period, I've borrowed $500 + 0.02 × $500 = $500 × 1.02.
After 2 periods, I've borrowed ($500 × 1.02) × 1.02 = $500 × (1.02)2.
After 3 periods, I've borrowed $500 × (1.02)3.

Each period, the amount I owe multiplies by 1.02 (and is therefore growing exponentially).  At the end of 1 year, I'll owe $500 × (1.02)12 = $634.12, where $134.12 of that is interest ($14.12 more than I paid using the simple interest payment plan.)

In general, after t periods, I'll owe a total of p(1 + r)t.

With compound interest, my debt can accumulate quite quickly.  If I borrow that $500 for 10 years, then the simple interest payment plan would cost me $1,200 in interest, while the compound interest payment plan would cost me $4882.58 in interest.  That's why people talk of "the power of compound interest."

Payment Plan #3:  Overpaying

Suppose I need $100,000 to buy a house.  A loan to buy a house is called a mortgage, but it's essentially like any other loan.  My bank would be crazy to lend me that money using a simple or compound interest payment plan.  Let's see why.

Suppose the bank offers to loan me the money for 30 years at 6% interest, and interest is assessed every month.  That makes the periodic interest rate r = 6% ÷ 12 = 0.5% (or 0.005). 

I would owe 0.5% × $100,000 = $500 in interest for the first month.  If I pay exactly $500 each month, I end up with a simple interest plan, in which I still owe $100,000 at the end of the loan.  If I pay less than $500 each month, I'll owe even more at the end of the loan (the principal plus accumulated interest).  In the most extreme case, I pay $0 each month, resulting in a compound interest plan in which I owe over $600,000 at the end of the loan.  The bank is never going to trust me to be able to make a single large payment of $100,000 or $600,000 at the end of the loan. 

To reduce the amount I'll owe at the end of the loan, my monthly payment will need to be more than $500.  That way, every month I'll pay off all of the interest and some of the principal.

Suppose I pay $550 each month.  Again, The One Law Of Interest Payments guides us.  After one month, I owe $500 in interest, but I pay $550, which covers all of the interest and also pays off $50 of the loan (the principal).  That means I've effectively borrowed $50 less, so I've now borrowed "only" $99,950.  Since I've borrowed less, I'll now be charged less interest next month:  0.5% × $99,950 = $499.75.  Again, I pay $550, which now pays off all of the interest plus $50.25 of the principal.  The interest calculations for the first 3 months of this loan are summarized in the following table.


Month
Borrowed
Interest
Principal Paid Off
1
$100,000
0.5% × $100,000
= $500
$550 - $500
= $50
2
$100,000 - $50
= $99,950
0.5% × $99,950
= $499.75
$550 - $499.75
= $50.25
3
$99,950 - $50.25
= $99,899.75
0.5% × $99,899.75
= $499.49875
$550 - $499.49875
= $50.50125

Notice that each month, I've borrowed less, so I owe less interest, so I pay off more of the principal, so I've borrowed even less, and so on.  OK, so how much will I owe at the end of 30 years?  To answer that, we'll derive the general formula for interest payments.

The General Formula

So far, we've seen three payment plans, and in each one, my regular payment x is a constant.  These plans are summarized in the following table.


Payment Plan
Regular Payment
Simple Interest
xpr
Compound Interest
x = 0
Overpaying
x > pr

Clearly, the more I pay during the loan (larger x), the less I'll owe at the end of the loan.  In this section, we'll derive a general formula for how much I owe at the end of the loan, as a function of x (and pr, and t).

Initially, I borrow p.  After one period, The One Law Of Interest Payments tells me I'll owe a total of p(1 + r), which includes both the amount I borrowed (p) and one period of interest (pr).  I make a payment of x, which means now I've only borrowed p(1 + r) - x.  Notice that we multiplied the amount borrowed by (1 + r) and then subtracted x.  This same process will repeat every period, so after my next payment, I will multiply p(1 + r) - x itself by (1 + r) and then subtract x, resulting in the following pattern:

Originally, I borrowed p.
After 1 period, I've borrowed p(1 + r) - x.
After 2 periods, I've borrowed p(1 + r)2 - x(1 + r) - x.
After 3 periods, I've borrowed p(1 + r)3 - x(1 + r)2 - x(1 + r) - x.
After t periods, I've borrowed p(1 + r)t - x(1 + r)t-1 - x(1 + r)t-2 ... - x(1 + r) - x

Recognizing that (1 + r)t-1 + (1 + r)t-2 ... + (1 + r) + 1 is a geometric series whose sum is
[(1 + r)t- 1] ÷ r, our formula simplifies to

p(1 + r)t - x[(1 + r)t - 1] ÷ r

which tells me how much I owe after borrowing p at a periodic interest rate of r, and making payments of x for t periods.  This is The General Formula.

Using The General Formula


If this formula is really so general, we should be able to use it to calculate both simple and compound interest, and indeed we can.

In a compound interest payment plan, x = 0 (since I don't pay interest until the end of the loan).  Plugging x = 0 into the general formula, the ugly righthand term immediately disappears, and we are left with p(1 + r)t, which we recognize as the formula for compound interest.

In a simple interest payment plan, x = pr (since I pay off the interest each period).  When we plug x = pr into the general formula, most of the formula cancels out, and we're left with just p.  And this makes perfect sense, because no matter how long I borrow for, I've always paid off all interest, and I therefore only owe the principal p at the end of the loan.

In my mortgage example, p = $100,000, r = 0.005, t = 360 (the number of months in 30 years), and x = $550.  Plugging these values into the formula, I get

($100,000)(1.005)360 - ($550)[(1.005)360 - 1] ÷ 0.005 = $49,774.25

I still owe almost $50,000 at the end of the loan.  Apparently, I should have made higher monthly payments.  But how high?

Payment Plan #3 (Revised):  Overpaying (to pay off the principal exactly)

I want to determine the regular payment x that will completely pay off the full loan (principal and interest) in exactly 30 years.  In this plan, at the end of the loan, I will owe $0, meaning that the general formula had better give me $0.

p(1 + r)t - x[(1 + r)t - 1] ÷ r = 0


By solving this equation for x, we can determine the correct monthly payment:

x = pr(1 + r)t ÷ [(1 + r)t - 1]

This is the mortgage payment formula you'll find elsewhere (in some equivalent form).

In my mortgage example, p = $100,000, r = 0.005, and t = 360.  Plugging these values into the formula, I get

x = ($100,000)(0.005)(1.005)360 ÷ [(1.005)360 - 1] = $599.55

Therefore, if the bank offers me a 30-year loan of $100,000 with a fixed (annual) interest rate of 6%, my monthly mortgage payment will be $599.55.  After 360 payments of $599.55, I will have paid off the loan in full, having paid a total of $215,838 for the privilege of borrowing $100,000 for 30 years.  But, of course, now we know there's nothing arbitrary about that $215,838.  It's the logical consequence of applying The One Law Of Interest Payments.

Friday, September 14, 2012

Dave Computes A Very Tiny Interpreter

Several years ago I designed a simple 4-bit computer processor that my students could build from TTL chips and wire. I called the processor the CHUMP (Cheap Homebrew Understandable Minimal Processor), and I called the corresponding programming language Chumpanese (which we imagine is not constrained by 4-bit addresses).  You can read an early draft of the paper I wrote on it here.

Anyway, I was playing around with a well-known OISC (one instruction set computer) language tonight, in which the only instruction is:

subeq a, b, c

This instruction behaves as follows:

mem[a] = mem[a] - mem[b];
if (mem[a] == 0)
  pc = mem[c];
else
  pc++;

(subleq is the more popular version, which branches when mem[a]<=0.)

It occurred to me tonight that I could easily write an interpreter for this OISC in Chumpanese.  I used one address for the program counter.  pc would contain a, pc+1 would contain b, pc+2 would contain c, and pc+3 would be the beginning of the next instruction.  Here is the very tiny OISC interpreter I wrote in Chumpanese:

fetch: read pc load it add 1 storeto b       // b = mem[pc + 1]
       read pc read it load it               // mem[a] (a=mem[pc])
       read b read it sub it                 // mem[a] - mem[b]
       read pc read it storeto it            // store in mem[a]
       ifzero jump                           // if (mem[a] == 0)
       read pc load it add 3 goto end        // pc + 3 (next inst)
jump:  read pc load it add 2 storeto c       // c = pc + 2
       read c read it load it                // mem[c]
end:   storeto pc goto fetch                 // set pc and repeat

Yes, my students found Chumpanese awfully confusing, too, even though they knew exactly what voltages would change in response to each instruction.

Thursday, September 6, 2012

Dave Computes Complex Roots, Poetically


There is a nerdy poem about the square root of three that Kal Penn recites in the movie Harold & Kumar Escape from Guantanamo Bay.  Here is the parody I wrote when I was teaching complex roots in my precalculus course last year.

The Cube Root Of Three

I take the cake, you must agree,
for I'm a cube root of a three!
There must be three of me to make
a product you cannot mistake.
You think I'm one point four four two?
Well I've got something more for you!
Take half of that and multiply
by minus one plus root three i.
Did I say i? I can't be real.
You can't imagine how I feel.
You cannot see how it can be
That three of me can make a three?
Just FOIL me with me and then
that conjugates with me again.
Do you feel foolish next to me?
Confused by my complexity?
My formula you can derive
in Precalc section six point five.

Wednesday, September 5, 2012

Dave Computes Hold'em Poker Starting Hands

Over the past few years, I've put far too much energy into Hold'em Poker computations.  Possibly the most useful thing I've done in this regard is simply to put together what I hope is the definitive source of starting hand data.  I wrote a Java program that simulated 10 million rounds of heads-up play, in which both players see the showdown.  (This would have been impossible without stumbling onto Kevin Suffecool's super-fast Poker Hand Evaluator, which I then ported to Java for convenience.)  I found, for example, that AA had the highest winning percentage of 85% and 32o had the lowest winning percentage of 32%.  I then simulated 10 million 3-player games, in which all 3 players saw the showdown.  This time AA won 73% of its games and 32o won 20%.  I then simulated 10 million 4-player games, then 5-player games, and so on, up to 10 players.  All of this data is available in a spreadsheet.

One obvious observation we can make from this data is that the relative value of a starting hand depends on the number of players.  This phenomenon is easy to explain:

1.  It takes a stronger hand to beat more opponents.
2.  Some hole cards are better at making strong hands (straights and flushes) but are worthless when they miss the board entirely.  Other hole cards will consistently make medium-strength hands (pairs and high cards) but will rarely make strong ones.

Rather than looking at how often a particular starting hand wins, I found it more useful to ask the question:  If I decided to play, say, 20% of the starting hands dealt to me, which 20% should I play? Heads-up, that would mean playing any hand A3s-or-better, and folding any hand K9o-or-worse.  I therefore call A3s a top-20% hand, because it is the least-winning hand of the top 20% of hands dealt in heads-up play.  (These percentages also appear in the spreadsheet)  This way of describing a starting hand makes it easy to analyze how the value of a hand depends on the number of players in the game.  For example, the following table follows the changing values of 3 particularly volatile hands.



77
A9o
JTs
2 players
top 4%
top 13%
top 24%
3 players
top 7%
top 16%
top 15%
4 players
top 10%
top 19%
top 11%
5 players
top 14%
top 20%
top 10%
7 players
top 19%
top 23%
top 8%
10 players
top 15%
top 32%
top 6%