4

I'm looking for an algorithm that will determine if the current mahjong hand is a winning one. If you are not familiar with the game, here's the basic idea (simplified):

  • There are three suits of tiles, each containing tiles ranked 1-9. There are also special tiles, seven types of them. Each tile exists in four copies, so there are 36 tiles of each suit and 28 special tiles.
  • A hand has 14 tiles in it.
  • A chow is a set of three tiles of a single suit with consecutive ranks.
  • A pong is a set of three identical tiles.
  • A kong is a set of four identical tiles.
  • A pair is a set of two identical tiles.
  • A winning hand is one in which the tiles form any number of chows, pongs, and/or kongs and one pair.

The hand is sorted by suit and then by rank. My idea is something like this:

  1. Mark all tiles as unvisited and nonwinning.
  2. Visit first unvisited tile.
  3. Check subsequent tiles until a chow, pong, or a kong is encountered, or until there is no possibility of it. If a combination is completed, mark all participating tiles as visited and winning
  4. If all tiles have been visited, check if all of them are winning. If not all tiles have been visited, go to 2.

The problem is that once a tile is a part of a combination is cannot be a member of any other combination, one that might make the hand a winning one.

Any ideas for a working algorithm?

AbyxDev
  • 1,363
  • 16
  • 30
Igor
  • 2,673
  • 5
  • 33
  • 39
  • pong and kong are the same thing? You've said they're both "a set of three identical tiles" – Marc B Feb 08 '11 at 20:08
  • If a winning hand must contain a pair you can narrow the search space considerably by selecting each possible pair and seeing if the rest makes chow/pong/kong (as opposed to grouping the hand and seeing if the groups happen to have a pair). – Ben Jackson Feb 08 '11 at 20:21
  • 1
    The algorithm in this [anser](http://stackoverflow.com/questions/4154960/algorithm-to-find-streets-and-same-kind-in-a-hand/4155177#4155177) finds a valid hand. – Christian Ammer Feb 08 '11 at 20:57

1 Answers1

2

Your algorithm is just fine if you embedded it into a backtracking algorithm (http://en.wikipedia.org/wiki/Backtracking). The easiest way to do it is to call your method recursively once you found a matching pair/chow/... but discard current choice it if not. In pseudo code this looks something like this:

1. Mark all tiles as nonwinning
2. Call function Backtracking

Function Backtracking:
1. If all tiles are marked winning return WINNING else NONWINNING
2. Visit tiles as described in your algorithm
3. When found a chow/pong/... or the first pair    
   3.1. Mark those tiles as winning.     
   3.2. Afterwards call method Backtracking.    
   3.3. If return value of 3.2 is WINNING also return WINNING    
   3.4. Else unmark the tiles as nonwinning again    
4. If not finished search for pair/chow/... by looping to 3.
5. All combinations are done and no winning movewas found so return NONWINNING

The idea behind is that you first try each pair/... as part of a winning hand but if this does not work just try the same by assuming it is not part of the winning hand.

If you are not only interested if it is a winning hand but all possible combinations of winning pairs/chows/... skip the return in step 3.3.

Howard
  • 38,639
  • 9
  • 64
  • 83