Использование минимаксного поиска для карточных игр с несовершенной информацией

Я хочу использовать минимаксный поиск (с отсечкой альфа-бета) или, скорее, поиск negamax, чтобы компьютерная программа играла в карточную игру.

Карточная игра на самом деле состоит из 4 игроков. Поэтому, чтобы иметь возможность использовать минимакс и т. Д., Я упрощаю игру домне" против "другие», После каждогопереехать"Вы можете объективно прочитать текущее состояние "Оценка от самой игры. Когда все 4 игрока поместили карту, высший выигрывает их всех - и карты значения рассчитываются.

Как ты неЯ не знаю, как точно распределены карты между тремя другими игроками, я подумал, что вы должны смоделировать все возможные распределения ("миры») с картами, которые не являются вашими. У вас есть 12 карт, у остальных 3 игроков всего 36 карт.

Так что мой подход заключается в этом алгоритме, гдеplayer это число от 1 до 3, обозначающее трех компьютерных игроков, для которых программе может понадобиться найти ходы. А также-player выступает за противников, а именно всех трех других игроков вместе.

private Card computerPickCard(GameState state, ArrayList 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 cards;
    if (player >= 1 && player  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;
        }
    }
}

Вроде нормально работает, но на глубину 1 (depthLeft=1), программе уже нужно рассчитать в среднем 50 000 ходов (размещенных карт). Это слишком много, конечно!

Итак, мои вопросы:

Корректна ли реализация вообще? Можете ли вы смоделировать такую игру? Что касается несовершенной информации, особенно?Как можно улучшить алгоритм по скорости и рабочей нагрузке?Могу ли я, например, уменьшить набор возможных ходов до случайного набора в 50%, чтобы повысить скорость при сохранении хороших результатов?я нашелАлгоритм UCT быть хорошим решением (возможно). Вы знаете этот алгоритм? Можете ли вы помочь мне реализовать это?