《魔塔》有没有可能实现算法自动拆塔算出生命max?

share
众所周知,普通的魔塔怪物有限,门有限,总之就是路线有限,但可能会是天文数字。分析一下,假设简单点的魔塔一层有15个怪,5个门,15层,就300个事件,每走2步多一个事件选择,则总共为150!=10^262,好像有点大实际上很多门和怪相连,设计算法时可以当成一个事件,总数应该会小很多

AB__King:不知道利用神经网络做拆塔ai是否可行? 发布于 2022-12-20 08:51:33

衪之闇:这个问题其实是一个旅行商问题吧,这种问题目前还是无解的,不过可以尝试使用禁忌算法,遗传算法,软件的话mathlab,lingo可以考虑 发布于 2022-12-18 01:07:23

花葬列nice:学过MATLAB你或许可以试试 发布于 2022-12-17 23:43:43

fjddy:这个贴可以区分回复者是否看过算法设计与分析 发布于 2022-12-17 23:09:43

heaven红叶石楠:只要是有限步能够完成的问题,就能做出来。ai可以拼魔方,所以魔塔也不是问题,只是计算量太大了。 发布于 2022-12-17 20:35:23

龙神乖:什么叫可行,一个要跑以年为单位时间的程序那能叫有可行性吗?低层元素不多的塔是可行,但在这基础上但凡增加一些新元素、特殊道具、隐藏空间(位置提前不自知),那对算法的复杂性都是爆炸性的增加,NP-hard是常态,就算塔比较特殊简化到指数级复杂度也可能因为数据量较大而要花比人脑得出的近似max多得多的时间。。。 发布于 2022-12-17 19:46:43

1543360836:当然可行,而且难度很低,只是计算复杂。可以先设定一个最简单的塔,遍历出最优解,然后不断增加元素,让塔的内容更丰富。 发布于 2022-12-17 18:01:53

辉钨实况:你可以试试模拟退火模拟退火可以将时间定下来之后进行尽量优的搜索。你可以把待定的打怪开门顺序定下来,然后用模拟退火不断交换其中的序列,在限定时间内不断的在较优解附近找更优解,所以地图的复杂度大也不至于T爆所以在限定时间内可以找到较优解,如果定下的时间越多,越有可能找到更优解。
当然,程序实现会因为魔塔的要素很多会很繁琐,你需要一大堆特判,而且如果用程序的话就失去了拆塔的乐趣了 发布于 2022-12-17 15:16:43

神风木影:你知道什么叫NP-Hard吗 发布于 2022-12-17 14:56:23

无影杰克:直接拆塔求最优解计算量太大~显然是不可取的
如果看做一个优化问题的话
可以先输入一些接近max的路线让机器优化或许可以实现(先进行一些路线约束)
然后计算上直接暴力求解精确解估计也做不到
改用类似于蒙特卡洛算法的求解
在较优解的基础上重新打10^5次,之后取最大值作为一个一次最优解
然后重复实验100次,取这100次中的最优解作为近似的最优解
这样得到最优解的概率通过计算,已经超过99%了
可以作为一个近似的最优解~
要是真正要求精确的最优解的话计算量太大很难跑出来的 发布于 2022-12-17 13:30:43

步步为营147:基本是不可能的,就像你之前说的,那么点东西都天文数字了,而现在的塔大多都是几十几百层的,真算起来估计乘方的位数都得几十位甚至上百位,所以别想了 发布于 2022-12-17 12:47:53

秋枫落去:现在的魔塔变异度很高,几乎所有的规律都会存在特例,但一定存在魔塔的基本程式.
虽然现实模型存在种种机制,难以拟合,但可以用简化模型来模拟.在只考虑攻防血钥匙的情况下计算出一般的拆塔流程理论上是完全可行的.即使离实际系统存在距离,然其普适性的参考意义依旧很大.
不要尝试枚举等无脑暴算的方式.计算机也需要依据一定的逻辑进行剪枝.通过把攻防钥匙换算成血量的期望,可以借此评估路线的优劣.
其实这方面的思路还有很多,但毕竟不是专业人士,数理分析肯定达不到科学家水平,所以需要逐步摸索.先从简单模型开始,此后再循序建立起逻辑拆塔的大厦. 发布于 2022-12-17 12:46:23

whoshiaz:有中毒的塔是没办法全排列暴力的 发布于 2022-12-17 11:05:03

