3D推箱子之《Zoko》

 

本文地址:http://sokoban.ws/blog/?p=4269

我之前的博文中介绍过不少3D的推箱子推广,如Puzzle Moppet、微软的Tinker、Berusky II、Psychoban、DeadEnd 3D、Sokoban 3D等等。

《Zoko》这个游戏也是一款极有特色的3D推箱子,发现这个游戏至少有一两年了,已经记不清是什么时候第一次见到这个游戏的。最近偶尔又从浏览器书签了翻出了这个游戏。这个游戏是个开源的作品,可以浏览器在线玩:https://lulea.github.io/game-off-2012/,一共只有5关,算是个半成品吧。这也反映出3D推箱子的流行程度比经典推箱子可能要更低一个数量级。

3D推箱子要解决人怎么往上走的问题,很多游戏的解决方案都是电梯。本游戏的电梯的特点是有人或箱子压在上面则上升,离开则下降复原。而其他更多的游戏是人踏上电梯,电梯则上升(或下降,取决于电梯当前状态),人离开电梯不动,导致空载的电梯可以处于升起或降下两种状态之一,状态更加不确定一些。

《Zoko》的另外一个特点是人可以推动竖直叠在一起的两个(或多个?)箱子,但水平的两个箱子推不动。

我想,3D推箱子流行度还有待提高的其中一个原因是:规则变多了,但是游戏的难度(计算复杂度)并没有得到提升,还是PSPACE完全。

为什么说3D推箱子还是PSPACE完全的呢?一是包括《Zoko》在内,许多3D推箱子的推广限制在2D情况等同于经典推箱子,所以难度不低于PSPACE。二是《Zoko》游戏中,每个3D格子的可能状态只有有限的几种(如空闲、有人或有箱子),从而关卡总状态是关卡格子数目的指数函数,因而有多项式空间算法可解,即难度也不高于PSPACE。

 

 

 

发表在 推箱子, 游戏, 计算机 | 留下评论

《花之谜题》的计算复杂度

 

作者:杨超

本文地址:http://sokoban.ws/blog/?p=4244

“P是否等于NP?”是Clay数学研究所(Clay Mathematics Institute,缩写CMI)2000年评出的七个奖金100万美元公开数学问题中的一个。Clay数学研究所的官网对每个问题都有正式的描述,其中对“P=NP?”问题的描述中,以扫雷游戏作为NP完全问题的代表,作了一些深入浅出的介绍,见下面官网截图。可见,一些益智小游戏和被数学家认为最重要的数学问题也有密切联系。

由于长期对推箱子游戏的喜爱,从而对推箱子类游戏的计算复杂度也很感兴趣。一般有点意思的推箱子类游戏对应的判定问题的计算复杂度,大多是NP完全或PSPACE完全的。对于具体一个推箱子类游戏,要完全确定其计算复杂度,有时也不见得容易。其中涉及的一个特别的因素是游戏的答案长度:是否总有多项式长度的答案?还是存在例子使得答案长度达到指数级别?

《花之谜题》(Hanano Puzzle)是一个令人爱不释手的游戏,我之前有两篇博文都分别介绍过。这个游戏特别之处在于一方面具有引力,另一方面可以通过开花抵抗引力向上推。

最近,我和合作者在 Elsevier 出版集团旗下的学术期刊 Information Processing Letters 上发表了一篇文章,研究了这个游戏的计算复杂度。有兴趣的朋友可以在此下载该文章的被接收的手稿:

Hanano Puzzle is NP-hard

正式发表的版本可以在 Elsevier 官网下载:

https://authors.elsevier.com/a/1YRTa4ZKAYBpN(此链接于2019年3月13日前都可以免费下载)正式版本的排版更为赏心悦目一些,学术出版集团 Elsevier 还是在学术出版过程中创造了不少价值。

发表在 数学, 游戏, 计算机 | 留下评论

2018年第七届广州马拉松

 

本文地址:http://sokoban.ws/blog/?p=4187

 

一、报名

今年广马换了运营商,从智美换成了中奥路跑。临近广马开赛前,爆出了智美的赛事终点前就给选手递国旗影响选手冲刺事件,广马换运营商还是有先见之明。

虽然换了运营商,但是广马依然列入中国田协、中央电视台和智美集团共同经营的“奔跑中国”系列赛,只是宣传上并没有突出这一赛事品牌。

