Answers.Body: <p>Some suggestions:</p>
  <ol>
  <li><p>You have a loop in which <em>illegal moves</em> 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.</p>
  </li>
  <li><p>Try to play a few &quot;pre-moves&quot; to make the game easier.  For example I start with this (now is for Player 'X' to move):</p>
  <p><a href="https://i.sstatic.net/QveI0.png" rel="nofollow noreferrer"><img src="https://i.sstatic.net/QveI0.png" alt="enter image description here" /></a></p>
  <p>Then you may see convergence sooner.  Always a good idea to start from a dead-easy case.</p>
  </li>
  <li><p>Notice that the optimal value is not the &quot;perfect score&quot;.  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).</p>
  <p>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 <a href="https://ai.stackexchange.com/questions/31536/what-is-the-optimal-score-for-tic-tac-toe-for-a-reinforcement-learning-agent-aga/31537#31537">this answer</a>.</p>
  </li>
  <li><p>For me it took much more than 50K games to see convergence.  It's more like 1-2M games.  (<strong>Correction</strong>:  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.)</p>
  </li>
  <li><p>Your neural network may be a bit too small.</p>
  </li>
  </ol>
  <p><strong>Remark:</strong> 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 &quot;logical&quot; domains.  My own research is focused on combining logic structure with deep learning.</p>
  <p>My code is here：
  <a href="https://github.com/Cybernetic1/policy-gradient" rel="nofollow noreferrer">https://github.com/Cybernetic1/policy-gradient</a></p>
  
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2021-09-01T13:12:05.047Z
Answers.Text: Really great response!
Answers.UserDisplayName: Andre Goulart
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2021-09-01T06:17:23.390Z
Answers.LastActivityDate: 2021-09-11T04:12:43.427Z
Answers.LastEditDate: 2021-09-11T04:12:43.427Z
Answers.UserDisplayName: Yan King Yin
Body: <p>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.</p>
  
  <p>RandomPlayer ("Player X") vs PolicyAgent ("Player O")</p>
  
  <p><a href="https://i.sstatic.net/ctsIa.png" rel="nofollow noreferrer"><img src="https://i.sstatic.net/ctsIa.png" alt="enter image description here"></a></p>
  
  <p>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. </p>
  
  <p>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. </p>
  
  <p>Here is also a project which did the same, which I want to do, but with success. 
  <a href="https://github.com/fcarsten/tic-tac-toe/blob/master/tic_tac_toe/DirectPolicyAgent.py" rel="nofollow noreferrer">https://github.com/fcarsten/tic-tac-toe/blob/master/tic_tac_toe/DirectPolicyAgent.py</a>
  I did not get what I am making different.</p>
  
  <p><strong>Code:</strong></p>
  
  <p>Packages:</p>
  
  <pre><code>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
  </code></pre>
  
  <p>Neural Net:</p>
  
  <pre><code>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
  </code></pre>
  
  <p>Policy Agent:</p>
  
  <pre><code>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) &gt; 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 = []
  </code></pre>
  
Comments.ContentLicense: CC BY-SA 4.0
Comments.CreationDate: 2021-09-11T04:15:17.843Z
Comments.Text: I am of the conviction that policy gradient (in its naive form at least) does not converge for Tic Tac Toe.  Looking for confirmation from others....
Comments.UserDisplayName: Yan King Yin
Tags: <neural-networks><reinforcement-learning><policy-gradients><pytorch>
Title: Policy Gradient on Tic-Tac-Toe not working
UserDisplayName: DanischKhurshid
ThreadText: # Policy Gradient on Tic-Tac-Toe not working
  
  (Asked by: username_0 on 2020-05-22)
  
  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 = []
  
  **Tags:** neural-networks, reinforcement-learning, policy-gradients, pytorch
  > **Comments:**
  > **username_1**: I am of the conviction that policy gradient (in its naive form at least) does not converge for Tic Tac Toe.  Looking for confirmation from others....  
  
  ---
  
  ## 1 answers
  
  ### Answer by username_1 on 2021-09-01. Score: 2
  
  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):
  
     [![enter image description here](https://i.sstatic.net/QveI0.png)](https://i.sstatic.net/QveI0.png)
  
     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](https://ai.stackexchange.com/questions/31536/what-is-the-optimal-score-for-tic-tac-toe-for-a-reinforcement-learning-agent-aga/31537#31537).
  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>
  
  > **Comments:**
  > **username_2**: Really great response!  
  
  ---
  
  