I'm developing a game for android, and now i came to the AI part of it. I never wrote AI (previous application didn't need it), i tried to read what i found and thought it will be useful.

Since i'm developing for android, i'm forced to use java (yes, i can use the ndk, but it is far too much effort for the needed results), i'm memory bound and the less i use the cpu the better(i don't want my app to drain all the battery).

I'm first developing a 1 vs 1 situation, but i would like to improve it to be a X vs Y in future(not strictly related to this topic, but please keep this in mind when responding. I prefer expandable and maintainable code overs strict efficiency).

I have D = A + B + C entities(the real player controls A entities, the enemy controls B, and there are C unallocated entities). A player wins when all the opposite entities are killed, so even with 1 remaining entity, if the opposite player doesn't control any more, the player wins.

Since an entity can perform 2 actions, one on the enemy entities and one on the unallocated entities, so each choice/node has a branching of B + C
This leads to a big growth of a possible choices-tree.

In addition, in my game cyclic states can appear (cyclic state = you are in state A. You and the enemy do a some actions, and then you are again in state A). I would like to avoid this, even letting the AI do not-the-best-suited-move.

In addition i would like the AI not always to perform the best guessed action, but to randomly choose with a given distribution between the best e.g. 5 possible moves(obviously i need to find the 5 best possible moves, i can code the choice on my own ): predictability kills fun.

And the AI will have a maximum set of time to make its choice(that thus will probably be not the best one, but the better it can find in the give time).

I read about minmax and alpha-beta pruning, but i don't know if it can be the best algorithm for my case, if it is memory or processor hungry, if it can provide the best X moves and not only the best one, and it can be extended to work with more player..
In addition i don't know if it is heavier to reconstruct the tree each turn or to keep it in memory..

Useful resources, maybe with implementations details or code, would be really appreciated

A possible tree
http://www.pasteall.org/pic/show.php?id=25213

I'm developing a game for android, and now i came to the AI part of it. I never wrote AI (previous application didn't need it), i tried to read what i found and thought it will be useful.

Since i'm developing for android, i'm forced to use java (yes, i can use the ndk, but it is far too much effort for the needed results), i'm memory bound and the less i use the cpu the better(i don't want my app to drain all the battery).

I'm first developing a 1 vs 1 situation, but i would like to improve it to be a X vs Y in future(not strictly related to this topic, but please keep this in mind when responding. I prefer expandable and maintainable code overs strict efficiency).

I have D = A + B + C entities(the real player controls A entities, the enemy controls B, and there are C unallocated entities). A player wins when all the opposite entities are killed, so even with 1 remaining entity, if the opposite player doesn't control any more, the player wins.

Since an entity can perform 2 actions, one on the enemy entities and one on the unallocated entities, on each turn the player A has B + C possible choices.
This leads to a big growth of a possible choices-tree.

In addition, in my game cyclic states can appear (cyclic state = you are in state A. You and the enemy do a some actions, and then you are again in state A). I would like to avoid this, even letting the AI do not-the-best-suited-move.

In addition i would like the AI not always to perform the best guessed action, but to randomly choose with a given distribution between the best e.g. 5 possible moves(obviously i need to find the 5 best possible moves, i can code the choice on my own ): predictability kills fun.

And the AI will have a maximum set of time to make its choice(that thus will probably be not the best one, but the better it can find in the give time).

I read about minmax and alpha-beta pruning, but i don't know if it can be the best algorithm for my case, if it is memory or processor hungry, if it can provide the best X moves and not only the best one, and it can be extended to work with more player..
In addition i don't know if it is heavier to reconstruct the tree each turn or to keep it in memory..

Useful resources, maybe with implementations details or code, would be really appreciated

I'm developing a game for android, and now i came to the AI part of it. I never wrote AI (previous application didn't need it), i tried to read what i found and thought it will be useful.

Since i'm developing for android, i'm forced to use java (yes, i can use the ndk, but it is far too much effort for the needed results), i'm memory bound and the less i use the cpu the better(i don't want my app to drain all the battery).

I'm first developing a 1 vs 1 situation, but i would like to improve it to be a X vs Y in future(not strictly related to this topic, but please keep this in mind when responding. I prefer expandable and maintainable code overs strict efficiency).

I have D = A + B + C entities(the real player controls A entities, the enemy controls B, and there are C unallocated entities). A player wins when all the opposite entities are killed, so even with 1 remaining entity, if the opposite player doesn't control any more, the player wins.

Since an entity can perform 2 actions, one on the enemy entities and one on the unallocated entities, on each turn the player A has B + C possible choices.
This leads to a big growth of a possible choices-tree.

In addition, in my game cyclic states can appear (cyclic state = you are in state A. You and the enemy do a some actions, and then you are again in state A). I would like to avoid this, even letting the AI do not-the-best-suited-move.

In addition i would like the AI not always to perform the best guessed action, but to randomly choose with a given distribution between the best e.g. 5 possible moves(obviously i need to find the 5 best possible moves, i can code the choice on my own ): predictability kills fun.

And the AI will have a maximum set of time to make its choice(that thus will probably be not the best one, but the better it can find in the give time).

I read about alpha-beta pruning, but i don't know if it can be the best algorithm for my case, if it is memory or processor hungry, if it can provide the best X moves and not only the best one, and it can be extended to work with more player..
In addition i don't know if it is heavier to reconstruct the tree each turn or to keep it in memory..

