1
$\begingroup$

I tried to build an 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.

Best Rewgards

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()
$\endgroup$
2
$\begingroup$

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?

$\endgroup$
  • 1
    $\begingroup$ Wow! That was an incredibly sophisticated answer! I guess that your idea is the best solution to my problem. I'd have to give it some more thought to figure out how to do that properly but thank you very much:). So would you say that Q-learning isn't that good for multi agent tasks in general and if so what would you prefer (A2C, Policy Gradient....)? Best Regards $\endgroup$ – Robin_at_Cantelli Jan 16 at 19:45
  • 1
    $\begingroup$ @Robin_at_Cantelli Those are all standard RL agents originally formulated for the standard single-agent MDP setting, they'd all have similar problems. All of these things (including $Q$-learning) may work if you treat the opponent as part of "the environment" (which is essentially also what I suggested in my answer, skipping some states means you treat those parts of the trajectory as being part of the environment's inherent dynamics), but you often need extra tricks to avoid "overfitting" to an imperfect player. See also: ai.stackexchange.com/q/7963/1641 $\endgroup$ – Dennis Soemers Jan 16 at 19:58
  • 1
    $\begingroup$ In addition to that, there's also a whole field of Multi-Agent Reinforcement Learning research with lots of different algorithms dedicated to multi-agent settings (also often variants of traditional RL algorithms, with some extra tricks) $\endgroup$ – Dennis Soemers Jan 16 at 20:00
  • 1
    $\begingroup$ Ok I see. So it seems to be the best approach to use the kind of algorithm (DQN,QL,A2C and so on) which seems to be the best fit for your current problem an if you have the multi agent task on top you try to modify the the state similar to what you suggested. Good that I thought about trying to build an agent for the German game of scat in the future. There you have 3 agents...oh dear;) Thanks for the outstanding educational experience you provided! $\endgroup$ – Robin_at_Cantelli Jan 16 at 20:21
  • 1
    $\begingroup$ @Robin_at_Cantelli That's right! If the answer helped, you can mark it as accepted such that it no longer shows up in the list of unanswered questions. Of course you can also wait until you got a chance to implement my suggestions and verify whether that really completely solves it, or if there is something else that I may have missed. $\endgroup$ – Dennis Soemers Jan 16 at 20:37

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.