What am I doing wrong with this AI?

Question

I am creating a very naive AI (it maybe shouldn't even be called an AI, as it just tests out a lot of possibilites and picks the best one for him), for a board game I am making. This is to simplify the amount of manual tests I will need to do to balance the game.

The AI is playing alone, doing the following things: in each turn, the AI, playing with one of the heroes, attacks one of the max 9 monsters on the battlefield. His goal is to finish the battle as fast as possible (in the least amount of turns) and with the fewest amount of monster activations.

To achieve this, I've implemented a think ahead algorithm for the AI, where instead of performing the best possible move at the moment, he selects a move, based on the possible outcome of future moves of other heroes. This is the code snippet where he does this, it is written in PHP:

/** Perform think ahead moves
 *
 * @params int         $thinkAheadLeft      (the number of think ahead moves left)
 * @params int         $innerIterator       (the iterator for the move)
 * @params array       $performedMoves      (the moves performed so far)
 * @param  Battlefield $originalBattlefield (the previous state of the Battlefield)
 */
public function performThinkAheadMoves($thinkAheadLeft, $innerIterator, $performedMoves, $originalBattlefield, $tabs) {
    if ($thinkAheadLeft == 0) return $this->quantify($originalBattlefield);

    $nextThinkAhead = $thinkAheadLeft-1;
    $moves = $this->getPossibleHeroMoves($innerIterator, $performedMoves);
    $Hero = $this->getHero($innerIterator);
    $innerIterator++;
    $nextInnerIterator = $innerIterator;
    foreach ($moves as $moveid => $move) {
        $performedUpFar = $performedMoves;
        $performedUpFar[] = $move;
        $attack = $Hero->getAttack($move['attackid']);
        $monsters = array();
        foreach ($move['targets'] as $monsterid) $monsters[] = $originalBattlefield->getMonster($monsterid)->getName();
        if (self::$debug) echo $tabs . "Testing sub move of " . $Hero->Name. ": $moveid of " . count($moves) . "  (Think Ahead: $thinkAheadLeft | InnerIterator: $innerIterator)\n";

        $moves[$moveid]['battlefield']['after']->performMove($move);

        if (!$moves[$moveid]['battlefield']['after']->isBattleFinished()) {
            if ($innerIterator == count($this->Heroes)) {
                $moves[$moveid]['battlefield']['after']->performCleanup();
                $nextInnerIterator = 0;
            }
            $moves[$moveid]['quantify'] = $moves[$moveid]['battlefield']['after']->performThinkAheadMoves($nextThinkAhead, $nextInnerIterator, $performedUpFar, $originalBattlefield, $tabs."\t", $numberOfCombinations);
        } else $moves[$moveid]['quantify'] = $moves[$moveid]['battlefield']['after']->quantify($originalBattlefield);
    }

    usort($moves, function($a, $b) {
        if ($a['quantify'] === $b['quantify']) return 0;
        else return ($a['quantify'] > $b['quantify']) ? -1 : 1;
    });

    return $moves[0]['quantify'];
}

What this does is that it recursively checks future moves, until the $thinkAheadleft value is reached, OR until a solution was found (ie, all monsters were defeated). When it reaches it's exit parameter, it calculates the state of the battlefield, compared to the $originalBattlefield (the battlefield state before the first move). The calculation is made in the following way:

 /** Quantify the current state of the battlefield
 *
 * @param Battlefield $originalBattlefield (the original battlefield)
 *
 * returns int (returns an integer with the battlefield quantification)
 */
public function quantify(Battlefield $originalBattlefield) {

    $points = 0;
    foreach ($originalBattlefield->Monsters as $originalMonsterId => $OriginalMonster) {
        $CurrentMonster = $this->getMonster($originalMonsterId);

        $monsterActivated = $CurrentMonster->getActivations() - $OriginalMonster->getActivations();
        $points+=$monsterActivated*($this->quantifications['activations'] + $this->quantifications['activationsPenalty']);

        if ($CurrentMonster->isDead()) $points+=$this->quantifications['monsterKilled']*$CurrentMonster->Priority;
        else {
            $enragePenalty = floor($this->quantifications['activations'] * (($CurrentMonster->Enrage['max'] - $CurrentMonster->Enrage['left'])/$CurrentMonster->Enrage['max']));

            $points+=($OriginalMonster->Health['left'] - $CurrentMonster->Health['left']) * $this->quantifications['health'];
            $points+=(($CurrentMonster->Enrage['max'] - $CurrentMonster->Enrage['left']))*$enragePenalty;
        }
    }

    return $points;
}

When quantifying some things net positive points, some net negative points to the state. What the AI is doing, is, that instead of using the points calculated after his current move to decide which move to take, he uses the points calculated after the think ahead portion, and selecting a move based on the possible moves of the other heroes.

Basically, what the AI is doing, is saying that it isn't the best option at the moment, to attack Monster 1, but IF the other heroes will do this-and-this actions, in the long run, this will be the best outcome.

After selecting a move, the AI performs a single move with the hero, and then repeats the process for the next hero, calculating with +1 moves.

ISSUE: My issue is, that I was presuming, that an AI, that 'thinks ahead' 3-4 moves, should find a better solution than an AI that only performs the best possible move at the moment. But my test cases show differently, in some cases, an AI, that is not using the think ahead option, ie only plays the best possible move at the moment, beats an AI that is thinking ahead 1 single move. Sometimes, the AI that thinks ahead only 3 moves, beats an AI that thinks ahead 4 or 5 moves. Why is this happening? Is my presumption incorrect? If so, why is that? Am I using wrong numbers for weights? I was investigating this, and run a test, to automatically calculate the weights to use, with testing an interval of possible weights, and trying to use the best outcome (ie, the ones, which yield the least number of turns and/or the least number of activations), yet the problem I've described above, still persists with those weights also.

I am limited to a 5 move think ahead with the current version of my script, as with any larger think ahead number, the script gets REALLY slow (with 5 think ahead, it finds a solution in roughly 4 minutes, but with 6 think ahead, it didn't even find the first possible move in 6 hours)

HOW THE FIGHT WORKS: The fight works in the following way: a number of heroes (2-4) controlled by the AI, each having a number of different attacks (1-x), which can be used once or multiple times in a combat, are attacking a number of monsters (1-9). Based on the values of the attack, the monsters lose health, until they die. After each attack, the attacked monster gets enraged if he didn't die, and after each heroes performed a move, all monsters get enraged. When the monsters reach their enrage limit, they activate.

DISCLAIMER: I know that PHP is not the language to use for this kind of operation, but as this is only an in-house project, I've preferred to sacrifice speed, to be able to code this as fast as possible, in my native programming language.

UPDATE: The quantifications that we currently use look something like this:

$Battlefield->setQuantification(array(
 'health'                   =>  16,
 'monsterKilled'            =>  86,
 'activations'              =>  -46,
 'activationsPenalty'       =>  -10
));

Answer 1

If there is randomness in your game, then anything can happen. Pointing that out since it's just not clear from the materials you have posted here.

If there is no randomness and the actors can see the full state of the game, then a longer look-ahead absolutely should perform better. When it does not, it is a clear indication that your evaluation function is providing incorrect estimates of the value of a state.

In looking at your code, the values of your quantifications are not listed and in your simulation it looks like you just have the same player make moves repeatedly without considering the possible actions of the other actors. You need to run a full simulation, step by step in order to produce accurate future states and you need to look at the value estimates of the varying states to see if you agree with them, and make adjustments to your quantifications accordingly.

An alternative way to frame the problem of estimating value is to explicitly predict your chances of winning the round as a percentage on a scale of 0.0 to 1.0 and then choose the move that gives you the highest chance of winning. Calculating the damage done and number of monsters killed so far doesn't tell you much about how much you have left to do in order to win the game.