If you ever attended a boring lecture, you probably know this game by heart. Frequently scribbled on textbook margins and school desks, it’s insanely popular and fun to play. Talking to a friend about MySQL made me wonder if such a respectable, high performance database can be misused and tricked into being a gaming platfom. While it isn’t likely going to run Quake, maybe a simple game of Tic-Tac-Toe would be just right.
Why would anyone do this? Well, making floppy drives play The Imperial March isn’t very useful either, but it’s darn entertaining. MySQL is a powerful tool with strong scripting capabilities and Turing complete as well, so implementing this game in a single player mode is possible.
First, we need a board. To keep things simple, we’ll keep it as a 9 letter string - matrix element with position (1,1) will be the first element, then element (1,2) and so on .
After defining something to store and describe the board in, we declare AI is using ‘o’ and the player will be playing with ‘x’. Underscores are used to represent unclaimed fields. Since MySQL isn’t Perl or Python, we’ll have to improvise a little and create a function to check what’s placed on the board at a specific (row,column) position.
This is a good time to talk about the AI. Taking the classic approach isn’t something you do when coding for fun, so I decided to do something different. When doing something weird in a database engine, why not use it in your advantage? Basic combinatorics tells us each field can be either ‘o’, ‘x’ or empty, and there are 9 fields so that’s 39 = 19,683 possible board positions. Also, many positions are invalid - you can’t have all x’s because players take turns, you can’t play after you’ve lost etc. so the real number of valid board is much smaller (it’s 5477).
Game theory teaches us Tic-Tac-Toe can never actually be won if you pick optimal moves, so we’ll run it once to generate a tree of best computer moves given a certain position, store it permanently in the database, and use it to defeat the puny human.
Each optimal move for a certain position will be stored as a table row along with its predecessor’s id, so we can look it up and know where to move.
If you ever saw Wargames, you probably remember the scene where the kid saves the world by making the computer play Tic-Tac-Toe with itself. The same thing is done here (minus saving the world part). Computer plays both sides, but when impersonating a human it checks all moves, not just the best one, because a human might make a mistake. To determine the best move, a recursive minimax algorithm is used, checking long-term consequence of a move (‘move’ function) and choosing the one with a best outcome.
This python algorithm is ran only once; it recursively traverses the moves tree and inserts nodes as database rows. Our database could also be imported from external file, effectively eliminating any external dependencies, even if they are only a one-time thing. A single database row also contains state flags to determine if the game is over or not.
Making it fancy
That’s all nice, it works, but one more thing… can we make it 3D, just for fun? Mysql can execute shell commands, but apparently you can’t pipe anything through shell scripts. Let’s use a trick - very often it produces long, long tables, and to facilitate looking at the data you can set a pager - something it will pipe your output through, like less or your favorite editor. Why not using that and piping it through … figlet! One apt-get install figlet later, finding a cool looking 3d font and a little sed to strip everything not important and we’re left with this.
mysql>pagersed-e's/| ta | bli | ca |//g'-e's/ \+/ /g'-e's/[+\-]//g'-e'/^$/d'|figlet-f'larry3d.flf'mysql>callplace_x(2,3);