Let us continue this mini-series on the casual video games I like. Today I would like to talk about Mahjong. Mahjong is a matching-pair game which uses game tiles from a traditional Chinese game with the same name. The original Mahjong was a game for four players which was often played for the purpose of gambling – not unlike poker. The game we play on our computers should probably be called Mahjong Solitaire, because it is played by only one player. Because of its popularity and because it uses the same game tiles, Mahjong Solitaire in the West is currently called just Mahjong which may sometimes be confusing.

As with other solitaire games, I made my two versions of the game. The first Mahjong game I made was inspired by a popular Mahjong game, previously available free on the Internet which for some reason is no longer available. I tried to make visuals as similar to it as possible. And the effects are quite good, I think.

There are a number of interesting facts about Mahjong. Let’s say we want to find out whether the current deal is solvable or not. How many combinations of moves do we have to check? To calculate that we need to make a number of observations. The first observation is that the only way to get stuck is to remove the tiles of a particular category in a wrong order. Why is that?

The observation we can easily make is that once all four tiles of a certain category are available, we can remove all of them immediately without a fear that this is a mistake. This is quite obvious. Now let us assume that we have found out the correct pairing for each category. Is it possible to get stuck by removing the pairs in the wrong order? Assume that yes, indeed, it is possible and we got stuck. But, also by assumption, if we change the order of the moves we have made, we would not get stuck. But this is not possible, because in both orderings, we end up removing the same tiles. So, regardless of the order, the final outcome is the same, the pile we obtain after removing certain pairs is always the same no matter in which order we remove these pairs. Thus, since it cannot be simultaneously stuck and not stuck, we infer that the order of removal does not matter.

It turns out that the only thing that matters is which of the four tiles we match within each category. Let’s number tiles in each category from 1 to 4. How can we match these tiles? We can match 1 with 2 and 3 with 4. We can match 1 with 3 and 2 with 4. And we can match 1 with 4 and 2 with 3. There are no other possibilities. So, for every category, there are three ways we can pair its tiles. Since there are 36 categories, there are altogether 3^{36} combinations. How much is that? It is 150,094,635,296,999,140. So, we have one hundred and fifty thousand trillion combinations to check if we want to know if a game is solvable. Unfortunately, it is not possible to run all of them on the computers we currently have. Maybe, if our computers were 1,000,000 faster, then finding out deterministically whether a Mahjong deal is solvable would be possible. Unless of course, somebody finds some algorithmic improvements which make it unnecessary to check all combinations. This may be possible although right now I am too lazy to think about it.

And so, I recently made my second Mahjong game, which is very similar to the first one. As I was making it, I found that there is a problem with translating “Tiles” into other languages. A tile in English is something rectangular which is used to cover surfaces, especially in bathrooms or kitchens or on roofs. And so, if a low-quality translator translates a Mahjong game from English, s/he just uses the equivalent of ‘tile’ in his/her language. But this is a mistake. Many languages – and checking Wikipedia’s Mahjong’s page confirms it – use word ‘stone’ to denote Mahjong game pieces. This is true in languages as diverse as Dutch, Polish, and Romanian.

Finally, as with Minesweeper, I wanted to give players an option to play games which are solvable. As you may know, some Mahjong deals are insolvable regardless of what you do. And so, I had to check which deals are solvable. But I did not check the thousands of trillions of combinations as described above. Instead, I just made the computer play every deal a number of times, every time using a different, randomized pairings. Then, I counted how many times a computer was able to solve the game. If the number was 0, then I treated the game as unsolvable. Of course, the game could still have been solvable – the computer just could have not found the correct pairings. But that did not matter – I wanted to have games which were proved to be solvable and false negatives were not really a problem. Moreover, the number of times the game was solved gave me an approximation for difficulty a human player could experience while playing a particular deal. And this is how I created various difficulty levels in my games.

Well, that’s it. I hope you found some valuable information here :)

## No comments:

## Post a Comment