Archive for the ‘Uncategorized’ category

Shaker Dice and Edge Labelings

June 21st, 2021

Last year I saw an interesting Kickstarter campaign for “shaker dice”. The product was shaped like a credit card, with a number of reservoirs with tiny balls. Instead of tossing, you would shake the device and then read off random numbers based on where a specially colored ball ended up in a channel below the reservoir. When the campaign failed to fund, I felt pretty motivated to produce my own version, for a couple of reasons. First, it used lasercut plastic. This is a medium I’ve used for a bunch of puzzles, so I felt that the design work would be pretty straightforward for me. Second, they just got the implementation all wrong.

This was the top image on the campaign page for that Kickstarter. The first clue that they didn’t understand their market is they thought folks would not want more dice.

To see why I thought that, let’s take a step back, and consider what the function of dice actually is. It seems obvious, at first glance, it’s just to produce a random number. But I’d argue there’s more to it than that. Games are social; what you really want is to communicate a random result to other people around a table. This is why you can expect to get a bit of side-eye if you bring a D-Total to a D&D night.

It’s eighteen dice in one! Want to know what number I just rolled? It’s really simple, just read the included manual.

The biggest problem with No More Dice is that because it produces a large number of different results at the same time, it doesn’t communicate which one is the one you care about. So the first change in my design was to split each die into a separate item. I also wanted to increase the size of the balls and the numbers at the positions where the balls end up, in order to make the dice readable from farther away. There was an important practical limitation; the thickest available plastic sheet for the middle layer was 4.9mm thick, so I was looking at 4mm balls. That’s not really enough to make numbers that are readable from across a table, but at least you can see the positions of the balls reasonably well.

At this point, it became clear that the size of the dice was going to be an issue. Even a d4 would be bigger than most regular dice; a d6 would be huge, and d10 or above would be entirely impractical, once we consider that you’d be carrying each of the standard RPG dice together as a set. Getting to a full set of dice that gamers might consider reasonable was going to take a bit of creativity.

My first observation was that I could abandon the biggest selling point of No More Dice: that you didn’t have to toss them. Early on, I decided that I wanted there to be a bit of padding on the back of the dice so you could set them down on a table and let gravity hold the balls in place at the bottom of the channel. But if there was padding on the front side as well, and the dice had numbers on both sides, and you could toss them… my d4 could also be a d8. Uh oh. Multiple functions? Was I heading down the dark path to the D-Total? It’s a fair worry, but, most importantly, the result requires no interpretation. It’s still just the number above the specially colored ball. Second, the physical gesture used communicates which die was rolled. If I shook it and set it down, it was a d4. If I shook it and tossed it, (so it could land on either side with equal probability) it was a d8.

That idea was enough to get me most of the way to a full set. The same principle could give me a d6/d12, and a d10 with 5 balls. (The d10 could also be a d5, but since that isn’t a standard die, it seemed better to balance the numbers by putting the odds and evens on opposite sides.) Two problems remained. The d6/d12 was bigger than I wanted it to be, and there was just no reasonable way to get a d20.

There was a good reason to hope that solutions existed. Having only one ball be distinguishable from the others leaves a lot of potential information unused. In principle, with 5 balls of different colors, there are 5! permutations, or enough for a d120. Just one that requires a manual to decode a numerical result from the permutation. If only there was a genuinely good die-roll decoding technique. Something where a single symbol would be enough to tell you how to find your result, no manual required. Something that gamers already do all the time with the results of dice rolls. Something like basic arithmetic.

In fact, the answer was a mathematical structure that I already knew about, in another context. A perfect Golomb ruler is a way of marking a line with n marks such that each of the integers between 1 and n choose 2 is one of the distances between two marks. One perfect Golomb ruler with 4 marks is {0, 1, 4, 6}.

Another model for the same structure is a “graceful labeling” of the edges of a complete graph. We label the nodes with integers, and the edge labeling is induced by taking the absolute difference of the nodes on that edge. By using two specially colored balls whose positions correspond to nodes on the graph, the edges give us our die-roll results. Slap a minus sign on the die, and what you need to do is clear enough.

That allows us to have a d6 that is the same size as the d4, but now we’ve lost the d12 that occupied the same die. Can we get it back? Not with a graceful labeling, unfortunately, but if we use addition rather than subtraction on the other side of the die, we can get all of the numbers between 7 and 12 using {3, 4, 5, 7} as our set of numbers on the other side.

We could, in fact, have used addition on both sides of the die, as the sums from {0, 1, 2, 4} also give us 1 through 6. Complete edge labelings induced by addition have been studied by mathematicians as well: they’re called “harmonious labelings”. (The usual definition uses addition modulo the number of edges. I didn’t think gamers were likely to put up with mod though, so I’m not using it.) While I could have gone with the design with addition on both sides, I ended up preferring the one with a plus side and a minus side, mostly because it echoes what I used for the d20.

