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