<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>

CC BY-SA 4.0
2021-09-04T04:54:15.977Z
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
Yan King Yin
CC BY-SA 4.0
2020-06-30T18:57:13.583Z
2020-06-30T18:57:13.583Z
Dennis Soemers
<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>

<reinforcement-learning><python><q-learning><game-ai><combinatorial-games>
q learning appears to converge but does not always win against random tic tac toe player
blue-sky
# 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:

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:

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  == 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  

---

