Shuffling a deck of cards (or other things) in CLIPS

This is another quick post (I’m working/procrastinating on some longer ones), but I couldn’t find a single place in the Internet that had this content already, so I think it’s important to write it!

I’ve been learning and playing with CLIPS as a rules engine for board games, and they usually require at least one deck of cards (or similar items) to be shuffled. CLIPS’s (random) function is “bad” (according to the docs, it’s based on ANSI C’s rand()) and the only way to seed it is with a (seed) function that takes a 64-bit integer, which is also bad depending on how many things you need to shuffle (read this if you want to understand why these things are bad for shuffling cards!).

Because of this, I thought I’d have to implement the whole shuffling outside CLIPS (in whatever program is wrapping the CLIPS environment) and I’d just assert the shuffled deck back into CLIPS, but I learned that user-defined functions can override system functions, so it’s possible to write my own (random) and (seed) and other seeding functions, and just do the shuffling inside CLIPS! I think this is a better approach, because it keeps the wrapper program simpler, and allows the CLIPS code to shuffle whatever it wants instead of having to rely on the wrapper program to know what to shuffle (which means it needs to know what to assert back into CLIPS). With this, we can shuffle decks of cards, a bunch of tokens, piles of modifiers, and whatever else needs to be shuffled as part of setting up and playing a game!

So here’s how to shuffle a deck of cards (or other things) in CLIPS! First of all, read this to understand the issues with CLIPS’s current (random) and (seed) functions, and why you should probably introduce your own user-defined functions for those.

I’m assuming the deck of cards is something like this:

(deftemplate deck
    (multislot cards)
    )

(note¹ on the formatting of my code)

It doesn’t matter what each card is. Usually I just assert each card as its own fact (this is very handy for many things), and the cards in the deck is actually a multifield of facts. Here’s how I initialise the deck (the cards deftemplate isn’t shown here because it’s pretty obvious):

(deffacts starting-deck
    (deck (cards
        (assert (card (number 1)))
        (assert (card (number 2)))
        (assert (card (number 3)))
        (assert (card (number 4)))
        (assert (card (number 5)))
        (assert (card (number 6)))
        (assert (card (number 7)))
        (assert (card (number 8)))
        (assert (card (number 9)))
        (assert (card (number 10)))
        ))
    )

And with that, I shuffle by introducing an “internal action”, which is a template created to drive rules to do certain things internal to the rules of the game:

(deftemplate internal-action
    (multislot action)
    )

(defrule start-shuffle-deck
    =>
    (bind ?deck-fact (nth$ 1 (find-fact ((?deck deck)) TRUE)))
    (bind ?deck-size (length$ (fact-slot-value ?deck-fact cards)))
    (assert (internal-action (action shuffle-deck ?deck-size)))
    )

The reason why start-shuffle-deck has to find the deck fact in the right-hand side of the rule is to guarantee that this rule will only fire once at the beginning of the program (because most decks have to be shuffled before the game starts). Thinking about it, in some games I could definitely improve this by asserting a simple fact at the beginning of the program:

(deffacts initial-deck-shuffle
    (internal-action (action shuffle-deck 10))
    )

Because the deck size is usually fixed. Certain games include different cards depending on the number of players or other things like that, so usually a static fact won’t help much. In these cases, the start-shuffle-deck rule can be used to dynamically determine the deck size and start a shuffle.

Anyway, here’s how the shuffle actually happens:

(defrule shuffle-deck
    ?cmd <- (internal-action (action shuffle-deck ?curr-index&:(> ?curr-index 1)))
    ?deck <- (deck (cards $?cards&:(> (length$ $?cards) 0)))
    =>
    (retract ?cmd)

    (bind ?picked-index (random 1 ?curr-index))
    ; Slight optimisation to avoid shuffling an item in the same place.
    (if (<> ?picked-index ?curr-index)
        then
        (bind ?picked-item (nth$ ?picked-index ?cards))
        (bind ?new-deck
            (replace$ ?cards ?picked-index ?picked-index (nth$ ?curr-index ?cards))
            )
        (bind ?new-deck
            (replace$ ?new-deck ?curr-index ?curr-index ?picked-item)
            )
        (modify ?deck (cards ?new-deck))
        )

    (if (> ?curr-index 2)
        then
        (assert (internal-action (action shuffle-deck (- ?curr-index 1))))
        else
        (assert (shuffle-deck-done))
        )
    )

; Here just in case, but should never be triggered.
(defrule shuffle-deck-bad-index
    ?cmd <- (internal-action (action shuffle-deck ?curr-index&:(< ?curr-index 2)))
    =>
    (println "Internal action of 'shuffle-deck' was generated with bad index " ?curr-index)
    (retract ?cmd)
    )

This is my CLIPS version of the Fisher-Yates shuffle. Remember that it’s very important that the (random) function is properly seeded and that its implementation does not display modulo bias or any other kind of bias (you ARE overriding the system (random) function, right?). For the last time, I’ll link you to this article so you can understand why this is important.

As a last thing, this CLIPS code for shuffling ends up asserting a (shuffle-deck-done) fact once it’s done. I found this to be a neat trick to sequence certain actions (e.g. we have to shuffle a deck before dealing cards to players) without having to rely on the salience of rules. As an illustration, here’s the left-hand side of the rule that deals cards to players as a setup of the game:

(defrule deal-cards
    (player-count-done)
    (shuffle-deck-done)
    (player (name ?pn))
    (not (hand-card (player-name ?pn)))
    ?d <- (deck (cards $?deck))
    =>
    ...
    )

You can see I also use this trick to do a count of how many players are in the game dynamically (although thinking about it again, I probably could’ve done this when the wrapper program asserts the players as well). I’m still learning how to best organise these logical blocks of rules. I’m using modules for some things, but in some cases I still want to sequence actions without having to break things into a lot of modules each with 1 or 2 rules inside them, so this trick has been helpful!