Non-Neural Network algorithms for large state space in zero sum games

Question

I was reading online that tic-tac-toe has a state space of $3^9 = 19,683$. From my basic understanding, this sounds too large to use tabular Q-learning, as the Q table would be huge. Is this correct?

If that is the case, can you suggest other (non-NN) algorithms I could use to create a TTT bot to play against a human player?

Answer 1

I was reading online that tic-tac-toe has a state space of $3^9 = 19,683$. From my basic understanding, this sounds too large to use tabular Q-learning, as the Q table would be huge. Is this correct?

That is a relatively small number of states that can easily be represented in a table on a modern computer. For a Q table, you would multiply by the number of moves possible in each state, but this is still a small amount of memory. Even with the most naive implementation that tracked impossible states and state/action pairs, using string state representations (so 10 bytes for each state/action key), and using double precision floating point for each action value (another 8 bytes), the full table would be around 3 megabytes in size.

So it is definitely possible to use tabular Q learning here. I have done just that whilst learning about RL - my Q-learning Tic Tac Toe agent is written in Python and available on Github. There are many ways to optimise the required space, e.g. only representing reachable states. Also in games with perfect control (moves directly result in a new state), it is common to use afterstate values instead of action values.

If that is the case, can you suggest other (non-NN) algorithms I could use to create a tic-tac-toe agent to play against a human player?

It is not the case, as explained. However, there are two basic approaches at the top level that are worth learning about for working with game trees:

• Forward planning or search algorithms, as mentioned by skillsmuggler in their answer. These use game rules plus a heuristic (measure of likely success) to explore the future states of the game and pick the search result with the best heuristic. Minimax with a heuristic only based on win/lose at the end is a very basic approach, but would cope just fine with Tic Tac Toe.

  • Other planning algorithms include Negamax (a minor variation of Minimax for zero-sum games) and MCTS (famously used in Alpha Go).

• Policy function improvement, which generate policies - maps of current state to actions - and have ways to assess them and select better policies.

  • Q learning, and the many algorithms of reinforcement learning are in this category, as well as genetic algorithms.
  • Tic Tac Toe is simple enough that you could hard-code a policy function that mapped any state to the next action. The xkcd webcomic encoded this policy into a diagram.

These two approaches are complementary, in that both can be used together to solve more sophisticated problems. For instance, value-based reinforcement learning algorithms - including Q learning - can be used to provide learned heuristics for a search algorithm. The categories I suggest above are not strict either, in that some algorithms are not clearly one thing or another.

Answer 2

In the case of TicTacToe, you can make use of game theory. The entire search space can be denoted by a game tree. You bot must now be able to maximize the chance of winning.

You can make use of the Maximin algorithm. This is still computationally intensive on large search spaces. To improve the efficiency Alpha-Beta pruning can be applied to reduce the number of nodes in the Game tree.

These are core AI concepts and will always perform better than neural networks on dully defined and relatively smaller search spaces. Neural networks perform better when it's too difficult to compute all the possible combinations of a game at a certain state.

You can have a look at this to build a TicTacToe bot.