Numerical Boardgame -- Help with with a pruning method (alpha-beta : minimax)
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 &gt;= 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.