<jupyter_start><jupyter_text>TicTacToe using Reinforcement Learning Introduction* This notebook aims to explain the most basic ideas of RL by building an AI that "learns" to play TicTacToe (hereby abbreviated as TTT).* iPython notebooks are a beatiful method to explain programming techniques. * No prior knowledge is assumed, except the rules of the game: 3 of any symbol in a row/column/diagonal results in a win for the player with whom that symbol ('X' or 'O') is associated.<jupyter_code>%matplotlib inline

# some basic imports.

import numpy as np
import matplotlib.pyplot as plt
from collections import Counter<jupyter_output><empty_output><jupyter_text>Step 1: Build a basic representation of TTT that is playable by an AI or Human player.<jupyter_code>class TTT:
    def __init__(self, grid = None):
        if grid == None:
            self.grid = [0] * 9
        else:
            self.grid = grid
    
    def get_state(self):
        return self.grid
    
    # report 1 or 2 if either of those players won.
    # report 0 if drawn.
    # report -1 if no winner yet.
    def result(self):
        cnt = Counter()
        
        # check the columns
        for j in range(3):
            cnt.clear()
            for i in range(j, 9, 3):
                cnt[self.grid[i]] += 1
            if cnt[1] == 3: return 1
            elif cnt[2] == 3: return 2
        
        # check the rows
        for i in range(0, 9, 3):
            cnt.clear()
            for j in range(3):
                k = i+j
                cnt[self.grid[k]] += 1
            if cnt[1] == 3: return 1
            elif cnt[2] == 3: return 2
        
        # check the diagonals
        cnt.clear()
        for i in [0,4,8]:
            cnt[self.grid[i]] += 1
        if cnt[1] == 3: return 1
        elif cnt[2] == 3: return 2
                
        cnt.clear()
        for i in [2,4,6]:
            cnt[self.grid[i]] += 1
        if cnt[1] == 3: return 1
        elif cnt[2] == 3: return 2
                   
        
        # check for draw (no more moves left to be played)
        cnt.clear()
        for i in self.grid:
            cnt[i] += 1
        if cnt[0] == 0:
            return 0
        
        # no result
        return -1
        
    # the board is indexed by numerals 0 through 8 by rows.
    # no checking is performed to ensure the correct player is playing.
    # player is either 1 or 2.
    def make_move(self, pos, player):
        if self.grid[pos] != 0:
            raise Exception("Cannot change already played position")
            return
        self.grid[pos] = player<jupyter_output><empty_output><jupyter_text>Step 2: Test the grid we built<jupyter_code># initial state, no one wins
t = TTT([0,0,0,
         0,0,0,
         0,0,0])
assert t.result() == -1


# player 1 wins along diagonal
t = TTT([0,0,1,
         0,1,0,
         1,0,1])
assert t.result() == 1


# player 2 wins along second column
t = TTT([1,2,0,
         0,2,0,
         0,2,1])
assert t.result() == 2

# drawn position
t = TTT([1,1,2,
         2,2,1,
         1,2,1])
assert t.result() == 0<jupyter_output><empty_output><jupyter_text>Step 3: Now, we build something that can play the game.* The symbolism is simple, the AI player takes in the state and "homogenizes" it. The player always thinks it is player 1 (this helps later).* It keeps track of each state, and marks with it, the probability that such a state transition leads to a victory.* Initially, all state transitions have the same probability, except those leading to a victory or loss.* There is a learning rate $\alpha$ which decides how quickly we change the probabilities.* Another parameter which I call $\theta$ decides how often we make the best possible move (exploitation) v/s a random move to explore a new possibility (exploration).<jupyter_code>import random
from pprint import pprint

class AI:
    # constructor argument: player #1 or #2
    def __init__(self, player):
        self.player = player 
        self.states = dict() # maps states with each move to each probability
        self.alpha = 0.95
        self.theta = 0.95
        self.history = []
        self.move_history = []
        
    # AI may be player #1, or #2, but with respect to states, 
    # we always want it to be player #1 
    def homogenize(self, ttt):
        if self.player == 1:
            return tuple(ttt)
        else:
            ttt = ['#' if x == 1 else x for x in ttt]
            ttt = [1 if x == 2 else x for x in ttt]
            ttt = [2 if x == '#' else x for x in ttt]
        return tuple(ttt)
    
    def new_game(self):
        self.history = []
        self.move_history = []
    
    # use the reward to impact all the states stored in history
    def notify_reward(self, reward):
        # V(s) <- V(s) + alpha*(V(s') - V(s))
        
        # set final state
        st = self.history[-1]
        self.states[st] = reward
        
        for i in range(len(self.history) - 2, -1, -1):
            cst = self.history[i]
            self.states[cst] = self.states[cst] + self.alpha * (self.states[st] - self.states[cst])
            st = cst
            
    def value(self, state):
        if state not in self.states:
            self.states[state] = 0.5
        return self.states[state]
    
    def play(self, ttt):
        state = self.homogenize(ttt.get_state())
        self.value(state) # in case we didn't compute this value :()
        self.history.append(state)
        
        # get state for every one of them moving forward.
        mutable_state = list(state)
        moves = []
        
        # compute the possible moves and the scores of the resulting states!
        for i in range(len(state)):
            if state[i] == 0:
                mutable_state[i] = 1
                moves.append((self.value(tuple(mutable_state)), i))
        
        # greedy if theta > threshold
        move = -1
        if random.random() <= self.theta:
            # exploitation
            m = max(moves, key = lambda x:int(x[0]))
            mxs = [x[1] for x in moves if x[0] == m[0]]
            random.shuffle(mxs)
            move = mxs[0]
        else:
            # exploration
            mxs = [x[1] for x in moves if x[0] > 0]
            random.shuffle(mxs)
            move = mxs[0]
            
        self.move_history.append(move)
        return move
ai1 = AI(1)
ai2 = AI(2)
for i in range(10000):
    t = TTT([0,0,0,
             0,0,0,
             0,0,0])
    ai1.new_game()
    ai2.new_game()
    while True:
        t.make_move(ai1.play(t), 1)
        if t.result() == 1:
            ai1.notify_reward(+1)
            ai2.notify_reward(0)
            break
        elif t.result() == 0:
            break

        t.make_move(ai2.play(t), 2)
        if t.result() == 2: 
            ai1.notify_reward(0)
            ai2.notify_reward(+1)
            break
        elif t.result() == 0:
            break
for i in range(10):
    t = TTT([0,0,0,
             0,0,0,
             0,0,0])
    ai1.new_game()
    ai2.new_game()
    while True:
        t.make_move(ai1.play(t), 1)
        if t.result() == 1:
            print("P1 wins")
            ai1.notify_reward(+1)
            ai2.notify_reward(0)
            break
        elif t.result() == 0:
            print("draw")
            break

        t.make_move(ai2.play(t), 2)
        if t.result() == 2: 
            print("P2 wins")
            ai1.notify_reward(0)
            ai2.notify_reward(+1)
            break
        elif t.result() == 0:
            print("draw")
            break<jupyter_output>draw
P2 wins
P1 wins
P1 wins
P1 wins
P1 wins
P1 wins
P1 wins
draw
P2 wins
StarcoderdataJupyterStructuredCleanDedup