Answers.Body: <p>The primary issue I see is that in the loop through time steps <code>t</code> in every training episode, you select <strong>actions for both players</strong> (who should have <strong>opposing goals</strong> to each other), but update <strong>a single <code>q_table</code></strong> (which can only ever be correct for the &quot;perspective&quot; of one of your two players) on <strong>both of those actions</strong>, and updating both of them using <strong>a single, shared reward function</strong>.</p>
  <p>Intuitively, I guess this means that your learning algorithm assumes that your opponent will always be helping you win, rather than assuming that your opponent plays optimally towards its own goals. You can see that this is likely indeed the case from your plot; you use <span class="math-container">$30,000$</span> training episodes, split up into <span class="math-container">$15$</span> chunks of <span class="math-container">$2,000$</span> episodes per chunk for your plot. In your plot, you also very quickly reach a score of about <span class="math-container">$1,950$</span> per chunk, which is almost the maximum possible! Now, I'm not 100% sure what the winrate of an optimal player against random would be, but I think it's likely that that should be lower than 1950 out of 2000. Random players will occasionally achieve draws in Tic-Tac-Toe, especially taking into consideration that your learning agent itself is also not playing optimally (but <span class="math-container">$\epsilon$</span>-greedily)!</p>
  <hr />
  <p>You should instead pick one of the following solutions (maybe there are more solutions, this is just what I come up with on the spot):</p>
  <ol>
  <li>Keep track of <strong>two different tables</strong> of <span class="math-container">$Q$</span>-values for the two different players, and update each of them only on <strong>half of the actions</strong> (each of them pretending that actions selected by the opponent are just stochastic state transitions created by &quot;the environment&quot; or &quot;the world&quot;). See <a href="https://ai.stackexchange.com/a/10033/1641">this answer for more on what these scheme would look like</a>.</li>
  <li>Only keep track of a <span class="math-container">$Q$</span>-value for your own agent (again only updating it on half the actions as described above -- specifically only on the actions your agent actually selected). Actions by the opposing player should then NOT be selected based on those same <span class="math-container">$Q$</span>-values, but instead by some different approach. You could for instance have opposing actions selected by a minimax or alpha-beta pruning search algorithm. Maybe selecting them to <strong>minimise</strong> instead of <strong>maximise</strong> values from the same <span class="math-container">$Q$</span>-table could also work (didn't think this idea fully through, not 100% sure). You probably could also just pick opponent actions randomly, but then your agent will only learn to play well against random opponents, not necessarily against strong opponents.</li>
  </ol>
  <hr />
  <p>After looking into the above suggestions, you'll probably also want to look into making sure that your agent experiences games in which it starts as Player 1, as well as games in which it starts as Player 2, and trains for both of those possible scenarios and learns how to handle both of them. In your evaluation code (after training), I believe that you always make the Random opponent play first, and the trained agent play second? If you don't cover this scenario in your training episodes, your agent may not learn how to properly handle it.</p>
  <hr />
  <p>Finally, a couple of small notes:</p>
  <ul>
  <li>Your discount factor <span class="math-container">$\gamma 0.1$</span> has an extremely small value. Common values in literature are values like <span class="math-container">$\gamma = 0.9$</span>, <span class="math-container">$\gamma = 0.95$</span>, or even <span class="math-container">$\gamma = 0.99$</span>. Tic-Tac-Toe episodes tend to always be very short anyway, and we tend to not care too much about winning quickly rather than winning slowly (a win's a win), so I would tend to use a high value like <span class="math-container">$\gamma = 0.99$</span>.</li>
  <li>A small programming tip, not really AI-specific: your code contains various conditions of the form <code>if &lt;condition&gt; == True :</code>, like: <code>if done == True :</code>. The <code>== True</code> part is redundant, and these conditions can be written more simply as just <code>if done:</code>.</li>
  </ul>
  
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2021-09-04T04:54:15.977Z
Answers.Text: I have an answer to your question: what is the optimal score against a random player.  See here:  https://ai.stackexchange.com/questions/31536/what-is-the-optimal-score-for-tic-tac-toe-for-a-reinforcement-learning-agent-aga/31537#31537
Answers.UserDisplayName: Yan King Yin
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2020-06-30T18:57:13.583Z
Answers.LastActivityDate: 2020-06-30T18:57:13.583Z
Answers.UserDisplayName: Dennis Soemers
Body: <p>q learning is defined as:</p>
  <p><a href="https://i.sstatic.net/sMDdm.png" rel="nofollow noreferrer"><img src="https://i.sstatic.net/sMDdm.png" alt="enter image description here" /></a></p>
  <p>Here is my implementation of q learning of the tic tac toe problem:</p>
  <pre><code>import timeit
  from operator import attrgetter
  import time
  import matplotlib.pyplot
  import pylab
  from collections import Counter
  import logging.handlers
  import sys
  import configparser
  import logging.handlers
  import unittest
  import json, hmac, hashlib, time, requests, base64
  from requests.auth import AuthBase
  from pandas.io.json import json_normalize
  from multiprocessing.dummy import Pool as ThreadPool
  import threading
  import time
  from statistics import mean 
  import statistics as st
  import os   
  from collections import Counter
  import matplotlib.pyplot as plt
  from sklearn import preprocessing
  from datetime import datetime
  import datetime
  from datetime import datetime, timedelta
  import matplotlib.pyplot as plt
  import matplotlib.ticker as ticker
  import matplotlib
  import numpy as np
  import pandas as pd
  from functools import reduce
  from ast import literal_eval
  import unittest
  import math
  from datetime import date, timedelta
  import random
  
  today = datetime.today()
  model_execution_start_time = str(today.year)+&quot;-&quot;+str(today.month)+&quot;-&quot;+str(today.day)+&quot; &quot;+str(today.hour)+&quot;:&quot;+str(today.minute)+&quot;:&quot;+str(today.second)
  
  epsilon = .1
  discount = .1
  step_size = .1
  number_episodes = 30000
  
  def epsilon_greedy(epsilon, state, q_table) : 
      
      def get_valid_index(state):
          i = 0
          valid_index = []
          for a in state :          
              if a == '-' :
                  valid_index.append(i)
              i = i + 1
          return valid_index
      
      def get_arg_max_sub(values , indices) : 
          return max(list(zip(np.array(values)[indices],indices)),key=lambda item:item[0])[1]
      
      if np.random.rand() &lt; epsilon:
          return random.choice(get_valid_index(state))
      else :
          if state not in q_table : 
              q_table[state] = np.array([0.0,0.0,0.0,0.0,0.0,0.0,0.0,0.0,0.0])
          q_row = q_table[state]
          return get_arg_max_sub(q_row , get_valid_index(state))
      
  def make_move(current_player, current_state , action):
      if current_player == 'X':
          return current_state[:action] + 'X' + current_state[action+1:]
      else : 
          return current_state[:action] + 'O' + current_state[action+1:]
  
  q_table = {}
  max_steps = 9
  
  def get_other_player(p):
      if p == 'X':
          return 'O'
      else : 
          return 'X'
      
  def win_by_diagonal(mark , board):
      return (board[0] == mark and board[4] == mark and board[8] == mark) or (board[2] == mark and board[4] == mark and board[6] == mark)
      
  def win_by_vertical(mark , board):
      return (board[0] == mark and board[3] == mark and board[6] == mark) or (board[1] == mark and board[4] == mark and board[7] == mark) or (board[2] == mark and board[5] == mark and board[8]== mark)
  
  def win_by_horizontal(mark , board):
      return (board[0] == mark and board[1] == mark and board[2] == mark) or (board[3] == mark and board[4] == mark and board[5] == mark) or (board[6] == mark and board[7] == mark and board[8] == mark)
  
  def win(mark , board):
      return win_by_diagonal(mark, board) or win_by_vertical(mark, board) or win_by_horizontal(mark, board)
  
  def draw(board):
      return win('X' , list(board)) == False and win('O' , list(board)) == False and (list(board).count('-') == 0)
  
  s = []
  rewards = []
  def get_reward(state):
      reward = 0
      if win('X' ,list(state)):
          reward = 1
          rewards.append(reward)
      elif draw(state) :
          reward = -1
          rewards.append(reward)
      else :
          reward = 0
          rewards.append(reward)
          
      return reward
  
  def get_done(state):
      return win('X' ,list(state)) or win('O' , list(state)) or draw(list(state)) or (state.count('-') == 0)
      
  reward_per_episode = []
              
  reward = []
  def q_learning():
      for episode in range(0 , number_episodes) :
          t = 0
          state = '---------'
  
          player = 'X'
          random_player = 'O'
  
  
          if episode % 1000 == 0:
              print('in episode:',episode)
  
          done = False
          episode_reward = 0
              
          while t &lt; max_steps:
  
              t = t + 1
  
              action = epsilon_greedy(epsilon , state , q_table)
  
              done = get_done(state)
  
              if done == True : 
                  break
  
              if state not in q_table : 
                  q_table[state] = np.array([0.0,0.0,0.0,0.0,0.0,0.0,0.0,0.0,0.0])
  
              next_state = make_move(player , state , action)
              reward = get_reward(next_state)
              episode_reward = episode_reward + reward
              
              done = get_done(next_state)
  
              if done == True :
                  q_table[state][action] = q_table[state][action] + (step_size * (reward - q_table[state][action]))
                  break
  
              next_action = epsilon_greedy(epsilon , next_state , q_table)
              if next_state not in q_table : 
                  q_table[next_state] = np.array([0.0,0.0,0.0,0.0,0.0,0.0,0.0,0.0,0.0])
  
              q_table[state][action] = q_table[state][action] + (step_size * (reward + (discount * np.max(q_table[next_state]) - q_table[state][action])))
  
              state = next_state
  
              player = get_other_player(player)
              
          reward_per_episode.append(episode_reward)
  
  q_learning()
  </code></pre>
  <p>The alogrithm player is assigned to 'X' while the other player is 'O':</p>
  <pre><code>    player = 'X'
      random_player = 'O'
  </code></pre>
  <p>The reward per episode:</p>
  <pre><code>plt.grid()
  plt.plot([sum(i) for i in np.array_split(reward_per_episode, 15)])
  </code></pre>
  <p>renders:
  <a href="https://i.sstatic.net/p3Jyj.png" rel="nofollow noreferrer"><img src="https://i.sstatic.net/p3Jyj.png" alt="enter image description here" /></a></p>
  <p>Playing the model against an opponent making random moves:</p>
  <pre><code>## Computer opponent that makes random moves against trained RL computer opponent
  # Random takes move for player marking O position
  # RL agent takes move for player marking X position
  
  def draw(board):
      return win('X' , list(board)) == False and win('O' , list(board)) == False and (list(board).count('-') == 0)
  
  x_win = []
  o_win = []
  draw_games = []
  number_games = 50000
  
  c = []
  o = []
  
  for ii in range (0 , number_games):
      
      if ii % 10000 == 0 and ii &gt; 0:
          print('In game ',ii)
          print('The number of X game wins' , sum(x_win))
          print('The number of O game wins' , sum(o_win))
          print('The number of drawn games' , sum(draw_games))
  
      available_moves = [0,1,2,3,4,5,6,7,8]
      current_game_state = '---------'
      
      computer = ''
      random_player = ''
      
      computer = 'X'
      random_player = 'O'
  
      def draw(board):
          return win('X' , list(board)) == False and win('O' , list(board)) == False and (list(board).count('-') == 0)
          
      number_moves = 0
      
      for i in range(0 , 5):
  
          randomer_move = random.choice(available_moves)
          number_moves = number_moves + 1
          current_game_state = current_game_state[:randomer_move] + random_player + current_game_state[randomer_move+1:]
          available_moves.remove(randomer_move)
  
          if number_moves == 9 : 
              draw_games.append(1)
              break
          if win('O' , list(current_game_state)) == True:
              o_win.append(1)
              break
          elif win('X' , list(current_game_state)) == True:
              x_win.append(1)
              break
          elif draw(current_game_state) == True:
              draw_games.append(1)
              break
              
          computer_move_pos = epsilon_greedy(-1, current_game_state, q_table)
          number_moves = number_moves + 1
          current_game_state = current_game_state[:computer_move_pos] + computer + current_game_state[computer_move_pos+1:]
          available_moves.remove(computer_move_pos)
       
          if number_moves == 9 : 
              draw_games.append(1)
  #             print(current_game_state)
              break
              
          if win('O' , list(current_game_state)) == True:
              o_win.append(1)
              break
          elif win('X' , list(current_game_state)) == True:
              x_win.append(1)
              break
          elif draw(current_game_state) == True:
              draw_games.append(1)
              break
  </code></pre>
  <p>outputs:</p>
  <pre><code>In game  10000
  The number of X game wins 4429
  The number of O game wins 3006
  The number of drawn games 2565
  In game  20000
  The number of X game wins 8862
  The number of O game wins 5974
  The number of drawn games 5164
  In game  30000
  The number of X game wins 13268
  The number of O game wins 8984
  The number of drawn games 7748
  In game  40000
  The number of X game wins 17681
  The number of O game wins 12000
  The number of drawn games 10319
  </code></pre>
  <p>The reward per episode graph suggests the algorithm has converged? If the model has converged shouldnt the number of O game wins be zero ?</p>
  
Tags: <reinforcement-learning><python><q-learning><game-ai><combinatorial-games>
Title: q learning appears to converge but does not always win against random tic tac toe player
UserDisplayName: blue-sky
ThreadText: # q learning appears to converge but does not always win against random tic tac toe player
  
  (Asked by: username_0 on 2020-06-26)
  
  q learning is defined as:
  
  [![enter image description here](https://i.sstatic.net/sMDdm.png)](https://i.sstatic.net/sMDdm.png)
  
  Here is my implementation of q learning of the tic tac toe problem:
  
  ```
  import timeit
  from operator import attrgetter
  import time
  import matplotlib.pyplot
  import pylab
  from collections import Counter
  import logging.handlers
  import sys
  import configparser
  import logging.handlers
  import unittest
  import json, hmac, hashlib, time, requests, base64
  from requests.auth import AuthBase
  from pandas.io.json import json_normalize
  from multiprocessing.dummy import Pool as ThreadPool
  import threading
  import time
  from statistics import mean 
  import statistics as st
  import os   
  from collections import Counter
  import matplotlib.pyplot as plt
  from sklearn import preprocessing
  from datetime import datetime
  import datetime
  from datetime import datetime, timedelta
  import matplotlib.pyplot as plt
  import matplotlib.ticker as ticker
  import matplotlib
  import numpy as np
  import pandas as pd
  from functools import reduce
  from ast import literal_eval
  import unittest
  import math
  from datetime import date, timedelta
  import random
  
  today = datetime.today()
  model_execution_start_time = str(today.year)+"-"+str(today.month)+"-"+str(today.day)+" "+str(today.hour)+":"+str(today.minute)+":"+str(today.second)
  
  epsilon = .1
  discount = .1
  step_size = .1
  number_episodes = 30000
  
  def epsilon_greedy(epsilon, state, q_table) : 
      
      def get_valid_index(state):
          i = 0
          valid_index = []
          for a in state :          
              if a == '-' :
                  valid_index.append(i)
              i = i + 1
          return valid_index
      
      def get_arg_max_sub(values , indices) : 
          return max(list(zip(np.array(values)[indices],indices)),key=lambda item:item[0])[1]
      
      if np.random.rand() < epsilon:
          return random.choice(get_valid_index(state))
      else :
          if state not in q_table : 
              q_table[state] = np.array([0.0,0.0,0.0,0.0,0.0,0.0,0.0,0.0,0.0])
          q_row = q_table[state]
          return get_arg_max_sub(q_row , get_valid_index(state))
      
  def make_move(current_player, current_state , action):
      if current_player == 'X':
          return current_state[:action] + 'X' + current_state[action+1:]
      else : 
          return current_state[:action] + 'O' + current_state[action+1:]
  
  q_table = {}
  max_steps = 9
  
  def get_other_player(p):
      if p == 'X':
          return 'O'
      else : 
          return 'X'
      
  def win_by_diagonal(mark , board):
      return (board[0] == mark and board[4] == mark and board[8] == mark) or (board[2] == mark and board[4] == mark and board[6] == mark)
      
  def win_by_vertical(mark , board):
      return (board[0] == mark and board[3] == mark and board[6] == mark) or (board[1] == mark and board[4] == mark and board[7] == mark) or (board[2] == mark and board[5] == mark and board[8]== mark)
  
  def win_by_horizontal(mark , board):
      return (board[0] == mark and board[1] == mark and board[2] == mark) or (board[3] == mark and board[4] == mark and board[5] == mark) or (board[6] == mark and board[7] == mark and board[8] == mark)
  
  def win(mark , board):
      return win_by_diagonal(mark, board) or win_by_vertical(mark, board) or win_by_horizontal(mark, board)
  
  def draw(board):
      return win('X' , list(board)) == False and win('O' , list(board)) == False and (list(board).count('-') == 0)
  
  s = []
  rewards = []
  def get_reward(state):
      reward = 0
      if win('X' ,list(state)):
          reward = 1
          rewards.append(reward)
      elif draw(state) :
          reward = -1
          rewards.append(reward)
      else :
          reward = 0
          rewards.append(reward)
          
      return reward
  
  def get_done(state):
      return win('X' ,list(state)) or win('O' , list(state)) or draw(list(state)) or (state.count('-') == 0)
      
  reward_per_episode = []
              
  reward = []
  def q_learning():
      for episode in range(0 , number_episodes) :
          t = 0
          state = '---------'
  
          player = 'X'
          random_player = 'O'
  
          if episode % 1000 == 0:
              print('in episode:',episode)
  
          done = False
          episode_reward = 0
              
          while t < max_steps:
  
              t = t + 1
  
              action = epsilon_greedy(epsilon , state , q_table)
  
              done = get_done(state)
  
              if done == True : 
                  break
  
              if state not in q_table : 
                  q_table[state] = np.array([0.0,0.0,0.0,0.0,0.0,0.0,0.0,0.0,0.0])
  
              next_state = make_move(player , state , action)
              reward = get_reward(next_state)
              episode_reward = episode_reward + reward
              
              done = get_done(next_state)
  
              if done == True :
                  q_table[state][action] = q_table[state][action] + (step_size * (reward - q_table[state][action]))
                  break
  
              next_action = epsilon_greedy(epsilon , next_state , q_table)
              if next_state not in q_table : 
                  q_table[next_state] = np.array([0.0,0.0,0.0,0.0,0.0,0.0,0.0,0.0,0.0])
  
              q_table[state][action] = q_table[state][action] + (step_size * (reward + (discount * np.max(q_table[next_state]) - q_table[state][action])))
  
              state = next_state
  
              player = get_other_player(player)
              
          reward_per_episode.append(episode_reward)
  
  q_learning()
  
  ```
  
  The alogrithm player is assigned to 'X' while the other player is 'O':
  
  ```
      player = 'X'
      random_player = 'O'
  
  ```
  
  The reward per episode:
  
  ```
  plt.grid()
  plt.plot([sum(i) for i in np.array_split(reward_per_episode, 15)])
  
  ```
  
  renders:
  [![enter image description here](https://i.sstatic.net/p3Jyj.png)](https://i.sstatic.net/p3Jyj.png)
  
  Playing the model against an opponent making random moves:
  
  ```
  ## Computer opponent that makes random moves against trained RL computer opponent
  # Random takes move for player marking O position
  # RL agent takes move for player marking X position
  
  def draw(board):
      return win('X' , list(board)) == False and win('O' , list(board)) == False and (list(board).count('-') == 0)
  
  x_win = []
  o_win = []
  draw_games = []
  number_games = 50000
  
  c = []
  o = []
  
  for ii in range (0 , number_games):
      
      if ii % 10000 == 0 and ii > 0:
          print('In game ',ii)
          print('The number of X game wins' , sum(x_win))
          print('The number of O game wins' , sum(o_win))
          print('The number of drawn games' , sum(draw_games))
  
      available_moves = [0,1,2,3,4,5,6,7,8]
      current_game_state = '---------'
      
      computer = ''
      random_player = ''
      
      computer = 'X'
      random_player = 'O'
  
      def draw(board):
          return win('X' , list(board)) == False and win('O' , list(board)) == False and (list(board).count('-') == 0)
          
      number_moves = 0
      
      for i in range(0 , 5):
  
          randomer_move = random.choice(available_moves)
          number_moves = number_moves + 1
          current_game_state = current_game_state[:randomer_move] + random_player + current_game_state[randomer_move+1:]
          available_moves.remove(randomer_move)
  
          if number_moves == 9 : 
              draw_games.append(1)
              break
          if win('O' , list(current_game_state)) == True:
              o_win.append(1)
              break
          elif win('X' , list(current_game_state)) == True:
              x_win.append(1)
              break
          elif draw(current_game_state) == True:
              draw_games.append(1)
              break
              
          computer_move_pos = epsilon_greedy(-1, current_game_state, q_table)
          number_moves = number_moves + 1
          current_game_state = current_game_state[:computer_move_pos] + computer + current_game_state[computer_move_pos+1:]
          available_moves.remove(computer_move_pos)
       
          if number_moves == 9 : 
              draw_games.append(1)
  #             print(current_game_state)
              break
              
          if win('O' , list(current_game_state)) == True:
              o_win.append(1)
              break
          elif win('X' , list(current_game_state)) == True:
              x_win.append(1)
              break
          elif draw(current_game_state) == True:
              draw_games.append(1)
              break
  
  ```
  
  outputs:
  
  ```
  In game  10000
  The number of X game wins 4429
  The number of O game wins 3006
  The number of drawn games 2565
  In game  20000
  The number of X game wins 8862
  The number of O game wins 5974
  The number of drawn games 5164
  In game  30000
  The number of X game wins 13268
  The number of O game wins 8984
  The number of drawn games 7748
  In game  40000
  The number of X game wins 17681
  The number of O game wins 12000
  The number of drawn games 10319
  
  ```
  
  The reward per episode graph suggests the algorithm has converged? If the model has converged shouldnt the number of O game wins be zero ?
  
  **Tags:** reinforcement-learning, python, q-learning, game-ai, combinatorial-games
  
  
  ---
  
  ## 1 answers
  
  ### Answer by username_1 on 2020-06-30. Score: 5 | Accepted answer
  
  The primary issue I see is that in the loop through time steps `t` in every training episode, you select **actions for both players** (who should have **opposing goals** to each other), but update **a single `q_table`** (which can only ever be correct for the "perspective" of one of your two players) on **both of those actions**, and updating both of them using **a single, shared reward function**.
  
  Intuitively, I guess this means that your learning algorithm assumes that your opponent will always be helping you win, rather than assuming that your opponent plays optimally towards its own goals. You can see that this is likely indeed the case from your plot; you use $30,000$ training episodes, split up into $15$ chunks of $2,000$ episodes per chunk for your plot. In your plot, you also very quickly reach a score of about $1,950$ per chunk, which is almost the maximum possible! Now, I'm not 100% sure what the winrate of an optimal player against random would be, but I think it's likely that that should be lower than 1950 out of 2000. Random players will occasionally achieve draws in Tic-Tac-Toe, especially taking into consideration that your learning agent itself is also not playing optimally (but $\epsilon$-greedily)!
  
  ---
  
  You should instead pick one of the following solutions (maybe there are more solutions, this is just what I come up with on the spot):
  
  1. Keep track of **two different tables** of $Q$-values for the two different players, and update each of them only on **half of the actions** (each of them pretending that actions selected by the opponent are just stochastic state transitions created by "the environment" or "the world"). See [this answer for more on what these scheme would look like](https://ai.stackexchange.com/a/10033/1641).
  2. Only keep track of a $Q$-value for your own agent (again only updating it on half the actions as described above -- specifically only on the actions your agent actually selected). Actions by the opposing player should then NOT be selected based on those same $Q$-values, but instead by some different approach. You could for instance have opposing actions selected by a minimax or alpha-beta pruning search algorithm. Maybe selecting them to **minimise** instead of **maximise** values from the same $Q$-table could also work (didn't think this idea fully through, not 100% sure). You probably could also just pick opponent actions randomly, but then your agent will only learn to play well against random opponents, not necessarily against strong opponents.
  
  ---
  
  After looking into the above suggestions, you'll probably also want to look into making sure that your agent experiences games in which it starts as Player 1, as well as games in which it starts as Player 2, and trains for both of those possible scenarios and learns how to handle both of them. In your evaluation code (after training), I believe that you always make the Random opponent play first, and the trained agent play second? If you don't cover this scenario in your training episodes, your agent may not learn how to properly handle it.
  
  ---
  
  Finally, a couple of small notes:
  
  * Your discount factor $\gamma 0.1$ has an extremely small value. Common values in literature are values like $\gamma = 0.9$, $\gamma = 0.95$, or even $\gamma = 0.99$. Tic-Tac-Toe episodes tend to always be very short anyway, and we tend to not care too much about winning quickly rather than winning slowly (a win's a win), so I would tend to use a high value like $\gamma = 0.99$.
  * A small programming tip, not really AI-specific: your code contains various conditions of the form `if <condition> == True :`, like: `if done == True :`. The `== True` part is redundant, and these conditions can be written more simply as just `if done:`.
  
  > **Comments:**
  > **username_2**: I have an answer to your question: what is the optimal score against a random player.  See here:  https://ai.stackexchange.com/questions/31536/what-is-the-optimal-score-for-tic-tac-toe-for-a-reinforcement-learning-agent-aga/31537#31537  
  
  ---
  
  