DAS Studio

Welcome everyone to my DAS Studio.

DAS Studio is all about magic tower! I am ambitious to make magic tower a eco-system!

I decide to put most of my past codes on here, so that everyone can have an inspiration of magic tower AI implementation.

I admit that some of the code contains too little comments. I happily programmed them within a month, and now even I will find some of the AI internal logic hard to read.

I plan to discard most of the code here, and turn to Python for everything except for AI.

How hard is magic tower

It seems like kidding, but magic tower is an instance of NP-complete problem. We will put the proof in the end.

However in most cases the magic tower is not that pathological, and can be approximated by dynamic programming.

My (old) algorithms for magic tower is partially dynamic programming, partially AI-some, with some heuristic assumption that helps much for solving approximating a magic tower.

What is Magic Tower?

Tower of the Sorcerer is considered the first instance of magic tower. Magic tower has been created and researched deeply in the twenty years.

Magic tower is a type of puzzle game. The kernel part of the repository is self-explanatory. However, playing the game by hand will make you understand more about the game rules. You can try Tower of the Sorcerer mentioned before for the origin of some of the rules.

Content

• kernel
  • A magic tower model.
  • used in X-NUCA, where I publicly (anonymously) polled for a magic tower AI algorithm.
• database
  • A set of test cases that is helpful for testing of the DAS/non-DAS utilities.
  • Partially provided by @David Lee.
  • Some adapted from the magic towers created by intelligent minds here.
  • Some hand-crafted, some generated by a magic tower generator (sadly it is still stupid).
  • I consider one of the best testcase in quality to be t1.mt . My best AI even can not beat it (The believed maximum is 666, as in t1.in). It is 魔塔-梦多古 遗忘之地 Magictower Mengduogu - Forgotten Land, authored by @motax4.
• mt-gui
  • A magic tower GUI based on the model.
  • Can be compiled into binary (both Windows and linux, Mac not tested), and Emscripten!
• mtenc
  • A pseudo public-key cryptography (really!?) that rely on solving a magic tower.
  • Internally a key generator from a magic tower and route.
• mapgen-ai
  • A example magic tower AI along with some implementation of magic tower generator based on the AI.
  • The version is barely compilable. Versions afterwards cannot compile since some hackish optimization is applied. Considering that I did not put them up.
  • Usage: (some utilities require your manual interrupt Ctrl-C, or it will run permanently.)
    • cd mapgen-ai && make
    • ./main < ../database/59-hut.mt
    • ./mtg_tester < ../database/59-hut.mt

License

The work is under with MIT license. (except the assets of mt-gui, some of them are not necessarily in public domain, and you may need to replace them to avoid problems; they are only for compilation easiness; also the code that is not authored by me, including zlib and base64(that may be one of the reason why I need to turn to python!))

Proof of NP completeness of magic tower

If we can provide arbitrarily strange graph:

We will reduce vertex cover problem (which is known to be NPC thanks to the great theoretical computer scientists) to magic tower.

First we need to define both problems:

Vertex cover:

Given a undirected graph G and an positive integer K, ask if there is a vertex subset of G, named G' whose cardinality is smaller than K, and every edge will have at least one vertex in G' that is connected to the edge.

Magic tower:

Given a magic tower map, brave initial power, enemies' power, and all miscellaneous data, is there a way to get the flag on the map? (See kernel directory to see the detailed definition of a magic tower. We assume that the input is not pathological to crash the magic tower engine.)

Proof:

Magic tower is in NP. It is obvious, the kernel directory is the certificate verifier that runs in polynomial time.

For the NP hardness part. We can transform a graph easily into magic tower. We leave details for enthusiastic readers.

Therefore we can make every vertex of original graph an uniformed enemy E1, every edge an blue crystal +1def, with every enemy accessible by brave initially.

And there is an enemy E2 that is defending for a flag.

E1 is Magic and solid, so that its damage is constant. let the constant be 1.

E2 is Solid and its health is a sufficient big number that as long as brave's defence power is lower than its attack power, the damage is infinite large to suffer.

When ask for a graph G(V, E) and k, we can have a brave that has k+1 health point, 1 attack point, 0 defence point, 0 magic defence point. E2's attack point is set to be |E|.

Therefore, in order to capture the flag, we need to collect every blue crystal on the map. And we need to defeat less than k enemy E1s before we have all of the blue crystals.

Therefore, the solution of the magic tower is the solution of the vertex cover problem.

If the graph is limited, however is star graph (which is very common in magic tower case, and is the weakest):

The magic tower problem is still stronger than (can express) 0-1 knapsack problem, which is still NPC. Proof is omitted here.