Select the next building to enqueue - AI Game programming

Question

I'm studing some AI concepts and trying to make some code to test my knowledge.

In a recent "standalone project" I tried to develop a AI to determine the best "path" for what buildings to enqueue respecting the "Ai Rules" (A simple building sheet and the rules are defined at the end)

One could say, just upgrade the HQ to max level and that will cut 50% of build time from the others building. But if I follow this path, the queue need to wait for to long to have enough resources for the next HQ level, thus not respecting the first AI Rule.

Then digging the internet I found the Minimax algorithm. I don't feel that it can give me what I want, mainly because the algorithm said it's for known scenarios with 2 players. I don't have 2players, it's the player against the time. Also, the player can receive a "boost" in resources (like pillage), then what was not available becomes available, changing everything.

With the Minimax in mind, I've tought to normalize the time and resource (0..1) and sum up the values then follow the path which has the minimium value and make this evaluation every time the queue it's close to become empty. The outcome from this will not be the global optimum, i'm aware, but it will be "reative".

However, even with this "normalized minimax", running this could (and certainly will) be a demanding operation. With 15 buildings up to level 30 each, I don't even want to know the time to run the code. Also, with low depth = bad decision and high depth = bad performance.

.

Finally, I got stucked. I'm not sure if it will work at all. Does anybody has any suggestion? Or better algorithm?

.

---

• The AI rules:
  1. The queue should never be empty (or, at least, the minimium possible)
  2. Must finish in the small amount of time possible. (by finish I mean, put everything in max level)

---

• The buildings rules:
  1. Time/Resource needed increase 10%/level.
  2. Max level is 10 and min level is 1 for all buildings.

---

• The Buildings sheet Name - Time(sec) - Resource - Bonus HQ - 100 - 100 - Reduce all buildings time (5%/level) Resource - 150 - 80 - 2 resource/sec/level Military - 80 - 80 - none

Answer 1

You might try out dynamic programming, see the checker example here for something that should help you in implementing an algorithm that solves it. The cost function should be able to come directly from your building sheet.