报名抽签没有中签,于是等开放公益慈善名额时,报了一个慈善半马的名额(2000元,先到先得,据后来公布的情况,300个公益慈善名额全部报满)。

二、领取装备

12月6日送儿子上幼儿园后,早早地就前往琶洲展馆(首次在琶洲领装备,对我而言乘地铁不用换乘线路,是更为方便一些)领装备。

刷身份证确认报名信息后,就进入展馆。今年的一大特点就是领装备就直接戴上一个比赛手环,作为比赛日入场凭证。直到比赛结束后才能剪掉。

公益慈善名额有专门的柜台,先领取了号码布和取衣卡后,在到另一处按号码柜台领取了比赛T恤存衣包等其他物品。今天换了adidas的T恤,存衣包也是透明的(这是一种进步吗?)。而号码布芯片是不知名的极峰体育提供。可见换了运营商,对产业链上的相关产品采购也有重要的影响。

领完就匆匆离开,也没来得及看看广马博览会。返回乘坐地铁时注意到广马的另外一顶“帽子”—-“中国马拉松大满贯”还邀请了范曾先生题字。不过这顶帽子仅对全马项目而言,如同IAAF金标赛事一样(IAAF官网上只公示了全马的男女前20名成绩)。我则希望广马的半马项目能一直保留下去。

三、比赛日

比赛日12月9日当天,闹钟5点40响起床。吃了一根香蕉上厕所后大概6点30多才到了地铁站。7点多才到了林和西C出口。打算从体育中心北门入场被志愿者提醒要先存包,于是小跑绕到西边存包后才从西门进入候跑区。今年对进场控制得比较严,还用紫外灯照射号码布辨认真伪(赛前高调使用手环作为入场凭证,这是声东击西吗?)。

今年不开放体育中心主场的二楼平台,只好排队上流动厕所,等到我时已经7点31分了。

全马的起跑后,我随着人群7点46分左右通过起点拱门。前面15公里基本保持6分配速。15公里后掉到了7分配速。快到16公里时,同事胡老师超过我和我打了声招呼(胡大教授是从F区出发追上来的,完赛成绩是2小时0分41秒)。17.5公里处慢走喝水见到赛事主裁判之一魏老师合影。20公里后的水站又慢走一段喝水。最后约净时2小时15分通过终点。赛道和去年应该是一模一样的。

今年索性不作任何GPS计时,手机放到腰包里。只带了个手表看时间,通过减去起跑时间和看路跑的赛道公里数牌子来估计自己的配速。

领取完赛包、毛巾、奖牌和取回存衣包后,就坐地铁离开。

很快收到短信说我的净时成绩为2小时15分7秒。的确大幅度刷新了最慢记录,比我赛前的乐观预计还要差一些。不过在半年多(七个月)跑量几乎为零,且体重直逼67公斤的情况下,也只能如此了。

可能由于开赛前和比赛前段下小雨,鞋袜湿透,右脚掌磨出一个水泡。赛后腿酸痛程度达到中等,但当天下午还是能坚持抱着孩子走一小会。

赛后通过官方微信查询分段计时(horizon),以及用号码和人脸识别查询照片(跑步维生素)。

四、赛后

赛后第二天12月10日,大腿前后以及臀大肌的酸痛程度有所增加,走路和下楼梯勉强还可以控制不表现出来。12月11日酸痛缓解。12月12日酸痛几乎完全消失。不过这几天早上抱着儿子送去幼儿园时的确感觉比往常累一些。

12月11日下载到完赛电子证书,半马报名名额10000名,完赛才6800人多一点点,完赛率比较低,可能和温度低和下雨有关。相比之下,前年2016年9000名额都有超过7000人完赛。我在男子半程4600多完赛选手中排名中间靠后,退步很大。

赛后两天,还在爱云动、mlszp.com等微信公众号和网站查询照片,但对比之下还是官方合作伙伴跑步维生素有3张特写值得收藏留念,于是答谢了摄影师共30元,10分钟左右就收到了电子原图。另外在跑步维生素上还答谢一张起跑人群中照片一张,10元,也收到原图。

从去年开始,通过人脸识别搜索马拉松的照片就普遍适用,并且如跑步维生素等马拉松照片的查询、搜索、下载、购买支付等服务只通过手机端微信公众号完成,可见技术的演变也非常快。于是又从跑步维生素上买了仅凭人脸识别找到的原图一张,再花10元,合计在跑步维生素上花了50元。

 

 

 

