There is a theoretical and implementational field ‘Game Theory’ (GT), originating in the 1940s, concerned with ‘games’: situations where players interact with each other and possibly some other objects in a very formalised way, gaining individual ‘pay-offs’ when the ‘game’ ends. Tic-Tac-Toe is a so-called ‘2-person zero-sum game’ and GT is concerned with what are the optimum player strategies and whether they can be algorithmically computed.
Another theoretical and and implementational field is ‘Reinforcement Learning‘ (RL), which is nearly as old and addresses so-called ‘Markov Decision Processes‘, where an ‘agent‘ takes ‘actions‘ in a reactive ‘environment‘ which changes it’s ‘state’ and earns ‘rewards‘, and is concerned with what are the optimum agent policies and whether they can be algorithmically computed.
Here are some thoughts on projects that could be pursued in this area
According to GT, there is an ‘optimal’ way to play any 2-person zero-sum game — a pair of so-called ‘maximin’ strategies — computable by the ‘minimax’ algorithm, not intractably for Chess, but feasibly for Tic-Tac-Toe. One way to bring RL into game playing takes any given opponent strategy and constructs an MDP where the opponent is absorbed in the MDP’s ‘environment’ and one can see what optimal policies are found by various RL algorithms (eg. Q-learning, SARSA, Policy Gradient).
Does the RL-defined optimal policy replicate the GT-defined optimal strategy (bearing in mind that they are computed very differently) ? [ the feasibility of minimax for Tic-Tac-Toe allows this to be empirically tested in a way not possible for a larger game ]
Does the RL-defined optimal policy depend on the chosen MDP-defining opponent strategy? Is it possible that the RL-defined optimum is actually better than the GT-derived ‘optimum’ and can learn to exploit a somehow ‘weak’ opponent?
One can consider other games — Tic-Tac-Toe’s optimum gives draw-at-worst guarantees to both players, but this is not the case for all 2-person zero-sum games
One can consider which RL algorithms used in this way for game playing obey realistic constraints faced by a human being seeking to learn to play well eg. some maybe unrealistically omniscient.
There are a number of approaches under the heading of ‘self-play’, sharing an aspiration to commence ‘tabula rasa’ with no expertise at all and to somehow learn strong or optimal play by alternating a learner/teacher role in rounds of RL ( this is an area likely to depart from theoretical guarantees )
For tackling games with larger state spaces than Tic-Tac-Toe, there are various approaches which attempt to by-pass intractably large tables indexed by discrete values with ‘function approximation’ and numerical encodings of the discrete values, and these could be explored. One could also see how such approaches fare on smaller, tractable cases such as Tic-Tac-Toe.
Classical RL algorithms deliver deterministic policies and its arguably the case that realism (not necessarily confined to games) for various reasons argues for non-deterministic policies and one could look at proposals that have been made in that direction.
The SARSA algorithm (see the ‘cliff walking’ example 6.6 p132 Sutton & Barto) is a so-called ‘on policy’ variant of the so-called ‘off policy’ Q-Learning algorithm, differing in looking ahead in its update mechanism not to a ‘greedy’ max_a Q(s,a) value, but instead to an ‘eps-greedy’ Q(s,a) value which is max_a Q(s.a) with prob (1 – eps) and is rand_a Q(s,a) with prob eps, so anticipating future ‘exploratory’ behaviour.