Friday, 22 May 2020

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:

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:

Monday, 4 May 2020

RetroChallenge April/May 2020: Golden Flutes and Great Escapes

I've ported the code of a game for the TRS-80 Model 1/3 from the Book Golden Flutes and Great Escapes: How to Write Adventure Games by Delton T. Horn. The game "The Golden Flute" is a simple adventure game with CRPG elements. The action takes place on a 10 X 10 grid. I added a nifty title screen graphic of  some of the members of the whimsical party of adventurers in the game.

I've also been engaged in some other hi-jinks. The winner of this year's Type-in Mania cup was Darren Ottery of Australia. Darren wrote a prominent early game in the MC-10 community, "Micomania." I remember playing this game as one of my first programs obtained through the Internet. Darren played it recently and posted a video of it online, because he couldn't get my game Miner running on MCX.  So I fixed Miner to work on the MCX and then I tried Micomania again myself just for the nostalgia of it. Well, I couldn't resist trying some of my speedup techniques on it. This morphed into making a better tracking algorithm for the enemy. Finally I did a little graphic editing using SKETCH to spiff-up the title page. In the end I sent it to Darren and he made a few more edits including putting me on the title page, which led to "Micomania 2."

Finally I have worked on some programs from a book for the Dick SMith VZ-200 computer, VZ200 Giant Book of Games by Tim Hartnell. One of the games I have got running on the MC-10 and (hopefully) fully debugged is "Rural Pursuits." Another one I am working on currently is "Chairman of the Board."

Rural Pursuits
There are just so many type-in programs out there it is hard to figure out which one to work on next. Some other folks have also been getting into the Basic program business. I was made aware of the Hartnell VZ-stuff by Mike Hawkey and David Maunder, who are trying to get the programs running on the VZ-200. Fabrizio Caruso posted a completely new puzzle game (with some arcade elements) in the MC-10 Facebook called "Mines Plus."  It's for next year's 10 liner, but although a small program, it is very addictive.  Curtis F. Kaylor posted a math skills game for kids on the MC-10 called "MathCom."  Darren Ottery added to MMania with TypeAttk, which is a typing skills testing program (made even more challenging on a real MC-10 I'm sure).  I have added these folks programs to the "Programmers" directory in my distro of the VMC10 Emulator.

Chairman of the Board by Tim Hartnell