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

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?

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.

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.

• Thank you. Would you also suggest the Maximin algorithm for games with even larger state space; for example, Chess? – mason7663 Mar 30 '20 at 8:36
• No. The Miaximin algorithm requires the entire search space to be properly defined. Incase of chess this is not possible as there are too many possibilities. This is also due to the fact that the different pieces follow different movement rules. This is the main reason why developing chess agents is very challenging. – skillsmuggler Mar 30 '20 at 9:10
• In the case of chess, yes the search space is too large. Both in terms of space complexity and time complexity. Have a look at this should give you an idea of the complexity of the task. – skillsmuggler Mar 30 '20 at 11:55
• For connect 4, you can consider it to be a relatively small search space. This again depends on the computing resources. For connect 4 you can make use of Minimax. – skillsmuggler Mar 30 '20 at 11:57
• It's an algorithm. In theory it can be used for all 0/1 games. The threshold is determined by your computing resources. A larger state space requires more resources. If you have them available, you can make use of Minimax. In case of chess, even super computers do not have enough computing power to implement Minimax. – skillsmuggler Apr 2 '20 at 7:38