← rota-baxter-winning-games
CSCAT2024__main1.tex
\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}
% \usepackage{fontspec}
% \usepackage{luatexja-fontspec}
% \setsansfont{Arial} % 任意のフォントに変更可能
% \setmainjfont{YuGothic} % 日本語フォントを設定
\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{\xem}{\mathrm{opm}}
\newcommand{\m}{\mathrm{mex}}
\newcommand{\G}[2]{\mathcal{G}_{#1}(#2)}
\renewcommand{\O}[2]{\mathcal{O}_{#1}(#2)}
\newcommand{\B}[2]{\mathcal{B}_{#1}(#2)}
\newcommand{\M}[2]{\mathcal{M}_{#1,#2}}
\renewcommand{\H}[3]{\mathcal{H}_{#1,#2,#3}}
\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}
\newenvironment<>{question}[1][]{%
\setbeamercolor{block title}{fg=white,bg=red!75!black} % Set the block title color to red
\setbeamercolor{block body}{fg=black,bg=red!20!white} % Set the block body color to light red
\begin{block}#2{#1}}
{\end{block}}
\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}
\begin{frame}\frametitle{Table of Contents}
\tableofcontents
\end{frame}
\section[Introduction]{Introduction: Bouton's theorem}
% \subsection{Nim and 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}
% \subsection{Games and its addition}
\section{Combinatorial Games and generalized Bouton's theorem}
\begin{frame}\frametitle{Definition of games}
\begin{columns}
\begin{column}{0.8 \textwidth}
\begin{definition}[Game]
A \emph{game} $\X=(X,\to)$ 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}
\begin{example}[$\Nim{n}$: $n$-heap nim]
The game $\Nim{n} = (\N^{n},\to)$ is
% a game whose underlying set is $\N^{n}$ and relation $\to \subset \N^{n} \times \N^{n}$ is
defined by
\[
(a_i)_{1\leq i \leq n} \to (b_i)_{1\leq i \leq n} \iff
\exists i (a_i> b_i \land a_j = b_j (j\neq i))
\]
\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}{Outcome: Winning/Losing state}
\begin{columns}
\begin{column}{0.8 \textwidth}
\begin{definition}[Outcome]
For a game $\X=(X,\to)$ and a state $x\in X$, its \emph{outcome} $\O{\X}{x}$ is recursively defined by
\[
\O{\X}{x}\coloneqq
\begin{cases}
W & (x\to \forall x' , \O{\X}{x'}=L)\\
L & (x\to \exists x' , \O{\X}{x'}=W)
\end{cases}
\]
\end{definition}
\begin{proposition}
For a game $\X=(X,\to)$, a state $x$ is a winning state if and only if $\G{\X}{x}=0$.
\end{proposition}
\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}[Conway addition]
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}
\begin{example}
$\Nim{n} = \Nim{1} + \dots + \Nim{1}$
\end{example}
\memo{Write a diagram!}
\end{frame}
\begin{frame}{Grundy number}
\begin{columns}
\begin{column}{0.8 \textwidth}
\begin{definition}
The \emph{mex} of a finite subset $S \subset \N$ is $\min{(\N\setminus S)}$.
\end{definition}
% \begin{example}
% $\mex{\{0,1,2,4,6}\} = 3$, \hspace{10pt}
% $\mex{\emptyset}
% % =\min{\N \setminus \emptyset}
% =0$
% \end{example}
\begin{definition}[Grundy number]
For a game $\X=(X,\to)$ and a state $x\in X$, its \emph{Grundy number} $\G{\X}{x}$ is recursively defined by
\[
\G{\X}{x}\coloneqq \mex{\{\G{\X}{x'}\mid x\to x'\}}
\]
\end{definition}
\begin{proposition}
For a game $\X=(X,\to)$, a state $x$ is a winning state if and only if $\G{\X}{x}=0$.
\end{proposition}
\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}{Generalized Bouton's theorem}
\begin{theorem}[{Generalized Bouton's theorem [see CGT, Siegel]}]
For two games $(X, \to_X)$ and $(Y, \to_Y)$,
we have
\[
\G{\X+\Y}{x,y} = \G{\X}{x} \nsum \G{\Y}{y}.
\]
\end{theorem}
\begin{example}[Original Bouton's theorem]
$\G{\Nim{n}}{(a_i)_{1\leq i \leq n}} = \G{\Nim{1}}{a_1}\nsum \dots \nsum \G{\Nim{1}}{a_n} = a_1 \nsum \dots \nsum a_n$
\end{example}
Generalized Bouton's theorem is one of the most important tools in combinatorial game theory.
\end{frame}
\begin{frame}\frametitle{Motivation}
Where does the nim-sum come from?
Why is the nim-sum useful?
\end{frame}
\section{Category of games}
% \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}
% For a game $\X $
% \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: 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}{What is a morphism of games?(1/2): Historical Remark}
Historically, morphisms of games have been (relative) \emph{strategies}:
\begin{itemize}
\item A. Joyal, Remarques sur la théorie des jeux à deux personnes, 1977
\item M. Hyland, Game semantics, 1997
\item J.Baez, Classical vs Quantum Computation (Week 3) (The n-Category Caf\'{e}), 2006.
\end{itemize}
However, we will adopt a more classical categorical approach, which is to define a morphism as a \dq{structure-preserving function}.
\end{frame}
\begin{frame}\frametitle{What is a morphism of games?(2/2): Our definition}
\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}
% \begin{figure}
% \centering
% \includegraphics[width=0.6\linewidth]{images/Gamemorphisms.jpeg}
% \end{figure}
% \begin{figure}
% \centering
% \includegraphics[width=0.75\linewidth]{images/Game_Morphisms.jpeg}
% \end{figure}
% \memo{Put an example.}
\begin{figure}
\centering
\includegraphics[width=1\linewidth]{images/Game_morphisms3.jpeg}
\end{figure}
\end{frame}
\begin{frame}\frametitle{}
We can prove game morphisms preserve \dq{game-theoretic data}:
\begin{proposition}
Game morphisms preserve
\begin{itemize}
\item Winning/Losing states,
\item Grundy numbers,
% \item Birthday (= height = the length of the longest path),
\item (and any "recursive data.")
\end{itemize}
\end{proposition}
\begin{example}[Birhtday]
For a game $\X=(X,\to)$ and a state $x\in X$, its \emph{birthday} $\B{\X}{x}$ is recursively defined by
\[
\B{\X}{x} =
\begin{cases}
0 &(\{x' \mid x\to x'\}= \emptyset)\\
\displaystyle 1+ \max_{x\to x'} \B{\X}{x'} & (otherwise).
\end{cases}
\]
\end{example}
% \begin{proposition}
% The category of games $\Gs$ is complete and cocomplete.
% \end{proposition}
% \begin{example}
% The terminal game $T=(\N, \to_{\text{bin}})$
% \end{example}
\end{frame}
\begin{frame}\frametitle{Categorical structure of games}
The category of games $\Gs$ has good categorical properties, including:
\begin{proposition}[$\Gs$ is LFP.]
The category of games $\Gs$ is locally finitely presentable. In particular, it is complete and cocomplete.
\end{proposition}
% \memo{Terminal, subobject classifier}
Colimits are created by $U\colon \Gs \to \Set$, but limits are non-trivial!
\begin{example}[The terminal game]
The terminal game $T=(\N, \to_{\text{bin}})$ is the \emph{binary nim}.
% whose underlying set is $\N$ and
For $n,m\in \N$, $n\to_{\text{bin}}m$ if $m$ appears in the binary expasion of $n$. For example,
\[
10000=2^{4}+2^{8}+2^{9}+2^{10}+2^{13}\to_{\text{bin}} 4,8,9,10,13.
\]
\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}
\[
\begin{tikzcd}[ampersand replacement = \&, row sep = 5pt]
\text{ W/L states} \& \leftrightsquigarrow\&\Pf(\{W,L\})\ar[r]\& \{W,L\}\\
\text{Grundy number} \& \leftrightsquigarrow\& \Pf(\N)\ar[r,"\mathrm{mex}"]\& \N\\
\text{Birthday} \& \leftrightsquigarrow\& \Pf(\N)\ar[r,"1+ \max"]\& \N\\
\end{tikzcd}
\]
\end{example}
% \memo{Write}
\end{frame}
\begin{frame}{Digression: Grundy $\vdash$ Nim $\vdash$ Birthday}
The most important game, Nim, and the two most important values, Grundy number and birthday, characterize each other by adjunction!
% First, the ($1$-heap) Nim is the von Neumann formulation of numbers:
% \[
% \Nim{1} = \nu\colon \N \to \Pf(\N)\colon n \mapsto \{0, \dots, n-1\}
% \]
\[
\begin{tikzcd}[ampersand replacement=\&, column sep = 150pt]
(\N,\leq) \ar[r,"\Nim{1}", ""'{name=M}]\& (\Pf(\N), \subset) \ar[l,"\m",""'{name=B}, bend left]\ar[l,"1+\max"',""{name=U}, bend right]\ar[phantom, "\perp", from = B, to= M]\ar[phantom, "\perp", from = M, to= U]
\end{tikzcd}
\]
\end{frame}
\section[Application]{Application: Generalized generalized Bouton's theorem}
\begin{frame}{Let's return to our original motivation!}
% Then, let's return to our original motivation!
\begin{block}{Motivation}
Where does Nim-sum come from?
\end{block}
In this section,
\begin{itemize}
\item let $\ast$ be a monoidal structure on $\Gs$ such that the forgetful functor
\[
U \colon \Gs \to \Set
\]
is lax monoidal, and
\item let $\A= (A, \alpha)$ be a $\Pf$-algebra.
\end{itemize}
\begin{example}
The prototypical example is the Conway addition $\ast=+$ and the W/L algebra $\A = (\{W,L\}, \alpha)$.
\end{example}
\end{frame}
% \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}
\begin{frame}\frametitle{The reduced monoid}
\begin{definition}[The reduced monoid]
Then we can construct the \emph{reduced monoid} $\M{\ast}{\A}$ by the following procedure:
\begin{enumerate}
\item The terminal game $T$ has the unique monoid structure w.r.t. $(\Gs,\ast)$.
\item The forgetful functor $U\colon \Gs \to \Set$, which is lax-monoidal, induces a monoid structure on the set $UT$.
\item Let $\M{\ast}{\A}$ be the maximum quotient monoid of $UT$ that the canonical map $\h_{T,\A}\colon UT \to A$ factor through.
\end{enumerate}
\end{definition}
The multiplication of $\M{\ast}{\A}$ is denoted by $\circledast$.
For any game $\X = (X, \to)$, there is a canonical map
\[
\H{\ast}{\A}{\X}\colon X= U\X \to UT \to \M{\ast}{\A}
\]
\end{frame}
\begin{frame}\frametitle{Generalized generalized Bouton's theorem}
So far, from
\begin{itemize}
\item a monoidal structure $\ast$ on $\Gs$ such that $U$ is lax monoidal, and
\item a $\Pf$-algebra $\A$
\end{itemize}
we have obtained
\begin{itemize}
\item the reduced monoid $(\M{\ast}{\A}, \circledast)$, and
\item a function $\H{\ast}{\A}{\X}\colon X \to \M{\ast}{\A}$ for each game $\X$.
\end{itemize}
\begin{theorem}[Generalized generalized Bouton's theorem]
For two games $\X$ and $\Y$, we have
\[
\H{\ast}{\A}{\X\ast \Y}(x,y) = \H{\ast}{\A}{\X}(x) \circledast \H{\ast}{\A}{\Y}(y)
\]
\end{theorem}
\end{frame}
\begin{frame}\frametitle{Where does the Nim-sum come from?}
\begin{proposition}
Consider the case where $\ast$ is the Conway addition $+$, and $\A$ is the W/L algebra.
\begin{itemize}
\item In this case, the generalized generalized Bouton's theorem coincides with the original Bouton's theorem.
\item That is, we have $\H{+}{W/L}{\X}(x) = \G{\X}{x}$, and
% is equal to $\mathcal{G}_{\X}\colon X \to \N$, and
\item the reduced monoid $\M{+}{W/L}$ is isomorphic to the abelian group of nim-sum $(\N, \nsum)$!!
\end{itemize}
\end{proposition}
\end{frame}
% \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{Future works}
\begin{frame}\frametitle{Other instances of the gen. gen. Bouton's theorem}
% Our theorem is far more general than the, so b
By considering other monoidal structures, we want to provide new theorems to combinatorial game theory (and write a paper)!
\begin{itemize}
\item I have already constructed another monoidal structure,
\pause
\item obtained another instance of the generalized generalized Bouton's theorem,
\pause
\item which was quite non-trivial and practical method,
\pause
\item but was already known as \emph{remoteness method} in CGT.
\pause
\end{itemize}
\begin{question}[Open question]
Classify all monoidal structure on $\Gs$ such that $U \colon \Gs \to \Set$ is (lax) monoidal.
\end{question}
\end{frame}
\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}
% \memo{Terminal, subobject classifier}
\begin{question}[Open question (vague)]
Is there a \dq{nice} Grothendieck topos that contains $\Gs$ as a coreflective subcategory?
\end{question}
\end{frame}
\begin{frame}\frametitle{Unifying other game theories}
Our approach does not depend on $\Set$ and $\Pf$, and may be applicable for a broader class of categories and endofunctors.
\begin{question}[Open question]
Generalize our framework to a (locally presentable) category and an (accessible and taut) endofunctor.
\end{question}
This is motivated not only by category theory, but also by game theory!
% rather than category theory!
\begin{itemize}
\item Transfinite games ($\mathcal{P}_{< \kappa}\colon \Set \to \Set$)
\item Partizan games ($\Pf\times \Pf \colon \Set \to \Set$)
\item Multi-player games (?)
\item Probabilistic games (?)
\end{itemize}
\end{frame}
\begin{frame}\frametitle{Differential structure on Games}
Considering the origin of nim-sum, I am not fully satisfied with this result. In particular, we did mot demystify the following non-trivial equation, which was crucial to prove the original Bouton's theorem:
\begin{proposition}
% For any $S, T \in \Pf(\N)$,
\[
\mex{S}\nsum\mex{T} = \mex{(S\nsum\mex{T}) \cup (\mex{S}\nsum T)}.
\]
\end{proposition}
To me, this looks like the Rota-Baxter equation:
\[
\textstyle (\int f) \cdot (\int g) =\int((f \cdot \int g) + (\int f \cdot g)).
\]
\begin{question}[Open question]
Is there a differential $2$-rig structure on $\Gs$?
\end{question}
\end{frame}
\begin{frame}\frametitle{References}
\begin{description}
\item[Joyal] Remarques sur la théorie des jeux à deux personnes, 1977.
\item[Honsell and Lenisa] Conway Games, Coalgebraically, 2009.
\item[Adamek, Milius, and Moss] On Well-Founded and Recursive Coalgebras, 2020.
\item[Taylor] Practical foundations of mathematics, 1999.
\item[Abuku, Sakai, and Suetsugu] %組合せゲーム理論の世界
\end{description}
\begin{description}
\item[Joyal] Remarques sur la théorie des jeux à deux personnes, 1977.
\item[Honsell and Lenisa] Conway Games, Coalgebraically, 2009.
\item[Adamek, Milius, and Moss] On Well-Founded and Recursive Coalgebras, 2020.
\item[Taylor] Practical foundations of mathematics, 1999.
\item[Abuku, Sakai, and Suetsugu] %組合せゲーム理論の世界
\end{description}
\end{frame}
\end{document}
\begin{frame}\frametitle{}
\end{frame}