Back in 2011, some folks cross-compiled Doom (the original, not the reboot, obviously) to JavaScript, leveraging the capabilities of the then-relatively-young
<canvas> element and APIs. I was really impressed to see that JavaScript had come so far and that
performance on desktop devices was so slick. Sure, this was an 18-year-old video game, but it was playable in a browser, which was a long way from the environment for which it
was originally developed.
Now Doom 3‘s playable in a browser, and my mind’s blown all over again. This follows almost the same curve – Doom 3’s 16 years old – but it still goes to show that there’s
little limit to the power of client-side browser programming. They’ve done this magic with WebAssembly; while WebAssembly goes
slightly against my ideas about the open-source nature of the Web, I still respect the power it commands to do heavyweight crunching tasks like this one.
How long until AAA developers start developing with the Web as an additional platform?
A long while ago, inspired by Nick Berry‘s analysis of optimal Hangman strategy, I worked it backwards to find the
hardest words to guess when playing Hangman. This week, I showed these to my colleague Grace – who turns out to be a fan of word puzzles – and our conversation inspired me to go a little deeper. Is it possible, I
thought, for me to make a Hangman game that cheats by changing the word it’s thinking of based on the guesses you make in order to make it as difficult as possible for you to
win?
The principle is this: every time the player picks a letter, but before declaring whether or not it’s found in the word –
Make a list of all possible words that would fit into the boxes from the current game state.
If there are lots of them, still, that’s fine: let the player’s guess go ahead.
But if the player’s managing to narrow down the possibilities, attempt to change the word that they’re trying to guess! The new word must be:
Legitimate: it must still be the same length, have correctly-guessed letters in the same places, and contain no letters that have been declared to be incorrect
guesses.
Harder: after resolving the player’s current guess, the number of possible words must be larger than the number of possible words that would have
resulted otherwise.
You might think that this strategy would just involve changing the target word so that you can say “nope” to the player’s current guess. That happens a lot, but it’s not always the
case: sometimes, it’ll mean changing to a different word in which the guessed letter also appears. Occasionally, it can even involve changing from a word in which the guessed
letter didn’t appear to one in which it does: that is, giving the player a “freebie”. This may seem counterintuitive as a strategy, but it sometimes makes sense: if
saying “yeah, there’s an E at the end” increases the number of possible words that it might be compared to saying “no, there are no Es” then this is the right move for a
cheating hangman.
Playing against a cheating hangman also lends itself to devising new strategies as a player, too, although I haven’t yet looked deeply into this. But logically, it seems that the
optimal strategy against a cheating hangman might involve making guesses that force the hangman to bisect the search space: knowing that they’re always going to adapt towards the
largest set of candidate words, a perfect player might be able to make guesses to narrow down the possibilities as fast as possible, early on, only making guesses that they actually
expect to be in the word later (before their guess limit runs out!).
I also find myself wondering how easily I could adapt this into a “helpful hangman”: a game which would always change the word that you’re trying to guess in order to try to make you
win. This raises the possibility of a whole new game, “suicide hangman”, in which the player is trying to get themselves killed and so is trying to pick letters that can’t
possibly be in the word and the hangman is trying to pick words in which those letters can be found, except where doing so makes it obvious which letters the player must avoid next.
Maybe another day.
In the meantime, you’re welcome to go play the game (and let me know what you think, below!) and, if you’re of such an inclination, read the source code. I’ve used some seriously ugly techniques to make this work, including regular expression metaprogramming (using
regular expressions to write regular expressions), but the code should broadly make sense if you want to adapt it. Have fun!
Update 26 September 2019, 16:23: I’ve now added “helpful mode”, where the computer tries to cheat on your behalf
rather than against you, but it’s not as helpful as you’d think because it assumes you’re playing optimally and have already memorised the dictionary!
You may recall that on Halloween I mentioned that the Bodleian had released a mini choose-your-own-adventure-like adventure game book, available freely online. I decided that this didn’t go quite far
enough and I’ve adapted it into a hypertext game, below. (This was also an excuse for me to play with Chapbook, Chris Klimas‘s new under-development story format for Twine.
If the thing you were waiting for before you experienced Shadows Out of Time was it to be playable in your browser, wait no longer: click here to play the game…
Notes from #musetech18 presentations (with a strong “collaboration” theme). Note that these are “live notes” first-and-foremost for my own use and so are probably full of typos. Sorry.
Matt Locke (StoryThings, @matlocke):
Over the last 100 years, proportional total advertising revenue has been stolen from newspapers by radio, then television: scheduled media that is experienced
simultaneously. But we see a recent drift in “patterns of attention” towards the Internet. (Schedulers, not producers, hold the power in radio/television.)
The new attention “spectrum” includes things that aren’t “20-60 minutes” (which has historically been dominated by TV) nor “1-3 hours” (which has been film), but now there are
shorter and longer forms of popular medium, from tweets and blog posts (very short) to livestreams and binging (very long). To gather the full spectrum of attention, we need to span
these spectra.
Rhythm is the traditions and patterns of how work is done in your industry, sector, platforms and supply chains. You need to understand this to be most-effective (but this is
hard to see from the inside: newcomers are helpful). In broadcast television as a medium, the schedules dictate the rhythms… in traditional print publishing, the major
book festivals and “blockbuster release” cycles dominate the rhythm.
Then how do we collaborate with organisations not in our sector (i.e. with different rhythms)? There are several approaches, but think about the rhythmic impact.
Partnered with Google Arts & Heritage; Google’s first single-partner project and also their first project with a multi-site organisation.
This kind of tech can be used to increase access (e.g. street view of closed sites) and also support curatorial/research aims (e.g. ultra-high-resolution photography).
Aside from the tech access, working with a big company like Google provides basically “free” PR. In combination, these benefits boost reach.
Learnings: prepare to work hard and fast, multi-site projects are a logistical nightmare, you will need help, stay organised and get recordkeeping/planning in place early, be aware
that there’ll be things you can’t control (e.g. off-brand PR produced by the partner), don’t be afraid to stand your ground where you know your content better.
Decide what successw looks like at the outset and with all relevant stakeholders involved, so that you can stay on course. Make sure the project is integrated into contributors’
work streams.
Daria Cybulska (Wikimedia UK, @DCybulska):
Collaborative work via Wikimedians-in-residence not only provides a boost to open content but involves engagement with staff and opens further partnership opportunities.
Your audience is already using Wikipedia: reaching out via Wikipedia provides new ways to engage with them – see it as a medium as well as a platform.
Wikimedians-in-residence, being “external”, are great motivators to agitate processes and promote healthy change in your organisation.
Creative Collaborations ([1] Kate Noble @kateinoble, Ina Pruegel @3today, [2] Joanna Salter, [3] Michal Cudrnak, Johnathan Prior):
Digital making (learning about technology through making with it) can link museums with “maker culture”. Cambridge museums (Zoology, Fitzwilliam) used a “Maker in Residence”
programme and promoted “family workshops” and worked with primary schools. Staff learned-as-they-went and delivered training that they’d just done themselves (which fits maker culture
thinking). Unexpected outcomes included interest from staff and discovery of “hidden” resources around the museums, and the provision of valuable role models to participants. Tips: find
allies, be ambitious and playful, and take risks.
National Maritime Museum Greenwich/National Maritime Museum – “re.think” aimed to engage public with emotive topics and physically-interactive exhibits. Digital wing allowed leaving
of connections/memories, voting on hot issues, etc. This leads to a model in which visitors are actively engaged in shaping the future display (and interpretation) of exhibitions.
Stefanie Posavec appointed as a data artist in residence.
SoundWalk Strazky at Slovak National Gallery: audio-geography soundwalks as an immersive experiential exhibition; can be done relatively cheaply, at the basic end. Telling fictional
stories (based on reality) can help engage visitors with content (in this case, recreating scenes from artists’ lives). Interlingual challenges. Delivery via Phonegap app which provides
map and audio at “spots”; with a simple design that discourages staring-at-the-screen (only use digital to improve access to content!).
Lightning talks:
Maritime Museum Greenwich: wanted to find out how people engage with objects – we added both a museum interpretation and a community message to each object. Highly-observational
testing helped see how hundreds of people engage with content. Lesson: curators are not good judges of how their stuff will be received; audience ownership is amazing. Be reactive.
Visitors don’t mind being testers of super-rough paper-based designs.
Nordic Museum / Swedish National Heritage Board explored Generous Interfaces: show first, don’t ask, rich overviews, interobject relationships, encourage exploration etc. (Whitelaw,
2012). Open data + open source + design sprints (with coding in between) + lots of testing = a collaborative process. Use testing to decide between sorting OR filtering;
not both! As a bonus, generous interfaces encourage finding of data errors. bit.ly/2CNsNna
IWM on the centenary of WWI: thinking about continuing the crowdsourcing begun by the IWM’s original mission. Millions of assets have been created by users. Highly-collaborative
mechanism to explore, contribute to, and share a data space.
Lauren Bassam (@lswbassam) on LGBT History and co-opting of Instagram as an archival space: Instagram is an unconventional archival source, but provides a few benefits in
collaboration and engagement management, and serves as a viable platform for stories that are hard to tell using the collections in conventional archives. A suitably-engaged community
can take pride in their accuracy and their research cred, whether or not you strictly approve of their use of the term “archivist”. With closed stacks, we sometimes forget how important
engagement, touch, exploration and play can be.
Owen Gower (@owentg) from Dr. Jenner’s House Museum and Garden: they received EU REVEAL funding to look at VR as an engagement tool. Their game is for PSVR and has a commercial
release. The objects that interested the game designers the most weren’t necessarily those which the curators might have chosen. Don’t let your designers get carried away and fill the
game with e.g. zombies. But work with them, and your designers can help you find not only new ways to tell stories, but new stories you didn’t know you could
tell. Don’t be afraid to use cheap/student developers!
Rebecca Kahm @rebamex from Pelagios Commons (@Pelagiosproject): the problem with linked data is that it’s hard to show its value to end users (or even show museums “what you can do”
with it). Coins have great linked data, in collections. Peripleo was used to implement a sort-of “reverse Indiana Jones”: players try to recover information to find where an
artefact belongs.
Jon Pratty: There are lots of useful services (Flickr, Storify etc.) and many are free (which is great)… but this produces problems for us in terms of the long-term
life of our online content, not to mention the ethical issues with using services whose business model is built on trading personal data of our users. [Editor’s note: everything being
talked about here is the stuff that the Indieweb movement have been working on for some time!] We need to de-siloise and de-centralise our content
and services. redecentralize.org? responsibledata.io?
In-House Collaboration and the State of the Sector:
Rosie Cardiff @RosieCardiff, Serpentine Galleries on Mobile Tours. Delivered as web application via captive WiFi hotspot. Technical challenges were significant for a relatively
small digital team, and there was some apprehension among frontline staff. As a result of these and other problems, the mobile tours were underused. Ideas to overcome barriers: report
successes and feedback, reuse content cross-channel, fix bugs ASAP, invite dialogue. Interesting that they’ve gained a print guides off the back of the the digital. Learn lessons and
relaunch.
Sarah Younaf @sarahyounas, Tyne & Wear Museums. Digital’s job is to ask the questions the museum wouldn’t normally ask, i.e. experimentation (with a human-centric bias). Digital is
quietly, by its nature, “given permission” to take risks. Consider establishing relationships with (and inviting-in) people who will/want to do “mashups” or find alternative uses for
your content; get those conversations going about collections access. Experimental Try-New-Things afternoons had value but this didn’t directly translate into ideas-from-the-bottom,
perhaps as a result of a lack of confidence, a requirement for fully-formed ideas, or a heavy form in the application process for investment in new initiatives. Remember you can’t
change everyone, but find champions and encourage participation!
Kati Price @katiprice on Structuring for Digital Success in GLAM. Study showed that technical leadership and digital management/analysis is rated as vital, yet they’re also
underrepresented. Ambitions routinely outstrip budgets. Assumptions about what digital teams “look” like from an org-chart perspective don’t cover the full diversity: digital teams look
very different from one another! Forrester Research model of Digital Maturity seems to be the closest measure of digital maturity in GLAM institutions, but has flaws (mostly relating to
its focus in the commercial sector): what’s interesting is that digital maturity seems to correlate to structure – decentralised less mature than centralised less mature than
hub-and-spoke less mature than holistic.
Jennifer Wexler, Daniel Pett, Chiara Bonacchi on Diversifying Museum Audiences through Participation and stuff. Crowdsourcing boring data entry tasks is sometimes easier than asking
staff to do it, amazingly. For success, make sure you get institutional buy-in and get press on board. Also: make sure that the resulting data is open so everybody can
explore it. Crowdsourcing is not implicitly democratisating, but it leads to the production of data that can be. 3D prints (made from 3D cutouts generated by crowdsourcing) are a useful
accessibility feature for bringing a collection to blind or partially-sighted visitors, for example. Think about your audiences: kids might love your hip VR, but if their parents hate
it then you still need a way to engage with them!
I see a lot of ideas online for things to do with your child, but most of them are a lot of work. Many of them involve an unnerving amount of craftiness and/or require going out to
buy things. Almost all of them involve moving around which, many days, is fine, but some days can be pretty rough. N…
I see a lot of ideas online for things to do with your child, but most of them are a lot of work. Many of them involve an unnerving amount of craftiness and/or require going out to
buy things. Almost all of them involve moving around which, many days, is fine, but some days can be pretty rough. Not that I don’t love getting down on the floor and playing with my
kid (I love it a great deal) but I’m an adult in my mid-thirties. I can pretend to be a dinosaur for about 90 minutes (something I happily list on my professional resume) but after an
hour and a half, all bets are off. And given that many days I’m home with my son for over eight hours, things can get a bit dicey.
I’ve taken the liberty of brainstorming some fun child/parent activities in which your child can be adventurous and creative and you can lie on the sofa reading a book. Here’s my list
so far.
The year was 1995, and CompuServe’s online service cost $4.95 per hour. Yet thousands of people logged into this virtual world daily.
WorldsAway was born 20 years ago, when Fujitsu Cultural Technologies, a subsidiary of Japanese electronics giant Fujitsu, released this online experiment in multiplayer communities.
It debuted as part of the CompuServe online service in September, 1995. Users needed a special client to connect; once online, they could chat with others while represented onscreen
as a graphical avatar.
I was already a veteran of BBSes (I even started my own), Prodigy, CompuServe, and the Internet when I saw an advertisement for WorldsAway in CompuServe magazine (one of my favorite
magazines at the time). It promised a technicolor online world where you could be anything you wanted, and share a virtual city with people all over the globe. I signed up to receive
the client software CD. Right after its launch in September, I was up and running in the new world. It blew my young mind.
For the last few months, I’ve been GMing a GURPS campaign (that was originally a Warhammer Fantasy Roleplay 1st-edition campaign, in turn built upon a mixture of commercially published and homegrown
modules, including, in turn, an AD&D module…) for a few friends.
So far, it’s included such gems as a player-written poem in a fictional language, another player’s drawing of the most-cinematic action sequence they’ve experienced so far… and the opportunity, during a play session that
coincided with a player’s birthday, to explain the layout of a ruined tower by presenting them with a cake baked into the shape of the terrain.
But mostly I wanted to make this post so that I had a point of context in case I ever get around to open-sourcing some of the digital tools I’ve been developing to help streamline our
play sessions. For example, most of our battle maps and exploration are presented on a ‘board’ comprised of a flat screen monitor stripped of its stand and laid on its back, connected
via the web to a tool that allows me to show, hide, or adapt parts of it from my laptop or mobile phone. Player stats, health, and cash, as well as the date, time, position of the sun
as well as the phases of the moons are similarly tracked and are available via any player’s mobile phone at any time.
These kinds of tools have been popular for ‘long-distance’/Internet roleplaying for years, but I think there’s a lot of potential in locally-linked, tabletop-enhancing
(rather than replacing) tools that deliver some of the same benefit to the (superior, in my opinion) experience of ‘proper’ face-to-face adventure gaming. Now, at least,
when I tell you for example about some software I wrote to help calculate the position of the sun in the sky of a fictional world, you’ll have a clue why I would do such a thing in the
first place.
As you may know, I’ve lately found an excuse to play with some new web technologies, and I’ve also taken the opportunity to try to gain a deeper
understanding of some less bleeding-edge technologies that I think have some interesting potential. And so it was that, while I was staffing the Three Rings stall at last week’s NCVO conference, I made use of the
time that the conference delegates were all off listening to a presentation to throw together a tech demo I call Steer!
As you can see from the GIF above, Steer! is a driving game. The track and your car are displayed in a web browser on a large screen,
for example a desktop or laptop computer, television, or tablet, and your mobile phone is used to steer the car by tilting it to swerve around a gradually-narrowing weaving road. It’s
pretty fun, but what really makes it interesting to me is the combination of moderately-new technologies I’ve woven together to make it possible, specifically:
The Device Orientation API, which enables a web application to detect the angle at which
you’re holding your mobile phone
Websockets as a mechanism to send that data in near-real-time from the phone to the browser, via a web server: for the
fastest, laziest possible development, I used Firebase for this, but I’m aware that I could probably get better performance by running a
local server on the LAN shared by both devices
The desktop browser does all of the real work: it takes the orientation of the device and uses that, and the car’s current speed, to determine how it’s position changes over the time
that’s elapsed since the screen was last refreshed: we’re aiming for 60 frames a second, of course, but we don’t want the car to travel slower when the game is played on a
slower computer, so we use requestAnimationFrame to get the fastest rate possible and calculate the time between renderings to work out how much of a change has
occurred this ‘tick’. We leave the car’s sprite close to the bottom of the screen at all times but change how much it rotates from side to side, and we use it’s rotated to decide how
much of its motion is lateral versus the amount that’s “along the track”. The latter value determines how much track we move down the screen “behind” it.
The track is generated very simply by the addition of three sine waves of different offset and frequency – a form of very basic procedural generation. Despite the predictability of mathematical curves, this results in a moderately organic-feeling road
because the player only sees a fraction of the resulting curve at any given time: the illustration below shows how these three curves combine to make the resulting road. The difficulty
is ramped up the further the player has travelled by increasing the amplitude of the resulting wave (i.e. making the curves gradually more-agressive) and by making the road itself
gradually narrower. The same mathematics are used to determine whether the car is mostly on the tarmac or mostly on the grass and adjust its maximum speed accordingly.
In order to help provide a visual sense of the player’s speed, I added dashed lines down the road (dividing it into three lanes to begin with and two later on) which zip past the car
and provide a sense of acceleration, deceleration, overall speed, and the impact of turning ‘sideways’ (which of course reduces the forward momentum to nothing).
This isn’t meant to be a finished game: it’s an experimental prototype to help explore some technologies that I’d not had time to look seriously at before now. However, you’re welcome
to take a copy – it’s all open source – and adapt or expand it. Particular ways in which it’d be fun to improve it might include:
Allowing the player more control, e.g. over their accelerator and brakes
Adding hazards (trees, lamp posts, and others cars) which must be avoided
Adding bonuses like speed boosts
Making it challenging, e.g. giving time limits to get through checkpoints
Day and night cycles (with headlights!)
Multiplayer capability, like a real race?
Smarter handling of multiple simultaneous users: right now they’d share control of the car (which is the major reason I haven’t given you a live online version to play
with and you have to download it yourself!), but it’d be better if they could “queue” until it was their turn, or else each play in their own split-screen view or something
Improving the graphics with textures
Increasing the entropy of the curves used to generate the road, and perhaps adding pre-scripted scenery or points of interest on a mathematically-different procedural generation
algorithm
Switching to a local LAN websocket server, allowing better performance than the dog-leg via Firebase
Greater compatibility: I haven’t tried it on an iPhone, but I gather than iOS devices report their orientation differently from Android ones… and I’ve done nothing to try to make
Steer! handle more-unusual screen sizes and shapes
Anything else? (Don’t expect me to have time to enhance it, though: but if you do so, I’d love to hear about it!)
There’s a wonderful tool for making web-based “choose your own adventure”-type games, called Twine. One of the best things about it is that it’s so
accessible: if you wanted to, you could be underway writing your first ever story with it in about 5 minutes from now, without installing anything at all, and when it was done you could
publish it on the web and it would just work.
But the problem with Twine is that, in its latest and best versions, you’re trapped into using the Twine IDE. The Twine IDE
is an easy-to-use, highly visual, ‘drag-and-drop’ interface for making interactive stories. Which is probably great if you’re into IDEs or if you don’t “know better”… but for those of us who prefer to do our writing in a nice clean, empty text editor like Sublime or TextMate or to script/automate our builds, it’s just frustrating to lose access to the tools we love.
Plus, highly-visual IDEs make it notoriously hard to collaborate with other authors on the same work without simply passing
it back and forwards between you: unless they’ve been built with this goal in mind, you generally can’t have two people working in the same file at the same time.
Earlier versions of Twine had a command-line tool called Twee that perfectly filled this gap. But the shiny new versions don’t. That’s where I came in.
In that way that people who know me are probably used to by now, I was very-slightly unsatisfied with one aspect of an otherwise fantastic product and decided that the
correct course of action was to reimplement it myself. So that’s how, a few weeks ago, I came to release Twee2.
If you’re interested in writing your own “Choose Your Own Adventure”-type interactive fiction, whether for the world or
just for friends, but you find user-friendly IDEs like Twine limiting (or you just prefer a good old-fashioned text editor), then give Twee2 a go. I’ve written a simple 2-minute tutorial to get you
started, it works on Windows, MacOS, Linux, and just-about everything else, and it’s completely open-source if you’d like to expand or
change it yourself.
(there are further discussions about the concept and my tool on Reddit here, here, here and here, and on the Twinery forums here, here and here)
My geek-crush Ben Foxall posted on Twitter on Monday morning to share
that he’d had a moment of fun nostalgia when he’d come into the office to discover that somebody in his team had covered his monitor with two layers of Post-It notes. The bottom layer
contained numbers – and bombs! – to represent the result of a Minesweeper board, and the upper layer ‘covered’ them so that individual Post-Its could be removed to reveal what lay
beneath. Awesome.
Not to be outdone, I hunted around my office and found some mini-Post-Its. Being smaller meant that I could fit more of them onto a monitor and thus make a more-sophisticated (and
more-challenging!) play space. But how to generate the board? Sure: I could do it by hand, but that doesn’t seem very elegant at all – plus, humans make really bad random number generators! I didn’t need quantum-tunnelling-seeded Minesweeper (yes, that’s a thing) levels of entropy, sure, but it’d still be nice to outsource the heavy lifting
to a computer, right?
So naturally, I wrote a program to do it for me. Want to see? It’s at danq.me/minesweeper. Just line up some Post-Its on a co-worker’s monitor to work out
how many you can fit across it in each dimension (I found that I could get 6 × 4 standard-sized Post-Its but 7× 5 or even 8× 5 mini-sized Post-Its very comfortablyonto one of the typical widescreen monitors in my office), decide how many mines you want, and click
Generate. Don’t like the board you get? Click it again!
And because I was looking for a fresh excuse to play with Periscope, I broadcast the first game I set up live to the Internet. In the end, 66
people ended up watching some or all of a paper-based game of Minesweeper played by my colleague Liz, including moments of cheering her on
and, in one weird moment, despair at the revelation that she was married. The internet’s strange, yo.
Anyway: in case you missed the Periscope broadcast, I’ve put it on YouTube. Sorry about the portrait-orientation filming: I
think it’s awful, too, but it’s a Periscope thing and I haven’t installed the new update that
fixes it yet.
Now go set up a game of Post-It Minesweeper for a friend or co-worker.
Rust, a 2013 indie survival game from Facepunch Studios, plays like a
cross between Minecraft and Grand Theft Auto. Players find themselves “born” into a mysterious wilderness, naked and alone, forced to forage for resources and to craft
clothing, supplies and shelter for themselves. They must contend with starvation, hypothermia and animal attacks, but by far the most dangerous threat comes from other players who
roam the island.
When the game was first opened up, all players were given the same default avatar: a bald white man. With the most recent update, Rust’s lead developer, Garry Newman, introduced
different avatars of different racial origins into the mix. However, they did so with a twist — unlike typical massively multiplayer online role-playing games, Rust does not
allow players to choose the race of their avatar. Instead, they are assigned one at random. Newman
explained the change in a blog post…
What’s the hardest word to guess, when playing hangman? I’ll come back to that.
Last year, Nick Berry wrote a fantastic blog post about the optimal strategy for Hangman. He showed that the best guesses
to make to get your first “hit” in a game of hangman are not the most-commonly occurring letters in written English, because these aren’t the most commonly-occurring
letters in individual words. He also showed that the first guesses should be adjusted based on the length of the word (the most common letter in 5-letter words is ‘S’, but the most
common letter in 6-letter words is ‘E’). In short: hangman’s a more-complex game than you probably thought it was! I’d like to take his work a step further, and work out which word is
the hardest word: that is – assuming you’re playing an optimal strategy, what word takes the most-guesses?
First, though, we need to understand how hangman is perfectly played. Based on the assumption that the “executioner” player is choosing words randomly, and that no clue is given as to
the nature of the word, we can determine the best possible move for all possible states of the game by using a data structure known as a tree. Suppose our opponent has chosen a
three-letter word, and has drawn three dashes to indicate this. We know from Nick’s article that the best letter to guess is A. And then, if our guess is wrong, the next
best letter to guess is E. But what if our first guess is right? Well, then we’ve got an “A” in one or more positions on the board, and we need to work out the next best
move: it’s unlikely to be “E” – very few three-letter words have both an “A” and an “E” – and of course what letter we should guess next depends entirely on what positions
the letters are in.
What we’re actually doing here is a filtering exercise: of all of the possible letters we could choose, we’re considering what possible results that could have. Then for
each of those results, we’re considering what guesses we could make next, and so on. At each stage, we compare all of the possible moves to a dictionary of all possible
words, and filter out all of the words it can’t be: after our first guess in the diagram above, if we guess “A” and the board now shows “_ A _”, then we know that of the
600+ three-letter words in the English language, we’re dealing with one of only about 134. We further refine our guess by playing the odds: of those words, more of them have a “C” in
than any other letter, so that’s our second guess. If it has a C in, that limits the options further, and we can plan the next guess accordingly. If it doesn’t have a C
in, that still provides us with valuable information: we’re now looking for a three-letter word with an A in the second position and no letter C: that cuts it
down to 124 words (and our next guess should be ‘T’). This tree-based mechanism for working out the best moves is comparable to that used by other game-playing computers. Hangman is
simple enough that it can be “solved” by contemporary computers (like draughts –
solved in 2007 – but unlike chess: while modern chess-playing
computers can beat humans, it’s still theoretically possible to build future computers that will beat today’s computers).
Now that we can simulate the way that a perfect player would play against a truly-random executioner, we can use this to simulate games of hangman for every possible word
(I’m using version 0.7 of this British-English dictionary).
In other words, we set up two computer players: the first chooses a word from the dictionary, the second plays “perfectly” to try to guess the word, and we record how many guesses it
took. So that’s what I did. Here’s the Ruby code I used. It’s heavily-commented and
probably pretty understandable/good learning material, if you’re into that kind of thing. Or if you fancy optimising it, there’s plenty of scope for that too (I knocked it out on a
lunch break; don’t expect too much!). Or you could use it as the basis to make a playable hangman game. Go wild.
Running the program, we can see that the hardest three-letter word is “xxv”, which would take 22 guesses (20 of them wrong!) to get. But aside from the roman numeral for 25, I don’t
think that “xxv” is actually a word. Perhaps my dictionary’s not very good. “Oak”, though, is definitely a word, and at 20 guesses (17 wrong), it’s easily enough to hang your opponent
no matter how many strokes it takes to complete the gallows.
There are more tougher words in the four-letter set, like the devious “quiz”, “jazz”, “zinc”, and “faux”. Pick one of those and your opponent – unless they’ve seen this blog post! – is
incredibly unlikely to guess it before they’re swinging from a rope.
As we get into the 5, 6, and 7-letter words you’ll begin to notice a pattern: that the hardest words with any given number of letters get easier the longer
they are. That’s kind of what you’d expect, I suppose: if there were a hypothetical word that contained every letter in the alphabet, then nobody would ever fail to (eventually) get it.
When we make a graph of each word length, showing which proportion of the words require a given number of “wrong” guesses (by an optimised player), we discover a “sweet spot” window in
which we’ll find all of the words that an optimised player will always fail to guess (assuming that we permit up to 10 incorrect guesses before they’re disqualified). The
window seems small for the number of times I remember seeing people actually lose at hangman, which implies to me that human players consistently play sub-optimally, and do not
adequately counteract that failing by applying an equal level of “smart”, intuitive play (knowing one’s opponent and their vocabulary, looking for hints in the way the game is
presented, etc.).
In case you’re interested, then, here are the theoretically-hardest words to throw at your hangman opponent. While many of the words there feel like they would quite-rightly be
difficult, others feel like they’d be easier than their ranking would imply: this is probably because they contain unusual numbers of vowels or vowels in unusual-but-telling positions,
which humans (with their habit, inefficient under normal circumstances, of guessing an extended series of vowels to begin with) might be faster to guess than a
computer.
I’ve got a new favourite game, this week: Movie Title Mash-Ups (with thanks to Cougar Town). Ruth and I sat up far too late last night, playing it.
Here’s how you do it:
Movie Title Mash-Ups
Take two movie titles which share a word (or several words, or just a syllable) at the end of one and at the beginning of the other. Shmoosh them together into a combined movie title,
then describe the plot of that movie in a single sentence by borrowing elements from both component movies. See if anybody can guess what your mash-up movies were.
Here are some examples. The answers are ROT13-encoded, but if you’re reading
this post directly on
my blog, you can click on each of them to decode them (once you’ve given up!).
—
Zombies claw their way out of a graveyard, and Batman spends most of the film hiding in the attic. Gur Qnex Xavtug bs gur Yvivat Qrnq
—
While trapped in an elevator at the end of October, a superficial man is hypnotised into murdering a bunch of high-school students with knife. Funyybj Unyybjrra
—
A crazy professor and a kid travel back in time in a souped-up car, where local bully Biff cuts off the kid’s hand and tells him he’s his father. Gur Rzcver Fgevxrf Onpx gb gur Shgher
—
Bill Murray has to live the same day over and over, until he can survive the zombie apocalypse by escaping to an island. Tebhaqubt Qnl bs gur Qrnq
—
A pair of alcoholic, out-of-work actors stay at the countryside house of a Monty, dangerous robot who has learned to override his programming. Jvguanvy naq V, Ebobg
—
An evil genie who maliciously manipulates words and misinterprets wishes opens a portal between Eternia and Earth, which He-Man and Skeletor come through. Jvfuznfgref bs gur Havirefr
—
A bunch of outlawed vigilante superheroes fight shapeshifters and werewolves as they investigate a mystical curse which threatens to shatter the fragile cease-fire between Dark and
Light forces in Russia. Avtug Jngpuzra
—
Harrison Ford and Michelle Pfeiffer hold a seance to communicate with subterranean humans who worship a giant bomb. Jung Yvrf Orarngu gur Cynarg bs gur Ncrf
—
A lion cub born to a royal family grows up, climbs the Empire State Building, and fights aeroplanes. Gur Yvba Xvat Xbat
—
James Bond is sent to investigate the murder of three British MI6 agents, who turn out to have been killed using a military satellite that concentrates the sun’s rays into a
powerful laser. (hint: both films are James Bond films)
Yvir naq Yrg Qvr Nabgure Qnl