继完成自己翻译论文排版之后，我第一次用latex beamer完成了自己的ppt，算是比较不错吧。由于时间仓促，所以在内容上不算是非常充足！

    在这次的实现中，我主要的感想有几点：

1. 一些错误类型，只有自己见得多了，就知道了，特别是一些特殊符号，很容易就报错了；
2. 好的东西是调出来的，最开始的时候或许排版啥的很不好，但是慢点调，总会有属于自己的模版；
3. 语言和语言之间很相似，现在站在一个大的整体上看，感觉就是class的声明，接着就是头文件，也就是包，最后就是正文，和其他语言，如C等，都是如出一辙，所以不用害怕，其实也不难。

    要说的只有这些吧。当自己遇到困难的时候，千万别恼怒，要知道，这是你在进步的预兆。可以看看我最后生成的最终版：http://wenku.baidu.com/view/1d70280bb52acfc789ebc9c6.html?st=1。

    想了想还是附上自己的代码共享给大家，需要注意，目录需要编译两次才出来。我直接用的是latexpdf **.tex：(图片没有给出，大家可以随便弄两张看看)

\documentclass[cjk,slidestop,mathserif]{beamer}

\usepackage{CJK}
\usepackage{beamerthemesplit} 
\usepackage{graphicx}
\useoutertheme{infolines}

\usetheme{Warsaw}	
\usecolortheme{crane}
\usecolortheme{seagull}

\setbeamertemplate{items}[ball]

\setbeamertemplate{blocks}[rounded][shadow=true]
\setbeamertemplate{navigation symbols}{}%去除底部比较酷的工具条，因为实际应用的很少

\begin{document}
\begin{CJK}{UTF8}{gkai}

\title{博弈论之公平组合游戏}
\author{欧阳梦云}
\institute[HUST]{华中科技大学}
%\date{\today}
\frame{\titlepage}
 
\frame{\tableofcontents}

\section{Introduction}

\subsection{An example}

\begin{frame}
\vspace{12pt}
 \frametitle{An example}\pause
 \begin{example}
  Description:\\
  有21枚石子组成的石堆，两人轮流进行游戏。每次游戏者可以
  取走石堆中不超过3枚的石子。谁取走最后一颗为胜利。
 \end{example}
\pause
$\clubsuit$ 你会先取么？ \\

\vspace{36pt}
\pause
Analysis：1，2，3 || 4 || 5，6，7|| 8 ... \\ 

\vspace{18pt}
\pause
Conclude：先走，取一个石子
\end{frame}

\subsection{Background}

\begin{frame}
 \frametitle{应用背景}
 \vspace{12pt}
 博弈论在当今的生活中，几乎每个领域都会或多或少的涉及。
   \begin{itemize}
    \item<1-> 经济学领域中的，一个比较经典的博弈问题就是{\alert{“囚徒困境”}}；
    \item<2-> 我们熟知的象棋比赛，电脑游戏；
    \item<3-> 甚至在生物领域，还存在着动物之间的博弈等等。
   \end{itemize}
   \vspace{10pt}
   \begin{table}
        \begin{tabular}{|c|c|c|}
        \hline
        甲乙策略 & 甲沉默 & 甲背叛 \\
        \hline
        乙沉默 & 二人同服刑一年 & 乙服刑10年，甲释放 \\
        \hline
        乙背叛 & 甲服刑10年，乙释放 & 二人同服刑8年 \\
        \hline
        \end {tabular}
    \end {table}
\end{frame}


\subsection{Definition}
\begin{frame}
 \frametitle{公平组合游戏}
 \vspace{16pt}
 公平组合游戏是博弈论的一个子集，它的成立需要如下前提：
 %\pause
 \vspace{6pt}
 \begin{enumerate}
  \item<1-> 两个参与者，游戏局面的状态集合是有限的；
  \item<2-> 在同一个局面下，两操作者可选择的操作集合完全相同，但每步必须得走；
  \item<3-> 无论如何游戏会在有限步内结束，且没有平局；
  \item<4-> 当无法进行操作时游戏结束，此时不能进行操作的一方输。
 \end{enumerate}

\end{frame}

