1
\$\begingroup\$

This is my Game-Board: enter image description here

-> The Red Balls are the AI-Controlled Actors.
-> The Blue Balls are the Player-Controlled Actors.
-> The Yellow Cells are the locations, from which the Red Balls can attack.
-> Each Red Ball can do 2 actions: move-move, move-attack, attack-attack.
-> At no time there can be 2 minions on one cell, but a minion can arrive on a cell another just left.

Its the AI's turn. Its planning the whole turn for all minions, each of them has the two moves.
The objective is to maximize the number of melee attacks, which can performed in a single turn (2 actions) on the player balls.

Problem I have in my current (brute-force) implementation:

  • Sometimes it is advisable for a minion to move, although it is already in a melee position, to make space for another minion, which can then move into melee range aswell.

Example: enter image description here

In this situation its more effective for the front minion to move once, so another minion can move into melee range as well.

Do you know an effective algorithm for this job? Thank you for your time!

\$\endgroup\$
4
  • 1
    \$\begingroup\$ Your first step would be to calculate all possible moves for each AI unit without regard for other AI units, rate each move by tactical and strategic considerations and order them by rating so you got a first, second, third etc. choice per unit. Then you need to find the solution with the best overall happiness. I am pretty sure that this last step is a quite well-researched optimization problem in computer science. I just can't remember how it was called. \$\endgroup\$
    – Philipp
    Commented Dec 14, 2016 at 16:10
  • \$\begingroup\$ Thanks. Would you mind to elaborate on this, maybe in an answer? :) \$\endgroup\$
    – user60245
    Commented Dec 14, 2016 at 16:54
  • \$\begingroup\$ I would if I could remember how that problem was called so I could look up how it is usually solved. I don't write incomplete answers. \$\endgroup\$
    – Philipp
    Commented Dec 14, 2016 at 16:58
  • \$\begingroup\$ I understand and appreciate this. \$\endgroup\$
    – user60245
    Commented Dec 15, 2016 at 11:37

1 Answer 1

Reset to default
-1
\$\begingroup\$

Alpha-Beta pruning: https://en.wikipedia.org/wiki/Alpha%E2%80%93beta_pruning is commonly used for those scenarios. Depends how do you want to your game behave, you can choose another algorithm. Difficulty of the game (as strong the opponent is) is how deep the AI goes in tree or size of stack.

\$\endgroup\$
1
  • \$\begingroup\$ The problem is that we are dealing with a game here where a "turn" means that the AI player makes a move with every single one of their units and each move affects the available options of the other units. The number of possible move combinations a player can make on their turn grows exponentially with the number of units they control. A search tree is not an appropriate solution for this problem because there are just too many possible options, even with optimizations like alpha-beta pruning. \$\endgroup\$
    – Philipp
    Commented Dec 15, 2016 at 14:26

You must log in to answer this question.