Newsgroups: rec.games.abstract
Subject: Mahjongg
Summary: 
Expires: 
Sender: 
Followup-To: 
Distribution: 
Organization: Northern Illinois Univ., Dept. of Mathematical Sciences
Keywords: 
Cc: 


Yesterday I spent a few hours playing mahjongg for the first time in 
my life. (A couple of versions were included in my Linux distribution.)
Has anyone got pointers to an analysis of the game? -- How likely is
it that a random deal is winnable? (I can't imagine a closed-form
answer is known, but I think I can see how I would set up the data 
types to allow the computer to play on its own.) 
Has anyone tested rules of thumb for how to play and win?

For those who have never played, I attach a synopsis of the game
(as I understand it!)

dave


                            MAHJONGG

A solitaire game played with 144 tiles, (essentially) 4 of each of 36
designs [*]. Tiles are randomly permuted and placed into an particular
tableau (the arrangement is described below) which leaves a subset of
tiles visible and a subset of those available for play. A player's
turn consists of removing a pair of available tiles having matching
design; if this leaves no remaining tiles, the player wins, but
otherwise if no such pair exists, the player loses.

The tableau begins with all tiles face-up in an irregular pyramid. There are
12 tiles in one row. Centered under (next to) that are
8 tiles in another row, with
  6 tiles in a row resting centered on them. Similarly we next have
10 tiles in a row, with
  6 tiles in a row resting on them and
    4 tiles in a row resting on those. The next row has more layers:
12 tiles in a row, with
  6 tiles in a row resting on them, 
    4 tiles in a row resting on those, and then
      2 tiles atop the middle of _those_.
Four more rows continue in this fashion, forming a mirror image of the
tiles already lain. This leaves just four remaining tiles: one dead center
at the top of the pyramid, the others off the sides of the two long middle
rows (one spare on the left, say, and the other two on the right).

A tile is available for play if it is completely visible and is at an
end of its row. For example, the tiles available for play at the beginning
of the game are the one spare at the top, the two spares on the far sides, and
2+
2+
  2+
2+
  2+
    2+
0+
  2+
    2+
      0
tiles available in the top 4 rows, respectively, with another 16 similarly
available in the bottom 4 rows (Total: 35). I hope I tallied that correctly.

Apart from the task of scanning the tableau to spot matching tiles, the only
moment of player interaction is to decide which pair of matching tiles
to remove when there is more than one such pair available for play at once; 
this choice will affect which choices become available in future moves.

One can show that, once the tiles are shuffled and arrayed, the total
human input amounts to a choice of how to partition each set of four tiles
into pairs. Thus there are 36 selections to be made, each time with 
three possible outcomes: 3^36 (about 10^17) possible ways to play that
particular deal. However, since it is highly unlikely that all four tiles
of a given design will be showing at once, most of these decisions will
be more or less forced, so that the total number of possible ways to play
a particular deal will be much much smaller. (I don't know how much
smaller but I'm confident the entire decision tree can be stored in
a machine in most deals.)

For heuristics: it is clear that those four spare tiles block quite a few
others, so there is value to removing them quickly. The tiles which are
not on a bottom row are blocking view of others and so there is information
value gained by removing them soon; on the other hand, there is the
value of having more options at any one time, gained by _not_ eliminating
any row (whether on the bottom or otherwise). When only _pairs_ of matching 
tiles remain, a configuration such as  A B A B  in one row will be unwinnable;
to avoid this and similar pitfalls, it is desirable to keep rows short.
In practice I make great use of the ability to see tiles which are not
yet available for play; I'm not sure how to incorporate that information
into patterns for decision-making which would be of any real use.


[*] The designs seem to be in four suits of nine, but 
that's irrelevant for play. These designs seem to be nearly the same
in the various versions I have seen. There is a quirk with two of
the sets of four: in each set there is in fact not a single design but
rather a _theme_ (flowers, say); the four tiles with this theme are
declared to match. Must be some historical tradition; in any event, 
the play proceeds as if there were indeed 36 sets of four matching designs.