chap5.tex

\chapter{蒙特卡洛智能体}
\label{section:MonteCarloPlayers}

本章主要讲述本文所使用的蒙特卡洛智能体的主要设计。\ref{section:MonteCarloSearchPlayer}~节首先给出将蒙特卡洛搜索应用于炉石传说的基本方法；
\ref{section:MonteCarloTreeSearchPlayer}~节首先讨论了蒙特卡洛树搜索如何使用确定化的思想来应对像炉石传说这样的隐藏信息随机游戏，
进而讨论了为何朴素的蒙特卡洛树搜索无法被直接应用于炉石传说，并在最后给出可对蒙特卡洛树搜索进行的相关优化。

\section{蒙特卡洛搜索智能体}
\label{section:MonteCarloSearchPlayer}

除了随机和规则智能体外，本文主要测试的智能体由蒙特卡洛搜索进行实现。具体而言，本文使用的蒙特卡洛智能体实现了可用于解决多臂赌博机问题的~UCB1~算法~\cite{auer2002finite}。
在多臂赌博机问题中，参与者需要在若干个随机出奖的赌博机之间进行选择，而使用~UCB1~算法能确保参与者在足够多次的尝试后获得最高的收益。

根据~\ref{section:MonteCarloSearch}~节所述的~UCB1~算法的基本过程，将其应用于炉石传说也并非难事。蒙特卡洛智能体的决策过程基本如下：
\begin{enumerate}
\item 根据当前游戏状态枚举出智能体在当前回合可以进行的所有操作序列；
\item 为每个可进行的操作序列均将游戏模拟至游戏结束，并保存模拟的结果；
\item 进入~UCB1~算法的循环阶段，使用公式~\ref{eq:UCB1}~选取操作序列并将游戏模拟至游戏结束，然后保存模拟的结果；
\item 在满足一定的预设条件后结束循环，并返回平均收益~$\bar{x}_j$~最高的操作序列。
\end{enumerate}

\section{蒙特卡洛树搜索智能体}
\label{section:MonteCarloTreeSearchPlayer}

上一节所描述的蒙特卡洛搜索智能体的缺陷在于其无法将操作过程中可能触发的隐藏信息纳入考虑，因为所有可能的操作序列在搜索开始前便以结束枚举。
能触发隐藏信息的操作在炉石传说随处可见，包括如图~\ref{fig:ragnaros}~中的炎魔之王拉格纳罗斯的随机效果，或是如图~\ref{fig:hs-hiddenInformationCard}~中的会触发抽牌动作的卡牌。
而使用蒙特卡洛树搜索则可以考虑这些可能被触发的隐藏信息。

\begin{figure}[!ht]
\centering
\includegraphics[width=2.5in]{img/Fig5-1a.png}
\includegraphics[width=2.5in]{img/Fig5-1b.png}
\caption{能触发隐藏信息的炉石传说卡牌}
\label{fig:hs-hiddenInformationCard}
\end{figure}

\subsection{确定化}
\label{section:Determinization}

确定化（Determinization）是一种可被用于为带随机和隐藏信息的游戏制作人工智能的办法，它又被称为完全信息蒙特卡洛（Perfect Information Monte Carlo）。对于给定的一局带有随机因素和隐藏信息的对弈，
它的\textbf{确定化}即为与其等效的完全信息的确定型对弈，其中当前的对弈状态将根据智能体所知悉的信息集进行生成，而所有原本的概率事件在确定化的版本中，它们的结果都是确定的。比如说，
卡牌游戏中最典型的游戏信息包括对手与我方牌堆出牌的顺序以及对手的手牌，那么在对应的确定化游戏中，双方的手牌和牌堆都是可见的。那么，智能体就可以通过已经知悉的信息推断出隐藏信息的可能结果，
并从中选择若干个结果组成若干个确定化版本，而后对确定化的对弈采用智能体所采用的算法进行决策，最终通过合并这些决策来决定在原本的隐藏信息的对弈下所应进行的决策。

在~\cite{cowling2012ensemble}~一文中，确定化的蒙特卡洛树搜索被应用于万智牌的手牌决策。在决策时，智能体会为每一个确定化构造一棵独立的蒙特卡洛树。对于每一棵蒙特卡洛树，
它们的所有隐藏信息的结果都会在构造前预先随机确定。以抽卡为例，当蒙特卡洛树进入状态~$s$~后需要进行抽卡，那么智能体将对抽卡的动作进行一次随机采样，得出一个拥有固定结果的结果操作~$a$~，
而操作~$a$~将使蒙特卡洛树从状态~$s$~进入状态~$s'$~。那么，在之后每一次蒙特卡洛树进入状态~$s$~时，智能体便不会再进行采样，而是让蒙特卡洛树直接进入状态~$s'$~。

确定化的使用无疑是必然的。考虑到万智牌的一副卡组中通常包含~60~张卡，其中大约可包含~15~种不同的卡。如果在蒙特卡洛树向下延伸的过程中每次遇到随机事件都考虑所有可能的结果的话，
蒙特卡洛树的分支系数将会以~$O((n!)^2)$~的速度上升。例如，一个回合中可进行的操作可能有~$5\sim 6$~种，那么第~1~层的分支系数可能就会达到~$75\sim 90$~，第~2~层就会达到~$7000\sim 8000$~，
而在第~3~层的时候就上百万了。在这种情况下，如果仍需要蒙特卡洛树给出相对可靠的结果，那么模拟的次数同样也需要一同增长，最终导致蒙特卡洛树搜索难以在有限的时间内做出决策。
尽管炉石传说中的一副卡组只包含~60~张卡，但分支系数上升的速度依旧是相同的。

