\documentclass[11pt]{article}

\usepackage{fullpage}
\usepackage{setspace}
\usepackage{parskip}
\usepackage{titlesec}
\usepackage[section]{placeins}
\usepackage{xcolor}
\usepackage{breakcites}
\usepackage{lineno}
\usepackage{hyphenat}



\usepackage{times}


\PassOptionsToPackage{hyphens}{url}
\usepackage[colorlinks = true,
            linkcolor = blue,
            urlcolor  = blue,
            citecolor = blue,
            anchorcolor = blue]{hyperref}
\usepackage{etoolbox}
\makeatletter
\patchcmd\@combinedblfloats{\box\@outputbox}{\unvbox\@outputbox}{}{%
  \errmessage{\noexpand\@combinedblfloats could not be patched}%
}%
\makeatother






\renewenvironment{abstract}
  {{\bfseries\noindent{\abstractname}\par\nobreak}\footnotesize}
  {\bigskip}

\titlespacing{\section}{0pt}{*3}{*1}
\titlespacing{\subsection}{0pt}{*2}{*0.5}
\titlespacing{\subsubsection}{0pt}{*1.5}{0pt}


\usepackage{authblk}


\usepackage{graphicx}
\usepackage[space]{grffile}
\usepackage{latexsym}
\usepackage{textcomp}
\usepackage{longtable}
\usepackage{tabulary}
\usepackage{booktabs,array,multirow}
\usepackage{amsfonts,amsmath,amssymb}
\providecommand\citet{\cite}
\providecommand\citep{\cite}
\providecommand\citealt{\cite}
% You can conditionalize code for latexml or normal latex using this.
\newif\iflatexml\latexmlfalse
\providecommand{\tightlist}{\setlength{\itemsep}{0pt}\setlength{\parskip}{0pt}}%

\AtBeginDocument{\DeclareGraphicsExtensions{.pdf,.PDF,.eps,.EPS,.png,.PNG,.tif,.TIF,.jpg,.JPG,.jpeg,.JPEG}}

\usepackage[utf8]{inputenc}
\usepackage[english]{babel}








\newcommand{\msun}{\,\mathrm{M}_\odot} 

\begin{document}

\title{Neural Network Directed Game Play~}



\author[1]{Christian Baker}%
\author[1]{Jack Langerman}%
\affil[1]{New York University}%


\vspace{-1em}



  
  \date{May 04, 2024}


\begingroup
\let\center\flushleft
\let\endcenter\endflushleft
\maketitle
\endgroup








\sloppy


\section*{Overview}
\begin{itemize}
\item Abstract 
\item Introduction\begin{itemize}
\item What is Neural Network Game Play 
\item How Neural Network Game Play Works
\item Creating a Game Graph for Tic-Tac-Toe
\item Traditional Tic-Tac-Toe Game Play vs Neural Network Game play
\item 
\end{itemize}
\item Implementation\begin{itemize}
\item Building the Tic-Tac-Toe Game in Python
\item Creating the Neural Network for Tic-Tac-Toe
\end{itemize}
\item Neural Network Development\begin{itemize}
\item Parameteric Player, Game Theory Player, and Keras Player
\item Training Parameteric Player using Algorithm 
\item Efficiency Testing of Parameteric Player
\item Parameteric Player vs Game Theory Player vs Keras player
\end{itemize}
\item Conclusion
\end{itemize}





\section*{Abstract}







\section*{Introduction}



\section {}



\section*{Implementation}

{\label{583331}}

The Implementation for the Tic-Tac-Toe Game is listed below

``` class Board: def \textbf{init}(self, p1, p2, state={[}{[}`-', `-',
`-'{]}, {[}`-', `-', `-'{]}, {[}`-', `-', `-'{]}{]}): self.state = state
self.p1 = p1 self.p2 = p2

\begin{verbatim}
def __str__(self):
    return ("\n".join([" ".join(line) for line in self.state]))
    
def isLegal(self, move):
    return (move[0] >= 0 and move[0] < 3 
            and move[1] >= 0 and move[1] < 3 
            and self.state[move[0]][move[1]] == '-')
        
def apply(self, move, token):
    self.state[move[0]][move[1]] = token
    
def draw(self):
    draw = True
    for r in self.state:
        for t in r:
            draw = draw and t!='-'
    # if draw:
    #     print("ITS A DRAW")
    return draw
    
def winner(self):
    c00 = self.state[0][0] != '-'
    c11 = self.state[1][1] != '-'
    c22 = self.state[2][2] != '-'
    r0dc0 = (  #r0 d c0
            (self.state[0][0]==self.state[0][1] and self.state[0][1]==self.state[0][2]) or
            (self.state[0][0]==self.state[1][1] and self.state[1][1]==self.state[2][2]) or
            (self.state[0][0]==self.state[1][0] and self.state[1][0]==self.state[2][0]))
    r1c1sd = ( #r1 c1 sd
            (self.state[1][0]==self.state[1][1] and self.state[1][1]==self.state[1][2]) or
            (self.state[0][1]==self.state[1][1] and self.state[1][1]==self.state[2][1])   or
            (self.state[0][2]==self.state[1][1] and self.state[1][1]==self.state[2][0]))
    c2r2 = ( #c2 r2
            (self.state[0][2]==self.state[1][2] and self.state[1][2]==self.state[2][2]) or
            (self.state[2][0]==self.state[2][1] and self.state[2][1]==self.state[2][2]))
    win = ((c00 and r0dc0) or (c11 and r1c1sd) or (c22 and c2r2))
    return win

def getLegalMoves(self):
    moves = []
    for r, row in enumerate(self.state):
        for c, col in enumerate(self.state):
            if self.state[r][c] == '-':
                moves.append((r, c))
    return moves  

def getLegalMovesIdx(self):
    moves = []
    for r, row in enumerate(self.state):
        for c, col in enumerate(self.state):
            if self.state[r][c] == '-':
                moves.append(r*3+c)
    return moves 
      
def gameOver(self):
    return self.draw() or self.winner()
\end{verbatim}

```

```

class TicTacToe: def \textbf{init}(self, p1, p2, verbose=True): self.p1
= p1 self.p2 = p2 self.verbose = verbose

\begin{verbatim}
def play(self):
    self.board = Board(self.p1, self.p2)
    if self.verbose:
        print("NEW GAME")
        print(self.board)
    
    self.p1.startGame()
    self.p2.startGame()
    
    cur = self.p1
    winner = None
    while True:
        move = cur.getMove(self.board)
        if self.board.isLegal(move):
            self.board.apply(move, cur.token)

            if self.board.winner():
                if self.verbose:
                    print("And the winner is...\n...{}".format(cur.token))
                    print(cur)
                    print(self.board)
                winner = cur
                break
                
            if self.board.draw():
                if self.verbose:
                    print("Its a draw...")

                winner = None
                break
            
            if cur == self.p2:
                cur = self.p1
            else:
                cur = self.p2
        else:
            if self.verbose:
                print("illegal")
                
            cur.illegal()
    
    if self.verbose:
        print(self.board)

    self.p1.endGame(winner)
    self.p2.endGame(winner)
    
    return winner
\end{verbatim}

``` import numpy as np

class Player: def \textbf{init}(self, token): self.token = token

\begin{verbatim}
def __str__(self):
    return self.token

def illegal(self):
    print("bad move ", self.token)
    return None

def getMove(self, board):
    '''
    board will call this function to get a move 
    from the player whenever it is their turn
    '''
    print("this should be implemented")

def startGame(self):
    pass

def endGame(self, winner):
    pass
    
    
\end{verbatim}

