浅谈如何解决不平等博弈问题.PPT

上传人:国*** 文档编号:1269707 上传时间:2019-01-25 格式:PPT 页数:43 大小:379.50KB
下载 相关 举报
浅谈如何解决不平等博弈问题.PPT_第1页
第1页 / 共43页
浅谈如何解决不平等博弈问题.PPT_第2页
第2页 / 共43页
浅谈如何解决不平等博弈问题.PPT_第3页
第3页 / 共43页
浅谈如何解决不平等博弈问题.PPT_第4页
第4页 / 共43页
浅谈如何解决不平等博弈问题.PPT_第5页
第5页 / 共43页
点击查看更多>>
资源描述

1、 浅谈如何解决不平等博弈问题广东省中山市第一中学 方展鹏引言 给出n棵竹子,高度分别为a1, a2 an,玩家L和R在这些竹子上面进行游戏,规则如下:两人轮流操作,玩家L先手;对于每次操作,先选定一棵高度不为0的竹子,然后砍掉该竹子的某一段,并且将与竹子底部不相连的部分也去掉; 最先无法进行操作的人输。假设玩家L和R都采取最优策略,问对于给出的局面谁会获胜。Hack This引言 对于上述问题,根据The Sprague-Grundy Theorem,我们可以轻松地设计出一个时间复杂度为O(n)的算法。 详 2007 的 )().()(),.,( 2121 nn xgxgxgxxxg 引言 T

2、he Sprague-Grundy Theorem 在 题 的 对于 局面,玩家L和玩家R的可选决策都相 如 两 的可选决策不相 会 ? 我们不 在游戏规则 一 :竹子的每一段都 上 L R,玩家L 砍 上L的段,玩家R 砍 上R的段。 上上述规则后,玩家L和玩家R的可选决策不相 。时我们The Sprague-Grundy Theorem在上述问题上也不 。 引言 currency1“的如何解决这两个玩家的可选决策fifl不相 的博弈问题,也 为不平等博弈问题Partizan Games 第一部分:如何 Surreal Number分一不平等”fl游戏 第部分:如何 规 等方法解决不平等博弈

3、问题 第部分: Surreal Number的定 一个surreal number 两个fifl”。我们 这两个fifl为fifl 与fifl 。 下,我们会将surreal number 作 L | R , 中L fifl,R fifl。 fifl和fifl中的 也为surreal number,且fifl中不 在 x fifl中 在 y x y。 的定 对于surreal number x = XL | XR 和y = YL | YR ,我们 且 不 在 以 不 在 。 出 的定后,我们可以定 1, | -1 -1,以 1 | = 2, | -1 = -2。 为0 0 | 1 1,且 0 | 1 + 0 | 1 = 1, 我们 0 | 1 = 1/2。 我们可以 出 -1 | 0 = -1/2。

展开阅读全文
相关资源
相关搜索

当前位置:首页 > 企业管理资料库 > 人力资源

Copyright © 2018-2021 Wenke99.com All rights reserved

工信部备案号浙ICP备20026746号-2  

公安局备案号:浙公网安备33038302330469号

本站为C2C交文档易平台,即用户上传的文档直接卖给下载用户,本站只是网络服务中间平台,所有原创文档下载所得归上传人所有,若您发现上传作品侵犯了您的权利,请立刻联系网站客服并提供证据,平台将在3个工作日内予以改正。