Nim 游戏与博弈论

今天主要学习关于Nim游戏的博弈论

该类游戏通常满足以下要求:

  1. 有两个参与者A B
  2. 该游戏对每个参与者是公平的(即无黑棋白棋等区分)
  3. A B分别按最优决策进行合法操作,无法操作者负

以2个人在n堆石子中取任意颗石子为例阿道夫,当且仅当 $xor^{n}_{i=1}SG_i=0$ 时先手为败

(老师说背结论就好了 哈哈)

而$SG(S)=mex{S’}$,即每种子状态的SG集中不包含的最小正非负整数

题目没啥好讲的,做完发现还是只会找规律,所以等于一题都不会…
今晚约等于荒废掉的一个晚上




Enjoy Reading This Article?

Here are some more articles you might like to read next:

  • 动手实现一个 RISC-V GPGPU(二):指令集设计
  • 数据结构 (CS1951@SJTU) 课程笔记汇总
  • 数据结构复健(四):树链剖分
  • 实现一个 std::map
  • 实现一个 std::priority_queue