Right, the d20. Taking 5 choose 2 gives us 10 for the number of possibilities given two specially colored balls out of five. It would be really great if we could pull off the same trick that we used for the d6/d12, by getting 1 through 10 on one side of the die and 11 through 20 on the other side. Alas, no combination of addition and subtraction on the two sides of the die will allow this. However, if we remove the requirement to have it also be a d10 we can get all of the numbers for a d20 with addition on one side and subtraction on the other. I wrote Python code using Google’s or-tools constraint solver to find valid numberings; the one I went with is {0, 1, 5, 18, 20} on the minus side and {1, 2, 5, 7, 9} on the plus side.

And that’s the entire set of standard RPG dice! It worked out pretty nicely that the whole set could be done with just two different sizes of the same design, each with a one dark ball version, and a two dark ball version with extra arithmetic.

As a coda, I did put some thought into what could be done with 6-ball shaker dice. One dark ball gives us my original d6/d12 design. Two dark balls gives us 6 choose 2 = 15, from which we could make a d15 or d30 if any solutions existed. But they do not. Three dark balls — well that would be ridiculous. 6 choose 3 is 20, so you could get an alternative d20 that didn’t require tossing, or a d40 that does. But what would you even do for labeling such a die? I settled on adding the two outside numbers, and subtracting the middle one. A d20 wasn’t possible, but a d40 was:

It’s utterly chonky, and makes you do an entirely unreasonable amount of arithmetic, all in order to give you a die that absolutely nobody needs — and I kind of love it.

The making of Angle Find!: a game of geometric discovery

September 2nd, 2012

Allow me to introduce Angle Find!, a game that I designed and developed for helping to teach students about angle measurements. If you have a little time to check out the game itself, I’d suggest clicking the above link and doing so before you read on.

The genesis of Angle Find! was a contest for geometry teaching games held in 2010 by the Games for Learning Institute. The contest required that the game be playable in a web browser. Although I created the start of a design for a game for that contest, I did not at that time write any code, and it was not until the fall of 2011 that I wrote the game for an independent study that I was taking in pursuit of a M. Ed. degree at Lewis & Clark. (This post is largely based on my write up of the experience that I made for that class.) I was inspired by the genre of “hidden object” games, where one is asked to find a number of cleverly disguised objects of a particular type, perhaps pencils or stars, within a busy picture. In the game I would write, the hidden objects would be angles of a certain size, hidden within a geometric configuration containing a number of different angles.

Technology Choices

Because I was not planning on marketing the game commercially, I felt free to try out newer web technologies that are not yet implemented in all common browsers. I needed a platform capable of handling vector graphics within a dynamic game screen area in a web browser. Reasonable options included Flash, Java, SVG, and the HTML5 canvas. The latter two seemed to allow easier integration, using Javascript, between the game screen and the web page it was embedded within. I had previously used SVG for my Lissajous demo, but I was intrigued by the HTML5 canvas, which seemed to have a more direct programming interface. Unfortunately, when I decided to use the HTML5 canvas, I hadn’t yet looked too closely at its capabilities; it turned out to be more low level than I had thought. In SVG a rectangle (for example) is an object that can have behavior (like responses to mouse clicks) defined for it. In the HTML5 canvas, drawing a rectangle merely changes the color of a block of pixels. I looked for a Javascript framework that would sit on top of the HTML5 canvas and give me some of the functionality that was present in SVG. I settled on an open source framework called CAKE. CAKE advertised itself as “SVG without the XML” which was in fact precisely what I wanted.

Now, having used CAKE to write a real application, I’m not sure I would recommend it to novice programmers who want to write their own apps. The documentation provided at the CAKE site is incomplete, and I had to spend a lot of time perusing their sample code and the CAKE framework code itself in order to figure out what I needed to do. The other platforms I mentioned have multiple books written about them, so you should be able to find one that fits your level of programming skill. If cross-browser compatibility is important to you, Flash is probably the best option at present.

Another consideration is that CAKE requires the the user to download the framework code in order to use it. The size of this file can increase a page’s download size significantly. There are tools to minimize the size of Javascript files, and the CAKE site recommends their use, but it is one more technological hurdle to jump. However, it may well be helpful to learn about these anyway if you are going to be doing a jot of Javascript programming. The other platforms do not require an extra framework download.

For the purpose of writing this game, I decided to ignore browser compatibility issues. In retrospect, I wish I had paid more attention; I ended up running into problems in testing the game when testers only had Internet Explorer available. The HTML5 canvas is not supported in Internet explorer 8 and earlier, and appeared to not be supported in Internet Explorer 9 in testing, although shows that it should be supported. Incidentally, that site is a good resource for finding out what features are supported on the major web browsers presently in use. It was also helpful to look around the site and see some of the newer web programming features that are out there; I learned about a couple of CSS features (the drop shadow and rounded box corners) that I ended up using in the final version of the game.

Creating a Prototype