发表在 健身, 广州 | 留下评论

跑步总结:第十个半年

 

本文地址:http://sokoban.ws/blog/?p=4180

 

从2018年5月起,基本没有怎么跑步,体重一路增长到66公斤。一直在忙各种学术活动,以及送孩子上幼儿园。每月跑量如下:

  • 2018年5月:0公里
  • 2018年6月:0公里
  • 2018年7月:4公里(西大球场1k+3k)
  • 2018年8月:3公里(西大球场1k+2k)
  • 2018年9月:0公里
  • 2018年10月:4公里(西大球场1k+3k)

半年合计:11公里。

 

 

发表在 游戏 | 留下评论

2018年广东省组合图论会议

 

本文地址:http://sokoban.ws/blog/?p=4153

2018年7月6日-8日,2018年广东省组合图论会议在珠海市中山大学珠海校区伍舜德国际学术交流中心举行。

7月6日,会议报到。

7月7日,在伍舜德学术中心2楼6号会议室进行第一天的报告。

西弗吉尼亚大学赖虹建教授作了题为“Some progresses of studies of group connectivity and modulo orientations of graphs”的一小时报告

华南师范大学周波教授作了题为“Some aspects of spectral graph theory”的报告。

华南师范大学尤利华教授作了题为“Sharp upper and lower bounds for the spectral radius of a nonnegative weakly irreducible tensor and its application”的报告。

广东轻工职业技术学院的张赞波教授作了题为“Paths and cycles of many lengths in digraphs”的报告。

华南师范大学刘岩教授作了题为“Fractional matching preclusion”的报告。

中山大学娄定俊教授作了题为“Panconnectedness of k-trees with sufficiently large toughness”的报告。

中山大学王玮教授作了题为“Rainbow ramsey theorem and logic”的报告。

华南师范大学张建斌副教授作了题为“The maximum spectral radius of k-uniform hypergraphs with r pendent vertices”的报告。

广东技术师范学院游志福副教授作了题为“Spectral radius and traceability of graphs with large minimum degree”的报告。

华南农业大学刘木伙副教授作了题为“Uniform spectral results on Hamiltonian problem”的报告。

第一天会后下午6时,与会人员合影留念。

7月8日上午,2018年广东省组合图论会议进行第二天的报告。

中山大学杨超作题为“Ricci-flat graphs with girth four”的报告。

中山大学胡平副教授作题为“Rainbow triangles in three-colored graphs”的报告。

广州大学张韬作题为的“Improved lower bounds on the degree-diameter problem”的报告。

暨南大学程冬琴副教授作题为“Strongly and hyper Hamiltonian laceability of balanced hypercubes with faulty edges”的报告。

绍兴文理学院孙跃方副教授作题为“Strong subgraph k-connectivity of digraphs”的报告。

西弗吉尼亚大学吴泱博士作题为“Supereulerian width of dense graphs”的报告。

本次会议参会的师生超过40人,共有16个会议报告,会议顺利结束。

合影照片、报告的演示文件可以在会议网站下载

发表在 数学 | 留下评论

macOS下使用glpk

 

本文地址:http://sokoban.ws/blog/?p=4137

最近需要编程计算一些数学问题,其中核心部分是解线性规划(Linear Programming)问题。我比较喜欢的方案是用C语言加上第三方的库。2013年我查过知道有glpk这个开源的库,于是自然打算还是用它。当时是在Linux系统下使用,安装调试没有太多问题。这次我是在macOS下使用,虽然说macOS也是个BSD Unix系统,但是还是遇到了不少麻烦,最后不太完美地解决了。本文的目的是记录一下。

一、首先在官网下载了最新版的GLPK 4.65.

二、虽然我也有一些在Linux系统下编译游戏的经验(如 XSokobanBerusky2),但还是不太清楚如何编译安装这个库,于是网上搜到这篇博文,基本按文中的方法安装。

三、安装后测试编译C程序,可以编译,但是链接报错。编译时头文件能找到,链接时却找不到链接库。我不知道如何解决,只好把libglpk.a文件找出来放到和源文件(如t.c)一起,用 gcc t.c libglpk.a 命令编译。

发表在 计算机 | 留下评论

跑步总结:第九个半年

 

