博弈论知识点总结

首先一些题目,我们要考虑,能否后手复制对手的操作。比如下面这道题:

不管先手如何操作,我们后手操作之后使得剩下的两个链完全相同。然后复制对手操作即可。

其次一个知识点是威佐夫博弈。

威佐夫博弈简单的说,就是有两堆石子,双方每次可以取一堆石子中的任意个,不能不取,或者取两堆石子中的相同个。先取完者赢。

然后发现,对于(0,0)(1,2)(3,5)(4,7)(6,13)(8,13)…均为先手必输。

发现规律,差值递增,而每个数对的第一个数都是差值*1.618。

最后是Nim游戏,SG函数,游戏的和。

参考我的另一篇博客:Nim 游戏、SG 函数、游戏的和

大部分问题都可以用这个方法解决,注意可以打表SG函数找规律。

原文地址:https://www.cnblogs.com/zarth/p/6711440.html