Finding Prime Numbers with Leaping Frogs

Imagine a pond that contains a long line of lily pads, each labelled with a number, starting with '2', '3', and so on.

A scary stork enters the pond, looking for frogs!  Each turn, the stork will move to a new lily pad, starting with lily pad 2.

When the stork reaches a lily pad, it looks for frogs:

• If the lily pad has no frogs on it, the stork finds one in the water. Take a new frog token and write the lily pad's number on its back. Put it on the lily pad with the stork.
• If the lily pad already has frogs on it, the stork won't look in the water, so this lily pad does not get a frog of its own.

The stork then shouts, "Boo!"  This scares the frogs, who jump away. All the frogs jump forward a number of lily pads equal to the number written on their backs.  Frog #2, for example, will make the first leap from lily pad #2 to lily pad #4, and then later to lily pad #6. (It's okay for frogs to share lily pads.)

Stop after however many turns you like.  When you're done, the numbered frogs represent all the prime numbers that you found (at least from numbers 2 to whatever lily pad you stopped at).

When a stork first reaches a lily pad, all the frogs there are the prime factors of that number.  For example, when the stork reaches lily pad #20, the stork will find frogs 2 and 5 there.  (20 = 2 x 2 x5.)  Lily pad 19, however, is empty when the stork arrives arrives: the newly minted frog 19 indicates that 19 is a prime number, and there are no other prime factors (other than 1).

To summarize:

1. Move the stork forward one lily pad (on the first turn, place it on lily pad 2).
2. If the lily pad has no frogs on it when the stork gets there, make a new frog with the lily pad's number.
3. All the frogs on the stork's lily pad jump forward a number of pads equal to their number.

Consider a simple mathematical process, like an algorithm that generates the digits of Pi. Pi never stops, so in a way, the algorithm provides a window into an arrangement of information that's infinitely long.

Now look at a slightly more complicated process, such as Conway's Game of Life. Much like the Pi-computing algorithm, this is just another mathematical process, but the arrangement of information it describes is somehow richer: the game represents a 2D space evolving over time, with gliders, glider guns generating them, and so on.

What's interesting about both of these is that the "world" defined by the algorithms is in some way independent of actually running the simulation. Two people who calculate Pi will come up with the same answer. You can calculate 1000 digits of Pi and come back half an hour later, and calcluate another 1000 digits, and you'll have the same 2000 digits as someone who did 2000 at once.

Similarly, two people who run Conway's game (from the same starting conditions) will watch the same set of events unfold. Just as with Pi, they can stop the simulation, take a coffee break, and turn it on again, and the world inside continues completely unaware. You can rewind it, run it again, and it's all the same.

So in a way, simulations are a way of exploring a mathematical space. The existence of that space, in some ways at least, is independent of whether and when we explore it. The fact that a certain collision between 13 gliders happens on turn ten billion of a particular game seed is independently discoverable - it's already there, encoded in the rules, awaiting our discovery.

Now consider simulated worlds that are rich enough to develop artificial life, sophisticated enough to be self-aware. (By this, I mean that the simulated beings have an internal model of their world that includes a representation of themselves.) If you're a materialist, I think it's a short step to imagine that such beings could have an experience of themselves that's as rich and as convincing as ours is.

Nevertheless, we could pause that simulation, rewind it, run multiple copies, and none of this would affect the experience of the beings inside, because their experience is wholly encoded in the interplay of information that the simulation rules describe.

Much like the glider collision, or the 100th digit of Pi, their consciousness is already there. Running the simulation just allows us to experience it. Their world is real, to them. Even if we don't run the simulation.

Even if we don't .. invent it?

