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.