\begin{frame}[label=here]
\vspace{12pt}
 \frametitle{P-position and N-position 定义}
 \begin{definition}
  P-position：后手必胜局面，winning for the Previous player。 \
  \
  \vspace{8pt}
  N-position：先手必胜局面，winning for the Next player。
 \end{definition}
 \vspace{24pt}
 \pause
  上面的例子中已经清晰的给出了这两种状态，\\
  \vspace{6pt}
  P-position就是上面的0，4，8，12... \\
  \vspace{6pt}
  N-position就是例如1，2，3，5...
\end{frame}

\subsection{Algorithm}
\begin{frame}
\vspace{12pt}
 通过上面的例子我们可以归纳出一般解决公平组合游戏的算法：
 \begin{enumerate}
  \item <1->将最终状态标记为P-position；
  \item <2->通过一步可以到达P-position的，都标记为N-position；
  \item <3->找到这样一个position，其所有的选择都只会到达N-position，将其标记为P-position；
  \item <4->如果在第3步中找到了一个P-position，则停止。否则继续第二步。
 \end{enumerate}
 \pause
\pause
\pause
 \pause
 \hyperlink{here}{\beamerbutton{$\blacklozenge$实例}}
 我们需要注意，这个算法是从最后状态分析。\\
 \pause
 \vspace{12pt}
 从算法中，我们也可以看出，P-position和N-position性质： \\
 $\clubsuit$ \color{blue}{所有的最终状态都是P-position；} \\
 \vspace{6pt}
 \pause
 $\clubsuit$ \color{blue}{从每个N-position，至少有一种方法可以到P-position；} \\
 \vspace{6pt}
 \pause
 $\clubsuit$ \color{blue}{每个P-position，每种方法都到达N-position。} \\
\end{frame}

\section{nim游戏}    %section
\subsection{An Typical Example}

\begin{frame}
\frametitle{An Example}
\vspace{12pt}
\begin{example}
Description: \\
现有5堆石子，石子的个数分别是2，3，4，甲乙两个参与者每次从这3堆石子中任选一堆取走石子，\
每次取走至少一个，至多整堆。最后取光者胜利。 
\end{example}
\vspace{16pt}
\pause
\ 问题：利用上面的策略分析依稀，如果你是甲，你会先走么？你该怎么走？

\pause
\pause
Analysis: \\
P-position (0,0,0)，如果只有两堆且等量，(0,1,1) or (0,2,2)... \\
\pause
\vspace{12pt}
如果堆的个数增加到100个以上，我们又怎么分析呢？ 
\end{frame}

\subsection{Conclude}

\begin{frame}
 \frametitle{Conclude}
 \vspace{12pt}
 \begin{alertblock}{Conclude}
  其实整个问题比较复杂，不过这类问题已经形成了一个有公式的解法，那就是每堆的个数相互“抑或”,\
  例如每堆的个数是$a_{1}$，$a_{2}$，...$a_{n-1}$,$a_{n}$,则 \
  $a_{1}$ $\bigoplus$ $a_{2}$ $\bigoplus$ $a_{3}$ ... $a_{n-1}$ $\bigoplus$ $a_{n} $)，\
  
  如果最后的结果是0，代表当前状态为P-position； \\
  非0，代表当前状态为N-position。\\
 \end{alertblock}
 \vspace{6pt}
 这样一来，问题也很简单了。
 \pause
 \vspace{20pt}
 PS:已经有人给出了准确的证明!大家有兴趣的可以看看。

\end{frame}

\section{Sum of Combinatorial Games}
\subsection{mex definition}

\begin{frame}
 \frametitle{mex(minimal excludant)运算}
 \vspace{18pt}
 \begin{definition}
  mex mex运算，就是施加在一个集合上的运算，表示最小的不属于这个集合的非负整数。 
 \end{definition}
 \vspace{8pt}
 例如mex$\{$0,1,2,4$\}$=3，mex$\{$2,3,5$\}$=0。 
 \vspace{12pt}
 \pause
 \begin{alertblock}{引申}
  对于有向无环图，定义关于图的每个顶点的Sprague-Garundy函数g为：g($x$)=mex$\{$g($y$) $\mid$ $y$是$x$的后继$\}$。
 \end{alertblock}

\end{frame}

\subsection{The Sprague Grundy Theorem}
\begin{frame}
\frametitle{SG函数和公平组合游戏}
\vspace{14pt}
 $\bigstar$上面已经给出了SG函数的定义。现在大家应该有很多疑问，为什么会引出SG函数？？ \\
 \pause
 \vspace{10pt}
 $\circlearrowleft$其实我们可以将所有的公平组合游戏抽象成一个有起始点的有向五环图，在顶点上有一枚石子，两名选手交替将石子移动，最后无法移动者为败。
 \\
 \pause
 \vspace{8pt}
 $\circlearrowright$这样一来，公平组合游戏中每个局面可以看作图的顶点，而顶点之间的边，即为操作。\
 经过抽象之后，很多问题就可以得到解决了，甚至可以给出所有的必胜操作步骤，以及每一步具体怎么操作。
