RetroChallenge April/May 2020: New Mahjong

I decided to take advantage of my son Charlie's newly minted Mathematics and Computer Science BSc from Dalhousie and the fact that he is trapped in the house because of Covid-19 to attempt to fix an old game of mine.  I made Mahjong many years ago, but all it did was throw the tiles into the traditional "turtle" format at random.  This meant that winning was a very rare occurrence.  Most computer versions of the game have an algorithm to ensure that there is at least one way to solve every puzzle from the beginning.  Then when you lose, you know it is because you somehow screwed up in removing the tiles.  This provides a much more rewarding play experience because you can typically play longer before running into dead ends and you know the puzzle is solvable (in principle).

I had vague ideas about how to implement such an algorithm, but they were really vague and all involved starting with a blank sheet and then placing pairs of tiles until the 3D turtle shape was built up of the stacked tiles.  So I set Charlie to the task of thinking about how to solve the problem of finding a solution. Next morning he presents me with the idea that it would be better to play the game forwards rather than backwards.  That is to say, start with the turtle populated somehow, have the computer play the game by removing sets of tiles randomly until none were left, then using that configuration.  He had a simple method worked out for mutating the values of the positions of tiles to map their "openness" or "closedness."  You can only remove a tile if it is free on one side, left or right, and not covered by a tile above.

Basically Charlie's method starts with a coding system for the original positions:

3-Win Graphic

1=open left and right

2=open left or right

3=not open left and right, but open above

4=not open left or right and above

5=not open left and right and above

Then whenever you remove a tile you subtract one from the positions left or right and 2 from the position below to adjust their values. Then just solve the puzzle forward using blank tiles. You randomly select two free tiles (<3 tiles) and assign them a pair of tiles (1-36), then "remove" as per above.  Repeat until you get to 0. If it runs into a block (which is relatively rare) where it can't find a final pair-- Restart. See lines 20-74 and 2000-2045: https://github.com/jggames/trs80mc10/blob/master/quicktype/Puzzle/Mahjong/NEWMAHJ12.TXT

I had done some research of my own and had come across a similar tip originally from the Stack Overflow coding site. Basically the author, Merlyn Morgan-Graham, suggested the same idea as Charlie, but he made it clear that what you do is start with a blank set of tiles in the turtle shape. He also provided insight into the problems you will face with this method, as occasionally you can end up with an odd number of tiles that are free (i.e. 1) and you will have to restart.  His estimates for how often this happened were very helpful and encouraging.

Long story short, we got the algorithm to work and the initial version timed to just under 2 minutes for program setup and algorithm completion. Obviously, it took a little longer if the algorithm hit an uneven completion and had to restart. Just running the algorithm (not including program initialization) timed to just over a minute, but in subsequent re-writes I think I have got this down to just under a minute.

Lots of data had to be stored, including a 3 dimensional array (15 X 9 X 5) to store all the initial position data and openness data. Other info was also required such as top tile, and the current height of each stack. We made use of many 144 element long 2-dimensional arrays to store pointers to the x, y and z of the valid positions and the current tile type in those positions. 144 represents the total number of tiles (i.e. 4 of the 36 types of tile, or two sets of every tile type). Processing these 2-dimensional arrays was great for speed, but we did have some difficulties moving back and forth between references to these lists and the 3-dimensional space with the info about each tiles' openness.

So I had to really streamline and pare down my initial routines for generating the unique low res tile set I had worked out for the original game. I was able to store all the tile info in strings and then just use MID$ to get to any particular tile I needed.  This was much better than my old version which stored tile detail in data statements and then constructed the strings in string memory.

I also added an undo feature that was lacking from the original, and since everything was pretty much stored in arrays already, a game save feature using the MC-10's CSAVE* command which allows you to easily save arrays to tape. Charlie's system of coding the open tile info also really sped up the searches for possible moves for the HELP/GAME OVER feature. In my old version every search required determining whether a tile was free by consulting its neighbours, instead of just storing this info permanently (and "mutate" the array every time you remove a tile as per Charlie's method).  The help feature simply presents the open tile pairs a set at a time.  If no such tiles exist, it presents the game over prompt.

So here's a video of me playing the new version:

As I mentioned, the algorithm has been speed up even further from this initial release. Here is a video of a speed test that indicates that even with initial program initialization you can be playing in just over a minute and a half:

Enjoy!  The game can be played here. Choose the "Play Our Original Micro Color Basic Games" option, then select "MAHJONG" from the Cassette menu and type RUN: