\documentclass[12pt,  portrait,aspectratio=169]{beamer}
% \documentclass[12pt]{beamer}
\usepackage[utf8]{inputenc}
\usepackage{amsfonts, amsthm, amssymb, mathtools,etoolbox}
\usepackage{blindtext}
\usepackage{hyperref}
\usepackage{tikz,tikz-cd}
\usepackage{array}
\usepackage{xcolor}
\usepackage{graphicx}
\usepackage{pifont}
\graphicspath{ {images/} }

\newtheorem{proposition}{Proposition}


\newcommand{\dq}[1]{``#1"}
\newcommand{\memo}[1]{\textcolor{red}{memo: #1}}
\newcommand{\N}{\mathbb{N}}
\newcommand{\Z}{\mathbb{Z}}
\newcommand{\X}{\mathbb{X}}
\newcommand{\Y}{\mathbb{Y}}
\newcommand{\W}{\mathbb{W}}
\newcommand{\gS}{\mathbb{S}}
\newcommand{\C}{\mathcal{C}}
\newcommand{\D}{\mathcal{D}}
\newcommand{\E}{\mathcal{E}}
\newcommand{\F}{\mathcal{F}}
\newcommand{\A}{\mathbb{A}}
\newcommand{\I}{\mathbb{I}}
\newcommand{\id}[1]{\mathrm{id}_{#1}}
\newcommand{\Pf}{\mathcal{P}_{\mathrm{fin}}}
\newcommand{\Set}{\mathrm{Set}}
\newcommand{\Gs}{\mathbf{Games}}
\newcommand{\nsum}{\oplus}
\newcommand{\Alg}[1]{\mathrm{Alg}_{#1}}
\newcommand{\Coalg}[1]{\mathrm{Coalg}_{#1}}
\newcommand{\PfAlg}{\Alg{\Pf}}
\newcommand{\PfCoalg}{\Coalg{\Pf}}
\newcommand{\mex}[1]{\mathrm{mex}(#1)}
\newcommand{\m}{\mathrm{mex}}
\newcommand{\G}[2]{\mathcal{G}_{#1}(#2)}
\newcommand{\rel}{\to}
\newcommand{\red}{\mathrm{red}}
\newcommand{\cp}{\ast}
\newcommand{\acc}{\rightsquigarrow}
\newcommand{\str}{\theta}
\newcommand{\Image}{\mathrm{Im}}
\newcommand{\HF}{\mathbb{HF}}
\newcommand{\Nim}[1]{\mathrm{Nim}_{#1}}
\newcommand{\Her}{\mathbb{H}}
\newcommand{\epi}{twoheadrightarrow}
\newcommand{\mono}{rightarrowtail}
\newcommand{\h}{\mathrm{h}}
\newcommand{\ADJ}[4]
    {
    \begin{tikzcd}[ampersand replacement = \&, column sep = small]
        {#1}
        \ar[rr, shift right=1.3ex, "{#2}"']
        \&\perp\&
        {#3}
        \ar[ll, shift right=1.3ex,"{#4}"']
    \end{tikzcd}
    }
\newcommand{\cmark}{\ding{51}}%
\newcommand{\xmark}{\ding{55}}%
\DeclarePairedDelimiter{\gen}{\langle}{\rangle}


% 定理環境の色の設定
\setbeamercolor{block title theorem}{bg=red!30, fg=black} % 定理環境のタイトル部分の色を変更
\setbeamercolor{block body theorem}{bg=red!10, fg=black} % 定理環境の本文部分の色を変更

% 命題環境の色の設定
\setbeamercolor{block title proposition}{bg=red!30, fg=black} % 命題環境のタイトル部分の色を変更
\setbeamercolor{block body proposition}{bg=red!10, fg=black} % 命題環境の本文部分の色を変更

% 定義環境の色の設定
\setbeamercolor{block title definition}{bg=blue!30, fg=black} % 定義環境のタイトル部分の色を変更
\setbeamercolor{block body definition}{bg=blue!10, fg=black} % 定義環境の本文部分の色を変更

% 例環境の色の設定
\setbeamercolor{block title example}{bg=green!30, fg=black} % 例環境のタイトル部分の色を変更
\setbeamercolor{block body example}{bg=green!10, fg=black} % 例環境の本文部分の色を変更


\usetheme{Darmstadt} 
\usecolortheme{seahorse}
\setbeamertemplate{items}[default]
\setbeamertemplate{navigation symbols}{}
\AtBeginSection[]
{
  \begin{frame}
    \frametitle{Table of Contents}
    \tableofcontents[currentsection]
  \end{frame}
}
\title{Combinatorial games as recursive coalgebras}
\author{Ryuya Hora}
% \institute{Graduate School of Mathematical Sciences, University of Tokyo/ National Institute of Informatics}
% \date{\today}
\date{March 15, 2024}


\begin{document}

\frame{\titlepage}


\begin{frame}\frametitle{Self Introduction}
{\Huge \textbf{Ryuya Hora}}
\begin{itemize}
    \item M2 student at the University of Tokyo
    \item RA at the National Institute of Informatics
    \item (One of) the organizers of Japan Combinatorial Game Theory Workshop!
\end{itemize}
Recently I've been studying
\begin{itemize}
    \item topos,
    \item automata, and
    \item $\infty$-categories.
\end{itemize}
\end{frame}

\begin{frame}\frametitle{This talk in one slide}
\end{frame}

% \section{Front matter}

\section[Introduction]{Introduction: Bouton's theorem}

\begin{frame}{Nim}
\begin{itemize}
  \item In the game \textbf{$n$-heap nim}, first, $n$ heaps of stones are given.
  \item Two players take turns choosing one heap and removing at least one stone from that heap.
  \item The player who is unable to take a stone loses.
\end{itemize}
\memo{write}

\end{frame}
\begin{frame}\frametitle{Bouton's theorem}
\begin{definition}
    The \emph{Nim-sum} $\nsum$ is \dq{bit-wise xor}, i.e., an abelian group structure on $\N$, induced by the binary expansion $\N \overset{\simeq}{\to} \bigoplus_{k=0}^{\infty} \Z/2\Z$.
\end{definition}
\begin{example}
    $5\nsum 7 = (101)_2 \nsum (111)_2 = (010)_2 = 2$
\end{example}
\begin{theorem}[{[Bouton, Ann. of Math., 1902]}]
    A state of $n$-heap nim $(a_1, \dots ,a_n)$ is winning state if and only if $a_1 \nsum \dots \nsum a_n =0$.
\end{theorem}
\begin{example}
    $(1,2,3),(0,1,1), (2,2,0)$ are winning states of the $3$-heap nim.
\end{example}
\end{frame}

\begin{frame}\frametitle{Definition of games}
\begin{columns}
    \begin{column}{0.8 \textwidth}
    \begin{definition}
    A \emph{game} is a pair of a (possibly infinite) set $X$ and a binary relation $\to \subset X \times X$ that satisfies the following two finiteness conditions
    \begin{enumerate}
        \item (finite options) $\# \{x' \in X \mid x\rel x'\}$ is finite, for any $x \in X$.
        \item (finite time) There is no infinite path. $x_0 \rel x_1 \rel x_2 \rel \dots$
    \end{enumerate}
    \end{definition}
    \begin{example}
        \begin{itemize}
            \item \cmark 21-game $(\{0,1, \dots 21\}, x\to x' \colon \iff x'-x \in \{1,2,3\})$
            \item \cmark $(\N,>)$ but  \xmark $(\Z, >)$
            \item \cmark Nim (Stone-taking game) $(\N^n,\to)$
        \end{itemize}
    \end{example}
    \end{column}
    \begin{column}{0.2 \textwidth}
    \begin{figure}
        \centering
        \includegraphics[width=1.1\linewidth]{images/JPEG image-4B87-BA53-02-0.jpeg}
    \end{figure}
    \end{column}
\end{columns}
\end{frame}

\begin{frame}\frametitle{Conway addition of games}
\begin{definition}
    The Conway addition $(X,\to_X) + (Y,\to_Y)$ of two games is the game $(X\times Y, \to_{+})$, where 
    \begin{itemize}
        \item the underlying set is the cartesian product $X\times Y$, and
        \item the relation $\to_{+}$ is defined by
    \[
    (x,y)\to_{+} (x', y') \iff (x\to_{X} x' \land y= y') \lor (x= x' \land y\to_{Y} y')
    \]
    \end{itemize} 
\end{definition}
\end{frame}


\begin{frame}{Nim-sum theorem}
    \begin{theorem}[Nim-sum theorem [see CGT, Siegel]]
        
    \end{theorem}
\end{frame}

\begin{frame}\frametitle{Motivation}
Where does the nim-sum come from?

Why is the nim-sum useful?
\end{frame}

\section[Games $\to$ Recursion]{Games $\to$ Recursion: Recursion in game theory}
\begin{frame}\frametitle{Section 1 in one slide}
\begin{itemize}
  \item \textbf{Combinatorial games} are games \dq{without factors of chance,} and are formalized using graph theory.
  \item A fundamental technique in combinatorial game theory is to define a \textbf{recursive value} for each position of the game and to calculate it.
  \item In this section, we define \textbf{the category of games}, which is the main subject of this talk, in the language of graph theory.
\end{itemize}
\end{frame}



\begin{frame}\frametitle{Recursion 1: Winning/Losing states}
\begin{columns}
    \begin{column}{0.8 \textwidth}
    \begin{definition}
    A \emph{game} is a pair of a (possibly infinite) set $X$ and a binary relation $\to \subset X \times X$ that satisfies the following two finiteness conditions
    \begin{enumerate}
        \item (finite options) $\# \{x' \in X \mid x\rel x'\}$ is finite, for any $x \in X$.
        \item (finite time) There is no infinite path. $x_0 \rel x_1 \rel x_2 \rel \dots$
    \end{enumerate}
    \end{definition}
    
    \end{column}
    \begin{column}{0.2 \textwidth}
    \begin{figure}
        \centering
        \includegraphics[width=1.1\linewidth]{images/JPEG image-4B87-BA53-02-0.jpeg}
    \end{figure}
    \end{column}
\end{columns}
\end{frame}

\begin{frame}\frametitle{Recursion 2: Birthday}
\begin{columns}
    \begin{column}{0.8 \textwidth}
    \begin{definition}
    A \emph{game} is a pair of a (possibly infinite) set $X$ and a binary relation $\to \subset X \times X$ that satisfies the following two finiteness conditions
    \begin{enumerate}
        \item (finite options) $\# \{x' \in X \mid x\rel x'\}$ is finite, for any $x \in X$.
        \item (finite time) There is no infinite path. $x_0 \rel x_1 \rel x_2 \rel \dots$
    \end{enumerate}
    \end{definition}
    \end{column}
    \begin{column}{0.2 \textwidth}
    \begin{figure}
        \centering
        \includegraphics[width=1.1\linewidth]{images/JPEG image-4B87-BA53-02-0.jpeg}
    \end{figure}
    \end{column}
\end{columns}
\end{frame}

\begin{frame}\frametitle{Recursion 3: Grundy number}
\begin{columns}
    \begin{column}{0.8 \textwidth}
    \begin{definition}
    A \emph{game} is a pair of a (possibly infinite) set $X$ and a binary relation $\to \subset X \times X$ that satisfies the following two finiteness conditions
    \begin{enumerate}
        \item (finite options) $\# \{x' \in X \mid x\rel x'\}$ is finite, for any $x \in X$.
        \item (finite time) There is no infinite path. $x_0 \rel x_1 \rel x_2 \rel \dots$
    \end{enumerate}
    \end{definition}
    \end{column}
    \begin{column}{0.2 \textwidth}
    \begin{figure}
        \centering
        \includegraphics[width=1.1\linewidth]{images/JPEG image-4B87-BA53-02-0.jpeg}
    \end{figure}
    \end{column}
\end{columns}
\end{frame}

\begin{frame}\frametitle{Game morphisms}
\begin{definition}
    A \emph{game morphism} $f\colon (X,\to_{X})\to(Y,\to_{Y})$ is a function $f\colon X \to Y$ that satisfies the following two conditions:
    \begin{enumerate}
        \item (Graph map) if $x\to_{X} x'$ then $f(x) \to_{Y} f(x')$.
        \item (Lifting property) if $f(x) \to_{X} y$, then there exists $x\to_{X} x'$ such that $f(x') = y$.
    \end{enumerate}
\end{definition}


\memo{Put an example.}


\end{frame}

\begin{frame}\frametitle{}
\begin{proposition}
    Game morphisms preserve 
    \begin{itemize}
        \item Winning/Losing states,
        \item Birthday,
        \item Grundy numbers,
        \item (and any "recursive data.")
    \end{itemize}
\end{proposition}

\begin{example}
    The terminal game
\end{example}
\end{frame}


\section[Games $\leftarrow$ Recursion]{Games $\leftarrow$ Recursion: Defining games using recursion}

\begin{frame}\frametitle{Section 2 in one slide}
\begin{itemize}
  \item Games = Recursive $\Pf$-coalgebras
  \item Game morphisms = $\Pf$-coalgebra morphisms
  \item Recursive data of games are $\Pf$-algebras (and associated morphisms)
  \item 
\end{itemize}
\end{frame}

\begin{frame}\frametitle{Algebra/Coalgebra of an endofunctor}
\begin{definition}
    For a category $\C$ and an endofunctor $T\colon \C \to \C$, 
    \begin{itemize}
        \item A $T$-algebra is a pair $(A,\alpha)$ of an object $A$ of $\C$ and a morphism $\alpha\colon TA \to A$.
        \item A $T$-coalgebra is a pair $(X,\theta)$ of an object $X$ of $\C$ and a morphism $\theta\colon X \to TX$.
    \end{itemize}
\end{definition}
\begin{example}
    We will consider the case where $\C=\Set$ and $T= \Pf\colon \Set \to \Set$. In this case,
    \begin{itemize}
        \item A $\Pf$-algebra is a function $\Pf(X) \to X$.
        \item A $\Pf$-coalgebra is a function $X \to \Pf(X)$, i.e., a graph whose vertices have finite out-degree.
        \pause \textbf{Games are $\Pf$-coalgebras.}
    \end{itemize}
\end{example}
\end{frame}

\begin{frame}\frametitle{Coalgebra-Algebra morphism and Recursive coalgebra}
\begin{definition}[Coalgebra-algebra morphism]
    % For a category $\C$ and an endofunctor $T$,
    A \emph{coalgebra-algebra} morphism from a $T$-coalgebra $(X,\theta)$ to a $T$-algebra $(A, \alpha)$ is a morphism $f\colon X \to A$ such that the following diagram commutes.
    \[
    \begin{tikzcd}[ampersand replacement=\&]
        X \ar[r,"f"]\ar[d,"\theta"]\&A\\
        TX \ar[r,"Tf"]\&TA\ar[u,"\alpha"']
    \end{tikzcd}
    \]
\end{definition}
\begin{definition}[Recursive coalgebra]
    A $T$-coalgebra $(X,\theta)$ is \emph{recursive} if for any $T$-algebra $(A,\alpha)$, there uniquely exists a coalgebra-algebra morphism $(X,\theta)\to (A, \alpha)$.
\end{definition}
\end{frame}

\begin{frame}\frametitle{Games = Recursive coalgebra}
\begin{theorem}
    The category of games $\Gs$ is equivalent to the category of recursive $\Pf$-coalgebras.
\end{theorem}
\begin{proof}
We can check the following two claims by concrete calculations:
    \begin{itemize}
        \item A $\Pf$-coalgebra $(X, \theta)$ is recursive if and only if its corresponding graph 
    % $(X, \{(x,x')\mid x' \in \theta(x)\})$
    $(X, x' \in \theta(x))$
    \item For two $\Pf$-coalgebras $(X,\theta),(X',\theta)$, a function $f\colon X \to X'$ is a $\Pf$-coalgebra morphism if and only if $f$ is a game morphism.
    \end{itemize}
\end{proof}
    
\end{frame}

\begin{frame}\frametitle{Recursive values = algebras}
% Any $\Pf$-algebra $(A,\alpha)$ defines \dq{recursive data} for games
% \[
% \{\h_{X,A}\colon X \to A\}_{(X,\to)\text{: game}}
% \]
\begin{corollary}
    Let $(A, \alpha)$ be a $\Pf$-algebra.
    For any  game $(X, \to)$, there exists a unique function $\h_{X,A}\colon X\to A$ such that 
    \[
        \h_{X,A}(x) = \alpha(\{\h_{X,A}(x')\mid x\to x'\})
    \]
\end{corollary}
\begin{example}
    W/L states 
    \[
    \Pf(\{W,L\}) \ni
    \]
\end{example}

\memo{Write}
\end{frame}



\section[Application]{Application: Theorem schema for Nim-sum theorem}



\begin{frame}\frametitle{Meta scheme for Grundy-type theorem}
% In this section, let $\otimes$ be a monoidal structure on $\Gs$
For a monoidal structure $\otimes$ on $\Gs$ and a $\Pf$-algebra $(A,\alpha)$, 
\begin{theorem}
    if the forgetful functor $U \colon \Gs \to \Set$ is lax monoidal, then
    
\end{theorem}
\end{frame}

\section{Applications and Future works}

\begin{frame}\frametitle{Categorical structure of games}
\begin{proposition}
    The category of games $\Gs$
    \begin{itemize}
        \item is locally finitely presentable (and in particular, complete and cocomplete).
        \item has a subobject classifier.
        \item admits (Epi, Mono) factorization system.
        \item is NOT cartesian closed.
    \end{itemize}
\end{proposition}
\end{frame}

\begin{frame}\frametitle{Unifying other game theories}
\end{frame}

\begin{frame}\frametitle{Differential structure on Games}
\end{frame}



\end{document}

\begin{frame}\frametitle{}
\end{frame}