(2024-01-22) Let's play some cards... in POSIX AWK -------------------------------------------------- Oh yeah. Some windozed morons kept saying something like "Linux has no games" for a long time, and it was never true. But what about "BusyBox has no games"? Technically, that is true: if the system solely has a single BusyBox binary in addition to the kernel, there are no games built into it. However, it does have an AWK interpreter (unless specifically built without it), and that is just enough to game on. Yes, some time ago I did create VTL-2, CHIP-8, Subleq16 and TinyChoice engine ports in AWK that could run in the BusyBox version as well, but what about "native" AWK-based games? Are there any at all? Well, it turned out that if we stay on the standard side of things and exclude all gawk-specific shenanigans like Awkventure or Awkaster, then we cannot find anything particularly interesting. Of course we could write some interactive fiction (again, say hello to TinyChoice), text-based sims like Lunar Lander or challenge-response games like Bulls and Cows pretty easily, but all that stuff is something quite trivial to implement in any programming language and can get boring pretty quickly. And I totally did understand why that's the case: AWK isn't really suited for anything other than line-based I/O. But I really wanted to influence the situation. At this point, I basically had three choices: 1) write my own roguelike game being a simpler and standard-compliant alternative to Awkventure, 2) write a port of Text Elite by Ian Bell ([1]) in addition to already existing JS, Python, Go and even Erlang ports, 3) write something no one had thought of porting to such a language before. Recently, I also have rediscovered the FreeCell solitaire game and started learning its history and quirks, so that kinda hugely helped me to lean towards the choice number 3. Maybe, I'll do a Text Elite port a bit later, who knows. So, enter FreeCell. Despite being first popularized by M$, it still is an awesome game by itself, and, in order to fully appreciate its awesomeness, I recommend you to read a long but comprehensive article at Solitaire Laboratory ([2]). To me, the most appealing part in comparison to most other patience/solitaire card games is randomness has almost no influence on the outcome and almost all deals are solvable (I think that eight impossible deals out of a million is a pretty good indication). How easily each of them is solvable is another story. Interestingly enough, there still is no mathematically proven method to detect whether a FreeCell deal is solvable or not, all the stats were found by human players and computer bruteforce simulations. In case you still don't know what this game is about, I could direct you to a tutorial on that Solitaire Laboratory website, but let's recap the basic FreeCell rules right here. 1. The game starts with four empty freecells (traditionally in the top left) and four empty homecells aka foundations (traditionally in the top right). Below (or in between) them, all 52 cards (if your deck has jokers, they are not used) are dealt in 8 columns (aka tableaus) in the random order. The cards are dealt horizontally though in rows that contain 8 cards each. So, each of the first four columns will contain 7 cards and each of the next four columns will contain 6 cards. 2. The last card in the column (or an existing card in any freecell) can be moved to a freecell. Only one card can be put into a freecell at a time. If the freecell is occupied by another card, you cannot put a new card there. 3. The last card from a column or a card from a freecell can be moved onto the homecell/foundation using the following rule: aces go to any empty foundations, deuces go onto the aces of the same suit, threes go onto the deuces of the same suit, and so on up to the kings. Once in a homecell, the card cannot be moved anywhere else anymore. 4. The last card from a column or a card from a freecell can be moved onto the end of another column if and only if the current last card in that column is a rank higher and of the opposite color. E.g. a ten of spades can be appended to the column that ends with a jack of hearts or diamonds, but not to the one that ends with a jack of clubs or spades. If the column is empty, any card can be moved onto it from a freecell or from the end of another column. 5. Technically, only one card can be moved across columns. However, almost all FreeCell implementations account for the amount of freecells and empty columns to allow so-called supermoves. So, if you have a column ending with a valid stack of cards (alternating colors and decreasing ranks), the maximum amount of cards in the stack you're allowed to move at once is determined by the formula (2^M) * (N + 1), where M is the amount of empty columns and N is the amount of empty freecells. 6. The goal of the game is to move all 52 cards to the homecells/foundations using the above rules. Sounds simple enough, right? Well, I thought so too. And started coding it up in AWK. And quickly realized it wasn't as easy as I thought. The first challenge arose right away: how to represent the playfield and how to render it. For the columns that have variable lengths, we cannot have a "normal" array, and the POSIX standard AWK doesn't have true multidimensional arrays either, only their associative emulation. Well, that's what I had to use anyway. For column rendering, I still had to assume the maximum amount of cards that a column could theoretically contain: imagine e.g. an untouched column 1 that ends with a king — that's 7 cards, and then we can stack everything from queen to ace, but in practice an ace would never end up there — that's 11 more. So, maximum column capacity is 18 cards, this is our virtual second array dimension. In fact, my rendering method "draws" 20 rows into a string but then strips all trailing whitespace from the result. Due to the specifics of AWK's "multidimensionality", I also had to keep track of the column lengths in a separate array and update it accordingly on every move to keep things efficient. Another challenge was a part of the mechanics that never got into any official FreeCell ruleset but all existing implementations employ it: autohome aka autoplay. The simplest variant of it means automatically putting cards into the homecells/foundations as soon as there is a possibility to do so. Unfortunately, this means that one cannot reuse lower-ranked cards to give place to some even lower-ranked cards if there's a need, and that rules out some deals that can only be solved with this. So, I settled on implementing what's called "safe autoplay" and being used in M$ FreeCell, FreeCell Pro and, I believe, Aisleriot I play on my Arch as well. Quoting from the Solitaire Laboratory: "Microsoft FreeCell or FreeCell Pro only plays an available card to its homecell automatically when all of the lower-ranked cards of the opposite color are already on the homecells (except that a two is played if the corresponding ace is on its homecell); aces are always played when available." On top of that, what most implementations use but no one mentions is the emulation of M$ FreeCell deal PRNG algorithm. It's a simple LCG modulo 2^31, nothing fancy. But what also matters is the initial deck layout before running this algorithm. This is the reason I had to change the suit order to clubs-diamonds-hearts-spades instead of something more convenient for internal representation and color detection. Why is all this important and we cannot just use a standard AWK's rand()? Well, we can but then we wouldn't be able to reproduce some famous deals that are known by their seeds ("game numbers") on teh interwebz and beyond. This is where I agreed to make the code more complex for the benefit of being able to unify the deal numbering. The biggest challenge though, and that's also related to unification and text-based UI simplification, was to implement correct column-to-column stack movement that would allow to get rid of explicit stack length specification in the second parameter and also to support the "standard notation" accepted on a lot of FreeCell-related websites and programs. This involved some heuristics I had to change several times for it to work correctly, but when it worked, I even added the "h" letter as the third option to use when moving a card to the foundation, i.e. 4, 40, and 4h all mean "move the last card from column 4 to the foundation". This was done because "*h" form is a part of that "standard" notation to move a card to its homecell. Right now, of course, you still have to press Enter/Return after entering each move, but, other than that, you can easily convert notation files to the command sequence. The resulting piece of code I named nnfc ("no-nonsense FreeCell", of course), with all its features, still is under 300 SLOC of pure POSIX AWK. And I wrote it all on my tty-driven Alpine on that old A1370, in busybox vi. Wanna know how it all turned out? Well, you can clone my repo and see for yourselves: git clone git://git.luxferre.top/nnfc.git Make sure to read the README file to know how to run the game with the options you need. For instance, on my Kindle, Kterm supports UTF-8 but doesn't support colors, so I run it as awk -f nnfc.awk -v MONOCHROME=1 and it displays all cards with a single color. So, here you are, my newly favorite card game is now playable on BusyBox-based systems, as well as anything else that can run AWK scripts within the current standard. I hope I have made at least some contribution to the AWK gaming scene with this humble entry. And no, I wasn't joking about porting Text Elite to POSIX AWK. I'm seriously considering it. --- Luxferre --- [1]: http://www.elitehomepage.org/text/index.htm [2]: https://www.solitairelaboratory.com/fcfaq.html