Chcę użyć wyszukiwania minimax (z przycinaniem alfa-beta), lub raczej wyszukiwania negamax, aby program komputerowy zagrał w grę karcianą.Używanie wyszukiwania minimax dla gier karcianych z niedoskonałymi informacjami
Gra karciana składa się w rzeczywistości z 4 graczy. Aby móc korzystać z minimax itp., Upraszczam grę "mnie" przeciw "innym". Po każdym "ruchu" możesz obiektywnie odczytać ocenę aktualnego stanu z samej gry. Kiedy wszyscy 4 gracze umieścili kartę, najwyższy wygrywa je wszystkie - a wartości kart liczą się.
Ponieważ nie wiesz, w jaki sposób dzieli się karty pomiędzy pozostałymi 3 graczami, pomyślałem, że musisz symulować wszystkie możliwe dystrybucje ("światy") z kartami, które nie są twoje. Masz 12 kart, pozostałe 3 graczy ma łącznie 36 kart.
Tak więc moim podejściem jest ten algorytm, w którym player jest liczbą od 1 do 3 symbolizującą trzy odtwarzacze komputerowe, których program może potrzebować, aby znaleźć ruchy. I -player oznacza przeciwników, a mianowicie wszystkich pozostałych trzech graczy razem.
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;
}
}
}
To wydaje się działać prawidłowo, ale na głębokości 1 (depthLeft=1), program już musi obliczyć 50.000 ruchów (umieszczone cards) na średniej. To oczywiście za dużo!
Więc moje pytania to:
- jest realizacja poprawne w ogóle? Czy możesz symulować taką grę? Co do niedoskonałych informacji, szczególnie?
- Jak ulepszyć algorytm prędkości i obciążenia pracą?
- Czy mogę na przykład zmniejszyć zestaw możliwych ruchów do losowego zestawu 50%, aby poprawić prędkość, zachowując przy tym dobre wyniki?
- Znalazłem UCT algorithm jako dobre rozwiązanie (może). Czy znasz ten algorytm? Czy możesz pomóc mi go wdrożyć?
Hmm, w odniesieniu do minimaxingu pod koniec gry. W tym momencie wiesz, że potrzebujesz x trików, aby wygrać. Każdy świat, w którym nie możesz (nie powinien) wygrać, możesz zignorować. Bo jeśli ten świat ma rację, i tak przegrałeś. Jeśli opierasz swoje prawdopodobieństwa na światach, które prowadzą do wygranej (zasadniczo używając myślenia życzeniowego), możesz prawdopodobnie przyciąć wyszukiwanie jeszcze bardziej – Cruncher