本文地址:http://sokoban.ws/blog/?p=4131

体重基本在61到62公斤浮动。最近6个月跑量如下:

  • 2017年11月:28公里(含福州西湖9公里)
  • 2017年12月:42公里(广马+黄埔马)
  • 2018年1月:0公里
  • 2018年2月:3公里(大年初一晨跑)
  • 2018年3月:22公里(含广州10k)
  • 2018年4月:10公里(中大10k)

半年总跑量:105公里。

 

发表在 健身 | 留下评论

2018年第20届中山大学校园马拉松10公里

 

本文地址:http://sokoban.ws/blog/?p=4107

上一届中山大学校园马拉松在2016年举办,我也跑了。

一、报名

4月11日中午,微信收到同事蔡老师发来的校园马拉松的通知及报名链接。没有太多犹豫,便在微信上报名了10公里组。同时也通知另一同事胡老师报名。

12日傍晚,收到报名成功短信。

二、领装备

和之前参加过的两次校园马拉松相比,这次似乎换了一个承办商。

4月19日上午9时,我按公布的时间来到体育部第二会议室,结果T恤等装备尚未运送到位。举办方居然不守时,这是我参加过多次跑步赛事第一次遇到。我等了半个多小时便离开。

当天下午2时,再次去领装备。号码布芯片是Active 的IPICO品牌,Active的在线报名系统使用过,但它们的芯片这是第一次看到。而比赛T恤居然是孟加拉国产的纯棉质地,太不专业了。居然没有参赛指南。

4月20日,收到保险短信,是富德生命人寿。

三、比赛日

4月21日,下午2时来到小礼堂和胡老师汇合。经过一些健美操、武术表演后,2点40多10公里组才起跑。前面胡老师带的太快,5公里后不得不减慢速度。中间喝水两次,最后自己录得53分24秒完赛,是三次参加校园马拉松10公里跑得最快的一次。上次广州10k赛后,快一个月完全没有训练,这次跑得比上月广州10k还更快一点点,而且也没有明显疲劳,还是非常满意。

换了承办商后,果然没有了剩余圈数的大屏幕,没有之前的组织水平高。

然后领取了一瓶功能饮料、完赛奖牌和没写成绩但是印上号码和现场盖章的完赛证书后离开。

四、赛后

没有收到赛后短信成绩通知。

 

 

发表在 健身 | 留下评论

2018年欢乐跑中国10公里锦标赛广州站

 

本文地址:http://sokoban.ws/blog/?p=4076

广州10公里从创办第一年起我每年必跑。第二年起由万达体育控股的盈方集团运营。去年,盈方集团还刚刚换了新logo如下。旧logo见我2016年的博文

一、报名

2月9日,在“欢乐跑中国”微信号上看到赛事开始报名的消息,马上转发同事蔡老师,并报名,微信支付100元报名费。

二、领装备

2月23日中午,骑共享单车到海珠区体育中心领取了装备。 T恤还是匹克赞助,号码布芯片也和去年一样是 ChronoTrack的B-TAG。

三、感冒与体重

今年过年期间感冒发烧,之后持续咳嗽,差不多大半个月才完全康复。体重可能也由很长时间62+公斤的水平降到61+公斤左右。

领装备前一天,又有感冒的症状。不过这次是小感冒,只流清鼻涕。领装备当天症状最严重。24日好转,但还是流鼻涕不断。25日起来后,只能说基本好了,偶尔可能还流点鼻涕。

(27日中午起才完全不流鼻涕)

四、保险

参加跑步比赛好几年了,常常赛前都会受到短信,告知赛事组委会统一购买的一天的运动意外保险保单号,还给出网址可查询保单详情等等。

这一次,赛前几天,3月22日,受到电子邮件发来的pdf格式的电子保单,是众安保险提供的赛事当天的“众安综合意外伤害保险”电子保单。记忆中这是第一次收到正式的电子保单,是不是跑步赛事的保险也越来越规范了?

五、比赛日

25日早上,按照约定和蔡老师于7点15分在地铁集合。到达广州塔二楼平台脱去外衣存包后,差不多是7点48分。进入A区候跑。

8点前,裁判引导参赛选手从二楼平台缓缓下到真正的起跑线前。8点比赛开跑,大约2分钟通过起点。这次全程基本和蔡老师并排前行。最后500米,蔡老师提速到4分左右的配速,我实在跟不上了。最后我们都以55分以内的时间完赛。我手表记录的净时间是54分51秒。

