SSCTF 2015 : 算法第4题(500)

SSCTF有些失败,这道题花了1天时间去想,然而最后跑出结果时已经晚了10分钟。大概如果前一天晚上没有看S5的话就不至于这样了。感觉有点对不起两位巨巨队友。


这是一个编写AI的程序题,我把给的客户端py文件的注释贴一下:

###########################################################################
# # 从前,有一只怪兽Y被四位美丽的公主抓走(=。=),并关在一座魔塔中。       #
# # 终于有一位英雄X挺身而出去救出,为了救出怪兽而与公主们浴血奋战。         #
# # 喂,什么设定 (ノಠ益ಠ)ノ彡┻━┻                                            #
# # 玩法:将下面的username/password更改为你的账号与密码,                   #  
# #       启动GameCli.py,然后请你写一个AI程序与127.0.0.1:22031通信。        #
# #       每次客户端都会发送当前局面,而你AI要做的就是根据局面发送行走指令。# 
# #      (hjkl这四个指令,你懂的)懂你喵!(╯>д<)╯⁽˙³˙⁾                     #
# # 状态说明:                                                              #
# #       ATK:攻击力 DEF:防御力 HP: 生命值                                #
# #       X:行坐标 Y:列坐标 L:当前楼层                                     #
# #       Score:英雄分数,初始18888,每发一次指令-1,当分数为负时游戏结束   #
# #       游戏胜利时分数会计入排行榜,可打开218.245.4.113:5000查看当前排名  #                                                #
# # 战斗说明:                                                              #
# #       遭遇公主即触发战斗,采用回合制,每回合勇士先攻击,然后公主攻击。  #
# #       每次攻击中 被攻击目标HP损失=攻击者ATK-被攻击者DEF。               # 
# # 说明:                                                                   #
# #       # ----- 墙,不可移动                                              #
# #       . ----- 空地,可移动                                              #
# #       / ----- 向上的楼梯,当走到该处会自动被传送到上一层的向下楼梯处    #
# #       \ ----- 向下的楼梯,当走到该处会自动被传送到下一层的向上楼梯处    #
# #       X ----- 你的英雄,初始 ATK:10 DEF:10 HP:1000                      #
# #       Y ----- 待拯救的怪兽                                              #
# #       A ----- 红宝石 ATK+5                                              #
# #       D ----- 蓝宝石 DEF+5                                              #
# #       P ----- 阿三神油 HP+500                                           #  
# #       a ----- 公主a ATK:80 DEF:60 HP:1000                               #
# #       b ----- 公主b ATK:200 DEF:100 HP:100                              #
# #       c ----- 公主c ATK:300 DEF:150 HP:1000                             #
# #       d ----- 公主d ATK:300 DEF:250 HP:3000                             #
# # 胜利条件:解决四位公主,拯救怪兽                                        #
# # 提示:可以先运行GameCli.py,再用TELNET连接,便于熟悉游戏                #
# # !!!注意:请不要对出题人进行人身攻击!!!                            #
# #  (╯‵□′)╯炸弹!•••*~●出题人                                            #
# ###########################################################################  

具体客户端文件:GameCli.py (7.1KB)(不过只有客户端没有服务端也是玩不了的...所以只是看看就好)


比如第一层的地图是这样的:

#####################
#X..#.....#.....#...#
#.#.#.#####.#.#.#.#.#
#...#.......#.#...#.#
#.###########.#####.#
#.#.......#...#.#...#
#.#.#####.#.###.#.###
#.#.#...#...#...#/#.#
#.#.#.#.#######.#.#.#
#.#.#.#.........#...#
#.#.#.#######.#####.#
#...#.....#.#.......#
#########.#.#########
#.......#...#.#.....#
#.###.#####.#.#.#.###
#...#.#...#.#...#...#
#####.#.#.#.#.#####.#
#.....#.#...#.#.....#
#.#####.#######.###.#
#...............#Yd.#
#####################


有的层会有道具,A加攻击力,D加防御力,P加血。
我们的目标Y就在第一层(0层),由Boss d把守。一上来我们是不足以打败她的,所以我们需要上楼(/)捡东西提高实力。
顺便一提,这个地图似乎并不是随机的(至少关键层不是)。d在0层,a在50层,b在100层,c在150层。打败c后,我们仍不能打败d,还需要继续向上爬到200层左右才能吃到足够的HP。

虽说学过AI这门课,但是那是入门级了解向的,感觉并没能帮上什么忙。所以最后写出的AI还是非常简单粗暴的。寻路就用A*来做,网上例子很多,我也是找了一个稍作修改就可以用了。
这里比较复杂的一个问题就是,有时你的目的地会被上下楼的楼梯挡住:

如图,你要吃到A,但是中途有向上的楼梯,一旦踩到楼梯你就去到上层了。此时你还要从上层移动到另外一格(这个方向的选择也需要考虑,不能往墙上移动)再移动回来踩到向下的楼梯,这样才能回来。
(如果遇到这种情况干脆放弃,不去吃道具的话,是肯定打不过BOSS的。)



最后撸出来的效果图:

注:本来我以为一次只能下一个指令,结果跑的很慢,跑到最后干掉了abc三个boss,分数却不足以回到0层了。最后我才发现一次可以下多个指令……此图仅作为演示,依旧是一次下一个指令的模式,所以分数下降很快。下图是改用批量指令模式后的得分。

在排行榜上第一名只下了264次指令。我的AI当时排第8名。但是若要刷分,其实还有很多策略。一开始我想可以在跑过一次之后,把所有的有效步数记录下来,下次一次性发送,极端情况下一次发送全部的指令,只要1步就能通关。但这实际上不现实,大概是道具的位置其实是有条件地随机的。

另外,题目中说建议用telnet来连接本地的客户端发指令,实际上我感觉telnet并不稳定,因此还是把客户端重新用C#艹了一遍。

添加评论

Loading