不平等博弈问题学习记录(三)(对于超实数在博弈下左大右小以及多堆情况的扩充)
发布日期:2021-06-29 06:00:08
浏览次数:2
分类:技术文章
本文共 2312 字,大约阅读时间需要 7 分钟。
前言
今天写的这一篇文章离写第一篇文章的时间可能有几天了,并且在这段时间里也有人向我提出了我错误的地方,现已做出更改
今天,我们又做到了一道题目,也是不平等博弈的,听了讲题,我对不平等博弈有了更深的理解Past感想(现在对前两篇博客已经做修改)
首先,不平等博弈,或者说是一个游戏,一直以来我觉得都可以用超实数来做,但今天我发现,其实超实数其实是一种数,这种游戏的状态不等价于超实数,就比如 ∗ * ∗符号,这个就不是超实数,所以这些东西都是超实数的扩充
还有呢,在超实数的运算 { X ∣ Y } \{X|Y\} { X∣Y}的定义中有“这两个集合中的元素也为超实数,且右集合中不存在一个元素 x x x使得左集合中存在一个元素 y y y满足 x ≤ y x \leq y x≤y”。 但事实上在博弈上很容易出现比如说 { 1 ∣ 0 } \{1|0\} { 1∣0}的情况,这个时候在博弈中仍然是合法的,但是却不能按一般的运算方法来做了,需要用一些特技来算了正文
超实数的定义中一定要左小右大
但在实际博弈中不一定满足 就比如一道题,有两个人,一个人每次能拿a个石子,一个人每次能拿b个石子,求多堆的时候的情况 这道题有一个规律,如果有一堆石子有x个,那么它的状态等价于x%(a+b)个,可能不会证明,但是能通过打几个表来找到规律,其中就有{l|r}(l>r)的运算 下面枚举a=2,b=3的情况- f(0)=0 0颗石子,先手必败
- f(1)=0 1颗石子,同样两个人都不能取,先手必败
- f(2)=1 第一个人能取,f(2)= { f(0) | Φ \Phi Φ }={ 0 | inf }=1
- f(3)= ∗ * ∗ 一个人拿了另一个人就不能拿,所以就是先手必胜,先手必胜有3种情况: ∗ + ↑ *+↑ ∗+↑ 、 ∗ + ↓ *+↓ ∗+↓ 、 ∗ * ∗ ,要怎么判断是三个中的哪个呢,由于 ↑ + ↑ ↑+↑ ↑+↑是一个第一个人必胜态, ↓ + ↓ ↓+↓ ↓+↓是第一个人必败态,所以只要把这个石子复制成2堆,若是第一个人必胜,那么就是 ∗ + ↑ * + ↑ ∗+↑,若是第二个人必胜,那么就是 ∗ + ↓ *+↓ ∗+↓,若是先手必败,那么就是 ∗ * ∗,两堆3个的石子,那么显然是先手必败,所以f(3)= ∗ * ∗,其实很显然,f(3)={f(1)|f(0)}={0|0}= ∗ * ∗
- f(4)= ∗ + ↑ *+↑ ∗+↑ 同f(3)的做法,两个4堆的石子,是第一个人必胜,所以f(4)= ∗ + ↑ * + ↑ ∗+↑,同时发现,解决了f(4)={f(2)|f(1)}={1|0}的问题,{1|0}= ∗ + ↑ * + ↑ ∗+↑
- f(5)=0 这个显然先手必败,所以是0,同时f(5)={f(3)|f(2)}={ ∗ * ∗|1},它竟然等于0
- f(6)=0 这个分析一下就知道,若第一个玩家先取,那么第二个玩家赢,若第二个玩家先取,那么第一个玩家赢,所以f(6)=0,得出f(6)={f(4)|f(3)}={ ∗ + ↑ *+↑ ∗+↑| ∗ * ∗}=0
- f(7)=1
- f(7)={f(5)|f(4)}={0| ∗ + ↑ * + ↑ ∗+↑},分析一下,这是一个先手必胜的状态,但是它等于几呢?一脸迷茫,猜一波结论,f(7)=1?证明呢,很简单,证明f(7)+(-1)=0就好了,也就是第二个人多一步,你可以自己分析一下步数,那就可以发现确实是先手必败 …其实已经有点循环了,后面的证明同理,不再说明 说重点,讲一讲超实数的加法吧
我们发现,对于这些奇奇怪怪的状态,还是带入实际问题用博弈的方式解决比较好,找不到比较好的定义
加法运算(用于超实数状态的多堆情况)
对于超实数 x= { X L X_L XL | X R X_R XR } 和 y = { Y L Y_L YL | Y R Y_R YR } ,它们的加法运算被定义为:
x+y={ X L X_L XL | X R X_R XR }+{ Y L Y_L YL | Y R Y_R YR }={ X L X_L XL+y,x+ Y L Y_L YL| X R X_R XR+y,x+ Y R Y_R YR}, 对于某个集合X和超实数y,X + y = { x + y : x ∈ \in ∈ X } 终止条件为 Φ \Phi Φ + n = Φ \Phi Φ相反数运算
对于超实数 x= { X L X_L XL | X R X_R XR } ,x的相反数为:- x = -{ X L X_L XL | X R X_R XR } = { - X R X_R XR | - X L X_L XL },对于集合X,-X={ -x : x ∈ \in ∈ X }
终止条件为-0=-{ | }={ | }=0其它定义
还有的定义是x-y=x+(-y)
根据上面三个官方的定义,还可以得到两个超实数之和还是超实数,并且加法满足交换律、结合律证明上面的 ↑ ↑ ↑ + ↑ ↑ ↑是先手必胜态
证明: ↑ ↑ ↑ + ↑ ↑ ↑ = { 0 | ∗ * ∗ } + { 0 | ∗ * ∗ } = { 0 + ↑ ↑ ↑ , ↑ ↑ ↑ + 0| ∗ * ∗ + ↑ ↑ ↑ , ↑ ↑ ↑ + ∗ * ∗ } = { ↑ ↑ ↑ | ∗ * ∗ + ↑ ↑ ↑ },所以是先手必胜可能就这些了吧,这些东西差不多可以让超实数在博弈中得到扩展,之后不平等博弈问题会在需要的时候继续更新新的篇目,记录(三)到这里就结束了
转载地址:https://blog.csdn.net/zhouyuheng2003/article/details/78975417 如侵犯您的版权,请留言回复原文章的地址,我们会给您删除此文章,给您带来不便请您谅解!
发表评论
最新留言
路过按个爪印,很不错,赞一个!
[***.219.124.196]2024年04月05日 16时15分47秒
关于作者
喝酒易醉,品茶养心,人生如梦,品茶悟道,何以解忧?唯有杜康!
-- 愿君每日到此一游!
推荐文章
为什么LED灯会越用越暗?
2019-04-29
为什么说卷积神经网络,是深度学习算法应用最成功的领域之一?
2019-04-29
在电网工作,有多高大上?
2019-04-29
「2020年大学生电子设计竞赛分享」电源题,省一等奖!
2019-04-29
又一国产开源微内核操作系统上线!源代码已开放下载
2019-04-29
10年老兵!从大学毕业生到嵌入式系统工程师的修炼之道……
2019-04-29
如何才能学好单片机?
2019-04-29
一根网线有这么多“花样”,你知道吗?
2019-04-29
雷军1994年写的诗一样的代码,我把它运行起来了!
2019-04-29
2020年大学生电子设计竞赛,B题,单相在线式不间断电源,详细技术方案!
2019-04-29
大佬终于把鸿蒙OS讲明白了,收藏了!
2019-04-29
C语言指针,这可能是史上最干最全的讲解啦(附代码)!!!
2019-04-29
国内大陆有哪些芯片公司处于世界前10?一起看看!
2019-04-29
单精度、双精度、多精度和混合精度计算的区别是什么?
2019-04-29
中国35位“大国工匠”榜单出炉!西工大、西电合计占半壁江山!清华仅1人!...
2019-04-29
知乎热议:嵌入式开发中C++好用吗?
2019-04-29
2020,Python 已死?
2019-04-29
漫画:程序员相亲?哈哈哈哈哈哈
2019-04-29
30种EMC标准电路分享,再不收藏就晚了!
2019-04-29
这100道Linux常见面试题,看看你会多少?
2019-04-29