〔博弈论|第二期〕教你成为常胜将军，来不来看看？

Description

这次配音拖了很久，然后应观众要求做了以下改动：
删去了正确或错误的提示视频
增加了每个问题后的回答
增加了无互动版与有互动版（无互动版可能有些问题看不到，建议看有互动版）
增加了BGM
配音与视频更为贴合
BGM：彭寒 - Back to Moon（识别图像）

Comments

密期望 2021-09-12

公平组合博弈可以简化为如下问题：在一个有向无环图（DAG）上，起点处有一枚棋子，双方轮流选择一个当前位置的后继进行移动，不能移动者判负。 up介绍了sg函数的一个简单表达，即只考虑两种取值：0（必败态），1（必胜态）。如果我们将必胜态扩展到正整数，那么我们可以得到一个更强有力的工具。假如，现在DAG上不止一枚棋子，而是有n枚，其余规则一样。显然，我们可以把n枚棋子所在位置组成的序列看成新的棋子，然后得到一个状态数大得多的DAG，然后解决问题。但这样计算量太大，常常无法令人满意。更优秀的做法是，定义DAG中一个节点（局面）的sg函数为，他所有后继局面的sg函数的值所组成的集合的mes（集合的mes定义为最小的没有出现的自然数）。我们发现，必败态的sg函数仍然为0，而必胜态的sg函数得到了拓展，可以是其他正整数。这时候就有一个结论：多个棋子所组整的整体的sg函数为所有棋子所在状态的sg函数的异或和（异或是一种二进制运算）。因此，会出现一个现象，可能所有的棋子都在必胜态，但综合起来，先手必负（比如两枚棋子在同一位置，后手永远可以模仿先手的操作）。综上所述，我们在没有大幅增加计算量的同时，解决了一个更复杂的问题。楼下提到的nim游戏也可以用这个解决。 nim游戏：n堆石子，每次操作可以选一堆取走任意数量棋子，无法取走石子判负。 nim游戏中，每堆石子的sg函数就等于石子数量。所以对每堆石子的数量求个异或和，就能判断胜负。

♥ 57 ↩ 8

大友陣 2021-09-17

海盗船上有一百枚金币，五个海盗分赃，游戏规则是从一号开始提出金币分配方案，其余人投票，如果有超过一半人反对则将方案提出者扔下大海，然后下一位提出方案，直至方案通过假设海盗们都为了自身利益最大化行动，不得违背游戏规则。请问一号最多可以让自己分得多少金币。

♥ 19 ↩ 11

无懈可击99 2021-09-12

制作很精良，三连了[打call]

♥ 9 ↩ 2

研究員塔罗兰 2021-09-12

x是…的后续，…是必败态，歪是x…（阿巴阿巴）

♥ 5

trace1729 2021-09-12

mknb！

♥ 2

通辽汗国驻成都大使 2021-11-17

由于提出方案的人不能投票，反对票需要超过半数。先考虑五号，五号无论什么情况下都会透反对，弄死其他人他就拿到全部。四号知道五号一定投反对，所以他为了活命，无论三提出什么方案就必须同意。三号知道四号五号的策略，同时他为了自己利益最大他需要搞死一号二号，所以一二号不管提出什么他一定反对。二号通过分析得出结论三号必定反对，四号必定同意，五号必定反对。一号一但死了他也活不成，所以他不能让一死，他也必须投同意票，自己才能活。所以一号可以提出自己全部拿走100枚金币，他自己不投票，最终票型为2比2 反对票未超过半数。

♥ 1 ↩ 1