Quiero utilizar la búsqueda de minimax (con poda alfa-beta), o más bien buscar negamax, para hacer que un programa de computadora juegue un juego de cartas.Uso de búsqueda de minimax para juegos de cartas con información imperfecta
El juego de cartas en realidad consiste en 4 jugadores. Entonces, para poder usar minimax, etc., simplifico el juego a "mí" contra los "otros". Después de cada "movimiento", puede leer objetivamente la evaluación del estado actual del juego en sí. Cuando los 4 jugadores hayan colocado la carta, la más alta los ganará a todos, y los valores de las cartas cuentan.
Como no sabes cómo es exactamente la distribución de cartas entre los otros 3 jugadores, pensé que debes simular todas las distribuciones posibles ("mundos") con las cartas que no son tuyas. Tienes 12 cartas, los otros 3 jugadores tienen 36 cartas en total.
Así que mi enfoque es este algoritmo, donde player es un número entre 1 y 3 que simboliza los tres jugadores de la computadora para los que el programa podría necesitar movimientos. Y -player representa a los oponentes, es decir, a los otros tres jugadores juntos.
private Card computerPickCard(GameState state, ArrayList<Card> cards) {
int bestScore = Integer.MIN_VALUE;
Card bestMove = null;
int nCards = cards.size();
for (int i = 0; i < nCards; i++) {
if (state.moveIsLegal(cards.get(i))) { // if you are allowed to place this card
int score;
GameState futureState = state.testMove(cards.get(i)); // a move is the placing of a card (which returns a new game state)
score = negamaxSearch(-state.getPlayersTurn(), futureState, 1, Integer.MIN_VALUE, Integer.MAX_VALUE);
if (score > bestScore) {
bestScore = score;
bestMove = cards.get(i);
}
}
}
// now bestMove is the card to place
}
private int negamaxSearch(int player, GameState state, int depthLeft, int alpha, int beta) {
ArrayList<Card> cards;
if (player >= 1 && player <= 3) {
cards = state.getCards(player);
}
else {
if (player == -1) {
cards = state.getCards(0);
cards.addAll(state.getCards(2));
cards.addAll(state.getCards(3));
}
else if (player == -2) {
cards = state.getCards(0);
cards.addAll(state.getCards(1));
cards.addAll(state.getCards(3));
}
else {
cards = state.getCards(0);
cards.addAll(state.getCards(1));
cards.addAll(state.getCards(2));
}
}
if (depthLeft <= 0 || state.isEnd()) { // end of recursion as the game is finished or max depth is reached
if (player >= 1 && player <= 3) {
return state.getCurrentPoints(player); // player's points as a positive value (for self)
}
else {
return -state.getCurrentPoints(-player); // player's points as a negative value (for others)
}
}
else {
int score;
int nCards = cards.size();
if (player > 0) { // make one move (it's player's turn)
for (int i = 0; i < nCards; i++) {
GameState futureState = state.testMove(cards.get(i));
if (futureState != null) { // wenn Zug gültig ist
score = negamaxSuche(-player, futureState, depthLeft-1, -beta, -alpha);
if (score >= beta) {
return score;
}
if (score > alpha) {
alpha = score; // alpha acts like max
}
}
}
return alpha;
}
else { // make three moves (it's the others' turn)
for (int i = 0; i < nCards; i++) {
GameState futureState = state.testMove(cards.get(i));
if (futureState != null) { // if move is valid
for (int k = 0; k < nCards; k++) {
if (k != i) {
GameState futureStateLevel2 = futureState.testMove(cards.get(k));
if (futureStateLevel2 != null) { // if move is valid
for (int m = 0; m < nCards; m++) {
if (m != i && m != k) {
GameState futureStateLevel3 = futureStateLevel2.testMove(cards.get(m));
if (futureStateLevel3 != null) { // if move is valid
score = negamaxSuche(-player, futureStateLevel3, depthLeft-1, -beta, -alpha);
if (score >= beta) {
return score;
}
if (score > alpha) {
alpha = score; // alpha acts like max
}
}
}
}
}
}
}
}
}
return alpha;
}
}
}
Esto parece funcionar bien, pero para una profundidad de 1 (depthLeft=1), el programa ya tiene que calcular movimientos (50.000) tarjetas colocadas en promedio. Esto es demasiado, por supuesto!
Así que mis preguntas son:
- es la implementación correcta en absoluto? ¿Puedes simular un juego como este? En cuanto a la información imperfecta, especialmente?
- ¿Cómo se puede mejorar el algoritmo de velocidad y carga de trabajo?
- ¿Puedo, por ejemplo, reducir el conjunto de posibles movimientos a un conjunto aleatorio del 50% para mejorar la velocidad, manteniendo buenos resultados?
- Encontré UCT algorithm para ser una buena solución (tal vez). ¿Conoces este algoritmo? ¿Me puedes ayudar a implementarlo?
Hmm, con respecto al minimaxing cerca del final del juego. En ese punto, sabes que necesitas x trucos para ganar. Cualquier mundo en el que no puedas (no debería) ganar puedes ignorarlo. Porque si ese mundo está bien, entonces has perdido de todos modos. Si basa sus probabilidades en los mundos que conducen a ganar (esencialmente utilizando ilusiones), entonces probablemente pueda reducir aún más la búsqueda. – Cruncher