Policy Gradient on Tic-Tac-Toe not working

Question

I wanted to implement the Policy Gradient on Tic-Tac-Toe. I tried to use the code that worked for any environment like CartPole-v0 to my Tic-Tac-To game. But it is not learning. There are no errors. Just the result is so bad.

RandomPlayer ("Player X") vs PolicyAgent ("Player O")

So one can see that the Policy Agent is not learning after 500 battles. Each battle consists of 100games against the random player. Together 500 * 100 games.

Can someone tell me the problem or the bug in my code. I can not figure it out. Or what I have to improve. It would be so great.

Here is also a project which did the same, which I want to do, but with success. https://github.com/fcarsten/tic-tac-toe/blob/master/tic_tac_toe/DirectPolicyAgent.py I did not get what I am making different.

Code:

Packages:

import torch
import torch as T
import torch.nn as nn
import torch.nn.functional as F
import torch.optim as optim

import numpy as np
import gym
from gym import wrappers

Neural Net:

class PolicyNetwork(nn.Module):
    def __init__(self, lr, input_dims, fc1_dims, fc2_dims, n_actions):
        super(PolicyNetwork, self).__init__()
        self.input_dims = input_dims
        self.lr = lr
        self.fc1_dims = fc1_dims
        self.fc2_dims = fc2_dims
        self.n_actions = n_actions

        self.fc1 = nn.Linear(self.input_dims, self.fc1_dims)
        self.fc2 = nn.Linear(self.fc1_dims, self.fc2_dims)
        self.fc3 = nn.Linear(self.fc2_dims, self.n_actions)

        self.optimizer = optim.Adam(self.parameters(), lr=lr)

    def forward(self, observation):
        state = T.Tensor(observation)
        x = F.relu(self.fc1(state))
        x = F.relu(self.fc2(x))
        x = self.fc3(x)
        return x

Policy Agent:

class PolicyAgent:
    def __init__(self, player_name):
        self.name = player_name
        self.value = PLAYER[self.name]

    def board_to_input(self, board):
        input_ = np.array([0] * 27)
        for i, val in enumerate(board):
            if val == self.value:
                input_[i] = 1  
            if val == self.value * -1:
                input_[i+9] = 1
            if val == 0:
                input_[i+18] = 1
        return np.reshape(input_, (1,-1))


    def start(self, learning_rate=0.001, gamma=0.1):
        self.lr = learning_rate
        self.gamma = gamma
        self.all_moves = list(range(0,9))
        self.policy = PolicyNetwork(self.lr, 27, 243, 91, 9)
        self.reward_memory = []
        self.action_memory = []

    def turn(self, board, availableMoves):
        state = self.board_to_input(board.copy())
        prob = F.softmax(self.policy.forward(state))
        action_probs = torch.distributions.categorical.Categorical(prob)
        action = action_probs.sample()

        while action.item() not in availableMoves:
            state = self.board_to_input(board.copy())
            prob = F.softmax(self.policy.forward(state))
            action_probs = torch.distributions.categorical.Categorical(prob)
            action = action_probs.sample()

        log_probs = action_probs.log_prob(action)
        self.action_memory.append(log_probs)

        self.reward_memory.append(0)
        return action.item()

    def learn(self, result):
        if result == 0:
            reward = 0.5
        elif result == self.value:
            reward = 1.0
        else:
            reward = 0

        self.reward_memory.append(reward)
        #print(self.reward_memory)

        self.policy.optimizer.zero_grad()
        #G = np.zeros_like(self.action_memory, dtype=np.float64)
        G = np.zeros_like(self.reward_memory, dtype=np.float64)


        #running_add = reward
        #for t in reversed(range(0, len(self.action_memory))):
        #    G[t] = running_add
        #    running_add = running_add * self.gamma

        #'''
        running_add = 0
        for t in reversed(range(0, len(self.reward_memory))):
            if self.reward_memory[t] != 0:
                running_add = 0
            running_add = running_add * self.gamma + self.reward_memory[t]
            G[t] = running_add
        for t in range(len(self.reward_memory)):
            G_sum = 0
            discount = 1
            for k in range(t, len(self.reward_memory)):
                G_sum += self.reward_memory[k] * discount
                discount *= self.gamma
            G[t] = G_sum
        mean = np.mean(G)
        std = np.std(G) if np.std(G) > 0 else 1
        G = (G-mean)/std
        #'''

        G = T.tensor(G, dtype=T.float)

        loss = 0
        for g, logprob in zip(G, self.action_memory):
            loss += -g * logprob

        loss.backward()
        self.policy.optimizer.step()

        self.reward_memory = []
        self.action_memory = []

Answer 1

Some suggestions:

1. You have a loop in which illegal moves by the RL agent are ignored. In other words, when the agent makes illegal moves, it is not punished, nor is there any +/- rewards for it whatsoever. In my program I treat illegal moves the same as losing the game.

2. Try to play a few "pre-moves" to make the game easier. For example I start with this (now is for Player 'X' to move):

   

   Then you may see convergence sooner. Always a good idea to start from a dead-easy case.

3. Notice that the optimal value is not the "perfect score". If you take win=2, lose=-2, draw=1, then the optimal score for the above game for Player 'X' is 1.5, not 2.0. (You can check the math).

   I wrote a small Python program to calculate the optimal score for an RL agent playing against a random opponent (both players assumed to never make illegal moves). See this answer.

4. For me it took much more than 50K games to see convergence. It's more like 1-2M games. (Correction: With more trails, I found that policy gradient seems unable to converge to the optimal value, but it did improve over time to reach a sub-optimal score.)

5. Your neural network may be a bit too small.

Remark: This is a good question and also very significant to artificial intelligence, as Tic Tac Toe is a game suitable for logic-based agents, and it is important to see how deep learning performs in such "logical" domains. My own research is focused on combining logic structure with deep learning.

My code is here： https://github.com/Cybernetic1/policy-gradient