Better Heuristic function for a game (AI Minimax)

Question

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).

• 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)

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.

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:

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?

Answer 1

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.

Answer 2

There is 1 simple way to improve your heuristic considerably. In your current heuristic, the values of square A1 is 8 less than the value of square A8. This makes the Birds inclined to move towards the left side of the game board, as a move to the left will always be higher than a move to the right. This is nit accurate. All squares on row 1 should have the same value. Thus assign all squares in row 1 a 1, in row 2 a 2, etc. This way the birds and larva won't be inclined to move to the left, and instead can focus on making a good move.

Answer 3

You could take into account the fact that birds will have a positional advantage over the larva when the larva is on the sides of the board, so if Larva is MAX then change the side tile values of the board to be smaller.