通过终点时,看到魏老师在专注进行裁判工作。她负责女子前35名的计时工作。

回家洗完澡,还不到10点。又收到短信,官方净时间是54分52秒。

大概是为了冲国际田联IAAF铜标赛事,本次10公里比赛居然有邀请东非长跑强国的选手。男子冠军只用了29分07秒,于是英雄戒指的达标线为47分07秒,为历届最快。

整体完赛情况还是非常满意,最后虽然没有冲起来,但是丝毫也不觉得疲倦,可以保持速度。赛后也完全没有酸疼。

六、赛后

比赛当天傍晚,就可以在跑步维生素公众号下载照片。用比赛号码和个人正面照双管齐下搜索,一共有20照片。下载了4张比较好的,懒得在手机上一张一张地保存了。

26日傍晚,官网能下载到完赛证书。但是5公里分段时间有误,可能用了岔路上的一个折返点的数据了。

27日,再到官网上重新下载证书,发现5公里分段时间更正了。组委会有错必纠,还是值得称赞。另外官网也能按号码下载照片,只是比跑步维生素少一些。

 

 

 

 

发表在 健身 | 留下评论

读书笔记(十九)天语物道–李政道评传

 

作者:杨超

本文地址:http://sokoban.ws/blog/?p=4055

《天语物道–李政道评传》是一本2017年底2018年初新出的书,作者赵天池为实验物理学家,他是1981年通过李政道主办的中美联合培养物理类研究生计划(CUSPEA)考试赴美留学的。受李政道影响,后面还有生化类的留学计划等,开启了改革开放后我国新一轮的留学热潮。科普作家“土摩托”袁越也写过文章说自己得益于此。

该书花了很大的篇幅讲了李政道的家族史,从他的曾祖父开始。而李政道的求学经历则比较波折,随着抗日战争的扩大,他从小学起就不断转学,小学中学大学都没有毕业。先后转入上海租界区、浙江衢州、江西赣州,考入迁到贵州湄潭县的浙江大学,最后大二转入西南联大。大学未毕业,经吴大猷推荐,通过“种子计划”留学美国。因此,李政道说过:

在赣州那段孤独无助的岁月,在敌机轰炸之下的逃难路上,环境再危险再艰苦,还是想办法要鼓励自己生存下去。怎么鼓励自己呢?每一个个人都有生存的意义。都是生命,可我跟蚂蚁不一样,我可以了解这个宇宙怎么演变的,世界万物遵循什么规律,而蚂蚁不能。

由于传记的作者是物理学家,对李政道研究工作作了科普性的介绍。1949年,李政道的博士毕业论文是关于白矮星的理论,那时人们尚未知道白矮星是恒星演化的晚年阶段。之后,李政道的研究领域涉及弱相互作用、统计力学、湍流等等。

其中,书中对李政道和杨振宁合作的关于弱相互作用宇称不守恒的获诺贝尔奖的工作更是深入浅出的介绍,来龙去脉讲得十分有趣。我读过一些基本粒子的标准模型的科普书,对此介绍较为简略,比如一般的只提到吴健雄的实验证实了宇称不守恒。读了此书,才知道几乎同时还有另外三组科学家也通过不同的实验独立验证。即一共有四组独立实验的验证,其中有三组是李政道直接推动的。

此外,作为最新的一本李政道传,难免花不少笔墨来介绍杨振宁以及李杨两人失和的原因,和否定杨建邺著《杨振宁传》的一些说法。至于那种说法更接近真实情况,只能由读者去判断了。

但无论如何,李政道和杨振宁都是伟大的中国物理学家,都非常爱国。通过两人的学术风格,我感觉到,李政道偏向于实用主义,他为发展中国的物理事业的工作面更广,如CUSPEA和很早就回国作实实在在的讲学等。杨振宁更加理想主义,就如他的工作更偏爱数学的美,加入美国籍成了他的一个心结,自己多次写文章谈到这个问题,谈到他父亲心底一定不会原谅他放弃中国国籍。2015年,杨振宁放弃美国国籍,重新加入中国籍,算是解了这个心结吧。

如同作者在自序中指出的,本书唯一的遗憾就是对李政道1962年后的研究工作和事迹介绍较少,几乎是一笔带过。

发表在 读书 | 留下评论