By Howard Katz
MacTech Quarterly
Spring 1989 – Page 28
During my last year of high school, I was initiated into the mysteries of male bonding and five-card stud by a older bachelor who resided on the second floor of the apartment building where I lived. I was seventeen, and for the most part, yes, it was a very good year. The fellow was a cab driver, and way back then the word “hack” had only one meaning. I still think fondly of this fellow, primarily for a little game of solitaire he introduced into my life.
I’ve never seen this game anywhere else, and indeed I don’t even know its name. All I know is that it has given me many hours of pleasure over the years as I’ve played it on and off. For the sake of this discussion, I’ll call it simply “Two-Match” for reasons that should soon be obvious. And now, in the finest traditions of our oral heritage, I’ll pass it on to you.
For it strikes me that this minor little diversion, in addition to being pleasurable in its own right, raises a number of interesting programming issues. What is even better, it also serves as a lovely little vehicle for talking about some of the rudiments of the art of object-oriented programming. And that (and not my boyhood reminiscences, no matter what you thought!) is really what this column is all about.
What I want to do with Two-Match, specifically, is to spend some time looking at the game, develop the outlines of a traditional approach to designing a program to play it, and finally recast the whole works into an object-oriented framework. The latter task will take more than one column to accomplish, but we’ll start the process in this installment.
The game itself is wondrously simple: you start with a facedown deck of cards in one hand and end up with a maximum of eight piles of cards on the table in front of you. If you finish up with no cards in your hand, you’ve won. If you end up with eight piles on the table, no further playable cards, and you haven’t exhausted the deck, you’ve lost. Figure 1 shows a typical game in progress after we’ve played three cards.
So what constitutes a playable card? Per Brinch Hansen has a wonderful quote in his book, The Architecture of Concurrent Programs: “Programming is the art of writing essays in crystal clear prose and making them executable.” Taking that as either an injunction or a challenge, I’ll present the rules for Two-Match in algorithmic form. Accordingly, here’s a little composition written in good old, classical Pascal:
while stillAlive do
if PairShowing(pile_1, pile_2) then
begin
stillAlive := DrawTwoCards(card_1,
card_2);
if stillAlive then
CoverTwoPiles(pile_1, pile_2,
card_1, card_2)
end
else
if DrawCard(card) then
stillAlive := StartNewPile(
numPiles + 1, card)This simply says: before each draw, look at the cards in front of you. If there’s a pair showing on the table, draw two cards and cover them both. If you can’t draw two cards because you’ve exhausted the deck, you’ve won. If there’s no pair showing on the table, draw one card and start a new pile. If you can’t start a new pile because you’ve already got eight showing, you’ve lost. That’s it!
Figure 1 shows the state of the game after we’ve started pile number three. We’ve paired up on fives and accordingly will draw two cards and cover them both. Another pair might occur during this covering process if one of our two new draws happens to be a queen. If both new cards are queens, we have to choose which two of the three piles to cover. (I have no idea what happens if our rules allow all three to be covered, except to suggest that we might call this variation of our basic game “Three Match.”)
In the finest Olympic spirit, the boolean flag
stillAlive does not indicate whether we’ve won or lost, only that we’ve played the game. We would have to look at the contents of another variable,
numCardsRemaining, to tell us which was the case: we’ve won if numCardsRemaining is 0. Not surprisingly, it starts out life with a value of 52. stillAlive and numCardsRemaining are only two of the thirteen globals that are used in this version of our game. All in all, we have the following declarations. The meaning of most of these should be self-evident.
card, card_1, card_2 : CardValue; { 1 .. 13 }
numCardsRemaining : integer;
pile_1, pile_2 : PileNumber;
stillAlive : boolean;
numPiles :integer;
gameNum : integer;
numWins, numLosses : integer;
deck : array[1..maxCards] of CardValue;
pile : array[PileNumber] of CardValue;There are only three functions and two procedures in our main loop (and in C, I wouldn’t even have to make that distinction!). The arguments for the functions PairShowing, DrawTwoCards, and DrawCard are obviously passed by reference; in Pascal, the formal declaration for PairShowing, for example, appears as follows:
function PairShowing(
var pile_1, pile_2: PileNumber ): Boolean;where PileNumber is declared as a rangetype of 0 .. 8 (we start with zero, obviously, because no piles are showing when we begin a new game). The function PairShowing would scan through all the piles on the table and return a function result of true for the game in progress in Figure 1. It would also return values of 1 and 3 for the arguments pile_1 and pile_2, respectively.
Let me just say that even such a seemingly trivial exercise in the art of programming design seems to permit of fascinatingly endless possibilities and permutations. I’ll simply note that my first attempt at Two-Match looked nothing like the above. As pleased as I was with that design initially — it “felt efficient” and took slightly less code than the above — it was far less intuitive at first glance, and for that reason I discarded it.
The game also raises fascinating questions about what is and is not tractable to an analytical solution. To wit: over the years, I have noticed that I’ve won, on the average, about one in every twenty-five games that I’ve played. My question is simply this: “Is there a way of deriving this probability analytically?”
Without going into it in any depth, I’ll simply abdicate the question with a probable “No” and leave this matter to others far better versed in this type of algorithmic analysis than I. If you’re at all curious about this matter, simply consider that you can both win and lose Two-Match in a very large number of ways. (And for what it’s worth, a seedy-looking academic type just slunk by, mumbling out of the corner of his mouth, “Psst, psst. Random graphs! Traveling Salesman!”)
However, I do claim that at least one of those ways of losing is easily tractable to combinatorial analysis. Specifically, I claim that the probability of losing Two-Match in eight straight cards is very, very close to 10.55%. (And indeed, this answer must be correct: my Macintosh tells me so!) I’ll leave the derivation of this result as an exercise for those of you whose days are not spent in pursuit of more meaningful goals.
However, even if I’m unable to come up with an analytical probability for the winning case, I can at least — admittedly in a somewhat brutish fashion — force my Mac to play game after endless game in search of a statistical solution. And that is exactly what I did: my machine ran for several nights in succession, playing sessions of 25,000 games each as I went off in search of the ideal statistic. I collected stats both on the number of games lost in 8 straight deals and won in 52. The start of a typical session produced the following WriteLn record:
| 1 | : 34 |
| 2 | : 14 |
| 3 | : 8 LOSS 1 |
| 4 | : 8 LOSS 2 |
| 5 | : 12 |
| 6 | : 12 |
| 7 | : 22 |
| 8 | : 10 |
| 9 | : 8 LOSS 3 |
| 10 | : 10 |
| 11 | : 8 LOSS 4 |
| 12 | : 22 |
| 13 | : 52 WIN ** 1 |
In the first thirteen games of this session, I won once and lost four times. To be more accurate, I actually lost twelve times, but I was really only interested in the case of lose-in-8-straight, to see how this compared with my theoretical calculation.
Sessions only varied in the number of times that I shuffled the deck at the start of each game, and this number was a constant for each session. Each game, in turn, only varied in the initial value for randSeed — which was carried forward from the prior game, except for the first game in each session which started with QuickDraw’s initial default value of 1 so that runs would be reproducible. Three sessions of 200, 400, and 800 shuffles, respectively, produced the following results:
| shuffles | 200 | 400 | 800 |
| p (lose in 8) | 11.040% | 11.224 | 11.672 |
| p (win in 52) | 5.404% | 5.104 | 6.800 |
The probabilities of losing in eight straight cards are slightly higher than my predicted figure of 10.55%. The probabilities of winning, ranging from 5.4% to 6.8%, are also somewhat higher than my own experience would have suggested. Given the nature of random-number generators and this type of simulation in general, I don’t think we should have any problem with these figures. With that said, we move on to what I promised earlier — an object-oriented recast of the same problem.
In our traditional approach to programming the game of Two-Match, we contrived a disparate collection of global data structures loosely stitched together in a runtime framework of Pascal procedures and functions. In an object-oriented approach, we’ll look for a more meaningful redistribution of these fundamental programming structures.
To make this transition, we have to stand back and take a fresh, new look at the entities that comprise our problem world. In the case of Two-Match, it’s fairly easy — we notice two things right off the bat: a deck of playing cards in our hand and several piles of cards on the table in front of us. We recognize, in other words, the simple fact that the Two-Match world contains two types of objects: decks and piles. This is indeed a promising start!
What we’re doing really is nothing more than redefining what we have to look at when we analyze a problem from an OOP perspective. In one sense, it’s very strange: we have to forget much of the art that we’ve learned so painfully, in terms of parsing our world into the artificial constructs of data structures, functions and procedures held together with a bit of syntactic sugar (or molasses, if our code runs slow!). Instead, we move backward toward a view of the world that is much more in accord with the natural way we’ve learned to look at it all our lives!
This resonance, this very nearly one-to-one correspondence between the natural granularity of the real world and the new unit of modularity we introduce in an object-oriented application, is for me the singularly most exciting thing about this new way of doing business. Others may choose to stress such wondrous concepts as inheritance, extensibility, and polymorphism (for which you can still be arrested in Alabama, by the way, even between consenting adults!) — and indeed we’ll look at all of these concepts in future columns — but for me the wonderful efficacy of the OOP approach starts right here in the design stage, before we even put pen to paper, as it were.
Our exercise becomes slightly trickier when we realize that the word “object” can also be applied to other entities that are far less concrete and visible than decks and piles. In the case of Two-Match, we also want a “master” object, if you will, to regulate each game, collect and print statistics, and to act as traffic cop, keeping the activities of our various other objects in synchronization. This object represents the game itself, a far more abstract entity and one we can’t point to quite so readily with an outstretched finger. Whether you envision this particular object as a game, a round, or a hand is of no particular consequence, except that you should feel comfortable with whatever label you attach.
We visualize all these objects as having a real existence of their own at runtime, much as we conceptually visualize an existence for integer variables, records, and handled blocks on the heap during program execution. Figure 2 shows a snapshot of our Two-Match objects in the heap, at the same stage in our game shown in Figure 1.
Note that we are showing five separate objects here — but only three separate types of objects: hands, decks, and piles. These types are more formally known as ”classes” in the world of OOP; it’s a happy congruence that the word “type” occurs here, for in Object Pascal, a class is indeed defined via the standard Pascal type mechanism with which we’re all familiar. N’est ce pas?
An object, then, is simply nothing more than an old, familiar variable — albeit a new kind of variable, an object variable — of a particular type or class. In Figure 2, for example, the object variable aHand is of type THand, or alternatively, the object aHand is an instance of the class THand. We’ll see what a class definition (aka object type) looks like in a minute.
I spoke earlier about the redistribution of traditional programming structures that occurs when we move into an object-oriented framework. The object aDeck in Figure 2, for example, contains a slot for the variable fNumCardsRemaining. This variable is nothing more than our old global friend numCardsRemaining, slightly renamed, constrained to a new scope, and relocated to where he (or she!) properly belongs.
Why do I say that? Because the knowledge that 49 cards remain in the deck after three plays is not really something we need know about on a global level. In point of fact, it’s only the deck object that needs to track this value in order to decide, on receiving a request to deal a new card, whether or not it can comply. What we’ve done, in other words, is to limit the scope of fNumCardsRemaining and make it local to our deck object. This is where it really belongs.
I spoke about class definitions. Here’s our class definition for TDeck, of which aDeck is one particular instance (and the only one we’ll have in any one game):
TDeck = object(TObject)
fDeck : array[1..kMaxCards] of CardValue;
fNumCardsRemaining : integer;
procedure TDeck.IDeck (
numShuffles: integer; maxCards: integer);
function TDeck.DrawCard (
var theCard : CardValue): boolean;
procedure TDeck.Shuffle;
end;Note the similarity of this structure to a standard Pascal record type. There’s our old friend fNumCardsRemaining, joined by the data structure fDeck which also led an earlier, happy existence as a global variable. In addition to encapsulating these two variables as data fields within our class definition, we’ve also added the two procedures and one function that only decks need know about.
Now that’s a miserable statement to leave you with, because I unfortunately have to stop — we’re running out of space. The only other point I want to make before we continue next time is that if all of this feels strange and awkward to you, try not to feel tremendously bad about it. On the one hand, consider: the author might be doing a very bad job!
On the other hand, this stuff is hard — it’s a new and strangely different way of looking at an old, familiar world. Some things are just plain hard to learn, as we painfully shift the way we think. The transition seems to be quite painful for some and laughably easy for others — though I’d say offhand that the former far outnumber the latter — and I don’t think that anyone has come up with a common denominator that makes it easy to predict which it’s going to be for you. I will note, if it makes you feel any better, that I definitely hail from the former camp.
So where do we go from here? Given the fact that I’m heavily involved with MacApp as the editor of “Frameworks,” the journal of the MacApp Developer’s Association, it’s perhaps not unnatural that I want to move toward a third version of our game, tied into a MacApp framework. We’ll continue our discussion of Two-Match in the next column, looking at some of the other concepts I’ve mentioned. We’ll also raise some interesting questions about efficiency. The implementations I’ve talked about here were done up in Lightspeed Pascal version 2.0, and I want to talk about other Object Pascal environments such as TML Pascal 2 and MPW. If that’s not enough to keep us busy, we can also port Two-Match to Smalltalk and C++! Is that enough for now?
The sources for Two-Match are available, if you’re curious, on a disk from the object library of the MacApp Developer’s Association, PO Box 23, Everett, Washington, USA 98206-0023. This disk will also be available through APDA (though I’m not sure if it’ll be listed by the time you read this).
If anything I’ve said bothers you, excites you, or you just want to tell me about the amazing version of Two-Match that you’ve developed (may a thousand programs bloom!), give me a call. I’m available on AppleLink as X0591, by telephone at (604) 738-0313, and via earth mail at 2074 McNicoll Avenue, Vancouver, BC, CANADA V6J 1A8. Just be aware: if you call and leave a message on my machine because I’m out, I’ll probably call you back collect. OK? I would love to talk to you.
I’ll close with one short thought and it’s this: if you are not taking the subject of object-oriented programming seriously — for whatever reason — you are doing a grave disservice to your craft, your career, and your creativity. Find your information somewhere else if you like — I won’t be upset — but check it out! Think about it. Do yourself a favor.
Good night, Mrs. Calabash, wherever you are.
