Vegetarian Vampire Solver

All things Desktop Dungeons

Re: Vegetarian Vampire Solver

Postby AvovA17 on Sat Mar 30, 2019 4:48 pm

I threw a web UI and an XP solver together on Thursday in 1 day, but the mathematically "full" xp solver is haaaaard.
UI itself is only like 50% done, cause I still need to code a page for editing monster attributes/adding more monsters.


XP solver is much harder, actually. The space of moves is enormous, and it shrinks too slow. The branching factor is too high. So we need way better logic for cutting off branches / not even considering certain actions.

Currently I use the following heuristics:
1) if there are no monsters higher level than you left (and no Humility), then stop and compute the remaining XP. End of tree branch.

1.5) Naturally, if 2 monsters have all attributes same, only killing one of them is considered. As I add support for more monster attributes, like "slowed" = True/False, the space of possible actions will grow like crazy. I think it is not realistic adding support for "wicked sick", for example.

2) I disallowed all kills of lower levels until nothing else is left. This can be relaxed later. I think this is actually mathematically correct: if you have a kill chain L_1, ..., L_n, and L_i < your level, then the kill chain
L_1, ..., L_{i-1}, L_{i+1}, ..., L_n, L_i will give you the same XP or more, since you have the same base XP, but possibly less bonus XP in the first case. This is not really a complete proof, and the statement might be wrong even, but I ran it without any limitations on lower level kills, and the optimal kill chain was the same (it took 50 min though).

Maybe I missed something, since there are so many items/boons/etc. Killing you own level can only be optimal if you have Balanced Dagger.

3) I use transposition tables, putting (monsters, hero) into the table. Without the tables it takes waaaay too long. With the table it finishes in 12 seconds (but currently I do not support most of dungeon features, like Balanced Dagger, IMAWAL, etc). Under "strategy limitations" I had "only up to L+3 kills allowed".

4) Naturally, I sort available actions so that the most promising ones go to the front.

5) I could do in every position one "greedy pass", just doing all the best actions until the end to get a very good estimate of what is achievable from this dungeon state. Not implemented at the moment. Not sure if it is needed.

6) For every position I estimate the total XP left (assuming I magically cannot even level up anymore, so that every monster gives me max bonus XP). If with this total I cannot beat the current best solution, abandon this branch.

If anybody can think of any other heuristics that can allow abandon search branches, let me know.


Also, my vacation is over, so I dunno how fast I can complete this project now.
Last edited by AvovA17 on Sat Mar 30, 2019 10:16 pm, edited 9 times in total.
AvovA17
 
Posts: 330
Joined: Tue Dec 26, 2017 5:38 pm

Re: Vegetarian Vampire Solver

Postby AvovA17 on Sat Mar 30, 2019 5:02 pm

In fact:
only L+1 kills allowed: 0.12 sec
L+2: 1 sec
L+3: 10 sec
L+4: 24 sec
L+5: 26 sec
L+6: 23 sec (huh?)
L+7: 21 sec (huh??)
L+8: 24.5 sec
L+9: 24.5 sec

I guess it can faster prune branches somehow if it already achieved really high XP in other tree paths.


This is all in python, not even in a proper number-crunching language like C++. I guess there is some hope for the solver to actually finish in finite time with most features in.

Amazingly, even if I allow all actions (even killing L1 monsters when you are L1/L2, for example), it finishes in finite time: 50 minutes.
AvovA17
 
Posts: 330
Joined: Tue Dec 26, 2017 5:38 pm

Re: Vegetarian Vampire Solver

Postby Ranger_762 on Tue Apr 23, 2019 2:20 pm

Thanks for the solver, it's helping in curing my wiki addiction; I swear that when I began playing, I spent much more time reading resources than actually playing... Not that I don't like that, it means that there's lots of content and that the game isn't too easy, but the learning curve looks more like a cliff than like a curve sometimes.
Ranger_762
 
Posts: 4
Joined: Sat Apr 20, 2019 11:08 am

Re: Vegetarian Vampire Solver

Postby AvovA17 on Thu Apr 25, 2019 12:04 pm

You are welcome.

I will finish the "xp maximizer" too when I have the time. Sadly, my vacation is over, and after work, personal stuff, and all the other hobbies, I cannot find the time to finish the code. Not much stuff left to do though.
AvovA17
 
Posts: 330
Joined: Tue Dec 26, 2017 5:38 pm

Re: Vegetarian Vampire Solver

Postby Ranger_762 on Fri Apr 26, 2019 8:04 pm

Nah, don't worry, I get it, I work a lot as well and any non-work related project I have progresses much slower than I'd expect. So finish it at your rhythm, it won't be lost time!
Ranger_762
 
Posts: 4
Joined: Sat Apr 20, 2019 11:08 am

Previous

Return to Desktop Dungeons

Who is online

Users browsing this forum: Bing [Bot] and 68 guests