UOJ Logo WrongAnswer的博客

博客

百度之星Astar决赛被虐记

2017-10-22 09:33:28 By WrongAnswer

作为无实力退役选手参加Astar玩玩,居然卡进决赛了。综合NOI排名(约47)和Astar线上赛的平均排名(约45),估计我的最终排名在40-50之间,拿奖是没希望了,就当一次旅游吧。

10月22日

报道等一系列行为。

对欢迎仪式的认识环节感到严重不习惯。

10月23日

开始

来到考场,发完密码条,诶怎么用户名是奇怪的名字?试了下,登不进去。然后通知说登录名是前面那个数字。

登进去一看,傻眼了,这个决赛居然是要我们写AI?exm?一直以为决赛和前面几轮一样传统。原来更像Codechef的Challenge啊。(后来想了想,Astar是个启发式搜索的算法,看这个名字也应该想到要考你写AI啊)然而我就打过少得可怜的几场Codechef,根本不会AI的那套理论啊,好尴尬。

仔细看题目,写的是一个类似多人贪食蛇的AI。贪食蛇在二维平面上进行,但可以沿任何方向移动,不仅仅是上下左右,以及蛇可以自交(非常赞啊)。局面会随机生成食物和障碍,吃食物会加长、减速,出界或者碰障碍或者和别人的蛇撞,蛇会死。还有加速道具啥的不过我没用过。当时觉得我滚粗稳了(最后确实是这样)。

第一阶段测试

前三四个小时是练习赛,不计入总分。于是我就开始胡搞,想想不管怎么样也得搞出个能活一段时间的AI。怎样避开障碍呢?脑补了一会儿物理常识,如果把障碍想象成电荷,利用斥力似乎就能避开障碍了?于是yy了个引力场,设当前蛇头 $H$ 的速度为 $v$,对每个障碍 $O$,给 $v$ 加上一个与 $OH$ 同向,大小反比于 $OH^2$ 的速度 $v'_O$,相当于施加一个“力”,最后输出合速度 $v+\sum_Ov'_O$ 方向。

问题是 $v'_O={k\over OH^2}$ 不会弄,就想,如果就地转弯的半径是 $r$,那么在 $OH=2r$ 的时候令 $v'_O=v$ 应该就稳了吧。这么想,推了会儿就写,写完交上去。

结果第一轮测出来发现我蛇一开始就死了!撞到下方的墙了,怎么萎事?不是很懂,就打了个100*100的表输出蛇在每个方向受到的“力”,发现好像都是同一个东西。接着看代码发现我把一个距离和速度搞混了,改。改完以后又发现这个力大得有些夸张,在场地中间这个力还是那么大,很不符合常识啊。

思索了一会儿发现,我的程序假设四周设满了障碍,每个障碍对蛇一个力,合力就巨大无比了,就调了参数。

吃食物还没写,赶紧写。大概是,如果附近最近的食物周围没有对方的蛇或者障碍,就往食物方向走。写完交上去测第二轮。

第二轮又GG了,莫名其妙往角落里面撞了。又用输出100*100的表观察,感觉速度还是有点奇怪。怀疑式子炸了,一看果然式子完全意识流了,啥都对不上,很无语。赶紧重新推,感觉没有什么问题:

$$v=\omega r\Rightarrow r={v\over\omega}$$

$$v={k\over(2r)^2}\Rightarrow k={4v^3\over\omega}$$

然而突然我发现最后一步 $x,y$ 分量算错了,赶紧改:

$${v_x\over d_x}=-{v\over d}\Rightarrow v_x=-{4v^3\over \omega d^3}d_x$$

改完以后感觉和谐了不少。三四两轮,都拿了几百分,似乎还行?然而一看别人的分数,动辄上千,就觉得很绝望。于是冷静地观察了一下自己为啥会低分。

看着屏幕,我的蛇一开始非常正常地吃食物躲别的蛇,不过躲得有点保守(离别的蛇还很远就扭头就跑)。之后,障碍生成得越来越多,然后我发现,我的蛇开始不停地绕环了!原来我的蛇在一个以三个障碍为顶点的三角形内,受到引力场作用,就一直在中间转,等了好久才出来!

想fix这个问题。

第二阶段测试

第一阶段测试结束,第二阶段开始正式计分了。