Useful resources, maybe with implementations details or code, would be really appreciated

I'm developing a game for android, and now i came to the AI part of it. I never wrote AI (previous application didn't need it), i tried to read what i found and thought it will be useful.

Since i'm developing for android, i'm forced to use java (yes, i can use the ndk, but it is far too much effort for the needed results), i'm memory bound and the less i use the cpu the better(i don't want my app to drain all the battery).

I'm first developing a 1 vs 1 situation, but i would like to improve it to be a X vs Y in future(not strictly related to this topic, but please keep this in mind when responding. I prefer expandable and maintainable code overs strict efficiency).

I have D = A + B + C entities(the real player controls A entities, the enemy controls B, and there are C unallocated entities). A player wins when all the opposite entities are killed, so even with 1 remaining entity, if the opposite player doesn't control any more, the player wins.

Since an entity can perform 2 actions, one on the enemy entities and one on the unallocated entities, on each turn the player A has B + C possible choices.
This leads to a big growth of a possible choices-tree.

In addition, in my game cyclic states can appear (cyclic state = you are in state A. You and the enemy do a some actions, and then you are again in state A). I would like to avoid this, even letting the AI do not-the-best-suited-move.

In addition i would like the AI not always to perform the best guessed action, but to randomly choose with a given distribution between the best e.g. 5 possible moves(obviously i need to find the 5 best possible moves, i can code the choice on my own ): predictability kills fun.

And the AI will have a maximum set of time to make its choice(that thus will probably be not the best one, but the better it can find in the give time).

I read about alpha-beta pruning, but i don't know if it can be the best algorithm for my case, if it is memory or processor hungry, if it can provide the best X moves and not only the best one, and it can be extended to work with more player..
In addition i don't know if it is heavier to reconstruct the tree each turn or to keep it in memory..

I'm developing a game for android, and now i came to the AI part of it. I never wrote AI (previous application didn't need it), i tried to read what i found and thought it will be useful.

Since i'm developing for android, i'm forced to use java (yes, i can use the ndk, but it is far too much effort for the needed results), i'm memory bound and the less i use the cpu the better(i don't want my app to drain all the battery).

I'm first developing a 1 vs 1 situation, but i would like to improve it to be a X vs Y in future(not strictly related to this topic, but please keep this in mind when responding. I prefer expandable and maintainable code overs strict efficiency).

I have D = A + B + C entities(the real player controls A entities, the enemy controls B, and there are C unallocated entities). A player wins when all the opposite entities are killed, so even with 1 remaining entity, if the opposite player doesn't control any more, the player wins.

Since an entity can perform 2 actions, one on the enemy entities and one on the unallocated entities, on each turn the player A has B + C possible choices.
This leads to a big growth of a possible choices-tree.

In addition, in my game cyclic states can appear (cyclic state = you are in state A. You and the enemy do a some actions, and then you are again in state A). I would like to avoid this, even letting the AI do not-the-best-suited-move.

In addition i would like the AI not always to perform the best guessed action, but to randomly choose with a given distribution between the best e.g. 5 possible moves(obviously i need to find the 5 best possible moves, i can code the choice on my own ): predictability kills fun.

And the AI will have a maximum set of time to make its choice(that thus will probably be not the best one, but the better it can find in the give time).

I read about alpha-beta pruning, but i don't know if it can be the best algorithm for my case, if it is memory or processor hungry, if it can provide the best X moves and not only the best one, and it can be extended to work with more player..
In addition i don't know if it is heavier to reconstruct the tree each turn or to keep it in memory..

I'm developing a game for android, and now i came to the AI part of it. I never wrote AI (previous application didn't need it), i tried to read what i found and thought it will be useful.

Since i'm developing for android, i'm forced to use java (yes, i can use the ndk, but it is far too much effort for the needed results), i'm memory bound and the less i use the cpu the better(i don't want my app to drain all the battery).

I'm first developing a 1 vs 1 situation, but i would like to improve it to be a X vs Y in future(not strictly related to this topic, but please keep this in mind when responding. I prefer expandable and maintainable code overs strict efficiency).

I have D = A + B + C entities(the real player controls A entities, the enemy controls B, and there are C unallocated entities). A player wins when all the opposite entities are killed, so even with 1 remaining entity, if the opposite player doesn't control any more, the player wins.

Since an entity can perform 2 actions, one on the enemy entities and one on the unallocated entities, on each turn the player A has B + C possible choices.
This leads to a big growth of a possible choices-tree.

In addition, in my game cyclic states can appear (cyclic state = you are in state A. You and the enemy do a some actions, and then you are again in state A). I would like to avoid this, even letting the AI do not-the-best-suited-move.

In addition i would like the AI not always to perform the best guessed action, but to randomly choose with a given distribution between the best e.g. 5 possible moves(obviously i need to find the 5 best possible moves, i can code the choice on my own ): predictability kills fun.

And the AI will have a maximum set of time to make its choice(that thus will probably be not the best one, but the better it can find in the give time).

I read about alpha-beta pruning, but i don't know if it can be the best algorithm for my case, if it is memory or processor hungry, if it can provide the best X moves and not only the best one, and it can be extended to work with more player..
In addition i don't know if it is heavier to reconstruct the tree each turn or to keep it in memory..