在综合~\ref{section:MonteCarloTreeSearch}~节所述的蒙特卡洛树搜索基本原理与~\ref{section:MonteCarloSearchPlayer}~节所述的蒙特卡洛搜索智能体的具体实现后，
蒙特卡洛树搜索智能体的具体实现便十分直观，在此便不再赘述。

值得注意的是，蒙特卡洛树搜索与蒙特卡洛搜索在执行步骤上的差异在于，蒙特卡洛树搜索需要对一棵树进行不断地扩展，每一次迭代都有可能需要为某个结点扩充子结点。
随着迭代数的增加，蒙特卡洛树的深度不断增加，在一次搜索中发生的可进行操作枚举的次数也会逐渐增加，而蒙特卡洛搜索则只需要在搜索的最开始的时候进行一次操作枚举。在实际测试时，
蒙特卡洛树搜索智能体的时间占用在蒙特卡洛搜索智能体的十倍以上，性能的瓶颈就在于操作枚举的步骤。对于炉石传说而言，
由于可进行的三种决策的顺序是不定的，以不同的顺序执行同样的操作也有可能意味着不同的结果，因此随着游戏进行到大约第~$6$~回合时，暴力枚举所能获取的可执行的操作序列便可能达到数万个，
而这其中只有少数几个是有价值的。因此直接将朴素的蒙特卡洛树搜索应用于炉石传说是不实际的。

\subsection{相关优化}
\label{section:Optimization}

尽管蒙特卡洛树搜索智能体的实现十分直观，但鉴于蒙特卡洛树的深度会随着模拟次数的增加而增加，在不对蒙特卡洛树搜索进行一定的优化的情况下，智能体恐怕难以在有限的时间内给出可靠的结果。
可对蒙特卡洛树搜索进行的性能方面的优化包括如下两点：

\begin{itemize}
\item \textbf{合并确定化采样}：确定化的思想要求在每次需要进行抽卡时都对抽卡的结果进行一次随机采样。实际上这样的效果等同于确定了双方牌组的出牌顺序，
因此完全可以在构建确定化所拥有的蒙特卡洛树之前，提前确定该确定化所对应的双方牌组顺序以及对手的手牌，如此一来便无需在遍历蒙特卡洛树的过程中再进行采样。
\item \textbf{操作剪枝}：蒙特卡洛树搜索的执行效率很大程度上取决于当前可进行操作序列的数量。当操作数量增加时，蒙特卡洛树搜索的耗时也会以很快的速度上升。
除此之外，操作数量的减少也使得在固定模拟次数的情况下，不同的操作可以被进行更多次的模拟，使得其近似得出的期望收益更加可靠。通过预定义的基于规则的启发知识，
智能体可在开始蒙特卡洛树搜索之前对部分显然无益的操作进行移除，以免智能体浪费时间为这些无益的操作进行模拟。值得注意的是，
在对操作进行移除的过程中一定要确保该操作不可能为最优解，否则不准确的移除反而将导致智能体决策强度的下降。
\item \textbf{启发式操作枚举}：在上一节的末尾，我们讨论了朴素蒙特卡洛树搜索应用于炉石传说的瓶颈。暴力枚举并不适合用于可操作实体数较多的炉石传说，
为了解决这个性能瓶颈必须为枚举算法加入一定的启发知识，使其能像人类玩家一样只去枚举有价值的操作序列。
\end{itemize}

除此之外，也有其他的一些优化方式可被用于蒙特卡洛树搜索智能体以提高其决策强度：

\begin{itemize}
\item \textbf{启发式模拟}：如~\ref{section:MCTSdef}~节所述，适当地在模拟策略中加入启发知识而不是使用完全随机的模拟策略可以使蒙特卡洛树搜索更好地模拟对手的行为。尽管完全随机的模拟策略确保了期望收益的可靠性，
但完全随机的模拟策略往往需要更多的模拟次数来给出同样可靠的期望收益，而且所给出的期望收益是针对所有类型的对手的。如果只考虑智能体所面对的真实对手，其往往只可能属于其中的少数几种类型，
那么完全随机模拟得出的期望收益反而是不准确的。

值得注意的是，尽管启发式模拟没有了随机模拟的这些缺点，但启发式模拟本身的启发知识使得智能体的结果产生了偏差。当这些启发知识不能很好地模拟实际的对手时，
其效果反而要比随机模拟来得更差。本文的实验部分将验证所加入启发知识的数量对智能体决策强度的影响。

\item \textbf{收益递减}：实际上，使用蒙特卡洛树搜索进行决策的智能体有一个很大的特点，就是在拥有比较大的优势时决策强度反而开始下降。这种行为的成因在于，在智能体拥有比较大的优势时，其所能执行的操作大部分都会拥有比较高的期望收益，
此时由于有限的模拟次数永远都是不充分的，加之操作间的期望收益差距过小，某些看起来不大合理的操作反而可能得出最高的期望收益。这种情况在智能体进入劣势时便会消失，在此时智能体往往能做出极其精确的最优操作。尽管对于多数游戏来说，
在优势情况下的随意决策往往影响很小，但在炉石传说中，由于拥有极强效果的卡牌过多，而且回合数越高时，玩家可支配的法力水晶越多，对手打出这样的卡牌并最终翻盘的可能性也更高，
因此炉石传说的智能体即便是在优势很大的情况下也应该继续通过尽可能拉大优势来尽早结束游戏。

在蒙特卡洛树搜索进行反向传播的过程中，通过在每一层结点为传播的模拟收益乘上一个递减系数~$\lambda \in (0,1]$~即可让智能体懂得尽可能早地结束游戏，因为如果某一种操作会使得游戏以更多的回合数才能取胜，尽管胜利的模拟收益仍为~$1$~，
但在逐层乘上递减系数后，操作对应的结点本身收到的收益反而比较小。
\end{itemize}