\end{frame}

\begin{frame}
 \frametitle{SG函数和公平组合游戏}
 \vspace{14pt}
 首先，所有最终节点，也就是没有出边的顶点，SG值为0，因为后继集合是空集。\\
 \pause
 \vspace{6pt}
 其次，对于一个$g(x)=0$的顶点$x$，他的后继$y$都满足$g(y)!=0$。\\
 \vspace{4pt}
 而对于一个$g(x)!=0$的顶点，必定存在一个后继$y$,满足$g(y)=0$。\\
 \vspace{10pt}
 \pause
 \begin{alertblock}{对应到公平组合游戏上}
  结合上面所说道的P-position和N-position的定义以及性质，我们可以看到，顶点$x$所代表的position是P-position \
  当且仅当$g(x)=0$,我们通过计算有向无环图每个顶点的SG值，就可以找到所有的必胜策略了。
 \end{alertblock}

\end{frame}

\begin{frame}
 \frametitle{An example}
  下图给出的是一个SG推倒函数，其中最开始有4个终节点，SG值都为0，接着a点和b点都被给出，上面的是通过推断的。
  \begin{figure}
    \includegraphics[width = 8cm]{sg.jpg}
  \end{figure} 

\end{frame}

\begin{frame}
 \frametitle{Conclude}
 \vspace{10pt}
 \begin{alertblock}{example}
  再给出一种情况，有n堆石子，每次可以从第一堆里去1，2，3颗，可以从第二堆里取奇数颗，第三堆及以后可以取任意颗。
 \end{alertblock}
 \vspace{6pt}
 这个问题我们又怎么解决呢？？ \\
\pause
\vspace{10pt}
其实我们可以把这个问题看作3个游戏，每个游戏对应有向无环图的一个顶点，这样一来，有向无环图有3个顶点。 \\
\vspace{4pt}
\pause
也就是进一步将SG函数抽象,\\
\pause
对应的第一个游戏，SG值是$x\%2$（$x$是一堆石子的个数）；\\
\pause
第二个游戏的SG值是$x\%2$； \\
\pause
第三个游戏对应的是一个$n-2$的nim游戏。
\end{frame}

\begin{frame}
 \frametitle{Conclude}
 \vspace{10pt}
 \begin{alertblock}{example}
  再给出一种情况，有n堆石子，每次可以从第一堆里去1，2，3颗，可以从第二堆里取奇数颗，第三堆及以后可以取任意颗。
 \end{alertblock}
\pause
\vspace{10pt}
 $\cdots$紧接着上面的分析：\\
 \vspace{6pt}
 在求得每个游戏SG值后，然后将所有的异或，也就得到了整体的SG值，这样就可以判断是否有必胜策略了。\\
 \pause
 \vspace{10pt}
 SG函数是让我们遇到看上去很复杂的游戏试图分成若干个子游戏，然后找出最终的SG值，来解决问题。\\
 \vspace{6pt}
 \pause
 当然了，这里的游戏还有很多变型模式，所以SG函数的应用领域就很广泛了。下面就是一个比较好的应用：
\end{frame}

\subsection{Applications}

\begin{frame}
\frametitle{具体应用}
\vspace{12pt}
这里所说的应用主要是在算法上的应用，当然了，博弈还可以用来写象棋程序等。
\begin{alertblock}{problems}
 \begin{enumerate}
  \item[1$\>$]http://acm.hdu.edu.cn/showproblem.php?pid=1907 
  \item[2$\>$]http://acm.hdu.edu.cn/showproblem.php?pid=2509
  \item[3$\>$]http://acm.hdu.edu.cn/showproblem.php?pid=1536
  \item[4$\>$]http://acm.hdu.edu.cn/showproblem.php?pid=1944
 \end{enumerate}

\end{alertblock}
\end{frame}

\frame{
    \frametitle{Questions and answers}
    \begin{figure}
        \includegraphics[width=6cm]{faq.jpg}
    \end{figure}
}
 
\end{CJK}
\end{document}