Now, if we discover that our world is based on a set of principles that could, in theory, be simulated, then what follows is that our world might not be 'real', either. Nobody's running it - nobody needs to!
Maybe somebody is running it, somewhere in another universe, but all that means is that they're exploring part if it. It doesn't mean that they're creating us, just that they know what we're up to (if they've run it this far).

Actually, this line of reasoning pretty much guarantees that an infinite multitude of different meta-worlds are exploring our universe through simulations, as well as all possible other universes, just exploring different parts of it.

Autocomplete & API Design

Autocomplete Rocks

As an avid Eclipse user, I love auto-complete.  It feels like it's a big, easily overlooked boost to how I program.  Not because it saves a few keystrokes here and there, but because it provides such a boon to explorability of the APIs that I use.  Essentially, I'm querying my programming environment to see what my options are.

Seeing a list of IntelliJ's top 20 auto-complete features, there are some really neat ones - chain completion is particularly cool.  IntelliJ will inspect in-scope variables several levels deep, so it's able to suggest methods of in-scope objects that I hadn't even considered.

Basically, this is a specific, but handy, limited method of querying my codebase/libraries.  I can envision more complicates ones, such as a completion that would help me with that perennial Java I/O plumbing problem of how I get from a FooWriter to a StringInputStream.  Could an IDE make a few suggestions?

Auto what?

I'm also a frequent user of Apache Tapestry, and one of the things that occasionally confounds me about it is that whenever I get rusty with a particular component, I need to look at the documentation to see what I can do with it.

Not docs accessed through my IDE, but actually busting out a web browser, and navigating through some documents meant for humans to read.  Actual essays!

This is because, in Tapestry, you write event handlers by giving an ordinary method a special name:

public void onSelectedFromMyWidget() { ... }

Tapestry uses reflection to make the association between the this method, and the "selected" event thrown by the component with the name 'MyWidget'.

But here the IDE knows nothing about the meaningful names.  There's no object to inspect, no interface that defines all the callback methods.  If I forget that the event type is 'selected' for LinkSubmit components but 'action' for ActionLink components, I have to go to the documentation.  If I don't realize I've misremembered, my event handler simply never gets passed any events.

I recently learned that HLS codes in Emacs, I wonder if this is related!

Bothered About Dungeons & Dragons

The height of the anti-D&D movement of the eighties was a painful time for me; it put several of my friendships on hiatus, and effectively end my close relationship with my best friend of the time.

At the time, I never heard of BADD - this anti D&D sentiment was a vague thing, seemingly fueled by parents' worries and a story about a young D&D fan who killed two young girls in nearby Orangeville. It was on the horizon - mixed up with religious ignorance south of the border.

After a dry spell of a few months, in the company of other friends, I found my way back into gaming - through the Fighting Fantasy RPG (of all things) and back into AD&D with a new group of enthusiasts and new friendships. An unpleasant chapter ended.

15 years later I stumble on this Wikipedia article about Patricia Pulling, the founder of BADD, and the whole thing acquires a much more human face; it's a tragic story, really. Fervently believing that the suicide death of her son was a result of D&D, she sued his school's principal and started her one-woman crusade.

The article goes on to say that although she and BADD gained a fair bit of media coverage through conservative and christian media, all of the lawsuits she initiated or later consulted for failed. Her own book discredited her through factual and mathematical errors, and eventually no less than the CDC concluded there was no link between fantasy gaming and suicide.

I find it very moving to look at this as the story of a mother who can't accept the loss of her son, and what a load of wasted effort and pain she stirred up for others in the process.

"BADD effectively ceased to exist", it concludes, "when Pulling died of cancer in 1997. By this time, BADD had been reduced to Pulling as its sole member." Sad stuff.

Burning Wheel

For the record, my favourite role-playing game is Burning Wheel, hands down, mostly because it changed the way I look at RPGs.


The reason for this is that 'the plot' emerges, much of the time, from the players seizing the initiative and pushing towards their characters' written goals (termed 'Beliefs'). Instead of taking a psychologically (and literally) armored, 'survive the adventure' stance, PCs take risks, go out on a limb, pursue their gauche obsessions to accomplish these goals.


The GM's task is to push the central conflict, while at the same time producing character-specific challenges that reveal the characters more fully, giving them hard moral decisions, catch-22 sacrifices, and stirring up deep inner turmoil.


You can do this in any game, of course, but in BW, the reward and advancement mechanics are built around this. There's no XP for the adventure, only for driving toward your characters' goals, and for embodying your character's personal flaws and development in ways that enhance the story.


BW games start with out-of-character collaboration at the table - the group hones in on a central conflict that gets everyone fired up, and then character concepts are hammered out. Off-theme oddballs who are just along for the ride aren't welcome.

Creativity & Spontaneity

Because of this, you do need the right group. Players who want to sit back and be entertained, having their dark and taciturn ranger take potshots from the back - whether because they just can't be bothered or because they're creatively inhibited - will tend to drag things down.


Apart from their goals, the players are given additional tools to have creative input - a Circles ability, which lets them drum up useful contacts from their past (in the way that Han Solo looks up Lando Calrissian), and "wises", which lets them propose world facts.


The GM needs a lot of spontaneity to be able to roll with whatever players come up with, but on the other hand, planning is much simpler since you don't need to produce any more content than interests you (with its accompanying stat blocks, etc.). Preparing 'plot' is counter-productive, and hinders the game.


Apart from pushing the central challenge, the GM's job is to keep the spotlight on the really interesting aspects of the story. Whole months of grinding, travel time, practice montages, investing, keeping up with the bills, all are blinked away neatly.

Shaped by the Story

As I said, you can of course do this sort of thing in any game - the real advantage is that BW is trying to steer you there. One of the clever things about D&D's XP and classes is the way that they insulate the characters from the story. As long as you show up and get your XP from your cousin's mediocre adventure, you get to advance along your pre-chosen archetypal hero's journey - new feats, powers, etc.


In BW, the characters and the story develop in response to one another much more tightly. If you want your paladin steed, wizard's tower, or crazy chain-fighting ability, you're going to have to get it yourself! Characters are profoundly shaped by their experiences.

Social Conflict

The other thing that must be mentioned is Duel of Wits. BW expressly puts the dynamics between characters, PCs included, within the scope of the mechanics. Just as physical combat has detailed mechanics for important conflicts, so does social/verbal conflict.


This gives some people an allergic reaction, because it means that the other people at the table can shape things as intimate as your character's pecking order in the group. Like the other aspects of collaboration in BW, this requires trust and open communication OOC - some people might not enjoy being the group's toady, others might relish it, and this makes all the difference.

What it does do, however, is vastly expand the scope of interesting conflict in the game. You can now have parties that bicker violently but yet never get stalled - they have the conflict and move on (perhaps grumbling resentfully or simmering for a chance to turn the tables, but moving on nevertheless). You can have low-combat games where the grand conflict is a debate with the domineering village priest, who is refusing to authorize badly needed funds from Rome on the grounds that the village isn't pious enough.

Coloring your Campaign

How do you come up with interesting elements to add to your campaign world?  A few months ago, I realized that I'd completely neglected to make any mention of animals, despite the whole campaign being set in the wilderness!

I wanted a tool that would help me remember to incorporate these things.  The end result of this little project was this (click to view):

The first version was a fancy series of concentric rings, which you could rotate to generate random combinations.  But printing/assembling was fiddly, rolling dice was easier anyways, and, more subtly, not all of the rings were meant to be used the same way.

This revised version (which I've actually had for a little while now, but never published here) is certainly easier to print, and is hopefully a little easier to use.

The philosophy behind this tool isn't to try to detail every aspect of a region, culture, or an NPC, but to create an interesting spine and then attach other details to it.


Brainstorming Silugan
For example, let's say the players are heading to Far Silugan, a location I haven't thought about much at all.  It's a riverside town at the edge of Keroon City's influence - beyond it are the trackless wastes of the Meer Galu.  That much I know, but what would make it memorable, or interesting?


I'll start with an Aspect of Nature - it seems fitting, because Far Silugan is so far from the city.  Rolling d8, I get 2: Landforms, Terrain, Geology.  (I haven't had my coffee, so nothing is leaping to mind yet.)  Now I'll add a Trend.  7: Upheaval.


Okay, that's interesting.  "Earthquake" is the obvious option, but the river makes me think of catastrophic erosion of a riverbank (possibly undermining important structures).  Maybe a sinkhole?  So, how does this influence the people?


Back to the top, I roll a sphere of human activity: 4 - Games, Play, Fashion.  Huh.  How is this affected by the erosion?  I roll a relation: 6 - Overt Domination Of.  The Games/Play/Fashion result isn't really grabbing me - I'm more interested in the undermined buildings that came to me before.


An emotion might be better: 8 - Celebration!  (Hah.)  Okay, fine, I can take a hint.


Now, how does what's happening present itself?  Nothing matters unless you perceive it.  I roll a sense: 5 - Smell.  Hmm.


Okay, Far Silugan is getting clear in my mind.  I see old, stone buildings, two or three stories mostly, but which have been completely undercut by the rapidly eroding river.  The populace, however, joyfully but steadfastly maintains the ancient arrangement of buildings, which somehow figures in a series of celebrations. The people maintain a laissez-faire, joyful outlook, and those that do not fish, busy themselves with maintaining the stonework.

After centuries of this erosion, the river now passes directly through the town, underneath the central plaza, now a dense arrangement of bridges and covered culverts.  Nevertheless, the erosion continues unabated, and one of the central buildings is expected to collapse any day now.  It is festooned with flags, streamers, and its lower story has been painted with wavy lines, symbolizing the wrinkles of old age.

When it finally does go, it will trigger a month-long celebration, during which the structure will be rebuilt atop new foundations.  The air is thick with the smell from countless fish being smoked in preparation.  Masons pile sand dredged from the river for mortar, while children play in the building's shadow, hoping to win at the game of being the last to touch the building before it falls, while old men pick their teeth, take bets on the falling day, and keep a watchful eye.

Alignment is Allegiance

Musing about alignment in D&D today, I had a realization.  The very word explains its purpose - who are you aligned with?  When the world is dark, do you stand with good King Osric, or with the forces of chaos?

Once you take this into an environment with plenty of moral gray - in other words, just about every poignant decision in the story - it's just the wrong tool for the job.  Alignment is not about morality, it's about allegiance.

In an urban political campaign, 'good' and 'evil' could be usefully replaced with more relevant alignments, like "Royalist" or "Republican".  It's not about what you should do, but who you're doing it for.