Search code examples
artificial-intelligenceheuristicsminimaxalpha-beta-pruningevaluation-function

Better Heuristic function for a game (AI Minimax)

There is a game that I've programmed in java. The game is simple (refer to the figure below). There are 4 birds and 1 larva. It is a 2 player game (AI vs Human).

enter image description here

  • Larva can move diagonally forward AND diagonally backward
  • Birds can ONLY move diagonally forward
  • Larva wins if it can get to line 1 (fence)
  • Larva also wins if birds have no moves left
  • Birds CANNOT "eat" the larva.
  • Birds win if Larva has NO move left (cannot move at all)

enter image description here

When the game starts, Larva begins, then ONE bird can move (any one), then Larva, etc...

I have implemented a MiniMax (Alpha Beta Pruning) and I'm using the following evaluate() function (heuristic function).

Let us give the following numbers to each square on the board.

enter image description here

Therefore, our evaluation function will be

h(n) = value of position of larva - value of position of bird 1 - value of position of bird 2 - value of position of bird 3 - value of position of bird 4

the Larva will try to MAXIMIZE the heuristic value whereas the Birds will try to MINIMIZe it

Example:

enter image description here

However, this is a simple and naive heuristic. It does not act in a smart manner. I am a beginner in AI and I would like to know what can I do to IMPROVE this heuristic function?

What would be a good/informed heuristic?

Solution

  • How about this :

    Maximum :larva

    Minimum :birds

    H(t)=max_distance(larva,line_8)+Σmin_distance(bird_n,larva)

    or

    H(t)=Σmin_distance(bird_n,larva) - min_distance(larva,line_1)

    max_distance(larva,line_8): to reflect the condition that larva is closer to the line 1.

    Σmin_distance(bird_n,larva): to reflect the condition that birds are closer to the larva(to block it).

    I believe there are still many thing could be considered ,for example ,the bird closest to the larva should have high priority to be chosen to move, but the direction about the function above make sense , and many details can be thought to improve it easily.