Dave Computes with Tag Systems

Overview

A tag system is arguably the simplest universal model of computation. It consists of a set of rules for rewriting strings, in which a fixed number of symbols are deleted from the beginning of a string and new symbols are added to the end. For example:

When a string starts with 0, remove the first 2 symbols and append 20.
When a string starts with 1, remove the first 2 symbols and append 01010.

We'll summarize the rules of this system as:

0x -> 20
1x -> 01010

These rules tell us to rewrite the string 10 as 01010, and to rewrite that as 01020, and so on, resulting in the following process:

10, 01010, 01020, 02020, 02020, 02020, ...

This process repeats a string that has already been reached, resulting in an infinite loop. Repeating is one of four possible outcomes when using a tag system. Halting is another outcome, which occurs when there is no rule for the starting symbol:

001, 120, 001010, 101020, 102001010, 200101001010

A related outcome is an underflow, in which the string length shrinks to below the deletion number, as would trivially be true for any one-character string in this particular system. Finally, a string can grow without bound:

101, 101010, 101001010, 100101001010, 010100101001010, 010010100101020, 001010010102020, 101001010202020, 100101020202001010, 010102020200101001010, 010202020010100101020, 020202001010010102020, 020200101001010202020, 020010100101020202020, 001010010102020202020, 101001010202020202020, 100101020202020202001010, ...

