q learning appears to converge but does not always win against random tic tac toe player

Question

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 ?

Answer 1

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