I am trying to write an AI to a game, where there is no real adversary. This means, that only the AI player has choices in which move to perform, his opponent may or may not react to the move the AI player made, but when he reacts, he will always do the one and only single move that he is able to do. The goal of this AI would be, to find a solution to the situation, which results in the least amount of monster activations.
To explain this a bit further, I will describe the game in a few words: there is a 3x3 board, on which there are some monsters. These monsters has a prewritten AI, and activate based on prewritten rules, ie, they do not have to make any decision at all. This is done, by an enrage mechanic, meaning, that when a monster hits it's enrage limit, it activates, and performs his single move action.
The AI should control the other side of this board, the hero players. Each hero player has a different number of possible moves, each move dealing an amount of damage to the monsters, and increasing it's enrage value, thus getting him closer to his enrage limit.
What I want to achieve, is to write an AI, that will perform this fight in the least amount of monster activations as possible.
For now, I've written a minimax algorithm for this, without the min player. I've done this, by calculating the negative effect of the monsters move, in the maximizing and only players move.
The AI works in the following way: he draws the game tree for a set amount of depth of moves, calculates the bottom move with a heuristic function, selects the highest value from the given depth, and returns the value of this function up one level, then repeat. When he reaches the top of the tree, he performs the move, with the highest quantification value.
This works, somewhat, but I have a big problem: As there is no randomness in the game, I was expecting that the greater the depth that he can search forward, the better moves he will find, but this is not always the case, sometimes a greater depth, returns a worse solution then a smaller depth
My questions are as follows:
- what could cause the above error? My quantification function? The weights that I use in the function? Or something else?
- is
minimaxthe correct algorithm to use, for a game where there is no real adversarry, or is there any algorithm that will perform better for a game like this?