We might call this behavior overflow or blowing up. (We can prove this particular string grows without bound by noting that the number of 2's grows from 0, to 3, to 6, to 9, etc.)

Every tag system has a number of symbols (3 for this system), a rule for each symbol (possibly excluding a halting symbol), and a deletion number (2 for this system).

I wrote a program to systematically test various simple tag systems. Here are a few of my favorites.


1-Tag Systems

We'll start with a simple 1-tag system (a system with deletion number 1).

0 -> 0
1 -> 01

This is a 1-tag system, because its deletion number is 1. Starting from the string 1, this system generates the following process.

1
01
10
001
010
100
0001
0010
0100
1000
00001

The boldface indicates that 1 is rewritten as 01. When we rewrite all of its symbols we get 001, which is fully rewritten as 0001, which becomes 00001, and so on. We can therefore think of this system as repeatedly inserting a single 0 at the front of the string.

A slight change to these rules results in a much more interesting tag system.

0 -> 1
1 -> 01

From starting string 0, this system gives us:

0
1
01
11
101
0101
1011
01101
11011
101101
0110101
1101011
10101101

We can easily show that any string will blow up in this system. At first, the blow up appears to be quite chaotic, but upon closer inspection we find the Fibonacci sequence in the lengths of the boldface strings. Specifically, string 0 (length 1) is rewritten as 1 (length 1), which is rewritten as 01 (length 2). When both of its digits are rewritten, we get 101 (length 3), and when all of its digits are rewritten we get 01101 (length 5), and then 10101101 (length 8). Furthermore, just as each Fibonacci number is the sum of the two previous Fibonacci numbers, each of these fully rewritten strings consists of the concatenation of the previous two such strings. For example, 01101 (the string corresponding to 5) consists of 01 (the string corresponding to 2) followed by 101 (the string corresponding to 3).

We might wonder how quickly these strings are growing. Do they grow in a linear fashion, so that each string grows on average by k characters, and the expected length of the nth string is kn? One thing we know about the Fibonacci sequence is that the next term is 1.618... (the golden ratio) times the current term (in the limit). That means that if the string representing the current Fibonacci number has length L, then L terms later it will be rewritten to have length 1.618L (roughly), or L + 0.618L. Therefore, the string grew by 0.618L over the course of L steps, or by an average of 0.618 symbols per step. After n steps, the string ought to be roughly 0.618n symbols long.

We can interpret the rule 1 -> 01 as finding the sum of the previous term in a numerical sequence (0) plus the current term (1). An interesting variation is to use the rule 1 -> 011, which finds the sum of the previous term (0) plus twice the current term (11). That gives us the following rules.

0 -> 1
1 -> 011

Starting from 0, the sequence of fully rewritten strings is now:

0 (length 1)
1 (length 1)
011 (length 3)
1011011 (length 7)
01110110111011011 (length 17)

That gives us the sequence 1, 1, 3, 7, 17, 41, ..., where adding the previous term to twice the current term gives us the next term. Here, we can prove the common ratio is 1 + sqrt(2), and from that we conclude that each string is growing by roughly sqrt(2) symbols, and that the nth string will consist of roughly 1.414n symbols. In the same way, the rule 1 -> 0011 gives us the common ratio 1 + sqrt(3), with strings growing by sqrt(3) symbols. In general, if the rule for rewriting the symbol 1 consists of a zeros and b ones, then the common ratio will be [b + sqrt(b^2 + 4a)] / 2.


Tag Systems relating to the Collatz Conjecture

Consider the following 2-tag system (a system with deletion number 2).

0x -> 1
1x -> 02
2x -> 111

Starting from the string 111, this system results in the following process:

111 (3)
102
202
2111
11111 (5)

11102

10202

20202

202111

2111111

11111111 (8)

11111102

11110202

11020202
02020202
0202021
020211
02111
1111 (4)
1102
0202
021
11 (2)
02
1 (1)

What is happening here? If we consider only the boldface steps (those consisting of all ones), we have produced the sequence 3, 5, 8, 4, 2, 1. When a number is even, we halve it. When a number is odd, we triple it, add 1, and (since the resulting number is always even) we immediately halve it.

even -> divide by 2
odd -> multiply by 3, then add 1, then divide by 2

Thus, the question of whether all positive integers (represented as a sequence of ones) will result in an underflow (terminating with a single 1) is equivalent to the famous Collatz conjecture (the 3n+1 problem). Every positive integer ever tested does result in an underflow. Proving this is true for all positive integers or disproving it would be a big deal. This is a significant open problem in mathematics.

Let's take a closer look at the rules for this system, shown again here.

0x -> 1
1x -> 02
2x -> 111

We have a rule that shrinks by 1 symbol (0x -> 1), a rule that grows by 1 symbol (2x -> 111), and a rule that replaces a string of 1s with a string of 02s (1x -> 02). If the original string of 1s has an even length, it is replaced by an equal length of 0202...02, resulting in the shrink rule firing. If the original string of 1s has an odd length, it is replaced by an equal length of 2020...2, resulting in the growth rule firing. In other words, 2-tag systems let us test if a string's length is odd or even. In this case, we have roughly an equal chance of growing by 1 or shrinking by 1, which is what appears to make this system teeter on the edge of underflow and blowing up.

Of course, we would also have an equal chance of growing or shrinking if we rewrote 1x as 20 (instead of 02). Let's see how the resulting system behaves.

0x -> 1
1x -> 20
2x -> 111

Starting from 11111 (5), we get to a single 1 and underflow:

11111 (5)

11120

12020

02020

0201

011

11 (2)

20

111 (3)

120

020
01
1 (1)

On the other hand, starting from 1111 (4), we eventually repeat the 4, resulting in an infinite loop:

1111 (4)

1120

2020

20111

111111 (6)

111120

112020

202020

2020111

20111111

111111111 (9)

111111120

111112020

111202020

120202020

020202020

02020201

0202011

020111

01111

1111 (4)

...

Here is the simple rule describing these number sequences:

odd -> divide by 1 (discarding any remainder)

even -> multiply by 3/2

Starting from any positive integer from 1 to 15, we either reach the number 1 (resulting in an underflow) or the number 4 (resulting in an infinite loop):

11, 5, 2, 3, 1

4, 6, 9, 4, ...

14, 21, 10, 15, 7, 3, 1

8, 12, 18, 27, 13, 6, 9, 4, ...

Starting from 16, we find a new infinite loop:

16, 24, 36, 54, 81, 40, 60, 90, 135, 67, 33, 16, ...

Now every number reaches 1, 4, or 16. (Mathematically, it may make more sense to stop at 0 instead of 1.) Are there other scenarios? I wrote a program to find out. The program tested integers up to 1 billion. Amazingly, every single number reached 1, 4, or 16. Even stranger, I found that

32.6868782% of numbers reach 1,
32.4952364% reach 4, and
34.8178854% reach 16.

How crazy is it that these are so closely balanced, and yet never seem to arrive at 1/3! These percentages appear to be remarkably stable (approximately true for numbers from 1 to n, regardless of the exact value of n.)

We can also create 3-tag systems based on the same idea.  For example:

0xx -> 1
1xx -> 022
2xx -> 1111

Notice that the 1xx -> 022 rule ensures that the 2xx rule (which adds 1 to the length of the string) will run twice as often as the 0xx rule (which subtracts 2), meaning that growing and shrinking are approximately balanced. The same is true if we use 1xx -> 202 or 1xx -> 220. Each of these rules produces different chaotic number sequences with seemingly no blow up. The same is true of:

0xx -> 11
1xx -> 002
2xx -> 11111

This system corresponds to:

(n mod 3 == 0) -> 2n / 3
(n mod 3 == 1) -> (5n + 4) / 3
(n mod 3 == 2) -> (2n - 1) / 3

All inputs tested result in underflow with final string 11 (2). (Mathematically, it may make more sense to stop at 1.) An input of 1111111111111111111 (19) doesn't underflow until 1,619 steps! Here is the resulting sequence:

19, 33, 22, 38, 25, 43, 73, 123, 82, 138, 92, 61, 103, 173, 115, 193, 323, 215, 143, 95, 63, 42, 28, 48, 32, 21, 14, 9, 6, 4, 8, 5, 3, 2

Similarly interesting behavior is observed for the rule 1xx -> 020 or 1xx -> 200.


Chaotic Tag Systems 

I'm especially interested in cases where a simple input in a simple tag system survives for a large number of steps before underflowing. Perhaps the most studied tag system is

0xx -> 00
1xx -> 1101

Let's observe what happens for input 111.

111
1101
11101
011101
10100
001101
10100 [repeat]

As we can see, an input of 111 repeats on the 7th step. An input of 1111 repeats on the 6th step. Here's a summary of this tag system's behavior on inputs consisting only of ones:

3 ones -> repeat on step 7
4 ones -> repeat on step 6
5 ones -> repeat on step 23
6 ones -> repeat on step 22
7 ones -> repeat on step 21
8 ones -> repeat on step 18
9 ones -> repeat on step 17
10 ones -> repeat on step 16
11 ones -> repeat on step 33
12 ones -> repeat on step 32
13 ones -> repeat on step 31

Doesn't sound particularly exciting, until we discover that an input of 20 ones repeats on step 2,158, and an input of 14 ones underflows on step 411. Here are some excerpts of that process, along with the length of the string at each step.

11111111111111  (14)
111111111111101  (15)
1111111111011101  (16)
11111110111011101  (17)
111101110111011101  (18)
1011101110111011101  (19)
11011101110111011101  (20)
111011101110111011101  (21)
0111011101110111011101  (22)
101110111011101110100  (21)
...
101110111011101110111010000000000110111011101000000  (51)
1101110111011101110100000000001101110111010000001101  (52)
11101110111011101000000000011011101110100000011011101  (53)
011101110111010000000000110111011101000000110111011101  (54)
10111011101000000000011011101110100000011011101110100  (53)
110111010000000000110111011101000000110111011101001101  (54)
1110100000000001101110111010000001101110111010011011101  (55)
01000000000011011101110100000011011101110100110111011101  (56)
0000000001101110111010000001101110111010011011101110100  (55)
000000110111011101000000110111011101001101110111010000  (54)
00011011101110100000011011101110100110111011101000000  (53)
1101110111010000001101110111010011011101110100000000  (52)
...
0000000000110100110100001101110111011101001101  (46)
000000011010011010000110111011101110100110100  (45)
00001101001101000011011101110111010011010000  (44)
0110100110100001101110111011101001101000000  (43)
010011010000110111011101110100110100000000  (42)
01101000011011101110111010011010000000000  (41)
0100001101110111011101001101000000000000  (40)
000110111011101110100110100000000000000  (39)
11011101110111010011010000000000000000  (38)
111011101110100110100000000000000001101  (39)
0111011101001101000000000000000011011101  (40)
101110100110100000000000000001101110100  (39)
1101001101000000000000000011011101001101  (40)
10011010000000000000000110111010011011101  (41)
110100000000000000001101110100110111011101  (42)
1000000000000000011011101001101110111011101  (43)
00000000000000110111010011011101110111011101  (44)
0000000000011011101001101110111011101110100  (43)
000000001101110100110111011101110111010000  (42)
00000110111010011011101110111011101000000  (41)
0011011101001101110111011101110100000000  (40)
101110100110111011101110111010000000000  (39)
...
000000000000001101  (18)
00000000000110100  (17)
0000000011010000  (16)
000001101000000  (15)
00110100000000  (14)
1010000000000  (13)
00000000001101  (14)
0000000110100  (13)
000011010000  (12)
01101000000  (11)
0100000000  (10)
000000000  (9)
00000000  (8)
0000000  (7)
000000  (6)
00000  (5)
0000  (4)
000  (3)
00  (2)

Notice the complex patterns in this computation.

Of the tag systems I discovered in my research, this next one is probably my favorite:

0xx -> 0
1xx -> 11001

Here, an input of 111, arguably the simplest possible input, takes 588 steps to underflow! An input of 24 ones takes 5,274 steps to underflow, and an input of 30 ones takes an amazing 90,263 steps to underflow!

Here are some other tag systems with long underflows:

0x -> 0, 1x -> 002, 2x -> 112, starting from 11, takes 780 steps to underflow.
0x -> 0, 1x -> 012, 2x -> 0102, starting from 111, takes 46,119 steps to underflow.
0xx -> 00, 1xx -> 10011, starting from 1111, takes 11,200 steps to underflow.
0x -> 0, 1x -> 0022, 2x -> 0102, starting from 1111, takes 65,923 steps to underflow.

Intentional Computation

Here's a tag system I actually invented deliberately (instead of stumbling on through a search of all simple tag systems).

0x -> 0
1x -> 1010

Here's a sample run of this tag system.

000000001010
00000010100

0000101000

001010000

10100000

1000001010

000010101010

00101010100

1010101000

101010001010

10100010101010

1000101010101010

001010101010101010

10101010101010100

1010101010101001010

101010101010010101010

10101010100101010101010

1010101001010101010101010

101010010101010101010101010

10100101010101010101010101010

1001010101010101010101010101010

010101010101010101010101010101010

01010101010101010101010101010100

0101010101010101010101010101000

010101010101010101010101010000

01010101010101010101010100000

0101010101010101010101000000

010101010101010101010000000

01010101010101010100000000

0101010101010101000000000

010101010101010000000000

01010101010100000000000

0101010101000000000000

010101010000000000000

01010100000000000000

0101000000000000000

010000000000000000

00000000000000000

0000000000000000

000000000000000

00000000000000

0000000000000

000000000000

00000000000

0000000000

000000000

00000000

0000000

000000

00000

0000

000

00

0

The boldfaced strings consist of a sequence of 0s of length x followed by a sequence of 10s of length y (where x and y must be powers of 2). Over the course of the computation, these strings are rewritten as other strings in the same format.

000000001010 (x = 8, y = 4)

000010101010 (x = 4, y = 8)

001010101010101010 (x = 2, y = 16)

010101010101010101010101010101010 (x = 1, y = 32)

Notice that with each full rewrite the 0 part is halved and the 10 part is doubled. This makes sense, since the 0x -> 0 rule tells us to halve the 0 part, and the 1x -> 1010 rule tells us to double the 10 part.

One interpretation is that the original string represents "8 times 4", which is solved by computing:

8 times 4

= 4 times 8

= 2 times 16

= 1 times 32

Hence, we can successfully multiply powers of two. BUT a more intriguing interpretation is that the string 0 represents the number 0, the string 00 represents the number 1, the string 0000 represents 2, the string 00000000 represents 3, the string 0000000000000000 represents 4, and so on, so that a length of 2^m represents the number m (and the same for the 10 part). In that case, our original string represented (3, 2), and we were performing addition, by computing:

3 + 2
= 2 + 3
= 1 + 4
= 0 + 5

A simple modification allows the calculation to halt upon computing the desired answer.

0x -> 0
1x -> 1212

Now input 000000001212 represents 3 + 2 (or 8 times 4), and is fully rewritten as follows.

020202021212
000012121212
001212121212121212
012121212121212121212121212121212
21212121212121212121212121212120

The result halts on a string of length 32, corresponding to our solution (5 for addition, or 32 for multiplication). This works because the string length remains even throughout the computation, so that the string never begins with the halting symbol (2) until the computation is done. The length of the first part of the string (consisting of 0s) is repeatedly halved, until it consists of a single 0. This makes the entire string length odd, finally allowing the halting symbol to reach the front of the string.


Universality of 2-Tag Systems

The previous examples illustrate four key operations that 2-tag systems (tag systems with deletion number 2) can perform:

* Add a constant to the length of a string
* Double the length of a string
* Halve the length of a string
* Test if a string's length is odd

These operations are sufficient to give us data structures--specifically, a stack of bits, like the following:

0
0
1

We can represent this stack with the binary number "100", with the low-order bit corresponding to the top of the stack. Now, "100" is the binary representation of the number 4, which we can represent by a string whose length depends on the number 4. Specifically, we'll represent the number n as Aa followed by n copies of Bb. Hence, AaBbBbBbBb represents the number 4, and therefore also represents the stack of bits "100" shown above. Likewise, AaBbBbBbBbBb represents the number 5, and therefore the stack of bits "101".

Pushing a 0 onto a stack doubles its numerical value. For example, pushing a 0 onto the stack "10" (2) results in the stack "100" (2 times 2 = 4). Hence, we can push a 0 by using rules in our tag system that double the length of a string:

Ax - > Cc
Bx -> DdDd

These rules transform AaBbBb (2, and therefore "10") into CcDdDdDdDd (4, and therefore "100").

Likewise, pushing a 1 onto a stack doubles and adds one to its numerical value. For example, pushing a 1 onto the stack "10" (2) results in the stack "101" (2 * 2 + 1 = 5). We can achieve this operation with the following rules:

Ax -> CcDd
Bx -> DdDd

These rules transform AaBbBb (2, and therefore "10") into CcDdDdDdDdDd (5, and therefore "101").

Given what we know, popping a value off the stack should primarily involve halving the length of a string. But we'll also want to know if we popped a 0 or 1. Notice that when there is a 0 on top of a stack, the string representing that stack contains an even number of copies of Bb. Likewise, when there is a 1 on top, the string contains an odd number of copies of Bb. For example, AaBbBbBbBb (4, and therefore "100") has a 0 on top, while AaBbBbBbBbBb (5, and therefore "101") has a 1 on top. Therefore, we'll need to halve the length of our string (to pop a value) and test if the resulting length is even or odd (to determine what value we popped). We can halve the length with:

Ax -> C
Bx -> D

These rules transform AaBbBbBbBb (4) into CDDDD and AaBbBbBbBbBb (5) into CDDDDD. Next, we apply the rules:

Cx -> Ee
Dx -> Ff

These rules transform CDDDD (originally 4) into eFfFf and CDDDDD (originally 5) into EeFfFf. This is a good result because we have distinguished between popping a 0 and a 1. Specifically, if we popped a 0, the "e" rule will run next, followed by several applications of the "f" rule. If we popped a 1, the "E" rule will run next, followed by several applications of the "F" rule. Suppose we don't care what value was popped, and we simply wish to discard it. We can do so with the rules:

ex -> gGg
fx -> Hh

Ex -> Gg
Fx -> Hh

The first pair of rules transforms eFfFf (originally 4) into GgHhHh (now 2), and the second pair transforms EeFfFf (originally 5) into that same result. Thus, the stack "100" and the stack "101" are both transformed into "10", corresponding to popping the top bit off the stack.

If we can represent a stack of bits, we can also use two stacks to represent a queue of bits. In 1964, Cocke and Minsky showed that the contents of a Turing machine tape containing 0s and 1s could be thought of as 2 stacks--one to the left of the cursor and one to the right, with the top values representing the symbols closest to the cursor. They then showed how a Turing machine could be translated into a 2-tag system using the operations described above. Because any Turing machine (including a universal Turing machine) can be converted into an equivalent 2-tag system (with an arbitrary number of symbols), we know that 2-tag systems are universal (and therefore so are 3-tag systems, 4-tag, etc).

Dave Computes Optimal Hold'em Poker Play

Computers are beginning to play hold'em poker as well as the top human players.  Such computer players really consist of three computer programs run in three separate phases.

Phase 1:  Buckets
Because of the astronomical number of possible poker situations, programs are needed to assign a wide range of situations to a limited number of buckets.  For example, maybe K8s falls into preflop bucket 5, Q5 with a flop of QTT falls into flop bucket 7, TT with a turn of 9742 falls into turn bucket 8, and 94 with a river of Q9862 falls into river bucket 6.  The computer also calculates the probability that a player will be dealt a hand assigned to preflop bucket 6 (for example), and the probability that such a hand will move into flop bucket 4, then into turn bucket 7, and finally into river bucket 7, when it will beat hands in river bucket 6 and lose to hands in river bucket 8.

Phase 2:  Learning the Abstract Game
With the precomputed buckets and probabilities, a second program can now simulate abstract poker games at great speed.  In this phase, there are no playing cards at all--just bucket numbers.  The output of this program is an enormous table indicating how to play any hand (e.g. flop bucket 7) in any situation (after a given history of folds, calls, and raises of varying amounts).  Computing this table can require hundreds of processors running for months on end.  Various approximations are needed to ensure that results are computed in a reasonable amount of time, such as limiting the number of players, number of raises allowed, possible sizes of raises, number of buckets, size of betting history stored, and skipping betting altogether on one or more streets.

Phase 3:  Playing Poker by Numbers
After phase 2 does all the hard work, we finally get to play poker again in phase 3.  Here, a program simply converts any hand dealt to a bucket number and then makes the correct play for that bucket and betting history as found in the enormous table computed in phase 2.

Dreams of a Human-Usable Poker System
Sadly, such computer players have so far focused almost exclusively on heads-up poker, a variation rarely played in practice.  And more importantly, we humans have not benefited from all these calculations.  Our poker books still tell us how to play based only on the authors' intuition and experience.  These books are also incomplete, providing no insight into how to play in a multitude of situations.  Such books also stress that how you play a hand depends on how your opponents have been playing, but don't provide a foundation for how to play when you first sit down at a table--your ABC poker.  I want to see a book based on computed tables describing optimal play.  Of course, I can't memorize the large tables used by poker programs, so I also want to see these tables distilled into useful rules of thumb I can easily keep in my head and apply in real time.

My Summer Poker Project
To that end, this summer I coded the first two of these phases, with the goal of developing a system to help me perform Phase 3 as a human player.  I used my Easy Formula to assign preflop hands to buckets numbered from 0 (J2 and worse) to 14 (AA).  On the flop, turn, and river, I used buckets numbered from 0 to 9, where bucket 7 (for example) has a 70-79% chance of winning in a heads-up showdown on the river.  (In practice, no hands fall into preflop bucket 0.)  See my Flop Formula to get a feel for the different flop buckets.

For Phase 2, I used a counterfactual regret minimization algorithm, as explained beautifully by Neller and Lanctot in their 2013 paper entitled An Introduction to Counterfactual Regret Minimization.  In this algorithm, players begin by making each move at random.  After each play, the computer makes a note of how much better it would have been to make a different move.  These regret values are accumulated for each information set (e.g. bucket number and betting history for this deal).  Future plays are weighted based on these regret scores.  Over a long (and seemingly unpredictable) period of time, these strategies converge to the Nash equilibrium.

There were three reasons I was forced to make approximations in my program.

1.  Limited computation time
2.  Limited computer memory
3.  Limited human memory (I wanted to keep the resulting tables small and memorizable.)

I found that doubling the number of buckets would merely double the time, but my limited human memory held me to 15 preflop buckets, 9 flop buckets, 10 turn buckets, and 10 river buckets.  Increasing the number of players, number of raises per street, or number of possible raise sizes increased the computation time exponentially.  Cutting out a round of betting saved enormous time, and limiting history stored was critical to keeping the size of the output data to a manageable size for my limited brain.

All my computations are based only on pot-sized raises.  Experimentations with larger raises revealed that they were almost never chosen.  Smaller raises were helpful (though not often preferred to pot-sized raises).  Such smaller raises led to complex betting strategies that would be challenging to memorize.  (In short, whenever it'd be preferable to make a smaller raise with a weaker hand, it becomes necessary to make smaller raises with some of the strongest hands, too, to prevent exploitation.)  My results are primarily based on 2 raises per street, which I suspect leads to a resulting strategy that reraises too many hands (unafraid of a third raise).

Summary of What I Learned
1.  If you're the first to enter a pot preflop (and you're not one of the blinds), enter with a raise.

2.  You should not often find yourself laying down hands that you bet for strength.  If you're raised, plan to call often.  Likewise, if you limped in, you should probably call a raise.

3.  Any time you try to get away with limping in with a weak hand, you must compensate by limping in with your strongest hands (or you can be exploited by an opponent who bets/raises when you show weakness).

4.  You must bluff sometimes (or you can be exploited by an opponent who folds to all your shows of strength).

5.  On the button, you should generally only bet with your strongest hands and bluff with your weakest hands--the ones that don't have a chance of winning otherwise.  This means that you should often accept free cards with marginal hands that could still improve, instead of semibluffing them or using continuation bets.  Of the hands in the middle that you check, you'll check the worst with intention of folding, and the best with intention of calling.

6.  Under the gun, you should often check with intention of raising your strongest hands.  This is especially true on the flop and turn when you weren't the aggressor in the previous street.  If you were the aggressor in the previous street, you should come out betting with anything decent as a semi bluff or continuation bet.  You generally don't want to check raise here or bluff your weakest hands.  If you're called, you'd rather have a chance of improving.

Heads Up Preflop Details
This data is based on a multi-street game with 40 million trials (9 hours).

The button (Btn) should raise with 3+ and limp in with the rest (calling with 2+ if raised).
If checked, the big blind (BB) should raise 4+.  If raised, BB should call 3s and 4s, and reraise 5+.

Multi-Player Preflop Details
This data is based on a 5-player preflop-only game (i.e. no betting on flop/turn/river) with 10 million trials (6 hours).  As a result, position in post-flop play did not factor into these results.  The summary you see here has been approximated and simplified a bit to keep the list memorizable.  I'm naming the seats as:  Btn, CO, UTG, BB, SB.  UTG (under the gun) is first to act preflop.  I'm also assigning numbers to the non-blind positions based on the hands they open with:  UTG = 6, CO = 5, Btn = 4.

Opening
Seat n opens by raising n (and folding the rest).
SB opens by limping with 1, raising 4, and limping with 8.
BB opens by raising 3 (when SB limps and all else fold).

Defending Against a Raise
When seat n raises, all (except BB) call n+1 and reraise n+2.
(This also holds when seat n limps and someone else raises.)
If SB raised, BB calls 1 and reraises 6.
If Btn/CO raised, BB calls 2 and reraises 7.
If UTG raised, BB calls 3 and reraises 8.

Defending Against 2 Raises
When seat n raises and someone reraises, call with n+3.

When Opponents Limp In
When seat n opens by limping in, non-blinds call n and blinds call any.
All can raise with 8.

When You Are Reraised
Call any.

Heads Up Post-Flop Details
This data is based on a multi-street game with 40 million trials (9 hours).  These results are highly simplified for ease of memorization.  (I have doubts about the validity of some of these thresholds.)

Flop/Turn, BB:  Bluff some and bet 7+ (on flop after raising preflop) or check any (otherwise).

Btn, after BB checked:  Bluff often and bet 7+ (on flop) or 8+ (on turn/river).

Flop/Turn, facing bet:  Call 5, raise 6+ (on flop with no preflop raise) or 8+ (otherwise).

River, BB:  Bluff often and bet 9.

River, facing bet:  Call 8, raise 9.

Dave Computes Players-Per-Street Statistics in Hold'em Poker

This data is based on a simulation of 100,000 hold'em poker deals with 5 players, with a cap of one pot-sized raise per round (to allow a large number of hands to complete in 8 hours).  Although the player strategies were probably far from optimal, I believe that the play frequencies computed at the end of 100,000 deals are probably fairly accurate.

19% of deals are decided preflop.
32% of deals are decided on the flop.
18% of deals are decided on the turn.
31% of deals are decided on the river.

On the flop, 47% of deals are heads-up, 27% are 3-way, 6% are 4-way, and 1% are 5-way.

On the turn, 38% of deals are heads-up, 9% are 3-way, 2% are 4-way, and 0% are 5-way.

On the river, 24% of deals are heads-up, 6% are 3-way, 1% are 4-way, and 0% are 5-way.

Since 100% of deals are multi-way preflop, it's important to know preflop play cold.
The next most common situations are a heads-up flop (47%), a heads-up turn (38%), a 3-way flop (27%), a heads-up river (24%), a 3-way turn (9%), a 3-way river and a 4-way flop (6%).

In other words, improve your heads-up flop/turn play before worrying about 3-way play, and 4-way play ought to be very rare.

Dave Computes a System for Evaluating Flops in Hold'em Poker

Here is a simple but effective system for giving a rough estimate of how good your Hold'em poker hand is on the flop.  We'll group hands by how likely they are to win a showdown in a heads-up game.  A hand that scores a 9 should win a heads-up showdown 90-100% of the time.  A hand that scores an 8 should win a heads-up showdown 80 - 89% of the time, and so on.  When a pair is made, this system awards more points for higher pairs--regardless of the presence of overcards in the flop or the strength of kickers.  This surprising aspect of the system is nonetheless consistent with probabilities of winning a hand, as determined empirically.  Of course, overcards and kickers do matter, but they don't often move a hand out from winning 75% of the time (say) to winning 65% or 85% of the time.

The Flop Scoring System
+9 for trips

+8 points for KK
+7 points for 99
+6 points for 66
+5 points for 22, 4-flush, open-ended straight, A on a paired flop
+4 high cards, gutshot
-1 for single-suit flop with no flush draw
-1 for no-gap (e.g. 987) or one-gap (e.g. 976) with no straight draw

9-Point Hands
These are made hands, like A5 with a flop of 432.  Most 9-point hands are trips, like 33 with a flop of K73, or 52 with a flop of 554.

8-Point Hands
J6 with a flop of JT6 scores 8 points for making 2 pairs.  AA with a flop of KT7 scores 8 for making a pair of aces, as does A2 with a flop of AQK (despite the weak kicker and threatening board).  So does K4 with a flop of K53 for making a pair of kings.

7-Point Hands
Q5 with a flop of QTT scores 7 for making a pair of queens (no credit awarded for making 2-pair on a paired board).  Likewise, J6 with a flop of AJ5 scores 7 for making a pair of jacks.

6-Point Hands
83 with a flop of A82 scores 7, as does 77 with a flop of 954.

5-Point Hands
54 with a flop of QT5 scores 5, as does J3 with a flop of 763.  Jc8h with a flop of Qh9h5h scores 5 for a 4-flush.  Likewise, KT with a flop of QJ4 scores 5 for an open-ended straight.  A5 with a flop of KK4 scores 5 for holding an ace on a paired flop.  Th6h with a flop of Ks6s3s scores 5 points:  6 for a pair of sixes and -1 for a single-suit flop.  Likewise, Q6 with a flop of 764 scores 5 points:  6 for a pair of sixes and -1 for a single-gap flop.

4-Point Hands
J2 with a flop of 432 scores 4 points:  5 for a pair of twos and -1 for a no-gap flop.  Nearly any other vaguely playable hand scores 4 points.  These are generally hands with an ace or a couple of high cards, like KJ with a flop of Q32, or A2 with a flop of 974.  Gutshots also score 4 points, like T4 with a flop of KQ9.

4-and-Lower
4-point hands are generally worthless.  These are hands you hope will improve for free, but you should probably not invest any money in them (even as bluffs).  Because of this, there's no sense in developing a rule to distinguish 4-point hands from 3-point hands.  The very worst hands score 1 point.  (All hands have at least a 10% chance on the flop of winning a heads-up showdown.)  1-point and 2-point hands have virtually no possibility of improving.  These hands are probably worth a single bluff given the right circumstances, but should otherwise be discarded.

Turn Scores
Regarding the dream of a scoring system for turn and river holdings, turn evaluation is very subtle.  It appears to depend about equally on both the strength of the hand you made and the number of single cards that an opponent could hold that would beat your hand.  Maybe the best way to evaluate the turn is simply to start with your flop score and then decide whether the turn card itself ought to bump the value of your hand up or down.  A formula would certainly be welcome, as evaluating your hand at the turn is quite critical.

River Scores
Evaluating at the river is probably less critical, as few hands ought to reach the river, and you can usually tell whether you made your hand or not and whether your opponent is likely to have made a better hand.  The single most important aspect of evaluating a hand at the river is the number of single cards that your opponent might hold that would beat your hand.

Dave Computes Playing No-Limit Poker against an All-In Maniac

You're heads-up (or may as well be) in a no-limit poker game against a maniac who goes all-in every hand.  How often should you call him down?

This scenario is quite common in play-chip poker games, where no money is on the line.  Clearly we should be able to exploit the maniac's play, and we can.

I wrote a computer simulation of poker games like this, beginning with various stack sizes and using various betting and calling thresholds.  In each scenario, I simulated 100,000 games in which one player eventually ran out of chips.  Here's what I learned.

Stack sizes make a big difference in correct calling frequency.  In particular, what really counts is the size of the smaller stack relative to the size of the ante.

Size Of Smaller Stack	Optimal Calling %	Sample Hold'em Hands	Caller Win %
100 × ante	7%	77, AK, ATs	95%
50 × ante	10%	66, AT, KJs	92%
20 × ante	23%	K9, K7s, A5	84%
10 × ante	34%	A2, K4s, K6	74%
5 × ante	55%	J3s, Q3, 87s	63%
2 × ante	76%	T3, 92s, 76	53%

against a maniac who goes all-in 100% of the time

In other words, if one of you has a stack size of 50 times the ante and the other has a larger stack, then you should call down the constant-all-in-maniac 10% of the time (which corresponds to hands like 66, AT, and KJs in Hold'em), and you can expect to finish with all the chips 92% of the time.  For me, the real take-home point here is not to loosen up too much when the stack sizes are big.

What if the maniac "only" goes all-in half of the time (and folds the other half)?  Here's what my simulation found for that scenario.

Size Of Smaller Stack	Optimal Calling %	Sample Hold'em Hands	Caller Win %
100 × ante	1%	AA, KK	99%
50 × ante	1%	AA, KK	98%
20 × ante	5%	77, AQs, AJs	95%
10 × ante	10%	66, AT, KJs	90%
5 × ante	17%	A8, KT, A6s	81%
2 × ante	34%	A2, K4s, K6	69%

against a maniac who goes all-in 50% of the time

Not surprisingly, when the maniac tightens up, so do we.  But notice we should now play much tighter against the 50% maniac than we did against the 100% maniac.  In a Hold'em game with stack sizes of just 50 times the ante, the maniac is raising hands as poor as J5s, and we're correct in folding QQ!  Why?  Because the simulation tells us so, presumably because our stack size (along with the 50% of the time that the maniac folds his ante to us) lets us wait for a nearly sure-thing with AA or KK, rather than risk going bankrupt with an unlucky loss with QQ.

How about if the maniac goes all-in with just 20% of his hands (and folds the rest)?  Now even a stack size of just 5 times the ante is sufficient to let us call with only the top 1% of hands.

Of course, many all-in maniacs will limp into a hand instead of folding, so these aren't very realistic scenarios.  Nonetheless, it's clear that when your opponents are making disproportionately huge raises and going all-in after tiny pots, your best strategy is to be patient with your large stack and play tight, knowing that your opponents will pay you off when you make huge hands.

Dave Computes The Feinberg Formulas for Hold'Em Poker Starting Hands

Part 1:  Ranking Starting Hands

How can we memorize which Hold'em starting hands to play?  Our first problem lies in ranking all 169 possible starting hands.  I did this in an earlier post, and showed that the ranking depends quite a bit on how many players are in the hand.  In the chart below, you can see the ranking of starting hands for a heads-up game, a 3-player game (in which all 3 showdown every hand), etc.  My interpretation is that the 3Way column (for example) is appropriate for any game in which we expect 3 players to see the flop, regardless of how many people were dealt in and how many stay for the showdown.

The Avg column ranks hands using a weighted average of the value of that hand in different sized games, with 50% of the weight given to a hand's value in a 2-way flop, 25% in a 3-way flop, 12.5% in a 4-way flop, etc.  I think of it as a correction to the 2Way column, where hands that weaken with more players (like 77) are pushed down the list, while hands that become stronger with multiple players (like KJs) move up.

Our challenge now is to find a formula that helps us memorize the ranking of the most commonly played hands (especially the top third).  I considered more formulas than I care to admit.  I'll present the best two of these below.  Both are very faithful to my hand ranking.  The "Simple Feinberg Formula" boasts a very simple rule, but can be difficult to use in practice.  The "Easy Feinberg Formula" requires a small effort to memorize, but is extremely easy to apply.


Part 2:  The Simple Feinberg Formula

In this formula, A = 14, K = 13, Q = 12, J = 11, T = 10, 9 = 9, and so on.  We simply triple the high card, add the kicker, add 3 if suited, and add the number of possible straights (using both cards), as illustrated by the following examples.

KJ:  3 × 13 (high) + 11 (kicker) + 2 (straights) = 52

A7s:  3 × 14 (high) + 7 (kicker) + 3 (suited) = 52

K9s:  3 × 13 (high) + 9 (kicker) + 3 (suited) + 1 (straights) = 52

QTs:  3 × 12 (high) + 10 (kicker) + 3 (suited) + 3 (straights) = 52

These hands have the same score because they're about equally strong in my ranking.  For a pocket pair, triple the value and add 34.

66:  3 × 6 + 34 = 52

Let's see the results.

So, if in a certain preflop situation you felt you ought to raise 14% of the time, you could raise any hand with a score of 52 or higher.  (See my earlier post for a discussion of how often to raise preflop.)

This formula exactly reproduces the top 50 hands in my ranking.  (In fact, the formula makes only 4 "mistakes" in ranking the top 60 hands, which can be corrected by adding 1 point to the scores of 55, 44, JT, and T9s.)  The formula is granular enough that you can adjust your play to your exact position.

Ok, so the scores are rather high, which makes it difficult to perform the necessary mental math quickly.  But I claim it's easier than it looks.  In most situations, a quick estimate is enough to decide whether to enter a hand.  You probably already recognize premium hands like 99, AQs, and AK and trash hands (nearly anything with a high card below a jack), so you can skip the math on these.

I find the fastest way to perform the calculation is to start with the high card, then add 1 if it's suited, then triple this result, then add the kicker, and finally add the number of straights.  You'll quickly discover that the same numbers come up all the time:

AXs = (14 + 1) × 3 =  45
AXo = KXs = 14 × 3 = 42
KXo = QXs = 13 × 3 = 39

QXo = JXs = 12 × 3 = 36

Once you know these, the math gets much easier.  Another key is to stop calculating as soon as the score passes the desired threshold (or clearly won't get there).  This way you won't have to determine the number of possible straights often.

If you'd prefer to work with smaller numbers, you can reduce the card values without affecting relative card rankings.  For example, you might use A=4, K=3, Q=2, J=1, T=0, etc., for the high card (but this requires using negative numbers for hands like 98s).

The Simple Feinberg Formula distributes the top 50% of starting hands into more than 20 hand groups.  That sounds great, and it is if you can take advantage of this in your play.  But you might not want to memorize a different strategy for each group.  The solution is to bundle multiple scores into larger groups.

A simple approach is to round all scores to the nearest multiple of 3 (for example).  50, 51, and 52 would all round to 51, and would therefore all be played the same way.  The good news is that this means there's no need to triple in the first place.  We could simply add the kicker and number of straights, divide by 3 and round to the nearest integer, then add the high card and 1 more if suited.  Now the numbers are smaller, but they're not really any easier to compute.  The bad news is that there are good reasons for treating scores of 50, 51, and 52 differently.

A better solution is to group scores into more meaningful ranges.  Suppose you consider 41 to be a reasonable threshold for raising heads-up, 47 for raising on the button, and 50 for raising from the cut-off.  Now you've got a few hand groups:  the 40-and-less group, the 41-46 group, the 47-49 group, and the 50 group.  Of course, this approach would require memorizing the numbers 41, 47, and 50, along with how to play such hands.  There must be an easier way...


Part 3:  The Easy Feinberg Formula

Although many people treat all small pocket pairs (66 - 22) the same, we see from our hand ranking that there are surprisingly large differences between the values of these hands.

The Simple Feinberg Formula above asked us to triple pair values, triple high values, and add 3 for suited hands.  That leads us to the following key observation.  If K8 (a top 30% hand) is about as strong as 44, then A8 (like K8, but with a higher top card) and K8s (like K8, but suited) should be about as strong as 55 (the next pair up).  In practice, this trick works impressively well.  For that reason, the Easy Feinberg Formula groups hands into "plays like 55," "plays like 66," etc.  (The strange kicker values in the Easy Feinberg Formula have been determined empirically, with the goal of faithfully producing the above hand rankings.)

Rule #1:  The value of pocket pair XX is X.

 Examples:  The value of 66 is 6.  The value of KK is 13.

Rule #2:  High card values are 3 for Ax, 2 for Kx, and 1 for Qx.  All other high cards are worth 0. 

Rule #3:  Kicker values are:

5 for xK
4 for xQ, xJ, xT
3 for x9
2 for x8, x7
1 for x6, x5, x4, x3
0 for x2

Examples:

AK = 3 (Ax) + 5 (xK) = 8
A2 = 3 (Ax) + 0 (x2) = 3
Q8 = 1 (Qx) + 2 (x8) = 3
T9 = 0 (Tx) + 3 (x9) = 3

Rule #4:  Add 1 if suited.

KQs = 2 (Kx) + 4 (xQ) + 1 (suited) = 7
J3s = 0 (Jx) + 1 (x3) + 1 (suited) = 2

If you can will yourself to memorize the kicker values, the payoff is a formula that's easy to apply and gives the following results, which again are quite faithful to the hand ranking shown earlier.

So, if in a certain preflop situation you felt you ought to raise 15% of the time, you could raise any hand with a score of 6 or higher.  An easy (but simplistic) rule might be to play 3+ from the blinds (and heads-up), 4+ from the button, 5+ from 1-off-the-button, and 6+ from 2-off-the-button.  Note that it's roughly the case that raising your score threshold by 2 will halve your play frequency.  So, if you believe someone would raise with a score of 4+, you might reraise them with a score of 6+.

Dave Computes Poker Play Frequencies

A super-important problem in poker is determining whether your poker hand is likely to be the best at the table, without knowing what your opponents hold.  In this post, I'll assume that you know absolutely nothing about your opponents' hands, but you know the exact value of your own hand.

For example, suppose you're one of 3 players in a Hold'em poker game.  You expect to have the best hand about 33% of the time.  Suppose you hold K7o preflop and you're first to act (on the button).  Using the spreadsheet I made available in an earlier post, you see that only 32% of all possible hands are more likely to win than your K7o.  I'll therefore refer to K7o as a 32% hand.  Since this is less than 33%, you might assume you have a better-than-even chance of holding the best hand.  Are you correct?  No.  Let's see why.

There is a 68% chance (100% - 32%) that your K7o will beat any single opponent.  That means there's a 0.68 * 0.68 = 46% chance that your hand is better than both of your opponents', and a 54% chance that it isn't.  How strong must your hand be to have a 50% chance of beating both?

Let p be the probability that a single opponent's hand will beat yours.  (In the case of K7o, p = 0.32.)  Then the probability of beating a single opponent is (1 - p).  The probability of beating both opponents is (1 - p)².  Now set this equal to 0.5 and solve for p.

(1 - p)² = 0.5
p = 1 - (0.5)^1/2 = 29.29%

What does that mean for our poker play?  It means we can't raise a K7o for value in this situation, because there's a 54% chance we're just giving that money away to an opponent.  Actually, the situation is not so straightforward.  If I'm on the button, I'll be last to act on all remaining rounds, giving me an edge that probably brings my chances of winning the hand closer to 50%.  (There are a lot of other subtleties to consider here, too.  If both opponents will call me down no matter what, then I have enough pot equity with my better-than-33% hand to raise for value.  However, in a 3-way hand, my K7o goes down in value and is now beaten by 36% of possible hands.)

So, it is reasonable to raise a top-29.29% hand for value in a 3-player game.  Solving
(1 - p)³ = 0.5, we find that it's reasonable to raise a top-20.63% for value in a 4-player game.  Note that this reasoning holds for any poker game.  But you can only apply it when you know the exact value of your hand, as you might in Hold'em preflop play.

Suppose we're on the button in a 4-player Hold'em game, and the first player folds.  Now we're effectively in a 3-player game, so we can raise a 29.29% hand for value.  This explains much of why your position changes the number of hands you can play.  (By the way, my math has convinced me that you should nearly always open with a raise in a game of hold'em.  I rarely open by calling.  When someone does limp ahead of me, I'm more likely to limp in with hands I might have opened with a raise.)

In general, in an n-player game, we can find this threshold by solving (1 - p)^{n - 1} = 0.5 for p.

p = 1 - 0.5^{1/(n - 1)}

Here's what we find.

Number Of Players	Threshold
2	50.00%
3	29.29%
4	20.63%
5	15.91%

Now, suppose you're in a 5-player game of Hold'em.  The player under the gun opens with a raise (which we'll assume is not particularly monstrous).  The next player folds.  You're on the button.  You believe that raiser must have a top-15.91% hand.  You have ATo--a 9.5% hand with one opponent.  Do you reraise?  If we ignore the fact that you have position on the raiser, you should fold.  Why?  Because your opponent holds a 15.91% hand or better--anything from A8o to AA.  More than half of those hands are stronger than your ATo.  To raise, your hand must be in the top 15.91% / 2 = 7.96%.  So, you could raise a KQs (7.84%) or AJo (7.54%), but should fold ATo.

Now suppose you're the original raiser and the player on the button reraises you with what you assume to be a top-7.96% hand.  Using the same logic (and still ignoring position), you should reraise them back (potentially capping or putting yourself all-in at this point) with a top-3.98% hand (7.96% / 2) like 77 or AKs, but should probably call otherwise.

Number Of Players	Raise	Reraise	Cap
2	50.00% (J5s)	25.00% (QTo)	12.50% (A7s)
3	29.29% (J9s)	14.64% (QJs)	7.32% (AQo)
4	20.63% (A3s)	10.31% (A8s)	5.16% (AJs)
5	15.91% (A8o)	7.96% (KQs)	3.98% (77)
6	12.94% (A9o)	6.47% (ATs)	3.24% (88)
7	10.91% (KTs)	5.46% (AKo)	2.73% (99)
8	9.43% (66)	4.71% (AJs)	2.36% (TT)
9	8.30% (A9s)	4.15% (77)	2.07% (JJ)
10	7.41% (AQo)	3.71% (AKs)	1.85% (JJ)

These playing frequencies turn out to be fairly close to those suggested by successful poker players.

Let's use this table to work through one more example.  If you're the first to act among 6 players, then you can raise your top-12.94% hands (ignoring position again), which would be A9o or better in a tight game.  If you're reraised, you can expect your opponent to hold a top-6.47% hand (ATs or better), and you can therefore raise them back with a top 3.24% hand (88 or better).  Note again that we're not taking position into account or, more importantly, the playing styles of your opponents.

Incidentally, if you look at preflop Hold'em play in this way, you're not stealing the blinds--you're raising for value.

All of this begs the question:  How can I determine the strength of my hole cards without constantly turning to a spreadsheet?  I'll address this in my next post.