A short one today. ^^
Some time ago, I read this article on an implementation of Snake in pure HTML by GrahamTheDev. The basic idea is that the game state is “stored” in the URL. Each URL renders that specific game state. That way, you could theoretically make all the actual game logic completely static. Now, in the Snake example they didn’t do that, as the space of possible game states is just waaaay too large. However, I thought this might be possible for a simpler game.
Game And Game States
The simplest game I could think of is Tic-tac-toe. Given that I recently met someone who didn’t actually know the game, let me give you a quick run-down:
It’s a game for two players, X and O. The playing field is a 3×3 grid. The starting player (usually X) places their symbol in any of the 9 squares. Then the other player places their symbol on any square that’s not yet occupied. This repeats until either a player gets 3 of their symbols in a row, or there are no more free squares – a draw.
A space of all possible games has a cardinality of 
. (This is an upper bound, as it assumes that there is no win condition.) We can reduce this by only considering unique positions instead of games. Put differently: We can get rid of the implicit game history encoded in the state. An upper bound of the cardinality of unique positions is 
. Still a lot, but we are getting into manageable territory.
Another thing we can do to reduce the game state space, is to make the second player (O) an engine. By encoding the engine response in the game state, we can get rid of a bunch of board states that can never be reached. An upper bound for the number of unique games using this method is 
.
By eliminating duplicate positions with different histories – as mentioned earlier – we can further reduce the number of possible states. In the end, we are left with 
possible game states – a totally reasonable number of HTML files. (This is the actual number that plopped out of my solution. However, I’m pretty sure this could theoretically be improved further by forcing the engine to reuse states as much as possible. If you manage to find an optimal solution, please let me know. ^^)
Solving The Game
(I just lost The Game.)
The calculation above assumes we have a Tic-tac-toe engine, so let’s build one. There are existing strategies that can just about always force a draw. However, I felt like implementing existing strategies is cheating. So I decided to implement a proper minimax algorithm to search for the optimal move. Probably a bit overkill, but since the calculations are done ahead of time, it doesn’t impact the actual game play at all.
Usually, when building game AIs, you’d use heuristics to bound the search and discard unfavorable branches early. However, since the search tree of Tic-tac-toe is so tiny, we can actually get away with brute-forcing everything.
The implementation looks something like this:
Find all possible moves. For each move, calculate the future board state. If that state is a win, use that move. If the future board state is a draw or a loss, save it for later and check the next move. Else, evaluate the best move for the opponent via recursion. If the chosen opponent move leads to a loss for them, use that move, else save it for later. Once all possible moves are evaluated, and none lead to a win, use any of the saved moves – preferably one that leads to a draw.
It should be noted that this approach assumes that the player will always make the best possible move. Put another way: The engine doesn’t use tactics – it’s pure computation.
The Result
Needless to say, I didn’t write 443 HTML files by hand. Instead, I wrote a Python script that calculates all possible game states and generates the HTML files. (Someone on the Fediverse actually called me a cheater for doing so. Not entirely sure how to respond to that, to be honest. 😅)
The source code is 279 lines. The generated output is ~ 240 KiB of HTML. (The HTML is a bit larger than technically necessary because there is additional stuff in there, like a link to the repo, and some taunts that are displayed when the game is not yet over, but the player is guaranteed to lose.)
You can find the source code over on GitHub. Yes, I know the code is messy, there are a bunch of things I should probably clean up. I thought, since the focus is on the game and not on the generator script, it would not be worth it.
The actual game is hosted on bunny.net: https://html-tictactoe.b-cdn.net/
Conclusion
Although this project was rather fun, I wasn’t sure if it’s worth writing an article about it. Now that the article is finished, I’m glad I did – it turned out better than I thought it would. ^^
Anyway, I hope you enjoyed it! In case you are in the mood for more HTML, check out my article on why HTML is a programming language.
See you soon,
Sigma