Q-Learning tic tac toe - bad player

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()


1 Answer

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?

• 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 – Robin_at_Cantelli Jan 16 '19 at 19:45
• @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 – Dennis Soemers Jan 16 '19 at 19:58
• 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) – Dennis Soemers Jan 16 '19 at 20:00
• 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! – Robin_at_Cantelli Jan 16 '19 at 20:21
• @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. – Dennis Soemers Jan 16 '19 at 20:37