I am trying to build a DQN to play tic tac toe but I just cannot get it to convergence. I tried both convolutional and fully connected feed forward networks but I just cant get the network to master the game. I measure the performance by letting the agent play against a random player and check the win percentage of the random player. It should converge to zero, but I cannot get it below 30%. Can someone maybe check the code, if I implemented something incorrectly? I would be so thankful, I don’t know how many hours I spent on hyperparameter search now…
Here is my code:
import numpy as np
import random
import matplotlib.pyplot as plt
import pickle

import torch
import torch.nn as nn
torch.manual_seed(0)


# returns new state
def play_move(st, player, move):
    state_copy = st.copy()
    while state_copy[move] != 0:
        move = int(input('This space is already occupied! Choose again: ')) - 1
    state_copy[move] = player
    return state_copy


# returns winner, game status (Done, Not Done, Draw)
def check_result(st):
    # check horizontal
    if st[0] == st[1] == st[2] and st[0] != 0:
        return st[0], 'Done'
    if st[3] == st[4] == st[5] and st[3] != 0:
        return st[3], 'Done'
    if st[6] == st[7] == st[8] and st[6] != 0:
        return st[6], 'Done'

    # check vertical
    if st[0] == st[3] == st[6] and st[0] != 0:
        return st[0], 'Done'
    if st[1] == st[4] == st[7] and st[1] != 0:
        return st[1], 'Done'
    if st[2] == st[5] == st[8] and st[2] != 0:
        return st[2], 'Done'

    # check diagonal
    if st[0] == st[4] == st[8] and st[0] != 0:
        return st[0], 'Done'
    if st[2] == st[4] == st[6] and st[2] != 0:
        return st[2], 'Done'

    # check for draw
    if st.count(0) == 0:
        return None, 'Draw'

    # otherwise
    return None, 'Not Done'


# prints board
def print_board(st):
    state_copy = st.copy()
    for i , symbol in enumerate(state_copy):
        if symbol == 0:
            state_copy[i] = ' '
        elif symbol == 1:
            state_copy[i] = 'X'
        elif symbol == -1:
            state_copy[i] = 'O'

    print('  ' + str(state_copy[0]) + ' | ' + str(state_copy[1]) + ' | ' + str(state_copy[2]) + '  ')
    print('-------------')
    print('  ' + str(state_copy[3]) + ' | ' + str(state_copy[4]) + ' | ' + str(state_copy[5]) + '  ')
    print('-------------')
    print('  ' + str(state_copy[6]) + ' | ' + str(state_copy[7]) + ' | ' + str(state_copy[8]) + '  ')


class CNN(nn.Module):
    def __init__(self, kernel):
        super(CNN, self).__init__()
        self.process_cnn = nn.Sequential(
            # transforms to 3x3 (formula: out = (in-k+2*p)/s + 1)
            nn.Conv2d(1, kernel, 3, stride=1, padding=1),
            nn.ReLU(True),
            # transforms to 3x3
            nn.Conv2d(kernel, kernel, 3, stride=1, padding=1),
            nn.ReLU(True)
        )

        self.process_lin = nn.Sequential(
            nn.Linear(3 * 3 * kernel, 9)
        )

    def process(self, x):
        x = x.view(-1, 1, 3, 3)
        # Apply convolutions
        x = self.process_cnn(x)
        # Flatten
        x = x.view([x.size(0), -1])
        # Apply linear layers
        x = self.process_lin(x)
        return x

    def forward(self, x):
        x = self.process(x)
        return x


class FF(nn.Module):
    def __init__(self, Nh1, Nh2, Nh3):
        super(FF, self).__init__()
        self.fc = nn.Sequential(
            nn.Linear(9, Nh1),
            nn.ReLU(True),
            nn.Linear(Nh1 ,Nh2),
            nn.ReLU(True),
            nn.Linear(Nh2, Nh3),
            nn.ReLU(True),
            nn.Linear(Nh3, 9)
        )

    def forward(self, x):
        x = x.view(-1, 9)
        x = self.fc(x)
        return x


# Initialize network
Nh1 = 16
Nh2 = 32
Nh3 = 16
# net = FF(Nh1, Nh2, Nh3)
# target_net = FF(Nh1, Nh2, Nh3)
kernel = 4
net = CNN(kernel)
target_net = pickle.loads(pickle.dumps(net))

# Define Loss Function
loss_fn = nn.MSELoss()


