Numerical Boardgame — Help with with a pruning method (alpha-beta : minimax)

Question

I'm developing a simple AI to play a boardgame which consists of N x N squares, each with a predefined value.

44 33 75 12 99 23
53 89 14 01 32 98
34 98 67 45 02 38
89 87 54 21 34 87
65 84 99 72 95 17

Each player can either (a) instant claim an unclaimed cell anywhere on the board, or (b) rush an unclaimed cell from a cell already owned. In the case of (b), any enemy cells that are touching the newly claimed cell are converted to your side.

Example:

• Player 1: (1,1) -- {89}
• Player 2: (3,1) -- {87}
• Player 1: rush->(2,1) -- {98}

In the scenario above, after the rush move, Player 1 now owns all three cells (since (3,1) was an adjacent cell to (2,1)).

I have the MiniMax algorithm working great for this. It's actually quite fun to watch the AI compete against each other. My problem is determining an effective way to prune moves from the tree. I attempted a trivial pruning method of:

 - - If the cell we're claiming is empty
 - - - If the neighbors of the cell we're claiming is empty
 - - - - If the neighbor's-neighbor is an enemy-owned cell
 - - - - - Prune this move

The idea above being, we don't want to claim a cell that could immediately result in the opponent rushing towards us, claiming for themselves the cell we just claimed.

This didn't go well.

I'm a bit at a loss for a decent heuristic for pruning moves at this point. Move ordering is a bit difficult because I can't just choose the highest remaining cell (can I?), since there are plenty of opportunities for the opponent to right-out rush that cell as soon as it's claimed. That is to say, if our opponent owns cell (4,4), it wouldn't be ideal for us to choose (4,2) since it could wind up being immediately rushed. But maybe it wouldn't hurt to start at the largest values and just test them out? I don't know.

Any help here is greatly appreciated.

Answer 1

I'm a bit at a loss for a decent heuristic for pruning moves at this point

You can start from the observation that for the side to move there is almost always a better alternative than doing nothing (at least in the first phase of the game, when there are many moves).

So you can try a "null" move (the side to play passes and lets the opponent get a free move): if the score of the subtree search (depth reduced by a R constant) is still high enough to cause a beta cutoff you can prune the tree.

The pseudo-code is something like:

switch_side_to_play()                                     // Null move
score = -ab_search(-beta, 1 - beta, depth - R - 1)
switch_side_to_play()

if (score >= beta )
  // return score (cutoff) or reduce the search depth

As every heuristic, it sometimes fails. This is an example from Chess but the same problem could happen in your game when there are only few moves available.

If White is to move, he will have to move Kd6, which results in stalemate, or move away from the pawn which loses it.

However if White could pass (null-move), Black would have to play Kc7 (White plays Ke7 and the pawn queens).

---

I'd start trying null move: if it works there is much to gain. If it doesn't work (Checkers / Othello are two well known examples), ProbCut heuristic would be a good alternative.

The general idea of ProbCut is to perform a shallow search. If the result is far outside the alpha-beta window you trust the search, otherwise you have to re-search to the full depth.

If you assume this relationship (linear model) between the value of a shallow search ($v'$) and the values of a full search ($v$):

$$v = a \cdot v' + b + \mathcal{E} $$

($\mathcal{E}$ is an error variable, normally distributed, with mean 0 and standard deviation $\sigma$)

Then the beta-cutoff condition of the alpha-beta algorithm ($v \ge \beta$) becomes:

$$ v′\ge \frac{Φ^{−1}(p) \cdot \sigma + \beta − b}{a} $$

(same for $\alpha$, see the linked paper for further details).

The nuisance is that you have to tune many parameters, but this is a very general pruning technique.

---

Move ordering is a bit difficult because I can't just choose the highest remaining cell (can I?), since there are plenty of opportunities for the opponent to right-out rush that cell as soon as it's claimed.

This is similar to captures in chess: you can take a piece but the opponent could recapture.

So a complex heuristic to evaluate the result of a sequence of captures on a square is a possibility, but also a simple heuristic like MVV-LVA (Most Valuable Victim - Least Valuable Aggressor) is very effective.

You could try highest remaining cell + sum of cells claimed by rush or highest remaining cell + sum of cells claimed by rush - (number of attacking cells) % 2.

According to this heuristic the last move has a value of 9 + (1 + 10) - 1. This is very coarse but it isn't for pruning, just for ordering.