Gaming with LaTeX: PDF-based Tic-tac-toe
19 Oct 2020Why aren’t there games written in LaTeX? In this post, I am exploring ways to include an (rather weak) AI in a PDF-based tic-tac-toe game, with the help of LaTeX. The results can be found in the folloing repo:
https://github.com/xziyue/tictactoe-pdf
Exhausting all states of tic-tac-toe
Being a simple process itself, the game of tic-tac-toe has a really small number of possible states. This repo provides an efficient C++ program to enumerate all valid states of tic-tac-toe and determine the winner of each state. According to the output, there are only 5478 valid games states.
If we are writing an AI for tic-tac-toe, we are essentially looking for an optimal transition of states to maximize the win rate of the AI players. More concretely, at the \(i\)th step, a player makes a move, which generates tic-tac-toe board state \(S^{i+1}\). It is obvious that \(S^0\) is the blank tic-tac-toe board; when \(i\) is odd, it is human player’s turn; when \(i\) is even, it is AI’s turn. All \(S^i\)’s are included in 5478 game states.
Therefore, the goal of the AI is to find best \(S^{2k}\)s, provided with all possible \(S^{2k-1}\)s, so that the chances of winning are maximized. Since all possible states and their corresponding winners are already known, the win rate of each AI’s move can be easily computed. As a result, it is fairly to write a naive AI.
The AI is implemented in Python, and the end result is a collection of states (\(S^{2k}\)), where each state is associated with a jump table to \(S^{2k+2}\), provided with human user’s input (\(S^{2k+1}\)). The Python program will generate the LaTeX source file for compilation.
Drawing tic-tac-toe board with LaTeX
The board drawing functionality is implemented with LaTeX3. The outcome is the
\drawtictactoe function, where:
- Argument 1 is the indices of \(\times\)s
- Argument 2 is the indices of \(\bigcirc\)s
- Argument 3 is the jump table for each human user’s move. It will be passed
to
\prop_set_from_keyval:Nnto generate a dictionary structure in LaTeX. The keys are each possible human player’s move; the values are the labels of the next states associated with the move.
An example usage of the macro:
\drawtictactoe{1,8}{0,7}{2=state141,3=state142,4=state143,5=state144,6=state145}