标签: 博弈论

8 篇文章

博弈论基础 – 框架
博弈论,可以定义为两人或多人面对一定的规则约束下,根据所掌握的信息,同时或先后,一次或多次地,从各自允许的行为中选择最优策略,通常要使自身收益最大化。
Luogu – P2148 – [SDOI2009]E&D
有 $2n$ 堆石子,编号分别为 $1, 2, \cdots, 2n$。将第 $2k-1$ 和 $2k$ 堆 $(1\leq k\leq n)$,归为同一组。第 $i$ 堆石子的个数是正整数 $s_i$.
定义分割操作:
  1. 任取一堆石子,不妨为第 $i$ 堆,将其全移走;
  2. 从和第 $i$ 堆同一组的石子中,取出若干正整数个石子,放到第 $i$ 堆的位置上。操作后,两堆石子数都要大于 $0$.
给定状态,问先手是否有必胜策略。
$n\leq 2\times 10^4, 1\leq s_i\leq 2\times 10^9$.
Nim石子游戏
给定数列 $n_1, n_2, \cdots, n_k$,表示有 $k$ 堆物品,第 $i$ 堆物品的数量为 $n_i$。
两人轮流从中取物品,规则:每次可以从一堆中拿走任意正整数个物品。先拿走最后一根的人胜利。
对于给定的数列,判断先手是否必胜,若必胜,输出第一次应该在哪堆取多少物品。
威佐夫博弈
有两堆,若干个物品,两个人轮流从某一堆或从两堆中取同样多的物品,规定每次最少拿走一个,最多不限制,最后拿光的人获胜。