I was reading another blog post about reinforcement learning using Monte Carlo and tabulation methods that provided an example of the technique using Blackjack. I decided to implement my own method using Tic-Tac-Toe as an example. The basic idea is that you generate a random state of a game, and you generate a random action based on that state. Then you play the rest of the game through until the end and record the outcome. Then you should be able to store the state, action, and outcome as a key in a dictionary that refers to a count. Each time that state-action-outcome occurs again, you update the count by one. Over time, your dictionary will encode information about the relative strengths of different actions for a given state.

In my implementation, I was thinking about Swift and how I would define a standard protocol for an object that could be used to produce a dictionary of state-action-outcome counts. So far, I think that you’d want methods to return the current state, the legal actions, the outcome (win, lose, draw, incomplete), and methods to make a move and reset the game.

Here’s my Python code so far:

import random

class TicTacToe:
    def __init__( self, boxes=None ):
        self.boxes = [ [ None, None, None ]
                     , [ None, None, None ]
                     , [ None, None, None ] ]
    def __repr__( self ):
        """
        Produce a pretty-printed version of the board
        """
        s = ""
        for i in range(3):
            for j in range(3):
                if self.boxes[i][j] is None:
                    s += ". "
                else:
                    s += str(self.boxes[i][j])+" "
            s += "\n"
        return s
    def reset( self ):
        self.boxes = [ [ None, None, None ]
                     , [ None, None, None ]
                     , [ None, None, None ] ]
    def getRow( self, i ):
        """
        Return on of the rows
        """
        return [ self.boxes[i][j] for j in range(3) ]
    def getColumn( self, i ):
        """
        Return one of the columns
        """
        return [ self.boxes[j][i] for j in range(3) ]
    def getDiagonal( self, direction ):
        """
        Return one of the diagonals, `direction` is 1 or -1
        """
        if direction == 1:
            return [ self.boxes[i][2-i] for i in range(3) ]
        elif direction == -1:
            return [ self.boxes[i][i] for i in range(3) ]
    def _win( self, itr ):
        """
        Helper function for the winner function
        """
        reduced = list( set( itr ) )
        if len( reduced ) == 1:
            return reduced[0]
        else:
            return None
    def winner( self ):
        """
        Return an integer code for the following cases
          0: 0 wins
          1: 1 wins
          2: draw
          3: in progress
        """
        rows = [ self.getRow(i) for i in range(3) ]
        cols = [ self.getColumn(i) for i in range(3) ]
        diags = [ self.getDiagonal(1), self.getDiagonal(-1) ]
        options = rows + cols + diags
        for option in options:
            result = self._win( option )
            if result is not None:
                return result
        if None in self.state():
            return 3
        return 2
    def action( self ):
        """
        Return a random legal move, or None
        """
        play = []
        if None not in self.state():
            return None
        for i in range(3):
            for j in range(3):
                if self.boxes[i][j] == None:
                    play.append( [i,j] )
        random.shuffle( play )
        return play.pop()
    def state( self ):
        """
        Return a flattened array of the board
        """
        return [ item for sublist in self.boxes for item in sublist ]
    def play( self, token, location ):
        """
        Place a token at location if location is not None
        """
        if location is None:
            return
        i, j = location
        self.boxes[i][j] = token
    def generateRandomState( self, depth ):
        for i in range(depth):
            self.play(i%2,self.action())
            if None not in self.state():
                break
        #print self
        return self.state()
    def playRandomGame( self, player ):
        while True:
            self.play(player%2,self.action())
            #print self
            # check win
            if self.winner() != 3:
                break
            player += 1

def train(game,depth=0,n=1000):
    q = dict()
    for d in range(depth):
        for i in range(n):
            state = game.generateRandomState(d)
            if game.winner() < 3:
                continue
            if state is None:
                continue
            action = game.action()
            game.play(d%2,action)
            game.playRandomGame((d+1)%2)
            winner = game.winner()
            key = ( tuple(state), tuple(action), winner )
            if key in q.keys():
                q[key] += 1
            else:
                q[key] = 1
            game.reset()
    return q

def qactions( q, state, winner ):
    qs = dict()
    for k,v in q.iteritems():
        _state, _action, _winner = k
        if _state == tuple(state) and _winner == winner:
            qs[_action] = v
    return qs

def qaction( q, state, winner ):
    actions = qactions( q, state, winner )
    maximum = 0
    action = None
    for k,v in actions.iteritems():
        if v > maximum:
            maximum = v
            action = k
    return list(action)

# create a dictionary, q

tictactoe = TicTacToe()
q = train(tictactoe,depth=10,n=50000)

# then, interactively, I take a turn

t = TicTacToe()
t.play(0,[1,1])
print t

# and then ask the computer to make a turn

t.play(1,qaction( q, t.state(), 1 ))
print t

# et cetra