Why isn't my Q-Learning agent able to play tic-tac-toe?

Question

I tried to build a Q-learning agent which you can play tic tac toe against after training.

Unfortunately, the agent performs pretty poorly. He tries to win but does not try to make me 'not winning' which ends up in me beating up the agent no matter how many loops I gave him for training. I added a reward of 1 for winning the episode and it gets a reward of -0.1 when he tries to put his label on an non-empty square (after the attempt we have s = s'). I also start with an epsilon=1 which decreases in every loop to add some more randomness at the beginning because I witnessed that some (important in my opinion) states did not get updated. Since I spend some hours of debugging without noticeable progress I'd like to know what you think.

PS: Don't care about some print statements and count variables. Those where for debugging.

Code here or on Github

import numpy as np
import collections
import time

Gamma = 0.9
Alpha = 0.2


class Environment:
    def __init__(self):
        self.board = np.zeros((3, 3))
        self.x = -1  # player with an x
        self.o = 1  # player with an o
        self.winner = None
        self.ended = False
        self.actions = {0: (0, 0), 1: (0, 1), 2: (0, 2), 3: (1, 0), 4: (1, 1),
                        5: (1, 2), 6: (2, 0), 7: (2, 1), 8: (2, 2)}

    def reset_env(self):
        self.board = np.zeros((3, 3))
        self.winner = None
        self.ended = False

    def reward(self, sym):
        if not self.game_over():
            return 0
        if self.winner == sym:
            return 10
        else:
            return 0

    def get_state(self,):
        k = 0
        h = 0
        for i in range(3):
            for j in range(3):
                if self.board[i, j] == 0:
                    v = 0
                elif self.board[i, j] == self.x:
                    v = 1
                elif self.board[i, j] == self.o:
                    v = 2
                h += (3**k) * v
                k += 1
        return h

        def random_action(self):
            return np.random.choice(self.actions.keys())

    def make_move(self, player, action):
        i, j = self.actions[action]
        if self.board[i, j] == 0:
            self.board[i, j] = player

    def game_over(self, force_recalculate=False):
        # returns true if game over (a player has won or it's a draw)
        # otherwise returns false
        # also sets 'winner' instance variable and 'ended' instance variable
        if not force_recalculate and self.ended:
            return self.ended

        # check rows
        for i in range(3):
            for player in (self.x, self.o):
                if self.board[i].sum() == player*3:
                    self.winner = player
                    self.ended = True
                    return True

        # check columns
        for j in range(3):
            for player in (self.x, self.o):
                if self.board[:, j].sum() == player*3:
                    self.winner = player
                    self.ended = True
                    return True

        # check diagonals
        for player in (self.x, self.o):
            # top-left -> bottom-right diagonal
            if self.board.trace() == player*3:
                self.winner = player
                self.ended = True
                return True
            # top-right -> bottom-left diagonal
            if np.fliplr(self.board).trace() == player*3:
                self.winner = player
                self.ended = True
                return True

        # check if draw
        if np.all((self.board == 0) == False):
            # winner stays None
            self.winner = None
            self.ended = True
            return True

        # game is not over
        self.winner = None
        return False

    def draw_board(self):
        for i in range(3):
            print("-------------")
            for j in range(3):
                print("  ", end="")
                if self.board[i, j] == self.x:
                    print("x ", end="")
                elif self.board[i, j] == self.o:
                    print("o ", end="")
                else:
                    print("  ", end="")
            print("")
        print("-------------")




class Agent:
    def __init__(self, Environment, sym):
        self.q_table = collections.defaultdict(float)
        self.env = Environment
        self.epsylon = 1.0
        self.sym = sym
        self.ai = True

    def best_value_and_action(self, state):
        best_val, best_act = None, None
        for action in self.env.actions.keys():
            action_value = self.q_table[(state, action)]
            if best_val is None or best_val < action_value:
                best_val = action_value
                best_act = action
        return best_val, best_act

    def value_update(self, s, a, r, next_s):
        best_v, _ = self.best_value_and_action(next_s)
        new_val = r + Gamma * best_v
        old_val = self.q_table[(s, a)]
        self.q_table[(s, a)] = old_val * (1-Alpha) + new_val * Alpha

    def play_step(self, state, random=True):
        if random == False:
            epsylon = 0
        cap = np.random.rand()
        if cap > self.epsylon:
            _, action = self.best_value_and_action(state)
        else:
            action = np.random.choice(list(self.env.actions.keys()))
            self.epsylon *= 0.99998
        self.env.make_move(self.sym, action)
        new_state = self.env.get_state()
        if new_state == state and not self.env.ended:
            reward = -5
        else:
            reward = self.env.reward(self.sym)
        self.value_update(state, action, reward, new_state)


class Human:
    def __init__(self, env, sym):
        self.sym = sym
        self.env = env
        self.ai = False

    def play_step(self):
        while True:
            move = int(input('enter position like: \n0|1|2\n------\n3|4|5\n------\n6|7|8'))
            if move in list(self.env.actions.keys()):
                break
        self.env.make_move(self.sym, move)



def main():
    env = Environment()
    p1 = Agent(env, env.x)
    p2 = Agent(env, env.o)
    draw = 1
    for t in range(1000005):

        current_player = None
        episode_length = 0
        while not env.game_over():
            # alternate between players
            # p1 always starts first
            if current_player == p1:
                current_player = p2
            else:
                current_player = p1

            # current player makes a move
            current_player.play_step(env.get_state())

        env.reset_env()

        if t % 1000 == 0:
            print(t)
            print(p1.q_table[(0, 0)])
            print(p1.q_table[(0, 1)])
            print(p1.q_table[(0, 2)])
            print(p1.q_table[(0, 3)])
            print(p1.q_table[(0, 4)])
            print(p1.q_table[(0, 5)])
            print(p1.q_table[(0, 6)])
            print(p1.q_table[(0, 7)])
            print(p1.q_table[(0, 8)])
            print(p1.epsylon)

    env.reset_env()
    # p1.sym = env.x

    while True:
        while True:
            first_move = input("Do you want to make the first move? y/n :")
            if first_move.lower() == 'y':
                first_player = Human(env, env.x)
                second_player = p2
                break
            else:
                first_player = p1
                second_player = Human(env, env.o)
                break
        current_player = None

        while not env.game_over():
            # alternate between players
            # p1 always starts first
            if current_player == first_player:
                current_player = second_player
            else:
                current_player = first_player
            # draw the board before the user who wants to see it makes a move

            if current_player.ai == True:
                current_player.play_step(env.get_state(), random=False)
            if current_player.ai == False:
                current_player.play_step()
            env.draw_board()
        env.draw_board()
        play_again = input('Play again? y/n: ')
        env.reset_env()
        # if play_again.lower != 'y':
        #     break


if __name__ == "__main__":
    main()

Answer 1

The $Q$-learning rule that you have implemented updates $Q(S_t, A_t)$ estimates as follows, after executing an action $A_t$ in a state $S_t$, observing a reward $R_t$, and reaching a state $S_{t+1}$ as a result:

$$Q(S_t, A_t) \gets (1 - \alpha) Q(S_t, A_t) + \alpha (R_t + \gamma \max_a Q(S_{t+1}, a))$$

The implementation seems to be correct for the traditional setting for which $Q$-learning is normally described; single-agent MDPs. The problem is that you have a multi-agent setting, in which $Q$-learning is not always directly applicable.

Now, as far as I can see from a very quick glance at your code, it seems like you actually already have taken some important steps towards allowing it to work, and I think it should be quite close to almost working (at least for a simple game like Tic-Tac-Toe) already. Important things that you appear to already be doing correctly:

• Self-play training against an opponent who is hopefully gradually improving, as opposed to training against a uniform-at-random agent or a fixed-strategy agent.
• Add randomization during training to ensure sufficient diversity in generated experience.

---

I think the major issue that remains to be solved is in how you define the subsequent state $S_{t+1}$ after making a move in a state $S_t$.

The update target that the $Q$-learning update rule moves its $Q$-value estimates towards consists of two components:

1. The observed immediate reward $R_t$.
2. The discounted predicted future returns $\gamma \max_a Q(S_{t+1}, a)$ for the greedy policy.

The problem is that, in your implementation, $S_{t+1}$ is a state in which the opponent is allowed to make the next move $a$, rather than the RL agent. This means that $\max_a Q(S_{t+1}, a)$ is an incredibly optimistic, naive, unrealistic estimate of future returns. In fact, $\min_a Q(S_{t+1}, a)$ would be a much more realistic estimate (against an optimally-playing opponent), because the opponent gets to pick the next action $a$.

I think switching in $\min_a Q(S_{t+1}, a)$ rather than the $\max$ may have a good chance of working in this scenario, but I'm not 100% sure. It wouldn't be a "pretty" solution though, since you'd no longer be doing $Q$-learning, but something else altogether.

The proper $Q$-learning update may work well if you only present states to agents in which they're actually allowed to make the next move in the update rule. Essentially, you'd be plugging $\max_a Q(S_{t + 2}, a)$ into the update rule, replacing $S_{t+1}$ with $S_{t+2}$. Well... that's what you'd be doing in most cases. The only exception to be aware of would be terminal states. If an agent makes a move that leads to a terminal state, you should make sure to also run an additional update for that agent with the terminal game state $S_{t+1}$ (where $Q(S_{t+1}, a)$ will always be $0$ for any action $a$ if $S_{t+1}$ is terminal).

For a very closely related question, where I essentially provided an answer in the same spirit, see: How to see terminal reward in self-play reinforcement learning?