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 rush
ing 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 rush
ed. 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.
rush
ing, you also acquire all adjacent non-diagonal cells that are owned by your opponent. Since Player 1rush
ed(2,1)
, he also acquired(3,1)
since it was owned by an opponent. $\endgroup$ – ctote Mar 31 '15 at 19:10