Strategy for playing a board game with Minimax algorithm

Question

I want to build a player for the following game: You have a board where position 1 is your player, position 2 is the rival player, -1 is a blocked cell and some positive value is a bonus. You can move up, down, left, or right. Also, each bonus has a timer until it disappears (number of steps). Furthermore, each move has a timeout limit. At the end game, when at least one of the players is stuck, we check the scores and announce the winner.

Board example:

 -1 -1  0  0  0 -1 -1  -1
 -1  0 -1 -1 -1  0  0  340
 -1 -1  0  0  0 -1  0   0
 -1  0  0 -1  1 -1  0  -1
 -1  0  0 -1 -1  0  0   0
  0  0 -1 -1 -1  0  2  -1
  0 -1  0  0 -1  0  0  600
 -1 -1  0  0 -1 -1 -1  -1
  0 -1  0  0  0  0 -1  -1

I'm using the MiniMax algorithm with a time limit to play the game. If we got to children, we return $\infty$ for a player win, $-\infty$ for the rival win, and $0$ for a tie. If we got to a specific depth, we calculate the heuristic value. If we got timeout in some place in MiniMax, then we return the last calculated direction. I'm trying to figure out a good strategy to win this game or get to a tie if no solution is possible.

What heuristic function would you define?

What I thought - four factors:

1. $f_A$ - The number of steps possible from each direction from the current position.
2. $f_B$ - The analytical distance from the center.
3. $f_C=\max_{b\in Bonus}\frac{X * I}{Y}$ - where $X$ is value of the bonus, $I$ is $1$ if we can get to the bonus, before it disappears (otherwise $0$) and $Y$ is the distance between the bonus and the player.
4. $F_D$ - The distance between the players. The final formula: $$ f(s)=0.5\cdot(9-f_A(s))+0.2\cdot f_C(s)-0.2\cdot f_D(s)-0.1\cdot f_B(s) $$

I'm not sure if it will be a good strategy for that game or not. How would you define the heuristic function? It should also be quick to calculate it because the game has a timeout for each move.

In order words, what will give us the best indication that our player is going to win/lose/tie?

Answer 1

I'm not familiar with your game so I can't tell you what a good heuristic woul be in your specific case, but I can give you some advice on how to look for a good heuristic function.

As a rule of thumb, the heuristic function for a MiniMax algorithm is best kept simple and efficient, so you can get deeper into the tree. But it depends on how costly it is to compute the heuristic function compared to simulating moves in the game.

If the heuristic takes longer than simulating a game move, it might be worth simplifying it so it runs faster and you can look ahead further. This often leads to more emergent and advanced strategies that are hard to express mathematically. An extreme example of a simple heuristic would be the current player score minus the opponent's score. Since scores only change when someone lands on a bonus tile, many paths you take down the tree would have equal value, so you need to be able to look ahead many moves to find a non-zero heuristic and be able to prune parts of the tree. But because the heuristic is so fast to compute, you can do this and discover more non-obvious strategies, simply by brute force simulation. This leads to more emergent behavior, and would tell you more about different ways to play the game (if that is your goal).

If simulating a game move takes longer than your current heuristic, it's probably not worth making the heuristic faster since the game simulation is the dominating factor in how deep you can go down the tree. This case is much more difficult because it means you have to find optimal strategies (and how to express them as a heuristic function) yourself. This is more of an art than a science - ask any chess grandmaster. I'd look up existing literature on the game and see if any existing strategies can be translated into a heuristic function. If there is no literature (e.g. because the game is new or unpopular), you could spend some time playing it yourself to discover what works. Alternatively (and perhaps more interesting), you could use a simple heuristic function with more emergent behavior, increase the time the MiniMax algorithm has to make moves, and play against your NPC opponent a few times to see what strategies it discovers. Or even have two NPCs with different heuristic functions play against each other. Then try to incorporate those into your final heuristic function. This is also a way to determine which heuristic function is better, if you have multiple candidates.

There are ways to optimize the heuristic function automatically using machine learning (specifically reinforcement learning), but it's probably not worth opening that can of worms in your case.