一共三次测试,每两次隔半小时,每次测两轮,一共六轮。

第一次测试

思考了一会儿,觉得障碍不会动,只要靠近时绕过就行了,改成了距离太大就不算作用力,脸滚键盘弄了几个参数限制。然后局面边缘的障碍也只提取靠近的几个。

然而有的人的蛇靠别人的蛇撞上就得了1000+分,感觉这规则真是玄,正常地吃食物每局难以破1000分,别人撞一次就加1000分。想试试能否卡别人赚1000分,发现根本不会弄。

然后第一次测试的两轮,都中规中矩地拿了400+的大众分。观察我的蛇,发现似乎并没有什么变化,还是非常容易受障碍影响。

打完大概17名左右,觉得翻盘困难。

第二次测试

又yy了一会儿怎么卡别人,无果。

似乎还是要优化吃食物的效率?感觉参数还能继续调?又思索了一小会儿,发现障碍只要距离超过 ${2v\over\omega}$ 就不计算作用力,效果应该最好(差不多是和引力场没关系了)。

第二次测试。第三局300+,没进步,还是经常在没食物有障碍或者别的蛇的地方绕。

第四局,卧槽为什么显示效果这么鬼畜?盯着一个以为是自己的蛇看,发现几秒就撞上别人的蛇死了,卧槽不会是我哪里写挂了吧?不可能啊,我的AI这么保守怎么会犯这个错?结果出分,傻眼了,居然只有10分!也就是啥都没吃到。

然而看视频明明那条蛇吃东西了啊?后来通知这组显示效果挂了,蛇头和蛇身不同色,要以蛇身为准。嗯我看到的是蛇头是我的颜色蛇身不是我的颜色的蛇……可是我的蛇呢?找不到?!看到一共三个人10分,视频里看到没吃东西的蛇,策略都不像是我的啊?又数了下发现一组10个人但一开始只有9条蛇?

日哦!不会遇到灵异事件了吧。

至今不知道第四局怎么爆10的。

这时候只有20+名了,翻盘无望。

第三次测试

又yy了一会儿怎么卡别人,无果。

似乎我的蛇太怕别人的蛇了?嗯,对别人的蛇的参数还没调。可惜缺乏经验,对动的东西不是很会把握,于是继续保守向……

最后突然发现自己犯了个傻逼错误!我误把 $\omega=0.05\pi$ 算成了 $\omega=0.05$,怪不得会那么怕障碍!于是开始大幅度改参数,打出100*100速度表,发现只有靠边界两三行的地方会掉头,玛雅这不是太危险了?又调了一会儿调到一个看起来比较适中的参数。

测了五六轮发现,虽然靠障碍近了些但还是浪费一大把。果然还是自己感觉太差,$v=0.1$,$\omega=0.05\pi$ 时,$r$ 大概是 $0.6$ 到 $0.7$ 之间,离边界距离为 $2$ 不是很稳吗?

说到底还是自己被自己输出的调试语句欺骗了,以为一行就是很紧,却没意识到极限掉头不需要一行的距离。

这时候大概19名?

第三阶段测试

第三阶段测四轮,不能改代码,想想肯定要打铁滚粗了很不爽,就不看战况了。

最后把判定距离调成了预期的理论值,不知道是否有用。

只知道最后看的结果,4100+分,第15名。意料之中地打铁了。

结果

何柱第一名。SkyDec、Stilwell、xllend3、小火车、AKF等IOI/候选队大佬都获奖了。而我呢,就这么空手回家了。

尽管我Astar就这么滚粗了,不过也是第一次体验AI大战,看到了自己和别人的差距,也算是有不少收获了。

10月23日

旅游、颁奖。

颁奖前和OI大佬们一起在墙上拼了“ysy AK IOI2018”,其实我只拼了一点却莫名被采访QAQ

啥奖都没拿到太遗憾了。

技不如人,甘拜下风,加油努力,来年再战!

评论

ccc000111
祝WA爷爷捧杯而归!我们会在51nod上看您的精彩表现!
matthew99
哥哥,比期望排名高三十名,还说自己滚粗。要么你说自己滚粗假,要么你的期望排名假。
pojdd
膜拜大佬
ixctest
@mike

发表评论

可以用@mike来提到mike这个用户,mike会被高亮显示。如果你真的想打“@”这个字符,请用“@@”。