2
$\begingroup$

my Q-learning alghoritm currently choices the "sub optimal" option and not the best one.

from pprint import pprint
from random import shuffle, choice, random
from operator import itemgetter


epsilon = .03  # Exploration
gamma = .9  # Learning rate
epochs = 100000  # Number of matches vs itself
states = {}

WON = 1
LOSE = 0
TIE = 0.5

COLS = 3
ROWS = 3
SIZE = COLS * ROWS

def buildBoard():
    return [''] * SIZE


def prettyPrint(board):
    if type(board) != list:
        board = eval(board)

    print('+-----+')
    for i in range(SIZE):
        print('|{}'.format(board[i] if board[i] != '' else ' '), end='')
        if i in (2, 5, 8):
            print('|')
    print('+-----+')


def isFinished(board):
    # +-----+
    # |0|1|2|
    # |3|4|5|
    # |6|7|8|
    # +-----+
    for player in ('X', 'O'):
        # Check rows
        for i in range(0, SIZE, 3):
            if board[i] == board[i + 1] == board[i + 2] == player:
                return {'winner': player, 'finished': True}

        # Check cols
        for i in range(ROWS):
            if board[i] == board[i + 3] == board[i + 6] == player:
                return {'winner': player, 'finished': True}

    # Check diagonals
    if (board[0] == board[4] == board[8] or 
        board[2] == board[4] == board[6]) and board[4] != '':
        return {'winner': board[4], 'finished': True}

    # Is it a draw?
    for i in range(SIZE):
        if board[i] == '':
            return {'winner': None, 'finished': False}

    # Still running
    return {'winner': None, 'finished': True}


def genStates(state, player='X'):
    for i in range(SIZE):
        tmp = state[:]
        if tmp[i] == '':
            tmp[i] = player
            info = isFinished(tmp)

            if not info['finished']:
                reward = 0.5
                genStates(tmp, 'O' if player == 'X' else 'X')
            elif info["winner"] == 'X':
                reward = WON
            elif info["winner"] == 'O':
                reward = LOSE
            else:
                reward = TIE

            states[str(tmp)] = reward



def getAvalaibleStates(state, player):
    availables = []
    for i in range(SIZE):
        tmp = state[:]
        if tmp[i] == '':
            tmp[i] = player
            availables.append((tmp, states[str(tmp)]))

    shuffle(availables)
    return availables


def nextState(state, player, eps=epsilon):
    availables = getAvalaibleStates(state, player)

    if eps > random():
        return availables[0][0]

    # X player choices the max value, O the min value
    if player == 'X':
        availables.sort(key=itemgetter(1), reverse=True)
    else:
        availables.sort(key=itemgetter(1))

    return availables[0][0]


def updateState(state, nextState):
    states[str(state)] = states[str(state)] + gamma * states[str(nextState)]


def play():
    while True:
        state = buildBoard()
        who = input("X/O: ")
        player = 'X'
        prettyPrint(state)
        while not isFinished(state)['finished']:  # Until finish
            if player == who:
                state[int(input("[0-8]: "))] = who
            else:
                next = nextState(state, player)
                state = next

            player = 'O' if player == 'X' else 'X'

            prettyPrint(state)
        print(isFinished(state))

def train(epochs=epochs):
    wins, loses, draw = 0, 0, 0
    for _ in range(epochs):
        state = buildBoard()
        player = 'X'
        while not isFinished(state)['finished']:  # Until finish
            next = nextState(state, player)
            updateState(state, next)
            state = next
            if player == 'X':
                player = 'O'
            else:
                player = 'X'

        if isFinished(state)['winner'] == 'X':
            wins += 1
        elif isFinished(state)['winner'] == 'O':
            loses += 1
        else:
            draw += 1

        if _ % 10000 == 0:
            print("Epoch n°", _)
            print("wins: {} - loses: {} - draw: {}\n".format(wins, loses, draw))
            if wins == 0 and _ > 0:
                break
            wins, loses, draw = 0, 0, 0


state = buildBoard()
states[str(state)] = TIE
genStates(state)
train()
play()

Is it possibile that I have too big value for epsilon or for learning rate? Or do I need a different formula for update the Q state? Or do I share the state in the bad way?

Thank you

$\endgroup$

1 Answer 1

3
$\begingroup$

