Answers.Body: <p>The bad news is that there is no simple formula for calculating the state space or state+action space here. It is relatively easy to get upper or lower bounds to it, but complex to precisely calculate. Writing a maths formula for it would look like pseudocode but written in maths notation - a procedure, rather than a simple expression.</p>
  <p>Your calcuation of <span class="math-container">$3^9$</span> is an <em>overestimate</em> of the state space (i.e. ignoring actions), based on the full gamut of the state representation. It's an overestimate because it includes many impossible unreachable states such as <code>XX_______</code> or <code>____O____</code> where the turn sequence has not been followed. You could extend this representation space analysis though, by multiplying by all 9 actions to arrive at <span class="math-container">$9 \times 3^9 = 177141$</span>. This is an upper bound on the size of your Q table. As well as impossible states, it will include incorrect state and action combinations such as <code>(____X____, 4)</code>.</p>
  <p>Another way to arrive at a strict upper bound is to count all the nodes in the game decision tree. At the start, player X must make one of 9 decisions, player O must take one of the remaining 8 etc. This leads to the upper bound of <span class="math-container">$\sum_{t=0}^8 \prod_{c=9-t}^9 c$</span> (where <span class="math-container">$c$</span> is the number of choices available at time step <span class="math-container">$t$</span>). This resolves to <span class="math-container">$986409$</span> - higher than the number of representations! That's because many of the combinations end up in the same state - action sequence <span class="math-container">$(4,5,0)$</span> is the same board as <span class="math-container">$(0,5,4)$</span>. This will also include states that continue play after <code>X</code> or <code>O</code> have won.</p>
  <p>You can refine calculations by filtering, but there is no simple formula for that, because you have to apply the game rules, including turn-taking and winning conditions, to determine whether a state and action is valid. You will need to script something that generates one of the larger upper bound sets, then filter logically.</p>
  <p>I would suggest that the easiest calculation here is to start with all possible state representations and filter as follows:</p>
  <ul>
  <li>Remove all states where count of <code>X</code> is either less than count of <code>O</code>, or is more than <span class="math-container">$1$</span> higher.</li>
  <li>Remove all states which show either <code>X</code> or <code>O</code> (or both!) completing a line, because no action is possible from those states, so they are never added to the Q table.</li>
  </ul>
  <p>Then multiply each state by the count of <code>_</code>, and sum to get number of actions, thus expected size of a completed Q table. Note this correctly assigns a count of <span class="math-container">$0$</span> for full boards for drawn games, they won't appear in the Q table (it doesn't matter if you also want to filter these out).</p>
  <p>I have tested this with a short script and obtained the number <span class="math-container">$16167$</span>. So you can have some confidence that your learning algorithm is exploring all options.</p>
  
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2024-09-20T05:21:39.340Z
Answers.Text: I would really like to see the short script you wrote to obtain the number of 16167. Would you like to publish that somewhere for others to view?
Answers.UserDisplayName: Hans123
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2024-05-21T08:18:46.080Z
Answers.LastActivityDate: 2024-05-21T09:20:30.727Z
Answers.LastEditDate: 2024-05-21T09:20:30.727Z
Answers.UserDisplayName: Neil Slater
Answers.Body: <p>Great answer from <a href="https://ai.stackexchange.com/users/1847/neil-slater">@Neil Slater</a>; however, I wanted to give my 2 cents.</p>
  <p>Even though it's called &quot;tabular&quot; q-learning, it doesn't imply that you have to use a table to access it; yes, a table might have some advantages, but there are other data structures out there</p>
  <p>In particular, you can use a map instead (key-value data structure, equivalent of a dictionary in python) where you pass some sort of &quot;string representation of your board&quot; as key, and have as value an array of N possible moves</p>
  <p>Now the question is, do we really want to save that little memory, paying the additional cost of a map, or we can live with a sparse table with entries that are never used? I'd say the latter, as it's much easier to vectorize accesses and updates of such table</p>
  <p>Furthermore, if memory is your concerns, consider that tictactoe has a ton of symmetries: you can flip the board horizontally, vertically, rotate it, and flip the entries (X instead of O and viceversa) which will definitely save a lot of memories</p>
  
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2024-05-21T11:04:02.733Z
Answers.LastActivityDate: 2024-05-21T11:04:02.733Z
Answers.UserDisplayName: Alberto
Body: <p>i implemented the tabular q-learning algorithm for 3x3 tictactoe multiple times and everytime the number of entries in the q-table is 16,167. I wanna know how to calculate the number of 16,167. what is the formula to calculate it. the q-learning-algorithm also uses all symmetries. 0,90,180,270 degree rotations, horizontal, vertical, diagonal, antidiagonal.</p>
  <p>i know that a 3x3 Tic-Tac-Toe board can be in any combination of three states (empty, X, O) across 9 positions which means that it has
  3⁹=19,683 possible configurations</p>
  <p>can anybody please help me get the formula to calculate it?</p>
  <p>1st EDIT:
  An example entry of my q-table:</p>
  <p>('_XXX_O_OO', 6): 0.9024999999999993</p>
  <p>2nd EDIT:</p>
  <pre><code>&quot;('_________', 2)&quot;: 0.06166253080818989,
  &quot;('_________', 8)&quot;: 0.06166253080818989,
  &quot;('_________', 0)&quot;: 0.06166253080818989,
  &quot;('_________', 6)&quot;: 0.06166253080818989,
  
  &quot;('_________', 3)&quot;: 0.030324239570976224,
  &quot;('_________', 7)&quot;: 0.030324239570976224,
  &quot;('_________', 5)&quot;: 0.030324239570976224,
  &quot;('_________', 1)&quot;: 0.030324239570976224,
  
  &quot;('_________', 4)&quot;: 0.15534933785554575,
  </code></pre>
  <p>I save the board and all of its symmetries inside the q-table.</p>
  <p>3rd EDIT:</p>
  <p>my update_q_table function:</p>
  <pre><code>def update_q_table(
      board,
      action,
      reward,
      new_board,
      alpha,
      gamma,
      future_value,
  ):
      global Q_TABLE_DICT
      symmetric_states_and_actions = generate_symmetric_states_and_actions(board, action)
  
      old_value = Q_TABLE_DICT.get((board, action), 0)
  
      if game_over(new_board):
          # If it's a terminal state, there are no future rewards to consider
          next_max = 0
      else:
          next_max = future_value
      temporal_difference = reward + (gamma * next_max) - old_value
      new_q_value = old_value + (alpha * temporal_difference)
      # print(new_q_value)
      # Update the Q-value for the current state-action pair and its symmetric states
      for symmetric_state, symmetric_action in symmetric_states_and_actions:
          Q_TABLE_DICT[(symmetric_state, symmetric_action)] = new_q_value
  
      return new_q_value
  </code></pre>
  
