经管之家App
让优质教育人人可得
立即打开
全部版块
我的主页
›
论坛
›
经济学论坛 三区
›
博弈论
耶鲁开放课homework讨论——Zermelo th solution
楼主
zhaosoul
3121
15
收藏
2011-06-29
题目:一些石头,组成一个矩阵,mxn,每个地方放一个石头
2个玩家,玩家选择一个位置,如位于第i行和第j列交汇处的(记为 aij),那么我们就移除aij东北方向所有石头。即移除:
a1j a1j+1 a1j+2...a1n
a2j a2j+1 a2j+2...a2n
...
aij aij+1 aij+2...ain
这些石头
移除最后一颗石头的人输掉这个游戏
问找出这个博弈的解?
显然,最后一个点肯定应该是a(m,1)
我目前做法是,如果m=n,则玩家1只要选择a(m-1,2),之后维持行列元素相等,则可以必胜
若m不=n,不妨设m<n,这种情况下
该怎么做?
扫码加我 拉你入群
请注明:姓名-公司-职位
以便审核进群资格,未注明则拒绝
全部回复
沙发
2441414
2011-6-29 19:46:50
答案还是am-1n-1吧。。。。不知对不对。。。
扫码加我 拉你入群
请注明:姓名-公司-职位
以便审核进群资格,未注明则拒绝
藤椅
zhaosoul
2011-6-29 19:50:46
应该不是
在m与n不相等的情况下(假设 m<n)
我推导出来谁先碰 a(m,1) a(m-1,2) a(m-2,3)。。。a(1,m)这些点谁输,我一开始解答表述有误,不该是a(m-1,n-1)我改了
扫码加我 拉你入群
请注明:姓名-公司-职位
以便审核进群资格,未注明则拒绝
板凳
李庆利
2011-6-29 19:59:10
哎,实在不懂啊
扫码加我 拉你入群
请注明:姓名-公司-职位
以便审核进群资格,未注明则拒绝
报纸
zhaosoul
2011-6-29 20:30:41
貌似好像这个游戏的解是先行者赢,似乎可以归纳出来
扫码加我 拉你入群
请注明:姓名-公司-职位
以便审核进群资格,未注明则拒绝
地板
zhaosoul
2011-7-19 15:15:21
顶一个,没人讨论了么......
扫码加我 拉你入群
请注明:姓名-公司-职位
以便审核进群资格,未注明则拒绝
点击查看更多内容…
7楼
crozame
2011-7-23 18:48:00
逆向归纳,,从最后推。
扫码加我 拉你入群
请注明:姓名-公司-职位
以便审核进群资格,未注明则拒绝
8楼
zhaosoul
2011-8-2 14:57:02
逆向归纳....求解,怎么搞出来的
扫码加我 拉你入群
请注明:姓名-公司-职位
以便审核进群资格,未注明则拒绝
9楼
jinbian
2011-8-2 23:38:41
楼主你好,这是公开课《博弈论》里的问题吗? 看起来是个有趣的问题。现在太晚了,我明天有空时想想,应该可以给出答案。我以前认为博弈论公开课是面向大众水平的课程。楼主以为课程的深度和有趣程度如何?如果有什么别的有趣问题,欢迎拿出来一起分享。
这里有一个我的问题,如果你有想法,也可以告诉我:
https://bbs.pinggu.org/thread-1143796-1-1.html
扫码加我 拉你入群
请注明:姓名-公司-职位
以便审核进群资格,未注明则拒绝
10楼
jinbian
2011-8-3 13:43:12
嗯…… 不像我想的那么简单呢。这个游戏是Zermelo最先提出的吗?楼主可以说说它的背景,也许有助于我们解决。它出现在公开课的哪一集里?
扫码加我 拉你入群
请注明:姓名-公司-职位
以便审核进群资格,未注明则拒绝
11楼
jinbian
2011-8-3 14:28:33
说一点零散的思路吧,可能有不对的地方,欢迎指出来
1. 易证2*3的矩阵先手必胜(他只需第一步移动东北角的那个石头); 递归容易看出2*n(n>3)时先手也必胜(他第一步任然取东北角那个石头)
2. 注意到只要还有其他石头存在,两人都不会去碰左下角的四个石头:(m,1) (m-1,1) (m-1,2) (m,2). 胜负在这之前就会决出。所以,从(m,1) 向右上方引45度射线,如果1号某一步之后形成的格局是关于这条线对称的,那么2号便输了。实际上,如果2号尽量推迟他输的时间,那么要让2号最后拿(m,1),仅当1号能在某步达成对称格局才可以!所以如果说先手能赢的话,一定是先手可以先达到对称格局。
扫码加我 拉你入群
请注明:姓名-公司-职位
以便审核进群资格,未注明则拒绝
12楼
jinbian
2011-8-3 19:05:03
考一考楼主,把这个游戏稍作改变,现在这些石头放在三维空间中构成n*n*n的立方体,选中的石头及它东北方和后方的石头会被移除。问:先手有必胜策略没?
扫码加我 拉你入群
请注明:姓名-公司-职位
以便审核进群资格,未注明则拒绝
13楼
jinbian
2011-8-3 20:52:58
关于原题目的解法,我想还是不好直接递归,因为要考虑的类型比较多,不妨考虑反证法。
证明:假设后手有制胜策略,那么先手第一步选择左上角的那个石头,然后后手会用他的制胜策略选择一个石头;如果是这样,那么先手可以第一步就选择这个石头,这就等于他把自己变成了后手。然后他依照后手的制胜策略就可以获胜,与原假设矛盾。所以后手没有制胜策略,即先手有制胜策略。
扫码加我 拉你入群
请注明:姓名-公司-职位
以便审核进群资格,未注明则拒绝
14楼
jinbian
2011-8-3 20:55:00
但是这并没有告诉我们具体的制胜策略应该怎么走;具体的制胜策略走法还是要靠递归来做,这只能交给电脑来算了。
扫码加我 拉你入群
请注明:姓名-公司-职位
以便审核进群资格,未注明则拒绝
15楼
combing
2012-4-3 13:14:43
逆向归纳!
扫码加我 拉你入群
请注明:姓名-公司-职位
以便审核进群资格,未注明则拒绝
16楼
snowhym
2013-6-30 17:51:12
longlongago。。。。。我的结论:首先,m=n=1 后手赢。其余,先手胜。
原因:归纳法,首先可知若M=N≠1,则先手必胜;另外有,第一,若只有一行或一列,且m*n≠1,则先手必胜;第二,若有L型存在,即剔除到最后只剩余一行和一列时,且行和列不等,则先手必胜。(所谓先手必胜,则说明以上图形中后手选择必定会拿到最后一颗石头)。
另外,可知,任何N*M的点矩阵,都可以拆分成以上三种形状的点,即:— L □ 。
则根据以上已知内容,先手方只要以以上三种形状的点为基础进行取点,则每消除以上一个图形必定会得到下一个图形的先手取点权。而对于后手方,无论如何行动,在每一个拆分的小图形中的最后一点必定为自己拿到,因此,后手必定会拿到以上组合图形的最后一个点。
故,只要N*M不等于1,则先手方必胜。
扫码加我 拉你入群
请注明:姓名-公司-职位
以便审核进群资格,未注明则拒绝
相关推荐
免费!带solution manual的SOA exam-p指定教材!
hull第五版solution manual
求:Solution of <<corporate Finance Fundamentals>> 8e
solution
TIROLE <game theory> solution,梯若尔,泰勒尔 博弈论 答案
基本会计原理_solution_manual
AMOS 中 this solution is not admissble,这种情况应该怎么解决?
AlphaGo is not the solution to AI
PDE Solution Manual
北美精算SOA ERM end-of-module
栏目导航
博弈论
经管文库(原现金交易版)
金融工程(数量金融)与金融衍生品
真实世界经济学(含财经时事)
爱问频道
经管高考
热门文章
你的SSCI发表焦虑,AI真的能懂吗?——一篇 ...
CDA 数据分析师:统计制图实战指南 —— 让 ...
CDA数据分析脱产就业班于2025年08月02日开班 ...
这简单的几句话,完成了对传统和现代经济学 ...
2025年度国产AI芯片产业白皮书
数生万物,转型之本:数据资产运营白皮书-毕 ...
Machine-Learning-Tom-M.-Mitchell中文版.p ...
2025年中国城市可信数据空间行业研究报告
十四五能源发展成就报告
2025 生成式人工智能应用发展报告
推荐文章
AI狂潮席卷学术圈,不会编程也能打造专属智 ...
10月重磅来袭|《打造Coze/Dify专属学术智能 ...
最快1年拿证,学费不足5W!热门美国人工智能 ...
关于如何利用文献的若干建议
关于学术研究和论文发表的一些建议
关于科研中如何学习基础知识的一些建议 (一 ...
一个自编的经济学建模小案例 --写给授课本科 ...
AI智能体赋能教学改革: 全国AI教育教学应用 ...
2025中国AIoT产业全景图谱报告-406页
关于文献求助的一些建议
说点什么
分享
微信
QQ空间
QQ
微博
扫码加好友,拉您进群
各岗位、行业、专业交流群