You have a couple of mistakes around assigning reward, and the update mechanism.

You intend to grant 0 reward for a loss, 0.5 reward for a tie and 1 reward for a win. And you place those rewards as fixed state values for completed boards, that won't logically get updated. That is OK (provided you do take care to never update those values).

In the genStates function you also assign an interim value of 0.5 to incomplete board states. This is also OK as the initial value (any value would be in principle). However, it points to a problem - you don't seem to differentiate between the state value and the reward.

You also don't have a learning rate, just a discount factor (which for some reason you are calling the learning rate - it is not). As it happens, in such a simple game, both can be 1.

The update function for Q learning using afterstates should be:

$$V(s) \leftarrow V(s) + \alpha(R + \gamma \text{max}_{s'}[ V(s')] - V(s))$$

If you set $\alpha = 1$ (as you effectively have), then this becomes:

$$V(s) \leftarrow R + \gamma \text{max}_{s'}[ V(s')]$$

Your code is implementing:

$$V(s) \leftarrow V(s) + \gamma V(s')$$

You need to separate out the value function and reward calculation, so that you use $R$ and not $V(s)$ in the update. Not only should this fix the problem, but it will make how the algorithm works clearer. The simplest reward for incomplete game should be $0$ - other fixed values may work, but if they are high enough to interfere with the win/loss/tie rewards, then one of the players may prefer to lose early as opposed to win or draw in a longer game. So stick with $0$.

In addition, you are not updating using the max action, when taking exploratory moves. That makes your algorithm SARSA, not Q learning. At a low exploration rate, this probably won't make a big difference to the eventual state values. However, they won't actually, represent optimal play, but something close to it. If you really want to implement Q learning, you need to call updateState based on the maximising (or minimising) action, regardless of whether the player took it in the actual game.

Note that typically in zero-sum games, the rewards are -1 for loss, 0 for tie and +1 for a win. However, I don't think that makes any difference to you here, the important trick in a two-player game is to switch between actions that minimise and maximise the value function depending on whose turn it is, and it looks to me that you do that correctly.

Expect to play a few times 10,000 games in order to learn a perfect value function.

$\endgroup$
6
  • $\begingroup$ PT1. I really appreciate your extensive answer, tank you. But I don't understant some parts. In addition, you are not updating using the max action, when taking exploratory moves I have debugged the nextState function and I have these results: Availables: [(['O', 'X', '', '', 'O', 'X', 'X', '', 'O'], -1), (['', 'X', '', '', 'O', 'X', 'X', 'O', 'O'], 0), # ... O choose: ['O', 'X', '', '', 'O', 'X', 'X', '', 'O'] $\endgroup$ Oct 13, 2018 at 15:09
  • $\begingroup$ PT2. and Availables: [(['O', '', 'X', 'X', 'X', 'O', 'X', 'O', ''], 1), (['O', '', 'X', 'X', '', 'O', 'X', 'O', 'X'], 0), (['O', 'X', 'X', 'X', '', 'O', 'X', 'O', ''], 0)] X choose: ['O', '', 'X', 'X', 'X', 'O', 'X', 'O', ''] I have update the code with your suggestions, can you see it now? p.s. I have tried some games and I believe it works pretty well. The X player plays perfectly, the O no, I'm confusing... $\endgroup$ Oct 13, 2018 at 15:10
  • $\begingroup$ @CuriousPanda: Please revert your edits to the question that include fixes based on the answer. This Q&A site does not work if you fix all the issues in the question that I addressed in the answer. It looks like I am answering something different. It is also not possible to have a conversation where I answer the question and you add another question. If you want to ask another question, then start a brand new question (maybe link this one) $\endgroup$ Oct 13, 2018 at 17:59
  • $\begingroup$ @CuriousPanda: To answer your first comment, I mean when you don't use the sorted array, but choose a random value for the action to take. In that case, you should not call updateState(state, next) with next being the action that the player took in the game. Instead you should update with the maximising (or minimising) state always, even if it is different than the one that the player took. That is the difference between SARSA and Q Learning. $\endgroup$ Oct 13, 2018 at 18:19
  • $\begingroup$ Ok, I have removed all wrong updates. Your last answer solved all my questions and now the algorithm works for both of players. Thank you, your help has been important. $\endgroup$ Oct 13, 2018 at 19:27

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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