El uso de minimax de búsqueda para tarjeta de juegos con información imperfecta
https://stackoverflow.com//questions/12666119
-
11-12-2019 - |
italiano
english
français
española
中国
日本の
العربية
Deutsch
한국어
Português
RussianPregunta
Quiero usar minimax de búsqueda (con alfa-beta de la poda), o más bien negamax de búsqueda, hacer un programa de ordenador jugar un juego de cartas.
El juego de cartas, en realidad consta de 4 jugadores.Así que para ser capaz de utilizar minimax etc., Yo simplificar el juego del "yo" frente a los "otros".Después de cada "movimiento", que objetivamente puede leer el estado actual de la evaluación en el propio juego.Cuando todos 4 los jugadores han colocado la tarjeta, el más alto gana de todos ellos - y las tarjetas' recuento de los valores.
Como usted no sabe cómo la distribución de las tarjetas entre los otros 3 jugadores es exactamente, yo pensaba que usted debe simular todas las posibles distribuciones ("mundos") con las tarjetas que no son suyas.Tiene 12 tarjetas, los otros 3 jugadores de 36 cartas en total.
Así que mi planteamiento es este algoritmo, donde player es un número entre el 1 y el 3 simboliza los tres jugadores del equipo que el programa puede ser que necesite para encontrar movimientos.Y -player stands para los opositores, es decir, todos los otros tres jugadores.
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 debe calcular de 50.000 movimientos (coloca las tarjetas) en promedio.Esto es demasiado, ¡por supuesto!
Así que mis preguntas son:
- Es la aplicación correcta en todo?Se puede simular un juego como este?Con respecto a la información imperfecta, especialmente?
- ¿Cómo se puede mejorar el algoritmo de la velocidad y de la carga de trabajo?
- Puedo, por ejemplo, reducir el conjunto de movimientos posibles para un conjunto aleatorio de 50% para mejorar la velocidad, manteniendo buenos resultados?
- He encontrado UCT algoritmo para ser una buena solución (tal vez).¿Sabe usted de este algoritmo?Me puedes ayudar a implementarlo?
Solución
Minimax Búsqueda Como ha implementado, es el enfoque incorrecto para los juegos donde hay tanta incertidumbre. Dado que no conoce la distribución de tarjetas entre los otros jugadores, su búsqueda gastará una cantidad exponencial de tiempo que explore los juegos que no podrían suceder dada la distribución real de las tarjetas.
Creo que un mejor enfoque sería comenzar con buenas reglas para jugar cuando tenga poca o ninguna información sobre las manos de los otros jugadores. Cosas como:
- Si juegas primero en una ronda, toca tu tarjeta más baja, ya que tienes pocas posibilidades de ganar la ronda.
- Si juegas al último en una ronda, toca tu tarjeta más baja que ganará la ronda. Si no puedes ganar la ronda, entonces toca tu tarjeta más baja.
Inicialmente, no se moleste en la búsqueda de la búsqueda y solo juegue por estas reglas y haga que se asuma que todos los demás jugadores también usarán estas heurísticas. Como el programa observa la primera y la última. Los jugadores de cada juego de la ronda pueden acumular una tabla de información sobre las tarjetas, cada jugador es probable que tenga. P.ej. Un 9 habría ganado esta ronda, pero el jugador 3 no lo jugó, así que no debe tener tarjetas 9 o más. A medida que la información se recopila sobre la mano de cada jugador, el espacio de búsqueda finalmente se limitará al punto en que una búsqueda de miniMax de los posibles juegos podría producir información útil sobre la próxima tarjeta para jugar.
Otros consejos
Quiero aclarar detalles que el aceptado la respuesta en realidad no ir en.
En muchos juegos de cartas se puede degustar el desconocido cartas que tu oponente podría tener lugar de generar todos ellos.Usted puede tomar en cuenta la información como corto trajes y la probabilidad de que la celebración de ciertas tarjetas de juego hasta ahora al hacer este muestreo de peso la probabilidad de cada posible de la mano (cada mano es un mundo posible en el que vamos a resolver de forma independiente).A continuación, resolver cada mano usando perfecto de búsqueda de información.El mejor movimiento a través de todos estos mundos es a menudo el mejor movimiento en general - con alguna salvedad.
En juegos como el Póker esto no funciona muy bien ... el juego es todo acerca de la información oculta.Tienes que precisamente el balance de sus acciones para mantener la información acerca de tu mano oculta.
Pero, en juegos como el truco basado en los juegos de cartas, esto funciona bastante bien, particularmente desde que la nueva información se revela todo el tiempo.Muy bueno los jugadores tienen una buena idea de lo que todo el mundo tiene de todos modos.Así que, razonablemente fuerte Skat y el Puente de los programas se han basado en estas ideas.
Si usted puede resolver completamente el subyacente mundo, que es el mejor, pero si usted no puede, usted puede utilizar minimax o UCT para elegir la mejor jugada en cada mundo.También hay algoritmos híbridos (ISMCTS) que se trate de mezclar este proceso juntos.Ser cuidadoso acerca de las afirmaciones aquí.Simple de los métodos de muestreo son más fáciles de código, se debe intentar el enfoque más sencillo antes de una más compleja.
Aquí están algunos de los trabajos de investigación que le dan algo más de información sobre cuando el enfoque de muestreo a la información imperfecta ha funcionado bien:
Entender el Éxito de la Información Perfecta de Monte Carlo de Muestreo en el Juego Árbol de Búsqueda (En este trabajo se analiza cuando el enfoque de muestreo es probable que funcione.)
Mejorar el Estado de la Evaluación, Inferencia, y la Búsqueda de Truco Basado en los Juegos de cartas (Este documento describe el uso de muestreo en Skat)
Información imperfecta en un computacionalmente difícil juego (Este documento se describe el muestreo, en el Puente)
Información De Monte Carlo Árbol De Búsqueda (Este trabajo combina el muestreo y la UCT/Monte Carlo Árbol de Búsqueda para evitar los problemas en la primera referencia.)
El problema con la regla de los enfoques basados en la aceptan, la respuesta es que ellos no pueden tomar ventaja de los recursos computacionales, más allá de la necesaria para crear las reglas iniciales.Además, la regla de los enfoques basados estará limitado por el poder de las reglas que se puede escribir.La búsqueda de enfoques basados pueden usar el poder de la combinatoria de búsqueda para producir mucho más fuerte que el autor del programa.
