1
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ What do you mean by "already owned"? Is that a mistake? In your example, how is (2,1) already owned? $\endgroup$ – D.W. Mar 31 '15 at 17:14
  • $\begingroup$ What does it mean for a cell to be empty? It appears you have three concepts: claimed/unclaimed, owned/not owned, empty/not empty. How are they related? Are they synonyms? You haven't defined what you mean by empty nor how the moves affect emptiness. When you say empty, do you mean unowned? $\endgroup$ – D.W. Mar 31 '15 at 17:16
  • $\begingroup$ What have you tried so far? Have you tried using alpha-beta pruning? Have you tried using a heuristic evaluation function? You could also try iterative deepening, but I suspect experiments with a better evaluation function are more likely to lead to useful improvements. $\endgroup$ – D.W. Mar 31 '15 at 17:26
  • $\begingroup$ @D.W. -- Yes, sorry; unowned/unclaimed/empty and owned/claimed/not-empty are used synonymously. In my example, that is to say, any cell you acquire by rushing, you also acquire all adjacent non-diagonal cells that are owned by your opponent. Since Player 1 rushed (2,1), he also acquired (3,1) since it was owned by an opponent. $\endgroup$ – ctote Mar 31 '15 at 19:10
  • $\begingroup$ @D.W. -- I'm attempting to implement alpha-beta pruning. That's the primary purpose for this question actually. I'm trying to determine an algorithm to prune bad moves. I'm not sure if I should focus on point based algorithms that solely compare points, or a move based algorithm that looks at the move-set as a whole. $\endgroup$ – ctote Mar 31 '15 at 19:18
1
$\begingroup$

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.

zugzwang

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.

Move ordering example

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.