共同演化的基因演算法應用於賽局的共同演化能力

Abstract

這篇論文探討共同演化的基因演算法用於演化賽局策略的能力。更確切的說，這篇論文的討論限定在雙人、零和且對稱的賽局。在這樣的前提下，單純策略和混合策略被分開討論。要共同演化出一個混合策略的納許均衡是具有挑戰性的，因為均衡的策略不能獲得比其他策略更高的得益期望值。這個論點在剪刀、石頭、布的實驗中被驗證，因為所有的混合策略產生的得益期望值一樣，使得共同演化無法收斂到納許均衡。另一方面，在一些賽局中，單純策略是較容易共同演化的，尤其是族群之多樣性被特別保持的時候。實驗上，使用維持生態位的技巧，例如限制競爭式選擇法、確定性擁擠法，對於共同演化都有明顯的助益。更進一步，內文也展示了在共同演化中，族群大小和評估個體時最佳的對手數量之間，權衡折中的關係。在論文的最後，實驗上示範了一個賽局遊戲，相對於棋盤需要指數大小的族群才能演化，也就是仍存在對共同演化來說較困難的賽局。在這樣的賽局中，需要在族群中維持指數的對手來演化出最佳的策略。

This thesis investigates the ability of coevolutionary genetic algorithms to evolve game-playing strategies. Specifically, it focuses on two-player, zero-sum and symmetric games with both pure and mixed strategies. Pure and mixed strategies are discussed separately. Co-evolving the mixed strategy Nash equilibrium is challenging since the Nash strategy does not yield a higher payoff than other strategies. This argument is verified on the game of rock-paper-scissor, where all mixed strategies yield the same expected payoff and fail to converge to the Nash quilibrium. On the other hand, pure strategies are more co-evolvable with some games especially when the diversity is maintained in the population. Empirically, adopting niching techniques such as restricted tournament selection and deterministic crowding helps coevolution. Furthermore, this work empirically shows the trade-off between the population size and the optimal number of opponents used to evaluate an individual. Finally, this thesis demonstrates the existence of game strategies that require an exponentially large population with respect to the size of the game. In such games, exponentially many opponents need to be maintained to evolve an optimal strategy.