I made a completely free Scrabble-like game!
Pretty much all the online Scrabble games I’ve played are bloated, ad-ridden, gamified things that need sign-ups and stuff to play. I hate all this. I just want to play games without all the crud.
I make simple web apps. So why can’t I make a Scrabble clone?
And I did! It’s still early days. Things don’t work or are broken. There are things it doesn’t do right. But this is kinda playable right now. Before you let me know things are broken please see if I already know about it.
Sure, this is not the BEST Scrabble clone. But it’s free, needs no sign up, has no ads. There are no catches. I just use Fathom Analytics to collect minimal, anonymised usage stats. That’s it! You can just play!
But there’s something about it that the computer nerds will find interesting. I think. Read on if you want to know how this works because a static-file, multiplayer game without a login or database… how does that work?
How DOES it work?
Ages ago I heard a thing on a podcast, and I can’t even remember what it was, that made me wonder if you could have an online, multi-player, turn-based game where the game state is encoded in URLs and you just swap URLs with other people using messaging to take turns.
You could prove this with something very simple like tic-tac-toe. But that seemed TOO simple. And I love word games. So Scrabble seemed to be a reasonable step up.
What you are about to read is a technical deep-dive on encoding Scrabble games in URLs. This is kinda computer-sciencey stuff including binary representations of data, bitwise operations, and JavaScript “BigInts”. I hope it’s interesting to someone!
Aside: Scrabble(TM) is owned by Mattel and Hasbro and they have enforced their copyright over some aspects of the game in the past, so I’m cautious about naming it and using anything of the game that may be copyrighted.
Computer Science – a quick primer on binary representations
We don’t talk a lot about “bits” in web development. The high-level languages we use, the speed of processing, and the memory we have available in computers nowadays means we don’t have to think about it much. But I want to do something super efficient here, so I’m turning to binary encoding.
Under the hood, our computers use binary – 0’s and 1’s to represent data.
Whole numbers usually translate pretty directly. Zero is 0 in binary. Eight is 1000. Thirteen is 1101. I won’t go into why here. But bigger numbers take up more bits.
Boolean “true/false” values can be represented in just a single bit!
Letters and characters? Well, they are also converted to numbers. Numbers are really all that we’ve got. And computers use standardised codes for this. Major standards for encoding text are ASCII and Unicode (sometimes known as UTF).
ASCII is pretty simple. Each character is given a number that fits into, say, 7 bits. 7 bits gives you numbers up to 128. That lets you have lower case and upper case Latin alphabet that we use for English, digits 0-9 and still have 66 slots for punctuation and other stuff.
Aside: This is fine for English, but in the global world there’s a huge number of other characters we might want to use, and Unicode includes all sorts of non-Latin characters and all the emoji!
But what if you don’t need punctuation? In Scrabble you only need single-case letters (and blanks) on your tiles. That’s 27 options. And 27 options fit into just 5 bits. So can we just do that?
Of course you can!
In fact, if you know what the “shape” of your data is, you can really efficiently “encode” it in Binary.
I’m going to propose, below, that data for a “player” in Scrabble is:
- A score that is a number between 0 and 1000
- A “rack” of tiles, that is a list of 7 letters
We know this data “shape”. So if we can somehow manipulate individual bits we can store a player as a single string of bits. 10 bits for the score. And 5 bits for each letter. 45 bits in total.
This then raises questions though. Like, what if a player is at the end of the game and only has 4 tiles? Well, we can either use one of the spare (not-a-letter) 5-bit values to mean “empty”. OR… we could add another bit of data that says how many letters there are and only store those letters. The number 7 can be represented in 3 bits (111) so a player could be:
- A score that is a number between 0 and 1000 (10 bits)
- A count of the number of tiles in the rack (3 bits)
- A “rack” of tiles, that is a list of up to 7 letters (5 bits each)
There’s a trade off here. If we have 7 letters then we’re adding 3 bits for the count.
But if we have less than 7 letters, we save at least 2 bits (5 fewer bits for a letter, but 3 added for the count). A player with just one tile saves 27 bits!
This is all super-nerdy stuff. But hopefully you see what I’m trying to do here.
There is an issue though, and that’s that the languages we use on the web don’t necessarily make it easy to work with individual bits. I’ll come back to this later.
In the meantime, given we know we can use bits in this way, how can we represent a Scrabble game?
If you think this is all very interesting then I can highly recommend Julia Evan’s “Zine” (small-comic-book format) called “How Integers and Floats Work“, and you can tinker with binary codes and numbers using her simple integer.exposed tool.
Minimal Scrabble game representations
I started by wondering what the smallest way to represent a Scrabble-like game was. I don’t want URLs to get too long as I pass the game state around. So how can I do this efficiently?
Things you COULD store are:
The board.
This is a 15×15 square grid where each square can be empty or contain a letter.
A letter can be one of 26 things, or a blank (which is different to empty!). If we do a minimal binary representation, this fits into 5 bits.
Representing the whole board would take up up to 1,125 bits. That 161, 7-bit ASCII characters.
Could you compress this? Maybe by encoding multiple empty spaces somehow? Maybe. But that gets complicated.
What else do we need?
The Players
Players have a tile rack – that’s up to 7 lots of 5-bits-per-tile. So 35 bits.
Players also have a score. That could be up to 1000, so let’s give that 10 bits.
I’ll ignore names for now. I think we can do without that. Is that it? I think it is, as moves will be separate.
So a player can be up to 45 bits each. That’s 7, 7-bit ASCII characters.
The Tile Bag
You could choose to store the tile bag. There are 100 tiles, so this would be 100 * 5 = 500 bits.
That’s another 72, 7-bit ASCII characters.
Summing up, if you were to store data in this way: board state, player state and tile bag, that’s a total of 1,715 bits, or 245 characters. Not bad I suppose.
There may be some efficiencies to be gained somewhere. But it would either:
- Be very minimal on average; or
- Add complexity to the encoding
But it feels like there’s some data duplication here. Perhaps we can do better?
Alternative: Store the Moves
Rather than storing the board and the player scores, we could just store a list of moves. This may be more efficient. But it may also be hard to tell.
A list of moves can be “played back” onto the board to get player scores and the board state.
You also don’t need to maintain a tile bag. The “full bag” minus all the used tiles (in players hands or on the board) gives you the tiles remaining. You can shuffle them whenever you like. You don’t have to keep the original shuffled order – that doesn’t affect the game.
So what does a move look like? It can be tricky because a move can “wrap” around other letters or words on the board.
There’s three options:
- Combine a starting point co-ordinate on the board with the entire word played. Oh, you’ll need a flag to say if it’s across or down too. For a 5-letter word, this would be 2 * 4-bit co-ordinates, a 1-bit flag, and 5 * 5-bit tiles. That’s 34 bits in total for a 5-letter word.
- Same as 1, but you only store the played tiles, and you skip existing tiles when you replay moves onto the board. That might reduce the storage from option 1 by a bit (for some moves, by a LOT!)
- Have a list of played tiles, each with their coordinates. This would be 2 * 4-bit co-ordinates and a 5-bit tile per letter played. So 13 bits per letter, or 65 bits for a 5-letter word.
Option 3 seems inefficient, especially for longer words.
Option 2, in hindsight seems best. But I didn’t consider it at the time.
So I went with option 1.
The internet says that the average number of words played in a game seems to be between 16 and 22 per player. It feels like a low-move game would have longer words. There’s 100 tiles. A 34-move game averages very close to 3 tiles per move. So that’s 8 + 1 + (3 * 5) = 24 bits per move, and 34 * 24 = 816 bits for an average-looking game.
This is better than storing a 1,125-bit board. It will vary per game, but we’ve reduced the ASCII character representation to 117 characters from 161. That’s pretty good.
A conclusion on game storage
So a minimal data set is:
- Array of moves at 5n + 9 bits per move and an average-looking game using around 816 bits.
- Player tile “racks” at 5 * 7 = 35 bits each. 70 bits total.
That’s it. Everything else – the board, the tile bag, the scores, can all be derived from this.
Is this the most efficient way? I wouldn’t really know without some experimentation or writing some complicated formulae. There may be games where another encoding works better. But this seems good to me.
Working with bits in JavaScript
As I said before, it’s not entirely easy working with individual bits in modern web development languages.
I’m making a Scrabble-like web app, so JavaScript is the language I have to hand.
JavaScript does provide operators for working with bits. But the difficulty is that its types are more abstract/high level. And the JavaScript Number type doesn’t directly map whole numbers into Binary. All numbers in JavaScript are actually “floating point”, which means they are stored in a complicated format that’s suitable for both whole numbers (“integers”) and decimal numbers.
HOWEVER… while I was thinking about this I remembered that JavaScript has a “BigInt” type for storing “Big Integers”. This sounds good. We need integers really.
And BigInt’s support binary (“bitwise”) operators like shifts (which move binary numbers left and right) and logical AND / OR. These are exactly what we need, and it seems that a BigInt is almost unlimited in size, and so a single BigInt can represent a Player, a Move, or an entire game!!
This is exactly what I need.
And just to note again, if you think this is all very interesting then I can highly recommend Julia Evan’s “Zine” (small-comic-book format) called “How Integers and Floats Work“, and you can tinker with binary codes and numbers using her simple integer.exposed tool.
A small library class for bitwise manipulation of BigInts
The BigInt’s worked out GREAT!
But I found myself doing a lot of what I called “push” and “pop”, of bits like with Arrays. Like, “Here’s a number that’s less than 15. It’s 3 bits long. Please “push” it onto the right-hand side of my BigInt.
(A push “left shifts” the bits of the BigInt to the left and then does a logical OR to add the new bits on. A pull does a logical “AND” of the BigInt with a mask like 1111111 to get the popped value, and then “right shifts” the BigInt to move everything along.)
Abstracting this made my encoding and decoding work much easier. And I included functions/methods to convert the BigInt to and from both ASCII (7 bits at a time!) and then also into Base64, which can be sent in a URL! YAY!
You can see that little helper class in this Gist.
Making the game work
With all that binary data representation done, I could get on with building the game.
It turns out that complex game UI and logic can be a bit tricky. I’ve got the game to a state where it works in it’s basic form. It’s playable. And that’s great.
I could write a whole other post about all the user interface concerns and algorithms for doing stuff.
I mean, it’s not hard hard. It’s not Tears of the Kingdom or Call of Duty. But for a little web-based side-project? There’s been a lot to think about.
Right now I’m doing some simple play testing of the mechanic of sending links back and forth. Interestingly, most of the feedback I’ve had has either been about Scrabble stuff that I’ve not implemented yet, or about the UI. No one has really complained that sending links back and forth over messenger is annoying. So that’s good.
Why not give it a go? It’s at https://words.pico.games/, and it’s totally free.
Let me know what you think, but be sure to check GitHub issues before you report anything to see if I already know about it.
Enjoy!