4
$\begingroup$

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 minimax the 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?
$\endgroup$
1
$\begingroup$

Before the AI itself can be improved, there is a need to draw a clear line between the game and the AI which is playing the game. Both things have nothing in common, there are separate modules in the project. The game rules are defining which movements are possible on the board. They have to be fixed. It can either be a game of pacman, a game of monster chase or a game of tictactoe but not all of them together. If the game rules are fixed, it's possible to play the game by hand. That means, player1 is a human and player2 is a human. Both players have a score and at the end the game is lost or won.

Now we can talk about the AI which is playing the game. Usually, the AI has the same action space like a human player. The aim of the AI is to maximize it's reward. That means, the game rules are fixed and the AI can choose by it's AI rules which actions is played next. Such kind of controller can be automated, his performance can be tested and it's cpu consumption can be minimized.

The easiest form of an AI is a brute-force search in the game tree. This will solve any game. Advanced algorithm like A*, minimax, or alpha-beta pruning are used only to speed up the search process. That means, to play the game without access to a supercomputer.

$\endgroup$
  • $\begingroup$ I am sorry, but how does this relate to my question? The game rules in the above situation, are fixed, and the game is definitely playable by hand. I, of course, tried brute forcing myself through the game tree, and for small fights, this indeed works, and it helped me in giving me some benchmark results to use for quantification, but for larger trees, even on multiple threads, and 16GB of RAM, it takes VERY long or I simply run out of resources before it can even finish. That's why I am looking for an algorithm like minimax. $\endgroup$ – Adam Baranyai Jan 25 at 11:59
  • $\begingroup$ Such kind of descriptions are valuable. There is a clear problem (gametree search takes to long with 16 gb ram), a first attempt in solving the issue (minimax algorithm, but it doesn't worked well enough) and a question how to improve the situation. I think, you're here in the right forum at the right time and many people know the answer. $\endgroup$ – Manuel Rodriguez Jan 25 at 12:46
  • $\begingroup$ And how do you propose I should move forward? The reason why the brute force approach fails, is because there are way too many possible outcomes, that can be generated on the given board. For example, if the fight would take 15 turns to complete, in the lowest depth, the program would have to try out around 200.000.000 million possibilities (in the last depth only), and this is after pruning some simmilar branches of the tree already. $\endgroup$ – Adam Baranyai Jan 25 at 12:50
  • $\begingroup$ Feature based knowledge engineering works for most games. Some variables are created like distance-to-enemy, direction, speed and own score and these features are tracked over the game tree. $\endgroup$ – Manuel Rodriguez Jan 25 at 13:10

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.