[Draft #3 --- 2001/07/11 0517 UTC]
copyright ©David Ness, 8 July 1999-7 July 2001
[Draft
#3 --- 2001/07/11 0517 UTC]
Purpose
This document is the first one of a series that are being written to describe programs that simulate some well-known games. The purpose of these documents is to illustrate how some interesting computer languages can be used to deal with problems that do not have an `obvious' computational formulation. That is to say, these problems are not inherently or obviously numerical in character.
Thus our purpose is to expose how these problems might be dealt with by some of these new programming languages, particularly J and K . We recognize, at the outset, that we are not trying to contribute (much) to the study of the games themselves, but rather only using them as a vehicle to help us expose the characteristics of the languages.
Why Simulate Games?
Games are an interesting problem domain. In general they are characterized by:
Many games, and here poker is a good example, are complicated enough that is is not trivial for us to deal in an analytic fashion with the possibilities, yet simple enough that we can often---given the power of today's computers---perform exhaustive enumerations of the game space to allow us to check the quality of the simulation techniques that we use to help us understand the games.
It is also often the case that very simple changes to the rules of the game can produce situations which are complicated enough to make any analytic formalations impossible. An example of this is a game like `Deuces Wild' which creates situations of considerable complexity out of very simple rules.
Some Words about J and K
J and K belong to a class of vector (or array) oriented interpretive languages. These languages, while interpreted, generally perform much better in problem solving situations than many people might suspect, because they implement basic vector and matrix operations with such efficiency that their overall performance is often excellent. While interpreters generally consume more computer resource than compiled programs with respect to some aspects of a problem, the languages we are looking at here are so efficient in thier handling of vectors and matricies that they may, on balance, be very effective in handling certain classes of problems.
These languages are regularly used in situations where high performance real time work needs to be done. Indeed, both languages have considerable currency on Wall Street where they are often used to perform central core operations in trading systems that need to be able to handle analytical calculations on large data bases which are conjoined with streams of active market data.
This document is generated in two versions. In one version the examples and programs are all expressed in J, while in the other they are all expressed in K.
Program Technique
The programs given here are early attempts by the author in the use of the languages we describe. More experienced programmers might find better formulations, but as our purpose is to look at the application of the languages, our hope is that well-explained code will help the readers come to understand at least one approach to the problems, and that it will spur them on to develop their own formulations.
Card Games
Card games fall into a number of broad classes. The games in each class share many common characterisics. Some of these categories, and their primary characteristics, include:
We might choose different representations for each of these games. For example, if we were interested in talking about Bridge, the concept of `suit' turns out to be very important. In many situations one has to answer questions like `Does the hand have any Spades' There is also a ranking of suits and a concept of a trump suit.
For Poker, this isn't the case. While the value of some of the hands may be dependent on simple characteritics of suit (i.e. they are all of the same suit), for the most part suit is of little interest, while `denomination' plays a rather large role. This leads to some natural choices with respect to representation.
Representing Cards
We begin by developing some technology that will allow us to talk about hands of Cards.
J operators all have names. Actually most operators have two names, one used when the operator is monadic and the other used when the operator is dyadic. For example, ^ represents `exponential' when monadic and `power' when dyadic. Similarly, % is `reciprocal' when monadic and `divided by' when dyadic. When describing these below we will give both names as, for example, in ^ [exponential-power] or % [Reciprocal-Divided By] .
We also note that J is 0-origin. The `first' column of a matrix is called Column 0. This applies to everything in J.
Operators we are about to need can now be described briefly. J `Help' facilities can be used to get the complete word on any of these definitions.
The basic math operations are + - * % , and they all have the usual dyadic meaning. An important distinction between the - [Negate-Minus] and the _ [Negative Sign-Infinity] should be emphasised. Consider 1 3 -5 7 . This is not a four element vector. It is a subtraction of one two element vector 5 7 from another 1 3 . But 1 3 _5 7 is a four element vector where the third element is negative.
< [Box-Less Than] has very different monadic and dyadic functions. As a monad, box takes whatever structure is to its right and places it into a box. While everything within a box has to be the same kind of thing (integer, character...), we can have vectors or matricies of boxes that have quite different things inside. The dyadic `less-than' function is the normal mathematical one.
# [Tally-Copy] As a monad, tally counts the number of elements of the thing on its right. As a dyad, copy produces each left hand element copies of each right hand element. For example 1 2 3#3 5 7 produces 3 5 5 7 7 7 .
i. [Integer-Index of] As a monad, integer produces a vector of integers from 0 up to its argument (minus one). As a dyad, index of performs a table lookup function that we will describe later when we need it.
@ [Atop] is real hard to describe. What it does is to avoid two successive operators from being treated as a `hook'. This is pretty deep J code so let's not worry about it for a while.
& [Bond/Compose] Bond converts dyadic operators into monadic operators. This is surprisingly useful. For example, %&13 converts the dyad `divided-by' into the monad `divided-by-13'.
| [Magnitude-Residue] As a monad, magnitude gives the absolute value of the argument to its right. As a dyad, a|b gives the remainder (residue) of dividing b by a .
<. [Floor-Lesser Of] As a monad, floor truncates its argument to the integer below (or just at) it. As a dyad it is the lesser of its left and right arguments.
, [Ravel-Append] As a monad, ravel `smashes' a matrix into a vector by (un)-ravelling it. As a dyad, a,b appends b to a.
? [Roll-Deal] As a monad roll produces a random integer in the range from 0 up to (one less than) its right argument. a ? b produces a elements drawn at random (without replacement) from the range 0 ... b-1 .
{ [Catalogue-From] We'll only describe the dyad `from' for the moment. From is the way we select an element from a vector. If we have 1 3{ 11 22 33 44 55 66 this results in 22 44 . 22 44 are the 2nd and 4th elements of the vector, and (remember) we refer to the elements (0-origin). So we ask for the 1 3 elements to get the 2nd and 4th.
=: [Is(Global)] is the basic global assignment operator. a =: 1 + 2 * i.4 will store 1 3 5 7 in a .
The each function is a J idiom. J has a built-in notion not only of a bunch of operators, but also of relations between operators such as `inverse'. each expolits this with respect to the > (open) which is the inverse of < (box). each essentially takes each element of a list of boxes, opens them, applies its left argument to the contents and then boxes them back. Thus it is a very convenient `iterator' that applies a function to a list.
idx is defined to be a two function `hook'. For idx one operator is # (copy) and the other is i.@# (integer atop tally). The purpose of this is to convert a boolean vector like 0 0 1 0 1 1 0 0 1 into a list of the indices where the value is `true' 2 4 5 8 . It works like this: The `hook' (g h) applied to argument y produces y g h y . That's the definition in this case. We get 0 0 1 0 1 1 0 0 1 # i.@# 0 0 1 0 1 1 0 0 1 Working from the right, tally (# ) leaves us with 0 0 1 0 1 1 0 0 1 # i. 9 I won't discuss the atop (@ ) that was processed here quite yet, but the tally counted the number of elements in the vector. The integer (i. ) now converts this to 0 0 1 0 1 1 0 0 1 # 0 1 2 3 4 5 6 7 8 Normal rules then cause copy (# ) to produce left vector copies of each right vector argument so we end up with 2 4 5 8 .
Card is a `train' of three operations of the form (Op1,Op2) The definition of the train (f g h) y is (f y) g (h y) , so Card will produce a list of two elements, one produced by (Op1 y) and the other produced by (Op2 y) . In this case Op1 is `remainder with respect to 13' and Op2 is <.@%&13 . This is `the floor of its argument divided by 13'. Thus the Card operator converts integers in the 0 ... 51 range into pairs where the first element is in the range 0 ... 12 and the second element is in the range 0 ... 3 . These represent denomination and suit respectively.
deal does a lot of work. (#&5) produces its right argument number of `5's and (#&52) produces its right argument number of `52's. Thus ((#&5)?(#&52)) produces its right argument number of five-card hands (vectors of 5 integers in the range 0-51 without replacement). The Card each@ part of this phrase causes the Card operator to be applied to each `card' in the dealt hands.
ShowHand is complicated and involves a bit too much to describe just yet. It also is a convenience, and thus not central to our condsiderations. Its form, however, diserves comment as this is the first case where we explicitly define something as a `verb'. The Name =: 3 : ... form defines Name to be a verb (either monadic or dyadic). The 3 is either followed by a quoted string or by a 0 and then subsequent lines of text up to a line containing only a right parenthesis. We will use both of these forms later.
These simple functions introduce a particular structure for talking about poker hands. At the lowest level the 52 distinct cards are represented by integers in the range 0 thru 51. For poker, however, this isn't a very useful representation. In order to make computation easier, the structure we choose is to represent each card as a two item vector consisting of (denomination,suit). The function Card converts any integer in the sequence of card numbers 0 ... 51 into a pair representing a denomination (the remainder with respect to 13) and a suit (the integer part of the quotient with respect to 13).
The deal n produces a `list' of n five card hands, drawn at random from the deck. For example:
The ShowHand function allows us to see the cards with their normal names should we wish:
At this point we have most of the technology that we need to be able to start experimenting with the game. Now it is time for a quick review of the rules of the game that we will want to implement.
Poker: The Game
In the basic game of poker we are concerned with ranking five card hands. These five cards may be the cards we were dealt (Straight Poker) or may be the result of selecting five cards from some larger number (usually seven) (`Seven Card' games) or by throwing away some cards and replacing them with new cards from the deck (`Draw Poker'). In some variations, certain cards are `wild' and can be `called' to be other cards to help increase the value of the hands.
In this paper we are concerned only with the evaluation of hands with respect to the `rules' of Poker. This is only a part (some would say the least interesting part) of the play of the game. The rules establish, without equivocation, the ranking of hands. However, it is the betting process that helps determine the interesting outcomes of playing poker in the real world.
It is not our purpose, here, to analyze poker `playing strategies'. That will come later. However, to the extent that we develop technology that allows us to deal and evaluate hands, we could later turn to studying some of the strategies that we might want to test. A later section of this paper will deal with strategic studies.
Poker: The Rules
Without falling prey to an attempt to give an absolutely complete description of poker hands, let's review some of the rules just to make sure we understand them the same way:
The fact that this discussion of the rules, even at this rather simple level, requires so much detail is some indication of the complexity of the situations that arise in poker. Culbertson's Hoyle is an excellent source for a definitive treatment of all of the rules, should the reader desire more detail.
Computing Poker Rankings
We want to develop some way of looking at a hand that allows us to categorize them without going into excruciating detail about each particular specific characteristic of the type of hands.
To do this, one particular function proves to be very useful:
There is some fairly complicated J needed to count up the denominations in a hand. This fragment chooses a method which involves a reasonable amount of computational work, but is otherwise straightforward. It seems to work about as quickly as more elaborate attempts.
First, we introduce the all important notion of an `adverb'. The / [Insert] is used in J to `compose' a new verb out of an existing verb. For example, +/ converts `plus' into `sum of' or `+ table'. For insert, the basic notion is that u/ causes the operator u to be placed between each element of its argument. Thus, +/1 3 5 7 results in 16 (i.e. 1+3+5+7 ). If we put it between two vectors, the effect is to produce the table that results from taking each element of the left vector and each element of the right vector and putting this operator between.
This notion is used twice in the definition of Cnt . Assume that y. is the right argument and is an `n by 5' array of the denominations of cards in n poker hands. Therefore (i.13) =/ y. will create a `13 by n by 5' array zeros and ones, having the value 1 where each of the denominations matches the corresponding index.
Next we want to add up these `counts', but we have to worry about the appropriate dimension. If we just try +/ , we will get a disappointing result of an `n by 5' array of 1s, (essentially indicating that there is one card per card in each hand... surprise!).
However, we can add across the second dimension of our array by `qualifying' the +/ operation with +/"1 . This tells J to add along the second dimension, returning the `13 by n' array that gives us the count of each denomination in each hand. Will discuss this further when we use it.
Now we can use our Cnt function if we put our data into the proper form. Hands is a 10 by 5 array of (boxed) cards. If we `open' the hands with >Hands we will have a 10 by 5 by 2 array of integers. For the purposes of counting the denominations, we will want to separate the denominations from the suits, so we can use the |: [Transpose] operator to rearrange the order of our indices. 2 0 1|:>Hands reorganizes Hands presenting its indices in last (2), first(0), middle(1) order. Then 0{2 0 1|:>Hands is a 10 by 5 array of denominations. We can hand this to Cnt and get a 13 by 10 array of denomination counts. By transposing this we get the 10 by 13 array we need.
In this form it is easy, for example, to see that 1{Hand contains a three-of-a-kind (of fives, column 0 is deuces, so column 3 is fives etc.). Notice also, that in this form there is no suit information. All of that has been neglected in forming this count.
Now we are getting ready to actually attempt to rank the hands. But to do so, we need to prepare to detect straights. They present an interesting problem, so we will do this by making a table:
The $ [Shape Of-Shape] function tells us the shape of an array when used as a monad, or it reshapes its right argument in the form indicated by its (vector) left argument if used as a dyad.
The code 9 13 $ 5 9 # 1 0 uses a cute trick to produce `rotated bands' of 1s. In this context think of the denomination count of a hand that has a straight. It will be a sequence of five ones in a row with zeros elsewhere. The code here produces a vector of five ones followed by nine zeros. The `shape' function then makes 9 rows of 13 elements out of this by continually re-using the (14 element)vector. If you think about the effect you see that there will be one more zero left over each new row. This effectively rotates the following elements to the right one slot.
This produces a table with ten rows. Each of the rows represents the one of the legal straights: 23456, 34567, ..., TJQKA, A2345 (represented as 2345A, of course).
By taking a Cnt and sorting it into ascending sequence, and taking the rightmost 5 elements, we can generate what we will call the `category' (Categ ) of a hand. This looks like the table:
The Type table then allows us to handle all of the major types of poker hands, with the exception of straights and flushes. Hands that are straights or flushes (or straight flushes) will be initially classified as `nothing' (their characteristic type is (1 1 1 1 1) ), but this will later be corrected by other operations.
Now the real work starts. As usual we need a couple more operators.
/: [Grade Up-Sort] as a monad returns indicies that would order its argument into an ascending sequence. /: 10 5 22 3 9 would produce 3 1 4 9 2 . If used as a dyad, it returns its left argument reordered according to its right argument.
hds gets the reorganized hands as we derived above. Counts gets the denomination counts of these hands, and Order gets the `ordering indicies' to sort each of the counts into ascending sequence.
~ [Reflexive] is an adverb which when attached to a monad causes its argument to be used both before and after the operation. A silly use might be +~ to mean `double'. A common use is /:~ which uses the result of `grade-up' to be applied to itself to produce the sorted argument (i.e. /:~ vec is the same as vec/:vec ).
} [Item Amend-Amend] is often hard to follow. This is the operator used to modify data in arrays. Oversimplifying, the form: vec =: (val) idx} vec produces the result vec with the (idx) elements modified to have values (val) .
First, each hand in the list is `counted' and saved in (Counts) . Then the characteristic type for each hand is computed and looked up in the Type table, and Categ is given the appropriate table type corresponding to the match of item to the table.
The reason that `five-of-a-kind' is (temporarily, as you will see) assigned a type of 10 will be clear in a moment, but the next step involves checking to see if the original hand matches one of the legal patterns for straights that are stored in Str . If so, its Categ is bumped up by 4 . This codes straights (and straight flushes, at least for the moment) as 4 .
The next line of code looks only at the `suits' of the hands being evaluated. If the `number of suits' in a hand is 1 , then that hand is a flush, and its Categ is bumped up by 5 . This codes ordinary flushes as 5 , and straight flushes as 9 (they were previously already coded as straights). Now we reduce the r by one if it is more than eight. This converts the straight flushes (from 9 to 8 ) and the five-of-a-kinds (from 10 to 9 ). We made them 10 originally (and temporarily) so they wouldn't be confused with the (equally temporary) assignment of 9 to straight flushes.
At this point, we have a proper categorization of each hand. However, we still need to figure out a way to rank within category. Fortunately here we can rely on a simple property of the way we generated the characteristic vector. The each of vectors indicate the order of the elements involved in characterizing the hand. Thus the (up to) five rightmost elements, when reversed, represent a convenient ranking statistic. We will show this effect in a moment, but first, one more task needs to be done.
Our current ranking rules, if applied blindly, would mis-rank an A2345 straight. By the rules so far, an A2345 straight would be ranked right behind a TJQKA and ahead of a 9TJQK, because the A would be (incorrectly) regarded as a `high' card. The Fix function detects these straights explicitly and then artificially re-ranks them by marking them as five-high rather than ace-high.
Let's take a look at the ranking that is generated by the current rank program as given above:
Take a look at the `rank vector' for Hands[4] . (Hands[0] is the first.) This vector is 2 7 3 9 12 11 . The 2 signifies categorization of the hand as `two pair'. The next three numbers 7 3 9 indicate that the cards are a pair of `9's, a pair of `5's and a `J' (the seventh column, the third column and the ninth column tabulate 9s, 5s and Js, respectively). Note that this `ranking vector' has the appropriate properties: the 2 (indicating 2 pair) will cause it to be ranked higher than any 1 (one pair) or 0 (no pair) hand, while it will lose to any 3 (three-of-a-kind) or above. The first element will tie any other two pair, in which case the next element (7) will cause it to outrank any two pair hand that has a high pair coded with a 6, 5, ..., 0 (8 thru 2). It will lose to a high pair coded with 8 ... 12 (T thru A). If two of the high two pair hands both have high pairs coded with a 7, the 3 the comes into play in a similar fashion, etc.
Trying a Simulation
Now that we have a way of categorizing hands, let's try a simulation. To make this easy we define a few functions:
It is easy to check these tabulation (and display) functions on our very limited test data set. Typing:
Running a simulation is easy. For example the code:
generates 10,000 hands and then tallies them. The result little window on the computer screen that indicates 4933 Nothings, 4296 One Pair, 489 Two Pair, 189 Three-of-a-kind, 45 Straights, 25 Flushes, 21 Full Houses, and two Four-of-a-kinds. No Straight Flushes or (obviously) Five-of-a-kind hands appear in the 10,000 simulated hands.
If we are curious, we can ask for the index of the `best' hand with:
indicating that 5469{ NewHands is the best of our 10,000. Asking for:
which would obviously make us very happy if we were dealt this hand in any real game.
We can also look at the worst hand, both to check our algorithms and to see just how bad a hand we might see if we played 10,000 hands.
indicates pretty miserable expectations. This is about as low as a hand can go, as if it were only `six-high' then it would be a straight (or something would be paired).
The next questions might focus on the efficiency of this formulation of the problem.
| Hands | Deal | Tabulate |
| 10000 | 0.66 sec | 0.77 sec |
| 20000 | 1.37 sec | 1.49 sec |
| 30000 | 2.04 sec | 2.25 sec |
| 40000 | 2.80 sec | 2.97 sec |
| 50000 | 3.46 sec | 3.79 sec |
| 60000 | 4.23 sec | 4.73 sec |
| 70000 | 4.95 sec | 5.49 sec |
| 80000 | 5.66 sec | 6.31 sec |
| 90000 | 6.43 sec | 7.08 sec |
| 100000 | 7.08 sec | 7.91 sec |
Examples of what you might want to study, and how to study it goes here.
| David Ness Date: 2001/07/11 0517 UTC |
 |