Categories
Artificial Intelligence (AI) Mastering Development

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

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 ?

Leave a Reply

Your email address will not be published. Required fields are marked *