不平等博弈问题学习记录(一)(超实数篇)
发布日期:2021-06-29 06:00:07
浏览次数:2
分类:技术文章
本文共 2000 字,大约阅读时间需要 6 分钟。
前言
听到博弈问题,第一个想到的想必是用SG函数做的博弈题,就比如Nim游戏
Nim游戏: 有N堆石子,每次选一堆石子,拿走若干石子(不能不取),先不能取的人输
定义个SG函数
对于SG函数,大致就记录两个东西吧定义SG函数g(x)=mex{ g(y) | y是x的后继 }
游戏的和的SG函数值是它的所有子游戏的SG函数值的异或
SG函数能解决很多问题,但是它并不是万能的。他只适用于两个玩家家能进行的操作完全相同的情况(平等博弈)
今天上午做清华集训2017day3T2,一开始以为是SG就可以做,后来因为T1、T3比较好打,所以就没打T2,下午讲题的时候听讲题的时候才知道这是不平等博弈题,所以不能使用SG函数 那么怎么做呢,听高三同学讲完了一遍,我仿佛还是在云里雾里,于是去找了2009的集训队论文方展鹏《浅谈如何解决不平等博弈问题》 感觉这篇论文还是讲的挺好的,但是呢,为了让我更好的记忆,我就开始写这一系列的学习记录了正文
不平等博弈问题(Partizan Games)有一个很好的解决方法是用 超实数(Surreal Number,高届的同学戏称其为super real number),具体的用处会在后面写到
话不多说,对于不平等博弈问题,先定义状态一个及以下后继状态(从有理数上定义)
首先考虑每个状态都只有一个及以下的后继状态的情况
- 如果没有人能操作,那么状态为0
- 如果当前状态只有第一个玩家能进行操作,那么状态为 x x x( x x x为第一个玩家连续能走的步数-[后继状态中第二个玩家是否能走])
- 如果当前状态只有第二个玩家能进行操作,那么状态为 − x -x −x( x x x为第二个玩家连续能走的步数-[后继状态中第一个玩家是否能走])
我们发现,这种定义的状态对单局而言非常无脑
我们发现当状态为 0 0 0时,一定是先手必败态 当状态不等于 0 0 0时,我们不能直接的根据状态值判断谁必胜(证明略)多个后继状态(引入超实数辅助定义)
如果状态的后继不止一个怎么办?
这是大部分题目里的情况,也是文章的重点 我们用超实数来概括所有的情况 定义超实数 { X ∣ Y } \{X|Y\} { X∣Y}(本质上它是超实数,但是好理解一点可以将其当成运算), X X X是第一个玩家能执行操作的后继状态的集合, Y Y Y是第二个玩家能执行操作的后继状态的集合(可以是空集,这个之后会讨论),结果为当前的状态若 X , Y X,Y X,Y都是有限集,那么 { L ∣ R } = { m a x ( L ) ∣ m i n ( R ) } \{L|R\}=\{max(L)|min(R)\} { L∣R}={ max(L)∣min(R)}
对于一个状态 l ∣ r {l|r} l∣r,如果 l < r l<r l<r那么 { l ∣ r } \{l|r\} { l∣r}的结果: 若 l 、 r l、r l、r之间有整数, { l ∣ r } = x \{l|r\}=x { l∣r}=x( l < x < r l < x < r l<x<r且 x x x是所有满足的数中离 0 0 0最近的整数) 若 l 、 r l、r l、r之间无整数, { l ∣ r } = x / y \{l|r\}=x/y { l∣r}=x/y( l < x / y < r l < x/y < r l<x/y<r且 y = 2 k ( k ∈ Z ∗ ) y=2^k(k\in\Z^*) y=2k(k∈Z∗)且y是所有满足条件的数中最小的数,x是在满足前面的条件下的可取值中离 0 0 0最近的整数前面说到在 { L ∣ R } \{L|R\} { L∣R}的运算中, L L L或 R R R会有为空集的情况
空集可以用 Φ \Phi Φ表示,不过一般也用"不写任何东西"来表示,比如说 { ∣ } = 0 \{|\}=0 { ∣}=0 事实上,空集可以当做无穷(如果是左边是空集,那么可以视为是无穷小,如果右边是空集,那么可以视为是无穷大)总结
这里的内容已经是真·简化版了
转载地址:https://blog.csdn.net/zhouyuheng2003/article/details/78939235 如侵犯您的版权,请留言回复原文章的地址,我们会给您删除此文章,给您带来不便请您谅解!
发表评论
最新留言
表示我来过!
[***.240.166.169]2024年04月03日 19时33分55秒
关于作者
喝酒易醉,品茶养心,人生如梦,品茶悟道,何以解忧?唯有杜康!
-- 愿君每日到此一游!
推荐文章
lili’s sqli-labs LESS7,8,9,10 补充知识
2019-04-29
第一天收获
2019-04-29
第一周:Centos 7 基础命令
2019-04-29
centos 7 用户创建、用户/文件权限管理
2019-04-29
文本处理(grep、sed)、正则表达式、vim基础
2019-04-29
find 命令特点及用法
2019-04-29
python实例018--验证爬下来的代理ip是否可用,去掉不可用的代理
2019-04-29
python实例019--爬取网站时的图片
2019-04-29
python实例020--爬取图片网站上的原图作为壁纸
2019-04-29
python实例021--利用python判断一个数是奇数还是偶数
2019-04-29
POJ 2481 Cows 树状数组 单点更新 (每个集合是几个集合的真子集)
2019-04-29
POJ 2482 线段树 离散化 扫描线 矩阵最大权值
2019-04-29
游戏源码
2019-04-29
图片头像
2019-04-29
cocos-creator游戏源码
2019-04-29
传奇游戏源码下载
2019-04-29
egret农场游戏源码
2019-04-29
当爱你的人不再爱你了,还有AI“安慰”你
2019-04-29
100%识别差评!用AI听懂网购者的“言外之意”
2019-04-29