def select_action(st, eps):
    allowed_actions = []
    for i, cell in enumerate(st):
        if cell == 0:
            allowed_actions.append(i)
    # Pass state through NN
    input = torch.tensor(st).float()
    output = net(input).float().squeeze().detach().numpy()
    # Get Q values of legal moves
    qvalues = []
    for action in allowed_actions:
        qvalues.append(output[action])
    # Implement behavior policy
    if len(allowed_actions) > 1:
        # assign equal value to all other allowed moves
        prob = np.ones(len(allowed_actions)) * eps / (len(allowed_actions) - 1)
        prob[np.argmax(qvalues)] = 1 - eps
    else:
        prob = [1]
    chosen_action = allowed_actions[
        np.random.choice(range(0, len(allowed_actions)), p=prob)]  # between all action(range(0,9) choose one)
    return chosen_action


def get_pred_and_target(st, next_state, act, player, discount):

    pred = torch.tensor([net(torch.tensor(st).float()).squeeze().detach().numpy()[act]])
    # Define reward
    reward = 0.
    winner, game_status = check_result(next_state)
    if game_status == 'Done' and winner == player:
        reward = 1.
    if game_status == 'Done' and winner != player:
        reward = -1.
    if game_status == 'Draw':
        reward = 0.
    # Define target
    if next_state.count(0) == 0:
        target = torch.tensor([reward], requires_grad=True).float()
    else:
        target = torch.tensor([reward]).float() + discount * torch.max(
            target_net(torch.tensor(st).float()))
    return pred, target


def select_random_action(state):
    # Create array with allowed moves
    allowed_actions = []
    for i, cell in enumerate(state):
        if cell == 0:
            allowed_actions.append(i)

    chosen_action = allowed_actions[np.random.choice(range(0, len(allowed_actions)))]
    return chosen_action


# Training against random player
num_epochs = 10000
epsilon_array = np.linspace(0.3, 0.01, num_epochs)  # epsilon decays with every epoch
lr_array = np.linspace(0.000001, .0000001, num_epochs)
results = []
percentages = []
preds = torch.tensor([0]).float()
targets = torch.tensor([0]).float()
training = True
playing = False
batch_size = 10
update_target = 100

if training:
    for epoch in range(num_epochs):
        lr = lr_array[epoch]
        # Define Optimizer
        optimizer = torch.optim.Adam(net.parameters(), lr=lr_array[epoch], weight_decay=1e-5)

        # Produce batch
        for i in range(batch_size):
            # Clear Board
            state = [0, 0, 0, 0, 0, 0, 0, 0, 0]

            epsilon = epsilon_array[epoch]
            game_status = 'Not Done'
            winner = None
            players_turn = random.choice([0, 1])

            while game_status == 'Not Done':
                if players_turn == 0:  # X's move
                    # print("\nAI X's turn!")
                    action = select_action(state, epsilon)
                    new_state = play_move(state, 1, action)
                else:  # O's move
                    # print("\nAI O's turn!")
                    action = select_random_action(state)
                    new_state = play_move(state, -1, action)

                # get pred and target for Q(s,a)
                pred, target = get_pred_and_target(state, new_state, action, 1, discount=0.99)
                # update batch
                preds = torch.cat([preds, pred])
                targets = torch.cat([targets, target])
                # update state
                state = new_state.copy()
                # print_board(new_state)
                winner, game_status = check_result(state)
                if winner is not None:
                    # print(str(winner) + ' won!')
                    if winner == 1:
                        results.append('X')
                    else:
                        results.append('O')
                else:
                    players_turn = (players_turn + 1) % 2
                if game_status == 'Draw':
                    # print('Draw!')
                    results.append('Draw')

        loss = loss_fn(preds, targets)
        optimizer.zero_grad()
        # Backward pass
        loss.backward()
        # Update
        optimizer.step()
        # Clear batch
        preds = torch.tensor([0]).float()
        targets = torch.tensor([0]).float()

        # update target net
        if epoch % update_target == 0:
            print('Epoch: ' + str(epoch))
            print(torch.mean(loss))
            print(pred)
            target_net = pickle.loads(pickle.dumps(net))
            percentage = results[-700:].count('O')/7
            percentages.append(percentage)
            print(f'Random player win percentage in the last 700 games: {percentage} %')
    print('Training Complete')

    # Plot draw percentage curve
    x = np.linspace(1, len(percentages), len(percentages))
    plt.plot(x, percentages)
    plt.show()