class HumanPlayer(Player):\\
`'' HumanPlayer allows a human to play through the standard input `''
def getMove(self, board): print(``The board state is as follows:'')
print(board) print(``your token is'', self.token) print(``\nWhat is your
move (row col)?''.format(board)) raw = input() spltRaw = raw.split(" ``)
move = (int(spltRaw{[}0{]}), int(spltRaw{[}1{]})) print(move) return
move

class RandomPlayer(Player): def getMove(self, board): moves =
board.getLegalMovesIdx() return moves{[}np.random.randint(len(moves)){]}

class ParametricPlayer(Player): def \textbf{init}(self, token):
Player.\textbf{init}(self, token) self.initWeights()

\begin{verbatim}
def getMove(self, board):
    # represent the board as a column vecotr
    x = self.boardToFeatureVec(board)
    
    # compute a probability distribution over the moves
    probs  = self.predict(x)

    # sample from it
    moveIdx = np.random.choice(np.arange(9), p=np.squeeze(probs)) 
    
    # reformat the choice to a tuple
    move = self.idx2move(moveIdx)
    
    # make sure the choice is legal -- if not set the prob of that move to 0 and resample
    # there is probably a better way to handle this, maybe it should loose if it breaks 
    # the rules...
    moves = board.getLegalMoves()
    while move not in moves:
        probs[moveIdx] = 0
        probs = probs / np.sum(probs)
        moveIdx = np.random.choice(np.arange(9), p=np.squeeze(probs))
        move = self.idx2move(moveIdx)
        
    return move

def predict(self, x):
    '''use logistic regression to predict move'''
    z = np.matmul(self.W, x)
    return self.softmax(z)

def initWeights(self):
    '''ititalize the weights of the model'''
    self.W = 1e-2 * np.random.randn(9, 19)

def softmax(self, x):
    return np.exp(x) / np.sum(np.exp(x))

def boardToFeatureVec(self, board):
    '''
    represent the board as a 19 x 1 column vector with a 1 in the first
    position to account for the bias, the even entries=1 to indicate an X
    and odd entries = 1 to indicate an O
    '''
    vec = np.zeros((1, 18))
    for i, r in enumerate(board.state):
        for j, t in enumerate(r):
            vec[0][(i*3+j)*2 + (1 if t=='O' else 0)] = 1 if board.state[i][j]!='-' else 0
    fvec = np.vstack(([1], vec.T))
    return fvec

def featureVecToBoard(self, vec):
    b = TTT.board.Board(None,None)
    vec = vec[1:]
    for i, v in enumerate(vec):
        j =   i // 2
        row = j // 3
        col = j % 3
        token = '-'
        if vec[i] == 1:
            if i%2 == 0:
                token = 'X'
                b.state[row][col] = token
            else:
                token = 'O'
                b.state[row][col] = token
    return b

def idx2move(self, move):
    return (move // 3, move%3)
\end{verbatim}

```





``` import keras import keras.backend as K from keras.models import
Model, Sequential from keras.layers import Dense, Activation from keras
import optimizers from keras import regularizers K.clear\_session()

class KerasPlayer(PP.ParametricPlayer): def \textbf{init}(self, token):
PP.ParametricPlayer.\textbf{init}(self, token)

\begin{verbatim}
    # build a single hidden layer neural network with 25 hidden units
    self.model = self.buildModel(20, 25) 


def predict(self, x):
    return self.model.predict(x).T

    
def buildModel(self, nin, nh):
    model = Sequential()
    model.add(Dense(nh, input_shape=(nin,), activation='tanh'))
    model.add(Dense(nout, activation='softmax', name='output'))

    opt = optimizers.Adam(lr=0.001)
    
    model.compile(optimizer=opt,
                     loss='sparse_categorical_crossentropy',
                     metrics=['accuracy'])

    return model



def getMove(self, board):
    x = self.board2Vec(board, self.token)
    
    # compute a probability distribution over the moves
    probs  = self.predict(x)

    moveIdx = np.random.choice(np.arange(9), p=np.squeeze(probs)) 
    
    move = self.idx2move(moveIdx)
    
    moves = board.getLegalMoves()
    while move not in moves:
        probs[moveIdx] = 0
        probs = probs / np.sum(probs)
        moveIdx = np.random.choice(np.arange(9), p=np.squeeze(probs))
        move = self.idx2move(moveIdx)
    
    # save the gamestate and move to use as the data for later learning
    self.curX.append(np.squeeze(x))
    

    self.cury.append( moveIdx ) 
\end{verbatim}

``` import copy import numpy as np

class TreePlayer(TTT.player.Player): def \textbf{init}(self, token):
TTT.player.Player.\textbf{init}(self, token)

\begin{verbatim}
def getMove(self, board):
    print("I am", self.token, "I shall play")
    root = TreePlayer.Node(board, self.token, None)
    
    moves = [node.score() for node in root.get_children()]
    
    eval_fn = np.argmax if self.token == 'X' else np.argmin
    a = eval_fn(moves)
    print("idx, move, score\t",a, root.get_children()[a].move, moves[a],"\n")
    return root.get_children()[a].move

class Node:
    '''A node of the game tree'''
    def __init__(self, board, token, move):
        self.board = board
        self.token = token
        self.children = []
        self.move = move

    def __str__(self):
        return self.board.__str__()
    
    
    def get_children(self):
        if len(self.children)==0:
            self.children = self.gen_children()
            
        return self.children
    
    def gen_children(self):
        children = []
        moves = self.board.getLegalMoves()
        for m in moves:
            b = TTT.board.Board(None, None, copy.deepcopy(self.board.state))
            b.apply(m, self.token)
            
            child = TreePlayer.Node(b, self.switchToken(self.token), m)
            children.append( child )
        
        return children
    
    def score(self):
        if self.board.winner():
            score = 1 if self.token=='O' else -1
        else:
            scores = [node.score() for node in self.get_children()]
            eval_fn = max if self.token == 'X' else min
            if self.board.draw(): 
                return 0
            else:
                score = eval_fn(scores)
                
        return score
    
    def switchToken(self, token):
        if token=='X':
            return 'O'
        else:
            return 'X'
\end{verbatim}

\begin{verbatim}
    return move
\end{verbatim}

```

\selectlanguage{english}
\FloatBarrier
\end{document}