For my first prototype of the game, which had only one level, I wanted a configuration of lines and angles that would be as simple as possible to produce but not entirely trivial to play through. I settled on a set of three lines along with the angles induced by their intersections. This ended up feeling like it had an appropriate level of complexity for an introduction to the game, so I kept this configuration for the first set of levels in the final game.

I decided to specify the lines in a given level by a point and the angle at which it deviates from horizontal. Having the angles made it easy to see the differences in angles, (which would be the angles present in the level) and having a point on the line made it easy to adjust the position of the line by changing the point. I positioned the lines by trial and error and eyeballing to keep the configuration of lines balanced and spread out, so this was useful.

The early part of programming the game involved doing a fair amount of high school level math. Turning angles into slopes required some trig, and finding endpoints and intersections took some algebra. I found myself a little rusty, and had to look up or rederive a couple of formulas. It occurred to me that this kind of experience of applying mathematics to solve genuine problems would be very powerful for students. At the same time, their genuineness as problems to me is impossible to bottle—a word problem about a programmer who needs to find an intersection between two lines would lose it entirely. Nevertheless, I believe that if we teach young people programming and encourage and reward curious exploration and problem solving, meaningful mathematical experiences will abound, even if we can’t guarantee that all of a set of standards will be touched.

Level Design

Turning the prototype into a complete game required several more levels to be designed. In designing levels I was limited by the small number of sets of angles that met my desired criteria. I wanted to use only angles that were multiples of 5°, I wanted no angle smaller than 20°, (because small angles would be harder to click on) and I wanted the minimum difference between angles in a level to be 10°. On top of that I wanted to avoid, as much as possible, repeating angles between levels. The choice of a configuration based on a 40°-60°-80° triangle for the first level was almost preordained, as it has a large minimum angle, a large minimum difference, and no angle that is not a multiple of 10°. It also has the pleasing property that every multiple of 20° between 40° and 140° is represented.

I wanted the difficulty and complexity of the levels to increase gradually as the game progresses. Introducing an additional parallel line in the second level set increases the number of intersections from three to five, without increasing the number of different angles that have to be distinguished. Making all four lines non-parallel in the third level set increases the number of intersections again, to six. Within the first two level sets, easier levels (with larger minimum angle size differences) precede harder ones.

In the first level in the final level set I kept the difficulty under control by including two intersections where the lines meet at the same angle. However, for the final level I wanted one with every intersection having a different pair of angles. In order to do this I had to relax my design constraints somewhat: I allowed myself a smaller minimum angle and angles that were not multiples of 5°. To find an appropriate configuration of lines, I used the concept of a Golomb ruler. A Golomb ruler can be thought of as a set of marks on a stick where each distance between marks is a unique integer. The set {0, 1, 4, 6} is one such set; this set is called a perfect Golomb ruler because every integer between 1 and 6 is represented as a difference between two members of the set.

Notice that the set of angles induced by the intersections of a set of lines is the set of differences between the absolute bearings of the lines, modulo 180° and with the complication that you also get all of their supplementary angles for free. Picking a convenient multiple of the members of the perfect Golomb ruler above for the absolute bearings of the lines would therefore give me a well spread out set of angles. I wanted a largest angle that was a multiple of 6°, and as large as possible while still being less than 90° and distinguishable from its own supplement. The choice of 84° seemed reasonable. Since 84° = 6° · 14, scaling the members of the perfect Golomb ruler by 14 gives 0°, 14°, 56°, and 84° (all plus some constant) for the absolute bearings of the lines, and 14°, 28°, 42°, 56°, 70°, 84°, 96°, 110°, 124°, 138°, 152°, and 166° for the angles, which is as good of a set as I could have hoped for.

Future Directions and New Angles

I tested the game out on a small number of middle school students. Testing revealed that students had more trouble with obtuse angles than with acute ones, and with distinguishing angles that were relatively close. I revised the angles present on one of the levels which previously had 50° and 60° angles, which my testers had trouble with. I also increased the size of the clickable sectors to make narrow angles harder to misclick.

The first phase of this project has come to a close with the completion of the independent study that I wrote it for, but I expect to continue to fix problems and add features to Angle Find! in the future.

Currently, the game lacks replayability; the level designs are static, and present no challenge once they have been memorized. I am considering writing a random level generator. Generated levels would follow the hand designed ones, and the game would make it clear that the hand designed levels constitute the game proper, with the generated levels being an optional bonus for players who are just having too much fun to quit. It should be possible to have generated levels adapt their difficulty level to a player’s performance in previous levels.

I also want to add a set of levels with angles occurring in the context of various kinds of triangles and quadrilaterals, with perhaps three or four polygons per level. I could reuse the idea of coloring lines with special properties by coloring sides with the same lengths the same; this would allow players to discover the relationship between congruent sides and congruent angles in an isosceles triangle.

Finally, I would like to be able to work with educators to see the results of implementing the game in broader settings. It would be wonderful if Angle Find! could find a place as an enjoyable tool for discovery for students learning about angle measurement and properties.