Answers.Body: <p>In the case of TicTacToe, you can make use of game theory. The entire search space can be denoted by a <a href="https://en.wikipedia.org/wiki/Game_tree" rel="nofollow noreferrer">game tree</a>. You bot must now be able to maximize the chance of winning.</p>
  
  <p>You can make use of the <a href="https://en.wikipedia.org/wiki/Minimax#Minimax_algorithm_with_alternate_moves" rel="nofollow noreferrer">Maximin algorithm</a>. This is still computationally intensive on large search spaces. To improve the efficiency <a href="https://en.wikipedia.org/wiki/Alpha%E2%80%93beta_pruning" rel="nofollow noreferrer">Alpha-Beta pruning</a> can be applied to reduce the number of nodes in the Game tree.</p>
  
  <p>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.</p>
  
  <p>You can have a look at <a href="https://www.freecodecamp.org/news/how-to-make-your-tic-tac-toe-game-unbeatable-by-using-the-minimax-algorithm-9d690bad4b37/" rel="nofollow noreferrer">this</a> to build a TicTacToe bot.</p>
  
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2020-03-30T08:36:17.830Z
Answers.Text: Thank you. Would you also suggest the Maximin algorithm for games with even larger state space; for example, Chess?
Answers.UserDisplayName: mason7663
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2020-03-30T09:10:04.163Z
Answers.Text: 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.
Answers.UserDisplayName: skillsmuggler
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2020-03-30T11:35:38.550Z
Answers.Text: Thank you. When you say too many possibilities, do you mean too many states / too large of a state space? Then, if the different pieces with their respective movement rules causes too many states, how about a game like Connect Four, where the pieces all follow the same movement rules? Could Minimax be used for that, or is the state space too large for that too? If so, what alternatives could be used?
Answers.UserDisplayName: mason7663
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2020-03-30T11:55:12.860Z
Answers.Text: 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](https://en.wikipedia.org/wiki/Deep_Blue_(chess_computer)) should give you an idea of the complexity of the task.
Answers.UserDisplayName: skillsmuggler
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2020-03-30T11:57:44.527Z
Answers.Text: 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.
Answers.UserDisplayName: skillsmuggler
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2020-04-01T20:21:04.770Z
Answers.Text: Thank you. How do you know what Minimax can and can't be used for? What's the state space 'cut off' for Minimax?
Answers.UserDisplayName: mason7663
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2020-04-02T07:38:38.050Z
Answers.Text: 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.
Answers.UserDisplayName: skillsmuggler
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2020-03-30T08:29:26.700Z
Answers.LastActivityDate: 2020-03-30T08:29:26.700Z
Answers.UserDisplayName: skillsmuggler
Answers.Body: <blockquote>
  <p>I was reading online that tic-tac-toe has a state space of <span class="math-container">$3^9 = 19,683$</span>. From my basic understanding, this sounds too large to use tabular Q-learning, as the Q table would be huge. Is this correct?</p>
  </blockquote>
  <p>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.</p>
  <p>So it is definitely possible to use tabular Q learning here. I have done just that whilst learning about RL - <a href="https://github.com/neilslater/game_playing_scripts/blob/master/tictactoe_q.py" rel="nofollow noreferrer">my Q-learning Tic Tac Toe agent is written in Python and available on Github</a>. 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 <a href="https://stats.stackexchange.com/questions/411932/reinforcement-learning-afterstate-and-afterstate-value-functions">afterstate values</a> instead of action values.</p>
  <blockquote>
  <p>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?</p>
  </blockquote>
  <p>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:</p>
  <ul>
  <li><p>Forward planning or search algorithms, as mentioned by <a href="https://ai.stackexchange.com/a/19870/1847">skillsmuggler in their answer</a>. 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.</p>
  <ul>
  <li>Other planning algorithms include Negamax (a minor variation of Minimax for zero-sum games) and MCTS (famously used in Alpha Go).</li>
  </ul>
  </li>
  <li><p>Policy function improvement, which generate policies - maps of current state to actions - and have ways to assess them and select better policies.</p>
  <ul>
  <li>Q learning, and the many algorithms of reinforcement learning are in this category, as well as genetic algorithms.</li>
  <li>Tic Tac Toe is simple enough that you could hard-code a policy function that mapped any state to the next action. The <a href="https://xkcd.com/832/" rel="nofollow noreferrer">xkcd webcomic encoded this policy into a diagram</a>.</li>
  </ul>
  </li>
  </ul>
  <p>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.</p>
  
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2021-04-24T10:30:39.823Z
Answers.LastActivityDate: 2021-04-25T10:48:03.233Z
Answers.LastEditDate: 2021-04-25T10:48:03.233Z
Answers.UserDisplayName: Neil Slater
Body: <p>I was reading online that tic-tac-toe has a state space of <span class="math-container">$3^9 = 19,683$</span>. From my basic understanding, this sounds too large to use tabular Q-learning, as the Q table would be huge. Is this correct?</p>
  <p>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?</p>
  
Tags: <reinforcement-learning><q-learning><algorithm-request><tic-tac-toe><zero-sum-games>
Title: Non-Neural Network algorithms for large state space in zero sum games
UserDisplayName: mason7663
ThreadText: # Non-Neural Network algorithms for large state space in zero sum games
  
  (Asked by: username_0 on 2020-03-29)
  
  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?
  
  **Tags:** reinforcement-learning, q-learning, algorithm-request, tic-tac-toe, zero-sum-games
  
  
  ---
  
  ## 2 answers
  
  ### Answer by username_2 on 2021-04-24. Score: 2 | Accepted answer
  
  > 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](https://github.com/username_2/game_playing_scripts/blob/master/tictactoe_q.py). 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](https://stats.stackexchange.com/questions/411932/reinforcement-learning-afterstate-and-afterstate-value-functions) 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 [username_1 in their answer](https://ai.stackexchange.com/a/19870/1847). 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](https://xkcd.com/832/).
  
  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 by username_1 on 2020-03-30. Score: 0
  
  In the case of TicTacToe, you can make use of game theory. The entire search space can be denoted by a [game tree](https://en.wikipedia.org/wiki/Game_tree). You bot must now be able to maximize the chance of winning.
  
  You can make use of the [Maximin algorithm](https://en.wikipedia.org/wiki/Minimax#Minimax_algorithm_with_alternate_moves). This is still computationally intensive on large search spaces. To improve the efficiency [Alpha-Beta pruning](https://en.wikipedia.org/wiki/Alpha%E2%80%93beta_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](https://www.freecodecamp.org/news/how-to-make-your-tic-tac-toe-game-unbeatable-by-using-the-minimax-algorithm-9d690bad4b37/) to build a TicTacToe bot.
  
  > **Comments:**
  > **username_0**: Thank you. Would you also suggest the Maximin algorithm for games with even larger state space; for example, Chess?  
  > **username_1**: 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.  
  > **username_0**: Thank you. When you say too many possibilities, do you mean too many states / too large of a state space? Then, if the different pieces with their respective movement rules causes too many states, how about a game like Connect Four, where the pieces all follow the same movement rules? Could Minimax be used for that, or is the state space too large for that too? If so, what alternatives could be used?  
  > **username_1**: 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](https://en.wikipedia.org/wiki/Deep_Blue_(chess_computer)) should give you an idea of the complexity of the task.  
  > **username_1**: 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.  
  > **username_0**: Thank you. How do you know what Minimax can and can't be used for? What's the state space 'cut off' for Minimax?  
  > **username_1**: 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.  
  
  ---
  
  