数学、博弈问题
Posted by Mars . Modified at
记录一些数学定义、公理和定理。
数论
余数
同余定理
两个整数a,b,如果他们同时对一个自然数m求余所得的余数相同,则称a,b对于模m同余。记作a≡b(mod m)
。读为:a同余于b模m。在这里“≡”是同余符号。
- 模
m
的两个同余数a
和b
的差diff = a - b
,被它们的模数m
整除:(a-b) % m === 0
; - 模
m
的两个同余数a
和b
的和、差、积
,与它们模m
后余数的和、差、积
同余:(a + b) % m === (a % m + b % m) % m
和、差、积、商取模
(a + b) % m === (a % m + b % m) % m
;(a - b) % m === (a % m - b % m + m) % m
;(a * b) % m === ((a % m) * (b % m)) % m
;(a / b) % m === (a * B) % m
= (a * b^(m-2)) % m; (其中B
是b
关于m
的乘法逆元。)
最大公约数、最小公倍数
辗转相除找最大公约数
function gcd(num1, num2) {
return num2 === 0 ? num1 : gcd(num2, num1 % num2);
}
找两数最小公倍数
let LCM = num1 * num2 / gcd(num1,num2);
图相关
两点之间距离
博弈问题
博弈问题分类
- 无偏博弈(Impartial Game):
- 游戏有两个人参与,二者轮流做出决策,双方均知道游戏的完整信息,且可做出的决策集合相同;
- 任意一个游戏者在某一确定状态可以作出的决策集合只与当前的状态有关,而与游戏者无关;
- 游戏中的同一个状态不可能多次抵达,游戏以玩家无法行动为结束,且游戏一定会在有限步后以非平局结束;
- 总而言之,参与游戏的双方除了有先手后手外,其他毫无区别。
- 非无偏博弈:与无偏博弈的区别主要是可作出的决策集合与游戏者有关(例如棋牌游戏,双方互相不能使用对方的棋子);
- 反常博弈:与无偏博弈的区别主要是,反常游戏的胜者是最后第一个无法行动的玩家,而败者是最后行动的一方;
状态与必胜、必败状态
状态就是游戏的局面信息,游戏的进行由状态之间转移表示。
假设当前状态为S
,当前的先手游戏者做出了决策P
,那么游戏状态可能变为T
,那么我们称T
为S
的后继状态,代表状态T
可以通过状态S
经由某种决策而得到。
- 必胜状态:某一个游戏状态S,对于当前先手的游戏者必胜;
- 必败状态:某一个游戏状态S,对于当前先手的游戏者必败;
有关必胜、必败状态的几个定理:
- 如果一个状态
S
没有任何后继状态,它是必败状态; - 如果一个状态
S
的后续状态集合中,存在一个必败状态,那么S
为必胜状态; - 如果一个状态
S
的后续状态集合中,全部都是必胜状态,那么S
为必败状态;
定理2和3是显然的,定理1的解释是:S
没有后续状态,则当前游戏者无法做决策(无法行动)。根据游戏定义,这时它是败者。
著名IG游戏
Nim 游戏
有
n
堆石子[a1, a2, ... an]
,两名玩家每次从这些石子堆中移除若干石子,规则如下:
- 每次只能选择一堆,只能在这一堆中进行移除;
- 每次移除的石子数量在
[1, ai]
之间;- 最先无法移除石子的人,为败者。
Nim 游戏的结论
结论:Nim游戏在所有石子堆a1,a2 ... an
的异或和为0的时候,先手必败,否则先手必胜。
Nim游戏结论解释
定义Nim和为: a1 ^ a2 ^ a3 .... ^ an
,Nim和为0的状态称为Nim平衡。
- 根据上节定义1,没有后继状态的状态为必败状态。这里当所有石子堆的数目全为0,为必败状态,此时Nim和为0;
- 当前状态的Nim和如果不为0:则当前先手总可以找到一种移除方法,使得Nim和归0;
- 当前状态的Nim和如果为0:则当前先手的任何移除方法,都使得Nim和不再为0;
对于2
和3
的解释:
- Nim平衡的本质是:
a1、a2 ... an
这n个数的二进制表示中,二进制的每一位上,都有偶数个1
; - 如果当前Nim不平衡:此时可知当前Nim和
N
一定有奇数个1
的数位。那么我们从最高位开始,选择第一个具有奇数个1
的位置t
,假设它对应的数为ai
,那么我们可以将这个数位-1
,然后利用移除的这个最高位数,将t
之后的非Nim平衡位,“配平”为偶数(类似借位的思想)。具体地,我们可以将ai
替换为ai ^ N
; - 如果当前Nim平衡:此时玩家在
a1、a2 ... an
中选择一个数ai
进行减小操作,一定会将ai
的某个数位t
由0变1(或由1变0),之后的Nim和一定不为0;
因此,Nim和总是在0与非0之间变换:
- 当初始Nim和为0时,因为先手一定会将其变为非0,而后手之后又可以将其归0,所以先手将一直面临Nim和为0的状态,直到到达石子数全为0的必败状态,先手败;
- 当初始Nim和不为0时,先手可以选择将其变为Nim平衡,后手一定会打破Nim平衡,因此后手一直面临Nim和为0的状态,直到到达石子数全为0的必败状态,先手胜;
Nim游戏的启示:SG定理
SG定理由Sprague-Grundy
提出,它定义了一个SG函数:
- 任意一个状态
x
:SG(x) = mex(S)
,其中S是集合S = { SG(y) }
,y
是x
的后继状态; mex(S)
表示不在集合S
内的最小非负整数: 例如mex({0,1,3,4}) === 2
,因为2
是不在集合{0,1,3,4}
中出现的最小非负整数;- 对于必败状态
s
,因为后续状态集合为空,因此SG(s) === 0
; - SG定理:游戏整体的SG函数值,等于各子游戏SG函数值的Nim和(异或和)。
- 游戏的SG函数值为
0
,则先手必败,否则先手必胜。