I am trying to make an AI for the dominoes blocking game. but I am having issues with the hidden information part of the game.
I made a minimax implementation for an AI to play 2 player 14-piece dominoes, which is a perfect information game, with the heuristic of just subtracting the number of pips from a hand to another. the algorithm works pretty well at a depth of 20 moves with alpha-beta pruning. I would like to try to move to a 2 player 7-piece game with a boneyard of 14 pieces, this does introduce imperfect information which I have no experience with, and I couldn't find any minimax algorithm for this kind of games. how would I adapt my old approach? should I change my heuristic? I'm fairly new to game AIs so any help is appreciated. if you want to take a look at my mess of C code here is a link to my repository. here's a snippet of my minimax function:
int minmax(game *g, int depth, int alpha, int beta, int maximizing_player){
if(over(g))
return endgame_evaluation(g) * 1000;
if(depth == 0)
return heuristic_evaluation(g);
struct move moves[MAX];
int n = 0, score;
get_moves(g, moves, &n);
sort_moves(moves, n);
switch(n){
case 0:
pass(g);
score = minmax(g, depth, alpha, beta, !maximizing_player);
unpass(g);
return score;
case 1:
domove(g, moves[0]);
score = minmax(g, depth-1, alpha, beta, !maximizing_player);
unmove(g, moves[0]);
return score;
default:
if(maximizing_player){
for(int i = 0; i < n; i++){
domove(g, moves[i]);
score = minmax(g, depth-1, alpha, beta, 0);
unmove(g, moves[i]);
alpha = max(alpha, score);
if(beta <= alpha)
break;
}
return alpha;
} else {
for(int i = 0; i < n; i++){
domove(g, moves[i]);
score = minmax(g, depth-1, alpha, beta, 1);
unmove(g, moves[i]);
beta = min(beta, score);
if(beta <= alpha)
break;
}
return beta;
}
}
}
Minimax generally works best in perfect information games, however the concept will still work if you don't have all the information about certain things.
I don't know this particular game you are referring to. But you definitely need to modify the algorithm to account for any uncertainties, and try to use statistics or similar to "see into the future".
1If the uncertainty only affects the evaluation of a given gamestate you can very simply use probability or similar in your evaluation function and use the minimax itself as normal.
If the uncertainty also affects what moves that can be played you need to do some more work. Then you can either alter the number of possible moves to include all different cases that can happen, use probability to determine which possible cases to look at, or any other technique to reduce the number of possible moves.