Comments.ContentLicense: CC BY-SA 4.0
Comments.CreationDate: 2024-05-20T10:20:09.057Z
Comments.Text: This is going to depend on the representation and approach you used. For example, are you using state-only representation, or state/action? Please share the representation used in your Q table. Use [edit] to add it to the question
Comments.UserDisplayName: Neil Slater
Comments.ContentLicense: CC BY-SA 4.0
Comments.CreationDate: 2024-05-20T10:24:13.910Z
Comments.Text: I added an example entry of my q-table
Comments.UserDisplayName: Hans123
Comments.ContentLicense: CC BY-SA 4.0
Comments.CreationDate: 2024-05-20T10:28:22.377Z
Comments.Text: Thank you. That's not quite what I expected, so I am not quite sure how you are normalising by symmetry. Assuming you start with `_________` and agent is selecting actions in $[0,8]$, the agent could play actions 1, 3, 5 or 7 which all result in the "same" board. How is that resolved? I.e. how is the canonical next state decided out of `_X_______`, `___X_____`, `_____X___` and `_______X_`?
Comments.UserDisplayName: Neil Slater
Comments.ContentLicense: CC BY-SA 4.0
Comments.CreationDate: 2024-05-20T10:36:01.947Z
Comments.Text: Are you searching for existing entries that match by trying all possible transformations?
Comments.UserDisplayName: Neil Slater
Comments.ContentLicense: CC BY-SA 4.0
Comments.CreationDate: 2024-05-20T10:38:55.240Z
Comments.Text: I added 2nd and 3rd EDIT. Do these answer your questions?
Comments.UserDisplayName: Hans123
Comments.ContentLicense: CC BY-SA 4.0
Comments.CreationDate: 2024-05-20T10:44:53.320Z
Comments.Text: > Are you searching for existing entries that match by trying all possible transformations? – No, but lookup in the dictionary via the (board, action) tuple.
Comments.UserDisplayName: Hans123
Comments.ContentLicense: CC BY-SA 4.0
Comments.CreationDate: 2024-05-20T10:45:45.703Z
Comments.Text: Looks like you are instead *storing* all possible combinations, and using the symmetry to manage table updates? Oddly enough, that makes the calculation _easier_, because your symmetry handling is not changing the count at all :-)
Comments.UserDisplayName: Neil Slater
Comments.ContentLicense: CC BY-SA 4.0
Comments.CreationDate: 2024-05-20T10:49:28.613Z
Comments.Text: > Looks like you are instead storing all possible combinations, and using the symmetry to manage table updates? - Yes
Comments.UserDisplayName: Hans123
Comments.ContentLicense: CC BY-SA 4.0
Comments.CreationDate: 2024-05-20T10:54:06.680Z
Comments.Text: cuz, i didn't know how to use canonical states for a (board, action) tuple. for minimax algorithm it worked fine, cuz I only had the board as key and either -1,0,1 (rewards) as value. but here i have a tuple of board,action.
Comments.UserDisplayName: Hans123
Comments.ContentLicense: CC BY-SA 4.0
Comments.CreationDate: 2024-05-20T11:52:39.310Z
Comments.Text: please, let me know if you have any ideas how to get to the 16,167 :)
Comments.UserDisplayName: Hans123
Tags: <reinforcement-learning><q-learning><tic-tac-toe>
Title: tic-tac-toe - tabular q-learning - what is the formula to calculate the number of entries in the q-table
UserDisplayName: Hans123
ThreadText: # tic-tac-toe - tabular q-learning - what is the formula to calculate the number of entries in the q-table
  
  (Asked by: username_0 on 2024-05-20)
  
  i implemented the tabular q-learning algorithm for 3x3 tictactoe multiple times and everytime the number of entries in the q-table is 16,167. I wanna know how to calculate the number of 16,167. what is the formula to calculate it. the q-learning-algorithm also uses all symmetries. 0,90,180,270 degree rotations, horizontal, vertical, diagonal, antidiagonal.
  
  i know that a 3x3 Tic-Tac-Toe board can be in any combination of three states (empty, X, O) across 9 positions which means that it has
  3⁹=19,683 possible configurations
  
  can anybody please help me get the formula to calculate it?
  
  1st EDIT:
  An example entry of my q-table:
  
  ('\_XXX\_O\_OO', 6): 0.9024999999999993
  
  2nd EDIT:
  
  ```
  "('_________', 2)": 0.06166253080818989,
  "('_________', 8)": 0.06166253080818989,
  "('_________', 0)": 0.06166253080818989,
  "('_________', 6)": 0.06166253080818989,
  
  "('_________', 3)": 0.030324239570976224,
  "('_________', 7)": 0.030324239570976224,
  "('_________', 5)": 0.030324239570976224,
  "('_________', 1)": 0.030324239570976224,
  
  "('_________', 4)": 0.15534933785554575,
  
  ```
  
  I save the board and all of its symmetries inside the q-table.
  
  3rd EDIT:
  
  my update\_q\_table function:
  
  ```
  def update_q_table(
      board,
      action,
      reward,
      new_board,
      alpha,
      gamma,
      future_value,
  ):
      global Q_TABLE_DICT
      symmetric_states_and_actions = generate_symmetric_states_and_actions(board, action)
  
      old_value = Q_TABLE_DICT.get((board, action), 0)
  
      if game_over(new_board):
          # If it's a terminal state, there are no future rewards to consider
          next_max = 0
      else:
          next_max = future_value
      temporal_difference = reward + (gamma * next_max) - old_value
      new_q_value = old_value + (alpha * temporal_difference)
      # print(new_q_value)
      # Update the Q-value for the current state-action pair and its symmetric states
      for symmetric_state, symmetric_action in symmetric_states_and_actions:
          Q_TABLE_DICT[(symmetric_state, symmetric_action)] = new_q_value
  
      return new_q_value
  
  ```
  
  **Tags:** reinforcement-learning, q-learning, tic-tac-toe
  
  > **Comments:**
  > **username_1**: This is going to depend on the representation and approach you used. For example, are you using state-only representation, or state/action? Please share the representation used in your Q table. Use [edit] to add it to the question  
  > **username_0**: I added an example entry of my q-table  
  > **username_1**: Thank you. That's not quite what I expected, so I am not quite sure how you are normalising by symmetry. Assuming you start with `_________` and agent is selecting actions in $[0,8]$, the agent could play actions 1, 3, 5 or 7 which all result in the "same" board. How is that resolved? I.e. how is the canonical next state decided out of `_X_______`, `___X_____`, `_____X___` and `_______X_`?  
  > **username_1**: Are you searching for existing entries that match by trying all possible transformations?  
  > **username_0**: I added 2nd and 3rd EDIT. Do these answer your questions?  
  > **username_0**: > Are you searching for existing entries that match by trying all possible transformations? – No, but lookup in the dictionary via the (board, action) tuple.  
  > **username_1**: Looks like you are instead *storing* all possible combinations, and using the symmetry to manage table updates? Oddly enough, that makes the calculation _easier_, because your symmetry handling is not changing the count at all :-)  
  > **username_0**: > Looks like you are instead storing all possible combinations, and using the symmetry to manage table updates? - Yes  
  > **username_0**: cuz, i didn't know how to use canonical states for a (board, action) tuple. for minimax algorithm it worked fine, cuz I only had the board as key and either -1,0,1 (rewards) as value. but here i have a tuple of board,action.  
  > **username_0**: please, let me know if you have any ideas how to get to the 16,167 :)  
  
  ---
  
  ## 2 answers
  
  ### Answer by username_1 on 2024-05-21. Score: 1 | Accepted answer
  
  The bad news is that there is no simple formula for calculating the state space or state+action space here. It is relatively easy to get upper or lower bounds to it, but complex to precisely calculate. Writing a maths formula for it would look like pseudocode but written in maths notation - a procedure, rather than a simple expression.
  
  Your calcuation of $3^9$ is an *overestimate* of the state space (i.e. ignoring actions), based on the full gamut of the state representation. It's an overestimate because it includes many impossible unreachable states such as `XX_______` or `____O____` where the turn sequence has not been followed. You could extend this representation space analysis though, by multiplying by all 9 actions to arrive at $9 \times 3^9 = 177141$. This is an upper bound on the size of your Q table. As well as impossible states, it will include incorrect state and action combinations such as `(____X____, 4)`.
  
  Another way to arrive at a strict upper bound is to count all the nodes in the game decision tree. At the start, player X must make one of 9 decisions, player O must take one of the remaining 8 etc. This leads to the upper bound of $\sum\_{t=0}^8 \prod\_{c=9-t}^9 c$ (where $c$ is the number of choices available at time step $t$). This resolves to $986409$ - higher than the number of representations! That's because many of the combinations end up in the same state - action sequence $(4,5,0)$ is the same board as $(0,5,4)$. This will also include states that continue play after `X` or `O` have won.
  
  You can refine calculations by filtering, but there is no simple formula for that, because you have to apply the game rules, including turn-taking and winning conditions, to determine whether a state and action is valid. You will need to script something that generates one of the larger upper bound sets, then filter logically.
  
  I would suggest that the easiest calculation here is to start with all possible state representations and filter as follows:
  
  * Remove all states where count of `X` is either less than count of `O`, or is more than $1$ higher.
  * Remove all states which show either `X` or `O` (or both!) completing a line, because no action is possible from those states, so they are never added to the Q table.
  
  Then multiply each state by the count of `_`, and sum to get number of actions, thus expected size of a completed Q table. Note this correctly assigns a count of $0$ for full boards for drawn games, they won't appear in the Q table (it doesn't matter if you also want to filter these out).
  
  I have tested this with a short script and obtained the number $16167$. So you can have some confidence that your learning algorithm is exploring all options.
  
  > **Comments:**
  > **username_0**: I would really like to see the short script you wrote to obtain the number of 16167. Would you like to publish that somewhere for others to view?  
  
  ---
  
  ### Answer by username_2 on 2024-05-21. Score: 1
  
  Great answer from [@username_1](https://ai.stackexchange.com/users/1847/username_1); however, I wanted to give my 2 cents.
  
  Even though it's called "tabular" q-learning, it doesn't imply that you have to use a table to access it; yes, a table might have some advantages, but there are other data structures out there
  
  In particular, you can use a map instead (key-value data structure, equivalent of a dictionary in python) where you pass some sort of "string representation of your board" as key, and have as value an array of N possible moves
  
  Now the question is, do we really want to save that little memory, paying the additional cost of a map, or we can live with a sparse table with entries that are never used? I'd say the latter, as it's much easier to vectorize accesses and updates of such table
  
  Furthermore, if memory is your concerns, consider that tictactoe has a ton of symmetries: you can flip the board horizontally, vertically, rotate it, and flip the entries (X instead of O and viceversa) which will definitely save a lot of memories
  
  
  ---
  
  