In the previous post I described the process of reading a rulebook for the first time: you read up to page 10, where it says “oh and if a blue piece captures a red piece then advance the morale track.” Before reaching that page you already had a game in your head, and now you need to add one more rule and you obtain a new, slightly larger game. I wanted a software engine where that is reflected in the architecture. In this post I’ll explain RulePages and the operations that combine them into a game. The main outermost operation, the one you apply in your brain after you’ve finished reading all the rules, is called oapply after the operad-algebra constructor of the same name in AlgebraicDynamics.jl. But we’ll see another operation too!
GameRule and RulePage
A page owns two things: a set of offered actions, and a way to reduce the actions it offered by applying that action to the state. An offer, called a GameRule, is a pair: a condition (predicate) and a list of actions. When the condition holds on some state, the page offers those actions, e.g. “if it’s your turn, you can play cards A, B, or C.”
struct GameRule<State, Action> {
let condition: (State) -> Bool
let actions: (State) -> [Action]
}
RulePage bundles a list of these with a reducer. The reducer is partial: given an action, it either handles it (mutating state, returning logs and follow-up actions) or returns nil if it doesn’t handle that action.
struct RulePage<State, Action: Hashable> {
let name: String
let rules: [GameRule<State, Action>]
let reduce: (inout State, Action) -> ([Log], [Action])?
}
How RulePages compose
A game is a list of RulePages and is called a ComposedGame. To collect the legal actions in a state, take the union over what every page offers:
func getLegalActions(state: State) -> [Action] {
pages.flatMap { page in
page.rules.flatMap { rule in
rule.condition(state) ? rule.actions(state) : []
}
}
}
To apply an action, offer it to every page. (We require that exactly one page claims it: each action’s enum case has a single owner, so at most one reducer returns non-nil. The loop below early-exits as an optimization):
func reduce(into state: inout State, action: Action) -> [Log] {
for page in pages {
if let (logs, followUps) = page.reduce(&state, action) {
return logs + followUps.flatMap { reduce(into: &state, action: $0) }
}
}
return []
}
Let me mention a couple of extensions that ComposedGame supports.
- A reducer may return follow-up actions: Hearts scores a hand by having the action that ends the trick emit
.scoreHand, which the scoring page handles. - A priority rule fires instead of the one that would normally claim an action: e.g. a victory check,
.claimVictory, pre-empts ordinary play the moment the game is won. - AutoRules are logical entailments of the state, they read it directly and apply consequences with no action involved: noticing that hearts were played this trick causes a “hearts broken” flag to be set.
Presumably these extensions are equivalent to a purer framework that has extra state to orchestrate these additional actions and the ordering. The north star of this design is to think like a game designer or a player learning the game, and I do feel these extensions are intuitive.
Hearts
Hearts demonstrates the way games decompose. First of all, it has a simple trick-taking core: four players follow the suit that was led. We can add the rest one piece at a time.
Page one: play a card. On your turn, before the trick is full, you may play any card in your hand.
static var playPage: RulePage<State, Action> {
RulePage(
name: "Play",
rules: [GameRule(
condition: { $0.phase == .playing && $0.currentTrick.count < 4 },
actions: { state in (state.hands[state.player] ?? []).map { .playCard($0) } }
)],
reduce: { state, action in
guard case .playCard(let card) = action else { return nil }
state.hands[state.player]?.removeAll { $0 == card }
state.currentTrick.append(TrickPlay(seat: state.player, card: card))
state.player = state.player.next
return ([Log(msg: "\(state.player) plays \(card)")], [])
}
)
}
This already runs: four players take turns dumping cards into a pile.
Follow the suit that was led. The first real rule narrows the offer. Replace the permissive actions with legalPlays, which is just a filter on the hand:
var legalPlays: [Card] {
guard let hand = hands[player] else { return [] }
return currentTrick.isEmpty ? legalLeads(hand) : legalFollows(hand)
}
func legalFollows(_ hand: [Card]) -> [Card] {
let led = currentTrick[0].card.suit
let inSuit = hand.filter { $0.suit == led }
return inSuit.isEmpty ? hand : inSuit // must follow if you can
}
Note what did not change: the reducer.
Resolve the trick. A new page that owns one new action. It offers .resolveTrick exactly when the trick is full, awards the cards to the highest card of the led suit, and makes that seat lead next.
static var trickPage: RulePage<State, Action> {
RulePage(
name: "Trick",
rules: [GameRule(
condition: { $0.currentTrick.count == 4 },
actions: { _ in [.resolveTrick] }
)],
reduce: { state, action in
guard case .resolveTrick = action else { return nil }
let winner = state.trickWinner!
state.award(state.currentTrick, to: winner)
state.currentTrick.removeAll()
state.player = winner
return ([Log(msg: "\(winner) takes the trick")], [])
}
)
}
Score the hand. Another page owning another action, .scoreHand: count one point per heart, thirteen for the queen of spades. Append it after the play and trick pages.
Now stop reading. With three pages plus scoring you have a playable game of Hearts.
Add the passing phase. Hearts opens with each player passing three cards. This is a whole new phase that runs before play, and a whole new pair of actions: .selectPassCard and .confirmPass. It is a new page. The existing pages don’t need to know about it.
static var passingPage: RulePage<State, Action> {
RulePage(
name: "Passing",
rules: [
GameRule(
condition: { $0.phase == .passing && ($0.passingState?.selected.count ?? 0) < 3 },
actions: { state in (state.hands[state.player] ?? []).map { .selectPassCard($0) } }
),
GameRule(
condition: { $0.passingState?.selected.count == 3 },
actions: { _ in [.confirmPass] }
)
],
reduce: { state, action in
switch action {
case .selectPassCard(let c): state.passingState?.selected.append(c); return ([], [])
case .confirmPass: state.executePasses(); return ([Log(msg: "Cards passed")], [])
default: return nil
}
}
)
}
Shooting the moon. If one player takes every heart and the queen, they score zero and everyone else takes 26. This is an amendment to scoring, and it lives entirely inside the hand page’s reducer:
// inside scoreCurrentHand()
for seat in Seat.allCases where isShootingTheMoon(seat: seat) {
handPenalties[seat] = 0
for other in Seat.allCases where other != seat { handPenalties[other] = 26 }
}
No other page can tell that this rule exists.
You may not lead hearts until they are broken. The last amendment narrows the cards you can lead with:
func legalLeads(_ hand: [Card]) -> [Card] {
if heartsBroken { return hand }
let nonHearts = hand.filter { $0.suit != .hearts }
return nonHearts.isEmpty ? hand : nonHearts
}
Every amendment was implemented in one of three ways: a new page owning a new case for the action enum (passing, trick resolution), a narrowing of some page’s offer (follow suit, can’t lead hearts), or a tweak to one page’s reducer (shooting the moon). None of them reached across pages.
Bonding: even more compositionality
oapply builds a game by taking the disjoint union of pages. The predicates are each checked for truth and the actions are unioned. The reducers are all run (though we assume only one handler, which was the reason for the early exit in the code above). But we can tease out another operator from what we just described above! I’m calling it bonding, written $\oplus$, and it is the product to oapply’s sum (yes it’s an oplus but it makes sense to me).
Bonding folds two compatible RulePages into a single RulePage: it ANDs the preconditions, concatenates the reduce-steps in list order, and unions the offers, though in practice there’s only one nonempty offer field, as you’ll see in the example. Because the reduce steps concatenate in order, $\oplus$ is associative but not commutative: a page that reads what an earlier page wrote must come after it.
Hearts rules are better combined with bonding!
Legal plays are an AND of independent restrictions. The rulebook gives three sentences about what you may play, and each narrows the same .playCard:
FollowSuit: follow the led suit if you canNoLeadHearts: do not lead hearts until they breakFirst2Clubs: the holder of 2♣ leads it on the first trick
Each is a modifier contributing one predicate, and bonding them ANDs them. So bonding is like amending the rules by saying “oh, but you can’t…” or “oh, but you have to…” The earlier version of legalPlays inlined these amendments. But it’s better expressed as three fragments $\oplus$’d together. If you use the rule that hearts and the queen of spades cannot be played on the first trick, you can bond that in.
Hand scoring is an ordered sum of penalty contributions.
Hearts+1: plus one per heartQueen+13: plus thirteen for the queen of spadesShootMoon: plus 0 and other players get plus 26
If you want to use “minus ten for the jack of diamonds” then bond in JackDiamonds-10. Shooting the moon reads the finished total and inverts it, so it must bond last. That is the non-commutative half: the moon page does not commute with the additions it depends on.
The full picture, so far
Here’s how everything fits:
oapply is borrowed vocabulary. In the AlgebraicJulia line of work, following Vagner, Spivak, and Lerman, oapply is the action of a wiring-diagram operad on an algebra of open dynamical systems. The operad’s operations are boxes wired together: each inner box exposes ports, the operation says how the ports connect, and oapply evaluates the wiring into one composite system. The wiring carries real information: which output feeds which input.
I don’t quite live up to this. My pages share one global State and one global Action enum, and the “wiring” is just “collect these $n$ pages”. We don’t have to express that the “trick pile” from the rule that plays a card is the same “trick pile” that is scored and removed later. We just let both rules refer to the same-named State member. The wires have zero length. The corollary is that we can’t paste in a new RulePage that introduces new state members, which would be ideal. Imagine a game like Magic: the Gathering where your friend plays a card you’ve never seen, and that card says to count all the creatures on the battlefield. That’s the compositionality that I’m going for in its most extreme form: new rules being added on the fly to make a larger game. In my engine you’d have to have already known about this card and supplied a “creatureCount” state member.
Next steps
The external API of ComposedGame, getLegalActions and reduce, is exactly the generic interface we need to implement a game-playing agent. It has always been a required feature of this project that the games are automatically playable by a reusable bot. The bot I have right now is a Monte-Carlo tree search (MCTS) bot that knows how to play with more than two players, and with hidden information. I’ll talk about that later.
In addition, the implementation of games is actually not in Swift, it’s in JSON. Inspired by Ludii, I have developed a domain-specific language that will eventually allow users to share their own game rules with each other. The motivating example I’m working towards is taking a Vassal module and a PDF of the rulebook, and working with an AI agent to write the JSON. I’m developing an agent skill to do this in one shot. Combined with the graphics from the Vassal module, you’d have a rules-enforced complete game app with a bot opponent. The fact that the mathematical rules engine is sticking so closely to how a human reader digests a rulebook should allow the coding agent to translate the text in the rulebook “easily”. We’ll see.