:这类程序已经有了很多,一般被称为拆塔AI(不是真正意义上的AI),主要是利用动态规划的方法进行计算。有n个节点的魔塔(一般情况下把怪物和门视为节点;如果有吸血、破甲等特殊属性,需要把血瓶、宝石视为节点;如果节点过多,可以分别计算开不同的门的情况,只把要开的门和怪物视为节点),复杂度可以由题主说的n!降到2^n,再根据魔塔本身的特点进行剪枝,或人脑分析与程序计算相结合,有不少魔塔被AI攻克。
高难塔《风之谷2》《无尽轮回》《镜像结界》的制作有AI参与;《一夜登天》《梦多古》《梦境石》某些区域的max由AI首先打出(依靠人脑打出的难度很大);在探索《不愿独醒》《银河——星石传说》《Quella》max的过程中,AI或作为强力的竞争对手,引发人更深层次的研究,或对某些局部进行计算,起到了重要的作用。
但是,随着魔塔规模的增加,完成计算需要的时间和内存剧增。目前,对于单层塔,绝大部分都可以计算出max(某些因特殊的布局或机制,复杂度极高的塔除外,如《朝歌山》《机械世界》);对于5-10层的低层塔,如果以转换为主,不包含(或仅包含少量的)加点、道具和特殊机制,一般也可以计算;对于20层以上的高层塔,只要路线不是特别单一,直接计算是基本不可能的,必须先依靠人脑分析,找到思路,然后计算局部的最优打法。 发布于 2022-12-17 10:57:13

NewUserARTZ:当然可以,只是规模和难度会超乎想象,没有人会花大量时间研究一个非常巧妙又不产生经济价值的算法 发布于 2022-12-17 10:41:03

苍龙啸天斩:首先,必须遍历才可以证明是最优解,否则只是有效解之一。
对于某一个特定的塔,通过遍历寻找最优解是可行的,但如果塔本身元素多,程序设计也会很复杂。 发布于 2022-12-17 10:37:23

63031051:把每开一个门,打一只怪,吃一块宝石当作一个state,估计这问题就是同Hamilton环之类的问题是NP的。
人玩塔的时候可以靠直觉但是计算机视觉只能一个个试state, 发布于 2022-12-17 10:10:53

鋼鐵意志:你觉得对新新魔塔、神秘魔塔、破碎的神圣剑这些能适用吗? 发布于 2022-12-17 10:04:43

Godel_Rosser:给你找到了,反正我看不懂
这好像是一个蓝宝石转换教程塔




发布于 2022-12-17 10:02:53

fell_flower:具体说下,生命最大来自能力的临界获取。即使我们知道初期先拿攻击,后期拿防御。那么每一个攻击力的代价可以计算。吃掉攻击力后的每个伤害也计算,包括大小和减幅。因为有时不是减伤的的是最优,比如连吃两红宝石导致伤害大幅下降,大于两个连续的蓝宝石。这里每步的策略只考虑一个宝石,如果两个也可以三个,显然复杂度上涨很快不可取。如果每步最优,结果也会离最优解很近,一般就这样处理。
钥匙的话,先考虑可打的怪,连开两门怎么处理?这里 复杂度上涨更快。应该当作宝石可考虑的条件,如果钥匙够拿到宝石,那么将宝石纳入计算范围。缺钥匙怎么处理?这里跳过,至少我不知道,if多一个可不是一个。这里的基础是连通图。
要么看博弈或者强化学习,当然都解决不了魔塔最优。 发布于 2022-12-17 09:53:13

liu8713177:没必要做这样的ai,计算量到是不大。但是你需要收集不同装备下怪物的伤害,和收益。某些塔还需要上到高层先拿攻防装备经验。。当你收集完这些后,再按收益去排序。就是最优解。 发布于 2022-12-17 09:49:13

fell_flower:与其说是数学问题,不如说是任凭想象。 发布于 2022-12-17 09:46:43

739099308:可以,但不具有普适性 发布于 2022-12-17 09:46:33

幻灵异梦碧麟劫:以上纯属想象,没学过相关编程知识,不了解实际可否操作 发布于 2022-12-17 09:32:33

更多《魔塔》有没有可能实现算法自动拆塔算出生命max?相关问题

问题:《魔塔》有没有可能实现算法自动拆塔算出生命max?

回答:狂战开荒是最难的 详情 >

问题:《魔塔》敢问各位大佬,怎么入门拆塔啊?rt,为什么我毫无头绪啊,为什

回答:。。。额,这个,表示我没有喜闻,真可怜。。人生若只如初见 何事秋风悲画扇 详情 >

问题:《魔塔》emm有大佬可以发一个最新的初心max数吗 法术流的 如

回答:问一下压缩包那个整合版是已经打上了全部mod了吗?我发现那个技能分开冷却mod没起作用。 详情 >

问题:【求助】整理魔塔大集合过程中部分魔塔作者询问

回答:韦德抓,还有个最高点抓,帅的。 详情 >

问题:《魔塔》大家放弃一个塔一般是什么原因

回答:又是一场突围,大胜之,顺手拿下城市 详情 >