H的部落阁

近似纳什均衡 纳什均衡要求所有人都没有偏离当前策略的动机。 纳什证明了n个人的有限博弈一定存在纳什均衡, 但是即使对于两个人的情形, 如果每个人的策略空间很大, 均衡的求解还是会很困难。 如果放松求解的条件, 寻求一个策略使得每个人偏离增加的收益不超过一个常数, 则这个策略叫做一个近似纳什均衡(Approximate Nash Equilibria)。 考虑两个人的双矩阵博弈(bimatrix game), 寻找 PPAD-complete 的均衡求解还是很困难, 但是TS方法给出了在多项式时间内求得一个 0.3393 近似的均衡的算法。 收益的矩阵写法与近似均衡 对于两个人的策略, 可以表示成矩阵的形式. 以一个人的纯策略作为列索引, 另一个人的纯策略作为行索引, 两个矩阵中元素 (i,j)(i,j)(i,j) 分别对应的是行动 (ai,bj)(a_i,b_j)(ai​,bj​) 对两个人产生的收益。 给定两人的混合策略, 则矩阵中每一项被实现的概率就可以确定, 分别乘上对应的收益后加和就得到了这种策略下的期望收益。 记 R,CR, CR,C 分别是行玩家和列玩家的收益矩阵, (x1 ...

在这里整理几个不动点定理, 并说一说他们的应用. 一般来说, 对于一个集合 XXX 和一个映射 T:X↦XT:X \mapsto XT:X↦X, 如果存在 x∈Xx \in Xx∈X 满足 T(x)=xT(x) = xT(x)=x, 那么 xxx 就是一个不动点, 即它在映射下保持不变. *在很多领域中, 不动点是稳定（stability）和均衡（equilibrium）的代表——博弈（game）中的纳什均衡（Nash equilibrium）、阿罗-德布鲁经济体（Arrow-Debreu economy）中的一般均衡（general equilibrium）和马尔可夫链（Markov chain）的平稳分布（stationary distribution）都是不动点. * 巴拿赫不动点定理 巴拿赫不动点定理（Banach fixed point theorem）通常被叫作压缩映像原理原理（contraction mapping principle）, 它用构造性的方法证明了度量空间（metric space）中某些特殊映射（压缩映射）不动点的存在性和唯一性. 巴拿赫不动点定理 令 ( ...

博弈论基本知识 一般来说提到博弈论就想到的是纳什均衡, 那就直接来看看纳什做了什么工作. 纳什的博弈理论是基于缺乏联盟的非合作博弈形式, 即假设每个参与者的行动是独立的, 只关心自己利益的最大化. 考虑到每个人可以按照事先决定的概率分布在自己的策略空间混合, 对每个人来说, 对自己选取的每一种确定的行动, 就对应一个期望收益. 在非合作的前提下, 给定别人的策略, 每个人都希望自己的策略能够最大化自己的期望收益. 当每个人都不能通过仅仅改变自己的策略来提升自己的效益的时候, 就达到了一个纳什均衡点. 也就是说, 在一个均衡中, 某个人 iii 的策略 α\alphaα 如果被以正的概率选择, 则给定其他人的策略时, 这个策略一定是可以最大化自己期望效用的策略中的某一个, 这也是纳什均衡的另一个充要条件. 以下是数学化的描述： 有限博弈：博弈中有 nnn 个人, 每个人有有限个纯策略, 以及收益函数 pi:(π1,π2,⋯πn)→Rp_i: (\pi_1,\pi_2,\cdots \pi_n) \rightarrow \mathbb{R}pi​:(π1​,π2​,⋯πn​)→R 把所有 ...

WSL2开荒与机器学习环境（纯新手入门向） 每次换主机或者系统重装都要进行一大堆开荒的操作, 虽然操作起来流程都是一样的, 但总有地方需要查. 现在的网络环境下懂的不懂的人都在乱说, 每次寻找信息也要花费不少时间, 于是决定自己写一个文档供以后的自己参考. WSL和WSL2 新装的系统默认的WSL应该是WSL1, 如果想要更好更完整的体验可以升级到WSL2. 大致来说需要的操作是在系统的 启动或关闭windows功能 里面打开 Hyper-V 和 适用于Linux的Windows子系统. 大致来说WSL1和2的区别就是WSL2更像是一个虚拟机, 它的底层和 Docker 有着千丝万缕的联系；而WSL1更像是Linux和Win的无缝衔接, 这也导致了WSL1的功能和性能都在很大程度上被限制了. 这里再说一句网络上二者的区别. WSL1直接使用宿主机的网络, 如果你在WSL1里面监听一个端口, 直接使用 <宿主ip>:<监听port> 就可以建立连接. 这样的好处就是直接可以暴露WSL里面的端口, 简单方便. 但是如果宿主和WSL的端口号冲突了, 可想而知就会有一 ...

Introduction 这个实验的内容是自己写一个tiny shell，实现一些shell应该有的功能。其实上这个lab是我回课轮到的，但是到最后我还是没能完全弄懂，所以非常惭愧。总的来说想要通过所有的trace，只要把不确定的信号全部都暂时屏蔽了然后记得时不时回来处理被屏蔽的信号就可以了，但是我觉得这不是这个lab的“真谛”——做这个lab更应该明白为什么要屏蔽某个信号，然后屏蔽尽可能少的signal。 Shell Lab 说回来虽然我当时花了很长的时间来做这个lab，主要原因还是上课没有认真跟上节奏，管爷上课自娱自乐还不下课是真的难顶。要做好这个lab我的建议是先仔细看tsh.c的框架，然后研读CSAPP上关于屏蔽信号的内容，然后在ref的shell上操作一番，最后才是动手写，着急吃不了热豆腐啊。。。 这个lab没什么心情认真写了，我直接贴上代码吧以后心情好了补上文字。但是代码中的中文注释我已经尽可能详细了。 12345678910111213141516171819202122232425262728293031323334353637383940414243444546474 ...

Arch Lab的目的是加深对于Y86指令执行的理解。实验分城三个部分，Part A是完成三个程序的汇编代码，Part B要向已有的指令集中加入两条指令，Part C是优化代码，使其运行的尽可能快。 Part A 在sim/misc文件夹中，我们要编写三个Y86指令汇编代码，实现examples.c中相应函数的功能。 sum.ys 先来看一下c的程序： 12345678910/* sum_list - Sum the elements of a linked list */long sum_list(list_ptr ls){ long val = 0; while (ls) { val += ls->val; ls = ls->next; } return val;} 这是一个迭代求和的过程。实验材料并没有给出模板，但是可以参考教材图4-7给出的完整的程序文件的例子。这样的程序包括了数据和相应的所有指令。略微的区别在于书上是对一个数组进行求和，而lab要求对链表进行求和，所以要对取下一个数的方式做出修改， ...

Bomblab是第二个lab，简单来说任务就是通过阅读反汇编得到的代码和GDB调试，输入正确的字符串以过关，错误则可能会引爆炸弹。 看着好像很恐怖，引爆一次炸弹就要扣除最终一定的分数，但其实丝毫不用担心。一方面虽然lab本来是做过处理只能在服务器上运行的，但是只要找到合适的入口你就可以跳过服务器检测从而在本地拆弹，另一方面只要会设置断点，每次都在explode_bomb（引爆炸弹函数）处设断点，该收手时就收手，根本不用担心炸弹爆炸。但是我不推荐第一种方式，因为要是你有这种绕过服务器检测函数的水平，这个lab对你来说应该是没有难度的，正常做就好了。 有一点十分遗憾的是，在我写这个解析的时候服务器已经关掉了，而且我也并不会修改HEX使得炸弹在本地运行。于是我只能分析拆弹的流程，不能给出具体运行的截图，在此说一声抱歉。 很多网上的解析上来就说啊好你看这六个阶段每个阶段怎么怎么做，隐藏炸弹怎么怎么进。但是我在做lab时每次最先遇到的问题都不是题目本身，而是怎么理解接近十页的writeup，怎么开始。Bomblab最基本的工具就是GDB和SSH，但是大部分的解析几乎都略过了这一部分，所以我当时甚 ...

Introduction Attack Lab是ICS课程的第三个lab，顾名思义就是让我们想办法攻击一些程序，让其偏离原先的运行方式。这个lab的主要目的是理解缓冲区以及缓冲区溢出的隐患，以及相应的攻防。实验要求进行六次攻击，分别对应不同程度的防范，这可以说是所有lab里面最有趣的一个了。而且当时的树洞有很多求助贴却只得到了冷嘲热讽或者猜谜一般的回复，当且仅当你知道怎么写这个lab的时候你才能理解他们的“指点”。 或许你会觉得Alice已经给出了提醒，但是事实是：偏移的offset是0x128，所以如果你没有做出来根本就不能获得正确的提示，反而会被引入歧途，毕竟谁会想到128竟然是个十六进制的数呢。 Code Injection Attacks 前三个phase都是让程序运行我们写入的代码，所以我们要设置好运行的程序或者地址，然后让程序在ret时进入我们安排好的位置。 phase1 这是一个热身，只要把运行的位置跳转到touch1就可以了。 首先要获得可执行程序的反汇编代码。 打开ctarget.asm文件，查看有关test的程序部分。在test调用getbuf之后会有ret指令，考 ...

ICS Lab1: Data Lab Introduction 这是ICS课程的第一个lab，内容是熟悉位运算并通过位操作实现一些功能。 对于lab我的看法是不要浪费太多的时间，能讨论就一起讨论着做，能够参考前辈的工作就不用太多独立思考。只要不是CtrlCV，依样画葫芦的收获往往比自己研究来得快。lab的有些部分尤其是CMU移植过来之后加上的在最后一两个PKU魔改的part不是一般人轻易能够搞定的（dalaodalaodalao请直接忽略我的话因为dalaodalaodalao也不需要参考这种辣鸡文章吧），有时间不如多看CSAPP或者去做往年题。因为我是大二才转到信科学院的（匿名严肃谴责ljl老师招生不守信用事前一套背后一套），所以周围也没有什么要好的同学可以讨论作业，因此完成lab花费了我非常多的时间（尤其是后半学期），但是只是在绞尽脑汁研究奇技淫巧，对于核心内容的掌握没有太大帮助。这也是我决定重新写这一套lab并且分享过程的原因。 Data Lab是第一个lab，内容也是非常简单尤其是网上有大量的资料可以参考。许多位运算的技巧感觉并不是那么容易想到，所以我觉得只要能够按照解答看明白 ...

x2+y2=z2x^2 + y^2 = z^2 x2+y2=z2 测试公式 x2+y2=z2x^2 + y^2 = z^2x2+y2=z2 ac~\widetilde{ac} ac ∣abcd∣ \begin{vmatrix} a & b \\ c & d \end{vmatrix} ​ac​bd​​ ∑i=1n(1)\displaystyle\sum_{i=1}^n\tag{1} i=1∑n​(1) ∑i=1n2\textstyle\sum_{i=1}^n \tag* {2} ∑i=1n​2 aaa bbb 1.段落标题 1.1段落标题 1.2段落标题 1.2.1段落标题 1.2.2段落标题 2.段落标题 空格：\quad 测试图片引用 这是一行字 从这里可以下载文件 A+B  def‾‾△  C↑+ D↓A+B~~\underset{\triangle}{\overset{\LARGE\underline{\underline{\normalsize def}}}{}}~~C\uparrow+~D\downarrow ...